leetcode & lintcode 题解

2019年12月04日 阅读数:216
这篇文章主要向大家介绍leetcode & lintcode 题解,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

刷题备忘录,for bug-freehtml

招行面试题--求无序数组最长连续序列的长度,这里连续指的是值连续--间隔为1,并非数值的位置连续前端

问题:java

给出一个未排序的整数数组,找出最长的连续元素序列的长度。

如:

给出[100, 4, 200, 1, 3, 2],

最长的连续元素序列是[1, 2, 3, 4]。返回它的长度:4。

你的算法必须有O(n)的时间复杂度 。

 解法:node

初始思路
要找连续的元素,第一反应通常是先把数组排序。但悲剧的是题目中明确要求了O(n)的时间复杂度,要作一次排序,是不能达到的。不过咱们仍是先来看看排序的方案要怎么实现。

简单来讲,排序后咱们只要遍历数组,检查当前值减1是否等于上一个值,若是等,增长当前连续序列的计数;若是不等,将当前计数与当前最大值比较,若是更优替换最大值, 并重置计数为1。具体到细节上,咱们还要考虑几个问题:

- 第一个数

处理第一个数时是没有上一个值的。有人可能以为能够给存储上一个值的变量赋一个特别的初始值来表示处理的是第一个数。可是因为数组内元素的取值范围是全部的整数,不可能找出一个特别的值。因此代码中须要对第一个数作特殊的判断

- 重复的数

数组中可能会有重复的数,因此咱们不能光判断当前值减1等于或不等于上一个值。还须要加上一个等不等与上一个值的判断,若是等,说明是一个重复的数字,直接不作任何处理跳到数组中的下一个数。

- 最后一组连续序列

因为咱们只在遍历中发现当前值减1不等于上一个值时才尝试更新序列长度最大值。若是有一个连续序列一直持续到数组中的最后一个元素,这个序列的长度是没有获得处理的。所以咱们须要在遍历完数组后再尝试更新依稀最大值。

加入了这些细节考虑后,代码就呼之欲出了:


 1 class SolutionSort
 2 {
 3 public:
 4     int longestConsecutive(std::vector<int> &num)
 5     {
 6         std::sort(num.begin(), num.end());
 7         
 8         int maxLen = 0;
 9         int currentLen = 0;
10         int previous = 0;
11         
12         for(auto iter = num.begin(); iter != num.end(); ++iter)
13         {
14             if(iter == num.begin())//第一个数的特殊状况
15             {
16                 ++currentLen;
17             }
18             else
19             {
20                 if(*iter == previous)//重复数的状况
21                 {
22                     continue;
23                 }
24                 else if(*iter - 1 == previous)
25                 {
26                     ++currentLen;
27                 }
28                 else
29                 {
30                     if(currentLen > maxLen)
31                     {
32                         maxLen = currentLen;
33                     }
34                     currentLen = 1;
35                 }
36             }
37             previous = *iter;
38         }
39         
40                 //有一个连续序列持续到数组最后一个元素的状况
41         if(currentLen > maxLen)
42         {
43             maxLen = currentLen;
44         }
45         
46         return maxLen;
47     }
48 }; 使用排序的代码
提交后发现实际上是能够经过Judge Small和Judge Large的。可是这种方案始终不符合题目要求。

优化
要实现O(n)的时间复杂度,就不能对数组排序。其实咱们大脑在判断这个问题时就是不排序的。让咱们来模拟一下:

你看到[100, 4, 200, 1, 3, 2]这个数组,首先你会看99或者101在不在这个数组里,发现数组没这两个数,那么100组成的连续序列长度仅为1。接着会看5或者3在不在数组里,会发现3存在,5不存在;紧接着会看2在不在....直到发现0不在。从而获得4组成的最长序列为4。

总结一下会发现,咱们在判断某个数的连续序列时,会分别往减少和增大的方向找下一个连续数在不在数组中。而后把两个方向的长度加起来即为包含该数的一个连续序列。须要注意的是,当前数的长度计数只须要出如今一个方向的查找中计算便可,不然就重复了。要找一个数是否是在数组中,不可能用遍历的方法实现,这样时间复杂度就超过O(n)了。而要下降时间复杂度,一个经典的方案就是空间换时间。用增长空间复杂度的方法来换取时间复杂度的下降。因此咱们能够先对数组进行一次预处理,生成一份包含数组元素的哈希表。这样在求解某个数字在不在数组时就能够获得O(1)的时间复杂度。

那么咱们能够获得以下伪代码:

找连续序列函数(要找序列的值,方向)

  循环直到要找的值不在哈希表中

    序列长度+1

    若是增长方向,要找的序列值+1

    若是减小方向,要找的序列值-1

  循环结束

  返回序列长度

找连续序列函数结束

求解函数(数组)

  遍历数组生成哈希表

  遍历数组

    序列长度1 = 找连续序列函数(当前值,增长方向)

    序列长度2 = 找连续序列函数(当前值 - 1,减小方向)

    若是序列长度1 + 序列长度2 > 当前最长序列,更新最长序列

  遍历结束

求解函数结束

这个方案的时间复杂度应该是O(n) + O(n) * O(1) * O(平均序列长度)。若是平均序列长度等于n,如数组[3,4,2,1],复杂度就是O(n^2)了。看来还不可行,主要的时间复杂度都浪费在找连续序列上了。怎么能减小找连续序列的时间复杂度?通过观察咱们能够发现,4的最长序列和3,2,1的最长序列实际上是同样的。找过了4以后其实后面这3个数都不用找了。而咱们控制是否查找一个数的连续序列是经过判断数字是否在哈希表中来实现的,也就是说,若是咱们能够在找出一个数字在连续序列中后就将其移除,就能够避免之后再触发查找的循环。经过这个优化,时间复杂度将变为O(n) + O(n) + O(序列长度总和),能够认为是O(n)了。最后得出代码以下:


 1 classSolution
 2 {
 3 public:
 4     int longestConsecutive(std::vector<int> &num)
 5     {
 6         for(int i = 0; i < num.size(); ++i)
 7         {
 8             flags_.insert(num[i]);
 9         }
10             
11         int maxLen = 0;
12         
13         for(int i = 0; i < num.size(); ++i)
14         {
15             int ascendingMax = FindConsecutiveNumbers(ASCENDING, num[i]);
16             int decendingMax = FindConsecutiveNumbers(DECENDING, num[i] - 1);
17             
18             
19             if(ascendingMax + decendingMax > maxLen)
20             {
21                 maxLen = ascendingMax + decendingMax;
22             }
23         }
24         
25         return maxLen;
26     }
27     
28 private:
29     enum OrderBy
30     {
31         ASCENDING,
32         DECENDING
33     };
34     
35     int FindConsecutiveNumbers(OrderBy orderBy, int value)
36     {
37         int maxLen = 0;
38         
39         while(flags_.find(value) != flags_.end())
40         {
41             ++maxLen;
42             
43             flags_.erase(value);
44             
45             if(orderBy == ASCENDING)
46             {
47                 ++value;
48             }
49             else
50             {
51                 --value;
52             }        
53         }
54         
55         return maxLen;
56     }
57     
58     std::unordered_set<int> flags_;
59 };
View Code

 

和最大连续子数组--有正数和负数c++

 1 public class Solution {
 2     /**
 3      * @param A an integer array
 4      * @return  A list of integers includes the index of the first number and the index of the last number
 5      */
 6     public ArrayList<Integer> continuousSubarraySum(int[] A) {
 7         // Write your code here
 8         if (A == null || A.length == 0){
 9             return new ArrayList<Integer>();
10         }
11         int sum = A[0];
12         int max = sum;
13         int start = 0;
14         int end = 0;
15         int ans_s = start;
16         int ans_e = end;
17         ArrayList<Integer> ans = new ArrayList<Integer>();
18         for (int i = 1; i < A.length; i++) {
19             if (sum < 0) {
20                 sum = A[i];
21                 start = end = i;
22             } else {
23                 sum += A[i];
24                 end = i;
25             }
26             if (sum > max) {
27                 max = sum;
28                 ans_s = start;
29                 ans_e = end;
30             }
31         }
32         ans.add(ans_s);
33         ans.add(ans_e);
34         return ans;
35     }
36 }
View Code

 

leetcode 5. Longest Palindromic Substringgit

最长回文子串:动态规划github

 1 public class Solution {
 2     public String longestPalindrome(String s) {
 3         if (s == null || s.length() == 0) {
 4             return new String("");
 5         }
 6         
 7         int n = s.length();
 8         int maxLen = 1;
 9         String ans = "";
10         //p[i][j]表示第i个字符到第j个字符是否为回文串
11         boolean[][] p = new boolean[n][n];
12         for (int i = 0; i < n; i++) {
13             p[i][i] = true;
14             ans = s.substring(i, i + 1);
15         }
16         for (int i = 0; i < n - 1; i++) {
17             if (s.charAt(i) == s.charAt(i + 1)) {
18                 p[i][i + 1] = true;
19                 maxLen = 2;
20                 ans = s.substring(i, i + 2);
21             }
22         }
23         
24         for (int len = 2; len < n; len++) {
25             for (int i = 0; i < n - len; i++) {
26                 if (s.charAt(i + len) == s.charAt(i)) {
27                     p[i][i + len] = p[i + 1][i + len - 1];
28                     if (p[i][i + len]) {
29                         if (len + 1 > maxLen) {
30                             maxLen = len + 1;
31                             ans = s.substring(i, i + len + 1);
32                             if (maxLen == n) {
33                                 return ans;
34                             }
35                         }
36                     }
37                 }
38             }
39         }
40         
41         return ans;
42     }
43 }
View Code

leetcode 31 Next Permutation面试

题意--求全排列的下一个排列算法

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
View Code

解法:express

算法的基本思想是对于给定的序列,从后往前找出现后一个数比前一个数大的位置,
假设此处较大数位置为b,较小数位置为a,而后再从b开始日后找最后一个大于nums[a]的数,必然能找到一个位置为c的数,交换nums[c]和nums[a],而且反转nums[a+1]~nums[length-1]

能够发现再找位置c的时候可使用二分法来提升效率,由于位置b日后是一个有序序列,而且是倒序的,便是在一个有序序列中找到最后一个大于某个数的数

为何要反转,由于交换事后的b位置开始就是一个倒序的有序序列,反转事后就变成了正序的有序序列,保证字典序最小

其实这种解法能够用来解决全排列的非递归形式,只需初始化第一个排列,而后while循环这个算法就能够了。由于当n很大时,递归层数太大。--百度的面试题,n个数全排列非递归

代码

 1 public class Solution {
 2     public void nextPermutation(int[] nums) {
 3         if (nums == null || nums.length <= 1) {
 4             return;
 5         }
 6         int len = nums.length;
 7         
 8         for (int i = len - 1; i > 0; i--) {
 9             if (nums[i] > nums[i - 1]) {
10                 int lastBigger = getLastBigger(nums, i, nums[i - 1]);
11                 swap(nums, i - 1, lastBigger);
12                 reverse(nums, i);
13                 return;
14             }
15         }
16         
17         reverse(nums, 0);
18     }
19     
20     //在倒序的子数组中二分法查找最后一个大于target的数
21     public int getLastBigger(int[] nums, int start, int target) {
22         int end = nums.length - 1;
23         int index = start;
24         
25         while (start <= end) {
26             int mid = start + (end - start) / 2;
27             if (nums[mid] > target) {
28                 index = mid;
29                 start = mid + 1;
30             } else {
31                 end = mid - 1;
32             }
33         }
34         
35         return index;
36     }    
37     
38     //反转数组,从start位置开始
39     public void reverse(int[] nums,int start) {
40         int end = nums.length - 1;
41         for (int i = 0; i < (end - start + 1) / 2; i++) {
42             int tmp = nums[start + i];
43             nums[start + i] = nums[end - i];
44             nums[end - i] = tmp;
45         }
46     }
47     
48     public void swap(int[] nums, int i, int j) {
49         int tmp = nums[i];
50         nums[i] = nums[j];
51         nums[j] = tmp;
52     }
53 }
View Code

 

leetcode 37. Sudoku Solver --数独

题意:给出数独的方案

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

A sudoku puzzle...

 

...and its solution numbers marked in red.

解法:遍历整个二维数组,对于每个空的格子,一次插入1-9看是否 合适,若是合适就继续下一次的递归循环,直到全部的空格子都被填满了数字。

 1 class Solution {
 2 public:
 3     void solveSudoku(vector<vector<char>>& board) {
 4         slove(board);
 5     }
 6     bool slove(vector<vector<char>>& board)
 7     {
 8         for (int i = 0; i < board.size(); i++)
 9         {
10             for (int j = 0; j < board[0].size(); j++) 
11             {
12                 if (board[i][j] == '.')
13                 {
14                     for (char c = '1'; c <= '9'; c++) 
15                     {
16                         if (isValid(board, i, j, c))
17                         {
18                             board[i][j] = c;
19                             if (slove(board))
20                             {
21                                 return true;
22                             }
23                             else
24                             {
25                                 board[i][j] = '.';
26                             }
27                         }
28                     }
29                     return false;
30                 }
31             }
32         }
33         return true;
34     }
35     bool isValid(vector<vector<char>>& board, int row, int col, char c) {
36         for (int i = 0; i < board.size(); i++) 
37         {
38             if (board[i][col] != '.' && board[i][col] == c) return false;
39             if (board[row][i] != '.' && board[row][i] == c) return false;
40             if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] != '.' &&
41             board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false;
42         }
43         return true;
44     }
45 };
View Code

 

最长公共字符串

题意:返回两个字符串的最长公共子串的长度

解法:dp,详见代码注释。

 1 public class Solution {
 2     /**
 3      * @param A, B: Two string.
 4      * @return: the length of the longest common substring.
 5      */
 6     
 7     //dp time O(mn)
 8     public int longestCommonSubstring(String A, String B) {
 9         // write your code here
10         if (A == null || B == null || A.length() == 0 || B.length() == 0) {
11             return 0;
12         }
13         int n = A.length();
14         int m = B.length();
15         //dp[i][j]表示当前A的第i个字符和B的第j个字符往前能构成的最长连续公共子串的长度
16         int[][] dp = new int[n + 1][m + 1];
17         int max = 0;
18         for (int i = 1; i <= n; i++) {
19             for (int j = 1; j <= m; j++) {
20                 if (A.charAt(i - 1) == B.charAt(j - 1)) {
21                     dp[i][j] = dp[i - 1][j - 1] + 1;
22                     max = Math.max(max, dp[i][j]);
23                 }
24             }
25         }
26         return max;
27     }
28 }
View Code

最长公共子序列

题意:返回两个字符串的最长公共子序列的长度

解法:dp,详见代码注释。

 1 public class Solution {
 2     /**
 3      * @param A, B: Two strings.
 4      * @return: The length of longest common subsequence of A and B.
 5      */
 6     public int longestCommonSubsequence(String A, String B) {
 7         // write your code here
 8         if (A == null || B == null || A.length() == 0 || B.length() == 0) {
 9             return 0;
10         }
11         int n = A.length();
12         int m = B.length();
13         //state : dp[i][j]表示A的前i个字符与B的前j个字符的最长公共子序列的长度
14         int[][] dp = new int[n + 1][m + 1];
15         //initialize
16         //function : dp[i][j] = dp[i - 1][j - 1] + 1 when A.charAt(i - 1) == B.charAt(j - 1)
17         // else dp[i][j] = Math.max(dp[i - 1][j - 1],Math.max(dp[i - 1][j], dp[i][j - 1]));           
18         for (int i = 1; i <= n; i++) {
19             for (int j = 1; j <= m;j++) {
20                 if (A.charAt(i - 1) == B.charAt(j - 1)) {
21                     dp[i][j] = dp[i - 1][j - 1] + 1;
22                 } else {
23                     dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
24                 }
25             }
26         }
27         //answer
28         return dp[n][m];
29     }
30 }
View Code

leetcode 45. Jump Game II

题意:找出最少跳几步能够到达最后一个位置。

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

Note:
You can assume that you can always reach the last index.
View Code

解法:把问题转化为层序遍历或者说是bfs。初始位置是第一层,由初始位置可到达的全部位置构成第二层,由第二层全部位置可到达的全部位置构成第三层,假设最后一个位置在第n层,则须要的步数即为n-1.详细解释见代码中的注释。

 1 public class Solution {
 2     public int jump(int[] nums) {
 3         if (nums == null || nums.length <= 1) {
 4             return 0;
 5         }
 6         int level = 0;      //当前层
 7         int levelStart = 0; //每一层的开始位置索引值
 8         int levelEnd = 0;   //每一层的结束位置索引值
 9         while (levelEnd - levelStart + 1 > 0) {
10             int nextLevelEnd = 0;
11             level++;
12             for (;levelStart <= levelEnd; levelStart++) { //遍历这一层的全部位置找到最远可到的位置,即为下一层的结束位置
13                 nextLevelEnd = Math.max(nextLevelEnd, levelStart + nums[levelStart]);
14                 if (nextLevelEnd >= nums.length - 1) {    //下一层的结束位置超过了数组的最后一位,则返回当前的层数
15                     return level;
16                 }
17             }
18             levelEnd = nextLevelEnd;
19         }
20         return 0;
21     }
22 }
View Code

 

leetcode 55  Jump Game

题意:数组中每一个元素表示在此位置最远能够向前跳几步,判断给定的数组可否到达最后一个位置,初始位置在第一个位置。

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.
View Code

解法:记录一个全局的最远可到达位置,遍历数组,若是当前最远位置小于数组索引,说明到不了当前位置,能够返回false。反之用由此位置能够到达的最远位置更新全局的最远位置。最后遍历到最后一个位置仍能够到达则返回true。

 1 public class Solution {
 2     public boolean canJump(int[] nums) {
 3         if (nums == null || nums.length == 0) {
 4             return false;
 5         }
 6         
 7         int farest = 0;
 8         for (int i = 0; i < nums.length; i++) {
 9             if (farest < i) {
10                 return false;
11             }
12             if (i + nums[i] > farest) {
13                 farest = i + nums[i];
14             }
15         }
16         
17         return true;
18     }
19 }
View Code

leetcode 32 Longest Valid Parentheses

题意:找出括号字符串中有效的连续括号组合最长的长度。

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.
View Code

解法:dp 。dp[i]表示以第i+1个字符结尾的括号字符串的最大长度。

1.若是s[i] == '(',则dp[i] = 0,由于括号不可能以'('结尾

2.若是s[i] == ')':

  a.第一种状况,s[i - 1] == '(',则dp[i] = dp[i - 2] + 2;

  b.第二种状况,s[i - 1] == ')' && s[i - dp[i - 1] - 1] == '(',则 dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]

固然这些状况须要注意i的取值范围,防止索引值越界。记录一个最大值,返回这个最大值便可。

 1 public class Solution {
 2     public int longestValidParentheses(String s) {
 3         if (s == null || s.length() == 0) {
 4             return 0;
 5         }
 6         int[] dp = new int[s.length()];
 7         int max = 0;
 8         for (int i = 1; i < s.length(); i++) {
 9             if (s.charAt(i) == '(') {
10                 dp[i] = 0;
11             } else {
12                 if (s.charAt(i - 1) == '(') {
13                     dp[i] = i > 1 ? dp[i - 2] + 2 : 2;
14                 } else if (i > dp[i - 1] && s.charAt(i - dp[i - 1] - 1) == '(') {
15                     dp[i] = i > dp[i - 1] + 1 ? dp[i - 1] + 2 + dp[i - dp[i - 1] - 2] : dp[i - 1] + 2;
16                 }
17             }
18             max = Math.max(max, dp[i]);
19         }
20         return max;
21     }
22 }
View Code

leetcode 41 First Missing Positive

题意:找到数组中第一个没出现的正整数,所谓第一个是指正整数从大到小排列的第一个没出现的。O(n)+O(1)

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.
View Code

解法:主要思路是将相应位置的值变为其索引值加一,若是不是的话,就交换。当nums[i] <= 0或者nums[i]>nums.length就不作交换了

        空数组返回1,没找到的话就返回nums.length + 1

 1 public class Solution {
 2     public int firstMissingPositive(int[] nums) {
 3         if (nums == null || nums.length == 0) {
 4             return 1;
 5         }
 6         for (int i = 0; i < nums.length; i++) {
 7             //若是nums[i] == nums[nums[i] - 1],则不作交换,避免死循环 而不用 nums[i] != i + 1
 8             while (nums[i] > 0 && nums[i] <= nums.length && nums[i] != nums[nums[i] - 1]) { 
 9                 int temp = nums[i];
10                 nums[i] = nums[nums[i] - 1];
11                 nums[temp - 1] = temp;
12                 //nums[nums[i] - 1] = temp;这是错误的,由于nums[i]更新过了
13             }
14         }
15         for (int i = 0; i < nums.length; i++) {
16             if (nums[i] != i + 1) {
17                 return i + 1;
18             }
19         }
20         return nums.length + 1;
21     }
22 }
View Code

leetcode 7 Reverse Integer--微软面试题

题意:反转一个整数,返回整数,若是溢出返回0。

解法:注意溢出状况,先把结果用long来表示,看结果是否超过了整数的边界。注意不用区分正负数。

 1 public class Solution {
 2     public int reverse(int x) {
 3         long ans = 0;
 4         while (x != 0) {
 5             ans = ans * 10 + x % 10;
 6             x = x / 10;
 7             if (ans > Integer.MAX_VALUE || ans < Integer.MIN_VALUE) {
 8                 return 0;
 9             }
10         }
11         return (int)ans;
12     }
13 }
View Code

lintcode Minimum Subtree

题意:找出节点和最小的子树。

Given a binary tree, find the subtree with minimum sum. Return the root of the subtree.

 注意事项

LintCode will print the subtree which root is your return node.
It's guaranteed that there is only one subtree with minimum sum and the given binary tree is not an empty tree.

您在真实的面试中是否遇到过这个题? Yes
样例
Given a binary tree:

     1
   /   \
 -5     2
 / \   /  \
0   2 -4  -5 
return the node 1.
View Code

解法:分治+递归。保存一个全局的最小值和最小值对应的子树的根节点。

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root the root of binary tree
     * @return the root of the minimum subtree
     */
    int minSum = Integer.MAX_VALUE;
    TreeNode minTree = null;
    public TreeNode findSubtree(TreeNode root) {
        // Write your code here
        helper(root);
        return minTree;
    }
    public int helper(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int sum = helper(root.left) + helper(root.right) + root.val;
        if (sum < minSum) {
            minSum = sum;
            minTree = root;
        }
        return sum;
    }
}
View Code

leetcode 114 Flatten Binary Tree to Linked List

题意:将二叉树按照前序遍历转换成链表,二叉树right指针表示next。

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6
The flattened tree should look like:
   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6
View Code

解法:分治法,相似于前序遍历的递归。先flatten左子树,再将当前根节点flatten,这时先将当前节点的右节点保存,再将当前节点的左子树设为右节点,在循环遍历到左子树的最后一个节点,将保存的右节点连上去,再flatten右子树。

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public void flatten(TreeNode root) {
12         if (root == null) {
13             return;
14         }
15         
16         flatten(root.left);
17         
18         TreeNode right = root.right;
19         root.right = root.left;
20         root.left = null;
21         while (root.right != null) {
22             root = root.right;
23         }
24         root.right = right;
25         if (root.right != null) {
26             flatten(root.right);
27         }
28     }
29 }
View Code

leetcode 56. Merge Intervals

题意:将重叠的间隔融合起来。

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
View Code

解法:先将间隔按照开始端点排序,再依次遍历,若是前一个的结束端点大于后一个开始端点而且小于后一个结束端点,则这两个重合。

 1 /**
 2  * Definition for an interval.
 3  * public class Interval {
 4  *     int start;
 5  *     int end;
 6  *     Interval() { start = 0; end = 0; }
 7  *     Interval(int s, int e) { start = s; end = e; }
 8  * }
 9  */
10 public class Solution {
11     public List<Interval> merge(List<Interval> intervals) {
12         List<Interval> ans = new ArrayList<>();
13         if (intervals == null || intervals.size() == 0) {
14             return ans;
15         }
16         Collections.sort(intervals, new MyComparator());
17         ans.add(new Interval(intervals.get(0).start, intervals.get(0).end));
18         int preStart = intervals.get(0).start;
19         int preEnd = intervals.get(0).end;
20         for (int i = 1; i < intervals.size(); i++) {
21             int start = intervals.get(i).start;
22             int end = intervals.get(i).end;
23             if (preEnd >= start && preEnd < end) {
24                 ans.remove(ans.size() - 1);
25                 ans.add(new Interval(preStart, end));
26                 preEnd = end;
27             } else if (preEnd < start) {
28                 ans.add(new Interval(start, end));
29                 preEnd = end;
30                 preStart = start;
31             }
32         }
33         return ans;
34     }
35     public class MyComparator implements Comparator<Interval> {
36         public int compare(Interval in1, Interval in2) {
37             return in1.start - in2.start;
38         }
39     }
40 }
View Code

 

10. Regular Expression Matching--hard

题意:判断字符串s和p是否匹配,模式字符串p中的'.'表明任意字符,'*'表明前一字符出现0次或任意次数。

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
View Code

解法:有dp和回溯两种方法,这里主要说dp的方法,回溯法在剑指offer里面有。

dp[i][j]表示s的前i-1个字符与p的前j-1个字符是否匹配,最后返回dp[s.length()][p.length()]便可。

1, If p.charAt(j) == s.charAt(i) :  dp[i][j] = dp[i-1][j-1];
2, If p.charAt(j) == '.' : dp[i][j] = dp[i-1][j-1];
3, If p.charAt(j) == '*': 
   here are two sub conditions:
               1   if p.charAt(j-1) != s.charAt(i) : dp[i][j] = dp[i][j-2]  //in this case, a* only counts as empty
               2   if p.charAt(i-1) == s.charAt(i) or p.charAt(i-1) == '.':
                              dp[i][j] = dp[i-1][j]    //in this case, a* counts as multiple a 
                           or dp[i][j] = dp[i][j-1]   // in this case, a* counts as single a
                           or dp[i][j] = dp[i][j-2]   // in this case, a* counts as empty
View Code

代码:注意初始化

 1 public class Solution {
 2     public boolean isMatch(String s, String p) {
 3         if (s == null && p == null) {
 4             return true;
 5         }
 6         if (s == null || p == null) {
 7             return false;
 8         }
 9         int m = s.length();
10         int n = p.length();
11         boolean[][] dp = new boolean[m + 1][n + 1];
12         dp[0][0] = true;
13         //形如“a*b*c*”的形式dp[0][i] = true
14         for (int i = 0; i < n; i++) {
15             if (p.charAt(i) == '*' && dp[0][i - 1]) {
16                 dp[0][i + 1] = true;
17             }
18         }
19         for (int i = 0; i < m; i++) {
20             for (int j = 0; j < n; j++) {
21                 if (p.charAt(j) == '.' || p.charAt(j) == s.charAt(i)) {
22                     dp[i + 1][j + 1] = dp[i][j];
23                 }
24                 if (p.charAt(j) == '*') {
25                     if (p.charAt(j - 1) != s.charAt(i) && p.charAt(j - 1) != '.') {
26                         dp[i + 1][j + 1] = dp[i + 1][j - 1];
27                     } else {
28                         dp[i + 1][j + 1] = dp[i + 1][j - 1] || dp[i + 1][j] || dp[i][j + 1];
29                     }
30                 }
31             }
32         }
33         return dp[m][n];
34     }
35 }
View Code

 

leetcode 138. Copy List with Random Pointer

题意:深度拷贝带有随机指针的链表

解法:用到hashmap,将新建节点与原节点映射

 1 /**
 2  * Definition for singly-linked list with a random pointer.
 3  * class RandomListNode {
 4  *     int label;
 5  *     RandomListNode next, random;
 6  *     RandomListNode(int x) { this.label = x; }
 7  * };
 8  */
 9 public class Solution {
10     public RandomListNode copyRandomList(RandomListNode head) {
11         if (head == null) {
12             return null;
13         }
14         Map<RandomListNode, RandomListNode> map = new HashMap<>();
15         RandomListNode cur = head;
16         while (cur != null) {
17             RandomListNode newNode = new RandomListNode(cur.label);   
18             map.put(cur, newNode);
19             cur = cur.next;
20         }
21         cur = head;
22         while (cur != null) {
23             map.get(cur).next = map.get(cur.next);
24             map.get(cur).random = map.get(cur.random);
25             cur = cur.next;
26         }
27         return map.get(head);
28     }
29 }
View Code

 

leetcode 8. String to Integer (atoi)--微软面试题

题意:将字符串转化为数字

解法:

主要注意的case:1.正负号;2.字符串前面开头有空格,过滤掉;3.遇到数字以后再遇到其余字符,直接返回当前结果;4.溢出状况,正数溢出返回最大整数,负数溢出返回最小整数。

 1 public class Solution {
 2     public int myAtoi(String str) {
 3         if (str == null || str.length() == 0) {
 4             return 0;
 5         } 
 6         int num = 0;
 7         int start = 0;
 8         boolean minus = false;
 9         while (start < str.length() && str.charAt(start) == ' ') {
10             start++;
11         }
12         if (start < str.length() && str.charAt(start) == '+') {
13             start++;
14         } else if (start < str.length() && str.charAt(start) == '-') {
15             start++;
16             minus = true;
17         }
18         for (int i = start; i < str.length(); i++) {
19             if ('0' <= str.charAt(i) && str.charAt(i) <= '9') {
20                 if (Integer.MAX_VALUE / 10 < num || (Integer.MAX_VALUE / 10 == num && Integer.MAX_VALUE % 10 < str.charAt(i) - '0')) {
21                     return minus ? Integer.MIN_VALUE : Integer.MAX_VALUE;
22                 }
23                 num = num * 10 + str.charAt(i) - '0';
24             } else {
25                 return minus ? -num : num;
26             }
27         }
28         return minus ? -num : num;
29     }
30 }
View Code

0-1背包问题--腾讯面试题

给出n个物品的体积A[i]和其价值V[i],将他们装入一个大小为m的背包,最多能装入的总价值有多大?

1.二维数组的作法

 1 public class Solution {
 2     /**
 3      * @param m: An integer m denotes the size of a backpack
 4      * @param A & V: Given n items with size A[i] and value V[i]
 5      * @return: The maximum value
 6      */
 7     public int backPackII(int m, int[] A, int V[]) {
 8         // write your code here
 9         if (A == null || A.length == 0 || V == null || V.length == 0) {
10             return 0;
11         }
12         int n = A.length;
13         int[][] dp = new int[n + 1][m + 1];
14         for (int i = 1; i <= n; i++) {
15             for (int j = 1; j <= m; j++) {
16                 if (j >= A[i - 1]) {
17                     dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - A[i - 1]] + V[i - 1]);
18                 } else {
19                     dp[i][j] = dp[i - 1][j];
20                 }
21             }
22         }
23         return dp[n][m];
24     }
25 }
View Code

2.一维数组的作法

 1 public class Solution {
 2     /**
 3      * @param m: An integer m denotes the size of a backpack
 4      * @param A & V: Given n items with size A[i] and value V[i]
 5      * @return: The maximum value
 6      */
 7     public int backPackII(int m, int[] A, int V[]) {
 8         // write your code here
 9         if (A == null || A.length == 0 || V == null || V.length == 0) {
10             return 0;
11         }
12         int n = A.length;
13         int[] dp = new int[m + 1];
14         for (int i = 1; i <= n; i++) {
15             for (int j = m; j >= A[i - 1]; j--) {
16                 dp[j] = Math.max(dp[j], dp[j - A[i - 1]] + V[i - 1]);
17             }
18         }
19         return dp[m];
20     }
21 }
View Code

leetcode 4. Median of Two Sorted Arrays

题意:求两个有序数组的中位数

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:
nums1 = [1, 3]
nums2 = [2]

The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5
View Code

解法:

理解并熟记findKthSmallestEle()这个通用的函数,找两个排序数组中第k大的数
时间复杂度在log(k),用到二分法相似的方法
每次比较两个数组的第k/2个数,舍弃比较小的数组的前k/2个数
再递归查找第k - k/2个数
如有一个数组不足k/2个数,则舍弃另一个数组的前k/2个数
递归总结条件是k==1或者有一个数组为空
注意这里的舍弃只是logic delete,让数组的起始位置向前移动k/2就能够实现
对于未排序的数组找第k大的数或者k小的数,有一个著名的算法叫作quick select算法,与quicksort相似,理解并熟记
View Code

代码:

 1 public class Solution {
 2     public double findMedianSortedArrays(int[] nums1, int[] nums2) {
 3         if (nums1 == null || nums2 == null) {
 4             return 0.0;
 5         }
 6         int m = nums1.length;
 7         int n = nums2.length;
 8         if (((m + n) & 1 ) == 0) {
 9             return (findKthSmallestEle(nums1, nums2, 0, 0, (m + n) / 2) + 
10                    findKthSmallestEle(nums1, nums2, 0, 0, (m + n) / 2 + 1)) / 2.0;
11         } else {
12             return findKthSmallestEle(nums1, nums2, 0, 0, (m + n) / 2 + 1) / 1.0;
13         }
14     }
15     public int findKthSmallestEle(int[] nums1, int[] nums2, int start1, int start2, int k) {
16         if (start1 >= nums1.length) {
17             return nums2[start2 + k - 1];
18         }
19         if (start2 >= nums2.length) {
20             return nums1[start1 + k - 1];
21         }
22         if (k == 1) {
23             return Math.min(nums1[start1], nums2[start2]);
24         }
25         if (nums1.length - start1 < k /2) {
26             return findKthSmallestEle(nums1, nums2, start1, start2 + k / 2, k - k / 2);
27         }
28         if (nums2.length - start2 < k /2) {
29             return findKthSmallestEle(nums1, nums2, start1 + k / 2, start2, k - k / 2);
30         }
31         if (nums1[start1 + k / 2 - 1] <= nums2[start2 + k / 2 - 1]) {
32             return findKthSmallestEle(nums1, nums2, start1 + k / 2, start2, k - k / 2);
33         } else {
34             return findKthSmallestEle(nums1, nums2, start1, start2 + k / 2, k - k / 2);
35         }
36     }
37 }
View Code

 

leetcode 404. Sum of Left Leaves

题意:求全部左叶子节点的值之和,也就是说叶节点必须是左孩子。

 1 Find the sum of all left leaves in a given binary tree.
 2 
 3 Example:
 4 
 5     3
 6    / \
 7   9  20
 8     /  \
 9    15   7
10 
11 There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.
View Code

解法:分治递归,在递归到下一个子树时,传入一个boolean参数表示该子树的根节点是否是左子节点,若是发现当前节点是叶子结点而且是左子节点,则返回节点值,不然返回左子树和右子树节点值之和。

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public int sumOfLeftLeaves(TreeNode root) {
12         if (root == null) {
13             return 0;
14         }
15         return helper(root.left, true) + helper(root.right, false);
16     }
17     public int helper(TreeNode root, boolean isLeft) {
18         if (root == null) {
19             return 0;
20         }
21         if (isLeft && root.left == null && root.right == null) {
22             return root.val;
23         }
24         return helper(root.left, true) + helper(root.right, false);
25     }
26 }
View Code

 

leetcode 449. Serialize and Deserialize BST

题意:序列化与反序列化bst,限制条件是不可以使用 全局/静态/类成员 变量

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.
View Code

解法:思路与以前作的序列化反序列化二叉树同样,使用前序遍历,不过此次在恢复的时候为了避免使用全局变量,增长了一个辅助队列来存储节点值,每遍历到一个节点,就将该节点值从队列中删除,这样就不用保存string 数组的索引值了。

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Codec {
11 
12     // Encodes a tree to a single string.
13     public String serialize(TreeNode root) {
14         if (root == null) {
15             return null;
16         }
17         StringBuilder ans = new StringBuilder();
18         helper(root, ans);
19         return ans.toString().substring(0, ans.length() - 1);
20     }
21     public void helper(TreeNode root, StringBuilder ans) {
22         if (root == null) {
23             ans.append("#").append(",");
24             return;
25         }
26         ans.append(String.valueOf(root.val)).append(",");
27         helper(root.left, ans);
28         helper(root.right, ans);
29     }
30 
31     // Decodes your encoded data to tree.
32     public TreeNode deserialize(String data) {
33         if (data == null) {
34             return null;
35         }
36         String[] strs = data.split(",");
37         Queue<String> qu = new LinkedList<>();
38         for (String str : strs) {
39             qu.offer(str);
40         }
41         return deHelper(qu);
42     }
43     public TreeNode deHelper(Queue<String> data) {
44         if (data.isEmpty()) {
45             return null;
46         }
47         if (data.peek().equals("#")) {
48             data.poll();
49             return null;
50         }
51         TreeNode root = new TreeNode(Integer.valueOf(data.poll()));
52         root.left = deHelper(data);
53         root.right = deHelper(data);
54         return root;
55     }
56 }
View Code

 

leetcode 99 Recover Binary Search Tree

题意:二叉搜索树两个节点交换了,在不改变树结构的前提下还原二叉树。时间复杂度 O(n),空间复杂度O(1).

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
View Code

解法:由题意可知会出现两次中序遍历的前一个节点值大于等于后一个节点值得状况,而且第一次出现时被交换的是前一个节点,第二次出现时被交换的是后一个节点,由于大的数被交换到前面,小的数被交换到后面,因此找到这两个节点,再交换他们的值便可。

中序遍历二叉树,而且保存在下一次遍历的时候传入前一个节点,找到第一次不知足前一个节点的值是否小于当前节点值,而且将前一个节点保存为第一个待交换节点,再找到第二次,而且将当前节点保存为第二个待交换节点。交换这两个节点的值。

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     TreeNode first = null;
12     TreeNode second = null;
13     TreeNode pre = new TreeNode(Integer.MIN_VALUE);
14     public void recoverTree(TreeNode root) {
15         if (root == null) {
16             return;
17         }
18         helper(root);
19         int temp = first.val;
20         first.val = second.val;
21         second.val = temp;
22     }
23     public void helper(TreeNode root) {
24         if (root == null) {
25             return;
26         }
27         helper(root.left);
28         if (first == null && pre.val >= root.val) {
29             first = pre;
30         }
31         if (first != null && pre.val >= root.val) {
32             second = root;
33         }
34         pre = root;
35         helper(root.right);
36     }
37 }
View Code

leetcode 117 Populating Next Right Pointers in Each Node

题意:将二叉树每一层的节点链接起来,左边节点的next为右边下一个节点,此题的前提条件是任意二叉树。因此此题的解法是一个通用解法。

解法:相似于116,也是一层一层链接。不过这里要用head和pre来分别表示下一层 的最左边节点和当前链接的前一节点。由于head不必定是上一个节点的左节点。

 1 /**
 2  * Definition for binary tree with next pointer.
 3  * public class TreeLinkNode {
 4  *     int val;
 5  *     TreeLinkNode left, right, next;
 6  *     TreeLinkNode(int x) { val = x; }
 7  * }
 8  */
 9 public class Solution {
10     public void connect(TreeLinkNode root) {
11         if (root == null) {
12             return;
13         }
14         //上一层的当前节点
15         TreeLinkNode cur = root;
16         //下一层的前一节点
17         TreeLinkNode pre = null;
18         //下一层的最左边节点
19         TreeLinkNode head = null;
20         while (cur != null) {
21             while (cur != null) {
22                 if (cur.left != null) {
23                     if (pre != null) {
24                         pre.next = cur.left;
25                     } else {
26                         head = cur.left;
27                     }
28                     pre = cur.left;
29                 }
30                 if (cur.right != null) {
31                     if (pre != null) {
32                         pre.next = cur.right;
33                     } else {
34                         head = cur.right;
35                     }
36                     pre = cur.right;
37                 }
38                 cur = cur.next;
39             }
40             cur = head;
41             head = null;
42             pre = null;
43         }
44     }
45 }
View Code

leetcode 116 Populating Next Right Pointers in Each Node

题意:将二叉树每一层的节点链接起来,左边节点的next为右边下一个节点,此题的前提条件是彻底二叉树。

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

You may only use constant extra space.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,
         1
       /  \
      2    3
     / \  / \
    4  5  6  7
After calling your function, the tree should look like:
         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL
View Code

解法:相似于层序遍历。pre是当前层的最左边子节点,cur是当前层的当前节点。一开始cur = pre,对cur的下一层节点作连接,cur = cur.next.每一层的cur遍历到这一层末尾时,pre= pre.left,pre变为下一层的最左边节点。

 1 /**
 2  * Definition for binary tree with next pointer.
 3  * public class TreeLinkNode {
 4  *     int val;
 5  *     TreeLinkNode left, right, next;
 6  *     TreeLinkNode(int x) { val = x; }
 7  * }
 8  */
 9 public class Solution {
10     public void connect(TreeLinkNode root) {
11         if (root == null) {
12             return;
13         }
14         //pre是当前层的最左边子节点,cur是当前层的当前节点
15         TreeLinkNode pre = root;
16         TreeLinkNode cur = null;
17         while (pre.left != null) {
18             cur = pre;
19             while (cur != null) {
20                 cur.left.next = cur.right;
21                 if (cur.next != null) {
22                     cur.right.next = cur.next.left;
23                 }
24                 cur = cur.next;
25             }
26             pre = pre.left;
27         }
28     }
29 }
View Code

leetcode 124. Binary Tree Maximum Path Sum

题意:二叉树两个节点之间路径的节点的和

 1 Given a binary tree, find the maximum path sum.
 2 
 3 For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
 4 
 5 For example:
 6 Given the below binary tree,
 7 
 8        1
 9       / \
10      2   3
11 Return 6.
View Code

解法:其实与二叉树两个节点之间的最大距离相似的。要注意的是节点的值多是负数,可是节点之间的距离是没有负数的。

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     int max = Integer.MIN_VALUE;
12     public int maxPathSum(TreeNode root) {
13         if (root == null) {
14             return 0;
15         }
16         helper(root);
17         return max;
18     }
19     public int helper(TreeNode root) {
20         if (root == null) {
21             return 0;
22         }
23         //左右子树的结果多是负的,因此要跟零做比较
24         int left = Math.max(0, helper(root.left));
25         int right = Math.max(0, helper(root.right));
26         max = Math.max(left + right + root.val, max);
27         //注意返回的不是要求的最大值,而只是这颗子树的左右子树最大的从根节点往下的节点值和
28         return left > right ? left + root.val : right + root.val;
29     }
30 }
View Code

滴滴面试题 二叉树距离最大的两个节点之间的距离

题目:若是咱们把二叉树看作图,父子节点之间的连线当作是双向的,咱们姑且定义“距离”为两个节点之间边的个数。写一个程序求一棵二叉树中相距最远的两个节点之间的距离。

以下图所示,树中相距最远的两个节点为A,B,最大距离为6。

书上对这个问题的分析是很清楚的,计算一个二叉树的最大距离有两个状况:

状况A: 路径通过左子树的最深节点,经过根节点,再到右子树的最深节点。
状况B: 路径不穿过根节点,而是左子树或右子树的最大距离路径,取其大者

对于状况A来讲,只须要知道左右子树的深度,而后加起来便可。

对于状况B来讲,须要知道左子树的最远距离,右子树的最远距离

这里的解法应该是最优的最简单的解法。首先维持一个最大距离的全局变量,在求树深度的时候,将左右子树的深度相加再加2与当前最大距离比较,取较大值。

 1 int max = 0;
 2 public int getHeight(TreeNode root){
 3     if (root == null) {
 4         return 0;
 5     }
 6     int leftHeight = getHeight(root.left) + 1;
 7     int rightHeight = getHeight(root.right) + 1;
 8     int len = leftHeight + rightHeight;
 9     max = len > max ? len : max;
10     return leftHeight > rightHeight ? leftHeight : rightHeight;
11 }
View Code

 

leetcode 25. Reverse Nodes in k-Group

题意:

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5
View Code

解法:先求出长度,再对k去整除,而后循环每一个k反转链表

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode* reverseKGroup(ListNode* head, int k) {
12         if (head == NULL || k <= 1) {
13             return head;
14         }
15         int len = 0;
16         ListNode* cur = head;
17         while (cur != NULL) {
18             len++;
19             cur = cur->next;
20         }
21         ListNode* dummy = new ListNode(0);
22         dummy->next = head;
23         ListNode* pre = dummy;
24         int groups = len / k;
25         while (groups-- > 0) {
26             int count = 1;
27             cur = pre->next;
28             ListNode* curt = cur;
29             ListNode* next = cur->next;
30             ListNode* nextNext = NULL;
31             while (count++ < k) {
32                 nextNext = next->next;
33                 next->next = cur;
34                 cur = next;
35                 next = nextNext;
36             }
37             pre->next = cur;
38             pre = curt;
39             pre->next = nextNext;
40         }
41         return dummy->next;
42     }
43 };
View Code

leetcode 146. LRU Cache--腾讯面试题

题意:

为最近最少使用(LRU)缓存策略设计一个数据结构,它应该支持如下操做:获取数据(get)和写入数据(set)。

获取数据get(key):若是缓存中存在key,则获取其数据值(一般是正数),不然返回-1。

写入数据set(key, value):若是key尚未在缓存中,则写入其数据值。当缓存达到上限,它应该在写入新数据以前删除最近最少使用的数据用来腾出空闲位置。
View Code
1 Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
2 
3 get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
4 put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
5 
6 Follow up:
7 Could you do both operations in O(1) time complexity?
View Code

思路:利用双向链表+hashmap。对于get方法,若是hashmap中存在相应的key,则取出返回,并将对应节点移动到链表的尾部,表示最新使用过,反之返回-1;对于put方法,先判断要put的值map中是否存在,若是存在则将相应节点移动到链表尾部,表示最新使用过,若是不存在要看当前链表长度是否已经到达cache的容量,若是到达了容量,则要删除链表头部节点,并将待插入节点插入链表尾部,反之直接插入链表尾部。因此要自定义一个将节点移动到链表尾部的方法。

 1 public class LRUCache {
 2     public class DoublyListNode {
 3         int val = 0;
 4         int key = 0;
 5         DoublyListNode next = null;
 6         DoublyListNode prev = null;
 7         public DoublyListNode(int val) {
 8             this.val = val;
 9         }
10     }
11     int capacity = 0;
12     int curtSize = 0;
13     HashMap<Integer, DoublyListNode> map;
14     DoublyListNode head = null;
15     DoublyListNode tail = null;
16     public LRUCache(int capacity) {
17         this.capacity = capacity;
18         map = new HashMap<>();
19     }
20     
21     public int get(int key) {
22         int value = -1;
23         if (map.containsKey(key)) {
24             DoublyListNode curt = map.get(key);
25             value = curt.val;
26             moveToTail(curt);
27         }
28         return value;
29     }
30     
31     public void put(int key, int value) {
32         if (capacity == 0) {
33             return;
34         }
35         DoublyListNode curt = null;
36         if (map.containsKey(key)) {
37             curt = map.get(key);
38             curt.val = value;
39             moveToTail(curt);
40         } else {
41             if (curtSize == capacity) {
42                 int k = head.key;
43                 map.remove(k);
44                 head = head.next;
45                 if (head != null) {
46                     head.prev = null;
47                 }
48                 curtSize--;
49             }
50             curt = new DoublyListNode(value);
51             curt.key = key;
52             map.put(key, curt);
53             if (head == null) {
54                 head = curt;
55             } else {
56                 tail.next = curt;
57                 curt.prev = tail;
58             }
59             curtSize++;
60             tail = curt;
61             tail.next = null;
62         }
63     }
64     public void moveToTail(DoublyListNode curt) {
65         if (curt.next == null) {
66             return;
67         }
68         //看是否在头部
69         if (curt.prev != null) {
70             curt.prev.next = curt.next;
71             curt.next.prev = curt.prev;
72             curt.prev = null;
73         } else {
74             head = head.next;
75             head.prev = null;
76         }
77         tail.next = curt;
78         curt.prev = tail;
79         tail = curt;
80         tail.next = null;        
81     }
82 }
83 
84 /**
85  * Your LRUCache object will be instantiated and called as such:
86  * LRUCache obj = new LRUCache(capacity);
87  * int param_1 = obj.get(key);
88  * obj.put(key,value);
89  */
View Code

 

leetcode 11 Container With Most Water

题意:

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.
View Code

思路:两指针分别从头和尾开始,找出比前一个长度高的竖线。

代码:

 1 public class Solution {
 2     public int maxArea(int[] height) {
 3         int left = 0;
 4         int right = height.length - 1;
 5         int max = 0;
 6         while (left < right) {
 7             int h = Math.min(height[right], height[left]);
 8             max = Math.max(max, (right - left) * h);
 9             while (height[left] <= h && left < right) {
10                 left++;
11             }
12             while (height[right] <= h && left < right) {
13                 right--;
14             }
15         }
16         return max;
17     }
18 }
View Code

 

扔鸡蛋问题

There is a building of n floors. If an egg drops from the k th floor or above, it will break. If it's dropped from any floor below, it will not break.

You're given two eggs, Find k while minimize the number of drops for the worst case. Return the number of drops in the worst case.

思路:

2016/11/29 first 题意没明白 若是一直不明白就记住吧
好比说有100层楼,从N楼开始扔鸡蛋会碎,低于N楼扔不会碎,如今给咱们两个鸡蛋,让咱们找到N,而且最小化最坏状况。
由于只有两个鸡蛋,因此第一个鸡蛋应该是按必定的间距扔,好比10楼,20楼,30楼等等,好比10楼和20楼没碎,30楼碎了,那么第二个鸡蛋就要作线性搜索,分别尝试21楼,22楼,23楼等等直到鸡蛋碎了,就能找到临界点。那么咱们来看下列两种状况:
1. 假如临界点是9楼,那么鸡蛋1在第一次扔10楼碎掉,而后鸡蛋2依次遍历1到9楼,则总共须要扔10次。
2. 假如临界点是100楼,那么鸡蛋1须要扔10次,到100楼时碎掉,而后鸡蛋2依次遍历91楼到100楼,总共须要扔19次。
因此上述方法的最坏状况是19次,那么有没有更少的方法呢,上面那个方法每多扔一次鸡蛋1,鸡蛋2的线性搜索次数最多仍是10次,那么最坏状况确定会增长,因此咱们须要让每多扔一次鸡蛋1,鸡蛋2的线性搜索最坏状况减小1,这样可以保持总体最坏状况的平衡,那么咱们假设鸡蛋1第一次在第X层扔,而后向上X-1层扔一次,而后向上X-2层扔,以此类推直到100层,那么咱们经过下面的公式求出X:
X + (X-1) + (X-2) + ... + 1 = 100 -&gt; X = 14
因此咱们先到14楼,而后27楼,而后39楼,以此类推,最坏状况须要扔14次。
View Code

代码(注意数据类型long的使用):

 1 public class Solution {
 2     /**
 3      * @param n an integer
 4      * @return an integer
 5      */
 6     public int dropEggs(int n) {
 7         // Write your code here
 8         long sum = 0;
 9         for (int i = 1; i <= n; i++) {
10             sum += (long) i;
11             if (sum >= (long) n) {
12                 return i;
13             }
14         }
15         return 0;
16     }
17 }
View Code

leetcode 47 permutations II

题意:跟leetcode46的不一样点只是数字有重复的。在每一层递归中加上一个set就行了。

 1 class Solution {
 2 public:
 3     vector<vector<int>> permuteUnique(vector<int>& nums) {
 4         vector<vector<int>> ans;
 5         helper(nums, 0, ans);
 6         return ans;
 7     }
 8     void helper(vector<int>& nums, int index, vector<vector<int>>& ans) {
 9         if (index == nums.size() - 1) {
10             ans.push_back(nums);
11             return;
12         }
13         set<int> set;
14         for (int i = index; i < nums.size(); i++) {
15             if (set.find(nums[i]) == set.end()) {
16                 set.insert(nums[i]);
17                 swap(nums[i], nums[index]);
18                 helper(nums, index + 1, ans);
19                 swap(nums[i], nums[index]);
20             }
21         }
22     }
23 };
View Code

leetcode 46 permutations--微软面试题

题意:求出无重复字符串的全部排列。

解法:以前都是用dfs来作的。如今有了更好的解法-交换。每一位数字都跟后面的数字交换,递归。

 1 class Solution {
 2 public:
 3     vector<vector<int>> permute(vector<int>& nums) {
 4         vector<vector<int>> ans;
 5         helper(nums, 0, ans);
 6         return ans;
 7     }
 8     void helper(vector<int>& nums, int index, vector<vector<int>>& ans) {
 9         if (index == nums.size() - 1) {
10             ans.push_back(nums);
11             return;
12         }
13         for (int i = index; i < nums.size(); i++) {
14             swap(nums[i], nums[index]);
15             helper(nums, index + 1, ans);
16             swap(nums[i], nums[index]);
17         }
18     }
19 };
View Code

leetcode 28. Implement strStr()

题意:找一个字符串在另外一个字符串中出现的位置

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
View Code

解法:O(n^2)解法,循环查找,注意字符串长度为零的时候的状况

 1 public class Solution {
 2     public int strStr(String haystack, String needle) {
 3         if (haystack == null || needle == null) {
 4             return -1;
 5         }
 6         if (needle.length() == 0) {
 7             return 0;
 8         }
 9         for (int i = 0; i < haystack.length(); i++) {
10             for (int j = 0; j < needle.length(); j++) {
11                 if (i + needle.length() > haystack.length()) {
12                     return -1;
13                 }
14                 if (needle.charAt(j) != haystack.charAt(i + j)) {
15                     break;
16                 }
17                 if (j == needle.length() - 1) {
18                     return i;
19                 }
20             }
21         }
22         return -1;
23     }
24 }
View Code

 

leetcode 233. Number of Digit One

难度:hard

题意:

1 Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
2 
3 For example:
4 Given n = 13,
5 Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.
6 
7 Hint:
8 
9 Beware of overflow.
View Code

解析:1.数学公式的方法,比较难理解        

 1 Solution explanation:
 2 
 3 Let's start by counting the ones for every 10 numbers...
 4 
 5 0, 1, 2, 3 ... 9 (1)
 6 
 7 10, 11, 12, 13 ... 19 (1) + 10
 8 
 9 20, 21, 22, 23 ... 29 (1)
10 
11 ...
12 
13 90, 91, 92, 93 ... 99 (1)
14 
15 100, 101, 102, 103 ... 109 (10 + 1)
16 
17 110, 111, 112, 113 ... 119 (10 + 1) + 10
18 
19 120, 121, 122, 123 ... 129 (10 + 1)
20 
21 ...
22 
23 190, 191, 192, 193 ... 199 (10 + 1)
24 
25 1). If we don't look at those special rows (start with 10, 110 etc), we know that there's a one at ones' place in every 10 numbers, there are 10 ones at tens' place in every 100 numbers, and 100 ones at hundreds' place in every 1000 numbers, so on and so forth.
26 
27 Ok, let's start with ones' place and count how many ones at this place, set k = 1, as mentioned above, there's a one at ones' place in every 10 numbers, so how many 10 numbers do we have?
28 
29 The answer is (n / k) / 10.
30 
31 Now let's count the ones in tens' place, set k = 10, as mentioned above, there are 10 ones at tens' place in every 100 numbers, so how many 100 numbers do we have?
32 
33 The answer is (n / k) / 10, and the number of ones at ten's place is (n / k) / 10 * k.
34 
35 Let r = n / k, now we have a formula to count the ones at k's place: r / 10 * k
36 
37 2). So far, everything looks good, but we need to fix those special rows, how?
38 
39 We can use the mod. Take 10, 11, and 12 for example, if n is 10, we get (n / 1) / 10 * 1 = 1 ones at ones's place, perfect, but for tens' place, we get (n / 10) / 10 * 10 = 0, that's not right, there should be a one at tens' place! Calm down, from 10 to 19, we always have a one at tens's place, let m = n % k, the number of ones at this special place is m + 1, so let's fix the formula to be:
40 
41 r / 10 * k + (r % 10 == 1 ? m + 1 : 0)
42 
43 3). Wait, how about 20, 21 and 22?
44 
45 Let's say 20, use the above formula we get 0 ones at tens' place, but it should be 10! How to fix it? We know that once the digit is larger than 2, we should add 10 more ones to the tens' place, a clever way to fix is to add 8 to r, so our final formula is:
46 
47 (r + 8) / 10 * k + (r % 10 == 1 ? m + 1 : 0)
48 
49 As you can see, it's all about how we fix the formula. Really hope that makes sense to you.
View Code

代码:

1.数学公式

 1 public class Solution {
 2     public int countDigitOne(int n) {
 3         int count = 0;
 4         for (long k = 1; k <= n; k *= 10) {
 5             long r = n / k;
 6             long m = n % k;
 7             count += (r + 8) / 10 * k + (r % 10 == 1 ? m + 1 : 0);
 8         }
 9         return count;
10     }
11 }
View Code

2.递归求解的方法,参照《剑指offer》的解法。先求出最高位出现1的次数,再算出后面几位出现1的次数,而后加上去除最高位以后的数字出现1的次数。

 1 public class Solution {
 2     public int countDigitOne(int n) {
 3         if (n <= 0) {
 4             return 0;
 5         }
 6         String num = String.valueOf(n);
 7         return count(num);
 8     }
 9     public int count(String num) {
10         if (num == null || num.length() == 0) {
11             return 0;
12         }
13         char first = num.charAt(0);
14         int numOfFirst = 0;
15         if (first == '1') {
16             if (num.length() > 1) {
17                 numOfFirst = Integer.valueOf(num.substring(1)) + 1;
18             } else {
19                 numOfFirst = 1;
20             }
21         } else if (first > '1') {
22             numOfFirst = (int)Math.pow(10, num.length() - 1);
23         }
24         int numOfOthers = 0;
25         if (num.length() > 1) {
26             numOfOthers = (first - '0') * (num.length() - 1) * (int)Math.pow(10, num.length() - 2);
27         }
28         return numOfFirst + numOfOthers + count(num.substring(1));
29     }
30 }
View Code

1.注意overflow

leetcode 153. Find Minimum in Rotated Sorted Array--搜狐面试题

题意:

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.
View Code

解法:二分法,判断中间数字与头尾数字的关系

1.中间数字大于等于头数字,则最小数字在中间数字(包括)与末尾数字(包括)之间

2.中间数字小于等于头数字,则最小数字在中间数字(包括)与头数字(包括)之间

注意当有重复数字的时候,没法使用二分法,只能顺序查找。举一个例子原始数组是 0,1,1,1,1 旋转后多是1,0,1,1,1或者1,1,1,0,1 ,根据以前的方法无法断定0是在左边仍是右边。

 1 public class Solution {
 2     public int findMin(int[] nums) {
 3         if (nums == null || nums.length == 0) {
 4             return 0;
 5         }
 6         int end = nums.length - 1;
 7         int start = 0;
 8         if (nums[start] < nums[end]) {
 9             return nums[start];
10         }
11         while (start < end - 1) {
12             int mid = start + (end - start) / 2;
13             if (nums[mid] >= nums[start]) {
14                 start = mid;
15             } else {
16                 end = mid;
17             }
18         }
19         return nums[end];
20     }
21 }
View Code

bug-free process

1.第三次作了,注意无重复元素的时候使用二分法,有重复元素的时候只能顺序查找,给面试官举反例

leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal

题意:

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

解法:递归,树的遍历

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     int index = 0;
12     public TreeNode buildTree(int[] preorder, int[] inorder) {
13         if (preorder == null || preorder.length == 0 || inorder == null || inorder.length == 0) {
14             return null;
15         }
16         Map<Integer, Integer> in = new HashMap<>();
17         for (int i = 0; i < inorder.length; i++) {
18             in.put(inorder[i], i);
19         }
20         return helper(preorder, inorder, 0, inorder.length - 1, in);
21     }
22     public TreeNode helper(int[] preorder, int[] inorder, int start, int end, Map<Integer, Integer> in) {
23         if (index > preorder.length || start > end) {
24             return null;
25         }
26         TreeNode root = new TreeNode(preorder[index]);
27         int pos = in.get(preorder[index]);
28         index++;
29         root.left = helper(preorder, inorder, start, pos - 1, in);
30         root.right = helper(preorder, inorder, pos + 1, end, in);
31         return root;
32     }
33 }
View Code

bug-free process

1。第三次作,找到了最优解法。改进之处是先将中序遍历的索引号记住,在中序遍历中查找根节点的时候就节省时间。

leetcode 396. Rotate Function

题意:

Given an array of integers A and let n to be its length.

Assume Bk to be an array obtained by rotating the array A k positions clock-wise, we define a "rotation function" F on A as follow:

F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1].

Calculate the maximum value of F(0), F(1), ..., F(n-1).

Note:
n is guaranteed to be less than 105.

Example:

A = [4, 3, 2, 6]

F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26

So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.
View Code

解法:找到F(k)和F(k-1) 之间的关系

F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1]

F(k-1) = 0 * Bk[1] + 1 * Bk[2] + ... + (n-2) * Bk[n-1]+(n-1) * Bk[0] 

F(k) - F(k-1) = Bk[1] + Bk[2] + ... + Bk[n-1] + (1-n) * Bk[0] 

      = Bk[0] + Bk[1] + Bk[2] + ... + Bk[n-1] - n*Bk[0] 

      = A[0] + A[1] +...+A[n-1] + n*Bk[0] 

因此先求出F[0],而后F[k]均可以求出来了,注意Bk[0] 的变化是从A[0],A[n-1] ...A[1] 

public class Solution {
    public int maxRotateFunction(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        int n = A.length;
        int sum = 0;
        int f = 0;
        for (int i = 0; i < n; i++) {
            sum += A[i];
            f += i * A[i];
        }
        int max = f;
        for (int i = n - 1; i >= 1; i--) {
            f = f + sum - n * A[i];
            max = Math.max(f, max);
        }
        return max;
    }
}
View Code

1.找到F(k)和F(k-1) 之间的关系 2017/01/16

leetcode 342. Power of Four

题意:

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example:
Given num = 16, return true. Given num = 5, return false.

Follow up: Could you solve it without loops/recursion?
View Code

解法:仍是跟前面两题同样,也有简单的方法。总结4的次方的二进制表示的规律01,100,10000,1000000...,能够发现只有一个1而且1出如今奇数位上(末尾是第一位)。

因此用 n&(n-1) ==  0 && (n & 0x55555555) != 0 ,0x55555555 = 01010101010101010101010101010101,保证了只有奇数位上有1.

1 public class Solution {
2     public boolean isPowerOfFour(int num) {
3         return num > 0 && (num & (num - 1)) == 0 && (num & 0x55555555) != 0;
4     }
5 }
View Code

bug-free process

1.位操做的解法2017/01/04

leetcode 326. Power of Three

题意:

1 Given an integer, write a function to determine if it is a power of three.
2 
3 Follow up:
4 Could you do it without using any loop / recursion?
View Code

解法:跟leetcode231同样有循环的解法。可是也有tricky的解法。3的次方有特殊性:被3的次方整除的数必定是3的次方,找到int范围内最大3的次方3^19 = 1162261467,判断是否能够被其整除。

1 public class Solution {
2     public boolean isPowerOfThree(int n) {
3         return n > 0 && (1162261467 % n == 0);
4     }
5 }
View Code

bug-free process

1.更新了解法 2017/01/04

leetcode 231. Power of Two

题意:

Given an integer, write a function to determine if it is a power of two.
View Code

解法:最容易想到的解法是循环除以2,出现余数不为零的状况则不是2的次方。

可是有更好的方法就是总结2的次方数的二进制表示规律 01,10,100,1000,10000...,能够发现只有一个1,因此n&(n-1) = 0,反之则不是2的次方

1 public class Solution {
2     public boolean isPowerOfTwo(int n) {
3         return n > 0 && (n & (n - 1)) == 0;
4     }
5 }
View Code

bug-free process :

1.更新了解法。2017/01/04

leetcode 389. Find the Difference

题意:

Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t.

Example:

Input:
s = "abcd"
t = "abcde"

Output:
e

Explanation:
'e' is the letter that was added.
View Code

解法:与single number这题解法同样,都是异或,剩下的就是多出来的字符

1 public class Solution {
2     public char findTheDifference(String s, String t) {
3         int ret = t.charAt(0) - 'a';
4         for (int i = 0; i < s.length(); i++) {
5             ret ^= ((s.charAt(i) - 'a') ^ (t.charAt(i + 1) - 'a'));
6         }
7         return (char) (ret + 'a');
8     }
9 }
View Code

 

leetcode 387. First Unique Character in a String

题意:

Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.

Examples:

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.
Note: You may assume the string contain only lowercase letters.
View Code

解法:先记录每一个字母出现的次数。再从头遍历字符串发现次数为1的字母则返回索引值。

 1 public class Solution {
 2     public int firstUniqChar(String s) {
 3         if (s == null || s.length() == 0) {
 4             return -1;
 5         }
 6         int[] count = new int[26];
 7         for (int i = 0; i < s.length(); i++) {
 8             count[s.charAt(i) - 'a']++;
 9         }
10         for (int i = 0; i < s.length(); i++) {
11             if (count[s.charAt(i) - 'a'] == 1) {
12                 return i;
13             }
14         }
15         return -1;
16     }
17 }
View Code

bug-free process:

1.利用数组记录次数。 2017/01/02

leetcode 386. Lexicographical Numbers

题意:

Given an integer n, return 1 - n in lexicographical order.

For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].

Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.
View Code

解法:题意中的字典序实际上是按照字符串的字典序来排序整数。

对于一个整数 546 下一个字典序多是5460 (if 460 <=  n),或者547(if 47 <=  n),或者是55.

当个位数是9,好比549,则下一个若是不是5490,也不是550,而是55

 1 public class Solution {
 2     public List<Integer> lexicalOrder(int n) {
 3         List<Integer> ans = new ArrayList<>();
 4         int cur = 1;
 5         for (int i = 0; i < n; i++) {
 6             ans.add(cur);
 7             if (cur * 10 <= n) {
 8                 cur *= 10;
 9             } else if (cur % 10 != 9 && cur + 1 <= n) {
10                 cur++;
11             } else {
12                 while ((cur / 10) % 10 == 9) {
13                     cur /= 10;
14                 }
15                 cur = cur / 10 + 1;
16             }
17         }
18         return ans;
19     }
20 }
View Code

bug-free process:

1.必须重作一次,三种状况 2017/01/02

leetcode 383. Ransom Note

题意:

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

Note:
You may assume that both strings contain only lowercase letters.

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true
View Code

解法:题意是判断前一个单词是否能够由后一个单词的字母给组合起来,每个字母只能使用一次的状况下。

先记录后一个单词每一个字母出现的次数,再遍历前一个单词,将相应字母次数减一,减到小于0则返回false;

 1 public class Solution {
 2     public boolean canConstruct(String ransomNote, String magazine) {
 3         int[] count = new int[26];
 4         for (int i = 0; i < magazine.length(); i++) {
 5             count[magazine.charAt(i) - 'a']++;
 6         }
 7         for (int i = 0; i < ransomNote.length(); i++) {
 8             if (count[ransomNote.charAt(i) - 'a']-- == 0) {
 9                 return false;
10             }
11         }
12         return true;
13     }
14 }
View Code

1.没看懂题意 2017/01/02

leetcode 384. Shuffle an Array

题意:

Shuffle a set of numbers without duplicates.

Example:

// Init an array with set 1, 2, and 3.
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.
solution.shuffle();

// Resets the array back to its original configuration [1,2,3].
solution.reset();

// Returns the random shuffling of array [1,2,3].
solution.shuffle();
View Code

解法:shuffle操做:从左至右遍历数组,将当前元素与以前的遍历过的元素(包括本身)随机交换。

 1 public class Solution {
 2     int[] nums = null;
 3     int[] copy = null;
 4     Random random = null;
 5     public Solution(int[] nums) {
 6         this.nums = nums;
 7         copy = nums.clone();
 8         random = new Random();
 9     }
10     
11     /** Resets the array to its original configuration and return it. */
12     public int[] reset() {
13         return nums;
14     }
15     
16     /** Returns a random shuffling of the array. */
17     public int[] shuffle() {
18         for (int i = 1; i < copy.length; i++) {
19             int j = random.nextInt(i + 1);
20             swap(copy, i, j);
21         }
22         return copy;
23     }
24     public void swap(int[] nums, int i, int j) {
25         int temp = nums[i];
26         nums[i] = nums[j];
27         nums[j] = temp;
28     }
29 }
30 
31 /**
32  * Your Solution object will be instantiated and called as such:
33  * Solution obj = new Solution(nums);
34  * int[] param_1 = obj.reset();
35  * int[] param_2 = obj.shuffle();
36  */
View Code

1.随机交换2017/01/02

leetcode 398. Random Pick Index

题意:

Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.

Note:
The array size can be very large. Solution that uses too much extra space will not pass the judge.

Example:

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);

// pick(1) should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(1);
View Code

解法:用上一题(leetcode 382)的解法。注意的是不能将数组排序,由于排序以后索引就变了,就会出现错误。

错误代码(将数组排序了):

 1 public class Solution {
 2     int[] nums = null;
 3     public Solution(int[] nums) {
 4         this.nums = nums;
 5         Arrays.sort(this.nums);
 6     }
 7     
 8     public int pick(int target) {
 9         int ans = 0;
10         for (int i = 0; i < nums.length; i++) {
11             if (nums[i] == target) {
12                 ans = i;
13                 break;
14             }
15         }
16         int start = ans;
17         for (int i = 1; start + i < nums.length && nums[start + i] == target; i++) {
18             if (randomInt(start, start + i) == start) {
19                 ans = start + i;
20             }
21         }
22         return ans;
23     }
24     public int randomInt(int min, int max) {
25         return min + (int) (Math.random() * (max - min + 1)); 
26     }
27 }
28 
29 /**
30  * Your Solution object will be instantiated and called as such:
31  * Solution obj = new Solution(nums);
32  * int param_1 = obj.pick(target);
33  */
View Code

正确的代码

 1 public class Solution {
 2     int[] nums = null;
 3     public Solution(int[] nums) {
 4         this.nums = nums;
 5     }
 6     
 7     public int pick(int target) {
 8         int ans = -1;
 9         int count = 0;
10         for (int i = 0; i < nums.length; i++) {
11             if (nums[i] != target) {
12                 continue;
13             }
14             if (randomInt(0, count++) == 0) {
15                 ans = i;
16             }
17         }
18         return ans;
19     }
20     public int randomInt(int min, int max) {
21         return min + (int) (Math.random() * (max - min + 1)); 
22     }
23 }
24 
25 /**
26  * Your Solution object will be instantiated and called as such:
27  * Solution obj = new Solution(nums);
28  * int param_1 = obj.pick(target);
29  */
View Code

bug-free process:

1.与382相似的题,注意不能将数组提早排序。2017/01/02

leetcode 382. Linked List Random Node

题意:

Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen.

Follow up:
What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?

Example:

// Init a singly linked list [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);

// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();
View Code

解法:

1.分析,也可看一下http://blog.jobbole.com/42550/

Problem:
Choose k entries from n numbers. Make sure each number is selected with the probability of k/n
Basic idea:
Choose 1, 2, 3, ..., k first and put them into the reservoir.
For k+1, pick it with a probability of k/(k+1), and randomly replace a number in the reservoir.
For k+i, pick it with a probability of k/(k+i), and randomly replace a number in the reservoir.
Repeat until k+i reaches n
Proof:
For k+i, the probability that it is selected and will replace a number in the reservoir is k/(k+i)
For a number in the reservoir before (let's say X), the probability that it keeps staying in the reservoir is
P(X was in the reservoir last time) × P(X is not replaced by k+i)
= P(X was in the reservoir last time) × (1 - P(k+i is selected and replaces X))
= k/(k+i-1) × (1 - k/(k+i) × 1/k)
= k/(k+i)
When k+i reaches n, the probability of each number staying in the reservoir is k/n
Example
Choose 3 numbers from [111, 222, 333, 444]. Make sure each number is selected with a probability of 3/4
First, choose [111, 222, 333] as the initial reservior
Then choose 444 with a probability of 3/4
For 111, it stays with a probability of
P(444 is not selected) + P(444 is selected but it replaces 222 or 333)
= 1/4 + 3/4*2/3
= 3/4
The same case with 222 and 333
Now all the numbers have the probability of 3/4 to be picked
This Problem <Linked List Random Node>
This problem is the sp case where k=1
View Code

2.代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    ListNode head;
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    public Solution(ListNode head) {
        this.head = head;
    }
    
    /** Returns a random node's value. */
    public int getRandom() {
        ListNode cur = head;
        int ans = cur.val;
        for (int i = 1; cur.next != null; i++) {
            cur = cur.next;
            //等于[0,i]之间的任何一个整数均可以
            if (randInt(0,i) == 0) {
                ans = cur.val;
            }
        }
        return ans;
     } 
    //返回[0, i]之间的随机整数,每一个数的几率就是1/i+1
    private int randInt(int min, int max) {
        return min + (int)(Math.random() * ((max - min) + 1));
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(head);
 * int param_1 = obj.getRandom();
 */
View Code

3.错误代码,注意在getRandom()函数里面head要保持不变,由于getRandom会调用屡次

 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     ListNode head;
11     /** @param head The linked list's head.
12         Note that the head is guaranteed to be not null, so it contains at least one node. */
13     public Solution(ListNode head) {
14         this.head = head;
15     }
16     
17     /** Returns a random node's value. */
18     public int getRandom() {
19         int ans = head.val;
20         for (int i = 1; head.next != null; i++) {
21             head = head.next;
22             //等于[0,i]之间的任何一个整数均可以
23             if (randInt(0,i) == 0) {
24                 ans = head.val;
25             }
26         }
27         return ans;
28      } 
29     //返回[0, i]之间的随机整数,每一个数的几率就是1/i+1
30     private int randInt(int min, int max) {
31         return min + (int)(Math.random() * ((max - min) + 1));
32     }
33 }
34 
35 /**
36  * Your Solution object will be instantiated and called as such:
37  * Solution obj = new Solution(head);
38  * int param_1 = obj.getRandom();
39  */
View Code

bug-free process :

1.这个算法挺重要,必须掌握 ,注意在getRandom()函数里面head要保持不变,由于getRandom会调用屡次2017/01/02

leetcode 377. Combination Sum IV

题意:

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.
Follow up:
What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers?
View Code

解法:dp 。O(target*nums.length).combinations[i]表示以i为target可以获得的组合数。for all j,combinations[i] += combinations[i-nums[j]](when  i >= nums[j]).

 1 public class Solution {
 2     public int combinationSum4(int[] nums, int target) {
 3         int[] combinations = new int[target + 1];
 4         combinations[0] = 1;
 5         for (int i = 1; i <= target; i++) {
 6             for (int j = 0; j < nums.length; j++) {
 7                 if (i >= nums[j]) {
 8                     combinations[i] += combinations[i - nums[j]];
 9                 }
10             }
11         }
12         return combinations[target];
13     }
14 }
View Code

1.dp以target为dp目标。 2016/12/29

2.dp解法。2017/01/12

leetcode 376. Wiggle Subsequence

题意:

A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.

For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

Examples:
Input: [1,7,4,9,2,5]
Output: 6
The entire sequence is a wiggle sequence.

Input: [1,17,5,10,13,15,10,5,16,8]
Output: 7
There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].

Input: [1,2,3,4,5,6,7,8,9]
Output: 2
Follow up:
Can you do it in O(n) time?
View Code

解法:dp 时间复杂度O(n),由O(n)空间复杂度减少为O(1).

用up[i]和down[i]表示到nums[i]为止的以上升和降低结束的子序列的最大长度。先后两个数,有三种可能性。

1.nums[i]>nums[i-1] ,up[i] = down[i-1] + 1;

2.nums[i]<nums[i-1] ,down[i] = up[i-1] + 1;

3.nums[i]=nums[i-1] ,down[i] = down[i-1];up[i] = up[i-1];

因为只跟前一个数有关,因此能够减小空间复杂度,直接用up和down两个变量来记录up[i]和down[i]

 1 public class Solution {
 2     public int wiggleMaxLength(int[] nums) {
 3         if (nums.length <= 1) {
 4             return nums.length;
 5         }
 6         int len = nums.length;
 7         int up = 1;
 8         int down = 1;
 9         for (int i = 1; i < len; i++) {
10             if (nums[i] > nums[i - 1]) {
11                 up = down + 1;
12             } else if (nums[i] < nums[i - 1]) {
13                 down = up + 1;
14             }
15         }
16         return Math.max(up, down);
17     }
18 }
View Code

1.dp O(n)+O(1) ,up + down 2016/12/29

leetcode 375. Guess Number Higher or Lower II

题意:

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I'll tell you whether the number I picked is higher or lower.

However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.

Example:

n = 10, I pick 8.

First round:  You guess 5, I tell you that it's higher. You pay $5.
Second round: You guess 7, I tell you that it's higher. You pay $7.
Third round:  You guess 9, I tell you that it's lower. You pay $9.

Game over. 8 is the number I picked.

You end up paying $5 + $7 + $9 = $21.
Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.

Hint:

The best strategy to play the game is to minimize the maximum loss you could possibly face. Another strategy is to minimize the expected loss. Here, we are interested in the first scenario.
Take a small example (n = 3). What do you end up paying in the worst case?
Check out this article if you're still stuck.
The purely recursive implementation of minimax would be worthless for even a small n. You MUST use dynamic programming.
As a follow-up, how would you modify your code to solve the problem of minimizing the expected loss, instead of the worst-case loss?
View Code

解法:dp + recursion

For each number x in range[i~j]
we do: result_when_pick_x = x + max{DP([i~x-1]), DP([x+1, j])}
--> // the max means whenever you choose a number, the feedback is always bad and therefore leads you to a worse branch.
then we get DP([i~j]) = min{xi, ... ,xj}
--> // this min makes sure that you are minimizing your cost.

 1 public class Solution {
 2     public int getMoneyAmount(int n) {
 3         int start = 1;
 4         int end = n;
 5         int[][] dp = new int[n + 1][n + 1];
 6         return helper(dp, start, end);
 7     }
 8     public int helper(int[][] dp, int start, int end) {
 9         if (start >= end) {
10             return 0;
11         }
12         if (dp[start][end] != 0) {
13             return dp[start][end];
14         }
15         dp[start][end] = Integer.MAX_VALUE;
16         for (int i = start; i <= end; i++) {
17             int tmp = i + Math.max(helper(dp, start, i - 1), helper(dp, i + 1, end));
18             dp[start][end] = Math.min(tmp, dp[start][end]);
19         }
20         return dp[start][end];
21     }
22 }
View Code

1.dp的解法 2016/12/28

leetcode 374. Guess Number Higher or Lower

题意:

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I'll tell you whether the number is higher or lower.

You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):

-1 : My number is lower
 1 : My number is higher
 0 : Congrats! You got it!
Example:
n = 10, I pick 6.

Return 6.
View Code

解法:Binary Search。坑在了题意,Here "My" means the number which is given for you to guess not the number you put into guess(int num).

 1 /* The guess API is defined in the parent class GuessGame.
 2    @param num, your guess
 3    @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
 4       int guess(int num); */
 5 
 6 public class Solution extends GuessGame {
 7     public int guessNumber(int n) {
 8         int start = 1;
 9         int end = n;
10         while (start <= end) {
11             int mid = start + (end - start) / 2;
12             int res = guess(mid);
13             if (res == 0) {
14                 return mid;
15             } else if (res == -1) {
16                 end = mid - 1;
17             } else {
18                 start = mid + 1;
19             }
20         }
21         return 0;      
22     }
23 }
View Code

bug-free process:

1.bug-free 2016/12/28

leetcode 372. Super Pow

题意:

Your task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.

Example1:

a = 2
b = [3]

Result: 8
Example2:

a = 2
b = [1,0]

Result: 1024
View Code

解法:尚未太理解2016/12/28

 

leetcode 368. Largest Divisible Subset

题意:

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0.

If there are multiple solutions, return any subset is fine.

Example 1:

nums: [1,2,3]

Result: [1,2] (of course, [1,3] will also be ok)
Example 2:

nums: [1,2,4,8]

Result: [1,2,4,8]
View Code

解法:dp。整除具备传递性 if c % b  == 0 and b % a == 0, so c % a == 0。因此咱们先将数组排序,方便后面的查找。

count[i]表示觉得最大值nums[i]结束的subset的最大长度
pre[i]表示nums[i]的上一个比它小而且能够被它整除的的数的索引

 1 public class Solution {
 2     public List<Integer> largestDivisibleSubset(int[] nums) {
 3         //整除具备传递性 if c % b  == 0 and b % a == 0, so c % a == 0
 4         if (nums == null || nums.length == 0) {
 5             return new ArrayList<Integer>();
 6         }
 7         Arrays.sort(nums);
 8         int len = nums.length;
 9         //count[i]表示觉得最大值nums[i]结束的subset的最大长度
10         int[] count = new int[len];
11         //pre[i]表示nums[i]的上一个比它小而且能够被它整除的的数的索引
12         int[] pre = new int[len];
13         int endIndex = 0;
14         int max = 1;
15         for (int i = 0; i < len; i++) {
16             count[i] = 1;
17             pre[i] = -1;
18             for (int j = i - 1; j >= 0; j--) {
19                 if (nums[i] % nums[j] == 0) {
20                     if (1 + count[j] > count[i]) {
21                         count[i] = count[j] + 1;
22                         pre[i] = j;
23                     }
24                 }
25             }
26             if (count[i] > max) {
27                 endIndex = i;
28                 max = count[i];
29             }
30         }
31         List<Integer> ans = new ArrayList<Integer>();
32         ans.add(nums[endIndex]);
33         while (pre[endIndex] != -1) {
34             ans.add(nums[pre[endIndex]]);
35             endIndex = pre[endIndex];
36         }
37         return ans;
38     }
39 }
View Code

1.dp的作法 2016/12/27

leetcode 367. Valid Perfect Square

题意:判断一个数n是不是彻底平方数,不能用库函数。

解法:1.Binary Search O(logn)

 1 public class Solution {
 2     public boolean isPerfectSquare(int num) {
 3         long start = 1;
 4         long end = num;
 5         while (start <= end) {
 6             long mid = start + (end - start) / 2;
 7             if (mid * mid == (long) num) {
 8                 return true;
 9             } else if (mid * mid > (long) num) {
10                 end = mid - 1;
11             } else {
12                 start = mid + 1;
13             }
14         }
15         return false;
16     }
17 }
View Code

2.Math。利用彻底平方数的性质。O(n),可是代码简单。

This is a math problem:
1 = 1
4 = 1 + 3
9 = 1 + 3 + 5
16 = 1 + 3 + 5 + 7
25 = 1 + 3 + 5 + 7 + 9
36 = 1 + 3 + 5 + 7 + 9 + 11

因此让这个数不断减去递增的奇数,看最后是否会获得0;

 1 public class Solution {
 2     public boolean isPerfectSquare(int num) {
 3         int odd = 1;
 4         while (num > 0) {
 5             num -= odd;
 6             odd += 2;
 7         }
 8         return num == 0;
 9     }
10 }
View Code

bug-free process :

1.二分法和彻底平方数的性质 2016/12/27

365. Water and Jug Problem

题意:

You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.

If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.

Operations allowed:

Fill any of the jugs completely with water.
Empty any of the jugs.
Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.
Example 1: (From the famous "Die Hard" example)

Input: x = 3, y = 5, z = 4
Output: True
Example 2:

Input: x = 2, y = 6, z = 5
Output: False
View Code

解法:这题是纯数学题,只能硬背了。

去掉一些特殊状况(x == z || y == z || x +y == z)和 (x + y < z),剩下的状况先求x和y的最大公约数,在看z可否整除他们的最大公约数。

 1 public class Solution {
 2     public boolean canMeasureWater(int x, int y, int z) {
 3         if (x + y < z) {
 4             return false;
 5         }
 6         if (x == z || y == z || x +y == z) {
 7             return true;
 8         }
 9         return z % gcd(x, y) == 0; 
10     }
11     //最大公约数
12     public int gcd(int x, int y) {
13         while (y != 0) {
14             int temp = y;
15             y = x % y;
16             x = temp;
17         }
18         return x;
19     }
20 }
View Code

1.最大公约数的求法能够记住 2016/12/27

leetcode 357. Count Numbers with Unique Digits

题意:

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.

Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])

Hint:

A direct way is to use the backtracking approach.
Backtracking should contains three states which are (the current number, number of steps to get that number and a bitmask which represent which number is marked as visited so far in the current number). Start with state (0,0,0) and count all valid number till we reach number of steps equals to 10n.
This problem can also be solved using a dynamic programming approach and some knowledge of combinatorics.
Let f(k) = count of numbers with unique digits with length equals k.
f(1) = 10, ..., f(k) = 9 * 9 * 8 * ... (9 - k + 2) [The first factor is 9 because a number cannot start with 0].
View Code

解法:dp  。dp[i]表示长度为i+1的unique数字的个数。dp[0] = 10,dp[1] = 9 * 9,总结规律可知 dp[i] = dp[i - 1] * (9 - (i + 1) + 2).须要注意的是dp[0]须要变为0,由于0不能做为数字的开头。而后返回全部长度的个数和就能够了。

 1 public class Solution {
 2     public int countNumbersWithUniqueDigits(int n) {
 3         if (n == 0) {
 4             return 1;
 5         }
 6         int[] dp = new int[n];
 7         dp[0] = 9;
 8         int count = 10;
 9         for (int i = 1; i < n; i++) {
10             dp[i] = dp[i - 1] * (9 - (i  + 1) + 2);
11             count += dp[i];
12         }
13         return count;
14     }
15 }
View Code

1.注意0<=n<10^k,左闭右开的区间 2016/12/27

leetcode 355. Design Twitter

题意:

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able to see the 10 most recent tweets in the user's news feed. Your design should support the following methods:

postTweet(userId, tweetId): Compose a new tweet.
getNewsFeed(userId): Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
follow(followerId, followeeId): Follower follows a followee.
unfollow(followerId, followeeId): Follower unfollows a followee.
Example:

Twitter twitter = new Twitter();

// User 1 posts a new tweet (id = 5).
twitter.postTweet(1, 5);

// User 1's news feed should return a list with 1 tweet id -> [5].
twitter.getNewsFeed(1);

// User 1 follows user 2.
twitter.follow(1, 2);

// User 2 posts a new tweet (id = 6).
twitter.postTweet(2, 6);

// User 1's news feed should return a list with 2 tweet ids -> [6, 5].
// Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5.
twitter.getNewsFeed(1);

// User 1 unfollows user 2.
twitter.unfollow(1, 2);

// User 1's news feed should return a list with 1 tweet id -> [5],
// since user 1 is no longer following user 2.
twitter.getNewsFeed(1);
View Code

解法:HashMap+PriorityQueue.PriorityQueue读取最新的动态时,跟合并k个有序链表相似。

  1 public class Twitter {
  2     public static int timeStamp = 0;
  3     public class Tweet {
  4         int id = 0;
  5         int time = 0;
  6         Tweet next = null;
  7         public Tweet(int id) {
  8             this.id = id;
  9             this.time = timeStamp++;
 10         }
 11     }
 12     public class User {
 13         int id = 0;
 14         Set<Integer> followed = new HashSet<>();
 15         Tweet cur = null;
 16         public User(int id) {
 17             this.id = id;
 18             followed.add(id);
 19         }
 20         public void follow(int id) {
 21             followed.add(id);
 22         }
 23         public void unFollow(int id) {
 24             followed.remove(id);
 25         }
 26         public void post(int id) {
 27             Tweet tw = new Tweet(id);
 28             tw.next = cur;
 29             cur = tw;
 30         }
 31     }
 32     Map<Integer, User> userMap = null;
 33     /** Initialize your data structure here. */
 34     public Twitter() {
 35         userMap = new HashMap<>();
 36     }
 37     
 38     /** Compose a new tweet. */
 39     public void postTweet(int userId, int tweetId) {
 40         if (!userMap.containsKey(userId)) {
 41             userMap.put(userId, new User(userId));
 42         }
 43         userMap.get(userId).post(tweetId);
 44     }
 45     
 46     /** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
 47     public List<Integer> getNewsFeed(int userId) {
 48         List<Integer> ans = new ArrayList<>();
 49         if (!userMap.containsKey(userId)) {
 50             return ans;
 51         }
 52         PriorityQueue<Tweet> pq = new PriorityQueue<>(new MyComparator());
 53         for (int user : userMap.get(userId).followed) {
 54             Tweet tw = userMap.get(user).cur;
 55             if (tw != null) {
 56                 pq.offer(tw);
 57             }
 58         }
 59         int count = 0;
 60         while (!pq.isEmpty() && count < 10) {
 61             Tweet tw = pq.poll();
 62             ans.add(tw.id);
 63             count++;
 64             if (tw.next != null) {
 65                 pq.offer(tw.next);
 66             }
 67         }
 68         return ans;
 69     }
 70     
 71     /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
 72     public void follow(int followerId, int followeeId) {
 73         if (!userMap.containsKey(followerId)) {
 74             userMap.put(followerId, new User(followerId));
 75         }
 76         if (!userMap.containsKey(followeeId)) {
 77             userMap.put(followeeId, new User(followeeId));
 78         }
 79         userMap.get(followerId).follow(followeeId);
 80     }
 81     
 82     /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
 83     public void unfollow(int followerId, int followeeId) {
 84         if (!userMap.containsKey(followerId) || followerId == followeeId) {
 85             return;
 86         }
 87         userMap.get(followerId).unFollow(followeeId);
 88     }
 89     public class MyComparator implements Comparator<Tweet> {
 90         public int compare(Tweet t1, Tweet t2) {
 91             return t2.time - t1.time;
 92         }
 93     }
 94 }
 95 
 96 /**
 97  * Your Twitter object will be instantiated and called as such:
 98  * Twitter obj = new Twitter();
 99  * obj.postTweet(userId,tweetId);
100  * List<Integer> param_2 = obj.getNewsFeed(userId);
101  * obj.follow(followerId,followeeId);
102  * obj.unfollow(followerId,followeeId);
103  */
View Code

1.类封装的思想很重要。2016/12/27

leetcode 385. Mini Parser

题意:

Given a nested list of integers represented as a string, implement a parser to deserialize it.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Note: You may assume that the string is well-formed:

String is non-empty.
String does not contain white spaces.
String contains only digits 0-9, [, - ,, ].
Example 1:

Given s = "324",

You should return a NestedInteger object which contains a single integer 324.
Example 2:

Given s = "[123,[456,[789]]]",

Return a NestedInteger object containing a nested list with 2 elements:

1. An integer containing value 123.
2. A nested list containing two elements:
    i.  An integer containing value 456.
    ii. A nested list with one element:
         a. An integer containing value 789.
View Code

解法:注意题意要求返回的不是一个list,而是一个NestedInteger。

1.遇到'[',将当前cur入栈,而且新建一个NestedInteger

2.遇到']',如有数字,则将数字加入当前NestedInteger。栈顶元素出栈,而且将当前cur加入栈顶的NestedInteger。

3.遇到数字后面的',',则将数字加入当前的NestedInteger

最后返回当前的NestedInteger。

 1 /**
 2  * // This is the interface that allows for creating nested lists.
 3  * // You should not implement it, or speculate about its implementation
 4  * public interface NestedInteger {
 5  *     // Constructor initializes an empty nested list.
 6  *     public NestedInteger();
 7  *
 8  *     // Constructor initializes a single integer.
 9  *     public NestedInteger(int value);
10  *
11  *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
12  *     public boolean isInteger();
13  *
14  *     // @return the single integer that this NestedInteger holds, if it holds a single integer
15  *     // Return null if this NestedInteger holds a nested list
16  *     public Integer getInteger();
17  *
18  *     // Set this NestedInteger to hold a single integer.
19  *     public void setInteger(int value);
20  *
21  *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
22  *     public void add(NestedInteger ni);
23  *
24  *     // @return the nested list that this NestedInteger holds, if it holds a nested list
25  *     // Return null if this NestedInteger holds a single integer
26  *     public List<NestedInteger> getList();
27  * }
28  */
29 public class Solution {
30     public NestedInteger deserialize(String s) {
31         if (s == null || s.length() == 0) {
32             return null;
33         }
34         if (s.charAt(0) != '[') {
35             return new NestedInteger(Integer.valueOf(s));
36         }
37         int l = 0;
38         NestedInteger cur = null;
39         Stack<NestedInteger> stack = new Stack<>();
40         for (int r = 0; r < s.length(); r++) {
41             if (s.charAt(r) == '[') {
42                 if (cur != null) {
43                     stack.push(cur);
44                 }
45                 cur = new NestedInteger();
46                 l = r + 1;
47             } else if (s.charAt(r) == ']') {
48                 String num = s.substring(l, r);
49                 if (!num.isEmpty()) {
50                     cur.add(new NestedInteger(Integer.valueOf(num)));
51                 }
52                 if (!stack.isEmpty()) {
53                     NestedInteger top = stack.pop();
54                     top.add(cur);
55                     cur = top;
56                 }
57                 l = r + 1;
58             } else if (s.charAt(r) == ',') {
59                 if (s.charAt(r - 1) != ']') {
60                     String num = s.substring(l, r);
61                     cur.add(new NestedInteger(Integer.valueOf(num)));
62                 }
63                 l = r + 1;
64             }
65         }
66         return cur;
67     }
68 }
View Code

1.注意特殊状况的处理。当所给字符串只包含一个整数时,是形如“324”的。 2016/12/26

leetcode 341. Flatten Nested List Iterator

题意:

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Example 1:
Given the list [[1,1],2,[1,1]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2:
Given the list [1,[4,[6]]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].
View Code

解法:使用栈。将list中全部元素从后向前push到栈中,保证pop的时候是第一个元素。在hasNext中要安伯政栈顶的元素必定是Integer而不是list,也就是遇到list就要将其pop出来,再将其中的元素倒序push到栈中,直到栈顶元素是Integer。

 1 /**
 2  * // This is the interface that allows for creating nested lists.
 3  * // You should not implement it, or speculate about its implementation
 4  * public interface NestedInteger {
 5  *
 6  *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 7  *     public boolean isInteger();
 8  *
 9  *     // @return the single integer that this NestedInteger holds, if it holds a single integer
10  *     // Return null if this NestedInteger holds a nested list
11  *     public Integer getInteger();
12  *
13  *     // @return the nested list that this NestedInteger holds, if it holds a nested list
14  *     // Return null if this NestedInteger holds a single integer
15  *     public List<NestedInteger> getList();
16  * }
17  */
18 public class NestedIterator implements Iterator<Integer> {
19     Stack<NestedInteger> stack = null;
20     public NestedIterator(List<NestedInteger> nestedList) {
21         stack = new Stack<>();
22         for (int i = nestedList.size()- 1; i >= 0; i--) {
23             stack.push(nestedList.get(i));
24         }
25     }
26 
27     @Override
28     public Integer next() {
29         return stack.pop().getInteger();
30     }
31 
32     @Override
33     public boolean hasNext() {
34         while (!stack.isEmpty()) {
35             if (stack.peek().isInteger()) {
36                 return true;
37             }
38             NestedInteger cur = stack.pop();
39             for (int i = cur.getList().size() - 1; i >= 0; i--) {
40                 stack.push(cur.getList().get(i));
41             }
42         }
43         return false;
44     }
45 }
46 
47 /**
48  * Your NestedIterator object will be instantiated and called as such:
49  * NestedIterator i = new NestedIterator(nestedList);
50  * while (i.hasNext()) v[f()] = i.next();
51  */
View Code

1.注意hashNext里面的处理 2016/12/26

leetcode 354. Russian Doll Envelopes

题意:

You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.

What is the maximum number of envelopes can you Russian doll? (put one inside other)

Example:
Given envelopes = [[5,4],[6,4],[6,7],[2,3]], the maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).
View Code

解法:原型是leetcode 300。首先将所给数组进行预处理,将其封装成一个类,优先按照width排序,width相等的状况下按照height倒序排序。而后转化成了对height进行最长递增子序列的求解。

为何要这么排序?由于题意中并无要求按照顺序来叠信封,这么排序以后,就必须按照从前到后的顺序来了,知足最长递增子序列的背景,由于width是从小到大的,在width相等时,height是从大到小的,保证了width相等时,height增大也不会使子序列的长度增大。也能够先按照height来正序排序,再按照width来倒序排序。为何要一个正序一个倒序,看完下面这个例子就明白了。

[[2,3],[1,1],[4,6],[6,7],[4,5]],分别看两个都正序与一个正序一个倒序的状况。

 1 public class Solution {
 2     public int maxEnvelopes(int[][] envelopes) {
 3         if (envelopes.length < 2)
 4             return envelopes.length;
 5         A[] a = new A[envelopes.length];
 6         for (int i = 0; i < envelopes.length; i++) {
 7             a[i] = new A(envelopes[i][0], envelopes[i][1]);
 8         }
 9         Arrays.sort(a,new Comparator<A>(){
10             @Override
11             public int compare(A a, A b) {
12                 if (a.w != b.w) {
13                     return a.w - b.w;
14                 } else {
15                     return b.h - a.h;
16                 }
17             }
18         });        
19         int maxLen = 1;
20         int[] h = new int[envelopes.length];
21         h[0] = a[0].h;
22         for (int i = 1; i < envelopes.length; i++) {
23             int pos = getPos(h, 0, maxLen - 1, a[i].h);
24             if (pos == -1) {
25                 h[maxLen++] = a[i].h;                
26             } else 
27                 h[pos] = a[i].h;
28         }        
29         return maxLen;
30     }
31     public int getPos(int[] h, int start, int end, int num) {
32         int index = -1;
33         while (start <= end) {
34             int mid = start + (end - start) / 2;
35             if (h[mid] >= num) {
36                 end = mid - 1;
37                 index = mid;
38             } else {
39                 start = mid + 1;                
40             }            
41         }
42         return index;
43     }
44 }
45 class A {
46     int w = 0;
47     int h = 0;
48     public A(int w, int h) {
49         this.w = w;
50         this.h = h;
51     }
52 }
View Code

bug-free process:

1.注意预处理的方式 ,原型是leetcode300 2016/12/26

leetcode 334. Increasing Triplet Subsequence

题意:

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:
Return true if there exists i, j, k 
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.
Your algorithm should run in O(n) time complexity and O(1) space complexity.

Examples:
Given [1, 2, 3, 4, 5],
return true.

Given [5, 4, 3, 2, 1],
return false.
View Code

解法:将leetcode 300. Longest Increasing Subsequence的辅助数组改为长度为3就好了,若是第三位也被填了,说明存在长度为3的子序列。时间复杂度为O(n),空间复杂度为O(1).

 1 public class Solution {
 2     public boolean increasingTriplet(int[] nums) {
 3         if (nums == null || nums.length == 0) {
 4             return false;
 5         }
 6         int len = nums.length;
 7         int[] h = new int[3];
 8         h[0] = nums[0];
 9         h[1] = Integer.MAX_VALUE;
10         h[2] = Integer.MAX_VALUE;
11         for (int i = 1; i < len; i++) {
12             for (int j = 0; j < 3; j++) {
13                 if (h[j] >= nums[i]) {
14                     if (j == 2) {
15                         return true;
16                     }
17                     h[j] = nums[i];
18                     break;
19                 }
20             }
21         }
22         return false;
23     }
24 }
View Code

1.原型是leetcode300 2016/12/26

leetcode 300. Longest Increasing Subsequence

题意:

1 Given an unsorted array of integers, find the length of longest increasing subsequence.
2 
3 For example,
4 Given [10, 9, 2, 5, 3, 7, 101, 18],
5 The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.
6 
7 Your algorithm should run in O(n2) complexity.
8 
9 Follow up: Could you improve it to O(n log n) time complexity?
View Code

解法:若使用dp会得O(n^2)的解法。这里最优的解法是O(nlogn).

思路与代码:

 1 /*
 2  * solution2:  时间复杂度O(n*log(n)),空间复杂度O(n)
 3  * 新建一个辅助数组h,h[i]表示遍历到当前nums[j]位置时长度为i+1的递增子序列的最小末尾
 4  * h填入值的部分称做有效区,还未填入值的部分称做无效区
 5  * h[i]值的肯定,h[0] = nums[0],在遍历nums 的同时,在h[i]中找到第一个大于等于nums[j]的数,并将其替换为为nums[j],若是没找到则将h有效区后一个元素置为nums[j]
 6  * h[i]会一直保持有序状态,因此找第一个大于等于nums[j]的数能够用二分法,最后返回h有效区的长度便可
 7  * 因为在遍历的同时采用了时间复杂度为log(n)的二分查找,故时间复杂度为O(n*log(n))
 8  */
 9 public class Solution {
10     public int lengthOfLIS(int[] nums) {
11         int maxLen = 0;
12         if (nums.length == 0)
13             return maxLen;
14         int[] h = new int[nums.length];
15         h[0] = nums[0];
16         maxLen = 1;
17         for (int i = 1; i < nums.length; i++) {
18             int pos = getPos(h, 0, maxLen - 1, nums[i]);
19             if (pos == -1) {
20                 h[maxLen++] = nums[i];                
21             } else 
22                 h[pos] = nums[i];
23         }
24         return maxLen;        
25     }
26     public int getPos(int[] h, int start, int end, int num) {
27         int index = -1;
28         while (start <= end) {
29             int mid = start + (end - start) / 2;
30             if (h[mid] >= num) {
31                 end = mid - 1;
32                 index = mid;
33             } else {
34                 start = mid + 1;                
35             }            
36         }
37         return index;
38     }
39 }
View Code

bug-free process :

1.这题是代码原型,注意后面两题都要用到这个算法原型。 2016/12/26

leetcode 332. Reconstruct Itinerary

题意:

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:
If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
All airports are represented by three capital letters (IATA code).
You may assume all tickets form at least one valid itinerary.
Example 1:
tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Return ["JFK", "MUC", "LHR", "SFO", "SJC"].
Example 2:
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Return ["JFK","ATL","JFK","SFO","ATL","SFO"].
Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.
View Code

解法:题目是要找Eulerian path,顺便补充一下欧拉回路和欧拉路径的必要条件。

存在欧拉回路和欧拉路径的判断:
1)欧拉回路:
无向图:每一个顶点的度数都是偶数,则存在欧拉回路。
有向图:每一个顶点的入度都等于出度,则存在欧拉回路。
2)欧拉路径:
无向图:当且仅当该图全部顶点的度数为偶数 或者 除了两个度数为奇数外其他的全是偶数。
有向图:当且仅当该图全部顶点 出度=入度 或者 一个顶点 出度=入度+1,另外一个顶点 入度=出度+1,其 他顶点 出度=入度。

这题用Hierholzer's algorithm+PriorityQueue(用来确保字典序)+dfs。第一个出度变为零的节点确定就是末尾节点,PriorityQueue来存储节点的邻居,以字典序排序。

 1 public class Solution {
 2     Map<String, PriorityQueue<String>> graph;
 3     List<String> path;
 4     public List<String> findItinerary(String[][] tickets) {
 5         if (tickets == null || tickets.length == 0) {
 6             return new ArrayList<String>();
 7         }
 8         graph = new HashMap<>();
 9         for (String[] ticket : tickets) {
10             graph.putIfAbsent(ticket[0], new PriorityQueue());
11             graph.get(ticket[0]).add(ticket[1]);
12         }
13         path = new LinkedList<String>();
14         dfs("JFK");
15         return path;
16     }
17     public void dfs(String start) {
18         while (graph.containsKey(start) && !graph.get(start).isEmpty()) {
19             dfs(graph.get(start).poll());
20         }
21         path.add(0, start);
22     }
23 }
View Code

1.Eulerian path+Hierholzer's algorithm 2016/12/25

leetcode 331. Verify Preorder Serialization of a Binary Tree

题意:

One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as #.

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #
For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where # represents a null node.

Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character '#' representing null pointer.

You may assume that the input format is always valid, for example it could never contain two consecutive commas such as "1,,3".

Example 1:
"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return true

Example 2:
"1,#"
Return false

Example 3:
"9,#,#,1"
Return false
View Code

解法:利用节点的出入度。定义diff = outdegree - indegree。遇到下一个节点,将diff-1,由于增长了一个indegree,若是该节点不为空,则diff+2,由于它增长了两个outdegree。若是diff<0,则返回false,最后diff应该等于0.初始的时候diff=1.由于root没有入度。

 1 public class Solution {
 2     public boolean isValidSerialization(String preorder) {
 3         if (preorder == null) {
 4             return false;
 5         }
 6         String[] nodes = preorder.split(",");
 7         int diff = 1;
 8         for (String node : nodes) {
 9             if (--diff < 0) {
10                 return false;
11             }
12             if (!node.equals("#")) {
13                 diff += 2;
14             }
15         }
16         return diff == 0;
17     }
18 }
View Code

1.出入度的解法 2012/12/24

leetcode 324. Wiggle Sort II

题意:

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....

Example:
(1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6]. 
(2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].

Note:
You may assume all input has valid answer.

Follow Up:
Can you do it in O(n) time and/or in-place with O(1) extra space?
View Code

解法:先找到中位数,用quickselect找第k大的数 k = (len + 1) / 2;leetcode 215的算法。

  再用leetcode75的算法 + (1 + 2 * i) % (n | 1),后者的做用是将前半部分放到奇数位,后半部分放到偶数位。

 1 public class Solution {
 2      public void wiggleSort(int[] nums) {
 3         if (nums == null || nums.length == 0) {
 4             return;
 5         }
 6         int len = nums.length;
 7         int median = findKthLargestElement(nums, (len + 1) / 2, 0, len - 1);
 8         int left = 0;
 9         int right = len - 1;
10         int i = 0;
11         while (i <= right) {
12             if (nums[indexMapping(i, len)] > median) {
13                 swap(nums, indexMapping(i++, len), indexMapping(left++, len));
14             } else if (nums[indexMapping(i, len)] < median) {
15                 swap(nums, indexMapping(i, len), indexMapping(right--, len));
16             } else {
17                 i++;
18             }
19         }
20     }
21     public int indexMapping(int i, int n) {
22         return (1 + 2 * i) % (n | 1);
23     }
24     public void swap(int[] nums, int i, int j) {
25         int temp = nums[i];
26         nums[i] = nums[j];
27         nums[j] = temp;
28     }
29     public int findKthLargestElement(int[] nums, int k, int start, int end) {
30         if (start == end) {
31             return nums[start];
32         }
33         int left = start;
34         int right = end;
35         int pivot = nums[start + (end - start) / 2];
36         while (left <= right) {
37             while (left <= right && nums[left] < pivot) {
38                 left++;
39             }
40             while (left <= right && nums[right] > pivot) {
41                 right--;
42             }
43             if (left <= right) {
44                 int temp = nums[left];
45                 nums[left] = nums[right];
46                 nums[right] = temp;
47                 left++;
48                 right--;
49             }
50         }
51         if (end - left + 1 >= k) {
52             return findKthLargestElement(nums, k, left, end);
53         } else if (left - 1 == right) {
54             return findKthLargestElement(nums, k - (end - left + 1), start, right);
55         } else {
56             return findKthLargestElement(nums, k - (end - left + 1), start, right + 1);
57         }
58     }
59 }
View Code

leetcode 75. Sort Colors

题意:

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.
View Code

解法:一次替换的解法。O(n)时间复杂度,初始化两指针 left = 0;right = len - 1;

  在位置i遇到零将其与left交换,而且i++,left++

  遇到2将其与right交换,且right--;

  反之i++;

 1 public class Solution {
 2     public void sortColors(int[] nums) {
 3         if (nums == null || nums.length == 0) {
 4             return;
 5         }
 6         int left = 0;
 7         int right = nums.length - 1;
 8         int i = 0;
 9         while (i <= right) {
10             if (nums[i] == 0) {
11                 swap(nums, i, left);
12                 left++;
13                 i++;
14             } else if (nums[i] == 2) {
15                 swap(nums, i, right);
16                 right--;
17             } else {
18                 i++;
19             }
20         }
21     }
22     public void swap(int[] nums, int i, int j) {
23         int temp = nums[i];
24         nums[i] = nums[j];
25         nums[j] = temp;
26     }
27 }
View Code

2.一次替换 2012/12/22

leetcode 322. Coin Change

题意:

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Note:
You may assume that you have an infinite number of each kind of coin.
View Code

解法:dp。O(amount*n),n为coins数组的长度。

 1 public class Solution {
 2     public int coinChange(int[] coins, int amount) {
 3         if (amount == 0) {
 4             return 0;
 5         }
 6         if (amount == 0 || coins == null || coins.length == 0) {
 7             return -1;
 8         }
 9         int[] dp = new int[amount + 1];
10         dp[0] = 0;
11         for (int i = 1; i <= amount; i++) {
12             dp[i] = Integer.MAX_VALUE;
13             for (int j = 0; j < coins.length; j++) {
14                 if (i < coins[j]) {
15                     continue;
16                 }
17                 if (dp[i - coins[j]] != Integer.MAX_VALUE) {
18                     dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
19                 }
20             }
21         }
22         return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
23     }
24 }
View Code

 1.看到dp的提示,bug-free 2016/12/22

leetcode 319. Bulb Switcher

题意:

There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.

Example:

Given n = 3. 

At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off]. 

So you should return 1, because there is only one bulb is on.
View Code

解法:第i个灯泡位置i的因数是偶数个最后就是off,因数是奇数个最后就是on。有奇数个因数的数是彻底平方数。目的就是找前n个数有多少个彻底平方数。

  1.遍历,判断每一个数,遇到彻底平方数结果加一。TLE

  2.返回sqrt(n)。由于平方根是从1开始到sqrt(n)结束的,也就是说最多有sqrt(n)个彻底平方数。

1 public class Solution {
2     public int bulbSwitch(int n) {
3         return (int) Math.sqrt(n);
4     }
5 }
View Code

1.知道了快速求解1~n中彻底平方数个数的O(1)解法。2016/12/22

 leetcode 318. Maximum Product of Word Lengths

题意:

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:
Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return 16
The two words can be "abcw", "xtfn".

Example 2:
Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return 4
The two words can be "ab", "cd".

Example 3:
Given ["a", "aa", "aaa", "aaaa"]
Return 0
View Code

解法:位操做。主要是怎么判断两个单词是否包含共同的字母。用一个整数的某一位来表示相应位置字母是否存在,若存在置为1.若两个单词的位表示法按位与结果为零则不会包含共同字母。

 1 public class Solution {
 2     public int maxProduct(String[] words) {
 3         if (words == null || words.length == 0) {
 4             return 0;
 5         }
 6         int len = words.length;
 7         int[] bit = new int[len];
 8         for (int i = 0; i < len; i++) {
 9             for (int j = 0; j < words[i].length(); j++) {
10                 bit[i] |= 1 << (words[i].charAt(j) - 'a');
11             }
12         }
13         int max = 0;
14         for (int i = 0; i < len - 1; i++) {
15             for (int j = i + 1; j < len; j++) {
16                 if ((bit[i] & bit[j]) == 0) {
17                     max = Math.max(max, words[i].length() * words[j].length());
18                 }
19             }
20         }
21         return max;
22     }
23 }
View Code

bug-free process

1.位表示法,位运算符优先级较低,记得加括号 2016/12/21

leetcode 310. Minimum Height Trees

题意:

For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

Format
The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Example 1:

Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]

        0
        |
        1
       / \
      2   3
return [1]

Example 2:

Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

     0  1  2
      \ | /
        3
        |
        4
        |
        5
return [3, 4]

Hint:

How many MHTs can a graph have at most?
Note:

(1) According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”

(2) The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
View Code

解法:hint仍是很重要的,能够想到最多的root数是2,至关于图的最长一条路径的最中间的一个(奇数个)或两个(偶数个)节点。

因此将叶子节点一层一层删除(叶子节点也就是邻接表size = 1的节点),最后剩下的很少于两个节点的节点集合就是root,注意当n=1的时候,边表示法是空数组,也要返回

 1 public class Solution {
 2     public List<Integer> findMinHeightTrees(int n, int[][] edges) {
 3         if (n == 1) {
 4             List<Integer> roots = new ArrayList<>();
 5             roots.add(0);
 6             return roots;
 7         }
 8         //无向图转化为邻接表表示
 9         List<List<Integer>> graph = new ArrayList<>();
10         for (int i = 0; i < n; i++) {
11             graph.add(new ArrayList<>());
12         }
13         for (int[] edge : edges) {
14             graph.get(edge[0]).add(edge[1]);
15             graph.get(edge[1]).add(edge[0]);
16         }
17         //将叶子节点提出来
18         List<Integer> leaves = new ArrayList<>();
19         for (int i = 0; i < n; i++) {
20             if (graph.get(i).size() == 1) {
21                 leaves.add(i);
22             }
23         }
24         while (n > 2) {
25             n -= leaves.size();
26             List<Integer> nextLeaves = new ArrayList<>();
27             for (int i : leaves) {
28                 int neighbor = graph.get(i).get(0);
29                 graph.get(neighbor).remove((Integer) i);
30                 if (graph.get(neighbor).size() == 1) {
31                     nextLeaves.add(neighbor);
32                 }
33             }
34             leaves = nextLeaves;
35         }
36         return leaves;
37     }
38 }
View Code

bug-free process

1.将叶子节点一层一层删除,n==1 2016/12/21

leetcode 309. Best Time to Buy and Sell Stock with Cooldown

题意:

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
Example:

prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]
View Code

解法:

思路:

The series of problems are typical dp. The key for dp is to find the variables to represent the states and deduce the transition function.

Of course one may come up with a O(1) space solution directly, but I think it is better to be generous when you think and be greedy when you implement.

The natural states for this problem is the 3 possible transactions : buy, sell, rest. Here rest means no transaction on that day (aka cooldown).

Then the transaction sequences can end with any of these three states.

For each of them we make an array, buy[n], sell[n] and rest[n].

buy[i] means before day i what is the maxProfit for any sequence end with buy.

sell[i] means before day i what is the maxProfit for any sequence end with sell.

rest[i] means before day i what is the maxProfit for any sequence end with rest.

Then we want to deduce the transition functions for buy sell and rest. By definition we have:

buy[i]  = max(rest[i-1]-price, buy[i-1]) 
sell[i] = max(buy[i-1]+price, sell[i-1])
rest[i] = max(sell[i-1], buy[i-1], rest[i-1])
Where price is the price of day i. All of these are very straightforward. They simply represents :

(1) We have to `rest` before we `buy` and 
(2) we have to `buy` before we `sell`
One tricky point is how do you make sure you sell before you buy, since from the equations it seems that [buy, rest, buy] is entirely possible.

Well, the answer lies within the fact that buy[i] <= rest[i] which means rest[i] = max(sell[i-1], rest[i-1]). That made sure [buy, rest, buy] is never occurred.

A further observation is that and rest[i] <= sell[i] is also true therefore

rest[i] = sell[i-1]
Substitute this in to buy[i] we now have 2 functions instead of 3:

buy[i] = max(sell[i-2]-price, buy[i-1])
sell[i] = max(buy[i-1]+price, sell[i-1])
This is better than 3, but

we can do even better

Since states of day i relies only on i-1 and i-2 we can reduce the O(n) space to O(1). And here we are at our final solution:
View Code

代码:

 1 public class Solution {
 2     public int maxProfit(int[] prices) {
 3         if (prices == null || prices.length == 0) {
 4             return 0;
 5         }
 6         int sell = 0;
 7         int preSell = 0;
 8         int buy = Integer.MIN_VALUE;
 9         int preBuy = Integer.MIN_VALUE;
10         for (int price : prices) {
11             preBuy = buy;
12             buy = Math.max(preSell - price, preBuy);
13             preSell = sell;
14             sell = Math.max(preBuy + price, preSell);
15         }
16         return sell;
17     }
18 }
View Code

1.看了别人思路。2016/12/20

leetcode 122. Best Time to Buy and Sell Stock II

题意:

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
View Code

解法:将原数组转换成利润数组,当前节点的利润等于当前价格减去前一天的价格。从后往前方便计算,全部正数利润的总和就是最大利润。

 1 public class Solution {
 2     public int maxProfit(int[] prices) {
 3         if(prices == null || prices.length < 2) {
 4             return 0;
 5         }
 6         int sum = 0;        
 7         for(int i = prices.length-1; i > 0; i--){
 8             prices[i] = prices[i] - prices[i - 1];
 9             if(prices[i] > 0)
10                 sum += prices[i];              
11         }
12         return sum;        
13     }
14 }
View Code

leetcode 121. Best Time to Buy and Sell Stock

题意:

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:
Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
Example 2:
Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.
View Code

解法:将原数组转换成利润数组,当前节点的利润等于当前价格减去前一天的价格。求最大子数组和

 1 public class Solution {
 2     public int maxProfit(int[] prices) {
 3         if(prices == null || prices.length < 2) {
 4             return 0;
 5         }
 6         int ret = 0;
 7         int sum = 0;
 8         for(int i = prices.length - 1; i > 0; i--) {
 9             prices[i] = prices[i] - prices[i - 1];
10             if(sum < 0) {
11                 sum = 0;
12             }
13             sum += prices[i];
14             ret = Math.max(sum, ret);
15         }
16         return ret;        
17     }
18 }
View Code

 

leetcode 306. Additive Number

题意:

Additive number is a string whose digits can form additive sequence.

A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

For example:
"112358" is an additive number because the digits can form an additive sequence: 1, 1, 2, 3, 5, 8.

1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
"199100199" is also an additive number, the additive sequence is: 1, 99, 100, 199.
1 + 99 = 100, 99 + 100 = 199
Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Given a string containing only digits '0'-'9', write a function to determine if it's an additive number.
View Code

解法:基本思路是先肯定前两位,在日后逐步遍历看是否知足。前两位的长度是有限制的,由于要确保有第三位的存在。第一位长度i<=len/2,第二位长度j 知足max(i,j)<=len-i-j,len为字符串长度。

另外就是数据范围,小数据的话用long能够ac,follow up大数据应该用BigInteger

1.在较小的数据范围时使用long,会稍微快一点

 1 public class Solution {
 2     public boolean isAdditiveNumber(String num) {
 3         if (num == null || num.length() == 0) {
 4             return false;
 5         }
 6         int len = num.length();
 7         for (int i = 1; i <= len / 2; i++) {
 8             if (num.charAt(0) == '0' && i > 1) {
 9                 return false;
10             }
11             long first = Long.parseLong(num.substring(0, i));
12             for (int j = 1; Math.max(i, j) <= len - i - j; j++) {
13                 if (num.charAt(i) == '0' && j > 1) {
14                     break;
15                 }
16                 long second = Long.parseLong(num.substring(i, i + j));
17                 if (isValid(first, second, i + j, num)) {
18                     return true;
19                 }
20             }
21         }
22         return false;
23     }
24     public boolean isValid(long first, long second, int start, String num) {
25         if (start == num.length()) {
26             return true;
27         }
28         second = second + first;
29         first = second - first;
30         String sum = Long.toString(second);
31         return num.startsWith(sum, start) && isValid(first, second, start + sum.length(), num);
32     }
33 }
View Code

2.follow up:较大的数使用BigInteger

 1 import java.math.BigInteger;
 2 public class Solution {
 3     public boolean isAdditiveNumber(String num) {
 4         if (num == null || num.length() == 0) {
 5             return false;
 6         }
 7         int len = num.length();
 8         for (int i = 1; i <= len / 2; i++) {
 9             if (num.charAt(0) == '0' && i > 1) {
10                 return false;
11             }
12             BigInteger first = new BigInteger(num.substring(0, i));
13             for (int j = 1; Math.max(i, j) <= len - i - j; j++) {
14                 if (num.charAt(i) == '0' && j > 1) {
15                     break;
16                 }
17                 BigInteger second = new BigInteger(num.substring(i, i + j));
18                 if (isValid(first, second, i + j, num)) {
19                     return true;
20                 }
21             }
22         }
23         return false;
24     }
25     public boolean isValid(BigInteger first, BigInteger second, int start, String num) {
26         if (start == num.length()) {
27             return true;
28         }
29         second = second.add(first);
30         first = second.subtract(first);
31         String sum = second.toString();
32         return num.startsWith(sum, start) && isValid(first, second, start + sum.length(), num);
33     }
34 }
View Code

 

 

leetcode 307. Range Sum Query - Mutable

题意:

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.
Example:
Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
Note:
The array is only modifiable by the update function.
You may assume the number of calls to update and sumRange function is distributed evenly.
View Code

解法:最优解法是用Binary Indexed Trees(BIT)。可参考http://www.cnblogs.com/xudong-bupt/p/3484080.html

时间复杂度从O(m*n)降到了O(m*logn).m是调用次数,n为数组长度。

 1 public class NumArray {
 2     int[] sum = null;
 3     int[] nums = null;
 4     public NumArray(int[] nums) {
 5         if (nums == null || nums.length == 0) {
 6             return;
 7         }
 8         int len = nums.length;
 9         this.nums = nums;
10         sum = new int[len + 1];
11         for (int i = 1; i <= len; i++) {
12             sum[i] = nums[i - 1];
13         }
14         for (int i = 1; i <= len; i++) {
15             int pa = i + (((i - 1) ^ i) & i);
16             if (pa <= len) {
17                 sum[pa] += sum[i];
18             }
19         }
20     }
21 
22     void update(int i, int val) {
23         int diff = val - nums[i];
24         nums[i] = val;
25         int n = i + 1;
26         int len = sum.length;
27         while (n < len) {
28             sum[n] += diff;
29             n += (((n - 1) ^ n) & n);
30         }
31     }
32     public int getSum(int end) {
33         int endSum = 0;
34         while (end > 0) {
35             endSum += sum[end];
36             end -= ((end - 1) ^ end) & end;
37         }
38         return endSum;
39     }
40     public int sumRange(int i, int j) {
41         return getSum(j + 1) - getSum(i);
42     }
43 }
44 
45 
46 // Your NumArray object will be instantiated and called as such:
47 // NumArray numArray = new NumArray(nums);
48 // numArray.sumRange(0, 1);
49 // numArray.update(1, 10);
50 // numArray.sumRange(1, 2);
View Code

bug-free process:

1.看了BIT的解法,本身实现了一遍,遇到一个小问题就是位运算符与加号优先级,位运算符优先级较低,先运算要加括号。2016/12/18

leetcode 304. Range Sum Query 2D - Immutable

题意:

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Range Sum Query 2D
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:
Given matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
Note:
You may assume that the matrix does not change.
There are many calls to sumRegion function.
You may assume that row1 ≤ row2 and col1 ≤ col2.
View Code

解法:dp。利用dp[i][j]表示以(i - 1, j - 1)位右下角,以(0,0)位左上角的矩形的sum

 1 public class NumMatrix {
 2     int[][] dp = null;
 3     public NumMatrix(int[][] matrix) {
 4         if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
 5             return;
 6         }
 7         int m = matrix.length;
 8         int n = matrix[0].length;
 9         //dp[i][j]表示以(i - 1, j - 1)位右下角,以(0,0)位左上角的矩形的sum
10         dp = new int[m + 1][n + 1];
11         for (int i = 1; i <= m; i++) {
12             for (int j = 1; j <= n; j++) {
13                 dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + matrix[i - 1][j - 1];
14             }
15         }
16     }
17 
18     public int sumRegion(int row1, int col1, int row2, int col2) {
19         if(dp == null || dp.length == 0 || dp[0].length == 0) {
20             return 0;
21         }
22         return dp[row2 + 1][col2 + 1] - dp[row2 + 1][col1] - dp[row1][col2 + 1] + dp[row1][col1];
23     }
24 }
25 
26 
27 // Your NumMatrix object will be instantiated and called as such:
28 // NumMatrix numMatrix = new NumMatrix(matrix);
29 // numMatrix.sumRegion(0, 1, 2, 3);
30 // numMatrix.sumRegion(1, 2, 3, 4);
View Code

bug-free process

1.很简单的dp都没有想出来。 2016/12/16

leetcode 284. Peeking Iterator

题意:

Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation -- it essentially peek() at the element that will be returned by the next call to next().

Here is an example. Assume that the iterator is initialized to the beginning of the list: [1, 2, 3].

Call next() gets you 1, the first element in the list.

Now you call peek() and it returns 2, the next element. Calling next() after that still return 2.

You call next() the final time and it returns 3, the last element. Calling hasNext() after that should return false.

Hint:

Think of "looking ahead". You want to cache the next element.
Is one variable sufficient? Why or why not?
Test your design with call order of peek() before next() vs next() before peek().
For a clean implementation, check out Google's guava library source code.
Follow up: How would you extend your design to be generic and work with all types, not just integer?
View Code

解法:用一个全局变量来记录上一个当前的头元素便可

 1 // Java Iterator interface reference:
 2 // https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html
 3 class PeekingIterator implements Iterator<Integer> {
 4     Integer headElement = null;
 5     Iterator<Integer> iterator = null;
 6     public PeekingIterator(Iterator<Integer> iterator) {
 7         // initialize any member here.
 8         this.iterator = iterator;
 9     }
10 
11     // Returns the next element in the iteration without advancing the iterator.
12     public Integer peek() {
13         if (headElement == null) {
14             headElement = this.iterator.next();
15         }
16         return headElement;
17     }
18 
19     // hasNext() and next() should behave the same as in the Iterator interface.
20     // Override them if needed.
21     @Override
22     public Integer next() {
23         if (headElement != null) {
24             Integer temp = headElement;
25             headElement = null;
26             return temp;
27         }
28         return this.iterator.next();
29     }
30 
31     @Override
32     public boolean hasNext() {
33         if (headElement != null) {
34             return true;
35         }
36         return this.iterator.hasNext();
37     }
38 }
View Code

bug-free process

1.参考了Google's guava library source code,这个其实就是follow up的代码。2016/12/16

leetcode 279. Perfect Squares

题意:

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
View Code

解法:dp。某个数n 确定等于 n-j*j 加上一个彻底平方数 j*j,也就是说count[n] = count[n - j*j] + 1,遍历全部可能的j,取最小的count就行了。

 1 public class Solution {
 2     public int numSquares(int n) {
 3         int sqrt = (int) Math.sqrt(n);
 4         if (sqrt * sqrt == n) {
 5             return 1;
 6         }
 7         int[] count = new int[n + 1];
 8         count[0] = 0;
 9         for (int i = 1; i <= n; i++) {
10             count[i] = Integer.MAX_VALUE;
11         }
12         // For each i, it must be the sum of some number (i - j*j) and 
13         // a perfect square number (j*j).
14         for (int i = 1; i <= n; i++) {
15             for (int j = 1; j * j <= i; j++) {
16                 count[i] = Math.min(count[i], count[i - j * j] + 1);
17             }
18         }
19         return count[n];
20     }
21 }
View Code

bug-free process

1.dp解法没想出来。2016/12/15

leetcode 275. H-Index II

题意:

Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?

Hint:

Expected runtime complexity is in O(log n) and the input is sorted.
View Code

解法:二分法,找最前的知足citations[mid] >= (len - mid)的

 1 public class Solution {
 2     public int hIndex(int[] citations) {
 3         if (citations == null || citations.length == 0) {
 4             return 0;
 5         }
 6         int len = citations.length;
 7         int max = 0;
 8         int start = 0;
 9         int end = len - 1;
10         while (start <= end) {
11             int mid = start + (end - start) / 2;
12             if (citations[mid] >= (len - mid)) {
13                 max = len - mid;
14                 end = mid - 1;
15             } else {
16                 start = mid + 1;
17             }
18         }
19         return max;        
20     }
21 }
View Code

bug-free process

1.有了上一题经验,这一题就bug-free了。2016/12/15

leetcode 274. H-Index

题意:

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.

According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."

For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.

Note: If there are several possible values for h, the maximum one is taken as the h-index.

Hint:

An easy approach is to sort the array first.
What are the possible values of h-index?
A faster approach is to use extra space.
View Code

解法:hashtable

 1 public class Solution {
 2     public int hIndex(int[] citations) {
 3         if (citations == null || citations.length == 0) {
 4             return 0;
 5         }
 6         int len = citations.length;
 7         int[] count = new int[len + 1];
 8         for (int i = 0; i < len; i++) {
 9             if (citations[i] >= len) {
10                 count[len]++;
11             } else {
12                 count[citations[i]]++;
13             }
14         }
15         int h = 0;
16         for (int i = len; i >= 0; i--) {
17             h += count[i];
18             if (h >= i) {
19                 return i;
20             }
21         }
22         return 0;
23     }
24 }
View Code

bug-free process

1.没有想到hash表的解法,只想到了先排序,再从后往前找的办法。2016/12/15

263. Ugly Number

题意:

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.

Note that 1 is typically treated as an ugly number.
View Code

解法:

Just divide by 2, 3 and 5 as often as possible and then check whether we arrived at 1. Also try divisor 4 if that makes the code simpler / less repetitive.

 1 public class Solution {
 2     public boolean isUgly(int num) {
 3         if(num < 1)
 4             return false;
 5         for (int i = 2; i < 6 && num > 0; i++) {
 6             while (num % i == 0) {
 7                 num /= i;
 8             }
 9         }
10         return 1 == num;
11     }
12 }
View Code

换一种写法:

1 public class Solution {
2     public boolean isUgly(int num) {
3         while(num >= 2 && 0 == num % 2) num /= 2;
4         while(num >= 3 && 0 == num % 3) num /= 3;
5         while(num >= 5 && 0 == num % 5) num /= 5;
6         return 1 == num;
7     }
8 }
View Code

bug-free process:

1.记住这个解法。2016/12/14

leetcode 264. Ugly Number II

题意:

 1 Write a program to find the n-th ugly number.
 2 
 3 Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
 4 
 5 Note that 1 is typically treated as an ugly number.
 6 
 7 Hint:
 8 
 9 The naive approach is to call isUgly for every number until you reach the nth one. Most numbers are not ugly. Try to focus your effort on generating only the ugly ones.
10 An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.
11 The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L1, L2, and L3.
12 Assume you have Uk, the kth ugly number. Then Uk+1 must be Min(L1 * 2, L2 * 3, L3 * 5).
View Code

解法:

 1 public class Solution {
 2     public int nthUglyNumber(int n) {
 3         int[] ugly = new int[n];
 4         ugly[0] = 1;
 5         int factors2 = 2;
 6         int factors3 = 3;
 7         int factors5 = 5;
 8         int index2 = 0;
 9         int index3 = 0;
10         int index5 = 0;
11         for (int i = 1; i < n; i++) {
12             ugly[i] = Math.min(Math.min(factors2, factors3), factors5);
13             if (ugly[i] == factors2) {
14                 factors2 = 2 * ugly[++index2];
15             }
16             if (ugly[i] == factors3) {
17                 factors3 = 3 * ugly[++index3];
18             }
19             if (ugly[i] == factors5) {
20                 factors5 = 5 * ugly[++index5];
21             }
22         }
23         return ugly[n - 1];
24     }
25 }
View Code

bug-free process :

1.第二次作,找到了最优解法。2016/12/14

313. Super Ugly Number

题意:

Write a program to find the nth super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.

Note:
(1) 1 is a super ugly number for any given primes.
(2) The given numbers in primes are in ascending order.
(3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.
View Code

解法:将leetcode 264. Ugly Number II的解法通用化。时间复杂度O(n*k)

 1 public class Solution {
 2     public int nthSuperUglyNumber(int n, int[] primes) {
 3         int k = primes.length;
 4         int[] index = new int[k];
 5         int[] ugly = new int[n];
 6         ugly[0] = 1;
 7         for (int i = 1; i < n; i++) {
 8             ugly[i] = Integer.MAX_VALUE;
 9             for (int j = 0; j < k; j++) {
10                 ugly[i] = Math.min(ugly[i], primes[j] * ugly[index[j]]);
11             }
12             for (int j = 0; j < k; j++) {
13                 if (ugly[i] == primes[j] * ugly[index[j]]) {
14                     index[j]++;
15                 }
16             }
17         }
18         return ugly[n - 1];
19     }
20 }
View Code

bug-free process

1.用PriorityQueue TLE,将leetcode264的代码通用化。2016/12/21

leetcode 241. Different Ways to Add Parentheses

题意:

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.


Example 1
Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2
Output: [0, 2]


Example 2
Input: "2*3-4*5"

(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
Output: [-34, -14, -10, -10, 10]
View Code

解法:Divide & Conquer。与95. Unique Binary Search Trees II相似的作法。不过将表达式预处理了一下,将数字与运算符加入到了list里面,方便后面的提取

 1 public class Solution {
 2     public List<Integer> diffWaysToCompute(String input) {
 3         if (input == null || input.length() == 0) {
 4             return new ArrayList<Integer>();
 5         }
 6         List<String> express = new ArrayList<>();
 7         for (int i = 0; i < input.length(); i++) {
 8             int j = i;
 9             while (j != input.length() && Character.isDigit(input.charAt(j))) {
10                 j++;
11             }
12             String num = input.substring(i, j);
13             if (!num.isEmpty()) {
14                 express.add(num);
15                 i = j - 1;
16             } else {
17                 express.add(input.substring(i, i + 1));
18             }
19         }
20         return compute(express, 0, express.size() - 1);
21     }
22     public List<Integer> compute(List<String> express, int start, int end) {
23         List<Integer> ans = new ArrayList<>();
24         if (start == end) {
25             ans.add(Integer.valueOf(express.get(start)));
26             return ans;
27         }
28         for (int i = start + 1; i < end; i += 2) {
29             String op = express.get(i);
30             List<Integer> left = compute(express, start, i - 1);
31             List<Integer> right = compute(express, i + 1, end);
32             for (int a : left) {
33                 for (int b : right) {
34                     int c = 0;
35                     if (op.equals("+")) {
36                         c = a + b;
37                     } else if (op.equals("-")) {
38                         c = a - b;
39                     } else {
40                         c = a * b;
41                     }
42                     ans.add(c);
43                 }
44             }
45         }
46         return ans;
47     }
48 }
View Code

bug-free process

1.分治法没作出来。注意预处理,注意与其类似的一道题。2016/12/14

leetcode 74. Search a 2D Matrix

题意:

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
Given target = 3, return true.
View Code

解法:二分法。把整个矩阵当作一维的排序数组,二分查找。row = mid/n;col = mid %n;n为列数,mid为当作数组以后的索引

 1 public class Solution {
 2     public boolean searchMatrix(int[][] matrix, int target) {
 3         if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
 4             return false;
 5         }
 6         int m = matrix.length;
 7         int n = matrix[0].length;   
 8         int start = 0;
 9         int end = m * n - 1;
10         while (start <= end) {
11             int mid = start + (end - start) / 2;
12             int row = mid / n;
13             int col = mid % n;
14             if (matrix[row][col] == target) {
15                 return true;
16             }
17             if (matrix[row][col] < target) {
18                 start = mid + 1;
19             } else {
20                 end = mid - 1;
21             }
22         }
23         return false;
24     }
25 }
View Code

bug-free process

1.第二次作。bug-free。2016/12/14

leetcode 240. Search a 2D Matrix II

题意:

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.
For example,

Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
Given target = 5, return true.

Given target = 20, return false.
View Code

解法一:二分法分两步,O(m*n)

1.二分法找到最后可能出现的行,每一行的最左侧元素matrix[mid][0]与target做比较

  a.matrix[mid][0]== target,返回true

  b.matrix[mid][0]< target,记录此行为最后一行,并从下一行开始继续查找

  c.matrix[mid][0]> target,从前一行继续查找

2.遍历全部可能出现的行,逐行二分查找

 1 public class Solution {
 2     public boolean searchMatrix(int[][] matrix, int target) {
 3         if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
 4             return false;
 5         }
 6         int m = matrix.length;
 7         int n = matrix[0].length;
 8         int start = 0;
 9         int end = m - 1;
10         int index = 0;
11         //二分法找到最后可能出现的行,每一行的最左侧元素与target做比较
12         while (start <= end) {
13             int mid = start + (end - start) / 2;
14             if (matrix[mid][0] == target) {
15                 return true;
16             }
17             if (matrix[mid][0] < target) {
18                 index = mid;
19                 start = mid + 1;
20             } else {
21                 end = mid - 1;
22             }
23         }
24         //遍历全部可能出现的行,逐行二分查找
25         for (int i = 0; i <= index; i++) {
26             start = 0;
27             end = n - 1;
28             while (start <= end) {
29                 int mid = start + (end - start) / 2;
30                 if (matrix[i][mid] == target) {
31                     return true;
32                 }
33                 if (matrix[i][mid] < target) {
34                     start = mid + 1;
35                 } else {
36                     end = mid - 1;
37                 }
38             }
39         }
40         return false;
41     }
42 }
View Code

解法二:O(m+n),非二分法

1.首先选取右上角的数字做为当前数字,当前行为零,当前列为最后一列。

2.若是target等于当前数字,则返回true,若是target大于当前数字,则不可能在这一行,行数加一;若是target小于当前数字,则不可能在这一列,列数减一

代码:

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int row = 0;
        int col = matrix[0].length - 1;
        while (row <= matrix.length - 1 && col >= 0) {
            if (target == matrix[row][col]) {
                return true;
            } else if (target < matrix[row][col]) {
                col--;
            } else {
                row++;
            }
        }
        return false;
    }
}

bug-free process

1.第二次作了。bug-free。 2016/12/14

2.第三次,找到最优解法 2017/01/31

leetcode 230. Kth Smallest Element in a BST

题意:

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note: 
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

Hint:

Try to utilize the property of a BST.
What if you could modify the BST node's structure?
The optimal runtime complexity is O(height of BST).
View Code

解法:

1.非递归的中序遍历,返回第k个节点的值。

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public int kthSmallest(TreeNode root, int k) {
12         int count = 0;
13         Stack<TreeNode> s = new Stack<>();
14         s.push(root);
15         while (!s.isEmpty()) {
16             while (root != null && root.left != null) {
17                 root = root.left;
18                 s.push(root);
19             }
20             TreeNode cur = s.pop();
21             count++;
22             if (count == k) {
23                 return cur.val;
24             }
25             if (cur.right != null) {
26                 root = cur.right;
27                 s.push(root);
28             }
29         }
30         return 0;
31     }
32 }
View Code

2.二分法。与quickselect原理类似的。

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public int kthSmallest(TreeNode root, int k) {
12         int leftCount = countNodes(root.left);
13         if (leftCount < k - 1) {
14             return kthSmallest(root.right, k - leftCount - 1);
15         } else if (leftCount > k - 1) {
16             return kthSmallest(root.left, k);
17         } else {
18             return root.val;
19         }
20     }
21     public int countNodes(TreeNode root) {
22         if (root == null) {
23             return 0;
24         }
25         return 1 + countNodes(root.left) + countNodes(root.right);
26     }
27 }
View Code

bug-free process

1.非递归的解法作出来的,二分法比较好。2016/12/14

leetcode 236. Lowest Common Ancestor of a Binary Tree--微软面试题

题意:找两个树节点的最近公共祖先

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4
For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
View Code

解法:分治法。找到公共祖先则返回,只找到A,则返回A;只找到B,则返回B,找不到返回null

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
12         if (root == null) {
13             return root;
14         }
15         if (root == p || root == q) {
16             return root;
17         }
18         TreeNode left = lowestCommonAncestor(root.left, p, q);
19         TreeNode right = lowestCommonAncestor(root.right, p, q);
20         if (left != null & right != null) {
21             return root;
22         }
23         if (left != null) {
24             return left;
25         }
26         if (right != null) {
27             return right;
28         }
29         return null;
30     }
31 }
View Code

bug-free process:

1.第三次作,可是没记住最好的解法。2016/12/14

leetcode 229. Majority Element II

题意:

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

Hint:

How many majority elements could it possibly have?
Do you have a better hint? Suggest it!
View Code

解法:多数投票算法https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm的扩展。

这题没有说明答案必定是有的,因此后面要花费O(n)的时间去验证结果的正确去否。leetcode 169. Majority Element这一题就不用验证了。

 1 public class Solution {
 2     public List<Integer> majorityElement(int[] nums) {
 3         if (nums == null || nums.length == 0) {
 4             return new ArrayList<Integer>();
 5         }
 6         int len = nums.length;
 7         int majorA = 0;
 8         int majorB = 0;
 9         int countA = 0;
10         int countB = 0;
11         for (int i = 0; i < len; i++) {
12             if (nums[i] == majorA) {
13                 countA++;
14             } else if (nums[i] == majorB) {
15                 countB++;
16             } else if (countA == 0) {
17                 majorA = nums[i];
18                 countA++;
19             } else if (countB == 0) {
20                 majorB = nums[i];
21                 countB++;
22             } else {
23                 countA--;
24                 countB--;
25             }
26         }
27         //verify
28         countA = 0;
29         countB = 0;
30         for (int i = 0; i < len; i++) {
31             if (nums[i] == majorA) {
32                 countA++;
33             } else if (nums[i] == majorB) {
34                 countB++;
35             }
36         }
37         List<Integer> ans = new ArrayList<>();
38         if (countA > len / 3) {
39             ans.add(majorA);
40         }
41         if (countB > len / 3) {
42             ans.add(majorB);
43         }
44         return ans;
45     }
46 }
View Code

解题过程:

1.记住这个算法。2016/12/13

leetcode 169. Majority Element

题意:

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

解法:

多数投票算法https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm

 1 public class Solution {
 2     public int majorityElement(int[] nums) {
 3         int major = nums[0];
 4         int count = 0;
 5         for(int i = 0; i < nums.length; i++) {        
 6             if (count == 0) {
 7                 major = nums[i];
 8                 count++;
 9             } else if (major == nums[i]) {
10                 count++;
11             } else {
12                 count--;
13             }
14         }
15         return major; 
16     }
17 }
View Code

解题过程:

2.第二次看,彻底忘了。2016/12/13

leetcode 227. Basic Calculator II

题意:

 1 Implement a basic calculator to evaluate a simple expression string.
 2 
 3 The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.
 4 
 5 You may assume that the given expression is always valid.
 6 
 7 Some examples:
 8 "3+2*2" = 7
 9 " 3/2 " = 1
10 " 3+5 / 2 " = 5
11 Note: Do not use the eval built-in library function.
View Code

解法:1.两个栈,一个栈operators存储运算符,另外一个nums存储数字。遇到数字时,入nums,遇到运算符时,判断是乘除仍是加减。

  a.如果乘除,则看栈顶是否也有乘除,若是有则计算,没有则将当前符号入栈

  b.如果加减,则将栈中全部运算符计算完。

表达式的最后一位必定是数字,不能忘记入栈。便利完以后栈中可能还有未计算的部分,直接while循环出栈计算完。

 1 public class Solution {
 2     public int calculate(String s) {
 3         if (s == null || s.length() == 0) {
 4             return 0;
 5         }
 6         Stack<Integer> nums = new Stack<>();
 7         Stack<Character> operators = new Stack<>();
 8         int number = 0;
 9         for (int i = 0; i < s.length(); i++) {
10             if (s.charAt(i) == ' ') {
11                 continue;
12             }
13             if (Character.isDigit(s.charAt(i))) {
14                 number = number * 10 + s.charAt(i) - '0';
15             } else {
16                 nums.push(number);
17                 number = 0;
18                 if ((s.charAt(i) == '*' || s.charAt(i) == '/')) {
19                     if (!operators.isEmpty() && ((operators.peek() == '*') || (operators.peek() == '/'))) {
20                         char op = operators.pop();
21                         int a = nums.pop();
22                         int b = nums.pop();
23                         int c = 0;
24                         if (op == '*') {
25                             c = a * b;
26                         } else {
27                             c = b / a;
28                         }
29                         nums.push(c);
30                     }
31                 } else {
32                     while (!operators.isEmpty()) {
33                         char op = operators.pop();
34                         int a = nums.pop();
35                         int b = nums.pop();
36                         int c = 0;
37                         if (op == '+') {
38                             c = a + b;
39                         } else if (op == '-') {
40                             c = b - a;
41                         } else if (op == '*') {
42                             c = a * b;
43                         } else {
44                             c = b / a;
45                         }
46                         nums.push(c);
47                     }
48                 } 
49                 operators.push(s.charAt(i));
50             }
51         }
52         nums.push(number);
53         while (!operators.isEmpty()) {
54             char op = operators.pop();
55             int a = nums.pop();
56             int b = nums.pop();
57             int c = 0;
58             if (op == '+') {
59                 c = a + b;
60             } else if (op == '-') {
61                 c = b - a;
62             } else if (op == '*') {
63                 c = a * b;
64             } else {
65                 c = b / a;
66             }
67             nums.push(c);            
68         }
69         return nums.pop();
70     }
71 }
View Code

2.优化的解法。一个栈,只存数字。

 1 public class Solution {
 2     public int calculate(String s) {
 3         if (s == null || s.length() == 0) {
 4             return 0;
 5         }
 6         Stack<Integer> nums = new Stack<>();
 7         int number = 0;
 8         char op = '+';
 9         for (int i = 0; i < s.length(); i++) {
10             if (Character.isDigit(s.charAt(i))) {
11                 number = number * 10 + s.charAt(i) - '0';
12             } 
13             if (!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' ' || i == s.length() - 1){
14                 if (op == '+') {
15                     nums.push(number);
16                 } else if (op == '-'){
17                     nums.push(-number);
18                 } else if (op == '*') {
19                     nums.push(nums.pop() * number);
20                 } else {
21                     nums.push(nums.pop() / number);
22                 }
23                 op = s.charAt(i);
24                 number = 0;
25             }
26         }
27         int res = 0;
28         while (!nums.isEmpty()) { 
29             res += nums.pop();
30         }
31         return res;
32     }
33 }
View Code

解题过程:

1.当遇到乘除符号的时候怎么计算,还有表达式的最后一位数字别忘了。2016/12/13

leetcode 60 Permutation Sequence

题意:

 1 The set [1,2,3,…,n] contains a total of n! unique permutations.
 2 
 3 By listing and labeling all of the permutations in order,
 4 We get the following sequence (ie, for n = 3):
 5 
 6 "123"
 7 "132"
 8 "213"
 9 "231"
10 "312"
11 "321"
12 Given n and k, return the kth permutation sequence.
13 
14 Note: Given n will be between 1 and 9 inclusive.
View Code

解析:

在n!个排列中,第一位的元素老是(n-1)!一组出现的,也就说若是p = k / (n-1)!,那么排列的最开始一个元素必定是nums[p]。k 从0开始。

接下来就是第二个元素,也就是(n-1)!的排列,元素老是以(n-2)!一组出现的。令k=k%(n-1)!,p=k/(n-2)!,那么第二个元素就是去掉了第一个元素的新nums数组的nums[p]
**更新nums的方法是每加入一个元素则从nums中删除掉**(怎么去判断第二位以后的元素,这一步很重要,有了这样的更新就能够想通了,前提nums的删除操做比较简便)
若是nums是一个数组的话,更新起来就比较麻烦了,因此就不更新了,而是加一个visited数组来判断某个数字是否被用过,而后每次遍历数组找到第p+1个没被用过的数字

以此类推,获得第k-1个排列的排列。(由于这里k从0开始,题目中k从1开始)
View Code

代码:

 1 public class Solution {
 2     public String getPermutation(int n, int k) {
 3         if (n == 0) {
 4             return null;
 5         }
 6         
 7         int product = 1;
 8         for (int i = 1; i < n; i++) {
 9             product *= i;
10         }
11         StringBuilder ans = new StringBuilder("");
12         k = k - 1;
13         boolean[] visited = new boolean[n];
14         
15         for (int i = 0; i < n; i++) {
16             int p = k / product;
17             k = k % product;
18             int index = 0;
19             for (int j = 0; j < n; j++) {
20                 if (p == index && !visited[j]) {
21                     ans.append((char)('0' + j + 1));
22                     visited[j] = true;
23                     break;
24                 } else if (!visited[j]){
25                     index++;
26                 }
27             }
28             if (i != n - 1) {
29                 product /= n - i - 1;
30             }
31         }
32         
33         return ans.toString();
34     }
35 }
View Code

1.一种更简便的方法 11/5

2.不使用list的作法 11/16

3.bug-free 11/27

lintcode Sqrt(x) II求实数的平方根--搜狐面试题

题意:求double类型的平方根,返回值也是double类型的。

解法:

1.仍是二分法,要注意的是double类型在比较是否相等的时候是有一个精确度的。下面的解法是九章算法提供的,可是我以为仍是没有解决溢出的问题,当mid*mid的时候多是会溢出的。

 1 public class Solution {
 2     /**
 3      * @param x a double
 4      * @return the square root of x
 5      */
 6     public double sqrt(double x) {
 7         // Write your code here
 8         double start = 0;
 9         double end = x;
10         if (x <= 1) {
11             end = 1;
12         }
13         double eps = 1e-12;
14         while (end - start > eps) {
15             double mid = start + (end -start) / 2;
16             if (mid * mid < x) {
17                 start = mid;
18             } else {
19                 end = mid;
20             }
21         }
22         return start;
23     }
24 }
View Code

2.牛顿法,,能够参考这个https://www.zhihu.com/question/20690553

 1 public class Solution {
 2     /**
 3      * @param x a double
 4      * @return the square root of x
 5      */
 6     public double sqrt(double x) {
 7         // Write your code here
 8         double res = 1.0;
 9         double eps = 1e-12;
10 
11         while(Math.abs(res * res - x) > eps) {
12             res = (res + x / res) / 2;
13         }
14 
15         return res;
16     }
17 }
View Code

 

leetcode 69 Sqrt(x)

题意:

Implement int sqrt(int x).

Compute and return the square root of x.
View Code

解法:先利用倍增法找到左边界,和右边界。再利用二分法,注意的是数据类型的转换

 1 public class Solution {
 2     public int mySqrt(int x) {
 3         if (x < 2) {
 4             return x;
 5         }
 6         long a = (long) x;
 7         long start = 1;
 8         while (start * start < a) {
 9             start *= 2;
10         }
11         long end = start;
12         start /= 2;
13         int ans = 0;
14         while (start <= end) {
15             long mid = start + (end - start) / 2;
16             if (mid * mid == a) {
17                 return (int) mid;
18             }
19             if (mid * mid < a) {
20                 ans = (int) mid;
21                 start = mid + 1;
22             } else {
23                 end = mid - 1;
24             }
25         }
26         return ans;
27     }
28 }
View Code

1.左右边界的肯定及数据类型的选择 11/6

2.左右边界的肯定及数据类型的选择 11/16

3.bug-free 2016/12/06

leetcode 89 Gray Code

题意:

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2
Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.
View Code

解法:

gray code中文名叫格雷码
最初的解法是直接用深度搜索再加上去重,这样的话无疑有不少的重复计算,致使算法复杂度太大
第二次改进是在23行加上了break,稍微快了一些

后来在网上查找了更简便的方法,写几个例子出来找规律。
以3位格雷码为例。
0 0 0
0 0 1
0 1 1
0 1 0
1 1 0
1 1 1
1 0 1
1 0 0
能够看到第n位的格雷码由两部分构成,一部分是n-1位格雷码,再加上 1<<(n-1)和n-1位格雷码的逆序的和。

 1 public class Solution {
 2     public List<Integer> grayCode(int n) {
 3         List<Integer> codes = new ArrayList<>();
 4         if (n <= 1) {
 5             for (int i = 0; i <= n; i++) {
 6                 codes.add(i);
 7             }
 8             
 9             return codes;
10         }
11         
12         List<Integer> preCodes = grayCode(n - 1);
13         codes.addAll(preCodes);
14         for (int i = preCodes.size() - 1; i >= 0; i--) {
15             codes.add((1 << (n - 1)) | preCodes.get(i));
16         }
17         
18         return codes;
19     }
20 }
View Code

1.总结格雷码(graycode)的规律 11/13

2.bug-free 11/19

leetcode 91 Decode Ways

题意:

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.
View Code

解法:dp。可使用常数量空间

 1 public class Solution {
 2     public int numDecodings(String s) {
 3         if (s == null || s.length() == 0) {
 4             return 0;
 5         }
 6         int len = s.length();
 7         int[] dp = new int[3];
 8         dp[0] = 1;
 9         for (int i = 1; i <= len; i++) {
10             if (s.charAt(i - 1) == '0') {
11                 if (i != 1 && s.charAt(i - 2) > '0' && s.charAt(i - 2) < '3') {
12                     dp[i % 3] = dp[(i - 2) % 3];
13                 } else {
14                     return 0;
15                 }
16             } else {
17                 dp[i % 3] = dp[(i - 1) % 3];
18                 if (i != 1 && (s.charAt(i - 2) == '1' || (s.charAt(i - 2) == '2' && s.charAt(i - 1) < '7'))) {
19                     dp[i % 3] += dp[(i - 2) % 3];
20                 }
21             }
22         }
23         return dp[len % 3];
24     }
25 }
View Code

bug-free process:

1.数字字符串中包含0的时候怎么处理 11/17

2.粗心 在数值范围 bug 2016/11/30

3.bug-free ,改写成了常数空间的dp 2016/12/18

leetcode 93 Restore IP Addresses

题意:

1 Given a string containing only digits, restore it by returning all possible valid IP address combinations.
2 
3 For example:
4 Given "25525511135",
5 
6 return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
View Code

解法:backtracking 回溯法.每一个点有三个位置可插入

 1 public class Solution {
 2     public List<String> restoreIpAddresses(String s) {
 3         if (s == null || s.length() < 4) {
 4             return new ArrayList<String>();
 5         }
 6         List<String> ans = new ArrayList<String>();
 7         StringBuilder ip = new StringBuilder(s);
 8         helper(s, ans, 0, ip);
 9         return ans;
10     }
11     public void helper(String s, List<String> ans, int index, StringBuilder ip) {
12         if (ip.length() == s.length() + 3) {
13             ans.add(new String(ip));
14             return;
15         }
16         for (int i = index; i < index + 3; i++) {
17             //点以前的状况
18             if (Integer.valueOf(ip.substring(index, i + 1)) > 255) {
19                 return;
20             }
21             if (i != index && ip.charAt(index) == '0') {
22                 return;
23             }
24             if (i + 1 == ip.length()) {
25                 return;
26             }
27             //已经插入了两个点了,第三个点要考虑点以后的状况
28             if (ip.length() == s.length() + 2) {
29                 
30                 //第三个点以后的长度大于3
31                 if (ip.length() - 1 - i > 3) {
32                     continue;
33                 }
34                 if (Integer.valueOf(ip.substring(i + 1, ip.length())) > 255) {
35                     continue;
36                 }
37                 //第三个点以后的紧着是0,而且后面不止一位
38                 if (ip.length() - 1 - i > 1 && ip.charAt(i + 1) == '0') {
39                     continue;
40                 }
41             }
42             ip.insert(i + 1, '.');
43             helper(s, ans, i + 2, ip);
44             ip.deleteCharAt(i + 1);
45         }
46     }
47 }
View Code

1.每一个点有三个位置可插入,在最后一个点,要考虑不少种状况 11/17

2.忘了考虑  点插入位置在末尾的状况 2016/12/06

leetcode 96 Unique Binary Search Trees

题意:

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3
View Code

解法:动态规划。对于有n个节点的状况,能够用1~n分别做为根节点,当以i为根节点时,左子树是1~i-1,右子树是i+1~n,yii为根节点的bst的数量是左子树的数量乘以右子树的数量

   有dp[i] += dp[j] * dp[i - 1 - j] (1<=j<=i)

 1 public class Solution {
 2     public int numTrees(int n) {
 3         if (n <= 0) {
 4             return 0;
 5         }
 6         int[] dp = new int[n + 1];
 7         dp[0] = 1;
 8         for (int i = 1; i <= n; i++) {
 9             for (int j = 0; j < i; j++) {
10                 dp[i] += dp[j] * dp[i - 1 - j]; 
11             }
12         }
13         return dp[n];
14     }
15 }
View Code

1.动态规划的思路 11/18

2.bug-free 2016/12/06

leetcode 95  Unique Binary Search Trees II

 题意:

Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3
View Code

解法:分治法 对于 start~end 的根节点,求出其全部的左右子树,再以当前根节点组合左右子树。start > end 的时候返回加入了null的链表,不能返回null。

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public List<TreeNode> generateTrees(int n) {
12         if (n < 1) {
13             return new ArrayList<TreeNode>();
14         }
15         return helper(1, n);
16     }
17     public List<TreeNode> helper(int start, int end) {
18         List<TreeNode> bsts = new ArrayList<>();
19         if (start > end) {
20             bsts.add(null);
21             return bsts;
22         }
23         for (int i = start; i <= end; i++) {
24             List<TreeNode> left = helper(start, i - 1);
25             List<TreeNode> right = helper(i + 1, end);
26             for (TreeNode l : left) {
27                 for (TreeNode r : right) {
28                     TreeNode root = new TreeNode(i);
29                     root.left = l;
30                     root.right = r;
31                     bsts.add(root);
32                 }
33             }
34         }
35         return bsts;
36     }
37 }
View Code

1.分治法递归思路 11/19

2.仍是没想起来怎么作 ,注意边界条件的返回值 2016/12/06

leetcode 98 Validate Binary Search Tree

解法一:中序遍历递归。注意当所给树为空的时候返回true

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     boolean first = false;
12     int last = Integer.MIN_VALUE;
13     public boolean isValidBST(TreeNode root) {
14         if (root == null) {
15             return true;
16         }
17         if (!isValidBST(root.left)) {
18             return false;
19         }
20         if (!first) {
21             first = true; 
22         } else if (root.val <= last) {
23             return false;
24         }
25         last = root.val;
26         return isValidBST(root.right);  
27     }
28 }
View Code

解法二:中序遍历非递归

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     boolean first = false;
12     int last = Integer.MIN_VALUE;
13     public boolean isValidBST(TreeNode root) {
14         if (root == null) {
15             return true;
16         }
17         Stack<TreeNode> s = new Stack<>();
18         s.push(root);
19         while (!s.isEmpty()) {
20             while (root != null && root.left != null) {
21                 s.push(root.left);
22                 root = root.left;
23             }
24             TreeNode cur = s.pop();
25             if (!first) {
26                 first = true;
27             } else if (cur.val <= last) {
28                 return false;
29             }
30             last = cur.val;
31             if (cur.right != null) {
32                 root = cur.right;
33                 s.push(root);
34             }
35         }
36         return true;
37     }
38 }
View Code

1.非递归的时候最后一步右节点不为空的时候怎么处理 11/19

2.递归与非递归 bug-free 2016/12/06

leetcode 109 Convert Sorted List to Binary Search Tree

题意:

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
View Code

解法:利用中序遍从来构建。

  helper(n)是构建节点数为n的bst。不断的递归helper(n/2)至关于中序遍历的遍历左子树,每遍历一次,当前节点就日后移动一位。

 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 /**
10  * Definition for a binary tree node.
11  * public class TreeNode {
12  *     int val;
13  *     TreeNode left;
14  *     TreeNode right;
15  *     TreeNode(int x) { val = x; }
16  * }
17  */
18 public class Solution {
19     ListNode cur = null;
20     public TreeNode sortedListToBST(ListNode head) {
21         if (head == null) {
22             return null;
23         }
24         int len = getLen(head);
25         cur = head;
26         return helper(len);
27     }
28     public TreeNode helper(int n) {
29         if (n <= 0) {
30             return null;
31         }
32         TreeNode left = helper(n / 2);
33         TreeNode root = new TreeNode(cur.val);
34         cur = cur.next;
35         TreeNode right = helper(n - 1 - n / 2);
36         root.left = left;
37         root.right = right;
38         return root;
39     }
40     public int getLen(ListNode head) {
41         int len = 0;
42         while (head != null) {
43             len++;
44             head = head.next;
45         }
46         return len;
47     }
48 }
View Code

1.中序遍历的方法构建,一种顺序只有一种平衡二叉查找树吗 11/21

2.果真是忘了怎么去作。2016/12/06

leetcode 112. Path Sum

题意:是否存在根节点到叶子结点的节点值和等于某个值

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
View Code

解法:从根节点到叶子结点深度优先搜索,记录路径上的节点值和,到叶子节点的时候判断是否知足条件。

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public boolean hasPathSum(TreeNode root, int sum) {
12         if (root == null) {
13             return false;
14         }
15         return helper(root, sum, root.val);
16     }
17     public boolean helper(TreeNode root, int sum, int curSum) {
18         if (root.left == null && root.right == null) {
19             if (curSum == sum) {
20                 return true;
21             } else {
22                 return false;
23             }
24         }
25         if (root.left != null) {
26             if (helper(root.left, sum, curSum + root.left.val)) {
27                 return true;
28             }
29         }
30         if (root.right != null) {
31             if (helper(root.right, sum, curSum + root.right.val)) {
32                 return true;
33             }
34         }
35         return false;
36     }
37 }
View Code

leetcode 113 Path Sum II

题意:

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
return
[
   [5,4,11,2],
   [5,8,4,5]
]
View Code

解法:dfs,注意要求的是从根节点到叶子节点。

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public List<List<Integer>> pathSum(TreeNode root, int sum) {
12         List<List<Integer>> paths = new ArrayList<>();
13         if (root == null) {
14             return paths;
15         }
16         List<Integer> path = new ArrayList<>();
17         path.add(root.val);
18         helper(paths, path, root, sum, root.val);
19         return paths;
20     }
21     public void helper(List<List<Integer>> paths, List<Integer> path, TreeNode root, int sum, int curSum) {
22         if (root.left == null && root.right == null) {
23             if (curSum == sum) {
24                 paths.add(new ArrayList<>(path));
25             }
26             return;
27         }
28         if (root.left != null) {
29             path.add(root.left.val);
30             helper(paths, path, root.left, sum, curSum + root.left.val);
31             path.remove(path.size() - 1);
32         }
33         if (root.right != null) {
34             path.add(root.right.val);
35             helper(paths, path, root.right, sum, curSum + root.right.val);
36             path.remove(path.size() - 1);
37         }
38     }
39 }
View Code

1.题意看错了,看清题意 11/21

2.bug-free 2016/12/06

leetcode 437. Path Sum III

题意:找到二叉树中路径和等于给定值的路径种类数,路径的要求是从上到下,不要求根节点开始,叶子结点结束。

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11
View Code

解法:前缀和+hashmap+dfs

前缀和记录当前节点以前走过的路径的节点值和,hashmap存储前缀和以及前缀和出现的次数<preSum, ways>,每遍历一个节点判断preSum-target是否存在hashmap中,若是存在则将结果加上map.get(preSum-target),而后再分别遍历左子树和右子树,返回左子树和右子树的方法总数。

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public int pathSum(TreeNode root, int sum) {
12         HashMap<Integer, Integer> map = new HashMap<>();
13         map.put(0, 1);
14         return helper(root, 0, sum, map);
15     }
16     public int helper(TreeNode root, int curSum, int target, HashMap<Integer, Integer> map) {
17         if (root == null) {
18             return 0;
19         }
20         curSum += root.val;
21         int res = map.getOrDefault(curSum - target, 0);
22         map.put(curSum, map.getOrDefault(curSum, 0) + 1);
23         res += helper(root.left, curSum, target, map) + helper(root.right, curSum, target, map);
24         map.put(curSum, map.get(curSum) - 1);
25         return res;
26     }
27 }
View Code

leetcode 120 Triangle

题意:

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
View Code

 解法:动态规划,自底向上比较方便。

 1 public class Solution {
 2     public int minimumTotal(List<List<Integer>> triangle) {
 3         if (triangle == null || triangle.size() == 0 || triangle.get(0).size() == 0) {
 4             return 0;
 5         }
 6         int m = triangle.size();
 7         int n = triangle.get(m - 1).size();
 8         int[][] dp = new int[m][n];
 9         for (int i = 0; i < n; i++) {
10             dp[m - 1][i] = triangle.get(m - 1).get(i);
11         }
12         for (int i = m - 2; i >=0; i--) {
13             for (int j = 0; j < triangle.get(i).size(); j++) {
14                 dp[i][j] += triangle.get(i).get(j) + Math.min(dp[i + 1][j], dp[i + 1][j + 1]);
15             }
16         }
17         return dp[0][0];
18     }
19 }
View Code

1.动态规划的思路 11/22

2.bug-free 2016/12/06

leetcode 127 Word Ladder

题意:

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the word list
For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
View Code

解法:bfs,还有更优化的方法,待更新。

 1 public class Solution {
 2     public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
 3         if (wordList == null || wordList.size() == 0 || beginWord == null || endWord == null) {
 4             return 0;
 5         }
 6         
 7         wordList.add(endWord);
 8         int length = 0;
 9         Queue<String> qu = new LinkedList<>();
10         Set<String> visited = new HashSet<>();
11         qu.add(beginWord);
12         visited.add(beginWord);
13         
14         while (!qu.isEmpty()) {
15             length++;
16             int size = qu.size();
17             for (int i = 0; i < size; i++) {
18                 String cur = qu.poll();
19                 if (cur.equals(endWord)) {
20                     return length;
21                 }
22                 for (String neighbor : getAllWords(cur, wordList)) {
23                     if (!visited.contains(neighbor)) {
24                         qu.add(neighbor);
25                         visited.add(neighbor);
26                     }
27                 }
28             }
29         }
30         
31         return 0;
32     }
33     
34     public List<String> getAllWords(String word, Set<String> wordList) {
35         List<String> words = new ArrayList<>();
36         if (word == null) {
37             return words;
38         }
39         char[] arr = word.toCharArray();
40         for (int i = 0; i < word.length(); i++) {
41             char ch = arr[i];
42             for (char c = 'a'; c <= 'z'; c++) {
43                 if (c != ch) {
44                     arr[i] = c;
45                     if (wordList.contains(new String(arr))) {
46                         words.add(new String(arr));
47                     }
48                 }
49             }
50             arr[i] = ch;
51         }
52         
53         return words;
54     }
55 }
View Code

1.第一次超时了,为何? 一开始很慢11/22

2.第一次忘了去重,还有更优化的方法,待更新。bug-free 2016/12/10

leetcode 130 Surrounded Regions

题意:

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X
View Code

解法:矩阵的四条边上的'O'及其连通的'O',是没有被包围的,其他的都被包围了。因此先将这些不被包围的'O'改成'T',使用bfs。而后再遍历整个矩阵将'T'变为'O',剩下的'O'变为'X'。

   还有并查集的解法,待更新。2016/12/05 

 1 public class Solution {
 2     public class Position {
 3         int row = 0;
 4         int col = 0;
 5         public Position(int i, int j) {
 6             row = i;
 7             col = j;
 8         }
 9     }      
10     public void solve(char[][] board) {
11         if (board == null || board.length == 0) {
12             return;
13         }
14         int m = board.length;
15         int n = board[0].length;
16         //first row
17         for (int i = 0; i < n; i++) {
18             if (board[0][i] == 'O') {
19                 changeOToT(board, 0, i);
20             }
21             
22         }
23         if (m > 1) {
24             //last row
25             for (int i = 0; i < n; i++) {
26                 if (board[m - 1][i] == 'O') {
27                     changeOToT(board, m - 1, i);
28                 }
29             }
30         }
31         //first col
32         for (int i = 0; i < m; i++) {
33             if (board[i][0] == 'O') {
34                 changeOToT(board, i, 0);
35             }
36         }
37         if (n > 1) {
38             //last col
39             for (int i = 0; i < m; i++) {
40                 if (board[i][n - 1] == 'O') {
41                     changeOToT(board, i, n - 1);
42                 }
43             }
44         }
45         
46         for (int i = 0; i < m; i++) {
47             for (int j = 0; j < n; j++) {
48                 if (board[i][j] == 'T') {
49                     board[i][j] = 'O';
50                 } else if (board[i][j] == 'O') {
51                     board[i][j] = 'X';
52                 }
53             }
54         }
55     }
56     //bfs
57     public void changeOToT(char[][] board, int row, int col) {
58         board[row][col] = 'T';
59         Position pos = new Position(row, col);
60         Queue<Position> qu = new LinkedList<>();
61         qu.offer(pos);
62         while (!qu.isEmpty()) {
63             int size = qu.size();
64             for (int i = 0; i < size; i++) {
65                 Position curPos = qu.poll();
66                 int curRow = curPos.row;
67                 int curCol = curPos.col;
68                 //top
69                 if (curRow > 0 && board[curRow - 1][curCol] == 'O') {
70                     qu.offer(new Position(curRow - 1, curCol));
71                     board[curRow - 1][curCol] = 'T';
72                 }
73                 //down
74                 if (curRow < board.length - 1 && board[curRow + 1][curCol] == 'O') {
75                     qu.offer(new Position(curRow + 1, curCol));
76                     board[curRow + 1][curCol] = 'T';
77                 }
78                 //left
79                 if (curCol > 0 && board[curRow][curCol - 1] == 'O') {
80                     qu.offer(new Position(curRow, curCol - 1));
81                     board[curRow][curCol - 1] = 'T';
82                 }
83                 //right
84                 if (curCol < board[0].length - 1 && board[curRow][curCol + 1] == 'O') {
85                     qu.offer(new Position(curRow, curCol + 1));
86                     board[curRow][curCol + 1] = 'T';
87                 }
88             }
89         }
90     }
91 }
View Code

 1.思路 几种思路的比较 有坑注意 11/23

2. 2016/12/05 第二次作,发现第一次的去重是能够避免的,方法是每次加入queue以前先将相应位置改变为'T',这样就不用去重了 bug-free

 

leetcode 200. Number of Islands

题意:

View Code

解法:与上一题130相似的解法。还有并查集的解法,待更新。

 1 public class Solution {
 2     public class Position {
 3         int row = 0;
 4         int col = 0;
 5         public Position(int i, int j) {
 6             row = i;
 7             col = j;
 8         }
 9     }    
10     public int numIslands(char[][] grid) {
11         if (grid == null || grid.length == 0) {
12             return 0;
13         }
14         int m = grid.length;
15         int n = grid[0].length;
16         int count = 0;
17         for (int i = 0; i < m; i++) {
18             for (int j = 0; j < n; j++) {
19                 if (grid[i][j] == '1') {
20                     count++;
21                     changeOneToTwo(grid, i, j);
22                     j++;
23                 }
24             }
25         }
26         return count;
27     }
28     //bfs
29     public void changeOneToTwo(char[][] grid, int row, int col) {
30         grid[row][col] = '2';
31         Position pos = new Position(row, col);
32         Queue<Position> qu = new LinkedList<>();
33         qu.offer(pos);
34         while (!qu.isEmpty()) {
35             int size = qu.size();
36             for (int i = 0; i < size; i++) {
37                 Position curPos = qu.poll();
38                 int curRow = curPos.row;
39                 int curCol = curPos.col;
40                 //top
41                 if (curRow > 0 && grid[curRow - 1][curCol] == '1') {
42                     qu.offer(new Position(curRow - 1, curCol));
43                     grid[curRow - 1][curCol] = '2';
44                 }
45                 //down
46                 if (curRow < grid.length - 1 && grid[curRow + 1][curCol] == '1') {
47                     qu.offer(new Position(curRow + 1, curCol));
48                     grid[curRow + 1][curCol] = '2';
49                 }
50                 //left
51                 if (curCol > 0 && grid[curRow][curCol - 1] == '1') {
52                     qu.offer(new Position(curRow, curCol - 1));
53                     grid[curRow][curCol - 1] = '2';
54                 }
55                 //right
56                 if (curCol < grid[0].length - 1 && grid[curRow][curCol + 1] == '1') {
57                     qu.offer(new Position(curRow, curCol + 1));
58                     grid[curRow][curCol + 1] = '2';
59                 }
60             }
61         }
62     }
63 }
View Code

1.bug-free 还有并查集的解法,待更新。2016/12/05

 

leetcode 133 Clone Graph

题意:

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.


OJ's undirected graph serialization:
Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
Second node is labeled as 1. Connect node 1 to node 2.
Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/
View Code

解法:bfs+hashMap

 1 /**
 2  * Definition for undirected graph.
 3  * class UndirectedGraphNode {
 4  *     int label;
 5  *     List<UndirectedGraphNode> neighbors;
 6  *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 7  * };
 8  */
 9 public class Solution {
10     public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
11         if (node == null) {
12             return node;
13         }
14         HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
15         Set<UndirectedGraphNode> visited = new HashSet<>();
16         Queue<UndirectedGraphNode> qu = new LinkedList<>();
17         qu.offer(node);
18         visited.add(node);
19         while (!qu.isEmpty()) {
20             int size = qu.size();
21             for (int i = 0; i < size; i++) {
22                 UndirectedGraphNode cur = qu.poll();
23                 map.put(cur, new UndirectedGraphNode(cur.label));
24                 for (UndirectedGraphNode neighbor : cur.neighbors) {
25                     if (!visited.contains(neighbor)) {
26                         qu.offer(neighbor);
27                         visited.add(neighbor);
28                     }
29                 }
30             }
31         }
32         for (UndirectedGraphNode cur : map.keySet()) {
33             for (UndirectedGraphNode neighbor : cur.neighbors) {
34                 map.get(cur).neighbors.add(map.get(neighbor));
35             }
36         }
37         return map.get(node);
38     }
39 }
View Code

 

1.这是第二次作,发现了一个更快的方法,可是第一次犯了个小错误,在复制neighbors的时候把原节点复制过来了11/24

2.bug-free 2016/12/11

lintcode 460 K Closest Numbers In Sorted Array

题意:

Given a target number, a non-negative integer k and an integer array A sorted in ascending order, find the k closest numbers to target in A, sorted in ascending order by the difference between the number and target. Otherwise, sorted in ascending order by number if the difference is same.

Have you met this question in a real interview? Yes
Example
Given A = [1, 2, 3], target = 2 and k = 3, return [2, 1, 3].

Given A = [1, 4, 6, 8], target = 3 and k = 3, return [4, 1, 6].
View Code

解法:二分法找到最近的那个数,从最近 那个数开始往两边查找。时间复杂度为log(n)+O(k)

 1 public class Solution {
 2     /**
 3      * @param A an integer array
 4      * @param target an integer
 5      * @param k a non-negative integer
 6      * @return an integer array
 7      */
 8     public int[] kClosestNumbers(int[] A, int target, int k) {
 9         // Write your code here
10         if (A == null || A.length == 0 || k == 0 || k > A.length) {
11             return new int[0];
12         }
13         int len = A.length;
14         int start = 0;
15         int end = len - 1;
16         //选择差值最大的index为初始值
17         int index = Math.abs(A[0] - target) > Math.abs(A[end] - target) ? 0 : end;
18         while (start <= end) {
19             int mid = start + (end - start) / 2;
20             if (A[mid] == target) {
21                 index = mid;
22                 break;
23             }
24             if (Math.abs(A[mid] - target) < Math.abs(A[index] - target)) {
25                 index = mid;
26             } else if (Math.abs(A[mid] - target) == Math.abs(A[index] - target)) {
27                 //差值相等的时候 选择较小者
28                 if (A[mid] <= A[index]) {
29                     index = mid;
30                 } else {
31                     break;
32                 }
33             }
34             //继续下一轮比较
35             if (A[mid] < target) {
36                 start = mid + 1;
37             } else {
38                 end = mid - 1;
39             }
40         }
41         int left = index - 1;
42         int right = index + 1;
43         int count = 1;
44         int[] ans = new int[k];
45         ans[0] = A[index];
46         while (left >= 0 && right < len && count < k) {
47             if (Math.abs(A[left] - target) <= Math.abs(A[right] - target)) {
48                 ans[count++] = A[left--];
49             } else {
50                 ans[count++] = A[right++];
51             }
52         }
53         //尚未到达k个
54         while (left >= 0 && count < k) {
55             ans[count++] = A[left--];
56         }
57         while (right < len && count < k) {
58             ans[count++] = A[right++];
59         }
60         return ans;
61     }
62 }
View Code

1.第一次作踩了几个坑 2016/11/28

2.依然不熟练,记住本身的作法吧。 2016/12/12

leetcode 162. Find Peak Element 

 题意

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

click to show spoilers.

Note:
Your solution should be in logarithmic complexity.
View Code

解法:二分法,这里的难点在于不只要中点,还要将中点与中点和末端的中点去比较,从而判断峰值哪一侧

学到一点end - (end - mid) / 2; 与 mid + (end - mid) / 2;是结果不一样的两个式子,虽然化简后都为(end + mid)/2。
可是前者是更靠近末端的中位数,后者是更靠近前端的中位数。

这题用第一个式子,为何呢?由于这里主要是想让中位数与后面的数比较,若是选择第二个式子,在只剩两个数的时候,中位数比较的会是本身,选择第一个式子就会比较其后面一个数。

public class Solution {
    public int findPeakElement(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int len = nums.length;
        int start = 0;
        int end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            int rightMid = end - (end - mid) / 2;
            if (nums[mid] < nums[rightMid]) {
                start = mid + 1;
            } else if (nums[mid] > nums[rightMid]) {
                end = rightMid - 1;
            } else {
                start = mid;
                end = rightMid;
            }
        }
        return nums[start] > nums[end] ? start : end;
    }
}
View Code

1.第一次在lintcode上作的,本身的想法虽然ac了,可是感受不太好,看了九章的解法 遇到了一个小坑,必须得记住  2016/11/28

2.当相等的时候start和end怎么变化? 2016/12/03

3.无心中写出了一个不一样的方法,将mid和rightMid相等放在小于一块儿了 2016/12/18

 1 public class Solution {
 2     public int findPeakElement(int[] nums) {
 3         if (nums == null || nums.length == 0) {
 4             return -1;
 5         }
 6         int len = nums.length;
 7         int start = 0;
 8         int end = len - 1;
 9         while (start + 1 < end) {
10             int mid = start + (end - start) / 2;
11             int rightMid = end - (end - mid) / 2;
12             if (nums[mid] <= nums[rightMid]) {
13                 start = mid;
14             } else {
15                 end = rightMid - 1;
16             }
17         }
18         return nums[start] > nums[end] ? start : end;
19     }
20 }
View Code

 

lintcode 459 Closest Numbers In Sorted Array 

题意:

Given a target number and an integer array A sorted in ascending order, find the index i in A such that A[i] is closest to the given target.

Return -1 if there is no element in the array.

 Notice

There can be duplicate elements in the array, and we can return any of the indices with same value.

Have you met this question in a real interview? Yes
Example
Given [1, 2, 3] and target = 2, return 1.

Given [1, 4, 6] and target = 3, return 1.

Given [1, 4, 6] and target = 5, return 1 or 2.

Given [1, 3, 3, 4] and target = 2, return 0 or 1 or 2.
View Code

解法:二分法。小于往右,大于往左,若是距离减少了,则更新index

 1 public class Solution {
 2     /**
 3      * @param A an integer array sorted in ascending order
 4      * @param target an integer
 5      * @return an integer
 6      */
 7     public int closestNumber(int[] A, int target) {
 8         // Write your code here
 9         if (A == null || A.length == 0) {
10             return 0;
11         }
12         int start = 0;
13         int end = A.length - 1;
14         int index = Math.abs(A[0] - target) < Math.abs(A[end] - target) ? 0 : end;
15         while (start <= end) {
16             int mid = start + (end -start) / 2;
17             if (A[mid] == target) {
18                 return mid;
19             }
20             if (Math.abs(A[mid] - target) < Math.abs(A[index] - target)) {
21                     index = mid;
22             }
23             if (A[mid] < target) {
24                 start = mid + 1;
25             } else {
26                 end = mid - 1;
27             }
28         }
29         return index;
30     }
31 }
View Code

1.仍是有坑的,当距离没有减少的时候  2016/11/28 

2.bug-free 2016/12/18

lintcode 254 drop eggs 

题意:

There is a building of n floors. If an egg drops from the k th floor or above, it will break. If it's dropped from any floor below, it will not break.

You're given two eggs, Find k while minimize the number of drops for the worst case. Return the number of drops in the worst case.

Have you met this question in a real interview? Yes
Clarification
For n = 10, a naive way to find k is drop egg from 1st floor, 2nd floor ... kth floor. But in this worst case (k = 10), you have to drop 10 times.

Notice that you have two eggs, so you can drop at 4th, 7th & 9th floor, in the worst case (for example, k = 9) you have to drop 4 times.

Example
Given n = 10, return 4.
Given n = 100, return 14.
View Code

思路:

2016/11/29 first 题意没明白 若是一直不明白就记住吧

好比说有100层楼,从N楼开始扔鸡蛋会碎,低于N楼扔不会碎,如今给咱们两个鸡蛋,让咱们找到N,而且最小化最坏状况。

由于只有两个鸡蛋,因此第一个鸡蛋应该是按必定的间距扔,好比10楼,20楼,30楼等等,好比10楼和20楼没碎,30楼碎了,那么第二个鸡蛋就要作线性搜索,分别尝试21楼,22楼,23楼等等直到鸡蛋碎了,就能找到临界点。那么咱们来看下列两种状况:

假如临界点是9楼,那么鸡蛋1在第一次扔10楼碎掉,而后鸡蛋2依次遍历1到9楼,则总共须要扔10次。

假如临界点是100楼,那么鸡蛋1须要扔10次,到100楼时碎掉,而后鸡蛋2依次遍历91楼到100楼,总共须要扔19次。

因此上述方法的最坏状况是19次,那么有没有更少的方法呢,上面那个方法每多扔一次鸡蛋1,鸡蛋2的线性搜索次数最多仍是10次,那么最坏状况确定会增长,因此咱们须要让每多扔一次鸡蛋1,鸡蛋2的线性搜索最坏状况减小1,这样恩可以保持总体最坏状况的平衡,那么咱们假设鸡蛋1第一次在第X层扔,而后向上X-1层扔一次,而后向上X-2层扔,以此类推直到100层,那么咱们经过下面的公式求出X:

X + (X-1) + (X-2) + ... + 1 = 100 -> X = 14

因此咱们先到14楼,而后27楼,而后39楼,以此类推,最坏状况须要扔14次。
View Code

代码

 1 public class Solution {
 2     /**
 3      * @param n an integer
 4      * @return an integer
 5      */
 6     public int dropEggs(int n) {
 7         // Write your code here
 8         long sum = 0;
 9         for (int i = 1; i <= n; i++) {
10             sum += (long) i;
11             if (sum >= (long) n) {
12                 return i;
13             }
14         }
15         return 0;
16     }
17 }
View Code

1.一开始题意彻底没看懂 目标找到一种扔法,最小化最坏的状况 若是一直不明白就记住吧2016/11/29 

2.数据类型又忽略了,long。2016/12/18

lintcode 575 Expression Expand 

题意:

Given an expression s includes numbers, letters and brackets. Number represents the number of repetitions inside the brackets(can be a string or another expression).Please expand expression to be a string.

Have you met this question in a real interview? Yes
Example
s = abc3[a] return abcaaa
s = 3[abc] return abcabcabc
s = 4[ac]dy, return acacacacdy
s = 3[2[ad]3[pf]]xyz, return adadpfpfpfadadpfpfpfadadpfpfpfxyz
View Code

解法:非递归,用两个栈

 1 public class Solution {
 2     /**
 3      * @param s  an expression includes numbers, letters and brackets
 4      * @return a string
 5      */
 6     public String expressionExpand(String s) {
 7         // Write your code here
 8         if (s == null || s.length() == 0) {
 9             return s;
10         }
11         Stack<Integer> nums = new Stack<>();
12         Stack<String> strs = new Stack<>();
13         int num = 0;
14         
15         for (char c : s.toCharArray()) {
16             if (Character.isDigit(c)) {
17                 num = num * 10 + c - '0';
18             } else if (c == '[') {
19                 strs.push("[");
20                 nums.push(num);
21                 num = 0;
22             } else if (c == ']') {
23                 Stack<String> out = new Stack<>();
24                 while (!strs.isEmpty()) {
25                     String topStr = strs.pop();
26                     if (topStr.equals("[")) {
27                         StringBuilder outStrs = new StringBuilder("");
28                         StringBuilder outStr = new StringBuilder("");
29                         while (!out.isEmpty()) {
30                             outStr.append(out.pop());
31                         }
32                         if (!nums.isEmpty()) {
33                            int times = nums.pop();
34                            for (int i = 0; i < times; i++) {
35                                outStrs.append(outStr);
36                            }
37                         }
38                         strs.push(outStrs.toString());
39                         break;
40                     }
41                     out.push(topStr);
42                 }
43             } else {
44                 strs.push(String.valueOf(c));
45             }
46         }
47         
48         Stack<String> out = new Stack<>();
49         StringBuilder outStr = new StringBuilder("");
50         while (!strs.isEmpty()) {
51             String topStr = strs.pop();
52             out.push(topStr);
53         }
54         while (!out.isEmpty()) {
55             outStr.append(out.pop());
56         }
57         
58         return outStr.toString();
59     }
60 }
View Code

1.第一遍用递归的方法作出来了,可是不太好,最好能用非递归实现2016/11/29

lintcode 470 Tweaked Identical Binary Tree 

题意:

Check two given binary trees are identical or not. Assuming any number of tweaks are allowed. A tweak is defined as a swap of the children of one node in the tree.

 Notice

There is no two nodes with the same value in the tree.

Have you met this question in a real interview? Yes
Example
    1             1
   / \           / \
  2   3   and   3   2
 /                   \
4                     4
are identical.

    1             1
   / \           / \
  2   3   and   3   2
 /             /
4             4
are not identical.
View Code

解法:分治法

 1 /**
 2  * Definition of TreeNode:
 3  * public class TreeNode {
 4  *     public int val;
 5  *     public TreeNode left, right;
 6  *     public TreeNode(int val) {
 7  *         this.val = val;
 8  *         this.left = this.right = null;
 9  *     }
10  * }
11  */
12 public class Solution {
13     /**
14      * @param a, b, the root of binary trees.
15      * @return true if they are tweaked identical, or false.
16      */
17     public boolean isTweakedIdentical(TreeNode a, TreeNode b) {
18         // Write your code here
19         if (a == null && b == null) {
20             return true;
21         }
22         if (a == null || b == null) {
23             return false;
24         }
25         if (a.val != b.val) {
26             return false;
27         }
28         return (isTweakedIdentical(a.left, b.left) && 
29                isTweakedIdentical(a.right, b.right)) || 
30                (isTweakedIdentical(a.left, b.right) && 
31                isTweakedIdentical(a.right, b.left));
32     }
33 }
View Code

1.题意理解错误2016/11/29

2.bug-free 2016/12/19

lintcode 66 Binary Tree Preorder Traversal  / 67 Binary Tree Inorder Traversal / 68 Binary Tree Postorder Traversal 

解法:递归与非递归  面试时通常都是非递归

preorder non-recursion 先右后左各一次

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> order = new ArrayList<>();
        if (root == null) {
            return order;
        }
        Stack<TreeNode> s = new Stack<TreeNode>();
        s.push(root);
        while (!s.isEmpty()) {
            TreeNode node = s.pop();
            order.add(node.val);
            if (node != null && node.right != null) {
                s.push(node.right);
            }    
            if (node != null && node.left != null) {
                s.push(node.left);
            }
        }
        return order;
    }
}
View Code

preorder recursion

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> order = new ArrayList<>();
        if (root == null) {
            return order;
        }
        helper(root, order);
        return order;
    }
    public void helper(TreeNode root, List<Integer> order) {
        if (root == null) {
            return;
        }
        order.add(root.val);
        helper(root.left, order);
        helper(root.right, order);
    }
}
View Code

inorder non-recursion 左循环右一次

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public List<Integer> inorderTraversal(TreeNode root) {
12         List<Integer> ans = new ArrayList<Integer>();
13         if (root == null) {
14             return ans;
15         }
16         Stack<TreeNode> s = new Stack<>();
17         s.push(root);
18         while (!s.isEmpty()) {
19             while (root.left != null) {
20                 root = root.left;
21                 s.push(root);
22             }
23             TreeNode cur = s.pop();
24             ans.add(cur.val);
25             if (cur.right != null) {
26                 s.push(cur.right);
27                 root = cur.right;
28             }
29         }
30         return ans;
31     }
32 }
View Code

inorder recursion

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> order = new ArrayList<>();
        if (root == null) {
            return order;
        }
        helper(root, order);
        return order;
    }
    public void helper(TreeNode root, List<Integer> order) {
        if (root == null) {
            return;
        }
        helper(root.left, order);
        order.add(root.val);
        helper(root.right, order);
    }
}
View Code

postorder non-recursion 先左后右各一次,插入头部

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public List<Integer> postorderTraversal(TreeNode root) {
12         List<Integer> ans = new ArrayList<>();
13         if (root == null) {
14             return ans;
15         }
16         Stack<TreeNode> s = new Stack<>();
17         s.push(root);
18         while (!s.isEmpty()) {
19             TreeNode cur = s.pop();
20             ans.add(0, cur.val);
21             if (cur.left != null) {
22                 s.push(cur.left);
23             }
24             if (cur.right != null) {
25                 s.push(cur.right);
26             }
27         }
28         return ans;
29     }
30 }
View Code

 1.不熟练,仍是得记住 2016/11/29

2.前序遍历bug-free了 2016/12/01 

 3.中序遍历bug-free,后序遍历找到了更好的解法,与前序遍历倒序的 2016/12/18

lintcode 464 sort-integers-ii 

题意:

Given an integer array, sort it in ascending order. Use quick sort, merge sort, heap sort or any O(nlogn) algorithm.

Have you met this question in a real interview? 
Yes
Example
Given [3, 2, 1, 4, 5], return [1, 2, 3, 4, 5].
View Code

1.quickSort

 1 public class Solution {
 2     /**
 3      * @param A an integer array
 4      * @return void
 5      */
 6     public void sortIntegers2(int[] A) {
 7         // Write your code here
 8         if (A == null || A.length == 0) {
 9             return;
10         }
11         quickSort(A, 0, A.length - 1);
12     }
13     public void quickSort(int[] nums, int start, int end) {
14         if (start > end) {
15             return;
16         }
17         int left = start;
18         int right = end;
19         int pivot = nums[start + (end - start) / 2];
20         while (left <= right) {
21             while (left <= right && nums[left] < pivot) {
22                 left++;
23             }
24             while (left <= right && nums[right] > pivot) {
25                 right--;
26             }
27             if (left <= right) {
28                 int temp = nums[left];
29                 nums[left] = nums[right];
30                 nums[right] = temp;
31                 left++;
32                 right--;
33             }
34         }
35         quickSort(nums, start, right);
36         quickSort(nums, left, end);
37     }
38 }
View Code

2.mergeSort

 1 public class Solution {
 2     /**
 3      * @param A an integer array
 4      * @return void
 5      */
 6     int[] temp = null;
 7     public void sortIntegers2(int[] A) {
 8         // Write your code here
 9         if (A == null || A.length == 0) {
10             return;
11         }
12         temp = new int[A.length];
13         mergeSort(A, 0, A.length - 1);
14     }
15     public void mergeSort(int[] nums, int start, int end) {
16         if (start == end) {
17             return;
18         }
19         int mid = start + (end - start) / 2;
20         mergeSort(nums, start, mid);
21         mergeSort(nums, mid + 1, end);
22         merge(nums, start, end);
23     }
24     public void merge(int[] nums, int start, int end) {
25         int mid = start + (end - start) / 2;
26         for (int i = start; i <= end; i++) {
27             temp[i] = nums[i];
28         }
29         int left = start;
30         int right = mid + 1;
31         while (left <= mid && right <= end) {
32             if (temp[left] <= temp[right]) {
33                 nums[start++] = temp[left++];
34             } else {
35                 nums[start++] = temp[right++];
36             }
37         }
38         while (left <= mid) {
39             nums[start++] = temp[left++];
40         }
41     } 
42 }
View Code

3.heapSort

 1 public class Solution {
 2     /**
 3      * @param A an integer array
 4      * @return void
 5      */
 6     public void sortIntegers2(int[] A) {
 7         // Write your code here
 8         heapSort(A);
 9     }
10     public void heapSort(int[] a) {
11         for (int i = a.length / 2 - 1; i >= 0; i--) {
12             createHeap(a, i, a.length - 1);
13         }
14         for (int i = a.length - 1; i > 0; i--) {
15             int temp = a[0];
16             a[0] = a[i];
17             a[i] = temp;
18             createHeap(a, 0, i - 1);
19         }
20     }
21     public void createHeap(int[] a, int i, int end) {
22         int l = 2 * i + 1;
23         while (l <= end) {
24             if (l + 1 <= end && a[l + 1] > a[l]) {
25                 l = l + 1;
26             }
27             if (a[i] < a[l]) {
28                 int temp = a[i];
29                 a[i] = a[l];
30                 a[l] = temp;
31             }
32             i = l;
33             l = 2 * i + 1;
34         }
35     }
36 }
View Code

bug-free process:

1.快速排序,推排序和归并排序必需要熟练掌握 2016/11/30

2.quicksort,mergesort bug-free,heapsort 再写一次 2016/12/19

3.更新了heap sort的解法。2017/04/12

lintcode 87 remove-node-in-binary-search-tree 

题意:

Given a root of Binary Search Tree with unique value for each node. Remove the node with given value. If there is no such a node with given value in the binary search tree, do nothing. You should keep the tree still a binary search tree after removal.

Have you met this question in a real interview? Yes
Example
Given binary search tree:

    5
   / \
  3   6
 / \
2   4
Remove 3, you can either return:

    5
   / \
  2   6
   \
    4
or

    5
   / \
  4   6
 /
2
View Code

解法:第一步先找到要删除的节点,并返回其父节点(因此要用到dummynode);第二步删除该节点,多该节点右子树为空,则直接将左子节点替换,反之将右子树的最左节点替换

 1 /**
 2  * Definition of TreeNode:
 3  * public class TreeNode {
 4  *     public int val;
 5  *     public TreeNode left, right;
 6  *     public TreeNode(int val) {
 7  *         this.val = val;
 8  *         this.left = this.right = null;
 9  *     }
10  * }
11  */
12 public class Solution {
13     /**
14      * @param root: The root of the binary search tree.
15      * @param value: Remove the node with given value.
16      * @return: The root of the binary search tree after removal.
17      */
18     public TreeNode removeNode(TreeNode root, int value) {
19         // write your code here
20         if (root == null) {
21             return root;
22         }
23         TreeNode dummy = new TreeNode(0);
24         dummy.left = root;
25         TreeNode parent = findNode(dummy, root, value);
26         if (parent.left != null && parent.left.val == value) {
27             deleteNode(parent, parent.left);
28         } else if (parent.right != null && parent.right.val == value) {
29             deleteNode(parent, parent.right);
30         } else {
31             return dummy.left;
32         }
33         return dummy.left;
34     }
35     public TreeNode findNode(TreeNode parent, TreeNode root, int value) {
36         if (root == null || root.val == value) {
37             return parent;
38         }
39         if (root.val < value) {
40             return findNode(root, root.right, value);
41         } else {
42             return findNode(root, root.left, value);
43         }
44     }
45     public void  deleteNode(TreeNode parent, TreeNode node) {
46         if (node.right == null) {
47             if (parent.left == node) {
48                 parent.left = node.left;
49             } else {
50                 parent.right = node.left;
51             }
52         } else {
53             TreeNode father = node;
54             TreeNode child = node.right;
55             while (child.left != null) {
56                 father = child;
57                 child = child.left;
58             }
59             if (father.left == child) {
60                 father.left = child.right;
61             } else {
62                 father.right = child.right;
63             }
64             if (parent.left == node) {
65                 parent.left = child;
66             } else {
67                 parent.right = child;
68             }
69             child.right = node.right;
70             child.left = node.left;
71         }
72     }
73 }
View Code

1.没有想出有效的思路,主要是删除的时候应该将哪一个节点替换过来 2016/12/01

2.注意区分待删除节点右子树没有左子树的时候 2016/12/19

lintcode 581 Longest Repeating Subsequence  

1.与lintcode 77 很像的一道题,看了九章的答案才想到2016/12/01

leetcode 70. Climbing Stairs  

1.常数空间的解法 2016/12/01

leetcode 134. Gas Station 

题意:

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

Note:
The solution is guaranteed to be unique.
View Code

解法:

localSum从i到j的剩余汽油量,若是小于0,则意味着i到j不会有出发点,出发点就从i + 1开始,将localSum清零
sum是为了整个一圈的汽油剩余量,只有最后的sum > 0才会存在这个出发点

 1 public class Solution {
 2     public int canCompleteCircuit(int[] gas, int[] cost) {
 3         if (gas == null || cost == null || gas.length == 0 || cost.length == 0) {
 4             return -1;
 5         }
 6         int start = 0;
 7         int localSum = 0;
 8         int sum = 0;
 9         //localSum从i到j的剩余汽油量,若是小于0,则意味着i到j不会有出发点,出发点就从i + 1开始
10         //sum是为了整个一圈的汽油剩余量,只有最后的sum > 0才会存在这个出发点
11         for (int i = 0; i < gas.length; i++) {
12             localSum += gas[i] - cost[i];
13             sum += gas[i] - cost[i];
14             if (localSum < 0) {
15                 localSum = 0;
16                 start = i + 1;
17             }
18         }
19         return sum >= 0 ? start : -1;
20     }
21 }
View Code

bug-free process

1. O(n)的解法,贪心法  2016/12/01

2.bug-free 2016/12/19

leetcode 140 Word Break II

题意:返回给定的字符串能被给定的词典里面的单词切分的所有方案

解法:dfs+hashmap。判断单词的前一部分可否在字典中找到,若是能,则继续判断剩余的部分,并将剩余部分的切分结果与前一部分组合起来,返回这个结果就是总体的切分方案。hashmap用来记录某个子字符串的分割方案,在下次遇到这个子字符串的时候就能够直接返回了。

 1 public class Solution {
 2     public List<String> wordBreak(String s, List<String> wordDict) {
 3         return helper(s, wordDict, new HashMap<String, List<String>>());
 4     }
 5     public List<String> helper(String s, List<String> wordDict, HashMap<String, List<String>> map) {
 6         if (map.containsKey(s)) {
 7             return map.get(s);
 8         }
 9         List<String> res = new ArrayList<>();
10         if (s.length() == 0) {
11             res.add("");
12             return res;
13         }
14         for (String word : wordDict) {
15             if (s.startsWith(word)) {
16                 List<String> list = helper(s.substring(word.length()), wordDict, map);
17                 for (String l : list) {
18                     res.add(word + (l.isEmpty() ? "" : " ") + l);
19                 }
20             }
21         }
22         map.put(s, res);
23         return res;
24     }
25 }
View Code

 leetcode 139. Word Break--头条面试题

题意:判断给定的字符串可否被给定的词典里面的单词切分

解法:第二次作能想出dp的解法,但不是最优,最优解法是先获取整个字典中字符串的最大长度,避免在dp的时候有没必要要的计算

    dp[i]表示以第i个字符结尾的子字符串是否能够正确划分 

    if (wordDict.contains(s.substring(j, i)) && dp[j])  dp[i] = true;

public class Solution {
    public boolean wordBreak(String s, Set<String> wordDict) {
        if (s == null || wordDict == null || s.length() == 0) {
            return false;
        }
        int maxLen = getMaxLen(wordDict);
        int len = s.length();
        //dp[i]表示以第i个字符结尾的子字符串是否能够正确划分 
        boolean[] dp = new boolean[len + 1];
        dp[0] = true;
        for (int i = 1; i <= len; i++) {
            for (int j = i - 1; j >= 0 && i - j <= maxLen; j--) {
                if (wordDict.contains(s.substring(j, i)) && dp[j]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[len];
    }
    //最优解法是先获取整个字典中字符串的最大长度,避免在dp的时候有没必要要的计算
    public int getMaxLen(Set<String> wordDict) {
        int max = 0;
        for (String word : wordDict) {
            max = Math.max(max, word.length());
        }
        return max;
    }
}
View Code

2.2016/12/01 实现了普通的dp,但不是最优解

leetcode 142. Linked List Cycle II 判断链表是否有环,有的话返回环起点

解法:使用快慢指针判断,俩指针若相交必有环。 有环时再新加一个指针指向head,head与slow一块儿移动,交点即为环的起点

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast= fast.next.next;
            if (slow == fast) {
                ListNode start = head;
                while (start != null && slow != null) {
                    if (start == slow) {
                        return start;
                    }
                    slow = slow.next;
                    start = start.next;
                }
            }
        }
        return null;
    }
}
View Code

2.2016/12/02 这里slow=head,fast = head 循环的时候只用判断fast,不用去判断slow是否为空。 若是是求中点slow = head, fast=head.next 最后slow才是正确的中点

  反之slow=head,fast = head,当节点个数是偶数个时求得的slow会是中点的下一个,节点个数奇数个时,slow仍是中点

leetcode 143. Reorder List

解法:先找到中点,再将中点的下一个节点开始反转,最后双指针,一个指向头结点,一个指向尾结点,一块儿向next推动,合并左右两个部分

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param head: The head of linked list.
     * @return: void
     */
    public void reorderList(ListNode head) {  
        // write your code here
        if (head == null || head.next == null) {
            return ;
        }
        ListNode mid = findMid(head);
        ListNode rightHead = reverse(mid.next);
        mid.next = null;
        ListNode leftCurt = head;
        ListNode rightCurt = rightHead;
        while (leftCurt != null && rightCurt != null) {
            ListNode nextLeft = leftCurt.next;
            leftCurt.next = rightCurt;
            ListNode nextRight = rightCurt.next;
            rightCurt.next = nextLeft;
            leftCurt = nextLeft;
            rightCurt = nextRight;
        }
    }
    public ListNode findMid(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    public ListNode reverse(ListNode head) {
        // write your code here
        if (head == null) {
            return head;
        }
        ListNode prev = null;
        ListNode curt = head;
        while (curt != null) {
            ListNode next = curt.next;
            curt.next = prev;
            prev = curt;
            curt = next;
        }
        return prev;
    }
}
View Code

2. 2016/12/02 主要是要统一一下找链表中点和反转链表的标准写法,不要每次写的都不同,容易出错

找链表中点与反转链表的标准写法

    public ListNode findMid(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    public ListNode reverse(ListNode head) {
        // write your code here
        if (head == null) {
            return head;
        }
        ListNode prev = null;
        ListNode curt = head;
        while (curt != null) {
            ListNode next = curt.next;
            curt.next = prev;
            prev = curt;
            curt = next;
        }
        return prev;
    }
View Code

 leetcode 147. Insertion Sort List 

解法:用插入排序与dummy node ,每次将原来的链表中未排序的部分与dummy node链接的排序的部分比较,找位置插入

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        while (head != null) {
            ListNode node = dummy;
            while (node.next != null && node.next.val < head.val) {
                node = node.next;
            }
            ListNode next = head.next;
            head.next = node.next;
            node.next = head;
            head = next;
        }
        return dummy.next;
    }
}
View Code

1. dummy node 一开始后面不要接任何元素,从head开始一个一个加入 2016/12/02

leetcode 148. Sort List 

解法:归并排序 :先找到中点,再递归归并排序,链接两个排序子链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode sortList(ListNode head) {
        return mergeSort(head);
    }
    //归并排序
    public ListNode mergeSort(ListNode head) {
        //head.next == null是必须的,否则不会终结
        if (head == null || head.next == null) {
            return head;
        }
        ListNode mid = findMid(head);
        ListNode right = mid.next;
        mid.next = null;
        ListNode left = mergeSort(head);
        right = mergeSort(right);
        return merge(left, right);
    }
    //merge两个排序好的子链表
    public ListNode merge(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (left != null && right != null) {
            if (left.val < right.val) {
                cur.next = left;
                left = left.next;
            } else {
                cur.next = right;
                right = right.next;
            }
            cur = cur.next;
        }
        if (left != null) {
            cur.next = left;
        }
        if (right != null) {
            cur.next = right;
        }
        return dummy.next;
    }
    //找到中点
    public ListNode findMid(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}
View Code

2. 在归并排序的时候 递归结束的判断条件必定是 head == null || head.next == null ,后面的一项必须有,要否则会递归结束不了 2016/12/02

leetcode 150 Evaluate Reverse Polish Notation

解法:题意是计算反向波兰表达式(后缀表达式),利用栈,遇到数值则入栈,遇到操做符则将栈顶两个数值出栈,并计算结果后入栈。

public class Solution {
    public int evalRPN(String[] tokens) {
        if (tokens == null || tokens.length == 0) {
            return 0;
        }
        int len = tokens.length;
        Stack<Integer> operand = new Stack<>();
        for (int i = 0; i < len; i++) {
            if (tokens[i].equals("+") || tokens[i].equals("-") || 
                tokens[i].equals("*") || tokens[i].equals("/")) {
                if (operand.size() >= 2) {
                    int a = operand.pop();
                    int b = operand.pop();
                    int c = 0;
                    if (tokens[i].equals("+")) {
                        c = b + a;
                    } else if (tokens[i].equals("-")) {
                        c = b - a;
                    } else if (tokens[i].equals("*")) {
                        c = b * a;
                    } else {
                        c = b / a;
                    }
                    operand.push(c);
                } else {
                    return 0;
                }    
            } else {
                operand.push(Integer.valueOf(tokens[i]));
            }
        }
        if (!operand.isEmpty() && operand.size() == 1) {
            return operand.pop();
        }
        return 0;
    }
}
View Code

1.2016/12/03 题意中的Each operand may be an integer or another expression.这句话没看懂。我就把每一个字符串当作要么是操做符要么是整数了,结果仍是ac了。

leetcode 151 Reverse Words in a String

题意

Given an input string, reverse the string word by word.

For example,
Given s = "the sky is blue",
return "blue is sky the".

Update (2015-02-12):
For C programmers: Try to solve it in-place in O(1) space.

click to show clarification.

Clarification:
What constitutes a word?
A sequence of non-space characters constitutes a word.
Could the input string contain leading or trailing spaces?
Yes. However, your reversed string should not contain leading or trailing spaces.
How about multiple spaces between two words?
Reduce them to a single space in the reversed string.
View Code

解法:利用split(" "),以空格" "做为分隔符对原字符串进行分割,将获得的字符串数组,逆向组合起来,而且每一个字符串之间以空格分开,注意最后一个字符串的后面不要有空格。

  值得记住的是spit(" ")遇到多个空格时,也会分割,只是分得的字符串为"",也就是长度为零的字符串,在这里要省去这些字符串,不要将其假如最后的结果中

 1 public class Solution {
 2     public String reverseWords(String s) {
 3         if (s == null && s.length() == 0) {
 4             return s;
 5         }
 6         String[] arrs = s.split(" ");
 7         StringBuilder ans = new StringBuilder("");
 8         for (int i = arrs.length - 1; i >= 0 ; i--) {
 9             if (arrs[i].length() == 0) {
10                 continue;
11             }
12             ans.append(arrs[i]);
13             ans.append(" ");
14         }
15         return ans.length() > 0 ? ans.substring(0, ans.length() - 1) : "";
16     }
17 }
View Code

bug-free process

1.2016/12/03 愚蠢的将分割获得的字符串数组进行了先后交换倒序,这是多余的步骤

leetcode 152. Maximum Product Subarray

题意

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.
View Code

解法:动态规划,用两个数组分别记录以nums[i]结尾的子数组的最大乘积和最小乘积。判断当前nums[i]的正负性,根据如下规则更新两个数组

      用最大的数乘以一个正数会获得最可能大的数

        用最小的数乘以一个正数会获得最可能小的数

    用最小的数乘以一个负数会获得最可能大的数
    用最大的数乘以一个负数会获得最可能小的数

 1 public class Solution {
 2     public int maxProduct(int[] nums) {
 3         if (nums == null || nums.length == 0) {
 4             return 0;
 5         }
 6         int len = nums.length;
 7         //以nums[i]结尾的乘积最大子数组的乘积
 8         int[] max = new int[len];
 9         max[0] = nums[0];
10         //以nums[i]结尾的乘积最小子数组的乘积
11         int[] min = new int[len];
12         min[0] = nums[0];
13         int maxProduct = nums[0];
14         for (int i = 1; i < nums.length; i++) {
15             if (nums[i] > 0) {
16                 // 用最大的数乘以一个正数会获得最可能大的数
17                 max[i] = Math.max(nums[i], max[i - 1] * nums[i]);
18                 // 用最小的数乘以一个正数会获得最可能小的数
19                 min[i] = Math.min(nums[i], min[i - 1] * nums[i]);
20             } else if (nums[i] < 0) {
21                 // 用最小的数乘以一个负数会获得最可能大的数
22                 max[i] = Math.max(nums[i], min[i - 1] * nums[i]);
23                 // 用最大的数乘以一个负数会获得最可能小的数
24                 min[i] = Math.min(nums[i], max[i - 1] * nums[i]);                
25             } else {
26                 //nums[i] = 0时,max[i] = min[i] = 0
27                 max[i] = 0;
28                 min[i] = 0;
29             }
30             maxProduct = Math.max(maxProduct, max[i]);
31         }
32         return maxProduct;
33     }
34 }
View Code

1.2016/12/03 没有想出来,以上四句话很重要

2.仍是没记住 2016/12/20

166. Fraction to Recurring Decimal

题意:

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

For example,

Given numerator = 1, denominator = 2, return "0.5".
Given numerator = 2, denominator = 1, return "2".
Given numerator = 2, denominator = 3, return "0.(6)".
Hint:

No scary math, just apply elementary math knowledge. Still remember how to perform a long division?
Try a long division on 4/9, the repeating part is obvious. Now try 4/333. Do you see a pattern?
Be wary of edge cases! List out as many test cases as you can think of and test your code thoroughly.
Credits:
View Code

解法:主要是想到该怎么实现除法,而后就是利用hashmap来记录余数与商的对应,余数的重复表示这小数部分循环的开始

 1 public class Solution {
 2     public String fractionToDecimal(int numerator, int denominator) {
 3         if (denominator == 0) {
 4             return null;
 5         }
 6         StringBuilder ans = new StringBuilder("");
 7         if (numerator == 0) {
 8             ans.append("0");
 9             return ans.toString();
10         }
11         if (numerator > 0 && denominator < 0 || numerator < 0 && denominator > 0) {
12             ans.append('-');
13         }
14         long a = Math.abs((long) numerator);
15         long b = Math.abs((long) denominator);
16         //整数部分
17         long quotient = a / b;
18         a -= quotient * b;
19         ans.append(String.valueOf(quotient));
20         if (a != 0) {
21             ans.append(".");
22         } else {
23             return ans.toString();
24         }
25         //小数部分
26         int index = ans.length();
27         //记录每一个余数对应的商在字符串中的位置
28         Map<Long, Integer> remainders = new HashMap<>(); 
29         remainders.put(a, index);
30         int start = -1;
31         while (a != 0) {
32             index++;
33             a *= 10; 
34             quotient = a / b;
35             a -= quotient * b;
36             ans.append(String.valueOf(quotient));
37             //若是余数在以前出现过,则表示循环开始了,获取循环开始的位置
38             if (remainders.containsKey(a)) {
39                 start = remainders.get(a);
40                 ans.insert(start, '(');
41                 ans.append(')');
42                 return ans.toString();
43             }
44             remainders.put(a, index);
45         }
46         return ans.toString();
47     }
48 }
View Code

1.出错点很多,主要是负号的处理,数据类型的转换防止溢出 2016/12/03 not bug-free

leetcode 18 4Sum

题意:求四个数之和等于目标数

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]
View Code

思路:O(n^3)的时间复杂度,基于3sum的解法,至关于固定前两个数,对其他两个数用两指针方法。

 1 public class Solution {
 2     public List<List<Integer>> fourSum(int[] nums, int target) {
 3         Arrays.sort(nums);
 4         List<List<Integer>> result = new ArrayList<List<Integer>>();        
 5         for(int i =0;i<nums.length-3;i++){
 6             if(i>0&&nums[i]==nums[i-1]){
 7                 continue;//重复的直接跳过
 8             }
 9             for(int j = i+1;j<nums.length-2;j++){
10                 if(j>i+1&&nums[j]==nums[j-1]){
11                     continue;//重复的直接跳过
12                 }
13                 int left = j+1;//从i+1开始也是防止重复的办法
14                 int right = nums.length-1;
15                 while(left<right){
16                     if(nums[left]+nums[right]+nums[i]+nums[j] == target){
17                         List<Integer> temp = new ArrayList<Integer>();//必须每次新建
18                         temp.add(nums[i]);
19                         temp.add(nums[left]);
20                         temp.add(nums[right]);
21                         temp.add(nums[j]);
22                         Collections.sort(temp);
23                         result.add(temp);
24                         //特别注意下面两个while循环
25                         left++;
26                         right--;//防止重复                        
27                         while(left<right&&nums[left]==nums[left-1]){
28                             left++;//防止重复   
29                         } 
30                         while(left<right&&nums[right]==nums[right+1]){
31                             right--;//防止重复   
32                         }         
33                         //这两个条件特别重要,思考一下为什么分别是left++和right--;
34                     }else if(nums[left]+nums[right]+nums[i]+nums[j]<target){
35                         left++;
36                     }else{
37                         right--;
38                     }
39                 }
40             }
41         }
42         return result;
43         
44     }
45 }
View Code

优化过的代码,提早排除了一些不可能的状况,减小循环次数,可是时间复杂度是不变的。

  1 public class Solution {
  2     public List<List<Integer>> fourSum(int[] nums, int target) {
  3             ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
  4             int len = nums.length;
  5             if (nums == null || len < 4)
  6                 return res;
  7     
  8             Arrays.sort(nums);
  9     
 10             int max = nums[len - 1];
 11             if (4 * nums[0] > target || 4 * max < target)
 12                 return res;
 13     
 14             int i, z;
 15             for (i = 0; i < len; i++) {
 16                 z = nums[i];
 17                 if (i > 0 && z == nums[i - 1])// avoid duplicate
 18                     continue;
 19                 if (z + 3 * max < target) // z is too small
 20                     continue;
 21                 if (4 * z > target) // z is too large
 22                     break;
 23                 if (4 * z == target) { // z is the boundary
 24                     if (i + 3 < len && nums[i + 3] == z)
 25                         res.add(Arrays.asList(z, z, z, z));
 26                     break;
 27                 }
 28     
 29                 threeSumForFourSum(nums, target - z, i + 1, len - 1, res, z);
 30             }
 31     
 32             return res;
 33         }
 34     
 35         /*
 36          * Find all possible distinguished three numbers adding up to the target
 37          * in sorted array nums[] between indices low and high. If there are,
 38          * add all of them into the ArrayList fourSumList, using
 39          * fourSumList.add(Arrays.asList(z1, the three numbers))
 40          */
 41         public void threeSumForFourSum(int[] nums, int target, int low, int high, ArrayList<List<Integer>> fourSumList,
 42                 int z1) {
 43             if (low + 1 >= high)
 44                 return;
 45     
 46             int max = nums[high];
 47             if (3 * nums[low] > target || 3 * max < target)
 48                 return;
 49     
 50             int i, z;
 51             for (i = low; i < high - 1; i++) {
 52                 z = nums[i];
 53                 if (i > low && z == nums[i - 1]) // avoid duplicate
 54                     continue;
 55                 if (z + 2 * max < target) // z is too small
 56                     continue;
 57     
 58                 if (3 * z > target) // z is too large
 59                     break;
 60     
 61                 if (3 * z == target) { // z is the boundary
 62                     if (i + 1 < high && nums[i + 2] == z)
 63                         fourSumList.add(Arrays.asList(z1, z, z, z));
 64                     break;
 65                 }
 66     
 67                 twoSumForFourSum(nums, target - z, i + 1, high, fourSumList, z1, z);
 68             }
 69     
 70         }
 71     
 72         /*
 73          * Find all possible distinguished two numbers adding up to the target
 74          * in sorted array nums[] between indices low and high. If there are,
 75          * add all of them into the ArrayList fourSumList, using
 76          * fourSumList.add(Arrays.asList(z1, z2, the two numbers))
 77          */
 78         public void twoSumForFourSum(int[] nums, int target, int low, int high, ArrayList<List<Integer>> fourSumList,
 79                 int z1, int z2) {
 80     
 81             if (low >= high)
 82                 return;
 83     
 84             if (2 * nums[low] > target || 2 * nums[high] < target)
 85                 return;
 86     
 87             int i = low, j = high, sum, x;
 88             while (i < j) {
 89                 sum = nums[i] + nums[j];
 90                 if (sum == target) {
 91                     fourSumList.add(Arrays.asList(z1, z2, nums[i], nums[j]));
 92     
 93                     x = nums[i];
 94                     while (++i < j && x == nums[i]) // avoid duplicate
 95                         ;
 96                     x = nums[j];
 97                     while (i < --j && x == nums[j]) // avoid duplicate
 98                         ;
 99                 }
100                 if (sum < target)
101                     i++;
102                 if (sum > target)
103                     j--;
104             }
105             return;
106         }
107 }
View Code

 

leetcode 16. 3Sum Closest

题意:找出三个数之和与目标数最接近的和。

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
View Code

思路:依然是先将数组排序,再固定一个数,用两指针方法求另外两个数之和与当前固定数之和,得出最接近的。

 1 public class Solution {
 2     public int threeSumClosest(int[] num, int target) {
 3         int result = num[0] + num[1] + num[num.length - 1];
 4         Arrays.sort(num);
 5         for (int i = 0; i < num.length - 2; i++) {
 6             int start = i + 1, end = num.length - 1;
 7             while (start < end) {
 8                 int sum = num[i] + num[start] + num[end];
 9                 if (sum > target) {
10                     end--;
11                 } else {
12                     start++;
13                 }
14                 if (Math.abs(sum - target) < Math.abs(result - target)) {
15                     result = sum;
16                 }
17             }
18         }
19         return result;
20     }
21 }
View Code

 

leetcode 15. 3Sum

题意:三个数之和为零

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]
View Code

思路:先将数组排序,而后遍历数组,每次固定一个数,将3sum转化为2sum,a + b + C = 0,也就是a + b = -C。每次固定c的时候看c以后的两个数字之和是否等于-c,不用再往回找,由于往回找是重复的。时间复杂度O(n^2).还要注意去除重复的结果。

 1 public class Solution {
 2     public List<List<Integer>> threeSum(int[] nums) {
 3         if (nums == null || nums.length == 0) {
 4             return new ArrayList<List<Integer>>();
 5         }
 6         Arrays.sort(nums);
 7         List<List<Integer>> ans = new ArrayList<>();
 8         List<Integer> triple;
 9         for (int i = 0; i < nums.length - 2; i++) {
10             if (i == 0 || (i != 0 && nums[i] != nums[i - 1])) {
11                 int left = i + 1;
12                 int right = nums.length - 1;
13                 int sum = 0 - nums[i];
14                 while (left < right) {
15                     if (nums[left] + nums[right] == sum) {
16                         triple = new ArrayList<>();
17                         triple.add(nums[i]);
18                         triple.add(nums[left]);
19                         triple.add(nums[right]);
20                         ans.add(triple);
21                         while (left < right && nums[left] == nums[left + 1]) {
22                             left++;
23                         }
24                         while(left < right && nums[right] == nums[right - 1]) {
25                             right--;
26                         }
27                         left++;
28                         right--;
29                     } else if (nums[left] + nums[right] < sum) {
30                         left++;
31                     } else {
32                         right--;
33                     }
34                 }
35             }
36         }
37         return ans;
38     }
39 }
View Code

 

leetcode 1 Two Sum  

题意:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
UPDATE (2016/2/13):
The return format had been changed to zero-based indices. Please read the above updated description carefully.
View Code

解法:这是未排序的数组,若是先排序再求解则速度太慢。技巧是用hashMap保存遍历过的数值和索引,每次去hashmap中查找是否存在target-nums[i]的数值。

         时间复杂度O(n),空间复杂度O(n)

 1 public class Solution {
 2     public int[] twoSum(int[] nums, int target) {
 3         int[] ans = new int[2];
 4         if (nums == null) {
 5             return ans;
 6         }
 7         int len = nums.length;
 8         Map<Integer, Integer> map = new HashMap<>();
 9         for (int i = 0; i < len; i++) {
10             if (map.containsKey(target - nums[i])) {
11                 int index = map.get(target - nums[i]);
12                 ans[0] = Math.min(index, i);
13                 ans[1] = Math.max(index, i);
14                 return ans;
15             } else {
16                 map.put(nums[i], i);
17             }
18         }
19         return ans;
20     }
21 }
View Code

2. 仍是忘了怎么作,记住这个作法 2016/12/04

leetcode 167. Two Sum II - Input array is sorted

题意:

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
View Code

解法:俩指针初始分别指向头和尾。俩数和大于target左指针右移,俩数和小于target,右指针左移。

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] ans = new int[2]; 
        if (numbers == null) {
            return ans;
        }
        int len = numbers.length;
        int left = 0;
        int right = len - 1;
        while (left < right) {
            int add = numbers[left] + numbers[right];
            if (add == target) {
                ans[0] = left + 1;
                ans[1] = right + 1;
                return ans;
            } else if (add < target) {
                left++;
            } else {
                right--;
            }
        }
        return ans;
    }
}
View Code

 leetcode 173 Binary Search Tree Iterator

题意:

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
View Code

解法:其实就是二叉树的中序遍历的非递归形式。其中hasNext()对应着非递归形式中最外层while循环。next()对应着里面的入栈出栈操做。

   这里的时间复杂度是值的平均时间复杂度。调用n次next()是O(n)的时间,因此每次是O(1),空间复杂度也就是栈是O(h)

 1 /**
 2  * Definition for binary tree
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 
11 public class BSTIterator {
12     TreeNode cur = null;
13     Stack<TreeNode> stack = new Stack<>();;
14     public BSTIterator(TreeNode root) {
15         cur = root;
16     }
17 
18     /** @return whether we have a next smallest number */
19     public boolean hasNext() {
20         if (!stack.isEmpty() || cur != null) {
21             return true;
22         }
23         return false;
24     }
25 
26     /** @return the next smallest number */
27     public int next() {
28         while (cur!= null) {
29             stack.push(cur);
30             cur = cur.left;
31         }
32         TreeNode next = stack.pop();
33         cur = next.right;
34         return next.val;
35     }
36 }
37 
38 /**
39  * Your BSTIterator will be called like this:
40  * BSTIterator i = new BSTIterator(root);
41  * while (i.hasNext()) v[f()] = i.next();
42  */
View Code

2.lintcode 上作过一遍,此次又忘了。2016/12/04 

leetcode 179. Largest Number

题意:

1 Given a list of non negative integers, arrange them such that they form the largest number.
2 
3 For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.
4 
5 Note: The result may be very large, so you need to return a string instead of an integer.
View Code

解法:自定义比较器。先将整数转化为字符串,再用字符串来实现比较器。比较两个字符串的和的字典序。

 1 public class Solution {
 2     public class MyComparator implements Comparator<String> {
 3         public int compare(String a, String b) {
 4             return (b + a).compareTo(a + b);
 5         }           
 6     }
 7     public String largestNumber(int[] nums) {
 8         StringBuilder ans = new StringBuilder();
 9         if (nums == null || nums.length == 0) {
10             return ans.toString();
11         }
12         int len = nums.length;
13         String[] strs = new String[len];
14         for (int i = 0; i < len; i++) {
15             strs[i] = String.valueOf(nums[i]);
16         }
17         Arrays.sort(strs, new MyComparator());
18         for (int i = 0; i < len; i++) {
19             ans.append(strs[i]);
20         }
21         int start = 0;
22         while (start < ans.length() && ans.charAt(start) == '0') {
23             start++;
24         }
25         if (start == ans.length()) {
26             return "0";
27         }
28         return ans.substring(start);
29     }
30 
31 }
View Code

1.比较器的写法;防止0的出现 2016/12/04 

leetcode 187. Repeated DNA Sequences

题意:

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].
View Code

解法:

1.普通解法:利用两个hashset  a和b a用于记录,b用于产生结果。从第十位字符开始向后遍历整个字符串,判断长度为10的字符串是否在a出现过,没有则加入hashset  a,有的话则加入结果hashset b。

结果集必定要用hashset,不能用链表,用链表会出现重复。

 1 public class Solution {
 2     public List<String> findRepeatedDnaSequences(String s) {
 3         List<String> ans = new ArrayList<>();
 4         if (s == null) {
 5             return ans;
 6         }
 7         HashSet<String> dnas = new HashSet<>();
 8         for (int i = 9; i < s.length(); i++) {
 9             String sub = s.substring(i - 9, i + 1);
10             if (dnas.contains(sub) && !ans.contains(sub)) {
11                 ans.add(sub);
12             } else {
13                 dnas.add(sub);
14             }
15         }
16         return ans;
17     }
18 }
View Code

2.优化解法结合hashset和bit manipulation 。

00,01,10,11分别表明'A','C','G','T',能够用20个bit位来表明长度为10的子字符串。至关于将字符串从新编码了。能够减小substring的调用次数,加快效率。

 1 public class Solution {
 2     public List<String> findRepeatedDnaSequences(String s) {
 3         int len = s.length();
 4         if (len < 11) {
 5             return new ArrayList<String>();
 6         }
 7         //00,01,10,11分别表明'A','C','G','T',能够用20个bit位来表明长度为10的子字符串
 8         int[] bit = new int[20];
 9         bit['C' - 'A'] = 1;
10         bit['G' - 'A'] = 2;
11         bit['T' - 'A'] = 3;
12         int cur = 0;
13         int mask = 0x000fffff;
14         HashSet<String> ans = new HashSet<>();
15         HashSet<Integer> nums = new HashSet<>();
16         for (int i = 0; i < len; i++) {
17             cur <<= 2;
18             cur |= bit[s.charAt(i) - 'A'];
19             if (i < 9) {
20                 continue;
21             }
22             //只保留后20位,前12位清零
23             cur &= mask;
24             if (!nums.add(cur)) {
25                 ans.add(s.substring(i - 9, i + 1));
26             } 
27         }
28         
29         return new ArrayList<>(ans);
30     }
31 }
View Code

1. 没有想到优化的方法。 2016/12/05

199. Binary Tree Right Side View

题意:

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,
   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---
You should return [1, 3, 4].
View Code

解法:分层遍历,每次取最右边的那个节点

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public List<Integer> rightSideView(TreeNode root) {
12         if (root == null) {
13             return new ArrayList<Integer>();
14         }
15         List<Integer> ans = new ArrayList<Integer>();
16         Queue<TreeNode> qu= new LinkedList<>();
17         qu.offer(root);
18         while (!qu.isEmpty()) {
19             int size = qu.size();
20             for (int i = 0; i < size; i++) {
21                 TreeNode cur = qu.poll();
22                 if (i == size - 1) {
23                     ans.add(cur.val);
24                 }
25                 if (cur.left != null) {
26                     qu.offer(cur.left);
27                 }
28                 if (cur.right != null) {
29                     qu.offer(cur.right);
30                 }
31             }
32         }
33         return ans;
34     }
35 }
View Code

1.bug-free 2016/12/05

 leetcode 448 Find All Numbers Disappeared in an Array

题意:

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]
View Code

解法:将出现过的位置变为负的

1.遍历数组,当前元素为n,则nums[Math.abs(n) - 1] = - Math.abs(nums[Math.abs(n) - 1]);

2.再次遍历,将不为负数的位置加入list中

 1 public class Solution {
 2     public List<Integer> findDisappearedNumbers(int[] nums) {
 3         if (nums == null || nums.length == 0) {
 4             return new ArrayList<Integer>();
 5         }
 6         int len = nums.length;
 7         for (int i = 0; i < len; i++) {
 8             int index = Math.abs(nums[i]) - 1;
 9             nums[index] = -Math.abs(nums[index]);
10         }
11         List<Integer> ans = new ArrayList<Integer>();
12         for (int i = 0; i < len; i++) {
13             if (nums[i] > 0) {
14                 ans.add(i + 1);
15             }
16         }
17         return ans;
18     }
19 }
View Code

1.第一次作没有想出O(n)/O(1)的解法 2016/12/06

leetcode 201. Bitwise AND of Numbers Range

题意:

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.
View Code

解法:仔细观察能够发现规律,最后的结果是全部数字的最左边的共同部分

好比来看一个范围[26, 30],它们的二进制以下:

11010  11011  11100  11101  11110

左边的共同部分是11,因此最后结果是11000

因此先将m和n向右移,直到m和n相等,假设右移了i位,则最后结果为m<<i.

1.非递归的解法

 1 public class Solution {
 2     public int rangeBitwiseAnd(int m, int n) {
 3         int shift = 0;
 4         while (m != n) {
 5             m >>= 1;
 6             n >>= 1;
 7             shift++;
 8         }
 9         return m << shift;
10     }
11 }
View Code

2.递归解法

1 public class Solution {
2     public int rangeBitwiseAnd(int m, int n) {
3         if (m == n) {
4             return n;
5         }
6         return rangeBitwiseAnd(m / 2, n / 2) << 1;
7     }
8 }
View Code

1.没有想出最好的解法 2016/12/06

lintcode 127 Topological Sorting

题意:

Given an directed graph, a topological order of the graph nodes is defined as follow:

  • For each directed edge A -> B in graph, A must before B in the order list.
  • The first node in the order can be any node in the graph with no nodes direct to it.

Find any topological order for the given graph.

 Notice

You can assume that there is at least one topological order in the graph.

Example

For graph as follow:

picture

The topological order can be:

[0, 1, 2, 3, 4, 5]
[0, 2, 3, 1, 5, 4]

解法:为每一个节点增长入度这一参数,使用hashmap创建映射关系
首先遍历全部节点,将其邻居的入度加一 ,当某一个节点加入拓扑排序后,将其全部邻居的入度减一
有向图是没法从一个节点找到全部节点的,因此这里给出的参数是节点的列表,无向图只要是连通的就能够由一个节点找到全部节点
 1 /**
 2  * Definition for Directed graph.
 3  * class DirectedGraphNode {
 4  *     int label;
 5  *     ArrayList<DirectedGraphNode> neighbors;
 6  *     DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
 7  * };
 8  */
 9 public class Solution {
10     /**
11      * @param graph: A list of Directed graph node
12      * @return: Any topological order for the given graph.
13      */    
14     public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
15         // write your code here
16         ArrayList<DirectedGraphNode> answer = new ArrayList<>();
17         if (graph == null || graph.size() == 0) {
18             return answer;
19         }
20         
21         HashMap<DirectedGraphNode, Integer> inDegreeMap = new HashMap<>();
22         
23         for (DirectedGraphNode node : graph) {
24             for (DirectedGraphNode neighbor : node.neighbors) {
25                 if (inDegreeMap.containsKey(neighbor)) {
26                     inDegreeMap.put(neighbor, inDegreeMap.get(neighbor) + 1);
27                 } else {
28                     inDegreeMap.put(neighbor, 1);
29                 }
30             }
31         }
32         
33         Queue<DirectedGraphNode> queue = new LinkedList<>();
34         for (DirectedGraphNode node : graph) {
35             if (!inDegreeMap.containsKey(node)) {
36                 answer.add(node);
37                 queue.offer(node);
38             }
39         }
40         
41         while (!queue.isEmpty()) {
42             DirectedGraphNode node = queue.poll();
43             for (DirectedGraphNode neighbor : node.neighbors) {
44                 inDegreeMap.put(neighbor, inDegreeMap.get(neighbor) - 1);
45                 if (inDegreeMap.get(neighbor) == 0) {
46                     answer.add(neighbor);
47                     queue.offer(neighbor);
48                 }
49             }
50         }
51         
52         return answer;
53     }
54 }
View Code
leetcode 207. Course Schedule

题意:

 1 There are a total of n courses you have to take, labeled from 0 to n - 1.
 2 
 3 Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
 4 
 5 Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
 6 
 7 For example:
 8 
 9 2, [[1,0]]
10 There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
11 
12 2, [[1,0],[0,1]]
13 There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
14 
15 Note:
16 The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
17 
18 click to show more hints.
19 
20 Hints:
21 This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
22 Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
23 Topological sort could also be done via BFS.
View Code

解法:能够根据上一题lintcode 127 Topological Sorting来求解,只不过要在拓扑排序以后判断图中是否存在环,若存在环,则返回false,反之返回true。

回顾一下图的三种表示方式:边表示法(即题目中表示方法),邻接表法,邻接矩阵。咱们要用邻接表来表示图,来实现拓扑排序,找出最后是否存在入度不为0的节点,若存在则有环。

 1 public class Solution {
 2     public boolean canFinish(int numCourses, int[][] prerequisites) {
 3         if (prerequisites == null || prerequisites.length == 0) {
 4             return true;
 5         }
 6         int m = prerequisites.length;
 7         int[] inDegree = new int[numCourses];
 8         //构建邻接表adjacency lists表示图
 9         List<List<Integer>> graph = new ArrayList<>();
10         for (int i = 0; i < numCourses; i++) {
11             graph.add(new ArrayList<Integer>());
12         }
13         for (int i = 0; i < m; i++) {
14             graph.get(prerequisites[i][0]).add(prerequisites[i][1]);
15         }
16         //入度加一
17         for (int i = 0; i < m; i++) {
18             inDegree[prerequisites[i][1]]++;
19         }
20         Queue<Integer> qu = new LinkedList<>();
21         for (int i = 0; i < numCourses; i++) {
22             if (inDegree[i] == 0) {
23                 qu.offer(i);
24             }
25         }
26         while (!qu.isEmpty()) {
27