LintCode/牛客网：剑指Offer

第1章：

9.Fizz Buzz ：http://www.lintcode.com/zh-cn/problem/fizz-buzz/

解法1：(% String.valueOf)

(1.rst; 2.for(1,n),15,5,3,else; 3.return)

 1 public class Solution {
 2     public List<String> fizzBuzz(int n) {
 3         List<String> rst = new ArrayList<>();
 4         for (int i = 1; i <= n; i++) {
 5             if (i % 15 == 0) rst.add("FizzBuzz");
 6             else if (i % 5 == 0) rst.add("Buzz");
 7             else if (i % 3 == 0) rst.add("Fizz");
 8             else rst.add(String.valueOf(i));
 9         }
10         return rst;
11     }
12 }

View Code

解法2：(利用两个变量fizz和buzz计数，为3、5的时候则add Fizz和Buzz并清零。不需要使用%)

 1 public class Solution {
 2     public List<String> fizzBuzz(int n) {
 3         List<String> ret = new ArrayList<String>(n);
 4         for(int i=1,fizz=0,buzz=0;i<=n ;i++){
 5             fizz++;
 6             buzz++;
 7             if(fizz==3 && buzz==5){
 8                 ret.add("FizzBuzz");
 9                 fizz=0;
10                 buzz=0;
11             }else if(fizz==3){
12                 ret.add("Fizz");
13                 fizz=0;
14             }else if(buzz==5){
15                 ret.add("Buzz");
16                 buzz=0;
17             }else{
18                 ret.add(String.valueOf(i));
19             }
20         } 
21         return ret;
22     }
23 }

View Code

第2章：

366.Fibonacci: http://www.lintcode.com/en/problem/fibonacci/

解法：<Iterative><Two Pointers>(指针a指向第一个数，指针b指向第2个数，for循环a,b分别向后移动，返回a)

(1.a,b; 2.for(1,n),tmp,b,a; 3.return)

 1 class Solution {
 2     /**
 3      * @param n: an integer
 4      * @return an integer f(n)
 5      */
 6     public int fibonacci(int n) {
 7         // write your code here
 8         int a = 0, b = 1;
 9         for (int i = 1; i < n; i++) {
10             int tmp = b;
11             b = a + b;
12             a = tmp;
13         }
14         return a;
15     }
16 }

View Code

204.Singleton: http://www.lintcode.com/en/problem/singleton/

单例：

 1 class Solution {
 2     /**
 3      * @return: The same instance of this class every time
 4      */
 5     public static Solution instance = null;
 6     public static Solution getInstance() {
 7         if (instance == null) {
 8             instance = new Solution();
 9         }
10         return instance;
11     }
12 };

View Code

212.Space Replacement：http://www.lintcode.com/en/problem/space-replacement/

空格替换：

解法：<Two Pointers>(先for循环遍历得到newLen；i指向原数组从后向前移动，j指向新数组从后向前移动。非space的时候就把i的值给j指向位置，遇到space的时候就依次是02%来替换。)

(1.cnt,for-if(); 2.newLen,j; 3.for(length-1),if()-[nL-j++]=[i]; 4.else-02%; 5.return)

 1 public class Solution {
 2     /**
 3      * @param string: An array of Char
 4      * @param length: The true length of the string
 5      * @return: The true length of new string
 6      */
 7     public int replaceBlank(char[] string, int length) {
 8         // Write your code here
 9         int cnt = 0;
10         for (int i = 0; i < length; i++) {
11             if (string[i] == ' ') cnt++;
12         }
13         int newLen = length + cnt * 2;
14         int j = 1;
15         for (int i = length - 1; i >= 0; i--) {
16             if (string[i] != ' ') {
17                 string[newLen - j++] = string[i];
18             }
19             else {
20                 string[newLen - j++] = '0';
21                 string[newLen - j++] = '2';
22                 string[newLen - j++] = '%';
23             }
24         }
25         return newLen;
26     }
27 }

View Code

public class Solution {
    /**
     * @param string: An array of Char
     * @param length: The true length of the string
     * @return: The true length of new string
     */
    public int replaceBlank(char[] string, int length) {
        // Write your code here
        int cnt = 0;
        for (int i = 0; i < length; i++) {
            if (string[i] == ' ') {
                cnt++;
            }
        }
        
        int newLen = length + 2 * cnt;
        int j = newLen - 1;
        for (int i = length - 1; i >= 0; i--) {
            if (string[i] != ' ') {
                string[j--] = string[i];
            } else {
                string[j--] = '0';
                string[j--] = '2';
                string[j--] = '%';
            }
        }
        return newLen;
    }
}

View Code

365.Count 1 in Binary: http://www.lintcode.com/en/problem/count-1-in-binary/

二进制中1的个数：<Bit Manipulation>

我的解法：(1.Integer.toBinaryString(num)--将十进制数字转为二进制字符串； 2.str.toCharArray()--将字符串转为字符数组；)

 1 public class Solution {
 2     /**
 3      * @param num: an integer
 4      * @return: an integer, the number of ones in num
 5      */
 6     public int countOnes(int num) {
 7         // write your code here
 8         String str = Integer.toBinaryString(num);
 9         char[] ch = str.toCharArray();
10         int cnt = 0;
11         for (int i = 0; i < ch.length; i++) {
12             if (ch[i] == '1') cnt++; 
13         }
14         return cnt;
15     }
16 };

View Code

解法2：(位运算；num-1的结果是最右边1(包括1)的后面所有数取反，其他不变。例如1100-1=1011，111-1=110；(num-1)&num的结果便是把最右边的1置零。)O(m)

 1 public class Solution {
 2     /**
 3      * @param num: an integer
 4      * @return: an integer, the number of ones in num
 5      */
 6     public int countOnes(int num) {
 7         // write your code here
 8         int cnt = 0;
 9         while (num != 0) {
10             num = num & (num - 1);
11             cnt++;
12         }
13         return cnt;
14     }
15 };

View Code

解法3：(位运算；num和1与: 最右为1则1，最右为0则0，只能判断最右位；num右移。1&1=1，1&0=0，0&0=0；带符号右移>>会把所有的位右移，正数补0，负数补1; 无符号右移>>>，所有位右移，第一位补零)O(n)

 1 public class Solution {
 2     /**
 3      * @param num: an integer
 4      * @return: an integer, the number of ones in num
 5      */
 6     public int countOnes(int num) {
 7         // write your code here
 8         int cnt = 0;
 9         while (num != 0) {
10             cnt += num & 1;
11             num = num >>> 1;
12         }
13         return cnt;
14     }
15 };

View Code

35. Reverse Linked List: http://www.lintcode.com/en/problem/reverse-linked-list/

反转链表：(四步：1.tmp保存下一节点； 2.head指向prev； 3.head移动； 4.prev移动)

(prev-head移动遍历 tmp先保存head.next, 然后变换prev和head的指针; prev初始化为null; 最后返回prev)

 1 public class Solution {
 2     /**
 3      * @param head: The head of linked list.
 4      * @return: The new head of reversed linked list.
 5      */
 6     public ListNode reverse(ListNode head) {
 7         // write your code here
 8         ListNode prev = null;
 9         while (head != null) {
10             ListNode tmp = head.next;
11             head.next = prev;
12             prev = head;
13             head = tmp;
14         }
15         return prev;
16     }
17 }

View Code

36.Reverse Linked Lis II: http://www.lintcode.com/en/problem/reverse-linked-list-ii/

反转链表II：(1-[2-3-4]-5; 1.首先把head移动到目标范围前一指针；2.然后left和right作为范围头指针；right继续移动到范围尾指针；prev记录right下一个数；3.循环(n-m+1)次；4.最后把head指向right；)

(四个指针 head-left-right-prev; 初始head指向前一个,prev指向后一个; for(n-m+1)反转 prev-left-tmp三个一组; 循环后head.next=right; 与反转链表I的区别只在于需要head记录头指针,right记录尾指针; I的perv指向后一个null, II的prev指向后一个right.next)(ps:也可以省略right指针,因为反转最后prev就指向范围的最后一个节点, 所以只要head.next=prev即可)

 1 public class Solution {
 2     public ListNode reverseBetween(ListNode head, int m, int n) {
 3         ListNode dummy = new ListNode(0);
 4         dummy.next = head;
 5         head = dummy;
 6         
 7         for (int i = 0; i < m - 1; i++) {
 8             head = head.next;
 9         }
10         ListNode left = head.next;
11         ListNode right = head.next;
12         for (int i = 0; i < n - m; i++) {
13             right = right.next;
14         }
15         ListNode prev = right.next;
16         for (int i = 0; i < n - m + 1; i++) {
17             ListNode tmp = left.next;
18             left.next = prev;
19             prev = left;
20             left = tmp;
21         }
22         head.next = right;
23         return dummy.next;
24     }
25 }

View Code

135.Find Minimum in Rotated Sorted Array：http://www.lintcode.com/en/problem/find-minimum-in-rotated-sorted-array/

寻找旋转排序数组中的最小值：(思想：找出第一个小于[lo]的值(lo非固定)；)

([2, 0, 1]; while(lo<hi)，1. 首先如果[lo]<[hi],则可返回；2.定义mid，如果[mid]>=[lo]，lo=mid+1；3.否则hi=mid；)

(注意判断[mid]=[lo]的情况，此时mid-lo-2，hi-0；显然是移动lo指针)

(而对于另一种写法是找出第一个小于[hi]的值；1相同；2.定义mid，如果[mid]>[hi]lo=mid+1; 否则hi=mid；好像不存在[mid]=[hi]的情况，因为[mid]是偏左的)

(本题mid只能定义为偏左，不然似乎写不出来)

<Binary Search>(二分搜索情况变化太复杂 while(</<=/+1<), if(>)mid/mid+1,else-mid/mid-1?)

解法1：(区间长度为1; while(<),if(>=)mid+1, else-mid, return lo; 改while/if任何一个部分都会wrong)

 1 public class Solution {
 2     /**
 3      * @param nums: a rotated sorted array
 4      * @return: the minimum number in the array
 5      */
 6     public int findMin(int[] nums) {
 7         // write your code here
 8         int lo = 0, hi = nums.length - 1;
 9         while (lo < hi) {
10             if (nums[lo] < nums[hi]) return nums[lo];
11             int mid = lo + (hi - lo) / 2;
12             if (nums[mid] >= nums[lo]) lo = mid + 1;
13             else hi = mid;
14         }
15         return nums[lo];
16     }
17 }

View Code

解法2：(区间长度为2; while(+1<), 如果lo<hi, 说明没有rotate，直接返回lo；如果lo>=mid，搜索右区间；否则搜索左区间。对于区间长度为2的情况，不用mid+1/-1；最后再判断lo和hi的值即可)

(1.lo,hi; 2.while(+1<),if(<)return; 3.mid,if(>=)-mid,else-mid; 4.return Math.min)

 1 public class Solution {
 2     /**
 3      * @param nums: a rotated sorted array
 4      * @return: the minimum number in the array
 5      */
 6     public int findMin(int[] nums) {
 7         // write your code here
 8         int lo = 0, hi = nums.length - 1;
 9         while (lo + 1 < hi) {
10             if (nums[lo] < nums[hi]) return nums[lo];
11             int mid = lo + (hi - lo) / 2;
12             if (nums[mid] >= nums[lo]) lo = mid;
13             else hi = mid;
14         }
15         return Math.min(nums[lo],nums[hi]);
16     }
17 }

View Code

73.Construct Binary Tree from Preorder and Inorder Traversal: http://www.lintcode.com/en/problem/construct-binary-tree-from-preorder-and-inorder-traversal/

根据前序遍历和中序遍历构造树：(TreeNode helper(in,pre,inS,inE,preS); 如果(pre>len||inS>inE)null; 找出in中位置；递归得出left,right)

解法1：<Recursive>(Pre[a/bde/cfg] In[dbe/a/fcg] Pre[0]是root，在In中找到a是In[3]那么In[3]左边是左子树，右边是右子树。Pre[1]是左子树的根节点，同样在In中找到b，左边是左子树，右边是右子树。)

(1.helper; 2.helper:in,pre,preS,inS,inE; 3.if(||)null,root,index; 4.for(inS,inE)-index; 5.helper;)

 1 public class Solution {
 2     /**
 3      *@param preorder : A list of integers that preorder traversal of a tree
 4      *@param inorder : A list of integers that inorder traversal of a tree
 5      *@return : Root of a tree
 6      */
 7     public TreeNode buildTree(int[] preorder, int[] inorder) {
 8         // write your code here
 9         return helper(preorder, inorder, 0, 0, inorder.length - 1);
10     }
11     public TreeNode helper(int[] pre, int[] in, int preStart, int inStart, int inEnd) {
12         if (preStart > pre.length || inStart > inEnd) return null;
13         TreeNode root = new TreeNode(pre[preStart]);
14         int index = 0;
15         for (int i = inStart; i <= inEnd; i++) {
16             if (in[i] == pre[preStart]) {
17                 index = i;
18                 break;
19             }
20         }
21         root.left = helper(pre, in, preStart + 1, inStart, index - 1);
22         root.right = helper(pre, in, preStart + index- inStart + 1, index + 1, inEnd);
23         return root;
24     }
25 }

View Code

改进：(HashMap保存index的值)

(todo)

类似：

106. Construct Binary Tree from Inorder and Postorder Traversal: https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

根据中序遍历和后序遍历构造树：(helper(in,post,inS,inE,postE); 如果(preE<0||inS>inE)null; 找出in中位置；递归；)

(helper参数: in, post, inS, inE, postE; 1.终止条件为(||) return null; 2.postEnd作为new root; 3.在inS到inE之间遍历出root的位置作为index; 4.递归)

(主要是搞清迭代的值的变化)

 1 public class Solution {
 2     public TreeNode buildTree(int[] inorder, int[] postorder) {
 3         return helper(inorder, postorder, postorder.length - 1, 0, inorder.length - 1);
 4     }
 5     public TreeNode helper(int[] in, int[] post, int postEnd, int inStart, int inEnd) {
 6         if (postEnd < 0 || inStart > inEnd) return null;
 7         TreeNode root = new TreeNode(post[postEnd]);
 8         int index = 0;
 9         for (int i = inStart; i <= inEnd; i++) {
10             if (in[i] == post[postEnd]) {
11                 index = i;
12                 break;
13             }
14         }
15         root.left = helper(in, post, postEnd - inEnd + index - 1, inStart, index - 1);
16         root.right = helper(in, post, postEnd - 1, index + 1, inEnd);
17         return root;
18     }
19 }

View Code

40.Implement Queue by Two Stacks：http://www.lintcode.com/en/problem/implement-queue-by-two-stacks/

用栈实现队列：(1.push-push到stack1中；2.pop-当stack2为空时(if),把stack1中的数push到stack2中(while),返回pop; 3.top-同pop,最后返回peek)

解法：(注意的是，只有当stack2为空时才把stack1里的值push到stack2里在peek/pop, 否则直接peek或者pop)

 1 public class Queue {
 2     private Stack<Integer> stack1;
 3     private Stack<Integer> stack2;
 4 
 5     public Queue() {
 6        // do initialization if necessary
 7        stack1 = new Stack<Integer>();
 8        stack2 = new Stack<Integer>();
 9     }
10     
11     public void push(int element) {
12         // write your code here
13         stack1.push(element);
14     }
15 
16     public int pop() {
17         // write your code here
18         if (stack2.empty() == true) {
19             while (!stack1.empty()) {
20                 stack2.push(stack1.pop());
21             }
22         }
23         return stack2.pop();
24     }
25 
26     public int top() {
27         // write your code here
28         if (stack2.empty() == true) {
29             while (!stack1.empty()) {
30                 stack2.push(stack1.pop());
31             }
32         }
33         return stack2.peek();
34     }
35 }

View Code

38.Search a 2D Matrix II：http://www.lintcode.com/en/problem/search-a-2d-matrix-ii/

二维矩阵tar值的个数(每行每列sorted)：(左下向右上移动)

我的解法：(默认每行没有重复值。for循环搜索每行首尾范围。范围内的行里二分搜索)

 1 public class Solution {
 2     /**
 3      * @param matrix: A list of lists of integers
 4      * @param: A number you want to search in the matrix
 5      * @return: An integer indicate the occurrence of target in the given matrix
 6      */
 7     public int searchMatrix(int[][] matrix, int target) {
 8         // write your code here
 9         int cnt = 0;
10         if (matrix.length == 0) return cnt;
11         int m = matrix.length, n = matrix[0].length;
12         for (int i = 0; i < m; i++) {
13             if (matrix[i][0] <= target && target <= matrix[i][n - 1]) {
14                 int start = 0, end = n - 1;
15                 while (start <= end) {
16                     int mid = start + (end - start) / 2;
17                     if (matrix[i][mid] == target) {
18                         cnt++;
19                         break;
20                     }
21                     else if (matrix[i][mid] < target) start = mid + 1;
22                     else end = mid - 1;
23                 }
24             }
25         }
26         return cnt;
27     }
28 }

View Code

解法2：(从左下移到右上，那么cur的上面都是比cur小的，cur的右面都是比cur大的。)

(1.if(0); 2.cnt,m,n,x,y; 3.while(&&),if(>)x, else(<)y,else-x,y,cnt; 4.return)

 1 public class Solution {
 2     /**
 3      * @param matrix: A list of lists of integers
 4      * @param: A number you want to search in the matrix
 5      * @return: An integer indicate the occurrence of target in the given matrix
 6      */
 7     public int searchMatrix(int[][] matrix, int target) {
 8         // write your code here
 9         if (matrix.length == 0 || matrix[0].length == 0) return 0;
10         int cnt = 0;
11         int m = matrix.length, n = matrix[0].length;
12         int x = m - 1, y = 0;
13         while (x >= 0 && y < n) {
14             if (matrix[x][y] > target) x--;
15             else if (matrix[x][y] < target) y++;
16             else {
17                 x--;
18                 y++;
19                 cnt++;
20             }
21         }
22         return cnt;
23     }
24 }

View Code

111.Climbing Stairs: http://www.lintcode.com/en/problem/climbing-stairs/

爬楼梯：

解法1：<Recursive>(TLE)

解法2：(Array)

 1 public class Solution {
 2     /**
 3      * @param n: An integer
 4      * @return: An integer
 5      */
 6     public int climbStairs(int n) {
 7         // write your code here
 8         if (n == 0 || n == 1) return 1;
 9         int[] rst = new int[n];
10         rst[0] = 1;
11         rst[1] = 2;
12         for (int i = 2; i < n; i++) {
13             rst[i] = rst[i - 1] + rst[i - 2];
14         }
15         return rst[n - 1];
16     }
17 }

View Code

解法3：<Iterative>

 1 public class Solution {
 2     /**
 3      * @param n: An integer
 4      * @return: An integer
 5      */
 6     public int climbStairs(int n) {
 7         // write your code here
 8         if (n == 0 || n == 1) return 1;
 9         int a = 1, b = 2;
10         for (int i = 2; i <= n; i++) {
11             int tmp = b;
12             b = a + b;
13             a = tmp;
14         }
15         return a;
16     }
17 }

View Code

28.Search a 2D Matrix: http://www.lintcode.com/en/problem/search-a-2d-matrix/

搜索二维矩阵：(看作有序数组二分搜索)

 1 public class Solution {
 2     /**
 3      * @param matrix, a list of lists of integers
 4      * @param target, an integer
 5      * @return a boolean, indicate whether matrix contains target
 6      */
 7     public boolean searchMatrix(int[][] matrix, int target) {
 8         // write your code here
 9         if (matrix == null || matrix.length == 0){
10             return false;
11         }
12         if (matrix[0] == null || matrix[0].length == 0){
13             return false;
14         }
15         int start = 0;
16         int end = matrix.length - 1;
17         int row ;
18         while (start + 1 < end) {
19             int mid = start + (end - start)/2;
20             if (matrix[mid][0] == target){
21                 return true;
22             } else if (matrix[mid][0] < target) {
23                 start = mid ;
24             } else {
25                 end = mid ;
26             }
27         }
28         if (matrix[end][0] <= target){
29             row = end;
30         } else if (matrix[start][0] <= target){
31             row = start;
32         } else {
33             return false;
34         }
35      
36         start = 0;
37         end = matrix[0].length - 1;
38         while (start <= end) {
39             int mid = start + (end - start)/2;
40             if (matrix[row][mid] == target){
41                 return true;
42             } else if (matrix[row][mid] < target) {
43                 start = mid + 1;
44             } else {
45                 end = mid - 1;
46             }
47         }
48         return false;
49     }
50 }

View Code

160.Find Minimum in Rotated Sorted Array II: http://www.lintcode.com/en/problem/find-minimum-in-rotated-sorted-array-ii/

旋转排序数组最小值(含重复)：

 1 public class Solution {
 2     public int findMin(int[] num) {
 3         //  这道题目在面试中不会让写完整的程序
 4         //  只需要知道最坏情况下 [1,1,1....,1] 里有一个0
 5         //  这种情况使得时间复杂度必须是 O(n)
 6         //  因此写一个for循环就好了。
 7         //  如果你觉得，不是每个情况都是最坏情况，你想用二分法解决不是最坏情况的情况，那你就写一个二分吧。
 8         //  反正面试考的不是你在这个题上会不会用二分法。这个题的考点是你想不想得到最坏情况。
 9         int min = num[0];
10         for (int i = 1; i < num.length; i++) {
11             if (num[i] < min)
12                 min = num[i];
13         }
14         return min;
15     }
16 }
17 
18 // version 2: use *fake* binary-search
19 public class Solution {
20     /**
21      * @param num: a rotated sorted array
22      * @return: the minimum number in the array
23      */
24     public int findMin(int[] nums) {
25         if (nums == null || nums.length == 0) {
26             return -1;
27         }
28         
29         int start = 0, end = nums.length - 1;
30         while (start + 1 < end) {
31             int mid = start + (end - start) / 2;
32             if (nums[mid] == nums[end]) {
33                 // if mid equals to end, that means it's fine to remove end
34                 // the smallest element won't be removed
35                 end--;
36             } else if (nums[mid] < nums[end]) {
37                 end = mid;
38                 // of course you can merge == & <
39             } else {
40                 start = mid;
41                 // or start = mid + 1
42             }
43         }
44         
45         if (nums[start] <= nums[end]) {
46             return nums[start];
47         }
48         return nums[end];
49     }
50 }

View Code

 1 class Solution {
 2 public:
 3     int findMin(vector<int> &num) {
 4         int lo = 0;
 5         int hi = num.size() - 1;
 6         int mid = 0;
 7         
 8         while(lo < hi) {
 9             mid = lo + (hi - lo) / 2;
10             
11             if (num[mid] > num[hi]) {
12                 lo = mid + 1;
13             }
14             else if (num[mid] < num[hi]) {
15                 hi = mid;
16             }
17             else { // when num[mid] and num[hi] are same
18                 hi--;
19             }
20         }
21         return num[lo];
22     }
23 };

View Code

第3章：

373.Partition Array by Odd and Even: http://www.lintcode.com/en/problem/partition-array-by-odd-and-even/

奇偶分隔数组：<Two Pointers>

我的解法：

 1 public class Solution {
 2     /**
 3      * @param nums: an array of integers
 4      * @return: nothing
 5      */
 6     public void partitionArray(int[] nums) {
 7         // write your code here;
 8         int left = 0, right = nums.length - 1;
 9         while (left < right) {
10             if (nums[left] % 2 == 0) {
11                 swap(nums, left, right);
12                 right--;
13             } else {
14                 left++;
15             }
16             if (nums[right] % 2 != 0) {
17                 swap(nums, left, right);
18                 left++;
19             } else {
20                 right--;
21             }
22         }
23     }
24     public void swap(int[] nums, int a, int b) {
25         int tmp = nums[a];
26         nums[a] = nums[b];
27         nums[b] = tmp;
28     }
29 }

View Code

九章：

 1 public class Solution {
 2     /**
 3      * @param nums: an array of integers
 4      * @return: nothing
 5      */
 6     public void partitionArray(int[] nums) {
 7         int start = 0, end = nums.length - 1;
 8         while (start < end) {
 9             while (start < end && nums[start] % 2 == 1) {
10                 start++;
11             }
12             while (start < end && nums[end] % 2 == 0) {
13                 end--;
14             }
15             if (start < end) {
16                 int temp = nums[start]; nums[start] = nums[end]; nums[end] = temp;
17                 start++;
18                 end--;
19             } 
20         }
21     }
22 }

View Code

245.Subtree：http://www.lintcode.com/en/problem/subtree/

子树：(借助isSameTree递归；isSubtree：1.异常判断，T2=null则true，T1=null则false；2.T1和T2等的情况，if(isSame)true；3.递归isSubTree左右节点；

isSameTree：1.异常if(||)返回T1=T2；2.值等则递归if(val)；)

我的错误解法：(错误案例：{1,1,1,2,3,#,2,#,#,4,5,3}, {1,2,3,#,#,4,5} 当T1.val=T2.val的时候, 虽然T1!=T2, 但是可能T1的子节点仍然存在=T2的, 所以这里不能直接返回isSameTree)

 1 public class Solution {
 2     /**
 3      * @param T1, T2: The roots of binary tree.
 4      * @return: True if T2 is a subtree of T1, or false.
 5      */
 6     public boolean isSubtree(TreeNode T1, TreeNode T2) {
 7         // write your code here
 8         if (T2 == null) return true;
 9         if (T1 == null) return false;
10         if (T1.val == T2.val) return isSameTree(T1, T2);
11         else return isSubtree(T1.left, T2) || isSubtree(T1.right, T2);
12     }
13     public boolean isSameTree(TreeNode T1, TreeNode T2) {
14         if (T1 == null && T2 == null) return true;
15         if (T1 != null && T2 != null && T1.val == T2.val)
16             return isSameTree(T1.left, T2.left) && isSameTree(T1.left, T2.left);
17         return false;
18     }
19 }

View Code

正确解法：(isSameTree(T1,T2))

public class Solution {
    /**
     * @param T1, T2: The roots of binary tree.
     * @return: True if T2 is a subtree of T1, or false.
     */
    public boolean isSubtree(TreeNode T1, TreeNode T2) {
        if (T2 == null) return true;
        if (T1 == null) return false;
        if (isSameTree(T1, T2)) return true;
        return isSubtree(T1.left, T2) || isSubtree(T1.right, T2);
    }
    
    public boolean isSameTree(TreeNode T1, TreeNode T2) {
        if (T1 == null || T2 == null) return T1 == T2;
        else if (T1.val == T2.val) 
            return isSameTree(T1.left, T2.left) && isSameTree(T1.right, T2.right);
        return false;
    }
}

View Code

174.Remove Nth Node From End of List: http://www.lintcode.com/en/problem/remove-nth-node-from-end-of-list/

删除倒数第N个节点：(定义两个指针left和right=dummy；首先right移动n次；然后left和right共同移动while(r.n!=null)；最后删除left后一节点；)

解法：<Two Pointers><Sliding Window>(dummy-1-2-3-4-5-null,2; left-dummy指向dummy, right移动n次指向2; while循环当right.next!=null,循环后left-3,right-5;删除left.next即可)

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) { val = x; }
 7  * }
 8  */
 9 public class Solution {
10     public ListNode removeNthFromEnd(ListNode head, int n) {
11         ListNode dummy =  new ListNode(0);
12         dummy.next = head;
13         ListNode left = dummy;
14         ListNode right = dummy;
15         for (int i = 0; i < n; i++) {
16             right = right.next;
17         }
18         while (right.next != null) {
19             left = left.next;
20             right = right.next;
21         }
22         left.next = left.next.next;
23         return dummy.next;
24     }
25 }

View Code

165.Merge Two Sorted Lists: http://www.lintcode.com/en/problem/merge-two-sorted-lists/

合并两个有序链表：

解法1：(当l1和l2都不为null时,选择val小的作为head.next并移动对应指针; 移动head指针; 有null的时候, 添加非null即可)

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) { val = x; }
 7  * }
 8  */
 9 public class Solution {
10     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
11         ListNode dummy = new ListNode(0);
12         ListNode head = dummy;
13         while (l1 != null && l2 != null) {
14             if (l1.val <= l2.val) {
15                 head.next = l1;
16                 l1 = l1.next;
17             } else {
18                 head.next = l2;
19                 l2 = l2.next;
20             } 
21             head = head.next;
22         }
23         if (l1 != null) head.next = l1;
24         if (l2 != null) head.next = l2;
25         return dummy.next;
26     }
27 }

View Code

解法2：<Recursion>(四个判断if null-return; <-递归,return;)

 1 public ListNode mergeTwoLists(ListNode l1, ListNode l2){
 2         if(l1 == null) return l2;
 3         if(l2 == null) return l1;
 4         if(l1.val < l2.val){
 5             l1.next = mergeTwoLists(l1.next, l2);
 6             return l1;
 7         } else{
 8             l2.next = mergeTwoLists(l1, l2.next);
 9             return l2;
10         }
11 }

View Code

371.Print Numbers by Recursion: http://www.lintcode.com/zh-cn/problem/print-numbers-by-recursion/

用递归打印1到最大N位整数-要求递归深度最大为N：(给出 N = 1, 返回[1,2,3,4,5,6,7,8,9]. 给出 N = 2, 返回[1,2,3,4,5,6,7,8,9,10,11,...,99].)

 1 public class Solution {
 2     /**
 3      * @param n: An integer.
 4      * return : An array storing 1 to the largest number with n digits.
 5      */
 6     public List<Integer> numbersByRecursion(int n) {
 7         // write your code here
 8         ArrayList<Integer> res = new ArrayList<>();
 9         num(n, 0, res);
10         return res;
11     }
12     
13     public void num(int n, int ans,ArrayList<Integer> res){
14         
15         if(n==0){
16             if(ans>0){
17                 res.add(ans);
18             }
19             return;
20         }
21         
22         for(int i=0; i<=9; i++){
23             num(n-1, ans*10+i, res);
24         }
25         
26     }
27 }

View Code

140.Fast Power: http://www.lintcode.com/en/problem/fast-power/

快速幂Calculate the a^n % b where a, b and n are all 32bit integers.：

(todo)

第4章：

376.Binary Tree Path Sum：http://www.lintcode.com/en/problem/binary-tree-path-sum/

二叉树路径和：(helper:如果null则return；如果root为叶, 判断 val等于tar则add,add,remove；并且所有叶节点都要return；主体：add,递归,remove)

解法：<Recursion>(1.如果root为叶节点, 两种情况：等于sum,那么add; 不等于sum,return; 2.如果root为null, 表明情况是root的父节点只有一个子节点, 递归另一个子节点即可,return;3. 非叶节点, 则add, 递归, remove; /先判断null, 再判断叶节点;)

 1 public class Solution {
 2     public List<List<Integer>> pathSum(TreeNode root, int sum) {
 3         List<List<Integer>> rst = new ArrayList<>();
 4         List<Integer> list = new ArrayList<>();
 5         helper(root, sum, list, rst);
 6         return rst;
 7     }
 8     public void helper(TreeNode root, int sum, List<Integer> list, List<List<Integer>> rst) {
 9         if (root == null) return;
10         if (root.left == null && root.right == null) {
11             if (root.val == sum) {
12                 list.add(root.val);
13                 rst.add(new ArrayList<Integer>(list));
14                 list.remove(list.size() - 1);
15             }
16             return;
17         }
18         list.add(root.val);
19         helper(root.left, sum - root.val, list, rst);
20         helper(root.right, sum - root.val, list, rst);
21         list.remove(list.size() - 1);
22     }
23 }

View Code

375.Clone Binary Tree: http://www.lintcode.com/en/problem/clone-binary-tree/

克隆二叉树：(递归)

 1 public class Solution {
 2     /**
 3      * @param root: The root of binary tree
 4      * @return root of new tree
 5      */
 6     public TreeNode cloneTree(TreeNode root) {
 7         // Write your code here
 8         if (root == null) return null;
 9         TreeNode newRoot = new TreeNode(root.val);
10         newRoot.left = cloneTree(root.left);
11         newRoot.right = cloneTree(root.right);
12         return newRoot;
13     }
14 }

View Code

211.String Permutation：http://www.lintcode.com/en/problem/string-permutation/

字符串置换(判断两个字符串的组成是否相同)：(整型数组记录字符出现次数)

解法1：(数组+排序 toCharArray-String转为char数组, Arrays.sort(char[] a)-排序;)

 1 public class Solution {
 2     /**
 3      * @param A a string
 4      * @param B a string
 5      * @return a boolean
 6      */
 7     public boolean stringPermutation(String A, String B) {
 8         // Write your code here
 9         char[] arrayA = A.toCharArray();
10         char[] arrayB = B.toCharArray();
11         int lengthA = arrayA.length;
12         int lengthB = arrayB.length;
13         if (lengthA != lengthB) return false;
14         Arrays.sort(arrayA);
15         Arrays.sort(arrayB);
16         for (int i = 0; i < lengthA; i++) {
17             if (arrayA[i] != arrayB[i]) return false;
18         }
19         return true;
20     }
21 }

View Code

解法2：(使用整型数组保存字符; 遍历两个字符串, 在对应位置上第一个+1, 第二个-1; 最后遍历数组, 都为0则true)

 1 public class Solution {
 2     /**
 3      * @param A a string
 4      * @param B a string
 5      * @return a boolean
 6      */
 7     public boolean stringPermutation(String A, String B) {
 8         // Write your code here
 9         if (A.length() != B.length()) return false;
10         int[] tmp = new int[256];
11         for (int i = 0; i < A.length(); i++) {
12             tmp[A.charAt(i)]++;
13             tmp[B.charAt(i)]--;
14         }
15         for (int i = 0; i < tmp.length; i++) {
16             if (tmp[i] != 0) return false;
17         }
18         return true;
19     }
20 }

View Code

69.Binary Tree Level Order Traversal：http://www.lintcode.com/en/problem/binary-tree-level-order-traversal/

二叉树的层序遍历：(queue:offer,poll,peek; while(queue不为空),list,size; for循环size，poll值cur，add，offer左右节点；rst；)

解法1：<BFS>(1.queue队列offer进root; 2.queue不为空时isEmpty(), 建list, for循环poll出queue中的值,offer左右子节点;)

 1 public class Solution {
 2     /**
 3      * @param root: The root of binary tree.
 4      * @return: Level order a list of lists of integer
 5      */
 6     public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
 7         // write your code here
 8         ArrayList<ArrayList<Integer>> rst = new ArrayList<>();
 9         if (root == null) return rst;
10         Queue<TreeNode> queue = new LinkedList<>();
11         queue.offer(root);
12         while (!queue.isEmpty()) {
13             ArrayList<Integer> list = new ArrayList<>();
14             int size = queue.size();
15             for (int i = 0; i < size; i++) {
16                 TreeNode cur = queue.poll();
17                 list.add(cur.val);
18                 if (cur.left != null) queue.offer(cur.left);
19                 if (cur.right != null) queue.offer(cur.right);
20             }
21             rst.add(list);
22         }
23         return rst;
24     }
25 }

View Code

解法2: <DFS>(深度优先; 1.定义helper(rst,root,height) 终止条件-null; 2.判断条件-height>=size,那么add(new)-添加一层; 3.获取层数添加值; 4.递归, 层数+1)

 1 public List<List<Integer>> levelOrder(TreeNode root) {
 2         List<List<Integer>> res = new ArrayList<List<Integer>>();
 3         levelHelper(res, root, 0);
 4         return res;
 5     }
 6     
 7     public void levelHelper(List<List<Integer>> res, TreeNode root, int height) {
 8         if (root == null) return;
 9         if (height >= res.size()) {
10             res.add(new LinkedList<Integer>());
11         }
12         res.get(height).add(root.val);
13         levelHelper(res, root.left, height+1);
14         levelHelper(res, root.right, height+1);
15     }

View Code

378.Convert Binary Search Tree to Doubly Linked List：http://www.lintcode.com/en/problem/convert-binary-search-tree-to-doubly-linked-list/

二叉查找树转换成双链表：

解法：(思路：如果左子树为已经转换好的双链表，则只需要连接此双链表和root以及右子树双链表，再转换右子树即可)

 1 public class Solution {
 2     /**
 3      * @param root: The root of tree
 4      * @return: the head of doubly list node
 5      */
 6 
 7     public DoublyListNode bstToDoublyList(TreeNode root) {
 8         if(null == root) return null;
 9         DoublyListNode result = helper(root);
10         while(result.prev != null)
11             result = result.prev;
12         return result;
13     }
14 
15     public DoublyListNode helper(TreeNode root) {
16         if(null == root) return null;
17         DoublyListNode node = new DoublyListNode(root.val);
18         if(null != root.left) {
19             DoublyListNode left = helper(root.left);
20             while(left.next != null)
21                 left = left.next;
22             node.prev = left;
23             left.next = node;
24         }
25         if(null != root.right) {
26             DoublyListNode right = helper(root.right);
27             while(right.prev != null)
28                 right = right.prev;
29             node.next = right;
30             right.prev = node;
31         }
32         return node;
33     }
34 }

View Code

374.Spiral Matrix：http://www.lintcode.com/en/problem/spiral-matrix/

螺旋矩阵：

解法：(1.用count表示边缘值。2.while循环条件是count*2小于row和col；3.for循环添加上侧和右侧。4.此时需要if判断是否只剩一行，如果是则只执行两个for循环break，否则继续后两个for循环)

 1 public class Solution {
 2     public List<Integer> spiralOrder(int[][] matrix) {
 3         List<Integer> rst = new ArrayList<>();
 4         if (matrix == null || matrix.length == 0)
 5             return rst;
 6         int rows = matrix.length;
 7         int cols = matrix[0].length;
 8         int count = 0;
 9         while (count * 2 < rows && count * 2 < cols) {
10             for (int i = count; i < cols - count; i++) {
11                 rst.add(matrix[count][i]);
12             }
13             for (int i = count + 1; i < rows - count; i++) {
14                 rst.add(matrix[i][cols - count - 1]);
15             }
16             
17             if (rows - 2 * count == 1 || cols - 2 * count == 1)
18                 break;
19             
20             for (int i = cols - count - 2; i >= count; i--) {
21                 rst.add(matrix[rows - count - 1][i]);
22             }
23             for (int i = rows - count - 2; i >= count + 1; i--) {
24                 rst.add(matrix[i][count]);
25             }
26             count++;
27         }
28         return rst;
29     }
30 }

View Code

105.Copy List with Random Pointer：http://www.lintcode.com/en/problem/copy-list-with-random-pointer/

复制带随机指针的链表：

12.Min Stack：http://www.lintcode.com/en/problem/min-stack/

带最小值操作的栈：(stack:push,pop,peek;

push：stack和minStack的大小始终一样，需要判断min的是否为空，为空则push，非空则push(Math.min)；

pop：两个都要pop，返回stack.pop();

min：minStack.peek();)

解法：(使用两个栈stack和minStack实现; stack来实现正常的pop功能; minStack功能是：保证peek是stack的最小值。pop时minStack也要pop所以minStack的size和stack的size是相同的，即minStack每一个位置记录了该位置时的最小值。具体实现：push-stack正常push，minStack选择min的push；pop-两个都要pop，返回stack的pop；min-minStack的peek)

 1 public class MinStack {
 2     private Stack<Integer> stack;
 3     private Stack<Integer> minStack;
 4     
 5     public MinStack() {
 6         stack = new Stack<Integer>();
 7         minStack = new Stack<Integer>();
 8     }
 9 
10     public void push(int number) {
11         stack.push(number);
12         if (minStack.isEmpty()) {
13             minStack.push(number);
14         } else {
15             minStack.push(Math.min(number, minStack.peek()));
16         }
17     }
18 
19     public int pop() {
20         minStack.pop();
21         return stack.pop();
22     }
23 
24     public int min() {
25         return minStack.peek();
26     }
27 }

View Code

67.Binary Tree Inorder Traversal: http://www.lintcode.com/en/problem/binary-tree-inorder-traversal/

中序遍历：(循环条件while(cur||stack); 内部循环-添值+指针左移; 出栈+添值+指针右移)

解法：(1.while条件为!null或者!empty; 2.内部while(!null)的时候,push与left, 即push进左树的所有左节点直到左叶子或者最左根; 3.pop左节点, add, cur遍历right)

 1 public class Solution {
 2     public List<Integer> inorderTraversal(TreeNode root) {
 3         List<Integer> rst = new ArrayList<Integer>();
 4         Stack<TreeNode> stack = new Stack<TreeNode>();
 5         TreeNode cur = root;
 6         while (cur != null || !stack.empty()) {
 7             while (cur != null) {
 8                 stack.push(cur);
 9                 cur = cur.left;
10             }
11             cur = stack.pop();
12             rst.add(cur.val);
13             cur = cur.right;
14         }
15         return rst;
16     }
17 }

View Code

66.Binary Tree Preorder Traversal: http://www.lintcode.com/en/problem/binary-tree-preorder-traversal/

前序遍历：(前序遍历和中序遍历是stack，层序遍历是queue)

解法：(1.判断null, 初始放入root; 2.while条件-empty; 3.pop,add,push右,push左)

 1 public class Solution {
 2     public List<Integer> preorderTraversal(TreeNode root) {
 3         List<Integer> rst = new ArrayList<>();
 4         Stack<TreeNode> stack = new Stack<>();
 5         if (root == null) return rst;
 6         stack.push(root);
 7         while (!stack.empty()) {
 8             TreeNode cur = stack.pop();
 9             rst.add(cur.val);
10             if (cur.right != null) stack.push(cur.right);
11             if (cur.left != null) stack.push(cur.left);
12         }
13         return rst;
14     }
15 }

View Code

第5章：

46.Majority Number：http://www.lintcode.com/en/problem/majority-number/

主元素(超过n/2个的数)：

解法：(使用count计数; 相同则+, 不同则减, count=0时则更换rst值; O(n)time+O(1)space)

 1 public class Solution {
 2     /**
 3      * @param nums: a list of integers
 4      * @return: find a  majority number
 5      */
 6     public int majorityNumber(ArrayList<Integer> nums) {
 7         // write your code
 8         int count = 1;
 9         int rst = nums.get(0);
10         for (int i = 1; i < nums.size(); i++) {
11             if (count == 0) {
12                 rst = nums.get(i);
13             } 
14             if (rst == nums.get(i)) count++;
15             else count--;
16         }
17         return rst;
18         
19     }
20 }

View Code

41.Maximum Subarray: http://www.lintcode.com/en/problem/maximum-subarray/

最大连续子数组：（维护两个变量：maxEndingHere和maxSoFar；迭代；）

解法：(从A[0]开始向右遍历，如果已经解决了A[0]-A[i-1]中的最大连续subarray，那么A[0]-A[i]的最大连续subarray要么是A[0]-A[i-1]的结果，要么是以A[i]作为结尾的一段subarray；记前者是maxSoFar，后者是maxEndingHere；显然maxEndingHere的值为(前一个数的maxEndingHere加上A[i])或者(a[i])这两个数之间的最大值。)

1 public static int maxSubArray(int[] A) {
2     int maxSoFar=A[0], maxEndingHere=A[0];
3     for (int i=1;i<A.length;++i){
4         maxEndingHere= Math.max(maxEndingHere+A[i],A[i]);
5         maxSoFar=Math.max(maxSoFar, maxEndingHere);    
6     }
7     return maxSoFar;
8 }

View Code

532.Reverse Pairs: http://www.lintcode.com/en/problem/reverse-pairs/

逆序对：

解法：(归并排序。mergeSort, merge; 分成若干小数组，求出逆序对个数，再归并得出总个数。注意[left]>[right]时，sum+=mid-left+1 因为right的小数已经放入tmp数组里不参与left后面的比较了，而left后的数都大于left)

 1 public class Solution {
 2     /**
 3      * @param A an array
 4      * @return total of reverse pairs
 5      */
 6     public long reversePairs(int[] A) {
 7         // Write your code here
 8         return mergeSort(A, 0, A.length - 1);
 9     }
10     public int mergeSort(int[] A, int low, int high) {
11         if (low >= high) return 0;
12         int mid = (low + high) / 2;
13         int sum = 0;
14         sum += mergeSort(A, low, mid);
15         sum += mergeSort(A, mid + 1, high);
16         sum += merge(A, low, mid, high);
17         return sum;
18     }
19     public int merge(int[]A, int low, int mid, int high) {
20         int[] tmp = new int[high - low + 1];
21         int left = low;
22         int right = mid + 1;
23         int k = 0;
24         int sum = 0;
25         
26         while (left <= mid && right <= high) {
27             if (A[left] <= A[right]) {
28                 tmp[k++] = A[left++];
29             } else {
30                 tmp[k++] = A[right++];
31                 sum += mid - left + 1;
32             }
33         }
34         while (left <= mid) {
35             tmp[k++] = A[left++];
36         }
37         while (right <= high) {
38             tmp[k++] = A[right++];
39         }
40         for (int i = 0; i < tmp.length; i++) {
41             A[i + low] = tmp[i];
42         }
43         return sum;
44     }
45 }

View Code

381.Spiral Matrix II：http://www.lintcode.com/en/problem/spiral-matrix-ii/

螺旋数组II(返回1-n^2的螺旋数组)：

解法：(和Spiral Matrix解法相同，count计数边缘宽度；while(count*2<n) 四个for循环及中间一个if判断语句；for1长度=for2长度+1=for3长度+1=for4长度+2)

 1 public class Solution {
 2     public int[][] generateMatrix(int n) {
 3         int[][] Matrix = new int[n][n];
 4         int count = 0;
 5         int num = 1;
 6         while (count * 2 < n) {
 7             for (int i = count; i < n - count; i++) {
 8                 Matrix[count][i] = num++;
 9             }
10             for (int i = count + 1; i < n - count; i++) {
11                 Matrix[i][n - count - 1] = num++;
12             }
13             
14             if (count * 2 == n - 1) break;
15             
16             for (int i = n - count - 2; i >= count; i--) {
17                 Matrix[n - count - 1][i] = num++;
18             }
19             for (int i = n - count - 2; i >= count + 1; i--) {
20                 Matrix[i][count] = num++;
21             }
22             count++;
23         }
24         return Matrix;
25     }
26 }

View Code

380.Intersection of Two Linked Lists：http://www.lintcode.com/en/problem/intersection-of-two-linked-lists/

两个链表的交叉：

我的解法：(使用list分别保存链表的值; 倒序对比链表中的值，遇到不同的则break；再遍历其中一个链表找到对应的节点) （O(n)time+O(n)space）

（注意比较值的时候必须用equals; 不然对于>128的数则报错！即：1->127,2->127 正确; 1->129,2->129 错误。参考：Integer值的问题）

（感觉对题目的理解有点问题。题目指的是链表交叉而不知只是值相等）

 1 public class Solution {
 2     /**
 3      * @param headA: the first list
 4      * @param headB: the second list
 5      * @return: a ListNode 
 6      */
 7     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
 8         // Write your code here
 9         if (headA == null || headB == null) return null;
10         List<Integer> listA = new ArrayList<>();
11         List<Integer> listB = new ArrayList<>();
12         ListNode index = headA;
13         while (headA != null) {
14             listA.add(headA.val);
15             headA = headA.next;
16         }
17         while (headB != null) {
18             listB.add(headB.val);
19             headB = headB.next;
20         }
21         int i = 0, j = 0;
22         for (i = listA.size() - 1, j = listB.size() - 1; i >= 0&&j >= 0; i--,j--) {
23             if (!listA.get(i).equals(listB.get(j))) break;
24         }
25         if (i == listA.size() - 1) return null;
26         for (int k = 0; k <= i; k++) {
27             index = index.next;
28         }
29         return index;
30     }  
31 }

View Code

解法：(把两个链表相接；则环的起始位置即是结果--即ListCycleII问题。题目要求链表结构不变，最后还需要把index的null节点置null)

 1 public class Solution {
 2     /**
 3      * @param headA: the first list
 4      * @param headB: the second list
 5      * @return: a ListNode 
 6      */
 7     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
 8         // Write your code here
 9         if (headA == null || headB == null) return null;
10         ListNode index = headA;
11         while (index.next != null)  index = index.next;
12         index.next = headB;
13         ListNode rst = listCycle(headA);
14         index.next = null;
15         return rst;
16     }
17     public ListNode listCycle(ListNode head) {
18         ListNode slow = head, fast = head.next;
19         if (fast == null || fast.next == null) return null;
20         while (slow != fast) {
21             slow = slow.next;
22             fast = fast.next.next;
23         }
24         slow = head;
25         fast = fast.next;
26         while (slow != fast) {
27             slow = slow.next;
28             fast = fast.next;
29         }
30         return slow;
31     }
32 }

View Code

379.Reorder array to construct the minimum number：http://www.lintcode.com/en/problem/reorder-array-to-construct-the-minimum-number/

数组重新排序以构造最小值：

解法：(todo)

 1 public class Solution {
 2     /**
 3      * @param nums n non-negative integer array
 4      * @return a string
 5      */
 6     public String minNumber(int[] nums) {
 7         // Write your code here
 8         int n = nums.length;
 9         if (n < 1) return "";
10         
11         String[] strs = new String[n];
12         for (int i = 0; i < n; i++) {
13             strs[i] = String.valueOf(nums[i]);
14         }
15         
16         Arrays.sort(strs, new Cmp());
17         
18         String ans = "";
19         for (int i = n - 1; i >= 0; i--) {
20             ans = ans.concat(strs[i]);
21         }
22         
23         int i = 0;
24         while (i < n && ans.charAt(i) == '0')
25             i ++;
26 
27         if (i == n) return "0";
28         return ans.substring(i);
29     }
30 }
31 class Cmp implements Comparator<String>{
32     @Override
33     public int compare(String a, String b) {
34         String ab = a.concat(b);
35         String ba = b.concat(a);
36         return ba.compareTo(ab);
37     }
38 }

View Code

5.Kth Largest Element：http://www.lintcode.com/en/problem/kth-largest-element/

第K大元素：

解法：( 快排思想；一次快排：把大于pivot移到右边，小于的移到左边；如果pivot的position为length-k+1，那么即为结果；否则大于则递归右边，小于则递归左边；)

(1.主函数：helper(nums, 0, length-1, length-k);

2.helper函数：(nums,lo,hi,k); 终止条件：(lo=hi)那么return；partition得出position位置；if(=k)return；if(<k)helper左边；if(>k)helper右边；

3.partition函数；)

 1 class Solution {
 2     /*
 3      * @param k : description of k
 4      * @param nums : array of nums
 5      * @return: description of return
 6      */
 7     public int kthLargestElement(int k, int[] nums) {
 8         // write your code here
 9         if (nums == null || nums.length == 0) {
10             return 0;
11         }
12         if (k <= 0) {
13             return 0;
14         }
15         return helper(nums, 0, nums.length - 1, nums.length - k + 1);
16         
17     }
18     public int helper(int[] nums, int l, int r, int k) {
19         if (l == r) {
20             return nums[l];
21         }
22         int position = partition(nums, l, r);
23         if (position + 1 == k) {
24             return nums[position];
25         } else if (position + 1 < k) {
26             return helper(nums, position + 1, r, k);
27         }  else {
28             return helper(nums, l, position - 1, k);
29         }
30     }
31     public int partition(int[] nums, int l, int r) {
32         // 初始化左右指针和pivot
33         int left = l, right = r;
34         int pivot = nums[left];
35         
36         // 进行partition
37         while (left < right) {
38             while (left < right && nums[right] >= pivot) {
39                 right--;
40             }
41             nums[left] = nums[right];
42             while (left < right && nums[left] <= pivot) {
43                 left++;
44             }
45             nums[right] = nums[left];
46         }
47         
48         // 返还pivot点到数组里面
49         nums[left] = pivot;
50         return left;         
51     }
52 };

View Code

第6章：

82.Single Number: http://www.lintcode.com/en/problem/single-number/

找出2n+1个数里单独的一个数：

解法：(位运算；异或^；一个数与自己异或为零；零与一个数异或为该数) (one-pass+constant extra space)

 1 public class Solution {
 2     /**
 3       *@param A : an integer array
 4       *return : a integer 
 5       */
 6     public int singleNumber(int[] A) {
 7         // Write your code here
 8         int rst = 0;
 9         for (int i = 0; i < A.length; i++) {
10             rst = rst ^ A[i];
11         }
12         return rst;
13     }
14 }

View Code

56.Two Sum: http://www.lintcode.com/en/problem/two-sum/

两数之和(返回数组中等于tar值的两数的index)：

解法：（HashMap 保存[i]的值；如果包含tar-[i]，则已经找到两个目标数；用到方法：map.containsKey；map.get）

 1 public class Solution {
 2     /*
 3      * @param numbers : An array of Integer
 4      * @param target : target = numbers[index1] + numbers[index2]
 5      * @return : [index1 + 1, index2 + 1] (index1 < index2)
 6      */
 7     public int[] twoSum(int[] numbers, int target) {
 8         // write your code here
 9         int[] rst = new int[2];
10         HashMap<Integer, Integer> map = new HashMap<>();
11         for (int i = 0; i < numbers.length; i++) {
12             if (map.containsKey(target - numbers[i])) {
13                 rst[0] = map.get(target - numbers[i]);
14                 rst[1] = i + 1;
15                 return rst;
16             }
17             map.put(numbers[i], i + 1);
18         }
19         return rst;
20     }
21 }

View Code

53.Reverse Words in a String: http://www.lintcode.com/en/problem/reverse-words-in-a-string/

反转字符串：(转数组+倒序遍历数组)

（ps：原解法错误无法处理中间多个空格情况；" a b "）

解法1：(利用正则表达式 split("\s+")表示按任意个空格分隔)

public class Solution {
    /**
     * @param s : A string
     * @return : A string
     */
    public String reverseWords(String s) {
        // write your code
        String[] array = s.trim().split("\s+");
        String rst = "";
        for (int i = array.length - 1; i > 0; i--) {
            rst += array[i] + " ";
        }
        return rst + array[0];
    }
}

View Code

解法2：(利用StringBuffer的method：sb.append；)

public class Solution {
    public String reverseWords(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }

        String[] array = s.split(" ");
        StringBuilder sb = new StringBuilder();

        for (int i = array.length - 1; i >= 0; --i) {
            if (!array[i].equals("")) {
                sb.append(array[i]).append(" ");
            }
        }
        //remove the last " "
        return sb.toString().trim();
    }
}

View Code

解法1改进：(不使用正则表达式，在循环内部使用判断语句)

public class Solution {

    public String reverseWords(String s) {

        String[] array = s.trim().split(" ");
        String rst = "";
        for (int i = array.length - 1; i >= 0; i--) {
            if(!array[i].equals("")){
                rst += array[i] + " ";
            }
        }
        return rst.trim();
    }
}

View Code

8.Rotate String：http://www.lintcode.com/en/problem/rotate-string/

旋转字符串：

解法：(整个旋转+两边分别旋转)

public class Solution {

    public void rotateString(char[] str, int offset) {
        // write your code here
        if (str.length == 0) return;
        int n = str.length;
        int k = offset % n;
        reverse(str, 0, n - 1);
        reverse(str, 0, k - 1);
        reverse(str, k, n - 1);
    }
    public void reverse(char[] str, int start, int end) {
        int i = start, j = end;
        while (i < j) {
            char tmp = str[j];
            str[j--] = str[i];
            str[i++] = tmp;
        }
    }
}

View Code

 1     /**
 2      * @param str: an array of char
 3      * @param offset: an integer
 4      * @return: nothing
 5      */
 6     public void rotateString(char[] str, int offset) {
 7         // write your code here
 8         if (str == null || str.length == 0)
 9             return;
10             
11         offset = offset % str.length;
12         reverse(str, 0, str.length - offset - 1);
13         reverse(str, str.length - offset, str.length - 1);
14         reverse(str, 0, str.length - 1);
15     }
16     
17     private void reverse(char[] str, int start, int end) {
18         for (int i = start, j = end; i < j; i++, j--) {
19             char temp = str[i];
20             str[i] = str[j];
21             str[j] = temp;
22         }
23     }
24 }

View Code

61.Search for a Range：http://www.lintcode.com/en/problem/search-for-a-range/

搜索区间(找出第一个和最后一个tar的位置)：

解法：

public class Solution {

    public int[] searchRange(int[] A, int target) {
        // write your code here
        int[] rst = new int[]{-1, -1};
        if (A.length == 0) return rst;
        int lo = 0, hi = A.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (A[mid] >= target) hi = mid;
            else lo = mid + 1;
        }
        if (A[lo] == target) rst[0] = lo;
        else return rst;
        
        hi = A.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo + 1) / 2;
            if (A[mid] <= target) lo = mid;
            else hi = mid - 1;
        }
        rst[1] = hi;
        return rst;
    }
}

View Code

第7章：

88.Lowest Common Ancestor：http://www.lintcode.com/en/problem/lowest-common-ancestor/

最近公共祖先：

解法：(递归 root为最低祖先条件是A和B分别在左右子树； )

(如果找到了就返回LCA；如果只找到A就返回A；只找到B就返回B；左右不为空返回root；左空返回右，右空返回左)

(具体：1.null/A/B 返回root；2.递归得left/right；3.左右非空返回root，有空的则返回非空)

 1 public class Solution {
 2     // 在root为根的二叉树中找A,B的LCA:
 3     // 如果找到了就返回这个LCA
 4     // 如果只碰到A，就返回A
 5     // 如果只碰到B，就返回B
 6     // 如果都没有，就返回null
 7     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2) {
 8         if (root == null || root == node1 || root == node2) {
 9             return root;
10         }
11         
12         // Divide
13         TreeNode left = lowestCommonAncestor(root.left, node1, node2);
14         TreeNode right = lowestCommonAncestor(root.right, node1, node2);
15         
16         // Conquer
17         if (left != null && right != null) {
18             return root;
19         } 
20         if (left != null) {
21             return left;
22         }
23         if (right != null) {
24             return right;
25         }
26         return null;
27     }
28 }

View Code

54.String to Integer II: http://www.lintcode.com/en/problem/string-to-integer-ii/

转换字符串到整数：

解法：(1.判空/非数字； 2.判断正负符号；3.遍历str，把数字添加到rst，rst=rst*10+(charAt(i)-0); 4.添加符号； 5.转int)

 1 public class Solution {
 2     /**
 3      * @param str: A string
 4      * @return An integer
 5      */
 6     public int atoi(String str) {
 7         // write your code here
 8         if (str == null || str.length() < 1)
 9         return 0;
10         
11         // trim white spaces
12         str = str.trim();
13  
14         char flag = '+';
15  
16         // check negative or positive
17         int i = 0;
18         if (str.charAt(0) == '-') {
19             flag = '-';
20             i++;
21         } else if (str.charAt(0) == '+') {
22             i++;
23         }
24         // use double to store result
25         double result = 0;
26     
27         // calculate value
28         while (str.length() > i && str.charAt(i) >= '0' && str.charAt(i) <= '9') {
29             result = result * 10 + (str.charAt(i) - '0');
30             i++;
31         }
32  
33         if (flag == '-')
34             result = -result;
35  
36         // handle max and min
37         if (result > Integer.MAX_VALUE)
38             return Integer.MAX_VALUE;
39  
40         if (result < Integer.MIN_VALUE)
41             return Integer.MIN_VALUE;
42  
43         return (int) result;
44     }
45 }

View Code

第8章：

112.Remove Duplicates from Sorted List：http://www.lintcode.com/en/problem/remove-duplicates-from-sorted-list/

删除排序链表中的重复元素：

 1 public class Solution {
 2     /**
 3      * @param ListNode head is the head of the linked list
 4      * @return: ListNode head of linked list
 5      */
 6     public static ListNode deleteDuplicates(ListNode head) { 
 7         // write your code here
 8         ListNode dummy = new ListNode(0);
 9         dummy.next = head;
10         if (head == null) return head;
11         while (head.next != null) {
12             if (head.val == head.next.val) head.next = head.next.next;
13             else head = head.next;
14         }
15         return dummy.next;
16     }  
17 }

View Code

50.Product of Array Exclude Itself: http://www.lintcode.com/en/problem/product-of-array-exclude-itself/

数组剔除元素后的乘积：

暴力解法：(两个for循环)

 1 public class Solution {
 2     /**
 3      * @param A: Given an integers array A
 4      * @return: A Long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]
 5      */
 6     public ArrayList<Long> productExcludeItself(ArrayList<Integer> A) {
 7         // write your code
 8         ArrayList<Long> rst = new ArrayList<>();
 9         long count = 1;
10         for (int i = 0; i < A.size(); i++ ) {
11             count = 1;
12             for (int j = 0; j < A.size(); j++) {
13                 if (i != j) count *= A.get(j);
14             }
15             rst.add(count);
16         }
17         return rst;
18     }
19 }

View Code

解法：（定义数组f保存右边数的乘积，从后向前扫描，f[i]即为a中包括i的右边所有数的乘积；例如[2,3,4];对应f-[24,12,4]; 接着从前向后遍历，用left记录i左边数的积，则rst只需add(left*f[i+1])即可；当i+1=len的时候 add left; 或者可以f增长一格保存1也可以；）

 1 public class Solution {
 2     /**
 3      * @param nums: Given an integers array A
 4      * @return: A Long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]
 5      */
 6     public ArrayList<Long> productExcludeItself(ArrayList<Integer> A) {
 7         int len = A.size();
 8         ArrayList<Long> B = new  ArrayList<Long>();
 9         long[] f = new long[len + 1];
10 
11         f[len] = 1;
12         for (int i = len - 1; i >= 0; i--) {
13             f[i] = A.get(i) * f[i + 1];
14         }
15         long left = 1;
16         for (int i = 0; i < len; i++) {
17             B.add(left * f[i + 1]);
18             left *= A.get(i);
19         }
20         return B;
21         
22     }
23 }

View Code

2017.4.15

牛客网

1.镜像二叉树：

递归与非递归(Stack)

import java.util.Stack;
public class Solution {
    

    public void Mirror(TreeNode root) {
        /*递归解法；
        if (root == null) return;

        Mirror(root.right);
        Mirror(root.left);
        
        TreeNode tmp = root.right;
        root.right = root.left;
        root.left = tmp;
        */
        
        /*非递归解法*/
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while (!stack.empty()) {
            TreeNode cur = stack.pop();
            if (cur.left != null)  stack.push(cur.left);
            if (cur.right != null) stack.push(cur.right);
            TreeNode tmp = cur.right;
            cur.right = cur.left;
            cur.left = tmp;
        }
    }
}

View Code

2. 顺时针打印矩阵：

（错误：边界问题；设计尾部都要n-1）

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
        ArrayList<Integer> rst = new ArrayList<>();
        if (matrix.length == 0 || matrix[0].length == 0) return rst;
        int row = matrix.length;
        int col = matrix[0].length;
        int cnt = 0;
        while (cnt * 2 < row && cnt * 2 < col) {
            for (int i = cnt; i < col - cnt; i++) {
                rst.add(matrix[cnt][i]);
            }
            for (int i = cnt + 1; i < row - cnt; i++) {
                rst.add(matrix[i][col - cnt - 1]);
            }
            
            if (row - cnt * 2 == 1 || col - cnt * 2 == 1) return rst;
            
            for (int i = col - cnt - 2; i >= cnt; i--) {
                rst.add(matrix[row - cnt - 1][i]);
            }
            for (int i = row - cnt - 2; i > cnt; i--) {
                rst.add(matrix[i][cnt]);
            }
               cnt++;
        }
        return rst;
    }
}

View Code

3.包含min函数的栈：

（push的时候比较特殊，需要判空+比较大小）

import java.util.Stack;

public class Solution {

    Stack<Integer> stack = new Stack<>();
    Stack<Integer> minStack = new Stack<>();
    
    public void push(int node) {
        stack.push(node);
        if (!minStack.empty()) {
            if (node > minStack.peek()) {
                minStack.push(minStack.peek());
                return;
            }
        } 
        minStack.push(node);
    }
    
    public void pop() {
        stack.pop();
        minStack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int min() {
        return minStack.peek();
    }
}

View Code

4.栈的压入、弹出序列：

(辅助栈；while循环内必须加判断stack.empty)

【思路】借用一个辅助的栈，遍历压栈顺序，先讲第一个放入栈中，这里是1，然后判断栈顶元素是不是出栈顺序的第一个元素，这里是4，很显然1≠4，所以我们继续压栈，直到相等以后开始出栈，出栈一个元素，则将出栈顺序向后移动一位，直到不相等，这样循环等压栈顺序遍历完成，如果辅助栈还不为空，说明弹出序列不是该栈的弹出顺序。

举例：

入栈1,2,3,4,5

出栈4,5,3,2,1

首先1入辅助栈，此时栈顶1≠4，继续入栈2

此时栈顶2≠4，继续入栈3

此时栈顶3≠4，继续入栈4

此时栈顶4＝4，出栈4，弹出序列向后一位，此时为5，,辅助栈里面是1,2,3

此时栈顶3≠5，继续入栈5

此时栈顶5=5，出栈5,弹出序列向后一位，此时为3，,辅助栈里面是1,2,3

….

依次执行，最后辅助栈为空。如果不为空说明弹出序列不是该栈的弹出顺序。

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

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if (pushA.length != popA.length) return false;
        if (pushA == null) return true;
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int i = 0; i < pushA.length; i++ ) {
            stack.push(pushA[i]);
            while ( !stack.empty() && stack.peek() == popA[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }
}

View Code

5.从上往下打印二叉树

(层序遍历-队列)

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

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

    }

}
*/
public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> rst = new ArrayList<>();
        if (root == null) return rst;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                rst.add(cur.val);
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
            }
        }
        return rst;
    }
}

View Code

6.二叉搜索树的后序遍历序列

(thinking: 二叉树用递归能解决很多问题~~)

错误解法：（递归，找到第一个小于root的值；复制到两个数组分别为左右树；再递归判断左右数组；错误示例：[7,4/6/5] 可见左右树均为BST后序，原数组也不一定为后序）

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        int n = sequence.length;
        if (n == 0 || n == 1) return true;
        for (int i = n - 1; i >= 0; i--) {
            
            if (sequence[i] < sequence[n - 1] || i == 0) {
                int[] left = new int[i + 1];
                int[] right = new int[n - i - 2];
                for (int j = 0; j <= i; j++) {
                    left[j] = sequence[j];
                }
                for (int j = i + 1; j < n - 1; j++) {
                    right[j - i - 1] = sequence[j];
                }
                return VerifySquenceOfBST(left) && VerifySquenceOfBST(right);
            }
                
        }
        
        return false;
    }
}

View Code

千辛万苦终于成功的正确解法：（复制数组+递归；几种特殊情况；第一：空为false，但递归空为true，所以只能借助helper把空提取出来了；第二：遍历全部都大于root值，此时i=0，需要单独列出；）

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        int n = sequence.length;
        if (n == 0) return false;
        return helper(sequence);
    }
    public boolean helper(int[] sequence) {
        int n = sequence.length;
        if (n == 0 || n == 1) return true;
        for (int i = n - 2; i >= 0; i--) {
            
            if (sequence[i] < sequence[n - 1]) {
                int[] left = new int[i + 1];
                int[] right = new int[n - i - 2];
                for (int j = 0; j <= i; j++) {
                    if (sequence[j] > sequence[n - 1]) return false;
                    left[j] = sequence[j];
                }
                for (int j = i + 1; j < n - 1; j++) {
                    if (sequence[j] < sequence[n - 1]) return false;
                    right[j - i - 1] = sequence[j];
                }
                return helper(left) && helper(right);
            }
            if (i == 0) {
                int[] right = new int[n - 1];
                for (int j = 0; j < n - 1; j++) {
                    right[j] = sequence[j];
                }
                return helper(right);
            }
                
        }
        
        return true;
    }
}

View Code

BST的后序序列的合法序列是，对于一个序列S，最后一个元素是x （也就是根），如果去掉最后一个元素的序列为T，那么T满足：T可以分成两段，前一段（左子树）小于x，后一段（右子树）大于x，且这两段（子树）都是合法的后序序列。完美的递归定义 : ) 。

改进：

/**
 * T: 二叉搜索树的后序遍历序列
 *
 * 题目描述
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
 * 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
 *
 *
 */
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        int n = sequence.length;
        if (n == 0) return false;
        if (n == 1) return true;
        return helper(sequence, 0, n - 1);
    }
    public boolean helper(int[] a, int start, int end) {
        if (start >= end) return true;
        int index = end - 1;
        while (index >= start && a[index] > a[end]) {
            index--;
        }
        for (int i = start; i < index; i++) {
            if (a[i] > a[end]) return false;
        }
        return helper(a, start, index) && helper(a, index + 1, end - 1);
    }
}

View Code

7.二叉树中和为某一值的路径

(bug free~ o(∩_∩)o )

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 {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        ArrayList<Integer> list = new ArrayList<>();
        ArrayList<ArrayList<Integer>> rst = new ArrayList<>();
        helper(root, target, rst, list);
        return rst;
    }
    public void helper(TreeNode root, int target, ArrayList<ArrayList<Integer>> rst, ArrayList<Integer> list) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            if (root.val == target) {
                list.add(root.val);
                rst.add(new ArrayList<Integer>(list));
                list.remove(list.size() - 1);
                return;
            }
        }
        list.add(root.val);
        helper(root.left, target - root.val, rst, list);
        helper(root.right, target - root.val, rst, list);
        list.remove(list.size() - 1);
        
    }
}

View Code

8.复杂链表的复制

(thinking：链表-递归)

解法1：递归

/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
public class Solution {
    public RandomListNode Clone(RandomListNode pHead)
    {
        if (pHead == null) return null; 
        RandomListNode newHead = new RandomListNode(pHead.label);
        if(pHead.random != null) newHead.random = new RandomListNode(pHead.random.label);
        newHead.next = Clone(pHead.next);
        return newHead;
    }
}

View Code

解法2：复制+random+拆分

public class Solution {
    public RandomListNode Clone(RandomListNode pHead){
        if (pHead == null) return null; 
        //复制
        RandomListNode pCur = pHead;
        while (pCur != null) {
            RandomListNode node = new RandomListNode(pCur.label);
            node.next = pCur.next;
            pCur.next = node;    //添加复制节点node;
            pCur = node.next; //移动pCur;
        }
        
        //random节点
        pCur = pHead;
        while (pCur != null) {
            if (pCur.random != null) pCur.next.random = pCur.random.next;
            pCur = pCur.next.next;
        }
        
        //拆分
        RandomListNode newHead = pHead.next;
        RandomListNode newCur = newHead;
        pCur = pHead;
        while (pCur != null) {
            pCur.next = newCur.next;
            if(newCur.next != null)newCur.next = newCur.next.next;
            pCur = pCur.next;
            newCur = newCur.next;
        }
        return newHead;
    }
}

View Code

9.二叉搜索树与双向链表