walterzhu29 / cplusplus-leetcode-solution Goto Github PK
View Code? Open in Web Editor NEWAlgorithm solutions.
cplusplus-leetcode-solution's People
Contributors
Stargazers
Watchers
cplusplus-leetcode-solution's Issues
Largest Divisible Subset
Description:
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.
Example:
Given nums = [1,2,3], return [1,2] or [1,3]
Given nums = [1,2,4,8], return [1,2,4,8]
Link:
http://www.lintcode.com/en/problem/largest-divisible-subset/
题目意思：
要求给出数组的一个子集，这个子集满足
1.任意两个数如a与b，a%b=0 或者 b%a=0。
2.这个子集尽可能大
解题思路：
首先有2个事实需要搞清楚：
1.任意两个数当a>b时，b%a是不等于0的，所以此题中任意两个数只有a%b才可能为0；
2.当有三个数a,b,c。满足b%a=0, c%b=0时，则c%a=0。所以当我们用一个数组来记录数组中第i个数字a前面有dp[i]个数字满足子集条件时，如果后面j位置数字b满足b%a=0时，则状态转移方程由此得出：
dp[j] = dp[i] + 1
本道题得到每个数与之前的数可以组成的满足要求子集的尺寸只是第一步，第二步是根据记录的最大的那个数往前推出集合（所求答案）。
Time Complexity：
O(N^2)时间，O(N)空间
完整代码：
vector<int> largestDivisibleSubset(vector<int>& nums)
{
vector<int> result;
if(nums.size() == 0)
return result;
sort(nums.begin(), nums.end());
vector<int> dpSize(nums.size());
int maxSize = 1;
int maxPoi = 0;
for(int i = 0; i < nums.size(); i++)
{
bool find = false;
for(int j = i-1; j >= 0; j--)
{
if(nums[i] % nums[j] == 0)
{
find = true;
dpSize[i] = dpSize[j] + 1;
break;
}
}
if(!find)
dpSize[i] = 1;
if(dpSize[i] > maxSize)
{
maxSize = dpSize[i];
maxPoi = i;
}
}
int bigger = nums[maxPoi];
for(int i = maxPoi; i >= 0; i--)
{
if(bigger % nums[i] == 0)
{
bigger = nums[i];
result.push_back(bigger);
}
}
return result;
}
Minesweeper解题报告
Description:
You are given a 2D char matrix representing the game board. 'M' represents an unrevealed mine, 'E' represents an unrevealed empty square, 'B' represents a revealed blank square that has no adjacent (above, below, left, right, and all 4 diagonals) mines, digit ('1' to '8') represents how many mines are adjacent to this revealed square, and finally 'X' represents a revealed mine.
Now given the next click position (row and column indices) among all the unrevealed squares ('M' or 'E'), return the board after revealing this position according to the following rules:
If a mine ('M') is revealed, then the game is over - change it to 'X'.
If an empty square ('E') with no adjacent mines is revealed, then change it to revealed blank ('B') and all of its adjacent unrevealed squares should be revealed recursively.
If an empty square ('E') with at least one adjacent mine is revealed, then change it to a digit ('1' to '8') representing the number of adjacent mines.
Return the board when no more squares will be revealed.
**Example2: **
Input: [['E', 'E', 'E', 'E', 'E'], ['E', 'E', 'M', 'E', 'E'], ['E', 'E', 'E', 'E', 'E'], ['E', 'E', 'E', 'E', 'E']] Click : [3,0] Output: [['B', '1', 'E', '1', 'B'], ['B', '1', 'M', '1', 'B'], ['B', '1', '1', '1', 'B'], ['B', 'B', 'B', 'B', 'B']]
Explanation:
**Example1: **
Input: [['B', '1', 'E', '1', 'B'], ['B', '1', 'M', '1', 'B'], ['B', '1', '1', '1', 'B'], ['B', 'B', 'B', 'B', 'B']] Click : [1,2] Output: [['B', '1', 'E', '1', 'B'], ['B', '1', 'X', '1', 'B'], ['B', '1', '1', '1', 'B'], ['B', 'B', 'B', 'B', 'B']]
Explanation:
Link:
https://leetcode.com/problems/minesweeper/#/description
解题方法：
一道挺无聊的题，具体步骤题目说明已经给出，使用尾递归解决，并且LeetCode的程序也有点问题（比如在扫雷中数字是不能走的）。
能点的方块有：'M', 'E'
不能点的方块有：'B', '1~8', 'X'
点到M游戏结束，点到E如果周边没有地雷则继续递归，如果有雷则显示雷的数量。
Tips:
整个递归过程中使用一个 bool变量gameover控制游戏能否进行。
完整代码：
vector<int> dirX = {-1, -1, -1, 0, 0, 1, 1, 1};
vector<int> dirY = {-1, 0, 1, -1, 1, -1, 0, 1};
class Solution
{
public:
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click)
{
bool gameover = false; //控制游戏能否继续
go(click[0], click[1], board, gameover);
return board;
}
void go(int x, int y, vector<vector<char>>& board, bool gameover)
{
if(!isValid(x, y, board) || gameover || (board[x][y] >= 48 && board[x][y] <= 56) || board[x][y] == 'X' || board[x][y] == 'B')
return;
if(board[x][y] == 'M')
{
gameover = true;
board[x][y] = 'X';
return;
}
int cnt = countMine(x, y, board);
if(cnt != 0)
{
board[x][y] = cnt + 48;
return;
}
board[x][y] = 'B';
for(int i = 0; i < 8; i++)
go(x+dirX[i], y+dirY[i], board, gameover);
}
bool isValid(int x, int y, vector<vector<char>>& board)
{
if(x < 0 || y < 0 || x >= board.size() || y >= board[0].size())
return false;
return true;
}
int countMine(int x, int y, vector<vector<char>>& board)
{
int cnt = 0;
for(int i = 0; i < 8; i++)
{
if(isValid(x + dirX[i], y + dirY[i], board) && board[x+dirX[i]][y + dirY[i]] == 'M')
cnt++;
}
return cnt;
}
};
Next Permutation解题报告
Description:
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.
Example:
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
Link:
https://leetcode.com/problems/next-permutation/#/description
解题方法：
从后往前找，找到第一个 nums[p] < nums[p+1]的数的位置p。
再次从后往前找，找到第一个nums[c] > nums[p]的数的位置c。
交换两个位置的数，再将p之后的数都反序。
Tips:
直接用reverse函数实现反序。
Time Complexity：
O(N)
完整代码：
void nextPermutation(vector<int>& nums)
{
int n = nums.size();
if(n < 2)
return;
int p = n-1, c = n-1;
while(p >= 0)
{
if(p != n-1 && nums[p] < nums[p+1])
break;
p--;
}
if(p < 0)
{
std::reverse(nums.begin(), nums.end());
return;
}
while(c > 0)
{
if(nums[c] > nums[p])
break;
c--;
}
int temp = nums[p];
nums[p] = nums[c];
nums[c] = temp;
std::reverse(nums.begin()+p+1, nums.end());
return;
}
3Sum
Description:
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.
Example:
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
Link:
https://leetcode.com/problems/3sum/#/description
题目意思：
在数组中找三个数组合使这三个数和为0，没有重复数组合。
解题方法：
类似于2sum in sorted array，使用首位指针的方式，因为这道题暴力解法为N^3，所以用N^2的方法是可AC行的。
Tips:
2sum中如果需要去重，只限定其中一个数不重复，但是3sum要使组合去重，则需要限定期中两个数不为重复组合。
在代码中表明了两次去重，第二次之所以从后面开始去重，仅仅是因为可以不必考虑前面会允许nums[start] = nums[start-1]的情况。
Time Complexity：
O(N^2)
完整代码：
vector<vector<int>> threeSum(vector<int>& nums)
{
vector<vector<int>> result;
if(nums.size() < 3)
return result;
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size(); i++)
{
if(i > 0 && nums[i] == nums[i-1])//第一个数去重
continue;
int target = -nums[i];
int start = i + 1, end = nums.size() - 1;
if(nums[end] < 0)
break;
while(start < end)
{
if(end != nums.size() - 1 && nums[end] == nums[end + 1])//第二个数去重
{
end--;
continue;
}
int temp = nums[start] + nums[end];
if(target > temp)
start++;
else
if(target < temp)
end--;
else
result.push_back({-target, nums[start++], nums[end--]});
}
}
return result;
}
Integer to Roman
Description:
Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.
Link:
https://leetcode.com/problems/integer-to-roman/#/description
题目意思：
把数字转换成罗马数字。
解题方法：
一个比较作弊的解法，先生成一部分对照表，然后从左往右构造。
完整代码：
string intToRoman(int num)
{
//按照这张表，可以直接从左往右按照罗马数字“右加”的法则生成结果
vector<int> n = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
vector<string> c = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
string result;
int i = 0;
while(num > 0)
{
int digit = num / n[i];
if(digit >= 1)
{
for(int j = 0; j < digit; j++)
result += c[i];
num -= digit * n[i];
}
i++;
}
return result;
}
Copy List with Random Pointer
Description:
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
Link:
[http://www.lintcode.com/en/problem/copy-list-with-random-pointer/]
解题思路：
解法1：O(n) space, DFS或者迭代
使用哈希表储存已经克隆的节点，当在哈希表中找到节点的时候直接使用，否则就创新的节点。
解法2：O(1) space, O(n) time
将新的点储存在以前每个老的结点之后，如：
0->0'->1->1'->2->2'->NULL
最后再用一次循环拆开。
总共三个循环：
第一次将新的节点添加到老List中去，第二次循环将新节点的random指向对应的新节点，第三次讲List拆开，最后返回新的节点第一个（用dummy node记录）。
Tips:
在进行DFS的时候，umordered_map需要用引用传递，不然内存超出限制。并且要先于下一步dfs之前把节点添加到其中，不然时间超出限制。
完整代码：
DFS：
RandomListNode *copyRandomList(RandomListNode *head)
{
unordered_map <int, RandomListNode*> um;
if(head == NULL)
return NULL;
return dfs(head, um);
}
RandomListNode *dfs(RandomListNode *node,
unordered_map<int, RandomListNode*> &um)
{
if(node == NULL)
return NULL;
if(um.find(node->label) != um.end())
return um[node->label];
RandomListNode *temp = new RandomListNode(node->label);
um[temp->label] = temp; //在进入新一轮DFS之前要先对哈希表进行更新，不然再次到这个节点又会重新之前的递归，进入死循环。
temp->random = dfs(node->random, um);
temp->next = dfs(node->next, um);
return temp;
}
Iteration:
class Solution
{
public:
RandomListNode *copyRandomList(RandomListNode *head)
{
unordered_map<int, RandomListNode*> hash;
RandomListNode* dummy =new RandomListNode(0);
RandomListNode* builder = dummy;
while(head)
{
RandomListNode* curr = NULL;
if(hash[head->label])
curr = hash[head->label];
else
{
curr = new RandomListNode(head->label);
hash[curr->label] = curr;
}
builder->next = curr;
if(head->random)
{
if(hash[head->random->label])
curr->random = hash[head->random->label];
else
{
curr->random = new RandomListNode(head->random->label);
hash[curr->random->label] = curr->random;
}
}
head = head->next;
builder = builder->next;
}
return dummy->next;
}
};
O(1) Space：
class Solution
{
public:
RandomListNode *copyRandomList(RandomListNode *head)
{
if(!head)
return NULL;
RandomListNode* dummy = new RandomListNode(0);
dummy->next = head;
while(head) //create new nodes behind every original node
{
RandomListNode* curr = new RandomListNode(head->label);
curr->next = head->next;
head->next = curr;
head = head->next->next;
}
//copy random point
head = dummy->next;
while(head)
{
if(head->random)
head->next->random = head->random->next;
head = head->next->next;
}
//remove copy list from original list, and repair the original list
head = dummy;
while(head->next)
{
RandomListNode* temp = head->next;
head->next = head->next->next;
head = head->next;
temp->next = head->next;
}
return dummy->next;
}
};
Word Break解题报告
Description:
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.
Example:
For example, given
s = "leetcode",
dict = ["leet", "code"].Return true because "leetcode" can be segmented as "leet code".
Link:
https://leetcode.com/problems/word-break/#/description
解题方法：
用DP做。
假设dp[i]表示从字符串S从0~i-1的子串能被word break掉。状态转移方程为：
dp[i] = dp[j] && wordDict中能找到substr(j, i-j)
(dp[j]对应的是S[j-1])
最前面dp[0]先初始化为true。
Tips:
在创建哈希表的时候把wordDict中最长的string长度记下来，如果i-j > 这个长度，则后面的子串可以不用检查。
Time Complexity：
时间：O(N^2)
空间：O(M)
完整代码：
bool wordBreak(string s, vector<string>& wordDict)
{
if(s.size() == 0 || wordDict.size() == 0)
return false;
unordered_set<string> hash;
int maxLen = 0;
for(string str: wordDict)
{
maxLen = str.size() > maxLen ? str.size() : maxLen;
hash.insert(str);
}
vector<bool> dp(s.size(), false);
dp[0] = true;
for(int i = 1; i <= dp.size(); i++)
{
for(int j = 0; j < i; j++)
{
if(!dp[j] || i - j > maxLen)
continue;
string temp = s.substr(j, i-j);
if(hash.find(temp) != hash.end())
{
dp[i] = true;
break;
}
}
}
return dp[s.size()];
}
Subarray Sum Closest
Description:
Given an integer array, find a subarray with sum closest to zero. Return the indexes of the first number and last number.
Example:
Given [-3, 1, 1, -3, 5], return [0, 2], [1, 3], [1, 1], [2, 2] or [0, 4].
Link:
[http://www.lintcode.com/en/problem/subarray-sum-closest/]
解题思路：
这道题求的是和最接近于0的子序列，暴力做法应该是N*N的时间复杂度，但是不能AC，所以在这里需要观察，所有子序列和的集合 = {0~n的子序列和，0~n的子序列和 - 0~m的子序列和}，这里m<n。
所以由此我们可以知道，当(0n的子序列和)与(0m的子序列和)值非常接近的时候，则（m+1~n）即为所要求的最接近0的子序列。
解题方法：
当我们求到所有从0开始的子序列和，对其进行排序再遍历，我们可以得到每两个最接近的从0开始的子序列和。至于排序后没有相邻的子序列和，则不进行考虑，因为最小的差值不会从不相邻的两个子序列和里面产生。在求所有0~m的子序列和的过程中应该记录下m对应的值（可以自定义数据结构或者用pair）。
Tips:
当用sort对含有pair的vector进行排序的时候，会优先针对pair::first进行排序，所以这道题可以不需要自己写排序函数。
Time Complexity：
sort函数的时间复杂度为：O(nlogn)
完整代码：
vector<int> subarraySumClosest(vector<int> nums)
{
if(nums.size() == 0)
return {};
vector<pair<int, int> > node;
node.push_back({0, 0});
int sum = 0;
for(int i = 0; i < nums.size(); i++)
{
sum += nums[i];
if(sum == 0)
return {0, i};
node.push_back({sum, i+1});
}
std::sort(node.begin(), node.end());
int min = 2147483647;
vector<int> result(2, 0);
for(int i = 1; i < node.size(); i++)
{
int temp;
temp = abs(node[i].first - node[i-1].first);
if(temp < min)
{
min = temp;
if(node[i].second < node[i-1].second)
{
result[0] = node[i].second;
result[1] = node[i-1].second - 1;
}
else
{
result[0] = node[i-1].second;
result[1] = node[i].second - 1;
}
}
}
return result;
}
Product of Array Except Self解题报告
Description:
Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Solve it without division and in O(n).
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)
Example:
For example, given [1,2,3,4], return [24,12,8,6].
Link:
https://leetcode.com/problems/product-of-array-except-self/#/description
解题方法：
扫描两次数组：
第一次从左往右扫描，记录从0 ~ i-1的积。
第二次从右往左扫描，记录从n-1 ~ i+1的积。
将两次扫描的结果对应的位置相乘得到所求的数组。
Tips:
如果出了输出数组不能用额外的空间。则可以用输出数组记录两次扫描的结果。并在第二次扫描的时候将结果算出来。
Time Complexity：
时间O(N) 空间O(1)
完整代码：
vector<int> productExceptSelf(vector<int>& nums)
{
int len = nums.size();
vector<int> result;
if(len == 0)
return result;
int sum = 1;
for(int i = 0; i < len; i++)
{
result.push_back(sum);
sum *= nums[i];
}
for(int i = len-1, sum = 1; i >= 0; i--)
{
result[i] *= sum; //直接算出结果
sum *= nums[i];
}
return result;
}
Increasing Triplet Subsequence
Description:
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.
Example:
Given [1, 2, 3, 4, 5], return true. Given [5, 4, 3, 2, 1], return false.
Link:
https://leetcode.com/problems/increasing-triplet-subsequence/#/description
题目意思：
判断一个数组是否有递增的长度>=3的子集（顺序不变）。
解题方法：
因为需要O(n)的时候解决，所以求最长递增子集的方法不适用（即DP）。
索性该题只需要求出是否存在长度>=3，则可以使用2个int变量min1, min2，代表最小数和第二小的数，只要在遍历过程中出现>=min2的数就可以返回true.
Time Complexity：
O(n)时间
完整代码：
bool increasingTriplet(vector<int>& nums)
{
if(nums.size() < 3)
return false;
int min1 = INT_MAX, min2 = INT_MAX;
for(int i = 0; i < nums.size(); i++)
{
if(nums[i] < min1)
min1 = nums[i];
if(nums[i] < min2 && nums[i] > min1)
min2 = nums[i];
if(nums[i] > min2)
return true;
}
return false;
}
Perfect Squares
Description:
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
Example:
Given n = 12, return 3 because 12 = 4 + 4 + 4
Given n = 13, return 2 because 13 = 4 + 9
####Link:
http://www.lintcode.com/en/problem/perfect-squares/
题目意思：
给出一个正整数n，求这个正整数最小可以由几个平方数相加而成。
####解题方法：
使用dp来解题，创建一个size为n+1的数组来储存从1~n的每个数的题解（平方数则为1）。
状态转移方程为dp[n] = min(dp[i] + dp[n-i])
Tips:
for(int j = 1; j*j <= i/2; j++) result[i] = result[i] > result[j*j] + result[i-j*j] ? result[j*j] + result[i-j*j] : result[i];
将j换成了j*j，是可以跳过一些不是平方数的数字，如果不换的话Lintcode时间报错但是leetcode可以AC。
Time Complexity：
当把j换成了j*j后，时间复杂度为O(nlogn)，否则为O(n^2)。
空间复杂度为O(n)。
完整代码：
int numSquares(int n)
{
if(n < 1)
return 0;
vector<int> result(n+1, INT_MAX);
for(int i = 1; i*i <= n; i++)
result[i*i] = 1;
for(int i = 2; i <= n; i++)
{
if(result[i] == INT_MAX)
for(int j = 1; j*j <= i/2; j++)
result[i] =
result[i] > result[j*j] + result[i-j*j] ?
result[j*j] + result[i-j*j] : result[i];
}
return result[n];
}
Longest Palindromic Substring
Description:
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
Input: "babad" Output: "bab" Note: "aba" is also a valid answer.
Input: "cbbd" Output: "bb"
Link:
https://leetcode.com/problems/longest-palindromic-substring/#/description
题目意思：
找出最长回文子串。
解题方法：
从头遍历一遍数组，针对每个元素找出最长回文串。
Tips:
对每个元素，要分别找奇数回文串和偶数回文串。
向两边扩展的时候应该同时检测是不是回文串，这样才不会超时。
Time Complexity：
O(N^2)时间
完整代码：
string longestPalindrome(string s)
{
if(s.size() == 0)
return 0;
int max = 0, start;
for(int i = 0; i < s.size(); i++)
{
//odd case
int temp = -1;
for(int j = 0; i - j >= 0 && i + j < s.size(); j++)
{
if(s[i - j] != s[i + j])
break;
temp = j * 2 + 1;
}
if(temp > max)
{
start =i - (temp - 1)/2;
max = temp;
}
//even case
temp = -1;
for(int j = 0; i - j >= 0 && i + j + 1 < s.size(); j++)
{
if(s[i - j] != s[i + j + 1])
break;
temp = j * 2 + 2;
}
if(temp > max)
{
start =i - (temp - 2)/2;
max = temp;
}
}
return s.substr(start, max);
}
Linked List Cycle
Description:
Given a linked list, determine if it has a cycle in it.
Example:
Given -21->10->4->5, tail connects to node index 1, return true
Link:
[http://www.lintcode.com/en/problem/linked-list-cycle/]
解题思路：
设定快慢指针，fast一次走两步，slow一次走一步，如果fast || fast->next == NULL则没有cycle，如果fast == slow 则存在循环。
Tips:
有两个指针，所以题目开始要查head和head->next是否为空。
在快慢指针跑起来以后，只要有循环那么一定会碰面，只要没有循环那么快指针肯定先到终点。
Time Complexity：
O(n)
完整代码：
bool hasCycle(ListNode *head)
{
if(head == NULL || head->next == NULL)
return false;
ListNode* fast;
ListNode* slow;
slow = head;
fast = head->next;
while(slow != fast)
{
if(fast == NULL || fast->next == NULL)
return false;
slow = slow->next;
fast = fast->next->next;
}
return true;
}
Valid Parentheses
Description:
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
Link:
https://leetcode.com/problems/valid-parentheses/#/description
解题方法：
一道很典型的考验栈的**的题目。
Tips:
在检测stack::top()的时候首先要检测stack是不是为空。
Time Complexity：
O(N)
完整代码：
bool isValid(string s)
{
if(s.size() % 2 != 0)
return false;
stack<char> chas;
for(char a: s)
{
if(a == '(' || a == '[' || a == '{')
chas.push(a);
else
{
if(chas.empty() || (chas.top() != a - 1 && chas.top() != a - 2)) //要先检查栈是不是空
return false;
else
chas.pop();
}
}
if(chas.size())
return false;
return true;
}
Container With Most Water
Description:
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.
Link:
https://leetcode.com/problems/container-with-most-water/#/description
题目意思：
给出一组数组代表木桶两边长度，求这组数组中任意两个边组成的木桶能装到最多的水。
解题方法：
这道题的解决定于两个条件：1. 两个木板距离；2. 两个木板中较短的那个木板长度。
所以当我们一开始取一头一尾两个木板时候，我们满足了条件1最大化。此时比较两个木板谁更短，更短的一边位置向中间移动一位。
这个解题**是：在保持最大距离的情况下，让两个木板较短的那块尽量长。
Tips:
使用三目运算符和单目运算符++ --让程序更快。
Time Complexity：
O(N)
完整代码：
int maxArea(vector<int>& height)
{
int max = 0, left = 0, right = height.size() - 1;
while(left < right)
{
int temp = height[left] > height[right] ? height[right--] : height[left++];
max = max > temp * (right - left + 1) ? max : temp * (right - left + 1) ;
}
return max;
}
Lowest Common Ancestor of a Binary Tree解题报告
Description:
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).”
Example:
_______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.
Link:
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/#/description
解题方法：
看到一种很巧妙的递归的解题方法：
1、从一个节点的左右子树本别去找p和q。
2、如果某个节点正是p和q其中一个，则返回本节点。
3、当在一个节点的左右子树找全了p和q，则返回本节点；如果没找全，则返回找到的那边；如果都没找到，则返回NULL。
可行性分析：
针对这种解题方法，容易产生一个地方的疑问：
当这个节点是p和q中的一个，并且这个节点的左右子树包含p和q中另一个怎么办？
其实这种递归方法的返回值来源只有这么几个：
- 某个符合条件的节点自身，
- p节点，
- q节点，
- NULL。
下面分析一下这几个来源：
1）在节点左右都没找到的情况下
2）在本节点本身为NULL的情况下才有。
p和q节点来源于二叉树里面p和q节点本身。
而以上所有非NULL的返回值都来源于2和3，至于1来源，其实是某个节点判断自己是共同祖先让然后返回自己。而这个方法精妙之处就在于此，只有在触碰到2和3来源时，才会返回非NULL的节点。递归此时开始往回返回节点，而当出现第一个共同祖先时，此时这个祖先其实就是我们所求的LCA，那么这个LCA会随着递归一直返回到第一层递归，而其他地方再也不会产生新的符合的节点并且返回。
当在递归函数中，先检查自身是不是p或q，意味着先从根的方向检查，如果这个节点是p和q其中一个，则这个节点变成了以上来源2或者3。如果这个节点的子树包含p和q中另一个，那么其他所有节点都不会成为以上的来源1。这意味着最后到root节点那一层这个节点会被保留下来。
如p和q不是以以上形式存在二叉树，而是有一个共同祖先的话。那么以上的来源2最终会在某个节点形成来源1。并且其他以外的节点都不会成为符合以上123来源的任何一个，只会是NULL。所以成为来源1的节点最终会被root那一层选择为返回节点。
Tips:
递归方法第三步的判断（即左右有一个则返回一个，没有则返回NULL）可以写在一起。
完整代码：
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
if(!root || !p || !q)
return NULL;
if(root == p || root == q) //如果本节点就是p或q，则返回本节点
return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if(left && right) //如果p和q都在本节点的左右子树中找到，则返回本节点
return root;
return left ? left : right; //左右找到一个就返回找到的那个，否则返回NULL
}
Rehashing
Description:
The size of the hash table is not determinate at the very beginning. If the total size of keys is too large (e.g. size >= capacity / 10), we should double the size of the hash table and rehash every keys. Say you have a hash table looks like below:
size=3, capacity=4
[null, 21, 14, null]
↓ ↓
9 null
↓
null
The hash function is:
int hashcode(int key, int capacity) {
return key % capacity;
}
here we have three numbers, 9, 14 and 21, where 21 and 9 share the same position as they all have the same hashcode 1 (21 % 4 = 9 % 4 = 1). We store them in the hash table by linked list.
rehashing this hash table, double the capacity, you will get:
size=3, capacity=8
index: 0 1 2 3 4 5 6 7
hash : [null, 9, null, null, null, 21, 14, null]
Given the original hash table, return the new hash table after rehashing .
Example:
Given [null, 21->9->null, 14->null, null],
return [null, 9->null, null, null, null, 21->null, 14->null, null]
Link:
http://www.lintcode.com/en/problem/rehashing/
Tips:
在重新计算key的时候，如果value是一个负数，那么使用value % capacity这个公式会产生负数，所以需要使用代替公式：
(value % capacity + capacity) % capacity
完整代码：
vector<ListNode*> rehashing(vector<ListNode*> hashTable)
{
int capacity = hashTable.size()*2;
vector<ListNode*> result(capacity, NULL);
for(int i = 0; i < hashTable.size(); i++)
{
if(hashTable[i] == NULL)
continue;
else
{
ListNode* head = hashTable[i];
while(head != NULL)
{
hashadd(result, head->val);
head = head->next;
}
}
}
return result;
}
void hashadd(vector<ListNode*> &result, int val)
{
int key = hashcode(val, result.size());
if(result[key] == NULL)
{
ListNode* temp = new ListNode(val);
result[key] = temp;
}
else
{
ListNode* head = result[key];
while(head->next != NULL)
head = head->next;
ListNode* temp = new ListNode(val);
head->next = temp;
}
}
int hashcode(int key, int capacity)
{
return (key % capacity + capacity) % capacity;
}
Reverse Nodes in k-Group
Description:
Given a linked list, reverse the nodes of a linked list k at a time and return its modified 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.
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
Link:
http://www.lintcode.com/en/problem/reverse-nodes-in-k-group/
解题思路：
在reverse linked list这道题的基础上，reverse这个函数的输入为（head, k）
假设k=4
原List：head->node1->node2->node3->node4->NULL
反转为：head->node4->node3->node2->node1->NULL
输出node1
否则则输出NULL
Tips:
代码注释1：
nk = nk->next;放在if语句后面，可以检测上一次反转正好把整个List反转完的情况。
代码注释2：
curr != nextPart而不是curr != nk->next是因为在循环的最后阶段nk的next会改变。
Time Complexity：
O(n)
完整代码：
ListNode *reverseKGroup(ListNode *head, int k)
{
ListNode *dummy = new ListNode(0);
dummy->next = head;
head = dummy;
while(true)
{
head = reverse(head, k);
if(head == NULL)
break;
}
return dummy->next;
}
ListNode *reverse(ListNode* head, int k)
{
ListNode *nk = head;
for(int i = 0; i < k; i++)
{
if(nk == NULL)
return NULL;
nk = nk->next; //1
}
if(nk == NULL)
return NULL;
ListNode *endNode = head->next;
ListNode *nextPart = nk->next;
ListNode *curr = head->next;
ListNode *prev = NULL;
ListNode *temp;
while(curr != nextPart) //2
{
temp = curr->next;
curr->next = prev;
prev = curr;
curr = temp;
}
head->next = prev;
endNode->next = nextPart;
return endNode;
}
Find All Anagrams in a String解题报告
Description:
Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.
Example:
Example 1:
Input:
s: "cbaebabacd" p: "abc"
Output:
[0, 6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2:
Input:
s: "abab" p: "ab"
Output:
[0, 1, 2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".
Link:
https://leetcode.com/problems/find-all-anagrams-in-a-string/#/description
解题方法：
用字符的分布来匹配anagrams，用slide window来优化暴力算法。当i>p的长度时，每次i++都相当于窗口右移动。左边需要减去刚刚划过的记录。
Tips:
不能用unordered_map来当哈希表。
Time Complexity：
O(n)
完整代码：
vector<int> findAnagrams(string s, string p)
{
vector<int> result;
int lenp = p.size();
int lens = s.size();
if(s.size() == 0 || p.size() > s.size())
return result;
vector<int> hash1(26);
vector<int> hash2(26);
for(auto a: p)
hash1[a-'a']++;
for(int i = 0; i < s.size(); i++)
{
hash2[s[i]-'a']++;
if(i >= lenp) hash2[s[i-lenp]-'a']--; //加上右边的记录，减去左边的记录
if(hash1 == hash2) result.push_back(i-lenp+1);
}
return result;
}
Insert Delete GetRandom O(1)解题报告
Description:
Design a data structure that supports all following operations in average O(1) time.
insert(val): Inserts an item val to the set if not already present.
remove(val): Removes an item val from the set if present.
getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.
Example:
// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);// Returns false as 2 does not exist in the set.
randomSet.remove(2);// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);// 2 was already in the set, so return false.
randomSet.insert(2);// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();
Link:
https://leetcode.com/problems/insert-delete-getrandom-o1/#/description
解题方法：
哈希表可以O(1)时间增加删除，vector可以在O(1)时间取得随机数、删除尾部元素、在尾部增加元素。
如果用哈希表记录vector里面元素的位置，在删除的时候将vector需要删除的元素与其尾部互换，就可以在O(1)时间删除该元素。
Tips
要取得[a,b)的随机整数，使用(rand() % (b-a))+ a;
要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a;
要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1;
通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。
要取得a到b之间的随机整数，另一种表示：a + (int)b * rand() / (RAND_MAX + 1)。
要取得0～1之间的浮点数，可以使用rand() / double(RAND_MAX)。
参考：http://www.cnblogs.com/afarmer/archive/2011/05/01/2033715.html
Time Complexity：
O(1)
完整代码：
class RandomizedSet
{
private:
vector<int> cache;
unordered_map <int, int> hash;
public:
/** Initialize your data structure here. */
RandomizedSet()
{
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
bool insert(int val)
{
if(hash.find(val) != hash.end())
return false;
cache.push_back(val);
hash[val] = cache.size() - 1;
return true;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
bool remove(int val)
{
if(hash.find(val) == hash.end())
return false;
hash[cache.back()] = hash[val]; //交换位置之前哈希表中对应的位置也要交换
swap(cache[cache.size() - 1], cache[hash[val]]);
cache.pop_back();
hash.erase(val);
return true;
}
/** Get a random element from the set. */
int getRandom()
{
return cache[rand()%cache.size()];
}
};
Reverse Linked List
Description:
Reverse a linked list.
Example:
For linked list 1->2->3, the reversed linked list is 3->2->1
Link:
http://www.lintcode.com/en/problem/reverse-linked-list/
解题思路：
针对每个节点curr，只要改变该节点的next，让其指向curr前一个节点（需要用一个变量prev储存），然后再对这个节点的下个节点进行相同的操作。
这道题搞清楚以后，针对k-group那道题的反转代码就会写了。
Tips:
在进行反转操作之后，head已经不是第一个节点了而是最后一个，此时用dummy并不好用，反而直接返回prev这个点方便。
Time Complexity：
O(n)，n为节点个数
完整代码：
ListNode *reverse(ListNode *head)
{
ListNode *temp;
ListNode *curr = head;
ListNode *prev = NULL;
while(curr != NULL)
{
temp = curr->next;
curr->next = prev;
prev = curr;
curr = temp;
}
return prev;
}
Jump Game
Description:
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.
Example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
Link:
http://www.lintcode.com/en/problem/jump-game/
题目意思：
给出一个数组，每个位置的值表示从此处位置可以向后跳几步，判断能否跳到最后一步。
解题方法：
解法1：DP
创建一个size为n的bool数组dp，表示每个位置是否能跳到。从1到n-1位置分别从后(从i-1)向前查(到0)找以判断i位置能否到达，判断方程为：dp[j] && A[j] >= i-j。如果可以，则将dp[i]设为true，否则为false;
解法2：greedy
**很简单，从前往后遍历数组，记录当前能跳到的最远位置int far，当有在far之前的位置(i <= far)能够跳到比far还远的时候(A[i] + i >= far)，就更新far，最后比较far和终点的远近。
Tips:
使用DP解法时可能会超时，但是当出现一个false时就可以直接返回false，因为当终点前一步都不能走到时，终点当然也不可能走到。
Time Complexity：
DP: O(N^2)
Greedy: O(N)
完整代码：
DP
bool canJump(vector<int> A)
{
vector<bool> reach(A.size(), false);
reach[0] = true;
for(int i = 1; i < A.size(); i++)
{
for(int j = i-1; j >= 0; j--)
{
if(reach[j] && A[j] >= i-j)
{
reach[i] = true;
break;
}
}
if(!reach[i])
return false;
}
return reach[A.size() - 1];
Greedy
bool canJump(vector<int> A)
{
if(A.size() == 0)
return false;
int far = A[0];
for(int i = 1; i < A.size(); i++)
if(i <= far && A[i] + i >= far)
far = A[i] + i;
return far >= A.size() - 1;
}
Longest Increasing Subsequence
####Description:
Given a sequence of integers, find the longest increasing subsequence (LIS).
You code should return the length of the LIS.
####Example:
For [5, 4, 1, 2, 3], the LIS is [1, 2, 3], return 3
For [4, 2, 4, 5, 3, 7], the LIS is [2, 4, 5, 7], return 4
####Link:
http://www.lintcode.com/en/problem/longest-increasing-subsequence/
####题目意思：
给一个数组nums，找出这个数组中最长的递增子集的个数，子集元素在数组中的顺序不能打破。
####解题方法：
DP:
- 创建一个数组
dp，代表数组中每个元素前面有几个比它小的元素（递增），从到到尾遍历数组nums，在i位置时，j从i-1到0去查找比nums[i]小的元素，在这些元素中找到对应的dp值最大的。状态方程为：dp[i] = max(dp[j])+1。
最后在dp中找到最大值max，并返回max+1。 - 维护一个递增的数组dp，利用binary search来查找输入数组中每个数在这个数组中的位置，并且在每次查找后，将查找的数替换dp中相应位置原有的数（如果查找的index超过dp的长度则在最后则添加在后面）。
####Tips:
注意dp数组仅仅记录了在某个位置上的元素前面有几个符合题目标准的数字，所以最后返回结果要+1，这才代表子集的个数。
####Time Complexity：
1.
时间O(N^2) 空间O(N)
2.
时间O(NlogN) 空间O(N)
####完整代码：
1.
int longestIncreasingSubsequence(vector<int> nums)
{
if(nums.size() == 0)
return 0;
vector <int> dp (nums.size(), 0);
for(int i = 1; i < nums.size(); i++)
{
int max = 0;
bool find = false;
for(int j = i-1; j >= 0; j--)
{
if(nums[j] < nums[i])
{
max = dp[j] > max ? dp[j] : max;
find = true;
}
}
if(find)
dp[i] = max+1; //如果没找到，dp值依然为0
}
int max = 0;
for(int i = 1; i < dp.size(); i++)
max = dp[i] > max ? dp[i] : max;
return max+1;
}
2.
int bs(vector<int>& nums, int n) {
int len = nums.size();
if(!len || n < nums[0])
return 0;
if(n > nums[len - 1])
return len;
int start = 0, end = len - 1;
while(start + 1 < end) {
int mid = start + (end - start) / 2;
if(nums[mid] == n)
return mid;
else if(nums[mid] > n)
end = mid;
else
start = mid;
}
if(nums[start] == n)
return start;
if(nums[end] == n)
return end;
if(nums[start] > n)
return start;
else
return end;
}
int LIS(vector<int>& nums) {
int len = nums.size();
if(len < 2)
return len;
vector<int> DP;
for(int i: nums) {
int index = bs(DP, i);
if(index == DP.size())
DP.push_back(i);
else
DP[index] = i;
}
return DP.size();
}
Hash Function
Description:
In data structure Hash, hash function is used to convert a string(or any other type) into an integer smaller than hash size and bigger or equal to zero. The objective of designing a hash function is to "hash" the key as unreasonable as possible. A good hash function can avoid collision as less as possible. A widely used hash function algorithm is using a magic number 33, consider any string as a 33 based big integer like follow:
hashcode("abcd") = (ascii(a) * 333 + ascii(b) * 332 + ascii(c) *33 + ascii(d)) % HASH_SIZE
= (97* 333 + 98 * 332 + 99 * 33 +100) % HASH_SIZE
= 3595978 % HASH_SIZE
here HASH_SIZE is the capacity of the hash table (you can assume a hash table is like an array with index 0 ~ HASH_SIZE-1).
Given a string as a key and the size of hash table, return the hash value of this key.f
Example:
For key="abcd" and size=100, return 78
Link:
http://www.lintcode.com/en/problem/hash-function/#
解题思路：
代码很简单，但是int类型非常容易溢出，所以在这里有两个点需要注意：
1）1LL * 任何数，就可以转化成long long数据类型，防止单次计算上溢
2）每次计算以后%HASH_SIZE，与最后去模效果一样，而且可以防止上溢
Tips:
因为result一开始等于0，所以每次对其33，而不是直接对char33，这样达到指数递减效果。
Time Complexity：
O(N)
完整代码：
int hashCode(string key,int HASH_SIZE)
{
if(key.size() == 0)
return 0;
int result = 0;
int len = key.size() - 1;
for(char ch : key)
result = (1LL * result * 33 + ch) % HASH_SIZE;
return result;
}
Ugly Number II
Description:
Ugly number is a number that only have factors 2, 3 and 5.
Design an algorithm to find the nth ugly number. The first 10 ugly numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12...
Example:
If n=9, return 10.
Link:
http://www.lintcode.com/en/problem/ugly-number-ii/
解题思路：
1：scan方式 O(n)时间
因为ugly number的因子只能是2 3 5所以可以把整个ugly number看作是由2 3 5不断与原有的ugly number里面每个数相乘所得到的3个集合的总集（集合最初只有元素1）。
需要有3个index分别代表2 3 5与集合中第几个数相乘。每次求出计算值找最小的一个加入到ugly集合中，对应的index则++。
Tips:
在scan方式中，注意判断语句。
if(add == u2) i2++; if(add == u3) i3++; if(add == u5) i5++;为正确语句。
而
if(add == u2) i2++; else { if(add == u3) i3++; else i5++; }会得出错误答案。
原因是在计算过程中，可能会出现相同的结果（并且同时为最小），例如2x3 = 6， 与3x2 = 6。此时需要将两个index都++，不然根据下面这部分代码的逻辑会先将i2++然后下一轮i3++，这样集合中将会出现2个6。
Time Complexity：
完整代码：
方法1：
int nthUglyNumber(int n)
{
vector<int> ugly;
ugly.push_back(1);
int i2 = 0, i3 = 0, i5= 0;
for(int i = 0; i < n; i++)
{
int u2 = ugly[i2] * 2;
int u3 = ugly[i3] * 3;
int u5 = ugly[i5] * 5;
int add = min(u5, min(u2, u3));
if(add == u2)
i2++;
if(add == u3)
i3++;
if(add == u5)
i5++;
ugly.push_back(add);
}
return ugly[n-1];
}
Merge k Sorted Lists
Description:
Merge k sorted linked lists and return it as one sorted list.
Analyze and describe its complexity.
Example:
Given lists:
[
2->4->null,
null,
-1->null
],
return -1->2->4->null.
Link:
http://www.lintcode.com/en/problem/merge-k-sorted-lists/
解题思路：
使用堆排序可以解决
Tips:
边创建priority_queue边建立新的链表能减少时间复杂度（解法2）。
Time Complexity：
O(kn)
完整代码：
1、
struct compare
{
bool operator ()(ListNode *a, ListNode *b)
{
return a->val > b->val;
}
};
class Solution
{
public:
ListNode *mergeKLists(vector<ListNode *> &lists)
{
if(lists.size() == 0)
return NULL;
priority_queue <ListNode *, vector<ListNode *>, compare> pq;
for(int i = 0; i < lists.size(); i++)
{
ListNode *temp = lists[i];
while(temp != NULL)
{
pq.push(temp);
temp = temp->next;
}
}
ListNode *dummy = new ListNode(0);
ListNode *tail = dummy;
while(!pq.empty())
{
tail->next = pq.top();
pq.pop();
tail = tail->next;
}
return dummy->next;
}
};
2、
struct compare
{
bool operator ()(ListNode *a, ListNode *b)
{
return a->val > b->val;
}
};
class Solution
{
public:
ListNode *mergeKLists(vector<ListNode *> &lists)
{
if(lists.size() == 0)
return NULL;
priority_queue <ListNode *, vector<ListNode *>, compare> pq;
for(auto a: lists)
{
if(a)
pq.push(a); //把几个root放进优先队列里面
}
ListNode *dummy = new ListNode(0);
ListNode *tail = dummy;
while(!pq.empty())
{
tail->next = pq.top();
pq.pop(); //先把最大的root pop掉
tail = tail->next;
if(tail->next)
pq.push(tail->next); //再把之前pop掉的那个root的next加入进来比较
}
return dummy->next;
}
};
String to Integer (atoi)
Description:
Implement atoi to convert a string to an integer.
Link:
https://leetcode.com/submissions/detail/107311468/
题目意思：
把string转换成int。
解题方法：
巨恶心一道题，但是考的是细心。
当从数字或者正负符号开始，期间只要是不正常的数字都为0；
当数字过大时候输出INT_MAX或者INT_MIN。
Time Complexity：
O(N)
完整代码：
int myAtoi(string str)
{
int i;
int neg = 1;
int count = 0;
long long result = 0;
for(i = 0; i < str.length(); i++) //handle space
{
if(str[i] == ' ')
continue;
else
if(str[i] == '+' || str[i] == '-' || (str[i] >= '0' && str[i] <= '9'))
break;
else
return 0;
}
for(; i < str.length(); i++)
{
if(str[i] == '-' || str[i] == '+')
{
count++;
if(str[i] == '-')
neg = -1;
if(count > 1)
return 0;
}
else
{
if(str[i] >= '0' && str[i] <= '9')
break;
else
return 0;
}
}
int len = 0;
for(; i < str.length(); i++)
{
if(str[i] >= '0' && str[i] <= '9')
{
if(++len > 10)
{
if(neg == -1)
return INT_MIN;
else
return INT_MAX;
}
result = result * 10 + str[i] - 48;
}
else break;
}
result *= neg;
if(result >= INT_MAX)
return INT_MAX;
if(result <= INT_MIN)
return INT_MIN;
return result;
}
Word Ladder解题报告
Description:
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 transformed word must exist in the word list. Note that beginWord is not a transformed word.
Example:
Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Link:
https://leetcode.com/problems/word-ladder/#/description
解题方法：
用哈希表把WordList中的单词记下来，然后用bfs。
transform的方法是根据现有单词的每个字母，用26个字母轮流去替换，如果替换出来的结果在哈希表中则代表可以走一步。每走完一步删除哈希表中对应的单词，这样可以保证不会走重复的步骤。
Tips:
用unordered_map在LeetCode里面不能AC，所以需要换成unordered_set。这样占用内存更小。
完整代码：
int ladderLength(string beginWord, string endWord, vector<string>& wordList)
{
unordered_set <string> hash;
for(auto a: wordList)
hash.insert(a);
queue<string> Q;
Q.push(beginWord);
int cnt = 0;
while(!Q.empty())
{
int len = Q.size();
cnt++;
for(int i = 0; i < len; i++)
{
string curr = Q.front();
Q.pop();
if(curr == endWord)
return cnt;
for(int j = 0; j < curr.size(); j++)
{
for(int k = 0; k < 26; k++)
{
string temp = curr;
temp[j] = 'a' + k;
if(hash.find(temp) != hash.end())
{
hash.erase(temp);
Q.push(temp);
}
}
}
}
}
return 0;
}
strStr
Description:
For a given source string and a target string, you should output the first index(from 0) of target string in source string.
If target does not exist in source, just return -1.
Example:
If source = "source" and target = "target", return -1.
If source = "abcdabcdefg" and target = "bcd", return 1.
Link:
http://www.lintcode.com/en/problem/strstr/#
Time Complexity：
O(N^2)
完整代码：
int strStr(const char *source, const char *target)
{
if(source == NULL || target == NULL)
//要写在最前面，不然当source为NULL时，s-t会导致死循环
return -1;
int s = strlen(source), t = strlen(target);
int i, j;
for(i = 0; i <= s - t; i++)
{
for(j = 0; j < t; j++)
if(source[i+j] != target[j])
break;
if(j == t)
//j == t而不是j == t-1
return i;
}
return -1;
}
Generate Parentheses解题报告
Description:
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
Example:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
Link:
https://leetcode.com/problems/generate-parentheses/#/description
解题方法：
使两个int：left和right各表示(和)还剩下多少个，用递归生成字符串，过程中需遵守的规则是left 不能大于 right。并且left和right都要大于0。
Tips:
字符串可以直接用运算符'+'
helper(builder + '(', left-1, right);
helper(builder + ')', left, right-1);
Time Complexity：
O(N^2)
完整代码：
vector<string> result;
vector<string> generateParenthesis(int n)
{
int left = n, right = n;
helper("", left, right);
return result;
}
void helper(string builder, int left, int right)
{
if(left > right || left < 0 || right < 0)
return;
if(left == 0 && right == 0)
{
result.push_back(builder);
return;
}
helper(builder + '(', left-1, right);
helper(builder + ')', left, right-1);
}
4Sum
Description:
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.
Example:
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]
]
Link:
https://leetcode.com/problems/4sum/#/description
题目意思：
与3sum类似
解题方法：
dfs + two points
Time Complexity：
O(N^3)
完整代码：
vector<vector<int> > result;
vector<vector<int>> fourSum(vector<int>& nums, int target)
{
if(nums.size() < 4)
return result;
sort(nums.begin(), nums.end());
if(nums[nums.size() - 1] < 0)
return result;
vector<int> record;
helper(nums, target, record, 0);
return result;
}
void helper(vector<int>& nums, int target, vector<int>& record, int start)
{
if(record.size() == 2)
{
findTarget(nums, target, record, start);
return;
}
for(int i = start; i < nums.size(); i++)
{
if(i != start && nums[i] == nums[i-1])
continue;
int t = target - nums[i];
record.push_back(nums[i]);
helper(nums, t, record, i+1);
record.pop_back();
}
}
void findTarget(vector<int>& nums, int target, vector<int>& record, int start)
{
int left = start, right = nums.size() - 1;
while(left < right)
{
if(left != start && nums[left] == nums[left-1])
{
left++;
continue;
}
int temp = nums[left] + nums[right];
if(temp > target)
right--;
else
if(temp < target)
left++;
else
{
record.push_back(nums[left]);
record.push_back(nums[right]);
result.push_back(record);
left++;
right--;
record.pop_back();
record.pop_back();
}
}
}
K Closest Points
Description:
Given some points and a point origin in two dimensional space, find k points out of the some points which are nearest to origin.
Return these points sorted by distance, if they are same with distance, sorted by x-axis, otherwise sorted by y-axis.
找出离原点最近的k个点，按照一定顺序排序
Example:
Given points = [[4,6],[4,7],[4,4],[2,5],[1,1]], origin = [0, 0], k = 3
return [[1,1],[2,5],[4,4]]
Link:
http://www.lintcode.com/en/problem/k-closest-points/
解题思路：
用priority queue就可解决。
优先队列的比较方法：
bool function（type a, type b）
如果返回0，则队列中a排在前面，反之则b排在前面。
Tips:
for(Point p: points) { pq.push(p); if(pq.size() > k) pq.pop(); }
这段代码可以节省空间，并且能保证不会漏掉任何一个点。
Time Complexity：
O(N)
完整代码：
int getDistance(Point &a, Point &b)
{
return (a.x-b.x) * (a.x-b.x) + (a.y - b.y) * (a.y - b.y);
}
Point originPoint;
struct compare
{
bool operator() (Point &a, Point &b)
{
int diff = getDistance(a, originPoint) - getDistance(b, originPoint);
if(diff == 0)
diff = a.x - b.x;
if(diff == 0)
diff = a.y - b.y;
return diff < 0;
}
};
class Solution
{
public:
vector<Point> kClosest(vector<Point>& points, Point& origin, int k)
{
originPoint = origin;
priority_queue <Point, vector<Point>, compare> pq;
for(Point p: points)
{
pq.push(p);
if(pq.size() > k)
pq.pop();
}
vector <Point> result;
while(!pq.empty())
{
Point p = pq.top();
result.push_back(p);
pq.pop();
}
reverse(result.begin(), result.end());
return result;
}
};
Rotate Image解题报告
Description:
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Follow up:
Could you do this in-place?
Link:
https://leetcode.com/problems/rotate-image/#/description
解题方法：
先将矩阵按照逆对角线翻转，在按照上下的中线翻转即可。
Tips:
注意在翻转的时候只用遍历一半的元素，如果遍历所有的元素则不会有变换（因为在遍历另一半的时候又会被翻转回来）。
Time Complexity：
O(N^2)
完整代码：
void rotate(vector<vector<int>>& matrix)
{
int len = matrix.size();
if(len == 0)
return;
for(int i = 0; i < len; i++)
for(int j = 0; j < len-i; j++) //只能交换逆对角线一边的数
Swap(matrix[i][j], matrix[len-1-j][len-1-i]);
for(int i = 0; i < len/2; i++)
for(int j = 0; j < len; j++) //只能交换一半的数
Swap(matrix[i][j], matrix[len-1-i][j]);
}
void Swap(int& a, int& b)
{
int temp = a;
a = b;
b = temp;
}
Remove Duplicates from Sorted Array解题报告（用STL解决）
Description:
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example,
Given input array nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.
Link:
https://leetcode.com/problems/remove-duplicates-from-sorted-array/#/description
解题方法：
用STL的unique function解决
unique用法
unique会移除一个数组中相邻并且重复的元素，返回最后一个元素下一个位置的迭代器。
完整代码：
return std::unique(nums.begin(), nums.end()) - nums.begin();
Remove Duplicate Numbers in Array
Description:
Given an array of integers, remove the duplicate numbers in it.
You should:
- Do it in place in the array.
- Move the unique numbers to the front of the array.
- Return the total number of the unique numbers.
Example:
Given nums = [1,3,1,4,4,2], you should:
Move duplicate integers to the tail of nums => nums = [1,3,4,2,?,?].
Return the number of unique integers in nums => 4.
Actually we don't care about what you place in ?, we only care about the part which has no duplicate integers.
Link:
http://www.lintcode.com/en/problem/remove-duplicate-numbers-in-array/
解题思路：
这道题意思是去除数组中的重复数字，并且把不重复的数字移动到数组前面，并且返回不重复数字的个数。
要求do it in place in the array, 也就是在O(n)的空间内完成。
解题方法：
所以解题方法有2中：
1）O(n)时间，O(n)空间：用哈希表去重，再把哈希表里的元素重新放进数组里面，记录数量。
2）O(nlogn)时间，O(1)空间：首先对数组排序，然后用快慢指针解决，快慢指针在同一起点，因为已经排序所以重复数字会排在一起，所以快指针一个个读取数字，每当读到与慢指针不同的数字，慢指针首先往后走一格（保存之前的数），然后再把快指针所在的数放到慢指针的位置（获得到新的数）。不停重复这个过程直到快指针走完数组。慢指针所在的位置就是最后一个unique number的位置。
Tips:
nums[++count] = nums[i];
Time Complexity：
方法1：O(n)时间 O(n)空间
方法2：O(nlogn)时间 O(1)空间
完整代码：
方法1
int count = 0;
if(nums.size() == 0)
return count;
unordered_map <int, bool> maps;
for(int i : nums)
maps[i] = true;
for(auto a : maps)
nums[count++] = a.first;
return count;
方法2
int count = 0;
if(nums.size() == 0)
return count;
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size(); i++)
{
if(nums[i] != nums[count])
nums[++count] = nums[i];
}
return count+1;
Kth Largest Element in an Array解题报告
Description:
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.
Note:
You may assume k is always valid, 1 <= k <= array's length.
Example:
Given [3,2,1,5,6,4] and k = 2, return 5.
Link:
https://leetcode.com/problems/kth-largest-element-in-an-array/#/description
解题方法：
######解法1：
直接用sort函数排序，再输出对应的数即可。方法比较粗暴，但是也能AC。
######解法2：
使用了快速排序的**，快速排序中有一个步骤叫partition，因为求第k大的数其实是求整个数组排序以后一个固定位置的数（nums.size() - k这个位置，下面用k来代替这个index）：
partition的实质是在进行了该操作以后，该数组在pivot之前的数一定不大于（或者不小于）pivot，在pivot之后的数一定不小于（或者不大于）pivot。也就是说在以后的排序中，这个pivot的位置上的元素是不会变的（哪怕变了也是一样的数）。这就找到了一个比快速排序更快捷的方法（worst case依然和quick sort一样），
1、当我们需要求这个数组在排序以后在k位置上的数，如果k正好在一次partition后pivot的这个位置上，可以直接返回这个数。
2、否则在包含k的这个范围内不断进行partition，直到出现1的情况。
3、当快速排序范围缩小到一个数的时候，其实这个数已经是被排序好的，那么直接返回就可以了。
然后需要确认另一个问题，partition以后，我们怎么能得到这个pivot的位置：
假设在一次partition中，左边的index设为left，右边的设为right，partition完成以后pivot的index变成了p。那么在这次partition完成以后可能会出现三种情况（暂且先不管k相对于他们的位置）：
1、数组nums分布情况为: start..... right, left, ... p ...end
2、数组nums分布情况为: start..... p, ... right, left ...end
3、数组nums分布情况为: start..... right, p, left, ...end
然后再来分析k与他们的分布关系：
当start <= k =< right时，此时不用管p在哪，直接对start~right这部分继续做partition。
当left < k <= end时，同上。
当k不在这两个范围内，说明right和left并不是连续的，也就是中间必然只有一个p，也就是说k == p，所以此时直接返回nums[k]就可以了。
Time Complexity：
可能是O(N)，但是worst case依然是O(N^2)。·
完整代码：
int findKthLargest(vector<int>& nums, int k)
{
return helper(nums, 0, nums.size() - 1, nums.size() - k);
}
int helper(vector<int>& nums, int start, int end, int k)
{
if(start == end)
return nums[start];
int left = start, right = end;
int mid = nums[left + (right - left)/2];
while(left <= right)
{
while(nums[left] < mid && left <= right)
left++;
while(nums[right] > mid && left <= right)
right--;
if(left <= right)
{
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
if(right >= k && start <= k)
return helper(nums, start, right, k);
if(left <= k && end >= k)
return helper(nums, left, end, k);
return nums[k];
}
Reverse Integer
Description:
Reverse digits of an integer.
Example:
Example1: x = 123, return 321
Example2: x = -123, return -321
Link:
https://leetcode.com/problems/reverse-integer/#/description
题目意思：
反转一个int数字
Tips:
y = y * 10 + x1 % 10; y与x1的符号一致。
Time Complexity：
O(log10 X)
完整代码：
int reverse(int x)
{
int x1 = x;
long long y = 0;
while(x1)
{
y = y * 10 + x1 % 10;
x1 /= 10;
}
if(y > INT_MAX || y < INT_MIN)
return 0;
return y;
}
Min Stack解题报告
Description:
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.
Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.
Link:
https://leetcode.com/problems/min-stack/#/description
解题方法：
方法来源：https://discuss.leetcode.com/topic/18556/c-using-two-stacks-quite-short-and-easy-to-understand
使用2个栈s1，s2:
s1负责正常栈的储存。
s2储存每次出现最小的数的。
这样当s1删除到最小的数的时候，s2也删除栈顶的数。这样可以保证s2的栈顶一直是当前最小数。因为即使s1里面包含的当前第二小的数而s2不包含，需要用到这个第二小的数的时候，这个数早就被删除了。比如：
s1: 栈顶(2->1->3->4);
s2: 栈顶(1->3->4);
当删除1时，2早就不在s1中，所以接下来最小数是3。
Tips:
如果在面试中不允许使用stack，自己写List也可以实现这个方法。
Time Complexity：
O(1)
完整代码：
class MinStack {
private:
stack<int> s1;
stack<int> s2;
public:
void push(int x) {
s1.push(x);
if (s2.empty() || x <= getMin()) s2.push(x);
}
void pop() {
if (s1.top() == getMin()) s2.pop();
s1.pop();
}
int top() {
return s1.top();
}
int getMin() {
return s2.top();
}
};
Subsets II
Description:
Given a list of numbers that may has duplicate numbers, return all possible subsets
Notice:
Each element in a subset must be in non-descending order.
The ordering between two subsets is free.
The solution set must not contain duplicate subsets.
Example:
If S = [1,2,2], a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
Link:
http://www.lintcode.com/en/problem/subsets-ii/#
解题方法：
同样是DFS, 只是需要多一个去重步骤。
Tips:
去重代码：
if(i != start && S[i] == S[i-1]) continue;
当循环时碰到与上一个相同的元素直接continue
完整代码：
vector<vector<int> > result;
vector<vector<int> > subsetsWithDup(const vector<int> &S)
{
if(S.size() == 0)
{
result.push_back({});
return result;
}
vector<int> source = S;
sort(source.begin(), source.end());
vector<int> temp;
helper(source, temp, 0);
return result;
}
void helper(const vector<int> &S, vector<int> &temp, int start)
{
result.push_back(temp);
for(int i = start; i < S.size(); i++)
{
if(i != start && S[i] == S[i-1])
continue;
temp.push_back(S[i]);
helper(S, temp, i+1);
temp.pop_back();
}
return;
}
Subsets
Description:
Given a set of distinct integers, return all possible subsets.
Notice
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
Example:
If S = [1,2,3], a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[ ]
]
Link:
http://www.lintcode.com/en/problem/subsets/
解题方法：
DFS求解，注意notice里面的条件不能忽略。
Tips:
当nums为NULL时，依然有子集NULL
完整代码：
vector<vector<int> > subsets(vector<int> &nums)
{
vector<vector<int> > result;
vector<int> temp;
if(nums.size() == 0)
{
result.push_back(temp); //当nums为NULL时，依然有子集NULL
return result;
}
sort(nums.begin(), nums.end());
helper(nums, result, temp,0);
return result;
}
void helper(vector<int> &nums, vector<vector<int> > &result, vector<int> &temp, int start)
{
result.push_back(temp);
for(int i = start; i < nums.size(); i++)
{
temp.push_back(nums[i]);
helper(nums, result, temp, i+1);
temp.pop_back();
}
return;
}
Sample
Description:
Link:
解题方法：
Tips:
Time Complexity：
完整代码：
Palindrome Linked List解题报告
Description:
Given a singly linked list, determine if it is a palindrome.
Follow up:
Could you do it in O(n) time and O(1) space?
Link:
https://leetcode.com/problems/palindrome-linked-list/#/description
解题方法：
难点在于如果在O(n) time and O(1) space解决这个问题。
可以用找链表中位数+反转后一半链表的方法处理链表，然后对比左半段链表和右半段链表。
找中位数用快慢指针非常简单，因为实际上是找到右半段链表前面一个结点，所以都不需要考虑奇偶问题，当快指针触底直接返回慢指针就可以。
不用额外空间反转链表(递归)：
输入参数：右边结点的第一个作为curr，和这个结点的前一个结点作为prev。
函数出口：当curr->next == NULL时，直接修改curr的next为记录的前一个节点，返回这个节点也就是反转后的head。
函数体：用一个next记录curr->next，然后使curr->next = prev；完成一次反转，将next作为下一次的curr，现在的curr作为下一次的prev。
Tips:
在反转链表时，不要把prev初始化为中位数的那个结点，这样最后比较的时候会进入死循环，应该把prev初始化为NULL。
Time Complexity：
时间：O(N)
空间：O(1)
完整代码：
bool isPalindrome(ListNode* head)
{
if(head == NULL || head->next == NULL)
return true;
ListNode* median = findMedian(head);
ListNode* rList = reverseList(NULL, median->next); //初始化为NULL
ListNode* lList = head;
while(rList != NULL)
{
if(rList->val != lList->val)
return false;
rList = rList->next;
lList = lList->next;
}
return true;
}
ListNode* reverseList(ListNode* prev, ListNode* curr)
{
if(curr->next == NULL)
{
curr->next = prev;
return curr;
}
ListNode* N = curr->next;
curr->next = prev;
return reverseList(curr, N);
}
ListNode* findMedian(ListNode* head)
{
ListNode* slow = head;
ListNode* fast = head;
while(fast != NULL)
{
if(fast->next == NULL || fast->next->next == NULL)
return slow;
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
Two Sum - Input array is sorted
Description:
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.
Example:
Given nums = [2, 7, 11, 15], target = 9
return [1, 2]
Link:
http://www.lintcode.com/en/problem/two-sum-input-array-is-sorted/
解题思路：
当input array已经被排序的时候，数组中两个数相加最小的情况是头两个数相加，相加最大的情况是最后两个数相加。所以用一头（start）一尾（end）两个指针，当nums[start] + nums[end] > target的时，头指针向后走，当nums[start] + nums[end] < target时，尾指针向前走。当相等时就是本题要找的两个index。否则即无解。
Time Complexity：
O(n)
完整代码：
vector<int> twoSum(vector<int> &nums, int target)
{
vector<int> result;
if(nums.size() < 2)
return result;
int start = 0, end = nums.size() - 1;
while(start < end)
{
int temp = nums[start] + nums[end];
if(temp < target)
start++;
else
if(temp >target)
end--;
else
{
result.push_back(start + 1);
result.push_back(end + 1);
return result;
}
}
return result;
}
Two Sum - Less than or equal to target
Description:
Given an array of integers, find how many pairs in the array such that their sum is less than or equal to a specific target number. Please return the number of pairs.
Example:
Given nums = [2, 7, 11, 15], target = 24.
Return 5.
2 + 7 < 24
2 + 11 < 24
2 + 15 < 24
7 + 11 < 24
7 + 15 < 25
Link:
http://www.lintcode.com/en/problem/two-sum-less-than-or-equal-to-target/
题目解读：
这道题给定了一个数组与一个target数，要求返回数组中“和”小于或者等于target数的两个数组合的个数。
解题方法：
首先将数组排序，然后使用头尾指针解决，当头尾两个数相加大于target，尾指针向前移；否则尾指针前面到头指针所有的数与头指针的数相加都会小于或等于target，所以count += end - start. 直到头指针和尾指针相交循环结束。
Time Complexity：
O(nlogn)
完整代码：
int twoSum5(vector<int> &nums, int target)
{
int count = 0;
if(nums.size() < 2)
return count;
sort(nums.begin(), nums.end());
int start = 0, end = nums.size() - 1;
while(start < end)
{
int temp = nums[start] + nums[end];
if(temp > target)
end--;
else
{
count += end - start;
start++;
}
}
return count;
}
Divide Two Integers解题报告
Description:
Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
Link:
https://leetcode.com/problems/divide-two-integers/#/description
解题方法：
可用减法代替除法，用左移的方法可以让divisor指数增长，再去与dividend做减法。
答案因为不能用乘法表示（比如divisor的2的几次方倍），所以代替方法是用1<<的操作算出来。
完整代码：
int divide(int dividend, int divisor)
{
if(divisor == 0 || (dividend == INT_MIN && divisor == -1))
return INT_MAX;
long d1 = labs(dividend), d2 = labs(divisor), ans = 0;
while(d1 >= d2)
{
int cnt = 1;
while((d2<<cnt) <= d1)
cnt++;
ans += 1<<(cnt-1); //用左移算出倍数
d1 -= d2<<(cnt-1); //减法代替除法
}
return (dividend > 0 ^ divisor > 0) ? -ans : ans;
}
High Five
Description:
There are two properties in the node student id and scores, to ensure that each student will have at least 5 points, find the average of 5 highest scores for each person.
给出一系列学生分数，求出每个学生最高的5门分数的平均分。
Example:
Given results = [[1,91],[1,92],[2,93],[2,99],[2,98],[2,97],[1,60],[1,58],[2,100],[1,61]]
Return
Link:
http://www.lintcode.com/en/problem/high-five/
解题思路：
本题重点是如果存储每个学生最高的5门的成绩，这里针对每个学生可以使用一个vector，这个vector容积为5，从第0到第4位以递减的方式储存5门成绩；当输入一个成绩时，从第0位开始比较，如果输入的成绩大于这一位置的原有成绩时，数组由这一位置整体向后挪一位，并且更新这一位置的成绩。
Time Complexity：
O(N)
完整代码：
map<int, double> highFive(vector<Record>& results)
{
map<int, vector<double>> record;
map<int, double> output;
for(Record r : results)
{
if(record[r.id].size() == 0)
{
vector<double> temp(5, 0);
helper(temp, r.score);
record[r.id] = temp;
}
else
{
helper(record[r.id], r.score);
}
}
for(auto a : record)
{
double sum = 0;
for(double d : a.second)
sum += d;
output[a.first] = sum/5;
}
return output;
}
void helper(vector<double>& v, int score)
{
for(int i = 0; i < 5; i++)
{
if(score <= v[i])
continue;
else
{
for(int j = 4; j > i; j--)
v[j] = v[j-1];
v[i] = score;
return;
}
}
}
Count Primes解题报告
Description:
Count the number of prime numbers less than a non-negative number, n.
Link:
https://leetcode.com/problems/count-primes/#/description
解题方法：
Time Complexity：
O(N*logN)
完整代码：
int countPrimes(int n)
{
if(n < 3)
return 0;
vector<bool> prime(n, true);
int cnt = 0;
for(int i = 2; i < n; i++)
{
if(!prime[i])
continue;
int ftr = 2;
while(i * ftr < n)
prime[i * ftr++] = false;
cnt++;
}
return cnt;
}
Construct Binary Tree from Preorder and Inorder Traversal
Description:
Given preorder and inorder traversal of a tree, construct the binary tree.
Link:
题目意思：
给出二叉树的先序和中序遍历结果，重构二叉树。
解题方法：
对于先序遍历分析：根左右
根节点永远在数组第一个（无论是整个二叉树的先序遍历还是二叉树中一个子树的先序遍历），在根节点之后，数组中的元素可以分为左右子树两组（并且元素位置不会交叉）。
对于中序遍历分析：左根右
如果在数组中能确定代表根节点的元素，那么该元素左边的部分为根节点的左子树，右边为右子树。
总结：
由以上观察可以总结出解题方法。最开始由先序得到一个根节点（此时是一棵树树），然后通过在中序上找到该节点可以知道这个根节点的左右子树总共有多少节点，再从先序中划分出左右子树，得到两个根节点（得到左右子树两棵树）。使用分治的**可以完成。
Tips:
在中序遍历数组中找根节点位置时候每次操作为O(N)，如果使用哈希表可以减小到O(1)。
Time Complexity：
使用哈希表为O(N)，遍历则为O(N^2)
完整代码：
class Solution
{
public:
unordered_map<int, int> um; //哈希表记录中序数组每个元素位置
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
{
if(preorder.size() != inorder.size())
return NULL;
buildindex(inorder);
return build(preorder, 0, preorder.size() - 1, 0, inorder.size() - 1);//用几个int变量来实现对数组的分割
}
void buildindex(vector<int>& inorder)//建立索引
{
for(int i = 0; i < inorder.size(); i++)
um[inorder[i]] = i;
}
TreeNode* build(vector<int>& preorder, int prestart, int preend, int instart, int inend)
{
if(prestart > preend)
return NULL;
TreeNode *temp =new TreeNode(preorder[prestart]);
int poi = um[temp->val];
temp->left = build(preorder, prestart + 1, prestart + poi - instart, instart, poi-1);
temp->right = build(preorder, prestart + poi - instart + 1, preend, poi + 1, inend);
return temp;
}
};
此题参考了：http://blog.csdn.net/sgbfblog/article/details/7783935 的帖子。
Rotate Function解题报告
Description:
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).
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.
Link:
https://leetcode.com/problems/rotate-function/#/description
解题方法：
1、暴力破解，通过F(k)的方程对每次进行环位移的数组来求出解，也能AC。
2、通过观察得知，F(k)都可以由F(k-1)求出，方程为F(i-1) + sum - n*A[n-i] = F(i)，其中sum为数组元素的和。所以求出F(0)和sum就可以把剩下的算出。
Time Complexity：
解法一：O(N^2)
解法二：O(N)
完整代码：
解法一：
int maxRotateFunction(vector<int>& A)
{
int max = INT_MIN;
if(A.size() == 0)
return 0;
for(int k = 0; k < A.size(); k++)
{
int sum = 0;
int i = 0;
for(; i < k; i++)
sum += (A[A.size() - k + i] * i);
for(int j = 0; j < A.size() - k; j++, i++)
sum += (A[j] * i);
max = sum > max ? sum : max;
}
return max;
}
解法二：
int maxRotateFunction(vector<int>& A)
{
if(A.size() == 0)
return 0;
int f = 0, sum = 0, n = A.size();
for(int i = 0; i < n; i++)
{
f += A[i] * i; //算出F(0)
sum += A[i]; //算出sum
}
int max = f;
for(int i = 1; i < n; i++)
{
f = f + sum - (n * A[n - i]); //F(i-1) + sum - n*A[n-i] = F(i)
max = f > max ? f : max;
}
return max;
}
LFU Cache解题报告
Description:
Design and implement a data structure for Least Frequently Used (LFU) 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 reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.
**Follow up:**Could you do both operations in O(1) time complexity?
Example:
LFUCache cache = new LFUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.get(3); // returns 3.
cache.put(4, 4); // evicts key 1.
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4
Link:
https://leetcode.com/problems/lfu-cache/#/description
解题方法：
想要在O(1)的时候内完成get()由key映射到node的哈希表keyToNode是不可免的。
当内存满时，需要删除使用频率最少的数，如果有几个相同的数则删除最早的那个。所以可以想到要把相同频率的数归纳到一起，我们还需要另一个由频率映射到list的另一个哈希表freToList。每个list里面储存的是相同频率的不同node或key。
当使用get()函数时，我们需要专门找到某个node，使其频率+1。为了能在O(1)的时候内完成这个操作。每个node除了储存value，频率以外，还需要储存的是其在freToList里某个list的迭代器。
由此，在O(1)时间完成频率的更新和加减node都可以实现了。最后一步问题很容易让人想不明白：当需要删除最少使用的node时，如何得到最少频率minFre从而在freTolist进行操作？
有几个需要认清的细节可以解决这个问题：
1、当有新的node加入的时候，minFre一定为1。
2、使minFre不为1的情况只有进行get()成功的时候或者用put()更新一个node的value的时候。
3、以上两个操作都不会使一个数的频率进行跳跃增长（即每次都只会让一个数的频率+1）。
由以上3点可以得出我们怎样不会使minFre出错的方法：
1、当有新的数加入的时候，使minFre = 1；
2、当对一个数的频率进行更改后，如果freToList[minFre].size() == 0,那么minFre一定为minFre++。
Tips:
使用list来储存相同频率的数，每次从list的前面插入，要删除时从list的后面删除。这样每次就会删除最早的最少使用次数的node。
如果每次从后面插入那么迭代器不好赋值，原因如下：
Time Complexity：
O(1)
完整代码：
class Node
{
public:
int val;
int fre;
list<int>::iterator iter;
Node(int v, int f): val(v), fre(f) {}
};
class LFUCache
{
private:
unordered_map<int, Node*> keyToNode;
unordered_map<int, list<int>> freToList;
int capacity;
int size;
int minFre;
public:
LFUCache(int capacity)
{
size = 0;
this->capacity = capacity;
}
int get(int key)
{
if(keyToNode[key] == NULL)
return -1;
list<int>::iterator change = keyToNode[key]->iter;
freToList[keyToNode[key]->fre++].erase(change);
freToList[keyToNode[key]->fre].push_front(key);
keyToNode[key]->iter = freToList[keyToNode[key]->fre].begin();
if(freToList[minFre].size() == 0)
minFre++;
return keyToNode[key]->val;
}
void put(int key, int value)
{
if(capacity <= 0)
return;
if(keyToNode[key] == NULL)
{
Node* curr = new Node(value, 1);
freToList[1].push_front(key);
curr->iter = freToList[1].begin();
keyToNode[key] = curr;
size++;
if(size > capacity)
{
keyToNode.erase(freToList[minFre].back());
freToList[minFre].pop_back();
size--;
}
//minFre should changed after(instead of before) we remove the LFU node,
//otherwise new nodes wouldn't get added in some special case.
minFre = 1;
}
else
{
get(key);
keyToNode[key]->val = value;
}
}
};
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.