剑指offer 后篇

2017-08-18  本文已影响0人  Cracks_Yi

1.丑数

把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

下一个丑数一定是前面某个丑数乘以2或者3或者5能得到的最小值,对应乘2、3、5的丑数分别记为p、q、r,看2p、3q、5r哪个数比较小,就是下一个丑数。比如说如果最小的是2p,下一个丑数就是这个数,更新p为p后一个丑数。注意,可能存在有不止一个数同时最小,这样的话对应都要更新。

public int GetUglyNumber_Solution(int index) {
    
    if(index == 0) return 0;
    
    int[] uglyNumbers = new int[index];
    uglyNumbers[0] = 1;
    
    int i2 = 0, i3 = 0, i5 = 0;
    
    for(int i = 1; i < index; i++){
        int m2 = uglyNumbers[i2] * 2;
        int m3 = uglyNumbers[i3] * 3;
        int m5 = uglyNumbers[i5] * 5;
        
        int min = Math.min(Math.min(m2,m3),m5);
        uglyNumbers[i] = min;
        
        if(min == m2) i2++;
        if(min == m3) i3++;
        if(min == m5) i5++;
     
    }
    
    return uglyNumbers[index-1];   
}

2.第一个只出现一次的字符

在一个字符串(1<=字符串长度<=10000,全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置

public int FirstNotRepeatingChar(String str) {
    if(str == null || str == "") return -1;
    
    HashMap<Character,Boolean> map = new HashMap();
    
    for(int i = 0; i < str.length(); i++){
        char ch = str.charAt(i);
        if(map.containsKey(ch)){
            if(map.get(ch)) map.put(ch,false);
        }else{
            map.put(ch,true);
        }
    }
    
    for(int i = 0; i < str.length(); i++){
        char ch = str.charAt(i);
        if(map.get(ch)) return i;
    }
    
    return -1;      
}

3.数组中的逆序对

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

4.两个链表的第一个公共结点

输入两个链表,找出它们的第一个公共结点。

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    
    ListNode p1 = pHead1;
    ListNode p2 = pHead2;
    
    int count1 = 0, count2 = 0;
    while(p1 != null){
        count1++;
        p1 = p1.next;
    }
    
    while(p2 != null){
        count2++;
        p2 = p2.next;
    }
    
   
    p1 = pHead1;
    p2 = pHead2;
    
    for(int i = 0; i < Math.abs(count1 - count2); i++){
        if(count1 > count2) p1 = p1.next;
        else p2 = p2.next;
    }
    
    while(p1 != null && p2 != null){
        if(p1 == p2) return p1;
        p1 = p1.next;
        p2 = p2.next;
    }
    
    return null;   
}

5.数字在排序字母中出现的次数

统计一个数字在排序数组中出现的次数。

看有序数组就想到二分查找,找到最小和最大的index。最要注意的是当high与low相差1时mid取哪个数的问题,把特殊情况拿出来。

public class Solution {
    public int GetNumberOfK(int [] array , int k) {

        int lower = getLower(array, k, 0, array.length - 1);
        int upper = getUpper(array, k, 0, array.length - 1);

        if(lower != -1 && upper != -1) return upper - lower + 1;
        return 0;
    }

    public int getLower(int[] array, int k, int low, int high){

        if(low > high) return -1;

        int mid = (low + high) / 2;
        if(k == array[mid]){
            if(low == mid) return mid;
            else return getLower(array, k, low, mid);
        }
        else if(k > array[mid]) return getLower(array, k, mid + 1, high);
        else return getLower(array, k, low, mid - 1);

    }

    public int getUpper(int [] array, int k, int low, int high){

        int mid = (low + high) / 2;
        while(low <= high){
            mid = (low + high) / 2;
            if(array[mid] == k){
                if(array[high] == k) return high;
                if(high - 1 == mid) return mid;
                else low = mid;
            }else if(array[mid] > k) high = mid - 1;
            else low = mid + 1;
        }

        return -1;     
    }
}

6.二叉树的深度

输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。

public int TreeDepth(TreeNode root) {
    if(root == null) return 0;
    
    int left = TreeDepth(root.left);
    int right = TreeDepth(root.right);
    
    return 1 + (left > right ? left : right);      
}

7.平衡二叉树

输入一棵二叉树,判断该二叉树是否是平衡二叉树。

 public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
       return getDepth(root) != -1;
    }


    public int getDepth(TreeNode root){
        if(root == null) return 0;

        int left = getDepth(root.left);
        int right = getDepth(root.right);

        if(left == -1 || right == -1) return -1;

        if(left - right > 1 || right - left > 1) return -1;

        return 1 + (left > right ? left : right);
    }
}

8. 数组中只出现一次的数字

一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

一个思路是HashSet,遍历数组,第一次出现先放入set,再次出现移除该元素,最后剩2个元素。

另一个思路是用异或,基于两个规则:两个相同的数异或为0,0异某数等于该数。于是将所有数异或的结果为两个只出现一次的数异或的结果,并且出现1的位置表示此位不同。根据第一次出现1的那一位是取0或者1把数组分为2份,每一份都包含一个出现一次的数和若干个出现2次的数,这样就可以分别算出这两个出现一次的数是多少了。

public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
    HashSet<Integer> set = new HashSet<Integer>();
    
    for(int elem: array){
        if(set.contains(elem)){
            set.remove(elem);
        }else{
            set.add(elem);
        }
    }
    
    Iterator iter = set.iterator();
    num1[0] = (int)iter.next();
    num2[0] = (int)iter.next();
}

9.和为S的连续正数序列

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

输出所有和为S的连续正数序列。序列内按照从小至大的顺序,序列间按照开始数字从小到大的顺序

设x~y有k个数,k = y - x + 1,
所以sum = (x + y) * k / 2 = (x + y)(y - x + 1) / 2。
进一步化简得y(y+1) = 2sum + xx - x,如果确定一个x,则右边为常数。检查右边开根号后向下取整和向上取整的乘积是否等于右边。
满足x < y 且 x、y均为正整数。

public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
    
    ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();

    sum = 2 * sum;
    
    int x = 1;
    int y;
    
    while(true){
        int c = sum + x * x - x;
        double cSqrt = Math.sqrt(c);
        y = (int)Math.floor(cSqrt);
        if(x >= y) return list;
        if(y * (y + 1) == c){
            ArrayList<Integer> temp = new ArrayList<Integer>();
            for(int i = x; i <= y; i++){
                temp.add(i);
            }
            list.add(temp);
        } 
        x++;
    }       
}

10.和为S的两个数字

输入一个递增排序的数组和一个数字S,在数组中查找两个数,是的他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。

跟leetcode上的第一题2sum差不多,用hashSet解决,因为哈希表查找时间复杂度是O(1)。不一样的是可能存在多个解,每次出一对新结果都要跟上一次结果比较;也可能不存在解,用一个标记判断解的存在。

public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
    
    
    ArrayList<Integer> list = new ArrayList<Integer>();
    
    HashSet<Integer> set = new HashSet<Integer>();
    
    boolean found = false;
    int first = 0, second = 0;
    
    for(int elem: array){
        if(set.contains(sum - elem)){
            if((!found) || (found && first * second > elem * (sum - elem))){ 
                first = sum - elem;
                second = elem;    
            }
            found = true;
        }
        set.add(elem);
    }
    
    if(found){
        list.add(first);
        list.add(second);
    }
    
    return list;       
}

11.左旋转字符串

汇编语言中有一种移位指令叫做循环左移(ROL),现在有个简单的任务,就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S,请你把其循环左移K位后的序列输出。例如,字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果,即“XYZdefabc”。是不是很简单?OK,搞定它!

public String LeftRotateString(String str,int n) {
    
    if(n == 0) return str;
    if(str == null || str.length() < n) return "";
    
    String first = str.substring(0,n);
    String second = str.substring(n);
    
    return second + first;
        
}

12.翻转单词顺序列

牛客最近来了一个新员工Fish,每天早晨总是会拿着一本英文杂志,写些句子在本子上。同事Cat对Fish写的内容颇感兴趣,有一天他向Fish借来翻看,但却读不懂它的意思。例如,“student. a am I”。后来才意识到,这家伙原来把句子单词的顺序翻转了,正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行,你能帮助他么?

public class Solution {
    public String ReverseSentence(String str) {
        if(str.trim().equals("")){
            return str;
        }
        String res = "";
        String[] words = str.split(" ");
        for(int i = words.length - 1; i >= 1; i--){
            res += words[i] + " ";
        }
        res += words[0];
        return res;
    }
}

13.扑克牌顺子

LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张_)...他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿!!“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何。如果牌能组成顺子就输出true,否则就输出false。为了方便起见,你可以认为大小王是0。

不考虑大小王,如果一个牌是顺子那么按大小排序后相邻间隔都为1;
如果一个牌是顺子那么加上大小王也能构成顺子,如果一个牌排序后总间隔不大于大小王数量,那么就可以把大小王插入其中形成顺子。

import java.util.*;

public class Solution {
    public boolean isContinuous(int [] numbers) {
        if(numbers == null || numbers.length != 5){
            return false;
        }
        int num0 = 0;
        Arrays.sort(numbers);
        int i = 0;
        while(i < numbers.length){
            if(numbers[i] == 0){
                num0++;
                i++;
            }else{
                break;
            }
        }
        for(; i < numbers.length - 1; i++){
            int gap = numbers[i+1] - numbers[i];
            if(gap < 1){
                return false;
            }else{
                num0 -= (gap - 1);
                if(num0 < 0){
                    return false;
                }
            }
        }
        return true;
    }
}

14.孩子们的游戏

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!_)。请你试着想下,哪个小朋友会得到这份礼品呢?(注:小朋友的编号是从0到n-1)

用链表模拟这个环,注意第二个for循环里面i<m-2。

public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if(n < 2 || m <= 0){
            return -1;
        }
        ListNode head = new ListNode(0);
        ListNode p = head;
        for(int i = 1; i < n; i++){
            p.next = new ListNode(i);
            p = p.next;
        }
        p.next = head;
        while(head.next != head){
            for(int i = 0; i < m-2; i++){
                head = head.next;
            }
            head.next = head.next.next;
            head = head.next;
        }
        return head.val;
    }
}

或者用数组或可变LIST来模拟这个情况。

15.求1+2+3+...+n

求1+2+3+...+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。

public int Sum_Solution(int n) {
    int sum = 0;
    Boolean b = (n>0) && ((sum = Sum_Solution(n-1) + n) > 0;
    return sum;  
}

16.不用加减乘除做加法

写一个函数,求两个整数之和,要求在函数体内不得使用+、-、*、/四则运算符号。

17.把字符串转换成整数

将一个字符串转换成一个整数,要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。

倒着遍历字符串中的字符,按位累加起来,第一个字符可能为符号“+”或"-"要单独处理。第一个字符不应为0,但我没设这个条件时仍然通过了,说明测试并不严密吧。

public class Solution {
    public int StrToInt(String str) {
        
        if (str == null) return 0;
        int len = str.length();
        if(len == 0) return 0;
        
        int sum = 0;
        int i = 0;
        for(; i < len - 1; i++){
            char ch = str.charAt(len - i - 1);
            if(ch < '0' || ch > '9'){
                return 0;
            }
            
            int digit = ch - '0';
            sum += digit * pow(10,i);
        }
        
        char ch = str.charAt(0);
        
        if(ch == '-') return sum * (-1);
        if(ch == '+') return sum;
        if(ch > '0' && ch <= '9'){
            int digit = ch - '0';
            return sum + digit * pow(10,i);
        } 
        
        return 0;   
        
    }
    
    
    public int pow(int base ,int k){
        if(k == 0) return 1;
        return pow(base, k-1) * base;
    }
}

18.数组中重复的数字

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。

    public boolean duplicate(int numbers[],int length,int [] duplication) {
        
        if(length == 0) return false;
        
        int[] copy = new int[length];
        
        for(int number : numbers){
            if(number < 0 || number > length - 1) return false;
            if(copy[number] == 0){
                copy[number] = 1;
            }else{
                duplication[0] = number;
                return true; 
            }
        }
        
        return false;
    }
}

19.构建乘积数组

给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]。不能使用除法。
解决思路是记录两个数组forward和backward,分别从前往后作乘积和从后往前做乘积。

import java.util.ArrayList;
public class Solution {
    public int[] multiply(int[] A) {
        
        if(A == null || A.length == 0 || A.length == 1) return A;
        int n = A.length;
        int[] B = new int[n];
        int[] forward = new int[n];
        int[] backward = new int[n];
        
        forward[0] = 1;
        backward[0] = 1;
        
        for(int i = 1; i < n; i++){
            forward[i] = forward[i - 1] * A[i - 1];
            backward[i] = backward[i - 1] * A[n - i];
        }
        
        for(int i = 0; i < n; i++){
            B[i] = forward[i] * backward[n - i - 1];
        }
        
        return B;
        
    }
}

或者B[i] = forward[i] * backward[i]

import java.util.ArrayList;
public class Solution {
    public int[] multiply(int[] A) {
        
        if(A == null || A.length == 0 || A.length == 1) return A;
        int n = A.length;
        int[] B = new int[n];
        int[] forward = new int[n];
        int[] backward = new int[n];
        
        forward[0] = 1;
        backward[n-1] = 1;
        
        for(int i = 1; i < n; i++){
            forward[i] = forward[i - 1] * A[i - 1];            
        }
        
        for(int i = n - 2; i >= 0; i--){
            backward[i] = backward[i + 1] * A[i + 1]; 
        }
        
        for(int i = 0; i < n; i++){
            B[i] = forward[i] * backward[i];
        }
        
        return B;
        
    }
}

20.正则表达式匹配

请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示任意一个字符,而''表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"abaca"匹配,但是与"aa.a"和"ab*a"均不匹配


二叉树的下一个结点

给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

如果该节点有右子树,则下一个节点是右子树的最左节点;
如果该节点没有右子树,则:
  如果该节点是爸爸的左子树,则下一个节点是爸爸,如果不是就继续向上直到寻找到某个祖先是它的爸爸的左子树为止,则此爸爸是下一个节点。如果一直都没找到这样的说明到了最后一个,返回NULL。

/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if(pNode == null){
            return null;
        }
        if(pNode.right != null){
            pNode = pNode.right;
            while(pNode.left!= null){
                pNode = pNode.left;
            }
            return pNode;
        }else{
            while(pNode.next != null){
                TreeLinkNode pTempNode = pNode;
                pNode = pNode.next;
                if(pNode.left == pTempNode){
                    return pNode;
                }
            }
        }
        return null;
    }
}


对称的二叉树

请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    boolean isSymmetrical(TreeNode pRoot)
    {
        if(pRoot == null){
            return true;
        }
        return judge(pRoot.left, pRoot.right);
    }
    
    boolean judge(TreeNode tLeft, TreeNode tRight){
        if(tLeft == null && tRight == null){
            return true;
        }else if(tLeft != null && tRight != null && tLeft.val == tRight.val){
            return judge(tLeft.left, tRight.right) && judge(tLeft.right, tRight.left);
        }else{
            return false;
        }
    }
}

按之字型顺序打印二叉树

请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。

栈先进后出的特点正好能实现每一次的反转,从左到右顺序的下一代也是从左到右(先左子树后右子树),从右到左顺序的下一代是从右到左(先右子树后左子树),按这个顺序再传递给下一个stack,读取时即实现反转。所以一次迭代是从左到右读一次再从右到左读一次。

import java.util.ArrayList;
import java.util.Stack;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if(pRoot == null){
            return res;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        Stack<TreeNode> reverseStack = new Stack<TreeNode>();
        stack.push(pRoot);
        while(!stack.isEmpty()){
            ArrayList<Integer> arr = new ArrayList<Integer>();
            while(!stack.isEmpty()){
                TreeNode node = stack.pop();
                arr.add(node.val);
                if(node.left != null){
                    reverseStack.push(node.left);
                }
                if(node.right != null){
                    reverseStack.push(node.right);
                }
            }
            res.add(arr);
            ArrayList reverseArr = new ArrayList<Integer>();
            if(reverseStack.isEmpty()){
                break;
            }
            while(!reverseStack.isEmpty()){
                TreeNode node = reverseStack.pop();
                reverseArr.add(node.val);
                if(node.right != null){
                    stack.push(node.right);
                }
                if(node.left != null){
                    stack.push(node.left);    
                }
            }
            res.add(reverseArr);         
        }
        return res;
    }
}

把二叉树打印成多行

从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行

import java.util.ArrayList;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if(pRoot == null){
            return res;
        }
        ArrayList<TreeNode> arr = new ArrayList<TreeNode>();
        ArrayList<TreeNode> nextArr = new ArrayList<TreeNode>();
        arr.add(pRoot);
        while(!arr.isEmpty()){
            ArrayList<Integer> current = new ArrayList<Integer>();
            for(TreeNode node : arr){
                current.add(node.val);
                if(node.left != null){
                    nextArr.add(node.left);
                }
                if(node.right != null){
                    nextArr.add(node.right);
                }
            }
            arr.clear();
            for(TreeNode node : nextArr){
                arr.add(node);
            }
            nextArr.clear();
            res.add(current);
        }
        return res;        
    }  
}

序列化二叉树

请实现两个函数,分别用来序列化和反序列化二叉树
二叉树的序列化是指:把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串,从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改,序列化的结果是一个字符串,序列化时通过 某种符号表示空节点(#),以 ! 表示一个结点值的结束(value!)。
二叉树的反序列化是指:根据某种遍历顺序得到的序列化字符串结果str,重构二叉树。

题目没看懂


二叉搜索树的第K个结点

给定一棵二叉搜索树,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4。

二叉搜索树中左节点<父节点<右节点,所以中序遍历即是按从小到大来遍历,再取第K个值即可。

import java.util.ArrayList;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {     
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        ArrayList<TreeNode> arr = new ArrayList<TreeNode>();
        traverse(pRoot, arr);
        if(k < 1){
            return null;
        }
        if(k <= arr.size()){
            return arr.get(k-1);
        }
        return null;
    }
    
    public void traverse(TreeNode pRoot, ArrayList<TreeNode> arr){
        if(pRoot == null){
            return;
        }
        traverse(pRoot.left, arr);
        arr.add(pRoot);
        traverse(pRoot.right, arr);
    }
}

但是这样的话就多花了时间和存储空间,因为过程中如果遍历到第K个就可以停止了,所以改一下代码为:

import java.util.ArrayList;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {   
    int count = 0;
    TreeNode KthNode(TreeNode pRoot, int k)
    {  
        if(pRoot == null){
            return null;
        }       
        TreeNode node = KthNode(pRoot.left, k);
        if(node != null){
            return node;
        }
        count++;
        if(k == count){
            return pRoot;
        } 
        node = KthNode(pRoot.right, k);
        if(node != null){
            return node;
        }        
        return null;      
    } 
    
}

数据流的中位数

如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流,使用GetMedian()方法获取当前读取数据的中位数。


滑动窗口的最大值

给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3,那么一共存在6个滑动窗口,他们的最大值分别为{4,4,6,6,6,5}; 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个: {[2,3,4],2,6,2,5,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5,1}, {2,3,4,[2,6,2],5,1}, {2,3,4,2,[6,2,5],1}, {2,3,4,2,6,[2,5,1]}。

暴力解法用python写实在是很简单。

# -*- coding:utf-8 -*-
class Solution:
    def maxInWindows(self, num, size):
        res = []
        if size <= 0:
            return res
        for i in range(len(num)-size+1):
            res.append(max(num[i:i+size]))
        return res

还有一个双端队列解法没看懂。。。


矩阵中的路径


机器人的运动范围

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18。但是,它不能进入方格(35,38),因为3+5+3+8 = 19。请问该机器人能够达到多少个格子?

public class Solution {
    int count = 0;
    public int movingCount(int threshold, int rows, int cols)
    {
        boolean[][] visited = new boolean[rows][cols];
        forward(threshold, rows, cols, 0, 0, visited);
        return count;
    }
    
    public void forward(int threshold, int rows, int cols, int row, int col, boolean[][] visited){
        if(row >= 0 && row < rows && col >= 0 && col < cols && 
           !visited[row][col] && sum(row) + sum(col) <= threshold){
            visited[row][col] = true;
            count++;
            forward(threshold, rows, cols, row - 1, col, visited);
            forward(threshold, rows, cols, row + 1, col, visited);
            forward(threshold, rows, cols, row, col - 1, visited);
            forward(threshold, rows, cols, row, col + 1, visited);
        }
        
    }
    
    private int sum(int x){
        int res = 0;
        int temp = x;
        while(temp > 0){
            res += temp % 10;
            temp /= 10;
        }
        return res;
    }
}


剪绳子

给你一根长度为n的绳子,请把绳子剪成整数长的m段(m、n都是整数,n>1并且m>1),每段绳子的长度记为k[0],k[1],...,k[m]。请问k[0]xk[1]x...xk[m]可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。

典型的动态规划题,cutRope(target) = max(cutRope(target-j)*j),当target == 2时是一个例外情况,因为它作为target较大时分解为一个2与另外的数相乘最好,但是target等于2时必须分成1**1。

public class Solution {
    public int cutRope(int target) {
        if(target == 2){
            return 1;
        }
        int[] max_mal = new int[target+1];
        max_mal[1] = 1;
        max_mal[2] = 2;
        for(int i = 3; i < target+1; i++){
            int temp_max = 1;
            for(int j = 1; j < i; j++){
                int temp = max_mal[j] * (i-j);
                if(temp > temp_max){
                    temp_max = temp;
                }
            }
            max_mal[i] = temp_max;         
        }     
        return max_mal[target]; 
    }
}
上一篇 下一篇

猜你喜欢

热点阅读