刷题备忘录，for bug-free
招行面试题--求无序数组最长连续序列的长度，这里连续指的是值连续--间隔为1，并不是数值的位置连续
问题：
给出一个未排序的整数数组，找出最长的连续元素序列的长度。 如： 给出[100, 4, 200, 1, 3, 2]， 最长的连续元素序列是[1, 2, 3, 4]。返回它的长度：4。 你的算法必须有O(n)的时间复杂度 。
解法：
初始思路
要找连续的元素，第一反应一般是先把数组排序。但悲剧的是题目中明确要求了O(n)的时间复杂度，要做一次排序，是不能达到的。不过我们还是先来看看排序的方案要怎么实现。 简单来说，排序后我们只要遍历数组，检查当前值减1是否等于上一个值，如果等，增加当前连续序列的计数；如果不等，将当前计数与当前最大值比较，如果更优替换最大值， 并重置计数为1。具体到细节上，我们还要考虑几个问题： - 第一个数 处理第一个数时是没有上一个值的。有人可能觉得可以给存储上一个值的变量赋一个特别的初始值来表示处理的是第一个数。但是由于数组内元素的取值范围是所有的整数，不可能找出一个特别的值。所以代码中需要对第一个数做特殊的判断 - 重复的数 数组中可能会有重复的数，所以我们不能光判断当前值减1等于或不等于上一个值。还需要加上一个等不等与上一个值的判断，如果等，说明是一个重复的数字，直接不做任何处理跳到数组中的下一个数。 - 最后一组连续序列 由于我们只在遍历中发现当前值减1不等于上一个值时才尝试更新序列长度最大值。如果有一个连续序列一直持续到数组中的最后一个元素，这个序列的长度是没有得到处理的。因此我们需要在遍历完数组后再尝试更新依稀最大值。 加入了这些细节考虑后，代码就呼之欲出了： class SolutionSort
{
public:
int longestConsecutive(std::vector<int> &num)
{
std::sort(num.begin(), num.end()); int maxLen = ;
int currentLen = ;
int previous = ; for(auto iter = num.begin(); iter != num.end(); ++iter)
{
if(iter == num.begin())//第一个数的特殊情况
{
++currentLen;
}
else
{
if(*iter == previous)//重复数的情况
{
continue;
}
else if(*iter - == previous)
{
++currentLen;
}
else
{
if(currentLen > maxLen)
{
maxLen = currentLen;
}
currentLen = ;
}
}
previous = *iter;
} //有一个连续序列持续到数组最后一个元素的情况
if(currentLen > maxLen)
{
maxLen = currentLen;
} return maxLen;
}
}; 使用排序的代码
提交后发现其实是可以通过Judge Small和Judge Large的。但是这种方案始终不符合题目要求。 优化
要实现O(n)的时间复杂度，就不能对数组排序。其实我们大脑在判断这个问题时就是不排序的。让我们来模拟一下： 你看到[, , , , , ]这个数组，首先你会看99或者101在不在这个数组里，发现数组没这两个数，那么100组成的连续序列长度仅为1。接着会看5或者3在不在数组里，会发现3存在，5不存在；紧接着会看2在不在....直到发现0不在。从而得到4组成的最长序列为4。 总结一下会发现，我们在判断某个数的连续序列时，会分别往减小和增大的方向找下一个连续数在不在数组中。然后把两个方向的长度加起来即为包含该数的一个连续序列。需要注意的是，当前数的长度计数只需要出现在一个方向的查找中计算即可，否则就重复了。要找一个数是不是在数组中，不可能用遍历的方法实现，这样时间复杂度就超过O(n)了。而要降低时间复杂度，一个经典的方案就是空间换时间。用增加空间复杂度的方法来换取时间复杂度的降低。所以我们可以先对数组进行一次预处理，生成一份包含数组元素的哈希表。这样在求解某个数字在不在数组时就可以得到O()的时间复杂度。 那么我们可以得到如下伪代码： 找连续序列函数(要找序列的值，方向) 循环直到要找的值不在哈希表中 序列长度+ 如果增加方向，要找的序列值+ 如果减少方向，要找的序列值- 循环结束 返回序列长度 找连续序列函数结束 求解函数(数组) 遍历数组生成哈希表 遍历数组 序列长度1 = 找连续序列函数(当前值，增加方向) 序列长度2 = 找连续序列函数(当前值 - ，减少方向) 如果序列长度1 + 序列长度2 > 当前最长序列，更新最长序列 遍历结束 求解函数结束 这个方案的时间复杂度应该是O(n) + O(n) * O() * O(平均序列长度)。如果平均序列长度等于n，如数组[,,,]，复杂度就是O(n^)了。看来还不可行，主要的时间复杂度都浪费在找连续序列上了。怎么能减少找连续序列的时间复杂度？经过观察我们可以发现，4的最长序列和3，，1的最长序列其实是一样的。找过了4之后其实后面这3个数都不用找了。而我们控制是否查找一个数的连续序列是通过判断数字是否在哈希表中来实现的，也就是说，如果我们可以在找出一个数字在连续序列中后就将其移除，就可以避免以后再触发查找的循环。通过这个优化，时间复杂度将变为O(n) + O(n) + O(序列长度总和)，可以认为是O(n)了。最后得出代码如下： classSolution
{
public:
int longestConsecutive(std::vector<int> &num)
{
for(int i = ; i < num.size(); ++i)
{
flags_.insert(num[i]);
} int maxLen = ; for(int i = ; i < num.size(); ++i)
{
int ascendingMax = FindConsecutiveNumbers(ASCENDING, num[i]);
int decendingMax = FindConsecutiveNumbers(DECENDING, num[i] - ); if(ascendingMax + decendingMax > maxLen)
{
maxLen = ascendingMax + decendingMax;
}
} return maxLen;
} private:
enum OrderBy
{
ASCENDING,
DECENDING
}; int FindConsecutiveNumbers(OrderBy orderBy, int value)
{
int maxLen = ; while(flags_.find(value) != flags_.end())
{
++maxLen; flags_.erase(value); if(orderBy == ASCENDING)
{
++value;
}
else
{
--value;
}
} return maxLen;
} std::unordered_set<int> flags_;
};
和最大连续子数组--有正数和负数
public class Solution {
/**
* @param A an integer array
* @return A list of integers includes the index of the first number and the index of the last number
*/
public ArrayList<Integer> continuousSubarraySum(int[] A) {
// Write your code here
if (A == null || A.length == 0){
return new ArrayList<Integer>();
}
int sum = A[0];
int max = sum;
int start = 0;
int end = 0;
int ans_s = start;
int ans_e = end;
ArrayList<Integer> ans = new ArrayList<Integer>();
for (int i = 1; i < A.length; i++) {
if (sum < 0) {
sum = A[i];
start = end = i;
} else {
sum += A[i];
end = i;
}
if (sum > max) {
max = sum;
ans_s = start;
ans_e = end;
}
}
ans.add(ans_s);
ans.add(ans_e);
return ans;
}
}
leetcode 5. Longest Palindromic Substring
最长回文子串：动态规划
public class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() == 0) {
return new String("");
}
int n = s.length();
int maxLen = 1;
String ans = "";
//p[i][j]表示第i个字符到第j个字符是否为回文串
boolean[][] p = new boolean[n][n];
for (int i = 0; i < n; i++) {
p[i][i] = true;
ans = s.substring(i, i + 1);
}
for (int i = 0; i < n - 1; i++) {
if (s.charAt(i) == s.charAt(i + 1)) {
p[i][i + 1] = true;
maxLen = 2;
ans = s.substring(i, i + 2);
}
}
for (int len = 2; len < n; len++) {
for (int i = 0; i < n - len; i++) {
if (s.charAt(i + len) == s.charAt(i)) {
p[i][i + len] = p[i + 1][i + len - 1];
if (p[i][i + len]) {
if (len + 1 > maxLen) {
maxLen = len + 1;
ans = s.substring(i, i + len + 1);
if (maxLen == n) {
return ans;
}
}
}
}
}
}
return ans;
}
}
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
解法：
算法的基本思想是对于给定的序列，从后往前找出现后一个数比前一个数大的位置，
假设此处较大数位置为b，较小数位置为a，然后再从b开始往后找最后一个大于nums[a]的数，必然能找到一个位置为c的数，交换nums[c]和nums[a]，并且反转nums[a+1]~nums[length-1]
可以发现再找位置c的时候可以使用二分法来提高效率，因为位置b往后是一个有序序列，并且是倒序的，即是在一个有序序列中找到最后一个大于某个数的数
为什么要反转，因为交换过后的b位置开始就是一个倒序的有序序列，反转过后就变成了正序的有序序列，保证字典序最小
其实这种解法可以用来解决全排列的非递归形式，只需初始化第一个排列，然后while循环这个算法就可以了。因为当n很大时，递归层数太大。--百度的面试题，n个数全排列非递归
代码
public class Solution {
public void nextPermutation(int[] nums) {
if (nums == null || nums.length <= 1) {
return;
}
int len = nums.length;
for (int i = len - 1; i > 0; i--) {
if (nums[i] > nums[i - 1]) {
int lastBigger = getLastBigger(nums, i, nums[i - 1]);
swap(nums, i - 1, lastBigger);
reverse(nums, i);
return;
}
}
reverse(nums, 0);
}
//在倒序的子数组中二分法查找最后一个大于target的数
public int getLastBigger(int[] nums, int start, int target) {
int end = nums.length - 1;
int index = start;
while (start <= end) {
int mid = start + (end - start) / 2;
if (nums[mid] > target) {
index = mid;
start = mid + 1;
} else {
end = mid - 1;
}
}
return index;
}
//反转数组，从start位置开始
public void reverse(int[] nums,int start) {
int end = nums.length - 1;
for (int i = 0; i < (end - start + 1) / 2; i++) {
int tmp = nums[start + i];
nums[start + i] = nums[end - i];
nums[end - i] = tmp;
}
}
public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
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看是否 合适，如果合适就继续下一次的递归循环，直到所有的空格子都被填满了数字。
class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
slove(board);
}
bool slove(vector<vector<char>>& board)
{
for (int i = ; i < board.size(); i++)
{
for (int j = ; j < board[].size(); j++)
{
if (board[i][j] == '.')
{
for (char c = ''; c <= ''; c++)
{
if (isValid(board, i, j, c))
{
board[i][j] = c;
if (slove(board))
{
return true;
}
else
{
board[i][j] = '.';
}
}
}
return false;
}
}
}
return true;
}
bool isValid(vector<vector<char>>& board, int row, int col, char c) {
for (int i = ; i < board.size(); i++)
{
if (board[i][col] != '.' && board[i][col] == c) return false;
if (board[row][i] != '.' && board[row][i] == c) return false;
if (board[ * (row / ) + i / ][ * (col / ) + i % ] != '.' &&
board[ * (row / ) + i / ][ * (col / ) + i % ] == c) return false;
}
return true;
}
};
最长公共字符串
题意：返回两个字符串的最长公共子串的长度
解法：dp，详见代码注释。
public class Solution {
/**
* @param A, B: Two string.
* @return: the length of the longest common substring.
*/
//dp time O(mn)
public int longestCommonSubstring(String A, String B) {
// write your code here
if (A == null || B == null || A.length() == 0 || B.length() == 0) {
return 0;
}
int n = A.length();
int m = B.length();
//dp[i][j]表示当前A的第i个字符和B的第j个字符往前能构成的最长连续公共子串的长度
int[][] dp = new int[n + 1][m + 1];
int max = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (A.charAt(i - 1) == B.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
max = Math.max(max, dp[i][j]);
}
}
}
return max;
}
}
最长公共子序列
题意：返回两个字符串的最长公共子序列的长度
解法：dp，详见代码注释。
public class Solution {
/**
* @param A, B: Two strings.
* @return: The length of longest common subsequence of A and B.
*/
public int longestCommonSubsequence(String A, String B) {
// write your code here
if (A == null || B == null || A.length() == 0 || B.length() == 0) {
return 0;
}
int n = A.length();
int m = B.length();
//state : dp[i][j]表示A的前i个字符与B的前j个字符的最长公共子序列的长度
int[][] dp = new int[n + 1][m + 1];
//initialize
//function : dp[i][j] = dp[i - 1][j - 1] + 1 when A.charAt(i - 1) == B.charAt(j - 1)
// else dp[i][j] = Math.max(dp[i - 1][j - 1],Math.max(dp[i - 1][j], dp[i][j - 1]));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m;j++) {
if (A.charAt(i - 1) == B.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
//answer
return dp[n][m];
}
}
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.
解法：把问题转化为层序遍历或者说是bfs。初始位置是第一层，由初始位置可到达的所有位置构成第二层，由第二层所有位置可到达的所有位置构成第三层，假设最后一个位置在第n层，则需要的步数即为n-1.详细解释见代码中的注释。
public class Solution {
public int jump(int[] nums) {
if (nums == null || nums.length <= 1) {
return 0;
}
int level = 0; //当前层
int levelStart = 0; //每一层的开始位置索引值
int levelEnd = 0; //每一层的结束位置索引值
while (levelEnd - levelStart + 1 > 0) {
int nextLevelEnd = 0;
level++;
for (;levelStart <= levelEnd; levelStart++) { //遍历这一层的所有位置找到最远可到的位置，即为下一层的结束位置
nextLevelEnd = Math.max(nextLevelEnd, levelStart + nums[levelStart]);
if (nextLevelEnd >= nums.length - 1) { //下一层的结束位置超过了数组的最后一位，则返回当前的层数
return level;
}
}
levelEnd = nextLevelEnd;
}
return 0;
}
}
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.
解法：记录一个全局的最远可到达位置，遍历数组，如果当前最远位置小于数组索引，说明到不了当前位置，可以返回false。反之用由此位置可以到达的最远位置更新全局的最远位置。最后遍历到最后一个位置仍可以到达则返回true。
public class Solution {
public boolean canJump(int[] nums) {
if (nums == null || nums.length == 0) {
return false;
}
int farest = 0;
for (int i = 0; i < nums.length; i++) {
if (farest < i) {
return false;
}
if (i + nums[i] > farest) {
farest = i + nums[i];
}
}
return true;
}
}
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.
解法：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的取值范围，防止索引值越界。记录一个最大值，返回这个最大值即可。
public class Solution {
public int longestValidParentheses(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int[] dp = new int[s.length()];
int max = 0;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == '(') {
dp[i] = 0;
} else {
if (s.charAt(i - 1) == '(') {
dp[i] = i > 1 ? dp[i - 2] + 2 : 2;
} else if (i > dp[i - 1] && s.charAt(i - dp[i - 1] - 1) == '(') {
dp[i] = i > dp[i - 1] + 1 ? dp[i - 1] + 2 + dp[i - dp[i - 1] - 2] : dp[i - 1] + 2;
}
}
max = Math.max(max, dp[i]);
}
return max;
}
}
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.
解法：主要思路是将相应位置的值变为其索引值加一，如果不是的话，就交换。当nums[i] <= 0或者nums[i]>nums.length就不做交换了
空数组返回1，没找到的话就返回nums.length + 1
public class Solution {
public int firstMissingPositive(int[] nums) {
if (nums == null || nums.length == 0) {
return 1;
}
for (int i = 0; i < nums.length; i++) {
//如果nums[i] == nums[nums[i] - 1]，则不做交换，避免死循环 而不用 nums[i] != i + 1
while (nums[i] > 0 && nums[i] <= nums.length && nums[i] != nums[nums[i] - 1]) {
int temp = nums[i];
nums[i] = nums[nums[i] - 1];
nums[temp - 1] = temp;
//nums[nums[i] - 1] = temp;这是错误的，因为nums[i]更新过了
}
}
for (int i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return nums.length + 1;
}
}
leetcode 7 Reverse Integer--微软面试题
题意：反转一个整数，返回整数，如果溢出返回0。
解法：注意溢出情况，先把结果用long来表示，看结果是否超过了整数的边界。注意不用区分正负数。
public class Solution {
public int reverse(int x) {
long ans = 0;
while (x != 0) {
ans = ans * 10 + x % 10;
x = x / 10;
if (ans > Integer.MAX_VALUE || ans < Integer.MIN_VALUE) {
return 0;
}
}
return (int)ans;
}
}
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.
解法：分治+递归。保存一个全局的最小值和最小值对应的子树的根节点。
/**
* 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;
}
}
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
解法：分治法，类似于前序遍历的递归。先flatten左子树，再将当前根节点flatten，这时先将当前节点的右节点保存，再将当前节点的左子树设为右节点，在循环遍历到左子树的最后一个节点，将保存的右节点连上去，再flatten右子树。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public void flatten(TreeNode root) {
if (root == null) {
return;
} flatten(root.left); TreeNode right = root.right;
root.right = root.left;
root.left = null;
while (root.right != null) {
root = root.right;
}
root.right = right;
if (root.right != null) {
flatten(root.right);
}
}
}
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].
解法：先将间隔按照开始端点排序，再依次遍历，如果前一个的结束端点大于后一个开始端点并且小于后一个结束端点，则这两个重合。
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
public class Solution {
public List<Interval> merge(List<Interval> intervals) {
List<Interval> ans = new ArrayList<>();
if (intervals == null || intervals.size() == 0) {
return ans;
}
Collections.sort(intervals, new MyComparator());
ans.add(new Interval(intervals.get(0).start, intervals.get(0).end));
int preStart = intervals.get(0).start;
int preEnd = intervals.get(0).end;
for (int i = 1; i < intervals.size(); i++) {
int start = intervals.get(i).start;
int end = intervals.get(i).end;
if (preEnd >= start && preEnd < end) {
ans.remove(ans.size() - 1);
ans.add(new Interval(preStart, end));
preEnd = end;
} else if (preEnd < start) {
ans.add(new Interval(start, end));
preEnd = end;
preStart = start;
}
}
return ans;
}
public class MyComparator implements Comparator<Interval> {
public int compare(Interval in1, Interval in2) {
return in1.start - in2.start;
}
}
}
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
解法：有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
代码：注意初始化
public class Solution {
public boolean isMatch(String s, String p) {
if (s == null && p == null) {
return true;
}
if (s == null || p == null) {
return false;
}
int m = s.length();
int n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
//形如“a*b*c*”的形式dp[0][i] = true
for (int i = 0; i < n; i++) {
if (p.charAt(i) == '*' && dp[0][i - 1]) {
dp[0][i + 1] = true;
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (p.charAt(j) == '.' || p.charAt(j) == s.charAt(i)) {
dp[i + 1][j + 1] = dp[i][j];
}
if (p.charAt(j) == '*') {
if (p.charAt(j - 1) != s.charAt(i) && p.charAt(j - 1) != '.') {
dp[i + 1][j + 1] = dp[i + 1][j - 1];
} else {
dp[i + 1][j + 1] = dp[i + 1][j - 1] || dp[i + 1][j] || dp[i][j + 1];
}
}
}
}
return dp[m][n];
}
}
leetcode 138. Copy List with Random Pointer
题意：深度拷贝带有随机指针的链表
解法：用到hashmap，将新建节点与原节点映射
/**
* Definition for singly-linked list with a random pointer.
* class RandomListNode {
* int label;
* RandomListNode next, random;
* RandomListNode(int x) { this.label = x; }
* };
*/
public class Solution {
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null) {
return null;
}
Map<RandomListNode, RandomListNode> map = new HashMap<>();
RandomListNode cur = head;
while (cur != null) {
RandomListNode newNode = new RandomListNode(cur.label);
map.put(cur, newNode);
cur = cur.next;
}
cur = head;
while (cur != null) {
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
return map.get(head);
}
}
leetcode 8. String to Integer (atoi)--微软面试题
题意：将字符串转化为数字
解法：
主要注意的case：1.正负号；2.字符串前面开头有空格，过滤掉；3.遇到数字之后再遇到其他字符，直接返回当前结果；4.溢出情况，正数溢出返回最大整数，负数溢出返回最小整数。
public class Solution {
public int myAtoi(String str) {
if (str == null || str.length() == 0) {
return 0;
}
int num = 0;
int start = 0;
boolean minus = false;
while (start < str.length() && str.charAt(start) == ' ') {
start++;
}
if (start < str.length() && str.charAt(start) == '+') {
start++;
} else if (start < str.length() && str.charAt(start) == '-') {
start++;
minus = true;
}
for (int i = start; i < str.length(); i++) {
if ('0' <= str.charAt(i) && str.charAt(i) <= '9') {
if (Integer.MAX_VALUE / 10 < num || (Integer.MAX_VALUE / 10 == num && Integer.MAX_VALUE % 10 < str.charAt(i) - '0')) {
return minus ? Integer.MIN_VALUE : Integer.MAX_VALUE;
}
num = num * 10 + str.charAt(i) - '0';
} else {
return minus ? -num : num;
}
}
return minus ? -num : num;
}
}
0-1背包问题--腾讯面试题
给出n个物品的体积A[i]和其价值V[i]，将他们装入一个大小为m的背包，最多能装入的总价值有多大？
1.二维数组的做法
public class Solution {
/**
* @param m: An integer m denotes the size of a backpack
* @param A & V: Given n items with size A[i] and value V[i]
* @return: The maximum value
*/
public int backPackII(int m, int[] A, int V[]) {
// write your code here
if (A == null || A.length == 0 || V == null || V.length == 0) {
return 0;
}
int n = A.length;
int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (j >= A[i - 1]) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - A[i - 1]] + V[i - 1]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][m];
}
}
2.一维数组的做法
public class Solution {
/**
* @param m: An integer m denotes the size of a backpack
* @param A & V: Given n items with size A[i] and value V[i]
* @return: The maximum value
*/
public int backPackII(int m, int[] A, int V[]) {
// write your code here
if (A == null || A.length == 0 || V == null || V.length == 0) {
return 0;
}
int n = A.length;
int[] dp = new int[m + 1];
for (int i = 1; i <= n; i++) {
for (int j = m; j >= A[i - 1]; j--) {
dp[j] = Math.max(dp[j], dp[j - A[i - 1]] + V[i - 1]);
}
}
return dp[m];
}
}
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
解法：
理解并熟记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类似，理解并熟记
代码：
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1 == null || nums2 == null) {
return 0.0;
}
int m = nums1.length;
int n = nums2.length;
if (((m + n) & 1 ) == 0) {
return (findKthSmallestEle(nums1, nums2, 0, 0, (m + n) / 2) +
findKthSmallestEle(nums1, nums2, 0, 0, (m + n) / 2 + 1)) / 2.0;
} else {
return findKthSmallestEle(nums1, nums2, 0, 0, (m + n) / 2 + 1) / 1.0;
}
}
public int findKthSmallestEle(int[] nums1, int[] nums2, int start1, int start2, int k) {
if (start1 >= nums1.length) {
return nums2[start2 + k - 1];
}
if (start2 >= nums2.length) {
return nums1[start1 + k - 1];
}
if (k == 1) {
return Math.min(nums1[start1], nums2[start2]);
}
if (nums1.length - start1 < k /2) {
return findKthSmallestEle(nums1, nums2, start1, start2 + k / 2, k - k / 2);
}
if (nums2.length - start2 < k /2) {
return findKthSmallestEle(nums1, nums2, start1 + k / 2, start2, k - k / 2);
}
if (nums1[start1 + k / 2 - 1] <= nums2[start2 + k / 2 - 1]) {
return findKthSmallestEle(nums1, nums2, start1 + k / 2, start2, k - k / 2);
} else {
return findKthSmallestEle(nums1, nums2, start1, start2 + k / 2, k - k / 2);
}
}
}
leetcode 404. Sum of Left Leaves
题意：求所有左叶子节点的值之和，也就是说叶节点必须是左孩子。
Find the sum of all left leaves in a given binary tree.
Example:
3
/ \
9 20
/ \
15 7
There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.
解法：分治递归，在递归到下一个子树时，传入一个boolean参数表示该子树的根节点是不是左子节点，如果发现当前节点是叶子结点并且是左子节点，则返回节点值，否则返回左子树和右子树节点值之和。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) {
return 0;
}
return helper(root.left, true) + helper(root.right, false);
}
public int helper(TreeNode root, boolean isLeft) {
if (root == null) {
return 0;
}
if (isLeft && root.left == null && root.right == null) {
return root.val;
}
return helper(root.left, true) + helper(root.right, false);
}
}
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.
解法：思路与之前做的序列化反序列化二叉树一样，使用前序遍历，不过这次在恢复的时候为了不使用全局变量，增加了一个辅助队列来存储节点值，每遍历到一个节点，就将该节点值从队列中删除，这样就不用保存string 数组的索引值了。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec { // Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) {
return null;
}
StringBuilder ans = new StringBuilder();
helper(root, ans);
return ans.toString().substring(0, ans.length() - 1);
}
public void helper(TreeNode root, StringBuilder ans) {
if (root == null) {
ans.append("#").append(",");
return;
}
ans.append(String.valueOf(root.val)).append(",");
helper(root.left, ans);
helper(root.right, ans);
} // Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == null) {
return null;
}
String[] strs = data.split(",");
Queue<String> qu = new LinkedList<>();
for (String str : strs) {
qu.offer(str);
}
return deHelper(qu);
}
public TreeNode deHelper(Queue<String> data) {
if (data.isEmpty()) {
return null;
}
if (data.peek().equals("#")) {
data.poll();
return null;
}
TreeNode root = new TreeNode(Integer.valueOf(data.poll()));
root.left = deHelper(data);
root.right = deHelper(data);
return root;
}
}
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?
解法：由题意可知会出现两次中序遍历的前一个节点值大于等于后一个节点值得情况，并且第一次出现时被交换的是前一个节点，第二次出现时被交换的是后一个节点，因为大的数被交换到前面，小的数被交换到后面，所以找到这两个节点，再交换他们的值即可。
中序遍历二叉树，并且保存在下一次遍历的时候传入前一个节点，找到第一次不满足前一个节点的值是否小于当前节点值，并且将前一个节点保存为第一个待交换节点，再找到第二次，并且将当前节点保存为第二个待交换节点。交换这两个节点的值。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
TreeNode first = null;
TreeNode second = null;
TreeNode pre = new TreeNode(Integer.MIN_VALUE);
public void recoverTree(TreeNode root) {
if (root == null) {
return;
}
helper(root);
int temp = first.val;
first.val = second.val;
second.val = temp;
}
public void helper(TreeNode root) {
if (root == null) {
return;
}
helper(root.left);
if (first == null && pre.val >= root.val) {
first = pre;
}
if (first != null && pre.val >= root.val) {
second = root;
}
pre = root;
helper(root.right);
}
}
leetcode 117 Populating Next Right Pointers in Each Node
题意：将二叉树每一层的节点连接起来，左边节点的next为右边下一个节点，此题的前提条件是任意二叉树。所以此题的解法是一个通用解法。
解法：类似于116，也是一层一层连接。不过这里要用head和pre来分别表示下一层 的最左边节点和当前连接的前一节点。因为head不一定是上一个节点的左节点。
/**
* Definition for binary tree with next pointer.
* public class TreeLinkNode {
* int val;
* TreeLinkNode left, right, next;
* TreeLinkNode(int x) { val = x; }
* }
*/
public class Solution {
public void connect(TreeLinkNode root) {
if (root == null) {
return;
}
//上一层的当前节点
TreeLinkNode cur = root;
//下一层的前一节点
TreeLinkNode pre = null;
//下一层的最左边节点
TreeLinkNode head = null;
while (cur != null) {
while (cur != null) {
if (cur.left != null) {
if (pre != null) {
pre.next = cur.left;
} else {
head = cur.left;
}
pre = cur.left;
}
if (cur.right != null) {
if (pre != null) {
pre.next = cur.right;
} else {
head = cur.right;
}
pre = cur.right;
}
cur = cur.next;
}
cur = head;
head = null;
pre = null;
}
}
}
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
解法：类似于层序遍历。pre是当前层的最左边子节点，cur是当前层的当前节点。一开始cur = pre，对cur的下一层节点做链接，cur = cur.next.每一层的cur遍历到这一层末尾时，pre= pre.left,pre变为下一层的最左边节点。
/**
* Definition for binary tree with next pointer.
* public class TreeLinkNode {
* int val;
* TreeLinkNode left, right, next;
* TreeLinkNode(int x) { val = x; }
* }
*/
public class Solution {
public void connect(TreeLinkNode root) {
if (root == null) {
return;
}
//pre是当前层的最左边子节点，cur是当前层的当前节点
TreeLinkNode pre = root;
TreeLinkNode cur = null;
while (pre.left != null) {
cur = pre;
while (cur != null) {
cur.left.next = cur.right;
if (cur.next != null) {
cur.right.next = cur.next.left;
}
cur = cur.next;
}
pre = pre.left;
}
}
}
leetcode 124. Binary Tree Maximum Path Sum
题意：二叉树两个节点之间路径的节点的和
Given a binary tree, find the maximum path sum. 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. For example:
Given the below binary tree, 1
/ \
2 3
Return 6.
解法：其实与二叉树两个节点之间的最大距离类似的。要注意的是节点的值可能是负数，但是节点之间的距离是没有负数的。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
if (root == null) {
return 0;
}
helper(root);
return max;
}
public int helper(TreeNode root) {
if (root == null) {
return 0;
}
//左右子树的结果可能是负的，所以要跟零作比较
int left = Math.max(0, helper(root.left));
int right = Math.max(0, helper(root.right));
max = Math.max(left + right + root.val, max);
//注意返回的不是要求的最大值，而只是这颗子树的左右子树最大的从根节点往下的节点值和
return left > right ? left + root.val : right + root.val;
}
}
滴滴面试题 二叉树距离最大的两个节点之间的距离
题目：如果我们把二叉树看做图，父子节点之间的连线看成是双向的，我们姑且定义“距离”为两个节点之间边的个数。写一个程序求一棵二叉树中相距最远的两个节点之间的距离。
如下图所示，树中相距最远的两个节点为A,B，最大距离为6。
书上对这个问题的分析是很清楚的，计算一个二叉树的最大距离有两个情况：
情况A: 路径经过左子树的最深节点，通过根节点，再到右子树的最深节点。
情况B: 路径不穿过根节点，而是左子树或右子树的最大距离路径，取其大者
对于情况A来说，只需要知道左右子树的深度，然后加起来即可。
对于情况B来说，需要知道左子树的最远距离，右子树的最远距离
这里的解法应该是最优的最简单的解法。首先维持一个最大距离的全局变量，在求树深度的时候，将左右子树的深度相加再加2与当前最大距离比较，取较大值。
int max = 0;
public int getHeight(TreeNode root){
if (root == null) {
return 0;
}
int leftHeight = getHeight(root.left) + 1;
int rightHeight = getHeight(root.right) + 1;
int len = leftHeight + rightHeight;
max = len > max ? len : max;
return leftHeight > rightHeight ? leftHeight : rightHeight;
}
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
解法：先求出长度，再对k去整除，然后循环每个k反转链表
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if (head == NULL || k <= ) {
return head;
}
int len = ;
ListNode* cur = head;
while (cur != NULL) {
len++;
cur = cur->next;
}
ListNode* dummy = new ListNode();
dummy->next = head;
ListNode* pre = dummy;
int groups = len / k;
while (groups-- > ) {
int count = ;
cur = pre->next;
ListNode* curt = cur;
ListNode* next = cur->next;
ListNode* nextNext = NULL;
while (count++ < k) {
nextNext = next->next;
next->next = cur;
cur = next;
next = nextNext;
}
pre->next = cur;
pre = curt;
pre->next = nextNext;
}
return dummy->next;
}
};
leetcode 146. LRU Cache--腾讯面试题
题意：
为最近最少使用（LRU）缓存策略设计一个数据结构，它应该支持以下操作：获取数据（get）和写入数据（set）。 获取数据get(key)：如果缓存中存在key，则获取其数据值（通常是正数），否则返回-1。 写入数据set(key, value)：如果key还没有在缓存中，则写入其数据值。当缓存达到上限，它应该在写入新数据之前删除最近最少使用的数据用来腾出空闲位置。
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put. get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
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. Follow up:
Could you do both operations in O(1) time complexity?
思路：利用双向链表+hashmap。对于get方法，如果hashmap中存在相应的key，则取出返回，并将对应节点移动到链表的尾部，表示最新使用过，反之返回-1；对于put方法，先判断要put的值map中是否存在，如果存在则将相应节点移动到链表尾部，表示最新使用过，如果不存在要看当前链表长度是否已经到达cache的容量，如果到达了容量，则要删除链表头部节点，并将待插入节点插入链表尾部，反之直接插入链表尾部。所以要自定义一个将节点移动到链表尾部的方法。
public class LRUCache {
public class DoublyListNode {
int val = 0;
int key = 0;
DoublyListNode next = null;
DoublyListNode prev = null;
public DoublyListNode(int val) {
this.val = val;
}
}
int capacity = 0;
int curtSize = 0;
HashMap<Integer, DoublyListNode> map;
DoublyListNode head = null;
DoublyListNode tail = null;
public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<>();
}
public int get(int key) {
int value = -1;
if (map.containsKey(key)) {
DoublyListNode curt = map.get(key);
value = curt.val;
moveToTail(curt);
}
return value;
}
public void put(int key, int value) {
if (capacity == 0) {
return;
}
DoublyListNode curt = null;
if (map.containsKey(key)) {
curt = map.get(key);
curt.val = value;
moveToTail(curt);
} else {
if (curtSize == capacity) {
int k = head.key;
map.remove(k);
head = head.next;
if (head != null) {
head.prev = null;
}
curtSize--;
}
curt = new DoublyListNode(value);
curt.key = key;
map.put(key, curt);
if (head == null) {
head = curt;
} else {
tail.next = curt;
curt.prev = tail;
}
curtSize++;
tail = curt;
tail.next = null;
}
}
public void moveToTail(DoublyListNode curt) {
if (curt.next == null) {
return;
}
//看是否在头部
if (curt.prev != null) {
curt.prev.next = curt.next;
curt.next.prev = curt.prev;
curt.prev = null;
} else {
head = head.next;
head.prev = null;
}
tail.next = curt;
curt.prev = tail;
tail = curt;
tail.next = null;
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
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.
思路：两指针分别从头和尾开始，找出比前一个长度高的竖线。
代码：
public class Solution {
public int maxArea(int[] height) {
int left = 0;
int right = height.length - 1;
int max = 0;
while (left < right) {
int h = Math.min(height[right], height[left]);
max = Math.max(max, (right - left) * h);
while (height[left] <= h && left < right) {
left++;
}
while (height[right] <= h && left < right) {
right--;
}
}
return max;
}
}
扔鸡蛋问题
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 -> X = 14
所以我们先到14楼，然后27楼，然后39楼，以此类推，最坏情况需要扔14次。
代码（注意数据类型long的使用）：
public class Solution {
/**
* @param n an integer
* @return an integer
*/
public int dropEggs(int n) {
// Write your code here
long sum = 0;
for (int i = 1; i <= n; i++) {
sum += (long) i;
if (sum >= (long) n) {
return i;
}
}
return 0;
}
}
leetcode 47 permutations II
题意：跟leetcode46的不同点只是数字有重复的。在每一层递归中加上一个set就好了。
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> ans;
helper(nums, , ans);
return ans;
}
void helper(vector<int>& nums, int index, vector<vector<int>>& ans) {
if (index == nums.size() - ) {
ans.push_back(nums);
return;
}
set<int> set;
for (int i = index; i < nums.size(); i++) {
if (set.find(nums[i]) == set.end()) {
set.insert(nums[i]);
swap(nums[i], nums[index]);
helper(nums, index + , ans);
swap(nums[i], nums[index]);
}
}
}
};
leetcode 46 permutations--微软面试题
题意：求出无重复字符串的所有排列。
解法：之前都是用dfs来做的。现在有了更好的解法-交换。每一位数字都跟后面的数字交换，递归。
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> ans;
helper(nums, , ans);
return ans;
}
void helper(vector<int>& nums, int index, vector<vector<int>>& ans) {
if (index == nums.size() - ) {
ans.push_back(nums);
return;
}
for (int i = index; i < nums.size(); i++) {
swap(nums[i], nums[index]);
helper(nums, index + , ans);
swap(nums[i], nums[index]);
}
}
};
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.
解法：O(n^2)解法，循环查找，注意字符串长度为零的时候的情况
public class Solution {
public int strStr(String haystack, String needle) {
if (haystack == null || needle == null) {
return -1;
}
if (needle.length() == 0) {
return 0;
}
for (int i = 0; i < haystack.length(); i++) {
for (int j = 0; j < needle.length(); j++) {
if (i + needle.length() > haystack.length()) {
return -1;
}
if (needle.charAt(j) != haystack.charAt(i + j)) {
break;
}
if (j == needle.length() - 1) {
return i;
}
}
}
return -1;
}
}
leetcode 233. Number of Digit One
难度：hard
题意：
Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n. For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13. Hint: Beware of overflow.
解析：1.数学公式的方法，比较难理解
Solution explanation: Let's start by counting the ones for every 10 numbers... 0, 1, 2, 3 ... 9 (1) 10, 11, 12, 13 ... 19 (1) + 10 20, 21, 22, 23 ... 29 (1) ... 90, 91, 92, 93 ... 99 (1) 100, 101, 102, 103 ... 109 (10 + 1) 110, 111, 112, 113 ... 119 (10 + 1) + 10 120, 121, 122, 123 ... 129 (10 + 1) ... 190, 191, 192, 193 ... 199 (10 + 1) 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. 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? The answer is (n / k) / 10. 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? The answer is (n / k) / 10, and the number of ones at ten's place is (n / k) / 10 * k. Let r = n / k, now we have a formula to count the ones at k's place: r / 10 * k 2). So far, everything looks good, but we need to fix those special rows, how? 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: r / 10 * k + (r % 10 == 1 ? m + 1 : 0) 3). Wait, how about 20, 21 and 22? 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: (r + 8) / 10 * k + (r % 10 == 1 ? m + 1 : 0) As you can see, it's all about how we fix the formula. Really hope that makes sense to you.
代码：
1.数学公式
public class Solution {
public int countDigitOne(int n) {
int count = 0;
for (long k = 1; k <= n; k *= 10) {
long r = n / k;
long m = n % k;
count += (r + 8) / 10 * k + (r % 10 == 1 ? m + 1 : 0);
}
return count;
}
}
2.递归求解的方法，参照《剑指offer》的解法。先求出最高位出现1的次数，再算出后面几位出现1的次数，然后加上去除最高位之后的数字出现1的次数。
public class Solution {
public int countDigitOne(int n) {
if (n <= 0) {
return 0;
}
String num = String.valueOf(n);
return count(num);
}
public int count(String num) {
if (num == null || num.length() == 0) {
return 0;
}
char first = num.charAt(0);
int numOfFirst = 0;
if (first == '1') {
if (num.length() > 1) {
numOfFirst = Integer.valueOf(num.substring(1)) + 1;
} else {
numOfFirst = 1;
}
} else if (first > '1') {
numOfFirst = (int)Math.pow(10, num.length() - 1);
}
int numOfOthers = 0;
if (num.length() > 1) {
numOfOthers = (first - '0') * (num.length() - 1) * (int)Math.pow(10, num.length() - 2);
}
return numOfFirst + numOfOthers + count(num.substring(1));
}
}
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.
解法：二分法,判断中间数字与头尾数字的关系
1.中间数字大于等于头数字，则最小数字在中间数字（包括）与末尾数字（包括）之间
2.中间数字小于等于头数字，则最小数字在中间数字（包括）与头数字（包括）之间
注意当有重复数字的时候，无法使用二分法，只能顺序查找。举一个例子原始数组是 0,1,1,1,1 旋转后可能是1,0,1,1,1或者1,1,1,0,1 ，根据之前的方法没法判定0是在左边还是右边。
public class Solution {
public int findMin(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int end = nums.length - 1;
int start = 0;
if (nums[start] < nums[end]) {
return nums[start];
}
while (start < end - 1) {
int mid = start + (end - start) / 2;
if (nums[mid] >= nums[start]) {
start = mid;
} else {
end = mid;
}
}
return nums[end];
}
}
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.
解法：递归，树的遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
int index = 0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || preorder.length == 0 || inorder == null || inorder.length == 0) {
return null;
}
Map<Integer, Integer> in = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
in.put(inorder[i], i);
}
return helper(preorder, inorder, 0, inorder.length - 1, in);
}
public TreeNode helper(int[] preorder, int[] inorder, int start, int end, Map<Integer, Integer> in) {
if (index > preorder.length || start > end) {
return null;
}
TreeNode root = new TreeNode(preorder[index]);
int pos = in.get(preorder[index]);
index++;
root.left = helper(preorder, inorder, start, pos - 1, in);
root.right = helper(preorder, inorder, pos + 1, end, in);
return root;
}
}
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.
解法：找到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;
}
}
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?
解法：还是跟前面两题一样，也有简单的方法。总结4的次方的二进制表示的规律01,100,10000,1000000...，可以发现只有一个1并且1出现在奇数位上（末尾是第一位）。
所以用 n&(n-1) == 0 && (n & 0x55555555) != 0 ,0x55555555 = 01010101010101010101010101010101,保证了只有奇数位上有1.
public class Solution {
public boolean isPowerOfFour(int num) {
return num > 0 && (num & (num - 1)) == 0 && (num & 0x55555555) != 0;
}
}
bug-free process
1.位操作的解法2017/01/04
leetcode 326. Power of Three
题意：
Given an integer, write a function to determine if it is a power of three. Follow up:
Could you do it without using any loop / recursion?
解法：跟leetcode231一样有循环的解法。但是也有tricky的解法。3的次方有特殊性：被3的次方整除的数一定是3的次方，找到int范围内最大3的次方3^19 = 1162261467,判断是否可以被其整除。
public class Solution {
public boolean isPowerOfThree(int n) {
return n > 0 && (1162261467 % n == 0);
}
}
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.
解法：最容易想到的解法是循环除以2，出现余数不为零的情况则不是2的次方。
但是有更好的方法就是总结2的次方数的二进制表示规律 01,10,100,1000,10000...,可以发现只有一个1，所以n&(n-1) = 0,反之则不是2的次方
public class Solution {
public boolean isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
}
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.
解法：与single number这题解法一样，都是异或，剩下的就是多出来的字符
public class Solution {
public char findTheDifference(String s, String t) {
int ret = t.charAt(0) - 'a';
for (int i = 0; i < s.length(); i++) {
ret ^= ((s.charAt(i) - 'a') ^ (t.charAt(i + 1) - 'a'));
}
return (char) (ret + 'a');
}
}
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.
解法：先记录每个字母出现的次数。再从头遍历字符串发现次数为1的字母则返回索引值。
public class Solution {
public int firstUniqChar(String s) {
if (s == null || s.length() == 0) {
return -1;
}
int[] count = new int[26];
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i) - 'a']++;
}
for (int i = 0; i < s.length(); i++) {
if (count[s.charAt(i) - 'a'] == 1) {
return i;
}
}
return -1;
}
}
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.
解法：题意中的字典序其实是按照字符串的字典序来排序整数。
对于一个整数 546 下一个字典序可能是5460 （if 460 <= n）,或者547（if 47 <= n）,或者是55.
当个位数是9，比如549，则下一个如果不是5490，也不是550，而是55
public class Solution {
public List<Integer> lexicalOrder(int n) {
List<Integer> ans = new ArrayList<>();
int cur = 1;
for (int i = 0; i < n; i++) {
ans.add(cur);
if (cur * 10 <= n) {
cur *= 10;
} else if (cur % 10 != 9 && cur + 1 <= n) {
cur++;
} else {
while ((cur / 10) % 10 == 9) {
cur /= 10;
}
cur = cur / 10 + 1;
}
}
return ans;
}
}
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
解法：题意是判断前一个单词是否可以由后一个单词的字母给组合起来，每一个字母只能使用一次的情况下。
先记录后一个单词每个字母出现的次数，再遍历前一个单词，将相应字母次数减一，减到小于0则返回false；
public class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] count = new int[26];
for (int i = 0; i < magazine.length(); i++) {
count[magazine.charAt(i) - 'a']++;
}
for (int i = 0; i < ransomNote.length(); i++) {
if (count[ransomNote.charAt(i) - 'a']-- == 0) {
return false;
}
}
return true;
}
}
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();
解法：shuffle操作：从左至右遍历数组，将当前元素与之前的遍历过的元素（包括自己）随机交换。
public class Solution {
int[] nums = null;
int[] copy = null;
Random random = null;
public Solution(int[] nums) {
this.nums = nums;
copy = nums.clone();
random = new Random();
}
/** Resets the array to its original configuration and return it. */
public int[] reset() {
return nums;
}
/** Returns a random shuffling of the array. */
public int[] shuffle() {
for (int i = 1; i < copy.length; i++) {
int j = random.nextInt(i + 1);
swap(copy, i, j);
}
return copy;
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(nums);
* int[] param_1 = obj.reset();
* int[] param_2 = obj.shuffle();
*/
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);
解法：用上一题（leetcode 382）的解法。注意的是不能将数组排序，因为排序之后索引就变了，就会出现错误。
错误代码（将数组排序了）：
public class Solution {
int[] nums = null;
public Solution(int[] nums) {
this.nums = nums;
Arrays.sort(this.nums);
}
public int pick(int target) {
int ans = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
ans = i;
break;
}
}
int start = ans;
for (int i = 1; start + i < nums.length && nums[start + i] == target; i++) {
if (randomInt(start, start + i) == start) {
ans = start + i;
}
}
return ans;
}
public int randomInt(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(nums);
* int param_1 = obj.pick(target);
*/
正确的代码
public class Solution {
int[] nums = null;
public Solution(int[] nums) {
this.nums = nums;
}
public int pick(int target) {
int ans = -1;
int count = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != target) {
continue;
}
if (randomInt(0, count++) == 0) {
ans = i;
}
}
return ans;
}
public int randomInt(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(nums);
* int param_1 = obj.pick(target);
*/
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();
解法：
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
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();
*/
3.错误代码，注意在getRandom()函数里面head要保持不变，因为getRandom会调用多次
/**
* 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() {
int ans = head.val;
for (int i = 1; head.next != null; i++) {
head = head.next;
//等于[0,i]之间的任何一个整数都可以
if (randInt(0,i) == 0) {
ans = head.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();
*/
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?
解法：dp 。O(target*nums.length).combinations[i]表示以i为target能够得到的组合数。for all j,combinations[i] += combinations[i-nums[j]](when i >= nums[j]).
public class Solution {
public int combinationSum4(int[] nums, int target) {
int[] combinations = new int[target + 1];
combinations[0] = 1;
for (int i = 1; i <= target; i++) {
for (int j = 0; j < nums.length; j++) {
if (i >= nums[j]) {
combinations[i] += combinations[i - nums[j]];
}
}
}
return combinations[target];
}
}
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?
解法：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]
public class Solution {
public int wiggleMaxLength(int[] nums) {
if (nums.length <= 1) {
return nums.length;
}
int len = nums.length;
int up = 1;
int down = 1;
for (int i = 1; i < len; i++) {
if (nums[i] > nums[i - 1]) {
up = down + 1;
} else if (nums[i] < nums[i - 1]) {
down = up + 1;
}
}
return Math.max(up, down);
}
}
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?
解法：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.
public class Solution {
public int getMoneyAmount(int n) {
int start = 1;
int end = n;
int[][] dp = new int[n + 1][n + 1];
return helper(dp, start, end);
}
public int helper(int[][] dp, int start, int end) {
if (start >= end) {
return 0;
}
if (dp[start][end] != 0) {
return dp[start][end];
}
dp[start][end] = Integer.MAX_VALUE;
for (int i = start; i <= end; i++) {
int tmp = i + Math.max(helper(dp, start, i - 1), helper(dp, i + 1, end));
dp[start][end] = Math.min(tmp, dp[start][end]);
}
return dp[start][end];
}
}
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.
解法：Binary Search。坑在了题意，Here "My" means the number which is given for you to guess not the number you put into guess(int num).
/* The guess API is defined in the parent class GuessGame.
@param num, your guess
@return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num); */ public class Solution extends GuessGame {
public int guessNumber(int n) {
int start = 1;
int end = n;
while (start <= end) {
int mid = start + (end - start) / 2;
int res = guess(mid);
if (res == 0) {
return mid;
} else if (res == -1) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return 0;
}
}
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
解法：还没有太理解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]
解法：dp。整除具有传递性 if c % b == 0 and b % a == 0, so c % a == 0。所以我们先将数组排序，方便后面的查找。
count[i]表示以为最大值nums[i]结束的subset的最大长度
pre[i]表示nums[i]的上一个比它小并且可以被它整除的的数的索引
public class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
//整除具有传递性 if c % b == 0 and b % a == 0, so c % a == 0
if (nums == null || nums.length == 0) {
return new ArrayList<Integer>();
}
Arrays.sort(nums);
int len = nums.length;
//count[i]表示以为最大值nums[i]结束的subset的最大长度
int[] count = new int[len];
//pre[i]表示nums[i]的上一个比它小并且可以被它整除的的数的索引
int[] pre = new int[len];
int endIndex = 0;
int max = 1;
for (int i = 0; i < len; i++) {
count[i] = 1;
pre[i] = -1;
for (int j = i - 1; j >= 0; j--) {
if (nums[i] % nums[j] == 0) {
if (1 + count[j] > count[i]) {
count[i] = count[j] + 1;
pre[i] = j;
}
}
}
if (count[i] > max) {
endIndex = i;
max = count[i];
}
}
List<Integer> ans = new ArrayList<Integer>();
ans.add(nums[endIndex]);
while (pre[endIndex] != -1) {
ans.add(nums[pre[endIndex]]);
endIndex = pre[endIndex];
}
return ans;
}
}
1.dp的做法 2016/12/27
leetcode 367. Valid Perfect Square
题意：判断一个数n是否是完全平方数，不能用库函数。
解法：1.Binary Search O(logn)
public class Solution {
public boolean isPerfectSquare(int num) {
long start = 1;
long end = num;
while (start <= end) {
long mid = start + (end - start) / 2;
if (mid * mid == (long) num) {
return true;
} else if (mid * mid > (long) num) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return false;
}
}
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；
public class Solution {
public boolean isPerfectSquare(int num) {
int odd = 1;
while (num > 0) {
num -= odd;
odd += 2;
}
return num == 0;
}
}
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
解法：这题是纯数学题，只能硬背了。
去掉一些特殊情况（x == z || y == z || x +y == z）和 (x + y < z)，剩下的情况先求x和y的最大公约数，在看z能否整除他们的最大公约数。
public class Solution {
public boolean canMeasureWater(int x, int y, int z) {
if (x + y < z) {
return false;
}
if (x == z || y == z || x +y == z) {
return true;
}
return z % gcd(x, y) == 0;
}
//最大公约数
public int gcd(int x, int y) {
while (y != 0) {
int temp = y;
y = x % y;
x = temp;
}
return x;
}
}
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].
解法：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不能作为数字的开头。然后返回所有长度的个数和就可以了。
public class Solution {
public int countNumbersWithUniqueDigits(int n) {
if (n == 0) {
return 1;
}
int[] dp = new int[n];
dp[0] = 9;
int count = 10;
for (int i = 1; i < n; i++) {
dp[i] = dp[i - 1] * (9 - (i + 1) + 2);
count += dp[i];
}
return count;
}
}
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 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 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(, ); // User 1's news feed should return a list with 1 tweet id -> [5].
twitter.getNewsFeed(); // User 1 follows user 2.
twitter.follow(, ); // User 2 posts a new tweet (id = 6).
twitter.postTweet(, ); // 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(); // User 1 unfollows user 2.
twitter.unfollow(, ); // 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();
解法：HashMap+PriorityQueue.PriorityQueue读取最新的动态时，跟合并k个有序链表类似。
public class Twitter {
public static int timeStamp = 0;
public class Tweet {
int id = 0;
int time = 0;
Tweet next = null;
public Tweet(int id) {
this.id = id;
this.time = timeStamp++;
}
}
public class User {
int id = 0;
Set<Integer> followed = new HashSet<>();
Tweet cur = null;
public User(int id) {
this.id = id;
followed.add(id);
}
public void follow(int id) {
followed.add(id);
}
public void unFollow(int id) {
followed.remove(id);
}
public void post(int id) {
Tweet tw = new Tweet(id);
tw.next = cur;
cur = tw;
}
}
Map<Integer, User> userMap = null;
/** Initialize your data structure here. */
public Twitter() {
userMap = new HashMap<>();
}
/** Compose a new tweet. */
public void postTweet(int userId, int tweetId) {
if (!userMap.containsKey(userId)) {
userMap.put(userId, new User(userId));
}
userMap.get(userId).post(tweetId);
}
/** 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. */
public List<Integer> getNewsFeed(int userId) {
List<Integer> ans = new ArrayList<>();
if (!userMap.containsKey(userId)) {
return ans;
}
PriorityQueue<Tweet> pq = new PriorityQueue<>(new MyComparator());
for (int user : userMap.get(userId).followed) {
Tweet tw = userMap.get(user).cur;
if (tw != null) {
pq.offer(tw);
}
}
int count = 0;
while (!pq.isEmpty() && count < 10) {
Tweet tw = pq.poll();
ans.add(tw.id);
count++;
if (tw.next != null) {
pq.offer(tw.next);
}
}
return ans;
}
/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
public void follow(int followerId, int followeeId) {
if (!userMap.containsKey(followerId)) {
userMap.put(followerId, new User(followerId));
}
if (!userMap.containsKey(followeeId)) {
userMap.put(followeeId, new User(followeeId));
}
userMap.get(followerId).follow(followeeId);
}
/** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
public void unfollow(int followerId, int followeeId) {
if (!userMap.containsKey(followerId) || followerId == followeeId) {
return;
}
userMap.get(followerId).unFollow(followeeId);
}
public class MyComparator implements Comparator<Tweet> {
public int compare(Tweet t1, Tweet t2) {
return t2.time - t1.time;
}
}
}
/**
* Your Twitter object will be instantiated and called as such:
* Twitter obj = new Twitter();
* obj.postTweet(userId,tweetId);
* List<Integer> param_2 = obj.getNewsFeed(userId);
* obj.follow(followerId,followeeId);
* obj.unfollow(followerId,followeeId);
*/
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.
解法：注意题意要求返回的不是一个list，而是一个NestedInteger。
1.遇到'[',将当前cur入栈，并且新建一个NestedInteger
2.遇到']',若有数字，则将数字加入当前NestedInteger。栈顶元素出栈，并且将当前cur加入栈顶的NestedInteger。
3.遇到数字后面的','，则将数字加入当前的NestedInteger
最后返回当前的NestedInteger。
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* public interface NestedInteger {
* // Constructor initializes an empty nested list.
* public NestedInteger();
*
* // Constructor initializes a single integer.
* public NestedInteger(int value);
*
* // @return true if this NestedInteger holds a single integer, rather than a nested list.
* public boolean isInteger();
*
* // @return the single integer that this NestedInteger holds, if it holds a single integer
* // Return null if this NestedInteger holds a nested list
* public Integer getInteger();
*
* // Set this NestedInteger to hold a single integer.
* public void setInteger(int value);
*
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
* public void add(NestedInteger ni);
*
* // @return the nested list that this NestedInteger holds, if it holds a nested list
* // Return null if this NestedInteger holds a single integer
* public List<NestedInteger> getList();
* }
*/
public class Solution {
public NestedInteger deserialize(String s) {
if (s == null || s.length() == 0) {
return null;
}
if (s.charAt(0) != '[') {
return new NestedInteger(Integer.valueOf(s));
}
int l = 0;
NestedInteger cur = null;
Stack<NestedInteger> stack = new Stack<>();
for (int r = 0; r < s.length(); r++) {
if (s.charAt(r) == '[') {
if (cur != null) {
stack.push(cur);
}
cur = new NestedInteger();
l = r + 1;
} else if (s.charAt(r) == ']') {
String num = s.substring(l, r);
if (!num.isEmpty()) {
cur.add(new NestedInteger(Integer.valueOf(num)));
}
if (!stack.isEmpty()) {
NestedInteger top = stack.pop();
top.add(cur);
cur = top;
}
l = r + 1;
} else if (s.charAt(r) == ',') {
if (s.charAt(r - 1) != ']') {
String num = s.substring(l, r);
cur.add(new NestedInteger(Integer.valueOf(num)));
}
l = r + 1;
}
}
return cur;
}
}
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 :
Given the list [[,],,[,]], By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [,,,,]. Example :
Given the list [,[,[]]], By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [,,].
解法：使用栈。将list中所有元素从后向前push到栈中，保证pop的时候是第一个元素。在hasNext中要安伯政栈顶的元素一定是Integer而不是list，也就是遇到list就要将其pop出来，再将其中的元素倒序push到栈中，直到栈顶元素是Integer。
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* public interface NestedInteger {
*
* // @return true if this NestedInteger holds a single integer, rather than a nested list.
* public boolean isInteger();
*
* // @return the single integer that this NestedInteger holds, if it holds a single integer
* // Return null if this NestedInteger holds a nested list
* public Integer getInteger();
*
* // @return the nested list that this NestedInteger holds, if it holds a nested list
* // Return null if this NestedInteger holds a single integer
* public List<NestedInteger> getList();
* }
*/
public class NestedIterator implements Iterator<Integer> {
Stack<NestedInteger> stack = null;
public NestedIterator(List<NestedInteger> nestedList) {
stack = new Stack<>();
for (int i = nestedList.size()- 1; i >= 0; i--) {
stack.push(nestedList.get(i));
}
} @Override
public Integer next() {
return stack.pop().getInteger();
} @Override
public boolean hasNext() {
while (!stack.isEmpty()) {
if (stack.peek().isInteger()) {
return true;
}
NestedInteger cur = stack.pop();
for (int i = cur.getList().size() - 1; i >= 0; i--) {
stack.push(cur.getList().get(i));
}
}
return false;
}
} /**
* Your NestedIterator object will be instantiated and called as such:
* NestedIterator i = new NestedIterator(nestedList);
* while (i.hasNext()) v[f()] = i.next();
*/
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]).
解法：原型是leetcode 300。首先将所给数组进行预处理,将其封装成一个类，优先按照width排序，width相等的情况下按照height倒序排序。然后转化成了对height进行最长递增子序列的求解。
为什么要这么排序？因为题意中并没有要求按照顺序来叠信封，这么排序之后，就必须按照从前到后的顺序来了，满足最长递增子序列的背景，因为width是从小到大的，在width相等时，height是从大到小的，保证了width相等时，height增大也不会使子序列的长度增大。也可以先按照height来正序排序，再按照width来倒序排序。为什么要一个正序一个倒序，看完下面这个例子就明白了。
[[2,3],[1,1],[4,6],[6,7],[4,5]],分别看两个都正序与一个正序一个倒序的情况。
public class Solution {
public int maxEnvelopes(int[][] envelopes) {
if (envelopes.length < 2)
return envelopes.length;
A[] a = new A[envelopes.length];
for (int i = 0; i < envelopes.length; i++) {
a[i] = new A(envelopes[i][0], envelopes[i][1]);
}
Arrays.sort(a,new Comparator<A>(){
@Override
public int compare(A a, A b) {
if (a.w != b.w) {
return a.w - b.w;
} else {
return b.h - a.h;
}
}
});
int maxLen = 1;
int[] h = new int[envelopes.length];
h[0] = a[0].h;
for (int i = 1; i < envelopes.length; i++) {
int pos = getPos(h, 0, maxLen - 1, a[i].h);
if (pos == -1) {
h[maxLen++] = a[i].h;
} else
h[pos] = a[i].h;
}
return maxLen;
}
public int getPos(int[] h, int start, int end, int num) {
int index = -1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (h[mid] >= num) {
end = mid - 1;
index = mid;
} else {
start = mid + 1;
}
}
return index;
}
}
class A {
int w = 0;
int h = 0;
public A(int w, int h) {
this.w = w;
this.h = h;
}
}
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.
解法：将leetcode 300. Longest Increasing Subsequence的辅助数组改成长度为3就行了，如果第三位也被填了，说明存在长度为3的子序列。时间复杂度为O(n),空间复杂度为O(1).
public class Solution {
public boolean increasingTriplet(int[] nums) {
if (nums == null || nums.length == 0) {
return false;
}
int len = nums.length;
int[] h = new int[3];
h[0] = nums[0];
h[1] = Integer.MAX_VALUE;
h[2] = Integer.MAX_VALUE;
for (int i = 1; i < len; i++) {
for (int j = 0; j < 3; j++) {
if (h[j] >= nums[i]) {
if (j == 2) {
return true;
}
h[j] = nums[i];
break;
}
}
}
return false;
}
}
1.原型是leetcode300 2016/12/26
leetcode 300. Longest Increasing Subsequence
题意：
Given an unsorted array of integers, find the length of longest increasing subsequence. For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
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. Your algorithm should run in O(n2) complexity. Follow up: Could you improve it to O(n log n) time complexity?
解法：若使用dp会得O(n^2)的解法。这里最优的解法是O(nlogn).
思路与代码：
/*
* solution2: 时间复杂度O(n*log(n)),空间复杂度O(n)
* 新建一个辅助数组h,h[i]表示遍历到当前nums[j]位置时长度为i+1的递增子序列的最小末尾
* h填入值的部分称作有效区，还未填入值的部分称作无效区
* h[i]值的确定，h[0] = nums[0],在遍历nums 的同时，在h[i]中找到第一个大于等于nums[j]的数，并将其替换为为nums[j]，如果没找到则将h有效区后一个元素置为nums[j]
* h[i]会一直保持有序状态，所以找第一个大于等于nums[j]的数可以用二分法,最后返回h有效区的长度即可
* 由于在遍历的同时采用了时间复杂度为log(n)的二分查找，故时间复杂度为O(n*log(n))
*/
public class Solution {
public int lengthOfLIS(int[] nums) {
int maxLen = 0;
if (nums.length == 0)
return maxLen;
int[] h = new int[nums.length];
h[0] = nums[0];
maxLen = 1;
for (int i = 1; i < nums.length; i++) {
int pos = getPos(h, 0, maxLen - 1, nums[i]);
if (pos == -1) {
h[maxLen++] = nums[i];
} else
h[pos] = nums[i];
}
return maxLen;
}
public int getPos(int[] h, int start, int end, int num) {
int index = -1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (h[mid] >= num) {
end = mid - 1;
index = mid;
} else {
start = mid + 1;
}
}
return index;
}
}
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.
解法：题目是要找Eulerian path，顺便补充一下欧拉回路和欧拉路径的必要条件。
存在欧拉回路和欧拉路径的判断：
1）欧拉回路：
无向图：每个顶点的度数都是偶数，则存在欧拉回路。
有向图：每个顶点的入度都等于出度，则存在欧拉回路。
2）欧拉路径：
无向图：当且仅当该图所有顶点的度数为偶数 或者 除了两个度数为奇数外其余的全是偶数。
有向图：当且仅当该图所有顶点 出度=入度 或者 一个顶点 出度=入度+1，另一个顶点 入度=出度+1，其 他顶点 出度=入度。
这题用Hierholzer's algorithm+PriorityQueue（用来确保字典序）+dfs。第一个出度变为零的节点肯定就是末尾节点，PriorityQueue来存储节点的邻居，以字典序排序。
public class Solution {
Map<String, PriorityQueue<String>> graph;
List<String> path;
public List<String> findItinerary(String[][] tickets) {
if (tickets == null || tickets.length == 0) {
return new ArrayList<String>();
}
graph = new HashMap<>();
for (String[] ticket : tickets) {
graph.putIfAbsent(ticket[0], new PriorityQueue());
graph.get(ticket[0]).add(ticket[1]);
}
path = new LinkedList<String>();
dfs("JFK");
return path;
}
public void dfs(String start) {
while (graph.containsKey(start) && !graph.get(start).isEmpty()) {
dfs(graph.get(start).poll());
}
path.add(0, start);
}
}
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
解法：利用节点的出入度。定义diff = outdegree - indegree。遇到下一个节点，将diff-1，因为增加了一个indegree，如果该节点不为空，则diff+2，因为它增加了两个outdegree。如果diff<0,则返回false，最后diff应该等于0.初始的时候diff=1.因为root没有入度。
public class Solution {
public boolean isValidSerialization(String preorder) {
if (preorder == null) {
return false;
}
String[] nodes = preorder.split(",");
int diff = 1;
for (String node : nodes) {
if (--diff < 0) {
return false;
}
if (!node.equals("#")) {
diff += 2;
}
}
return diff == 0;
}
}
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?
解法：先找到中位数，用quickselect找第k大的数 k = (len + 1) / 2;leetcode 215的算法。
再用leetcode75的算法 + (1 + 2 * i) % (n | 1)，后者的作用是将前半部分放到奇数位，后半部分放到偶数位。
public class Solution {
public void wiggleSort(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}
int len = nums.length;
int median = findKthLargestElement(nums, (len + 1) / 2, 0, len - 1);
int left = 0;
int right = len - 1;
int i = 0;
while (i <= right) {
if (nums[indexMapping(i, len)] > median) {
swap(nums, indexMapping(i++, len), indexMapping(left++, len));
} else if (nums[indexMapping(i, len)] < median) {
swap(nums, indexMapping(i, len), indexMapping(right--, len));
} else {
i++;
}
}
}
public int indexMapping(int i, int n) {
return (1 + 2 * i) % (n | 1);
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public int findKthLargestElement(int[] nums, int k, int start, int end) {
if (start == end) {
return nums[start];
}
int left = start;
int right = end;
int pivot = nums[start + (end - start) / 2];
while (left <= right) {
while (left <= right && nums[left] < pivot) {
left++;
}
while (left <= right && nums[right] > pivot) {
right--;
}
if (left <= right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
if (end - left + 1 >= k) {
return findKthLargestElement(nums, k, left, end);
} else if (left - 1 == right) {
return findKthLargestElement(nums, k - (end - left + 1), start, right);
} else {
return findKthLargestElement(nums, k - (end - left + 1), start, right + 1);
}
}
}
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.
解法：一次替换的解法。O(n)时间复杂度，初始化两指针 left = 0；right = len - 1；
在位置i遇到零将其与left交换，并且i++，left++
遇到2将其与right交换，且right--；
反之i++；
public class Solution {
public void sortColors(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}
int left = 0;
int right = nums.length - 1;
int i = 0;
while (i <= right) {
if (nums[i] == 0) {
swap(nums, i, left);
left++;
i++;
} else if (nums[i] == 2) {
swap(nums, i, right);
right--;
} else {
i++;
}
}
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
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.
解法：dp。O(amount*n),n为coins数组的长度。
public class Solution {
public int coinChange(int[] coins, int amount) {
if (amount == 0) {
return 0;
}
if (amount == 0 || coins == null || coins.length == 0) {
return -1;
}
int[] dp = new int[amount + 1];
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
dp[i] = Integer.MAX_VALUE;
for (int j = 0; j < coins.length; j++) {
if (i < coins[j]) {
continue;
}
if (dp[i - coins[j]] != Integer.MAX_VALUE) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}
}
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.
解法：第i个灯泡位置i的因数是偶数个最后就是off，因数是奇数个最后就是on。有奇数个因数的数是完全平方数。目的就是找前n个数有多少个完全平方数。
1.遍历，判断每个数，遇到完全平方数结果加一。TLE
2.返回sqrt(n)。因为平方根是从1开始到sqrt(n)结束的，也就是说最多有sqrt(n)个完全平方数。
public class Solution {
public int bulbSwitch(int n) {
return (int) Math.sqrt(n);
}
}
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
解法：位操作。主要是怎么判断两个单词是否包含共同的字母。用一个整数的某一位来表示相应位置字母是否存在，若存在置为1.若两个单词的位表示法按位与结果为零则不会包含共同字母。
public class Solution {
public int maxProduct(String[] words) {
if (words == null || words.length == 0) {
return 0;
}
int len = words.length;
int[] bit = new int[len];
for (int i = 0; i < len; i++) {
for (int j = 0; j < words[i].length(); j++) {
bit[i] |= 1 << (words[i].charAt(j) - 'a');
}
}
int max = 0;
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) {
if ((bit[i] & bit[j]) == 0) {
max = Math.max(max, words[i].length() * words[j].length());
}
}
}
return max;
}
}
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.
解法：hint还是很重要的，可以想到最多的root数是2，相当于图的最长一条路径的最中间的一个（奇数个）或两个（偶数个）节点。
所以将叶子节点一层一层删除（叶子节点也就是邻接表size = 1的节点），最后剩下的不多于两个节点的节点集合就是root，注意当n=1的时候，边表示法是空数组，也要返回
public class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
if (n == 1) {
List<Integer> roots = new ArrayList<>();
roots.add(0);
return roots;
}
//无向图转化为邻接表表示
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
//将叶子节点提出来
List<Integer> leaves = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (graph.get(i).size() == 1) {
leaves.add(i);
}
}
while (n > 2) {
n -= leaves.size();
List<Integer> nextLeaves = new ArrayList<>();
for (int i : leaves) {
int neighbor = graph.get(i).get(0);
graph.get(neighbor).remove((Integer) i);
if (graph.get(neighbor).size() == 1) {
nextLeaves.add(neighbor);
}
}
leaves = nextLeaves;
}
return leaves;
}
}
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]
解法：
思路：
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:
代码：
public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int sell = 0;
int preSell = 0;
int buy = Integer.MIN_VALUE;
int preBuy = Integer.MIN_VALUE;
for (int price : prices) {
preBuy = buy;
buy = Math.max(preSell - price, preBuy);
preSell = sell;
sell = Math.max(preBuy + price, preSell);
}
return sell;
}
}
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).
解法：将原数组转换成利润数组，当前节点的利润等于当前价格减去前一天的价格。从后往前方便计算，所有正数利润的总和就是最大利润。
public class Solution {
public int maxProfit(int[] prices) {
if(prices == null || prices.length < 2) {
return 0;
}
int sum = 0;
for(int i = prices.length-1; i > 0; i--){
prices[i] = prices[i] - prices[i - 1];
if(prices[i] > 0)
sum += prices[i];
}
return sum;
}
}
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.
解法：将原数组转换成利润数组，当前节点的利润等于当前价格减去前一天的价格。求最大子数组和
public class Solution {
public int maxProfit(int[] prices) {
if(prices == null || prices.length < 2) {
return 0;
}
int ret = 0;
int sum = 0;
for(int i = prices.length - 1; i > 0; i--) {
prices[i] = prices[i] - prices[i - 1];
if(sum < 0) {
sum = 0;
}
sum += prices[i];
ret = Math.max(sum, ret);
}
return ret;
}
}
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.
解法：基本思路是先确定前两位，在往后逐步遍历看是否满足。前两位的长度是有限制的，因为要确保有第三位的存在。第一位长度i<=len/2,第二位长度j 满足max(i,j)<=len-i-j,len为字符串长度。
另外就是数据范围，小数据的话用long可以ac，follow up大数据应该用BigInteger
1.在较小的数据范围时使用long，会稍微快一点
public class Solution {
public boolean isAdditiveNumber(String num) {
if (num == null || num.length() == 0) {
return false;
}
int len = num.length();
for (int i = 1; i <= len / 2; i++) {
if (num.charAt(0) == '0' && i > 1) {
return false;
}
long first = Long.parseLong(num.substring(0, i));
for (int j = 1; Math.max(i, j) <= len - i - j; j++) {
if (num.charAt(i) == '0' && j > 1) {
break;
}
long second = Long.parseLong(num.substring(i, i + j));
if (isValid(first, second, i + j, num)) {
return true;
}
}
}
return false;
}
public boolean isValid(long first, long second, int start, String num) {
if (start == num.length()) {
return true;
}
second = second + first;
first = second - first;
String sum = Long.toString(second);
return num.startsWith(sum, start) && isValid(first, second, start + sum.length(), num);
}
}
2.follow up:较大的数使用BigInteger
import java.math.BigInteger;
public class Solution {
public boolean isAdditiveNumber(String num) {
if (num == null || num.length() == 0) {
return false;
}
int len = num.length();
for (int i = 1; i <= len / 2; i++) {
if (num.charAt(0) == '0' && i > 1) {
return false;
}
BigInteger first = new BigInteger(num.substring(0, i));
for (int j = 1; Math.max(i, j) <= len - i - j; j++) {
if (num.charAt(i) == '0' && j > 1) {
break;
}
BigInteger second = new BigInteger(num.substring(i, i + j));
if (isValid(first, second, i + j, num)) {
return true;
}
}
}
return false;
}
public boolean isValid(BigInteger first, BigInteger second, int start, String num) {
if (start == num.length()) {
return true;
}
second = second.add(first);
first = second.subtract(first);
String sum = second.toString();
return num.startsWith(sum, start) && isValid(first, second, start + sum.length(), num);
}
}
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.
解法：最优解法是用Binary Indexed Trees（BIT）。可参考http://www.cnblogs.com/xudong-bupt/p/3484080.html。
时间复杂度从O(m*n)降到了O(m*logn).m是调用次数，n为数组长度。
public class NumArray {
int[] sum = null;
int[] nums = null;
public NumArray(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}
int len = nums.length;
this.nums = nums;
sum = new int[len + 1];
for (int i = 1; i <= len; i++) {
sum[i] = nums[i - 1];
}
for (int i = 1; i <= len; i++) {
int pa = i + (((i - 1) ^ i) & i);
if (pa <= len) {
sum[pa] += sum[i];
}
}
}
void update(int i, int val) {
int diff = val - nums[i];
nums[i] = val;
int n = i + 1;
int len = sum.length;
while (n < len) {
sum[n] += diff;
n += (((n - 1) ^ n) & n);
}
}
public int getSum(int end) {
int endSum = 0;
while (end > 0) {
endSum += sum[end];
end -= ((end - 1) ^ end) & end;
}
return endSum;
}
public int sumRange(int i, int j) {
return getSum(j + 1) - getSum(i);
}
}
// Your NumArray object will be instantiated and called as such:
// NumArray numArray = new NumArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);
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.
解法：dp。利用dp[i][j]表示以(i - 1, j - 1)位右下角，以(0,0)位左上角的矩形的sum
public class NumMatrix {
int[][] dp = null;
public NumMatrix(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return;
}
int m = matrix.length;
int n = matrix[0].length;
//dp[i][j]表示以(i - 1, j - 1)位右下角，以(0,0)位左上角的矩形的sum
dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + matrix[i - 1][j - 1];
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
if(dp == null || dp.length == 0 || dp[0].length == 0) {
return 0;
}
return dp[row2 + 1][col2 + 1] - dp[row2 + 1][col1] - dp[row1][col2 + 1] + dp[row1][col1];
}
}
// Your NumMatrix object will be instantiated and called as such:
// NumMatrix numMatrix = new NumMatrix(matrix);
// numMatrix.sumRegion(0, 1, 2, 3);
// numMatrix.sumRegion(1, 2, 3, 4);
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?
解法：用一个全局变量来记录上一个当前的头元素即可
// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html
class PeekingIterator implements Iterator<Integer> {
Integer headElement = null;
Iterator<Integer> iterator = null;
public PeekingIterator(Iterator<Integer> iterator) {
// initialize any member here.
this.iterator = iterator;
} // Returns the next element in the iteration without advancing the iterator.
public Integer peek() {
if (headElement == null) {
headElement = this.iterator.next();
}
return headElement;
} // hasNext() and next() should behave the same as in the Iterator interface.
// Override them if needed.
@Override
public Integer next() {
if (headElement != null) {
Integer temp = headElement;
headElement = null;
return temp;
}
return this.iterator.next();
} @Override
public boolean hasNext() {
if (headElement != null) {
return true;
}
return this.iterator.hasNext();
}
}
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.
解法：dp。某个数n 肯定等于 n-j*j 加上一个完全平方数 j*j，也就是说count[n] = count[n - j*j] + 1,遍历所有可能的j，取最小的count就好了。
public class Solution {
public int numSquares(int n) {
int sqrt = (int) Math.sqrt(n);
if (sqrt * sqrt == n) {
return 1;
}
int[] count = new int[n + 1];
count[0] = 0;
for (int i = 1; i <= n; i++) {
count[i] = Integer.MAX_VALUE;
}
// For each i, it must be the sum of some number (i - j*j) and
// a perfect square number (j*j).
for (int i = 1; i <= n; i++) {
for (int j = 1; j * j <= i; j++) {
count[i] = Math.min(count[i], count[i - j * j] + 1);
}
}
return count[n];
}
}
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.
解法：二分法，找最前的满足citations[mid] >= (len - mid)的
public class Solution {
public int hIndex(int[] citations) {
if (citations == null || citations.length == 0) {
return 0;
}
int len = citations.length;
int max = 0;
int start = 0;
int end = len - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (citations[mid] >= (len - mid)) {
max = len - mid;
end = mid - 1;
} else {
start = mid + 1;
}
}
return max;
}
}
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.
解法：hashtable
public class Solution {
public int hIndex(int[] citations) {
if (citations == null || citations.length == 0) {
return 0;
}
int len = citations.length;
int[] count = new int[len + 1];
for (int i = 0; i < len; i++) {
if (citations[i] >= len) {
count[len]++;
} else {
count[citations[i]]++;
}
}
int h = 0;
for (int i = len; i >= 0; i--) {
h += count[i];
if (h >= i) {
return i;
}
}
return 0;
}
}
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.
解法：
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.
public class Solution {
public boolean isUgly(int num) {
if(num < 1)
return false;
for (int i = 2; i < 6 && num > 0; i++) {
while (num % i == 0) {
num /= i;
}
}
return 1 == num;
}
}
换一种写法：
public class Solution {
public boolean isUgly(int num) {
while(num >= 2 && 0 == num % 2) num /= 2;
while(num >= 3 && 0 == num % 3) num /= 3;
while(num >= 5 && 0 == num % 5) num /= 5;
return 1 == num;
}
}
bug-free process:
1.记住这个解法。2016/12/14
leetcode 264. Ugly Number II
题意：
Write a program to find the n-th ugly number. 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. Note that 1 is typically treated as an ugly number. Hint: 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.
An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.
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.
Assume you have Uk, the kth ugly number. Then Uk+1 must be Min(L1 * 2, L2 * 3, L3 * 5).
解法：
public class Solution {
public int nthUglyNumber(int n) {
int[] ugly = new int[n];
ugly[0] = 1;
int factors2 = 2;
int factors3 = 3;
int factors5 = 5;
int index2 = 0;
int index3 = 0;
int index5 = 0;
for (int i = 1; i < n; i++) {
ugly[i] = Math.min(Math.min(factors2, factors3), factors5);
if (ugly[i] == factors2) {
factors2 = 2 * ugly[++index2];
}
if (ugly[i] == factors3) {
factors3 = 3 * ugly[++index3];
}
if (ugly[i] == factors5) {
factors5 = 5 * ugly[++index5];
}
}
return ugly[n - 1];
}
}
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.
解法：将leetcode 264. Ugly Number II的解法通用化。时间复杂度O(n*k)
public class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
int k = primes.length;
int[] index = new int[k];
int[] ugly = new int[n];
ugly[0] = 1;
for (int i = 1; i < n; i++) {
ugly[i] = Integer.MAX_VALUE;
for (int j = 0; j < k; j++) {
ugly[i] = Math.min(ugly[i], primes[j] * ugly[index[j]]);
}
for (int j = 0; j < k; j++) {
if (ugly[i] == primes[j] * ugly[index[j]]) {
index[j]++;
}
}
}
return ugly[n - 1];
}
}
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]
解法：Divide & Conquer。与95. Unique Binary Search Trees II类似的做法。不过将表达式预处理了一下，将数字与运算符加入到了list里面，方便后面的提取
public class Solution {
public List<Integer> diffWaysToCompute(String input) {
if (input == null || input.length() == 0) {
return new ArrayList<Integer>();
}
List<String> express = new ArrayList<>();
for (int i = 0; i < input.length(); i++) {
int j = i;
while (j != input.length() && Character.isDigit(input.charAt(j))) {
j++;
}
String num = input.substring(i, j);
if (!num.isEmpty()) {
express.add(num);
i = j - 1;
} else {
express.add(input.substring(i, i + 1));
}
}
return compute(express, 0, express.size() - 1);
}
public List<Integer> compute(List<String> express, int start, int end) {
List<Integer> ans = new ArrayList<>();
if (start == end) {
ans.add(Integer.valueOf(express.get(start)));
return ans;
}
for (int i = start + 1; i < end; i += 2) {
String op = express.get(i);
List<Integer> left = compute(express, start, i - 1);
List<Integer> right = compute(express, i + 1, end);
for (int a : left) {
for (int b : right) {
int c = 0;
if (op.equals("+")) {
c = a + b;
} else if (op.equals("-")) {
c = a - b;
} else {
c = a * b;
}
ans.add(c);
}
}
}
return ans;
}
}
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.
解法：二分法。把整个矩阵看成一维的排序数组，二分查找。row = mid/n;col = mid %n;n为列数，mid为看成数组之后的索引
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int m = matrix.length;
int n = matrix[0].length;
int start = 0;
int end = m * n - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
int row = mid / n;
int col = mid % n;
if (matrix[row][col] == target) {
return true;
}
if (matrix[row][col] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return false;
}
}
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.
解法一：二分法分两步,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.遍历所有可能出现的行，逐行二分查找
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int m = matrix.length;
int n = matrix[0].length;
int start = 0;
int end = m - 1;
int index = 0;
//二分法找到最后可能出现的行，每一行的最左侧元素与target作比较
while (start <= end) {
int mid = start + (end - start) / 2;
if (matrix[mid][0] == target) {
return true;
}
if (matrix[mid][0] < target) {
index = mid;
start = mid + 1;
} else {
end = mid - 1;
}
}
//遍历所有可能出现的行，逐行二分查找
for (int i = 0; i <= index; i++) {
start = 0;
end = n - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (matrix[i][mid] == target) {
return true;
}
if (matrix[i][mid] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
return false;
}
}
解法二：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).
解法：
1.非递归的中序遍历，返回第k个节点的值。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int kthSmallest(TreeNode root, int k) {
int count = 0;
Stack<TreeNode> s = new Stack<>();
s.push(root);
while (!s.isEmpty()) {
while (root != null && root.left != null) {
root = root.left;
s.push(root);
}
TreeNode cur = s.pop();
count++;
if (count == k) {
return cur.val;
}
if (cur.right != null) {
root = cur.right;
s.push(root);
}
}
return 0;
}
}
2.二分法。与quickselect原理相似的。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int kthSmallest(TreeNode root, int k) {
int leftCount = countNodes(root.left);
if (leftCount < k - 1) {
return kthSmallest(root.right, k - leftCount - 1);
} else if (leftCount > k - 1) {
return kthSmallest(root.left, k);
} else {
return root.val;
}
}
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
return 1 + countNodes(root.left) + countNodes(root.right);
}
}
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.
解法：分治法。找到公共祖先则返回，只找到A，则返回A；只找到B，则返回B，找不到返回null
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return root;
}
if (root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null & right != null) {
return root;
}
if (left != null) {
return left;
}
if (right != null) {
return right;
}
return null;
}
}
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!
解法：多数投票算法https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm的扩展。
这题没有说明答案一定是有的，所以后面要花费O(n)的时间去验证结果的正确去否。leetcode 169. Majority Element这一题就不用验证了。
public class Solution {
public List<Integer> majorityElement(int[] nums) {
if (nums == null || nums.length == 0) {
return new ArrayList<Integer>();
}
int len = nums.length;
int majorA = 0;
int majorB = 0;
int countA = 0;
int countB = 0;
for (int i = 0; i < len; i++) {
if (nums[i] == majorA) {
countA++;
} else if (nums[i] == majorB) {
countB++;
} else if (countA == 0) {
majorA = nums[i];
countA++;
} else if (countB == 0) {
majorB = nums[i];
countB++;
} else {
countA--;
countB--;
}
}
//verify
countA = 0;
countB = 0;
for (int i = 0; i < len; i++) {
if (nums[i] == majorA) {
countA++;
} else if (nums[i] == majorB) {
countB++;
}
}
List<Integer> ans = new ArrayList<>();
if (countA > len / 3) {
ans.add(majorA);
}
if (countB > len / 3) {
ans.add(majorB);
}
return ans;
}
}
解题过程：
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
public class Solution {
public int majorityElement(int[] nums) {
int major = nums[0];
int count = 0;
for(int i = 0; i < nums.length; i++) {
if (count == 0) {
major = nums[i];
count++;
} else if (major == nums[i]) {
count++;
} else {
count--;
}
}
return major;
}
}
解题过程：
2.第二次看，完全忘了。2016/12/13
leetcode 227. Basic Calculator II
题意：
Implement a basic calculator to evaluate a simple expression string. The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero. You may assume that the given expression is always valid. Some examples:
"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5
Note: Do not use the eval built-in library function.
解法：1.两个栈，一个栈operators存储运算符，另一个nums存储数字。遇到数字时，入nums，遇到运算符时，判断是乘除还是加减。
a.若是乘除，则看栈顶是否也有乘除，如果有则计算，没有则将当前符号入栈
b.若是加减，则将栈中所有运算符计算完。
表达式的最后一位一定是数字，不能忘记入栈。便利完之后栈中可能还有未计算的部分，直接while循环出栈计算完。
public class Solution {
public int calculate(String s) {
if (s == null || s.length() == 0) {
return 0;
}
Stack<Integer> nums = new Stack<>();
Stack<Character> operators = new Stack<>();
int number = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == ' ') {
continue;
}
if (Character.isDigit(s.charAt(i))) {
number = number * 10 + s.charAt(i) - '0';
} else {
nums.push(number);
number = 0;
if ((s.charAt(i) == '*' || s.charAt(i) == '/')) {
if (!operators.isEmpty() && ((operators.peek() == '*') || (operators.peek() == '/'))) {
char op = operators.pop();
int a = nums.pop();
int b = nums.pop();
int c = 0;
if (op == '*') {
c = a * b;
} else {
c = b / a;
}
nums.push(c);
}
} else {
while (!operators.isEmpty()) {
char op = operators.pop();
int a = nums.pop();
int b = nums.pop();
int c = 0;
if (op == '+') {
c = a + b;
} else if (op == '-') {
c = b - a;
} else if (op == '*') {
c = a * b;
} else {
c = b / a;
}
nums.push(c);
}
}
operators.push(s.charAt(i));
}
}
nums.push(number);
while (!operators.isEmpty()) {
char op = operators.pop();
int a = nums.pop();
int b = nums.pop();
int c = 0;
if (op == '+') {
c = a + b;
} else if (op == '-') {
c = b - a;
} else if (op == '*') {
c = a * b;
} else {
c = b / a;
}
nums.push(c);
}
return nums.pop();
}
}
2.优化的解法。一个栈，只存数字。
public class Solution {
public int calculate(String s) {
if (s == null || s.length() == 0) {
return 0;
}
Stack<Integer> nums = new Stack<>();
int number = 0;
char op = '+';
for (int i = 0; i < s.length(); i++) {
if (Character.isDigit(s.charAt(i))) {
number = number * 10 + s.charAt(i) - '0';
}
if (!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' ' || i == s.length() - 1){
if (op == '+') {
nums.push(number);
} else if (op == '-'){
nums.push(-number);
} else if (op == '*') {
nums.push(nums.pop() * number);
} else {
nums.push(nums.pop() / number);
}
op = s.charAt(i);
number = 0;
}
}
int res = 0;
while (!nums.isEmpty()) {
res += nums.pop();
}
return res;
}
}
解题过程：
1.当遇到乘除符号的时候怎么计算,还有表达式的最后一位数字别忘了。2016/12/13
leetcode 60 Permutation Sequence
题意：
The set [1,2,3,…,n] contains a total of n! unique permutations. By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3): "123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence. Note: Given n will be between 1 and 9 inclusive.
解析：
在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开始）
代码：
public class Solution {
public String getPermutation(int n, int k) {
if (n == 0) {
return null;
}
int product = 1;
for (int i = 1; i < n; i++) {
product *= i;
}
StringBuilder ans = new StringBuilder("");
k = k - 1;
boolean[] visited = new boolean[n];
for (int i = 0; i < n; i++) {
int p = k / product;
k = k % product;
int index = 0;
for (int j = 0; j < n; j++) {
if (p == index && !visited[j]) {
ans.append((char)('0' + j + 1));
visited[j] = true;
break;
} else if (!visited[j]){
index++;
}
}
if (i != n - 1) {
product /= n - i - 1;
}
}
return ans.toString();
}
}
1.一种更简便的方法 11/5
2.不使用list的做法 11/16
3.bug-free 11/27
lintcode Sqrt(x) II求实数的平方根--搜狐面试题
题意：求double类型的平方根，返回值也是double类型的。
解法：
1.还是二分法，要注意的是double类型在比较是否相等的时候是有一个精确度的。下面的解法是九章算法提供的，但是我觉得还是没有解决溢出的问题，当mid*mid的时候可能是会溢出的。
public class Solution {
/**
* @param x a double
* @return the square root of x
*/
public double sqrt(double x) {
// Write your code here
double start = 0;
double end = x;
if (x <= 1) {
end = 1;
}
double eps = 1e-12;
while (end - start > eps) {
double mid = start + (end -start) / 2;
if (mid * mid < x) {
start = mid;
} else {
end = mid;
}
}
return start;
}
}
2.牛顿法，，可以参考这个https://www.zhihu.com/question/20690553
public class Solution {
/**
* @param x a double
* @return the square root of x
*/
public double sqrt(double x) {
// Write your code here
double res = 1.0;
double eps = 1e-12;
while(Math.abs(res * res - x) > eps) {
res = (res + x / res) / 2;
}
return res;
}
}
leetcode 69 Sqrt(x)
题意：
Implement int sqrt(int x). Compute and return the square root of x.
解法：先利用倍增法找到左边界，和右边界。再利用二分法，注意的是数据类型的转换
public class Solution {
public int mySqrt(int x) {
if (x < 2) {
return x;
}
long a = (long) x;
long start = 1;
while (start * start < a) {
start *= 2;
}
long end = start;
start /= 2;
int ans = 0;
while (start <= end) {
long mid = start + (end - start) / 2;
if (mid * mid == a) {
return (int) mid;
}
if (mid * mid < a) {
ans = (int) mid;
start = mid + 1;
} else {
end = mid - 1;
}
}
return ans;
}
}
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.
解法：
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位格雷码的逆序的和。
public class Solution {
public List<Integer> grayCode(int n) {
List<Integer> codes = new ArrayList<>();
if (n <= 1) {
for (int i = 0; i <= n; i++) {
codes.add(i);
}
return codes;
}
List<Integer> preCodes = grayCode(n - 1);
codes.addAll(preCodes);
for (int i = preCodes.size() - 1; i >= 0; i--) {
codes.add((1 << (n - 1)) | preCodes.get(i));
}
return codes;
}
}
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.
解法：dp。可以使用常数量空间
public class Solution {
public int numDecodings(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int len = s.length();
int[] dp = new int[3];
dp[0] = 1;
for (int i = 1; i <= len; i++) {
if (s.charAt(i - 1) == '0') {
if (i != 1 && s.charAt(i - 2) > '0' && s.charAt(i - 2) < '3') {
dp[i % 3] = dp[(i - 2) % 3];
} else {
return 0;
}
} else {
dp[i % 3] = dp[(i - 1) % 3];
if (i != 1 && (s.charAt(i - 2) == '1' || (s.charAt(i - 2) == '2' && s.charAt(i - 1) < '7'))) {
dp[i % 3] += dp[(i - 2) % 3];
}
}
}
return dp[len % 3];
}
}
bug-free process：
1.数字字符串中包含0的时候怎么处理 11/17
2.粗心 在数值范围 bug 2016/11/30
3.bug-free ，改写成了常数空间的dp 2016/12/18
leetcode 93 Restore IP Addresses
题意：
Given a string containing only digits, restore it by returning all possible valid IP address combinations. For example:
Given "25525511135", return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
解法：backtracking 回溯法.每个点有三个位置可插入
public class Solution {
public List<String> restoreIpAddresses(String s) {
if (s == null || s.length() < 4) {
return new ArrayList<String>();
}
List<String> ans = new ArrayList<String>();
StringBuilder ip = new StringBuilder(s);
helper(s, ans, 0, ip);
return ans;
}
public void helper(String s, List<String> ans, int index, StringBuilder ip) {
if (ip.length() == s.length() + 3) {
ans.add(new String(ip));
return;
}
for (int i = index; i < index + 3; i++) {
//点之前的情况
if (Integer.valueOf(ip.substring(index, i + 1)) > 255) {
return;
}
if (i != index && ip.charAt(index) == '0') {
return;
}
if (i + 1 == ip.length()) {
return;
}
//已经插入了两个点了，第三个点要考虑点之后的情况
if (ip.length() == s.length() + 2) {
//第三个点之后的长度大于3
if (ip.length() - 1 - i > 3) {
continue;
}
if (Integer.valueOf(ip.substring(i + 1, ip.length())) > 255) {
continue;
}
//第三个点之后的紧着是0，并且后面不止一位
if (ip.length() - 1 - i > 1 && ip.charAt(i + 1) == '0') {
continue;
}
}
ip.insert(i + 1, '.');
helper(s, ans, i + 2, ip);
ip.deleteCharAt(i + 1);
}
}
}
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
解法：动态规划。对于有n个节点的情况，可以用1~n分别作为根节点，当以i为根节点时，左子树是1~i-1，右子树是i+1~n，yii为根节点的bst的数量是左子树的数量乘以右子树的数量
有dp[i] += dp[j] * dp[i - 1 - j] (1<=j<=i)
public class Solution {
public int numTrees(int n) {
if (n <= 0) {
return 0;
}
int[] dp = new int[n + 1];
dp[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
dp[i] += dp[j] * dp[i - 1 - j];
}
}
return dp[n];
}
}
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
解法：分治法 对于 start~end 的根节点，求出其所有的左右子树，再以当前根节点组合左右子树。start > end 的时候返回加入了null的链表，不能返回null。
/**
* 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<TreeNode> generateTrees(int n) {
if (n < 1) {
return new ArrayList<TreeNode>();
}
return helper(1, n);
}
public List<TreeNode> helper(int start, int end) {
List<TreeNode> bsts = new ArrayList<>();
if (start > end) {
bsts.add(null);
return bsts;
}
for (int i = start; i <= end; i++) {
List<TreeNode> left = helper(start, i - 1);
List<TreeNode> right = helper(i + 1, end);
for (TreeNode l : left) {
for (TreeNode r : right) {
TreeNode root = new TreeNode(i);
root.left = l;
root.right = r;
bsts.add(root);
}
}
}
return bsts;
}
}
1.分治法递归思路 11/19
2.还是没想起来怎么做 ，注意边界条件的返回值 2016/12/06
leetcode 98 Validate Binary Search Tree
解法一：中序遍历递归。注意当所给树为空的时候返回true
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
boolean first = false;
int last = Integer.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
if (!isValidBST(root.left)) {
return false;
}
if (!first) {
first = true;
} else if (root.val <= last) {
return false;
}
last = root.val;
return isValidBST(root.right);
}
}
解法二：中序遍历非递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
boolean first = false;
int last = Integer.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
Stack<TreeNode> s = new Stack<>();
s.push(root);
while (!s.isEmpty()) {
while (root != null && root.left != null) {
s.push(root.left);
root = root.left;
}
TreeNode cur = s.pop();
if (!first) {
first = true;
} else if (cur.val <= last) {
return false;
}
last = cur.val;
if (cur.right != null) {
root = cur.right;
s.push(root);
}
}
return true;
}
}
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.
解法：利用中序遍历来构建。
helper(n)是构建节点数为n的bst。不断的递归helper(n/2)相当于中序遍历的遍历左子树，每遍历一次，当前节点就往后移动一位。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
ListNode cur = null;
public TreeNode sortedListToBST(ListNode head) {
if (head == null) {
return null;
}
int len = getLen(head);
cur = head;
return helper(len);
}
public TreeNode helper(int n) {
if (n <= 0) {
return null;
}
TreeNode left = helper(n / 2);
TreeNode root = new TreeNode(cur.val);
cur = cur.next;
TreeNode right = helper(n - 1 - n / 2);
root.left = left;
root.right = right;
return root;
}
public int getLen(ListNode head) {
int len = 0;
while (head != null) {
len++;
head = head.next;
}
return len;
}
}
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.
解法：从根节点到叶子结点深度优先搜索，记录路径上的节点值和，到叶子节点的时候判断是否满足条件。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
return helper(root, sum, root.val);
}
public boolean helper(TreeNode root, int sum, int curSum) {
if (root.left == null && root.right == null) {
if (curSum == sum) {
return true;
} else {
return false;
}
}
if (root.left != null) {
if (helper(root.left, sum, curSum + root.left.val)) {
return true;
}
}
if (root.right != null) {
if (helper(root.right, sum, curSum + root.right.val)) {
return true;
}
}
return false;
}
}
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]
]
解法：dfs，注意要求的是从根节点到叶子节点。
/**
* 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<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> paths = new ArrayList<>();
if (root == null) {
return paths;
}
List<Integer> path = new ArrayList<>();
path.add(root.val);
helper(paths, path, root, sum, root.val);
return paths;
}
public void helper(List<List<Integer>> paths, List<Integer> path, TreeNode root, int sum, int curSum) {
if (root.left == null && root.right == null) {
if (curSum == sum) {
paths.add(new ArrayList<>(path));
}
return;
}
if (root.left != null) {
path.add(root.left.val);
helper(paths, path, root.left, sum, curSum + root.left.val);
path.remove(path.size() - 1);
}
if (root.right != null) {
path.add(root.right.val);
helper(paths, path, root.right, sum, curSum + root.right.val);
path.remove(path.size() - 1);
}
}
}
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
解法：前缀和+hashmap+dfs
前缀和记录当前节点之前走过的路径的节点值和，hashmap存储前缀和以及前缀和出现的次数<preSum, ways>，每遍历一个节点判断preSum-target是否存在hashmap中，如果存在则将结果加上map.get(preSum-target),然后再分别遍历左子树和右子树，返回左子树和右子树的方法总数。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int pathSum(TreeNode root, int sum) {
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
return helper(root, 0, sum, map);
}
public int helper(TreeNode root, int curSum, int target, HashMap<Integer, Integer> map) {
if (root == null) {
return 0;
}
curSum += root.val;
int res = map.getOrDefault(curSum - target, 0);
map.put(curSum, map.getOrDefault(curSum, 0) + 1);
res += helper(root.left, curSum, target, map) + helper(root.right, curSum, target, map);
map.put(curSum, map.get(curSum) - 1);
return res;
}
}
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.
解法：动态规划，自底向上比较方便。
public class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if (triangle == null || triangle.size() == 0 || triangle.get(0).size() == 0) {
return 0;
}
int m = triangle.size();
int n = triangle.get(m - 1).size();
int[][] dp = new int[m][n];
for (int i = 0; i < n; i++) {
dp[m - 1][i] = triangle.get(m - 1).get(i);
}
for (int i = m - 2; i >=0; i--) {
for (int j = 0; j < triangle.get(i).size(); j++) {
dp[i][j] += triangle.get(i).get(j) + Math.min(dp[i + 1][j], dp[i + 1][j + 1]);
}
}
return dp[0][0];
}
}
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.
解法：bfs，还有更优化的方法，待更新。
public class Solution {
public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
if (wordList == null || wordList.size() == 0 || beginWord == null || endWord == null) {
return 0;
}
wordList.add(endWord);
int length = 0;
Queue<String> qu = new LinkedList<>();
Set<String> visited = new HashSet<>();
qu.add(beginWord);
visited.add(beginWord);
while (!qu.isEmpty()) {
length++;
int size = qu.size();
for (int i = 0; i < size; i++) {
String cur = qu.poll();
if (cur.equals(endWord)) {
return length;
}
for (String neighbor : getAllWords(cur, wordList)) {
if (!visited.contains(neighbor)) {
qu.add(neighbor);
visited.add(neighbor);
}
}
}
}
return 0;
}
public List<String> getAllWords(String word, Set<String> wordList) {
List<String> words = new ArrayList<>();
if (word == null) {
return words;
}
char[] arr = word.toCharArray();
for (int i = 0; i < word.length(); i++) {
char ch = arr[i];
for (char c = 'a'; c <= 'z'; c++) {
if (c != ch) {
arr[i] = c;
if (wordList.contains(new String(arr))) {
words.add(new String(arr));
}
}
}
arr[i] = ch;
}
return words;
}
}
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
解法：矩阵的四条边上的'O'及其连通的'O'，是没有被包围的，其余的都被包围了。所以先将这些不被包围的'O'改为'T'，使用bfs。然后再遍历整个矩阵将'T'变为'O',剩下的'O'变为'X'。
还有并查集的解法，待更新。2016/12/05
public class Solution {
public class Position {
int row = 0;
int col = 0;
public Position(int i, int j) {
row = i;
col = j;
}
}
public void solve(char[][] board) {
if (board == null || board.length == 0) {
return;
}
int m = board.length;
int n = board[0].length;
//first row
for (int i = 0; i < n; i++) {
if (board[0][i] == 'O') {
changeOToT(board, 0, i);
}
}
if (m > 1) {
//last row
for (int i = 0; i < n; i++) {
if (board[m - 1][i] == 'O') {
changeOToT(board, m - 1, i);
}
}
}
//first col
for (int i = 0; i < m; i++) {
if (board[i][0] == 'O') {
changeOToT(board, i, 0);
}
}
if (n > 1) {
//last col
for (int i = 0; i < m; i++) {
if (board[i][n - 1] == 'O') {
changeOToT(board, i, n - 1);
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'T') {
board[i][j] = 'O';
} else if (board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}
}
//bfs
public void changeOToT(char[][] board, int row, int col) {
board[row][col] = 'T';
Position pos = new Position(row, col);
Queue<Position> qu = new LinkedList<>();
qu.offer(pos);
while (!qu.isEmpty()) {
int size = qu.size();
for (int i = 0; i < size; i++) {
Position curPos = qu.poll();
int curRow = curPos.row;
int curCol = curPos.col;
//top
if (curRow > 0 && board[curRow - 1][curCol] == 'O') {
qu.offer(new Position(curRow - 1, curCol));
board[curRow - 1][curCol] = 'T';
}
//down
if (curRow < board.length - 1 && board[curRow + 1][curCol] == 'O') {
qu.offer(new Position(curRow + 1, curCol));
board[curRow + 1][curCol] = 'T';
}
//left
if (curCol > 0 && board[curRow][curCol - 1] == 'O') {
qu.offer(new Position(curRow, curCol - 1));
board[curRow][curCol - 1] = 'T';
}
//right
if (curCol < board[0].length - 1 && board[curRow][curCol + 1] == 'O') {
qu.offer(new Position(curRow, curCol + 1));
board[curRow][curCol + 1] = 'T';
}
}
}
}
}
1.思路 几种思路的比较 有坑注意 11/23
2. 2016/12/05 第二次做，发现第一次的去重是可以避免的，方法是每次加入queue之前先将相应位置改变为'T'，这样就不用去重了 bug-free
leetcode 200. Number of Islands
题意：
解法：与上一题130类似的解法。还有并查集的解法，待更新。
public class Solution {
public class Position {
int row = 0;
int col = 0;
public Position(int i, int j) {
row = i;
col = j;
}
}
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int m = grid.length;
int n = grid[0].length;
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
count++;
changeOneToTwo(grid, i, j);
j++;
}
}
}
return count;
}
//bfs
public void changeOneToTwo(char[][] grid, int row, int col) {
grid[row][col] = '2';
Position pos = new Position(row, col);
Queue<Position> qu = new LinkedList<>();
qu.offer(pos);
while (!qu.isEmpty()) {
int size = qu.size();
for (int i = 0; i < size; i++) {
Position curPos = qu.poll();
int curRow = curPos.row;
int curCol = curPos.col;
//top
if (curRow > 0 && grid[curRow - 1][curCol] == '1') {
qu.offer(new Position(curRow - 1, curCol));
grid[curRow - 1][curCol] = '2';
}
//down
if (curRow < grid.length - 1 && grid[curRow + 1][curCol] == '1') {
qu.offer(new Position(curRow + 1, curCol));
grid[curRow + 1][curCol] = '2';
}
//left
if (curCol > 0 && grid[curRow][curCol - 1] == '1') {
qu.offer(new Position(curRow, curCol - 1));
grid[curRow][curCol - 1] = '2';
}
//right
if (curCol < grid[0].length - 1 && grid[curRow][curCol + 1] == '1') {
qu.offer(new Position(curRow, curCol + 1));
grid[curRow][curCol + 1] = '2';
}
}
}
}
}
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
/ \
\_/
解法：bfs+hashMap
/**
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* List<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/
public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) {
return node;
}
HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
Set<UndirectedGraphNode> visited = new HashSet<>();
Queue<UndirectedGraphNode> qu = new LinkedList<>();
qu.offer(node);
visited.add(node);
while (!qu.isEmpty()) {
int size = qu.size();
for (int i = 0; i < size; i++) {
UndirectedGraphNode cur = qu.poll();
map.put(cur, new UndirectedGraphNode(cur.label));
for (UndirectedGraphNode neighbor : cur.neighbors) {
if (!visited.contains(neighbor)) {
qu.offer(neighbor);
visited.add(neighbor);
}
}
}
}
for (UndirectedGraphNode cur : map.keySet()) {
for (UndirectedGraphNode neighbor : cur.neighbors) {
map.get(cur).neighbors.add(map.get(neighbor));
}
}
return map.get(node);
}
}
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].
解法：二分法找到最近的那个数，从最近 那个数开始往两边查找。时间复杂度为log(n)+O(k)
public class Solution {
/**
* @param A an integer array
* @param target an integer
* @param k a non-negative integer
* @return an integer array
*/
public int[] kClosestNumbers(int[] A, int target, int k) {
// Write your code here
if (A == null || A.length == 0 || k == 0 || k > A.length) {
return new int[0];
}
int len = A.length;
int start = 0;
int end = len - 1;
//选择差值最大的index为初始值
int index = Math.abs(A[0] - target) > Math.abs(A[end] - target) ? 0 : end;
while (start <= end) {
int mid = start + (end - start) / 2;
if (A[mid] == target) {
index = mid;
break;
}
if (Math.abs(A[mid] - target) < Math.abs(A[index] - target)) {
index = mid;
} else if (Math.abs(A[mid] - target) == Math.abs(A[index] - target)) {
//差值相等的时候 选择较小者
if (A[mid] <= A[index]) {
index = mid;
} else {
break;
}
}
//继续下一轮比较
if (A[mid] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
int left = index - 1;
int right = index + 1;
int count = 1;
int[] ans = new int[k];
ans[0] = A[index];
while (left >= 0 && right < len && count < k) {
if (Math.abs(A[left] - target) <= Math.abs(A[right] - target)) {
ans[count++] = A[left--];
} else {
ans[count++] = A[right++];
}
}
//还没有到达k个
while (left >= 0 && count < k) {
ans[count++] = A[left--];
}
while (right < len && count < k) {
ans[count++] = A[right++];
}
return ans;
}
}
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.
解法：二分法，这里的难点在于不仅要中点，还要将中点与中点和末端的中点去比较，从而判断峰值哪一侧
学到一点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;
}
}
1.第一次在lintcode上做的，自己的想法虽然ac了，但是感觉不太好，看了九章的解法 遇到了一个小坑，必须得记住 2016/11/28
2.当相等的时候start和end怎么变化？ 2016/12/03
3.无意中写出了一个不同的方法，将mid和rightMid相等放在小于一起了 2016/12/18
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 = len - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
int rightMid = end - (end - mid) / 2;
if (nums[mid] <= nums[rightMid]) {
start = mid;
} else {
end = rightMid - 1;
}
}
return nums[start] > nums[end] ? start : end;
}
}
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.
解法：二分法。小于往右，大于往左，如果距离减小了，则更新index
public class Solution {
/**
* @param A an integer array sorted in ascending order
* @param target an integer
* @return an integer
*/
public int closestNumber(int[] A, int target) {
// Write your code here
if (A == null || A.length == 0) {
return 0;
}
int start = 0;
int end = A.length - 1;
int index = Math.abs(A[0] - target) < Math.abs(A[end] - target) ? 0 : end;
while (start <= end) {
int mid = start + (end -start) / 2;
if (A[mid] == target) {
return mid;
}
if (Math.abs(A[mid] - target) < Math.abs(A[index] - target)) {
index = mid;
}
if (A[mid] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return index;
}
}
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.
思路：
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次。
代码
public class Solution {
/**
* @param n an integer
* @return an integer
*/
public int dropEggs(int n) {
// Write your code here
long sum = 0;
for (int i = 1; i <= n; i++) {
sum += (long) i;
if (sum >= (long) n) {
return i;
}
}
return 0;
}
}
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
解法：非递归，用两个栈
public class Solution {
/**
* @param s an expression includes numbers, letters and brackets
* @return a string
*/
public String expressionExpand(String s) {
// Write your code here
if (s == null || s.length() == 0) {
return s;
}
Stack<Integer> nums = new Stack<>();
Stack<String> strs = new Stack<>();
int num = 0;
for (char c : s.toCharArray()) {
if (Character.isDigit(c)) {
num = num * 10 + c - '0';
} else if (c == '[') {
strs.push("[");
nums.push(num);
num = 0;
} else if (c == ']') {
Stack<String> out = new Stack<>();
while (!strs.isEmpty()) {
String topStr = strs.pop();
if (topStr.equals("[")) {
StringBuilder outStrs = new StringBuilder("");
StringBuilder outStr = new StringBuilder("");
while (!out.isEmpty()) {
outStr.append(out.pop());
}
if (!nums.isEmpty()) {
int times = nums.pop();
for (int i = 0; i < times; i++) {
outStrs.append(outStr);
}
}
strs.push(outStrs.toString());
break;
}
out.push(topStr);
}
} else {
strs.push(String.valueOf(c));
}
}
Stack<String> out = new Stack<>();
StringBuilder outStr = new StringBuilder("");
while (!strs.isEmpty()) {
String topStr = strs.pop();
out.push(topStr);
}
while (!out.isEmpty()) {
outStr.append(out.pop());
}
return outStr.toString();
}
}
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.
解法：分治法
/**
* 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 a, b, the root of binary trees.
* @return true if they are tweaked identical, or false.
*/
public boolean isTweakedIdentical(TreeNode a, TreeNode b) {
// Write your code here
if (a == null && b == null) {
return true;
}
if (a == null || b == null) {
return false;
}
if (a.val != b.val) {
return false;
}
return (isTweakedIdentical(a.left, b.left) &&
isTweakedIdentical(a.right, b.right)) ||
(isTweakedIdentical(a.left, b.right) &&
isTweakedIdentical(a.right, b.left));
}
}
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;
}
}
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);
}
}
inorder 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> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<Integer>();
if (root == null) {
return ans;
}
Stack<TreeNode> s = new Stack<>();
s.push(root);
while (!s.isEmpty()) {
while (root.left != null) {
root = root.left;
s.push(root);
}
TreeNode cur = s.pop();
ans.add(cur.val);
if (cur.right != null) {
s.push(cur.right);
root = cur.right;
}
}
return ans;
}
}
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);
}
}
postorder 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> postorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
if (root == null) {
return ans;
}
Stack<TreeNode> s = new Stack<>();
s.push(root);
while (!s.isEmpty()) {
TreeNode cur = s.pop();
ans.add(0, cur.val);
if (cur.left != null) {
s.push(cur.left);
}
if (cur.right != null) {
s.push(cur.right);
}
}
return ans;
}
}
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].
1.quickSort
public class Solution {
/**
* @param A an integer array
* @return void
*/
public void sortIntegers2(int[] A) {
// Write your code here
if (A == null || A.length == 0) {
return;
}
quickSort(A, 0, A.length - 1);
}
public void quickSort(int[] nums, int start, int end) {
if (start > end) {
return;
}
int left = start;
int right = end;
int pivot = nums[start + (end - start) / 2];
while (left <= right) {
while (left <= right && nums[left] < pivot) {
left++;
}
while (left <= right && nums[right] > pivot) {
right--;
}
if (left <= right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
quickSort(nums, start, right);
quickSort(nums, left, end);
}
}
2.mergeSort
public class Solution {
/**
* @param A an integer array
* @return void
*/
int[] temp = null;
public void sortIntegers2(int[] A) {
// Write your code here
if (A == null || A.length == 0) {
return;
}
temp = new int[A.length];
mergeSort(A, 0, A.length - 1);
}
public void mergeSort(int[] nums, int start, int end) {
if (start == end) {
return;
}
int mid = start + (end - start) / 2;
mergeSort(nums, start, mid);
mergeSort(nums, mid + 1, end);
merge(nums, start, end);
}
public void merge(int[] nums, int start, int end) {
int mid = start + (end - start) / 2;
for (int i = start; i <= end; i++) {
temp[i] = nums[i];
}
int left = start;
int right = mid + 1;
while (left <= mid && right <= end) {
if (temp[left] <= temp[right]) {
nums[start++] = temp[left++];
} else {
nums[start++] = temp[right++];
}
}
while (left <= mid) {
nums[start++] = temp[left++];
}
}
}
3.heapSort
public class Solution {
/**
* @param A an integer array
* @return void
*/
public void sortIntegers2(int[] A) {
// Write your code here
heapSort(A);
}
public void heapSort(int[] a) {
for (int i = a.length / 2 - 1; i >= 0; i--) {
createHeap(a, i, a.length - 1);
}
for (int i = a.length - 1; i > 0; i--) {
int temp = a[0];
a[0] = a[i];
a[i] = temp;
createHeap(a, 0, i - 1);
}
}
public void createHeap(int[] a, int i, int end) {
int l = 2 * i + 1;
while (l <= end) {
if (l + 1 <= end && a[l + 1] > a[l]) {
l = l + 1;
}
if (a[i] < a[l]) {
int temp = a[i];
a[i] = a[l];
a[l] = temp;
}
i = l;
l = 2 * i + 1;
}
}
}
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
解法：第一步先找到要删除的节点，并返回其父节点（所以要用到dummynode）；第二步删除该节点，多该节点右子树为空，则直接将左子节点替换，反之将右子树的最左节点替换
/**
* 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 the binary search tree.
* @param value: Remove the node with given value.
* @return: The root of the binary search tree after removal.
*/
public TreeNode removeNode(TreeNode root, int value) {
// write your code here
if (root == null) {
return root;
}
TreeNode dummy = new TreeNode(0);
dummy.left = root;
TreeNode parent = findNode(dummy, root, value);
if (parent.left != null && parent.left.val == value) {
deleteNode(parent, parent.left);
} else if (parent.right != null && parent.right.val == value) {
deleteNode(parent, parent.right);
} else {
return dummy.left;
}
return dummy.left;
}
public TreeNode findNode(TreeNode parent, TreeNode root, int value) {
if (root == null || root.val == value) {
return parent;
}
if (root.val < value) {
return findNode(root, root.right, value);
} else {
return findNode(root, root.left, value);
}
}
public void deleteNode(TreeNode parent, TreeNode node) {
if (node.right == null) {
if (parent.left == node) {
parent.left = node.left;
} else {
parent.right = node.left;
}
} else {
TreeNode father = node;
TreeNode child = node.right;
while (child.left != null) {
father = child;
child = child.left;
}
if (father.left == child) {
father.left = child.right;
} else {
father.right = child.right;
}
if (parent.left == node) {
parent.left = child;
} else {
parent.right = child;
}
child.right = node.right;
child.left = node.left;
}
}
}
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.
解法：
localSum从i到j的剩余汽油量，如果小于0，则意味着i到j不会有出发点，出发点就从i + 1开始，将localSum清零
sum是为了整个一圈的汽油剩余量，只有最后的sum > 0才会存在这个出发点
public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
if (gas == null || cost == null || gas.length == 0 || cost.length == 0) {
return -1;
}
int start = 0;
int localSum = 0;
int sum = 0;
//localSum从i到j的剩余汽油量，如果小于0，则意味着i到j不会有出发点，出发点就从i + 1开始
//sum是为了整个一圈的汽油剩余量，只有最后的sum > 0才会存在这个出发点
for (int i = 0; i < gas.length; i++) {
localSum += gas[i] - cost[i];
sum += gas[i] - cost[i];
if (localSum < 0) {
localSum = 0;
start = i + 1;
}
}
return sum >= 0 ? start : -1;
}
}
bug-free process
1. O(n)的解法，贪心法 2016/12/01
2.bug-free 2016/12/19
leetcode 140 Word Break II
题意：返回给定的字符串能被给定的词典里面的单词切分的全部方案
解法：dfs+hashmap。判断单词的前一部分能否在字典中找到，如果能，则继续判断剩余的部分，并将剩余部分的切分结果与前一部分组合起来，返回这个结果就是整体的切分方案。hashmap用来记录某个子字符串的分割方案，在下次遇到这个子字符串的时候就可以直接返回了。
public class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
return helper(s, wordDict, new HashMap<String, List<String>>());
}
public List<String> helper(String s, List<String> wordDict, HashMap<String, List<String>> map) {
if (map.containsKey(s)) {
return map.get(s);
}
List<String> res = new ArrayList<>();
if (s.length() == 0) {
res.add("");
return res;
}
for (String word : wordDict) {
if (s.startsWith(word)) {
List<String> list = helper(s.substring(word.length()), wordDict, map);
for (String l : list) {
res.add(word + (l.isEmpty() ? "" : " ") + l);
}
}
}
map.put(s, res);
return res;
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
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;
}
}
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;
}
}
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;
}
}
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.
解法：利用split(" ")，以空格" "作为分隔符对原字符串进行分割，将得到的字符串数组，逆向组合起来，并且每个字符串之间以空格分开，注意最后一个字符串的后面不要有空格。
值得记住的是spit(" ")遇到多个空格时，也会分割，只是分得的字符串为"",也就是长度为零的字符串，在这里要省去这些字符串，不要将其假如最后的结果中
public class Solution {
public String reverseWords(String s) {
if (s == null && s.length() == 0) {
return s;
}
String[] arrs = s.split(" ");
StringBuilder ans = new StringBuilder("");
for (int i = arrs.length - 1; i >= 0 ; i--) {
if (arrs[i].length() == 0) {
continue;
}
ans.append(arrs[i]);
ans.append(" ");
}
return ans.length() > 0 ? ans.substring(0, ans.length() - 1) : "";
}
}
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.
解法：动态规划，用两个数组分别记录以nums[i]结尾的子数组的最大乘积和最小乘积。判断当前nums[i]的正负性，根据以下规则更新两个数组
用最大的数乘以一个正数会得到最可能大的数
用最小的数乘以一个正数会得到最可能小的数
用最小的数乘以一个负数会得到最可能大的数
用最大的数乘以一个负数会得到最可能小的数
public class Solution {
public int maxProduct(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int len = nums.length;
//以nums[i]结尾的乘积最大子数组的乘积
int[] max = new int[len];
max[0] = nums[0];
//以nums[i]结尾的乘积最小子数组的乘积
int[] min = new int[len];
min[0] = nums[0];
int maxProduct = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] > 0) {
// 用最大的数乘以一个正数会得到最可能大的数
max[i] = Math.max(nums[i], max[i - 1] * nums[i]);
// 用最小的数乘以一个正数会得到最可能小的数
min[i] = Math.min(nums[i], min[i - 1] * nums[i]);
} else if (nums[i] < 0) {
// 用最小的数乘以一个负数会得到最可能大的数
max[i] = Math.max(nums[i], min[i - 1] * nums[i]);
// 用最大的数乘以一个负数会得到最可能小的数
min[i] = Math.min(nums[i], max[i - 1] * nums[i]);
} else {
//nums[i] = 0时，max[i] = min[i] = 0
max[i] = 0;
min[i] = 0;
}
maxProduct = Math.max(maxProduct, max[i]);
}
return maxProduct;
}
}
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:
解法：主要是想到该怎么实现除法，然后就是利用hashmap来记录余数与商的对应，余数的重复表示这小数部分循环的开始
public class Solution {
public String fractionToDecimal(int numerator, int denominator) {
if (denominator == 0) {
return null;
}
StringBuilder ans = new StringBuilder("");
if (numerator == 0) {
ans.append("0");
return ans.toString();
}
if (numerator > 0 && denominator < 0 || numerator < 0 && denominator > 0) {
ans.append('-');
}
long a = Math.abs((long) numerator);
long b = Math.abs((long) denominator);
//整数部分
long quotient = a / b;
a -= quotient * b;
ans.append(String.valueOf(quotient));
if (a != 0) {
ans.append(".");
} else {
return ans.toString();
}
//小数部分
int index = ans.length();
//记录每个余数对应的商在字符串中的位置
Map<Long, Integer> remainders = new HashMap<>();
remainders.put(a, index);
int start = -1;
while (a != 0) {
index++;
a *= 10;
quotient = a / b;
a -= quotient * b;
ans.append(String.valueOf(quotient));
//如果余数在之前出现过，则表示循环开始了，获取循环开始的位置
if (remainders.containsKey(a)) {
start = remainders.get(a);
ans.insert(start, '(');
ans.append(')');
return ans.toString();
}
remainders.put(a, index);
}
return ans.toString();
}
}
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]
]
思路：O(n^3)的时间复杂度，基于3sum的解法，相当于固定前两个数，对其余两个数用两指针方法。
public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<List<Integer>>();
for(int i =0;i<nums.length-3;i++){
if(i>0&&nums[i]==nums[i-1]){
continue;//重复的直接跳过
}
for(int j = i+1;j<nums.length-2;j++){
if(j>i+1&&nums[j]==nums[j-1]){
continue;//重复的直接跳过
}
int left = j+1;//从i+1开始也是防止重复的办法
int right = nums.length-1;
while(left<right){
if(nums[left]+nums[right]+nums[i]+nums[j] == target){
List<Integer> temp = new ArrayList<Integer>();//必须每次新建
temp.add(nums[i]);
temp.add(nums[left]);
temp.add(nums[right]);
temp.add(nums[j]);
Collections.sort(temp);
result.add(temp);
//特别注意下面两个while循环
left++;
right--;//防止重复
while(left<right&&nums[left]==nums[left-1]){
left++;//防止重复
}
while(left<right&&nums[right]==nums[right+1]){
right--;//防止重复
}
//这两个条件特别重要，思考一下为何分别是left++和right--;
}else if(nums[left]+nums[right]+nums[i]+nums[j]<target){
left++;
}else{
right--;
}
}
}
}
return result;
}
}
优化过的代码，提前排除了一些不可能的情况，减少循环次数，但是时间复杂度是不变的。
public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
int len = nums.length;
if (nums == null || len < 4)
return res;
Arrays.sort(nums);
int max = nums[len - 1];
if (4 * nums[0] > target || 4 * max < target)
return res;
int i, z;
for (i = 0; i < len; i++) {
z = nums[i];
if (i > 0 && z == nums[i - 1])// avoid duplicate
continue;
if (z + 3 * max < target) // z is too small
continue;
if (4 * z > target) // z is too large
break;
if (4 * z == target) { // z is the boundary
if (i + 3 < len && nums[i + 3] == z)
res.add(Arrays.asList(z, z, z, z));
break;
}
threeSumForFourSum(nums, target - z, i + 1, len - 1, res, z);
}
return res;
}
/*
* Find all possible distinguished three numbers adding up to the target
* in sorted array nums[] between indices low and high. If there are,
* add all of them into the ArrayList fourSumList, using
* fourSumList.add(Arrays.asList(z1, the three numbers))
*/
public void threeSumForFourSum(int[] nums, int target, int low, int high, ArrayList<List<Integer>> fourSumList,
int z1) {
if (low + 1 >= high)
return;
int max = nums[high];
if (3 * nums[low] > target || 3 * max < target)
return;
int i, z;
for (i = low; i < high - 1; i++) {
z = nums[i];
if (i > low && z == nums[i - 1]) // avoid duplicate
continue;
if (z + 2 * max < target) // z is too small
continue;
if (3 * z > target) // z is too large
break;
if (3 * z == target) { // z is the boundary
if (i + 1 < high && nums[i + 2] == z)
fourSumList.add(Arrays.asList(z1, z, z, z));
break;
}
twoSumForFourSum(nums, target - z, i + 1, high, fourSumList, z1, z);
}
}
/*
* Find all possible distinguished two numbers adding up to the target
* in sorted array nums[] between indices low and high. If there are,
* add all of them into the ArrayList fourSumList, using
* fourSumList.add(Arrays.asList(z1, z2, the two numbers))
*/
public void twoSumForFourSum(int[] nums, int target, int low, int high, ArrayList<List<Integer>> fourSumList,
int z1, int z2) {
if (low >= high)
return;
if (2 * nums[low] > target || 2 * nums[high] < target)
return;
int i = low, j = high, sum, x;
while (i < j) {
sum = nums[i] + nums[j];
if (sum == target) {
fourSumList.add(Arrays.asList(z1, z2, nums[i], nums[j]));
x = nums[i];
while (++i < j && x == nums[i]) // avoid duplicate
;
x = nums[j];
while (i < --j && x == nums[j]) // avoid duplicate
;
}
if (sum < target)
i++;
if (sum > target)
j--;
}
return;
}
}
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).
思路：依然是先将数组排序，再固定一个数，用两指针方法求另外两个数之和与当前固定数之和，得出最接近的。
public class Solution {
public int threeSumClosest(int[] num, int target) {
int result = num[0] + num[1] + num[num.length - 1];
Arrays.sort(num);
for (int i = 0; i < num.length - 2; i++) {
int start = i + 1, end = num.length - 1;
while (start < end) {
int sum = num[i] + num[start] + num[end];
if (sum > target) {
end--;
} else {
start++;
}
if (Math.abs(sum - target) < Math.abs(result - target)) {
result = sum;
}
}
}
return result;
}
}
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]
]
思路：先将数组排序，然后遍历数组，每次固定一个数，将3sum转化为2sum，a + b + C = 0，也就是a + b = -C。每次固定c的时候看c之后的两个数字之和是否等于-c，不用再往回找，因为往回找是重复的。时间复杂度O(n^2).还要注意去除重复的结果。
public class Solution {
public List<List<Integer>> threeSum(int[] nums) {
if (nums == null || nums.length == 0) {
return new ArrayList<List<Integer>>();
}
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
List<Integer> triple;
for (int i = 0; i < nums.length - 2; i++) {
if (i == 0 || (i != 0 && nums[i] != nums[i - 1])) {
int left = i + 1;
int right = nums.length - 1;
int sum = 0 - nums[i];
while (left < right) {
if (nums[left] + nums[right] == sum) {
triple = new ArrayList<>();
triple.add(nums[i]);
triple.add(nums[left]);
triple.add(nums[right]);
ans.add(triple);
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while(left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
} else if (nums[left] + nums[right] < sum) {
left++;
} else {
right--;
}
}
}
}
return ans;
}
}
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.
解法：这是未排序的数组，如果先排序再求解则速度太慢。技巧是用hashMap保存遍历过的数值和索引，每次去hashmap中查找是否存在target-nums[i]的数值。
时间复杂度O(n),空间复杂度O(n)
public class Solution {
public int[] twoSum(int[] nums, int target) {
int[] ans = new int[2];
if (nums == null) {
return ans;
}
int len = nums.length;
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < len; i++) {
if (map.containsKey(target - nums[i])) {
int index = map.get(target - nums[i]);
ans[0] = Math.min(index, i);
ans[1] = Math.max(index, i);
return ans;
} else {
map.put(nums[i], i);
}
}
return ans;
}
}
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
解法：俩指针初始分别指向头和尾。俩数和大于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;
}
}
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.
解法：其实就是二叉树的中序遍历的非递归形式。其中hasNext()对应着非递归形式中最外层while循环。next()对应着里面的入栈出栈操作。
这里的时间复杂度是值的平均时间复杂度。调用n次next()是O(n)的时间，所以每次是O(1)，空间复杂度也就是栈是O(h)
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/ public class BSTIterator {
TreeNode cur = null;
Stack<TreeNode> stack = new Stack<>();;
public BSTIterator(TreeNode root) {
cur = root;
} /** @return whether we have a next smallest number */
public boolean hasNext() {
if (!stack.isEmpty() || cur != null) {
return true;
}
return false;
} /** @return the next smallest number */
public int next() {
while (cur!= null) {
stack.push(cur);
cur = cur.left;
}
TreeNode next = stack.pop();
cur = next.right;
return next.val;
}
} /**
* Your BSTIterator will be called like this:
* BSTIterator i = new BSTIterator(root);
* while (i.hasNext()) v[f()] = i.next();
*/
2.lintcode 上做过一遍，这次又忘了。2016/12/04
leetcode 179. Largest Number
题意：
Given a list of non negative integers, arrange them such that they form the largest number. For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330. Note: The result may be very large, so you need to return a string instead of an integer.
解法：自定义比较器。先将整数转化为字符串，再用字符串来实现比较器。比较两个字符串的和的字典序。
public class Solution {
public class MyComparator implements Comparator<String> {
public int compare(String a, String b) {
return (b + a).compareTo(a + b);
}
}
public String largestNumber(int[] nums) {
StringBuilder ans = new StringBuilder();
if (nums == null || nums.length == 0) {
return ans.toString();
}
int len = nums.length;
String[] strs = new String[len];
for (int i = 0; i < len; i++) {
strs[i] = String.valueOf(nums[i]);
}
Arrays.sort(strs, new MyComparator());
for (int i = 0; i < len; i++) {
ans.append(strs[i]);
}
int start = 0;
while (start < ans.length() && ans.charAt(start) == '0') {
start++;
}
if (start == ans.length()) {
return "0";
}
return ans.substring(start);
}
}
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"].
解法：
1.普通解法：利用两个hashset a和b a用于记录，b用于产生结果。从第十位字符开始向后遍历整个字符串，判断长度为10的字符串是否在a出现过，没有则加入hashset a，有的话则加入结果hashset b。
结果集一定要用hashset，不能用链表，用链表会出现重复。
public class Solution {
public List<String> findRepeatedDnaSequences(String s) {
List<String> ans = new ArrayList<>();
if (s == null) {
return ans;
}
HashSet<String> dnas = new HashSet<>();
for (int i = 9; i < s.length(); i++) {
String sub = s.substring(i - 9, i + 1);
if (dnas.contains(sub) && !ans.contains(sub)) {
ans.add(sub);
} else {
dnas.add(sub);
}
}
return ans;
}
}
2.优化解法结合hashset和bit manipulation 。
00,01,10,11分别代表'A','C','G','T'，可以用20个bit位来代表长度为10的子字符串。相当于将字符串重新编码了。可以减少substring的调用次数，加快效率。
public class Solution {
public List<String> findRepeatedDnaSequences(String s) {
int len = s.length();
if (len < 11) {
return new ArrayList<String>();
}
//00,01,10,11分别代表'A','C','G','T'，可以用20个bit位来代表长度为10的子字符串
int[] bit = new int[20];
bit['C' - 'A'] = 1;
bit['G' - 'A'] = 2;
bit['T' - 'A'] = 3;
int cur = 0;
int mask = 0x000fffff;
HashSet<String> ans = new HashSet<>();
HashSet<Integer> nums = new HashSet<>();
for (int i = 0; i < len; i++) {
cur <<= 2;
cur |= bit[s.charAt(i) - 'A'];
if (i < 9) {
continue;
}
//只保留后20位，前12位清零
cur &= mask;
if (!nums.add(cur)) {
ans.add(s.substring(i - 9, i + 1));
}
}
return new ArrayList<>(ans);
}
}
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].
解法：分层遍历，每次取最右边的那个节点
/**
* 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> rightSideView(TreeNode root) {
if (root == null) {
return new ArrayList<Integer>();
}
List<Integer> ans = new ArrayList<Integer>();
Queue<TreeNode> qu= new LinkedList<>();
qu.offer(root);
while (!qu.isEmpty()) {
int size = qu.size();
for (int i = 0; i < size; i++) {
TreeNode cur = qu.poll();
if (i == size - 1) {
ans.add(cur.val);
}
if (cur.left != null) {
qu.offer(cur.left);
}
if (cur.right != null) {
qu.offer(cur.right);
}
}
}
return ans;
}
}
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]
解法：将出现过的位置变为负的
1.遍历数组，当前元素为n，则nums[Math.abs(n) - 1] = - Math.abs(nums[Math.abs(n) - 1]);
2.再次遍历，将不为负数的位置加入list中
public class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
if (nums == null || nums.length == 0) {
return new ArrayList<Integer>();
}
int len = nums.length;
for (int i = 0; i < len; i++) {
int index = Math.abs(nums[i]) - 1;
nums[index] = -Math.abs(nums[index]);
}
List<Integer> ans = new ArrayList<Integer>();
for (int i = 0; i < len; i++) {
if (nums[i] > 0) {
ans.add(i + 1);
}
}
return ans;
}
}
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.
解法：仔细观察可以发现规律，最后的结果是所有数字的最左边的共同部分
比如来看一个范围[26, 30]，它们的二进制如下：
010 011 100 101 110
左边的共同部分是11，所以最后结果是11000
所以先将m和n向右移，直到m和n相等，假设右移了i位，则最后结果为m<<i.
1.非递归的解法
public class Solution {
public int rangeBitwiseAnd(int m, int n) {
int shift = 0;
while (m != n) {
m >>= 1;
n >>= 1;
shift++;
}
return m << shift;
}
}
2.递归解法
public class Solution {
public int rangeBitwiseAnd(int m, int n) {
if (m == n) {
return n;
}
return rangeBitwiseAnd(m / 2, n / 2) << 1;
}
}
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 -> Bin 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.
Have you met this question in a real interview?
Yes
Clarification
Example
For graph as follow:
The topological order can be:
[0, 1, 2, 3, 4, 5]
[0, 2, 3, 1, 5, 4]
解法：为每个节点增加入度这一参数，使用hashmap建立映射关系
首先遍历所有节点，将其邻居的入度加一 ，当某一个节点加入拓扑排序后，将其所有邻居的入度减一
有向图是无法从一个节点找到所有节点的，所以这里给出的参数是节点的列表，无向图只要是连通的就可以由一个节点找到所有节点
/**
* Definition for Directed graph.
* class DirectedGraphNode {
* int label;
* ArrayList<DirectedGraphNode> neighbors;
* DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
* };
*/
public class Solution {
/**
* @param graph: A list of Directed graph node
* @return: Any topological order for the given graph.
*/
public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
// write your code here
ArrayList<DirectedGraphNode> answer = new ArrayList<>();
if (graph == null || graph.size() == 0) {
return answer;
} HashMap<DirectedGraphNode, Integer> inDegreeMap = new HashMap<>(); for (DirectedGraphNode node : graph) {
for (DirectedGraphNode neighbor : node.neighbors) {
if (inDegreeMap.containsKey(neighbor)) {
inDegreeMap.put(neighbor, inDegreeMap.get(neighbor) + 1);
} else {
inDegreeMap.put(neighbor, 1);
}
}
} Queue<DirectedGraphNode> queue = new LinkedList<>();
for (DirectedGraphNode node : graph) {
if (!inDegreeMap.containsKey(node)) {
answer.add(node);
queue.offer(node);
}
} while (!queue.isEmpty()) {
DirectedGraphNode node = queue.poll();
for (DirectedGraphNode neighbor : node.neighbors) {
inDegreeMap.put(neighbor, inDegreeMap.get(neighbor) - 1);
if (inDegreeMap.get(neighbor) == 0) {
answer.add(neighbor);
queue.offer(neighbor);
}
}
} return answer;
}
}
leetcode 207. Course Schedule
题意：
There are a total of n courses you have to take, labeled from 0 to n - 1. 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] Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses? For example: 2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible. 2, [[1,0],[0,1]]
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. Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented. click to show more hints. Hints:
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.
Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
Topological sort could also be done via BFS.
解法：可以根据上一题lintcode 127 Topological Sorting来求解，只不过要在拓扑排序之后判断图中是否存在环，若存在环，则返回false，反之返回true。
回顾一下图的三种表示方式：边表示法（即题目中表示方法），邻接表法，邻接矩阵。我们要用邻接表来表示图，来实现拓扑排序，找出最后是否存在入度不为0的节点，若存在则有环。
public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
if (prerequisites == null || prerequisites.length == 0) {
return true;
}
int m = prerequisites.length;
int[] inDegree = new int[numCourses];
//构建邻接表adjacency lists表示图
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<Integer>());
}
for (int i = 0; i < m; i++) {
graph.get(prerequisites[i][0]).add(prerequisites[i][1]);
}
//入度加一
for (int i = 0; i < m; i++) {
inDegree[prerequisites[i][1]]++;
}
Queue<Integer> qu = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
qu.offer(i);
}
}
while (!qu.isEmpty()) {
int node = qu.poll();
for (int neighbors : graph.get(node)) {
//入度减一
inDegree[neighbors]--;
if (inDegree[neighbors] == 0) {
qu.offer(neighbors);
}
}
}
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] > 0) {
return false;
}
}
return true;
}
}
1. 忘了拓扑排序是怎么回事了。 2016/12/06
leetcode 210. Course Schedule II
题意：
There are a total of n courses you have to take, labeled from 0 to n - 1. 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] Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses. There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array. For example: 2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1] 4, [[1,0],[2,0],[3,1],[3,2]]
There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3]. Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented. click to show more hints. Hints:
This problem is equivalent to finding the topological order in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
Topological sort could also be done via BFS.
解法：所求即为拓扑排序的逆序。注意当变列表为空的时候，也就是每门课程都没有依赖课程，这时候返回的是任意顺序就行了。
public class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
if (prerequisites == null) {
return new int[0];
}
int m = prerequisites.length;
//转化为邻接表表示法
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<Integer>());
}
for (int i = 0; i < m; i++) {
graph.get(prerequisites[i][0]).add(prerequisites[i][1]);
}
//入度加一
int[] inDegree = new int[numCourses];
for (int i = 0; i < m; i++) {
inDegree[prerequisites[i][1]]++;
}
//入度为0的先加入队列中
Queue<Integer> qu = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
qu.offer(i);
}
}
//构建拓扑排序的逆序，即题目要求的结果
int[] reverseTopSort = new int[numCourses];
int index = numCourses - 1;
while (!qu.isEmpty()) {
int cur = qu.poll();
reverseTopSort[index--] = cur;
for (int neighbor : graph.get(cur)) {
//入度减一
inDegree[neighbor]--;
if (inDegree[neighbor] == 0) {
qu.offer(neighbor);
}
}
}
//存在环
if (index != -1) {
return new int[0];
}
return reverseTopSort;
}
}
1.prerequisites为空的时候，不能返回空数组。2016/12/07
leetcode 208. Implement Trie (Prefix Tree)--面试题
题意：
Implement a trie with insert, search, and startsWith methods.
解法：
1.用数组实现（递归），比较简单而且更优化 wordEnd = true表示一个单词的结束。当一个单词结束时，这条边对应的子节点wordEnd = true
class TrieNode {
// Initialize your data structure here.
private TrieNode[] children = new TrieNode[26];
boolean wordEnd = false;
public TrieNode() {
}
// Inserts a word into the trie.
public void insert(String word, int index) {
if (index == word.length()) {
wordEnd = true;
return;
}
char cur = word.charAt(index);
if (children[cur - 'a'] == null) {
children[cur - 'a'] = new TrieNode();
}
children[cur - 'a'].insert(word, index + 1);
}
public boolean search(String word, int index) {
if (index == word.length()) {
return wordEnd;
}
char cur = word.charAt(index);
if (children[cur - 'a'] == null) {
return false;
}
return children[cur - 'a'].search(word, index + 1);
}
// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String word, int index) {
if (index == word.length()) {
return true;
}
char cur = word.charAt(index);
if (children[cur - 'a'] == null) {
return false;
}
return children[cur - 'a'].startsWith(word, index + 1);
}
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
public void insert(String word) {
if (word == null || word.length() == 0) {
return;
}
root.insert(word, 0);
}
// Returns if the word is in the trie.
public boolean search(String word) {
if (word == null || word.length() == 0) {
return false;
}
return root.search(word, 0);
}
// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
if (prefix == null || prefix.length() == 0) {
return false;
}
return root.startsWith(prefix, 0);
}
}
// Your Trie object will be instantiated and called as such:
// Trie trie = new Trie();
// trie.insert("somestring");
// trie.search("key");
2.用数组实现（非递归），比递归更加优化
class TrieNode {
// Initialize your data structure here.
private TrieNode[] children = new TrieNode[26];
boolean wordEnd = false;
public TrieNode() {
}
// Inserts a word into the trie.
public void insert(String word) {
TrieNode cur = this;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (cur.children[c - 'a'] == null) {
cur.children[c - 'a'] = new TrieNode();
}
cur = cur.children[c - 'a'];
}
cur.wordEnd = true;
}
public boolean search(String word) {
TrieNode cur = this;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (cur.children[c - 'a'] == null) {
return false;
}
cur = cur.children[c - 'a'];
}
return cur.wordEnd;
}
// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String word) {
TrieNode cur = this;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (cur.children[c - 'a'] == null) {
return false;
}
cur = cur.children[c - 'a'];
}
return true;
}
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
public void insert(String word) {
if (word == null || word.length() == 0) {
return;
}
root.insert(word);
}
// Returns if the word is in the trie.
public boolean search(String word) {
if (word == null || word.length() == 0) {
return false;
}
return root.search(word);
}
// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
if (prefix == null || prefix.length() == 0) {
return false;
}
return root.startsWith(prefix);
}
}
// Your Trie object will be instantiated and called as such:
// Trie trie = new Trie();
// trie.insert("somestring");
// trie.search("key");
3.hashmap实现（递归）
class TrieNode {
// Initialize your data structure here.
Map<Character, TrieNode> children = null;
boolean wordEnd = false;
public TrieNode() {
children = new HashMap<>();
}
public void insert(String word) {
if (word.length() == 0) {
wordEnd = true;
return;
}
char first = word.charAt(0);
if (!children.containsKey(first)) {
children.put(first, new TrieNode());
}
String next = word.substring(1);
children.get(first).insert(next);
}
// Returns if the word is in the trie.
public boolean search(String word) {
if (word.length() == 0) {
return wordEnd;
}
char first = word.charAt(0);
if (!children.containsKey(first)) {
return false;
} else {
String next = word.substring(1);
return children.get(first).search(next);
}
}
// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String word) {
if (word.length() == 0) {
return true;
}
char first = word.charAt(0);
if (!children.containsKey(first)) {
return false;
} else {
String next = word.substring(1);
return children.get(first).startsWith(next);
}
}
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
public void insert(String word) {
if (word == null || word.length() == 0) {
return;
}
root.insert(word);
}
// Returns if the word is in the trie.
public boolean search(String word) {
if (word == null || word.length() == 0) {
return false;
}
return root.search(word);
}
// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
if (prefix == null || prefix.length() == 0) {
return false;
}
return root.startsWith(prefix);
}
}
// Your Trie object will be instantiated and called as such:
// Trie trie = new Trie();
// trie.insert("somestring");
// trie.search("key");
解题过程
3.第三次做了，还是出现了bug，下次用非递归实现。将wordEnd的位置放错，我放在了父节点上，应该放在子节点上。也就是说当一个单词结束时，这条边对应的子节点wordEnd = true 2016/12/08
leetcode 211. Add and Search Word - Data structure design
题意：也就是trie树的一个应用
Design a data structure that supports the following two operations: void addWord(word)
bool search(word)
search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter. For example: addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
Note:
You may assume that all words are consist of lowercase letters a-z. click to show hint. You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first.
解法：插入与之前trie树的一样了，用的是非递归的方法。查找的话如果遇到了'.'，就需要遍历每一棵子树
public class WordDictionary {
// Adds a word into the data structure.
TrieNode root = new TrieNode();
public void addWord(String word) {
if (word == null || word.length() == 0) {
return;
}
root.insert(word);
}
// Returns if the word is in the data structure. A word could
// contain the dot character '.' to represent any one letter.
public boolean search(String word) {
if (word == null || word.length() == 0) {
return false;
}
return root.search(word, 0);
}
}
class TrieNode {
// Initialize your data structure here.
private TrieNode[] children = new TrieNode[26];
boolean wordEnd = false;
public TrieNode() {
}
// Inserts a word into the trie.
public void insert(String word) {
TrieNode cur = this;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (cur.children[c - 'a'] == null) {
cur.children[c - 'a'] = new TrieNode();
}
cur = cur.children[c - 'a'];
}
cur.wordEnd = true;
}
public boolean search(String word, int index) {
if (index == word.length()) {
return wordEnd;
}
char cur = word.charAt(index);
if (cur == '.') {
for (int i = 0; i < 26; i++) {
if (children[i] != null && children[i].search(word, index + 1)) {
return true;
}
}
return false;
}
if (children[cur - 'a'] == null) {
return false;
}
return children[cur - 'a'].search(word, index + 1);
}
}
// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary = new WordDictionary();
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");
解题过程
1.bug-free 2016/12/08
leetcode 198. House Robber
题意：
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
解法：动态规划。dp[i]表示以到nums[i]位置时抢劫到的最多的钱.nums[i]有不抢和抢两种选择，取其中的最大值即可，dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])。
public class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int len = nums.length;
if (len == 1) {
return nums[0];
}
//dp[i]表示以到nums[i]位置时抢劫到的最多的钱
int[] dp = new int[len];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < len; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[len - 1];
}
}
优化：将额外空间优化为常数级。mod 2的做法，这个方法很通用，一定要记住。
public class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int len = nums.length;
if (len == 1) {
return nums[0];
}
//dp[i]表示以到nums[i]位置时抢劫到的最多的钱
int[] dp = new int[2];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < len; i++) {
dp[i % 2] = Math.max(dp[(i - 1) % 2], dp[(i - 2) % 2] + nums[i]);
}
return dp[(len - 1) % 2];
}
}
解题过程
2.一年前做的，现在果然就不会了。动态规划的做法 2016/12/09
leetcode 213. House Robber II
题意：
Note: This is an extension of House Robber. After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street. Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
解法：结合robI使用动态规划。
因为第一位和最后一位也是邻居，所以第一位和最后一位不能同时抢劫。可以分两种情况：
1.抢劫的范围是从第一位到倒数第二位
2.抢劫的范围是从第二位到最后一位
去这两种情况的较大值，也就是最后的结果。这两种情况也就是跟robI一样的情况了，只是数组的开始结束位置做了改变，稍微改变一下robI的代码就可以了。
public class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int len = nums.length;
if (len == 1) {
return nums[0];
}
//取从第一位开始到倒数第二位结束的结果与从第二位开始到最后一位结束的结果得较大值
return Math.max(rob1(nums, 0, len - 2), rob1(nums, 1, len - 1));
}
//这就是robI的解法了
public int rob1(int[] nums, int start, int end) {
if (start == end) {
return nums[start];
}
int[] dp = new int[2];
dp[0] = nums[start];
dp[1] = Math.max(nums[start + 1], nums[start]);
for (int i = 2; i < (end - start + 1); i++) {
dp[i % 2] = Math.max(dp[(i - 1) % 2], dp[(i - 2) % 2] + nums[start + i]);
}
return dp[(end - start) % 2];
}
}
解题过程
1.第一次做，没想出来 2016/12/09
leetcode 337. House Robber III
题意：
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night. Determine the maximum amount of money the thief can rob tonight without alerting the police. Example 1:
3
/ \
2 3
\ \
3 1
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
3
/ \
4 5
/ \ \
1 3 1
Maximum amount of money the thief can rob = 4 + 5 = 9.
解法：对每一个节点有两种选择，偷或者不偷。递归向下，now[0]表示当前根节点不偷，now[1]表示当前根节点偷
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int rob(TreeNode root) {
int[] res = robHelper(root);
return Math.max(res[0], res[1]);
}
public int[] robHelper(TreeNode root) {
int[] now = new int[2];
if (root == null) {
return now;
}
int[] left = robHelper(root.left);
int[] right = robHelper(root.right);
//now[0]表示当前根节点不偷，now[1]表示当前根节点偷
now[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
now[1] = left[0] + right[0] + root.val;
return now;
}
}
1。没有想出来，其实九章给出的两种答案是一种解法。2016/12/09
leetcode 378. Kth Smallest Element in a Sorted Matrix
题意：
Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix. Note that it is the kth smallest element in the sorted order, not the kth distinct element. Example: matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8, return 13.
Note:
You may assume k is always valid, 1 ≤ k ≤ n2.
解法：
1.最优解法二分法。以数据范围作为二分的空间。每次去计算矩阵中小于等于中位数的数的个数。
若个数小于k，则start = mid+ 1（也即是所求肯定大于中位数）；反之，end = mid - 1，同时记录可能的ans = mid（也就是说ans最大可能等于mid，再去mid-1之前去找，若找到则更新），最后返回ans。
时间复杂度为nlog(x) ,n为矩阵元素个数，x为最大值与最小值的差值
public class Solution {
public int kthSmallest(int[][] matrix, int k) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return -1;
}
int m = matrix.length;
int n = matrix[0].length;
int start = matrix[0][0];
int end = matrix[m - 1][n - 1];
int ans = 0;
while(start <= end) {
int mid = start + (end - start) / 2;
int count = 0;
int j = n - 1;
for (int i = 0; i < m; i++) {
while (j >= 0 && matrix[i][j] > mid) {
j--;
}
count += j + 1;
}
if (count < k) {
start = mid + 1;
} else {
ans = mid;
end = mid - 1;
}
}
return ans;
}
}
2.次优解法：优先队列。
a.先将第一行的每个元素加入优先队列（或者第一列）
b.执行k-1次：将队头元素poll出来，并且offer进去这个元素的同一列的下一行（上一步若是第一列，则是同一行的下一列）。
c.上一步需要位置信息，所以可以自定义一个类，并且实现优先队列的比较器。
实际上这个过程是poll了最小的k-1个数出来，那么第k个数就是下一个队头元素了。时间复杂度为klog(col),col为行数（klog(row),row为行数），第一步是选择第一行还是第一列可以比较一下选择较小值。
public class Solution {
public int kthSmallest(int[][] matrix, int k) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return -1;
}
int m = matrix.length;
int n = matrix[0].length;
PriorityQueue<Tuple> pq = new PriorityQueue<>(new MyComparator());
for (int i = 0; i < n; i++) {
pq.offer(new Tuple(0, i, matrix[0][i]));
}
for (int i = 0; i < k - 1; i++) {
Tuple t = pq.poll();
if (t.row == m - 1) {
continue;
}
pq.offer(new Tuple(t.row + 1, t.col, matrix[t.row + 1][t.col]));
}
return pq.poll().val;
}
}
class Tuple {
int row = 0;
int col = 0;
int val = 0;
public Tuple(int row, int col, int val) {
this.row = row;
this.col = col;
this.val = val;
}
}
class MyComparator implements Comparator<Tuple> {
public int compare(Tuple t1, Tuple t2) {
return t1.val - t2.val;
}
}
1.最优解法 2016/12/10
leetcode 373. Find K Pairs with Smallest Sums
题意：
You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k. Define a pair (u,v) which consists of one element from the first array and one element from the second array. Find the k pairs (u1,v1),(u2,v2) ...(uk,vk) with the smallest sums. Example 1:
Given nums1 = [1,7,11], nums2 = [2,4,6], k = 3 Return: [1,2],[1,4],[1,6] The first 3 pairs are returned from the sequence:
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
Example 2:
Given nums1 = [1,1,2], nums2 = [1,2,3], k = 2 Return: [1,1],[1,1] The first 2 pairs are returned from the sequence:
[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
Example 3:
Given nums1 = [1,2], nums2 = [3], k = 3 Return: [1,3],[2,3] All possible pairs are returned from the sequence:
[1,3],[2,3]
解法：优先队列。与上一题378相似的解法。
public class Solution {
public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<int[]> ans = new ArrayList<int[]>();
if (nums1 == null || nums2 == null) {
return ans;
}
int m = nums1.length;
int n = nums2.length;
if (m == 0 || n == 0) {
return ans;
}
PriorityQueue<Tuple> pq = new PriorityQueue<Tuple>(new MyComparator());
for (int i = 0; i < n; i++) {
pq.offer(new Tuple(0, i, nums1[0] + nums2[i]));
}
int min = Math.min(k, m * n);
for (int i = 0; i < min; i++) {
Tuple t = pq.poll();
ans.add(new int[]{nums1[t.row], nums2[t.col]});
if (t.row == m - 1) {
continue;
}
pq.offer(new Tuple(t.row + 1, t.col, nums1[t.row + 1] + nums2[t.col]));
}
return ans;
}
}
class Tuple {
int row = 0;
int col = 0;
int val = 0;
public Tuple(int row, int col, int val) {
this.row = row;
this.col = col;
this.val = val;
}
}
class MyComparator implements Comparator<Tuple> {
public int compare(Tuple t1, Tuple t2) {
return t1.val - t2.val;
}
}
解题过程：
1.优先队列的解法。2016/12/10
leetciode 215. Kth Largest Element in an Array
题意：
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element. For example,
Given [3,2,1,5,6,4] and k = 2, return 5. Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.
解法：1.优先队列 时间复杂度为O(n)logk
public class Solution {
public int findKthLargest(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return 0;
}
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i = 0; i <nums.length; i++) {
pq.offer(nums[i]);
if (pq.size() > k) {
pq.poll();
}
}
return pq.poll();
}
}
2.更加优化的quick select 快速选择算法 ，将quicksort修改一下，每次只查找左右两部分的其中一个。平均时间复杂度能到O(n),最坏时间复杂度为O(n^2)。
可以参考：https://en.wikipedia.org/wiki/Quickselect
在start~end的数组范围内找第k大的数。
如果大于等于轴元素的个数大于等于k个，那就去右半边找第k大的，反之，去左半边找第k - (end - left + 1)大的
注意left和right相差一位和两位是不同的情况
public class Solution {
public int findKthLargest(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return 0;
}
return quickSelect(nums, 0, nums.length - 1, k);
}
//在start~end的数组范围内找第k大的数
public int quickSelect(int[] nums, int start, int end, int k) {
if (start == end) {
return nums[end];
}
int pivot = nums[start + (end - start) / 2];
int left = start;
int right = end;
while (left <= right) {
while (nums[left] < pivot && left <= right) {
left++;
}
while (nums[right] > pivot && left <= right) {
right--;
}
if (left <= right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
//如果大于等于轴元素的个数大于等于k个，那就去右半边找第k大的，反之，去左半边找第k - (end - left + 1)大的
if (end - left + 1 >= k) {
return quickSelect(nums, left, end, k);
} else if (left - right == 1){
//left和right相差一位的时候，
return quickSelect(nums, start, right, k - (end - left + 1));
} else {
//left和right相差两位的时候
return quickSelect(nums, start, right + 1, k - (end - left + 1));
}
}
}
解题过程：
1.优先队列解法 bug-free ,quick select 方法还可以练一次2016/12/12
2.quick select bug-free 2012/12/22
leetcode 220. Contains Duplicate III
题意：
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.
解法：treeset (bst) treeset和treemap都是平衡bst
public class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (nums == null || nums.length == 0) {
return false;
}
TreeSet<Integer> set = new TreeSet<>();
for (int i = 0; i < nums.length; i++) {
Integer ceil = set.ceiling(nums[i] - t);
Integer floor = set.floor(nums[i] + t);
if ((ceil != null && ceil <= nums[i]) ||
(floor != null && floor >= nums[i])) {
return true;
}
set.add(nums[i]);
if (i >= k) {
set.remove(nums[i - k]);
}
}
return false;
}
}
解题过程
1.treeset 的用法，treemap没有treeset速度快 2016/12/12
leetcode 221. Maximal Square
题意：注意是正方形
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area. For example, given the following matrix: 1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 4.
解法：动态规划。以matrix[i][j]为右下角的正方形的最大边长 sideLen[i][j] = Math.min(sideLen[i - 1][j - 1], Math.min(sideLen[i - 1][j], sideLen[i][j - 1])) + 1;
public class Solution {
public int maximalSquare(char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
int m = matrix.length;
int n = matrix[0].length;
int maxLen = 0;
int[][] sideLen = new int[m][n];
for (int i = 0; i < m; i++) {
sideLen[i][0] = matrix[i][0] - '0';
if (sideLen[i][0] == 1) {
maxLen = 1;
}
}
for (int i = 0; i < n; i++) {
sideLen[0][i] = matrix[0][i] - '0';
if (sideLen[0][i] == 1) {
maxLen = 1;
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == '1') {
sideLen[i][j] = Math.min(sideLen[i - 1][j - 1], Math.min(sideLen[i - 1][j], sideLen[i][j - 1])) + 1;
maxLen = Math.max(maxLen, sideLen[i][j]);
}
}
}
return maxLen * maxLen;
}
}
解题过程：
1.没有想到。 2016/12/12
leetcode 222. Count Complete Tree Nodes
题意：
Given a complete binary tree, count the number of nodes. Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
解法：非递归的做法。
1.获得树的高度h（高度从0开始计数），只要不断的往左子树递归就可以了。空节点返回-1；
2.判断右子树的高度是否 为当前根节点高度减一 （h - 1）：
a.如果是的。说明最后一层的最后一个节点在右子树上。所以将总结点数加上左子树（左子树h-1层）的节点数目 (2^h) - 1 + 1(加一是根节点),将当前节点置为右子树根节点。
b.如果不是。说明最后一层的最后一个节点在左子树上。所以将总结点数加上右子树（右子树h-2层）的节点数目 (2^(h-1)) - 1 + 1(加一是根节点),将当前节点置为左子树根节点。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int height(TreeNode root) {
return root == null ? -1 : 1 + height(root.left);
}
public int countNodes(TreeNode root) {
int nodes = 0, h = height(root);
while (root != null) {
if (height(root.right) == h - 1) {
nodes += 1 << h;
root = root.right;
} else {
nodes += 1 << h-1;
root = root.left;
}
h--;
}
return nodes;
}
}
解题过程：
1.遍历的做法是tle的，记住树的节点数的计算方法，高度从0开始，高度为h的层，节点数为2^h,前h层节点数为2^(h + 1) - 1。2016/12/12.