5. Longest Palindromic Substring
96. Unique Binary Search Trees
122. Best Time to Buy and Sell Stock II
124. Binary Tree Maximum Path Sum
138. Copy List with Random Pointer
Permutation & Combination & Rotation
Given a string，find the longest Palindromic substring
expand from the center: find the char cluster first (cluster constructed by the same chars)，then expand to the left and the right.
string longestPalindrome(string s) {
if (s.empty()) return "";
if (s.size() == 1) return s;
int min_start = 0, max_len = 1;
for (int i = 0; i < s.size();) {
if (s.size() - i <= max_len / 2) // max_len found
break;
int j = i, k = i;
while (k < s.size()-1 && s[k+1] == s[k]) ++k; // Skip duplicate characters.
i = k+1;
while (k < s.size()-1 && j > 0 && s[k + 1] == s[j - 1]) { ++k; --j; } // Expand.
int new_len = k - j + 1;
if (new_len > max_len) { min_start = j; max_len = new_len; }
}
return s.substr(min_start, max_len);
}
Given a vector of the heights of walls, find the maximum water that could be trapped
Start from the left-most and the right-most walls, and then travese to the center, finding higher walls/ more trapped volunm.
int maxArea(vector<int>& height) {
int water = 0;
int i = 0, j = height.size() - 1;
while (i < j) {
int h = min(height[i], height[j]);
water = max(water, (j - i) * h);
while (height[i] <= h && i < j) i++;
while (height[j] <= h && i < j) j--;
}
return water;
}
给一个vector，找出所有符合a+b+c = 0 的组合
先sort。
traverse这个sorted array. 每到一个位置时，取当前数，下一个数，和数组最后一个数（最大数）求和。如果大于零，向后移动指针；如果小于零，则向前移动指针；等于零则为要找的组合。
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
std::sort(nums.begin(), nums.end());
if (nums.size() < 3) return res;
for (int i = 0; i < nums.size()-2; ++i) {
if ((i > 0) && (nums[i-1] == nums[i])) continue;
int l = i+1;
int r = nums.size()-1;
while (l < r) {
if (nums[i] + nums[l] + nums[r] < 0) l++;
else if (nums[i] + nums[l] + nums[r] > 0 ) r--;
else {
res.push_back(vector<int>{nums[i], nums[l], nums[r]});
r--;
l++;
while ((nums[l-1] == nums[l]) && (l < r)) l++; //get rid of duplicates
while ((nums[r+1] == nums[r]) && (l < r)) r--; //get rid of duplicates
}
}
}
return res;
}
给一个vector和一个target value，找出 a+b+c 最接近target 的组合
一样的思路，记录最接近的和即可
int threeSumClosest(vector<int>& nums, int target) {
if (nums.size() == 0) return 0;
else if (nums.size() == 1) return nums[0];
else if (nums.size() == 2) return nums[0] + nums[1];
int res = nums[0] + nums[1] + nums[2];
std::sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size()-2; ++i) {
if ((i > 0) && (nums[i-1] == nums[i])) continue;
int l = i+1;
int r = nums.size()-1;
while (l < r) {
int curSum = nums[i] + nums[l] + nums[r];
if (curSum == target) return target;
if (std::abs(curSum - target) < std::abs(res - target)) res = curSum;
if (curSum > target) {
r--;
while (nums[r+1] == nums[r] && (l < r)) r--;
}
else {
l++;
while (nums[l-1] == nums[l] && (l < r)) l++;
}
}
}
return res;
}
设一个container（我用的是vector，应该可以用priority queue），把每个lists当前的element装起来，找到这个container里面的min，连接到新的list上。
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.size() == 0) return nullptr;
vector<int> v(lists.size());
ListNode* res = new ListNode(0);
ListNode* cur = res;
short flag = lists.size();
for (unsigned int i = 0; i < lists.size(); ++i ) {
if (lists[i] == nullptr) v[i] = MAX_VAL;
else v[i] = lists[i]->val;
}
for (unsigned int j = 0; j < lists.size(); ++j ) {
if (v[j] == MAX_VAL) --flag;
}
while (flag) {
auto it = min_element(v.begin(), v.end());
cur->next = lists[it - v.begin()];
cur = cur->next;
lists[it - v.begin()] = lists[it - v.begin()]->next;
if (lists[it - v.begin()] == nullptr) {
v[it - v.begin()] = MAX_VAL;
--flag;
}
else {
v[it - v.begin()] = lists[it - v.begin()]->val;
}
}
return res->next;
}
两个两个合并（divid and conquer）
给一个排列，求下一个排列
From wiki：
- Find the largest index k such that nums[k] < nums[k + 1]. If no such index exists, just reverse nums and done.
- Find the largest index l > k such that nums[k] < nums[l].
- Swap nums[k] and nums[l].
- Reverse the sub-array nums[k + 1:].
void nextPermutation(vector<int>& nums) {
if (nums.empty() || nums.size() == 1) return;
auto iter = nums.end() - 2;
while(iter >= nums.begin()) {
if (*iter < *(iter + 1)) break;
iter --;
}
if (iter < nums.begin()) {
reverse(nums.begin(), nums.end());
return;
}
auto iter2 = nums.end() - 1;
while(iter2 > iter) {
if (*iter2 > *iter) break;
iter2--;
}
// int temp = *iter;
// *iter = *iter2;
// *iter2 = temp;
iter_swap(iter, iter2);
reverse(iter+1, nums.end());
}
给一个candidate set 和一个target，给出所有和为target的组合。每个数字可用多次
Input: candidates = [2,3,6,7], target = 7,
A solution set is: [ [7], [2,2,3] ]
Backtracking
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
//use backtracking
sort(candidates.begin(), candidates.end());
vector<vector<int>> res;
vector<int> temp;
bt(candidates, target, res, temp, 0);
return res;
}
void bt(vector<int>& candidates, int target, vector<vector<int>>& res,vector<int>& temp, int pos) {
if(target == 0) {
//valid result
res.push_back(temp);
return;
}
if(pos >= candidates.size() || target < candidates[pos]) {
//bounding: not valid result
return;
}
for(int i = pos; i < candidates.size(); ++i) {
temp.push_back(candidates[i]);
bt(candidates, target - candidates[i], res, temp, i);
temp.pop_back();
}
}
Dynamic Programming
每个数字只能用一次，求unique combinations。
和39题一样，只要跳过duplicates就好了
for(int i = pos; i < candidates.size();++i) {
if(i&&candidates[i]==candidates[i-1] &&i>pos) continue;
temp.push_back(candidates[i]);
bt(candidates, target - candidates[i], res, temp, i + 1);
temp.pop_back();
}
注意： i > pos 是为了防止特殊情况：如果开头第一个数（位于pos）和前一个数（pos-1）是一样的时候，不视为dup
给一个unsorted array，求第一个没出现的正整数
EX：[-1，1，2，-4，8，4]-> 3
要求：O(n) time, O(1) space
traverse这个array，如果一个数是正整数，并且在array的size范围内，把这个数放到对应的位置上。
traverse第二遍，第一个位置和所处的数不对应的，就是最小的没出现的正整数。
int firstMissingPositive(vector<int>& nums) {
if (nums.empty()) return 1;
if (nums.size() == 1) return (nums[0] == 1)? 2 : 1;
for (int i = 0; i < nums.size(); ++i ) {
if (nums[i] > 0 && nums[i] <= nums.size() && nums[i] != i+1 && nums[nums[i]-1] != nums[i]) {
//nums[nums[i]-1] != nums[i]为了防止无限循环
swap(nums[nums[i]-1], nums[i]);
i--;
}
}
int i = 0;
while (i < nums.size()) {
if (nums[i] != i+1) return i+1;
i++;
}
return i+1;
}
给一个vector，记录的是墙的高度，求能困住的水的体积（可以对比#11）
-
Brute Force: 每一格去找左边的最高和右边的最高，再取min（left_max, right_max），这一格水的高度就是min（left_max, right_max)- height[i].
-
Dynamic Programming:因为每次要找left_max和right_max是重复的，可以把找到的记下来。
-
2-pointers：在一个iteration里解决问题：
- Initialize left pointer to 0 and right pointer to size-1
- While left<right, do:
- If height[left] is smaller than height[right]
- If height[left] ≥ left_max, update left_max
- Else add left_max−height[left] to ans
- Add 1 to left (check next left).
- Else
- If height[right]≥right_max, update right_max
- Else add right_max−height[right] to ans
- Subtract 1 from right (check next right).
- If height[left] is smaller than height[right]
注： 因为update的都是较小的那一边，所以不用再比较min（left_max, right_max）
int trap(vector<int>& height) {
if (height.size() < 3) return 0;
int l = 0, r = height.size() - 1, res = 0;
int lm = height[l], rm = height[r];
while(l < r) {
int cl = height[l], cr = height[r];
if (cl < cr) {
if (cl < lm) res += (lm-cl);
else lm = cl;
l++;
}
else {
if (cr < rm) res += (rm-cr);
else rm = cr;
r--;
}
}
return res;
}
给一个正整数vector，每一个数代表能向前跳的距离，求从index 0 跳到最后一个index的最小步数
BFS：把整个vector分成几个level（一步之类能到的index是level 1，两步之内是level 2），一旦最后一个index出现在level里，return这个level
int jump(vector<int>& nums) {
int n = nums.size();
if(n<2)return 0;
int level=0,start = 0, end = 0;
while(true){
level++;
int maxend = end + 1;
for(;start<=end;start++){
maxend =max(maxend,nums[start]+start);
if(maxend>=n-1)return level;
}
end=maxend;
}
return 0; //never reach here actually
}
给一个不重复的数组，求排列
Backtracking：每一个recursive call都排好一位，push_back之后再还原
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
bt(nums, res, 0);
return res;
}
void bt(vector<int>& nums, vector<vector<int>>& res, int pos) {
if (pos >= nums.size()) {
res.push_back(nums);
return;
}
for (int i = pos; i < nums.size(); ++i) {
swap(nums[pos], nums[i]);
bt(nums, res, pos+1);
swap(nums[pos], nums[i]);
}
}
把一个matrix顺时针转90度
Credit to leetcode user @shichaotan:
先reverse，然后做transpose。
void rotate(vector<vector<int>>& matrix) {
reverse(matrix.begin(), matrix.end());
for (int i = 0; i < matrix.size(); ++i) {
for (int j = i + 1; j < matrix[i].size(); ++j)
swap(matrix[i][j], matrix[j][i]);
}
}
给一个string的vector，输出里把相同字母出现相同字数的string归到一起。
数字母，用字母个数作为key在一个map里存储string
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> m;
for (string s : strs) {
string stamp = charCount(s);
m[stamp].push_back(s);
}
vector<vector<string>> res;
for (auto p : m) {
res.push_back(p.second);
}
return res;
}
string charCount(string s) {
int counter[26] = {0};
string res = "";
for (int i = 0; i < s.size(); ++i) {
counter[s[i] - 'a'] += 1;
}
for (int j = 0; j < 26; ++j) {
if (counter[j] != 0) res+= string(counter[j], j + 'a');
}
return res;
}
给一个vector，找出和最大的subarray。
traverse这个array，一旦前面的和小于零即舍去不要。
public:
int maxSubArray(vector<int>& nums) {
int sum = 0, res = min_val;
for (int i : nums) {
sum += i;
res = (res<sum)? sum : res;
sum = (sum >=0)? sum : 0;
}
return res;
}
private:
int min_val = -2147483647;
//这里把res设成最小值是为了整个vector都是负数的情况
Credit to Leetcode user @sumedhds
int maxSubArray(vector& nums) {
int reset=0;
int maxsum=0;
for(int i=0; i<nums.size(); i++){
reset += nums[i];
reset = max(reset, nums[i]); //这里先比较，如果全是负数，那么最小的负数就会被留下来
maxsum = max(maxsum, reset);
}
return maxsum;
}
给一个vecter里面都是interval，把能合并的合并了
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
这题不难，但是回顾一下lambda expression：
lambda 表达式
[capture list] (params list) mutable exception-> return type { function body }
bool cmp(int a, int b)
{
return a < b;
}
int main{
vector<int> myvec{ 3, 2, 5, 7, 3, 2 };
vector<int> lbvec(myvec);
sort(myvec.begin(), myvec.end(), cmp); // 旧式做法
sort(lbvec.begin(), lbvec.end(), [](int a, int b) -> bool { return a < b; }); // Lambda表达式
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (ins.empty()) return vector<Interval>{};
vector<Interval> res;
sort(ins.begin(), ins.end(), [](Interval a, Interval b){return a.start < b.start;});
res.push_back(ins[0]);
for (int i = 1; i < ins.size(); i++) {
if (res.back().end < ins[i].start) res.push_back(ins[i]);
else
res.back().end = max(res.back().end, ins[i].end);
}
return res;
}
BFS
给两个数，n是可用的正整数（n=3 即可用 1，2，3） k是要给出的第几个组合。
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
一个一个排：第i个位置的数为 i + k/(n-1)!
string getPermutation(int n, int k) {
int i,j,f=1;
string s(n,'0');
//init
for(i=1;i<=n;i++){
f*=i; // f = n!
s[i-1]+=i; // make s become 1234...n
}
for(i=0,k--;i<n;i++){
f/=n-i; // how many perms with n-i-1 numbers
j=i+k/f; // calculate index of char to put at s[i]
char c=s[j];
s.erase(s.begin() + j); //get rid of the char we want
s.insert(s.begin() + i, c); // put it at the right place
k%=f; //finish arraging one char, move to the next
}
return s;
}
俩string代表俩binary number，输出他们的和（同样是string of binary number）
Credit to Leetcode User @makuiyu :
string addBinary(string a, string b)
{
string s = "";
int c = 0, i = a.size() - 1, j = b.size() - 1;
while(i >= 0 || j >= 0 || c == 1)
{
c += i >= 0 ? a[i --] - '0' : 0;
c += j >= 0 ? b[j --] - '0' : 0;
s = char(c % 2 + '0') + s;
c /= 2;
}
return s;
}
求x的开方（最接近的整数）
Newton's Method是一种求根的近似值的迭代方法。
要求x的开方，相当于是解f(a) = a^2 - x 的根。
我们用x作为近似值，根据Newton's Law: a_(n+1) = a_n - (f(a_n)/f'(a_n)), 带入f得a_(n+1) = a_n - (a_n^2 - x)/2a_n = (a_n^2 - x)/2a_n = (a_n - x/a_n)/2
所以每一次迭代，r = (r + x/r) / 2
int mySqrt(int x) {
long r = x;
while (r*r > x)
r = (r + x/r) / 2;
return r;
}
给一个代表路径的string，输出最简路径。
Input: "/home/"
Output: "/home"
Input: "/a/b/../"
Output: "/a"
..表示上一层
Input: "/a/b/./"
Output: "/a/b"
.表示当前层
把string变成stringstream，以‘/’断开，再逐个判断。
用vecotr装被split出来的string，如果要返回上一层，就pop_back
string simplifyPath(string path) {
vector<string> s;
string tmp;
stringstream ss(path);
while(getline(ss,tmp,'/')) {
if (tmp == "" or tmp == "."/* case // and case /./ */) continue;
if (tmp == ".." and !s.empty() /* case /../ */) s.pop_back();
else if (tmp != "..") s.push_back(tmp);
}
string res;
for(auto str : s) res += "/"+str;
return res.empty() ? "/" : res;
}
一个vector里只有0，1，2三种数。Sort这个array，把相同的数整理到一起。（输出的vector因该是[0,0,0...1,1,1.....2,2,2]）
标记0和2的位置：pos0 = 0， pos2 = size() - 1
如果是0就和pos0 swap，并且++pos0；同理如果是2就和pos2 swap，--pos2.
最后1自然被留在了中间。
void sortColors(vector<int>& nums) {
if (nums.empty() || nums.size() == 1) return;
int zeroP = 0, twoP = nums.size() - 1;
// I was considering about the dups, but it actually is not necessary
//while (zeroP < nums.size() && nums[zeroP] == 0) zeroP++;
//while (twoP >= 0 && nums[twoP] == 2) twoP--;
//if (zeroP > twoP) return;
for (int i = zeroP; i <= twoP; ++i) {
if (nums[i] == 0 && i != zeroP) swap(nums[i--], nums[zeroP++]);
else if (nums[i] == 2 && i!=twoP) swap(nums[i--], nums[twoP--]);
}
}
Credit to LeetCode User @shichaotan:
标记0，1，2三个位置：pos0 = -1， pos1 = -1， pos2 = -1.
每check一个数，如果是0，三个pos都加；如果是1，加pos1和pos2；如果是2，只加pos2.
void sortColors(int A[], int n) {
int n0 = -1, n1 = -1, n2 = -1;
for (int i = 0; i < n; ++i) {
if (A[i] == 0)
{
A[++n2] = 2; A[++n1] = 1; A[++n0] = 0;
}
else if (A[i] == 1)
{
A[++n2] = 2; A[++n1] = 1;
}
else if (A[i] == 2)
{
A[++n2] = 2;
}
}
}
n:可用的数 （n=4 即 1，2，3，4）
k: 生成k个数的组合
思路和perm一样，用backtracking
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> res;
vector<int> temp(k, 0);
if(k == 0) {
res.push_back(temp);
return res;
}
bt(n, k, res, temp, 1, 0);
return res;
}
void bt(int n, int k, vector<vector<int>>& res, vector<int>& temp, int start, int len) {
if(len == k) {
res.push_back(temp);
return;
}
for (int i = start; i <= n; ++i) {
temp[len++] = i;
bt(n, k, res, temp, i+1, len);
len--;
}
}
// void bt(int n, int k, vector<vector<int>>& res, vector<int>& temp, int start) {
// if(temp.size() == k) {
// res.push_back(temp);
// return;
// }
// for (int i = start; i <= n; ++i) {
// temp.push_back(i);
// bt(n, k, res, temp, i+1);
// temp.pop_back();
// }
// }
给一个数组，输出所有的subset
和perm的思路一样，只不过不管subset的size有多少都push_back到final res里
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> res;
if (nums.empty()) return res;
vector<int> temp;
bt(nums, temp, res, 0);
return res;
}
void bt(vector<int>& nums, vector<int>& temp, vector<vector<int>>& res, int start) {
res.push_back(temp);
for (int i = start; i < nums.size(); ++i) {
temp.push_back(nums[i]);
bt(nums, temp, res, i+1);
temp.pop_back();
}
}
Credit to LeetCode User @jianchao-li
首先，给的数组长度是n，那么就有2^n个subset
根据观察，1出现一次隔开一个，2连续出现两次然后空开两个，以此类推
[], [ ], [ ], [ ], [ ], [ ], [ ], [ ]
[], [1], [ ], [1 ], [ ], [1 ], [ ], [1 ]
[], [1], [2], [1, 2], [ ], [1 ], [2 ], [1, 2 ]
[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]
vector<vector<int>> subsets(vector<int>& nums) {
int n = nums.size(), p = 1 << n // size of subset;
vector<vector<int>> subs(p, []) //result;
for (int i = 0; i < p; i++) {
for (int j = 0; j < n; j++) {
if ((i >> j) & 1) {
subs[i].push_back(nums[j]);
}
}
}
return subs;
}
注：这种方法在有dups的时候无效，因为无法确定subset有多少个
给一个数n, 求用1，2.... n这n个数能组成多少个不同的binary search tree
Credit to LeetCode User @leo_mao:
n个数分别做root： 1 as root: # of trees = F(0) * F(n-1) // F(0) == 1 2 as root: # of trees = F(1) * F(n-2) 3 as root: # of trees = F(2) * F(n-3) ... n-1 as root: # of trees = F(n-2) * F(1) n as root: # of trees = F(n-1) * F(0)
所以循环的时候，memo[n-1]代表有n-1个数的时候有多少个bst；到n时，循环一遍memo，F(n) = F(0) * F(n-1) + F(1) * F(n-2) + F(2) * F(n-3) + ... + F(n-2) * F(1) + F(n-1) * F(0)
int numTrees(int n) {
vector<int> dp(n+1, 0);
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 1; j <=i; ++j) dp[i] += dp[j-1]*dp[i-j];
}
return dp[n];
}
Check if the given tree is symmetric.
Example:
1
/ \
2 2
/\ /\
3 4 4 3This is symmetric.
首先根的值要一样。
然后左右树要是镜像的。
镜像：
首先根值要一样。
然后左树的左子树要等于右树的右子树，左树的右子树要等于右树的左子树。
bool isSymmetric(TreeNode* root) {
return isMirror(root, root);
}
bool isMirror(TreeNode* left, TreeNode* right) {
if (!left && ! right) return true;
if (!left || !right) return false;
else return (left->val == right->val) && isMirror(left->left, right->right) && isMirror(left->right, right->left);
}
给一个array表示stock每天的价格，可以任意次数买卖，唯一的限制是必须卖了之后再买。求最大profit。
不难但是思路可能想不到。如果价格上涨，那就一直不卖。在价格下跌的前一天卖。profit就是连续上涨时的价差的和。
int maxProfit(vector<int>& prices) {
int max = 0;
for (int i = 1; i < prices.size(); ++i) {
if (prices[i] > prices[i-1]) {
max+= prices[i] - prices[i-1];
}
}
return max;
}
给一个binary tree，求sum最大的path。
这里的path可以是任意被parent-child边连起来的路线
从leaf往root，一共两种可能：
- curNode被包含在里面，那么max就是cur->val + leftmax + rightmax
- curNode不被包含，那么max就是max（leftmax，rightmax）
public:
int maxPathSum(TreeNode* root) {
helper(root);
return curMax;
}
private:
int curMax = - (1 << 16);
int helper (TreeNode* root){
if (!root) return 0;
int l = max(0, helper(root->left));
int r = max(0, helper(root->right));//这里如果rmax比lmax大的话，lmax就自动被覆盖了
curMax = max(curMax, l+r+root->val);
return max(l, r) + root->val;
}
一共n个站。给俩数组：gas[n]一个是在第n站能补给的油量，cost[n]是n开到n+1消耗的油量。
问能不能开一个循环。如果不能返回-1，能的话返回哪一站作为起点（假设唯一解）。
Credit to LeetCode User @daxianji007:
从第一站开始循环
如果够跑，继续循环；
如果不够，假设从下一站开始，并且记录油量的缺损；如果到最后剩余的油量能补上这一缺损，则可以达成；否则返回-1。
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int start = 0, total = 0, tank = 0;
for(int i = 0; i < gas.size(); i++) {
tank = tank + gas[i] - cost[i];
if (tank < 0) {
total += tank; tank = 0; start = i+1;
}
}
return (tank+total<0)? -1 : start;
}
一个数组里所有数字都出现了两次，只有一个数字出现过一次。求这个数。
不难想出别的方法，但是很难想到bit manipulation：
a xor b xor a = a
把所有的数字xor到一起，出现两次的数自己抵消了，只剩我们要找的出现过一次的数。
int singleNumber(vector<int>& nums) {
int a = 0;
for (int i : nums) {
a ^= i;
}
return a;
}
给一个list，node的结构是有一个next指针，一个random指针。做这个list的deep copy。
做一个unordered map （hashmap），把每个复制过的点放到hashmap里（防止重复copy）。
Space Complaxity： O（n）
- 处理next：in place 复制list： 1->2->3 变成 1->1->2->2->3->3
- 处理random：新复制的random = 旧node的random->next
- 分离：一个跳一个
Credit to LeetCode user @liaison:
Node* copyRandomList(Node* head) {
Node* iter = head;
Node* next;
// First round: make copy of each node,
// and link them together side-by-side in a single list.
while (iter != nullptr) {
next = iter->next;
Node* copy = new Node(iter->val, nullptr, nullptr);
iter->next = copy;
copy->next = next;
iter = next;
}
// Second round: assign random pointers for the copy nodes.
iter = head;
while (iter != nullptr) {
if (iter->random != nullptr) {
iter->next->random = iter->random->next;
}
iter = iter->next->next;
}
// Third round: restore the original list, and extract the copy list.
iter = head;
Node* pseudoHead = new Node(0, nullptr, nullptr);
Node* copy;
Node* copyIter = pseudoHead;
while (iter != nullptr) {
next = iter->next->next;
// extract the copy
copy = iter->next;
copyIter->next = copy;
copyIter = copy;
// restore the original list
iter->next = next;
iter = next;
}
return pseudoHead->next;
}
把一个linkedlist变成一头一尾一头一尾的顺序：
1-2->3->4 变成 1->4->2->3
1-2->3->4->5 变成 1->5->2->4->3
把最后一个node插到第一个后面，iterative over the list。
Time Complexity: O(n^2)
- 找到中间点。
- reverse后一半的list
- merge前后两半
Time Complexity: O(n)
void reorderList(ListNode *head) {
if (!head || !head->next) return;
// find the middle node: O(n)
ListNode *p1 = head, *p2 = head->next;
while (p2 && p2->next) {
p1 = p1->next;
p2 = p2->next->next;
}
// cut from the middle and reverse the second half: O(n)
ListNode *head2 = p1->next;
p1->next = NULL;
p2 = head2->next;
head2->next = NULL;
while (p2) {
p1 = p2->next;
p2->next = head2;
head2 = p2;
p2 = p1;
}
// merge two lists: O(n)
for (p1 = head, p2 = head2; p1; ) {
auto t = p1->next;
p1->next = p2;
p1->next->next = t;
p1 = p1->next->next;
p2 = p2->next;
}
}
找乘积最大的subarray
乘积就要记录最大正值和最小负值。
int maxProduct(vector<int>& nums) {
if(nums.empty()) return 0;
int cmax = nums[0], cmin = nums[0];
int res = cmax;
for (int i = 1; i < nums.size(); i++) {
if (nums[i] < 0) swap(cmax, cmin);
cmax = max(cmax*nums[i], nums[i]);
cmin = min(cmin*nums[i], nums[i]);
res = max(cmax, res);
}
return res;
}
次数就想到map，第几大就想到priority queue。
先用一个map统计每个字符串出现的次数，然后把字符串往pq（小顶堆）里放，同时控制pq的大小。
所以pq的top就是第k多出现的次数。那么只要字符串出现的字数大于top，就是我们要找的数。
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> counts;
priority_queue<int, vector<int>, greater<int>> max_k;
for(auto i : nums) ++counts[i];
for(auto & i : counts) {
max_k.push(i.second);
while(max_k.size() > k) max_k.pop();
}
vector<int> res;
for(auto & i : counts) {
if(i.second >= max_k.top()) res.push_back(i.first);
}
return res;
}
每一个iteration找出 num[i] > num[i+1]的数删掉；如果没有，就删最后一个。
用stack。如果num[i]比答案最会一个数字小，pop_back并且i--;
压栈时注意不能让0做第一个；
最后如果还没删够k个数，从尾巴上删；
string removeKdigits(string num, int k) {
string ans = "";
for (char c : num) {
while (ans.length() && ans.back() > c && k) {
ans.pop_back();
k--;
}
if (ans.length() || c != '0') ans.push_back(c);
}
while (ans.length() && k--) ans.pop_back();
return ans.empty() ? "0" : ans;
}
把一个字符串分成尽量多部分，每个字母只在一个部分中出现。
既然同样的字母只能在同一个部分，就找每个字母最后出现的位置
然后找同一个部分里最后一个出现的字母。
vector<int> partitionLabels(string S) {
int lp[26];
for (int i = 0; i < S.size(); i++)
lp[S[i] - 'a'] = i;
vector<int> res;
for (int j = 0, temp = 0, anchor = 0; j < S.size(); j++) {
temp = max(lp[S[j] - 'a'], temp);
if (j == temp) {
res.push_back(j - anchor + 1);
anchor = j+1;
}
}
return res;
}
主要是对stringstream的处理：如何变lowercase，如何去掉符号
string mostCommonWord(string paragraph, vector<string>& banned) {
unordered_set<string> ban(banned.begin(), banned.end());
unordered_map<string, int> count;
for (auto & c: paragraph) c = isalpha(c) ? tolower(c) : ' ';
istringstream iss(paragraph);
string w;
pair<string, int> res ("", 0);
while (iss >> w)
if (ban.find(w) == ban.end() && ++count[w] > res.second)
res = make_pair(w, count[w]);
return res.first;
}