295 Hard. Find Median from Data Stream
求一个数据流的中位数。维持一个最大堆和一个最小堆。保证二者的size只差<=1。
class MedianFinder
{
priority_queue<int> lo; // max heap
priority_queue<int, vector<int>, greater<int>> hi; // min heap
public:
// Adds a number into the data structure.
void addNum(int num)
{
lo.push(num); // Add to max heap
hi.push(lo.top()); // balancing step
lo.pop();
if (lo.size() < hi.size())
{ // maintain size property
lo.push(hi.top());
hi.pop();
}
}
// Returns the median of current data stream
double findMedian()
{
return lo.size() > hi.size() ? (double)lo.top() : (lo.top() + hi.top()) * 0.5;
}
};
990 Medium. Satisfiability of Equality Equations
首先假定a-z对应0-25，每个等号修改其指向的值。核心是理解find()函数，即字母指向的真实值
class Solution
{
public:
vector<int> value;
bool equationsPossible(vector<string>& equations)
{
value.resize(26);
for (int i = 0; i < value.size(); i++)
value[i] = i;
for (auto& equation : equations)
{
if (equation[1] == '=')
value[find((equation[3] - 'a'))] = find(equation[0] - 'a');
}
for (auto& equation : equations)
{
if (equation[1] == '!' && find(equation[3] - 'a') == find(equation[0] - 'a'))
return false;
}
return true;
}
int find(int x)
{
if (x != value[x])
return find(value[x]);
return x;
}
};
958 Medium. Check Completeness of a Binary Tree
判断是否是完全二叉树
class Solution
{
public:
bool isCompleteTree(TreeNode* root)
{
vector<TreeNode*> bfs;
bfs.push_back(root);
int i = 0;
while (i < bfs.size() && bfs[i])
{
bfs.push_back(bfs[i]->left);
bfs.push_back(bfs[i]->right);
i++;
}
while (i < bfs.size() && !bfs[i])
i++;
return i == bfs.size();
}
};
1546 Medium. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target
求所有的子数组，不重叠，其和为target
需要用map来保存[0,i]的sum，每得到一个新的sum [0,j]，查找是否存在sum-target。如果存在，那么[i,j]的和就是target。由贪心可知，下一段target的起始index一定小于j，所以用了一个变量start来去掉那些会发生重叠的子数组。
class Solution
{
public:
int maxNonOverlapping(vector<int> &nums, int target)
{
int sum = 0;
map<int, int> summap;
summap[0] = -1;
int start = -1;
int ret = 0;
for (int i = 0; i < nums.size(); i++)
{
sum += nums[i];
if (summap.find(sum - target) != summap.end())
{
int left = summap[sum - target];
if (start <= left)
{
start = i;
ret++;
}
}
summap[sum] = i;
}
return ret;
}
};
208 Medium. Implement Trie (Prefix Tree)
前缀树。需要一个bool来表示当前结点是否存了一个单词。用一个size为26的vector<Trie*>来检索单词。 注：没写析构函数
class Trie
{
private:
//Trie * child;
std::vector<Trie *> children;
bool ends;
public:
/** Initialize your data structure here. */
Trie()
{
children.resize(26, nullptr);
ends = false;
}
/** Inserts a word into the trie. */
void insert(string word)
{
Trie *p = this;
for (auto ch : word)
{
if (p->children[ch - 'a'] == nullptr)
{
p->children[ch - 'a'] = new Trie();
}
p = p->children[ch - 'a'];
}
p->ends = true;
}
/** Returns if the word is in the trie. */
bool search(string word)
{
Trie *p = this;
for (auto ch : word)
{
if (p->children[ch - 'a'] == nullptr)
{
return false;
}
p = p->children[ch - 'a'];
}
return p->ends;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix)
{
Trie *p = this;
for (auto ch : prefix)
{
if (p->children[ch - 'a'] == nullptr)
{
return false;
}
p = p->children[ch - 'a'];
}
return true;
}
};
337 Medium. House Robber III
对于一个node，有rob和not rob两种情况，当rob当前结点的时候，其两个子结点不能rob，只能rob其孙结点，递归调用其四个孙结点即可。
如果不rob当前结点，那么就可以递归调用其两个子结点
class Solution
{
public:
std::unordered_map<TreeNode *, int> mmap;
int rob(TreeNode *root)
{
if (root == NULL)
return 0;
if (mmap.count(root))
return mmap.at(root);
int v1 = rob(root->left) + rob(root->right);
int v2 = root->val;
if (root->left)
v2 += rob(root->left->left) + rob(root->left->right);
if (root->right)
v2 += rob(root->right->left) + rob(root->right->right);
int value = max(v1, v2);
mmap[root] = value;
return value;
}
};
1530 Medium. Number of Good Leaf Nodes Pairs
核心是返回一个vector<int> 来保存当前结点到所有叶子结点的距离。
两个叶子结点的距离，等于他们最近祖先到两个叶子结点的距离。
递归思路：一个结点到其所有叶子结点的距离，可以等于其所有子树的距离之和+2
class Solution
{
public:
int countPairs(TreeNode *root, int distance)
{
ans = 0;
dfs(root, distance);
return ans;
}
int ans = 0;
vector<int> dfs(TreeNode *root, int distance)
{
vector<int> ret;
if (root == NULL)
return ret;
auto v1 = dfs(root->left, distance);
auto v2 = dfs(root->right, distance);
if (v1.size() == 0 && v2.size() == 0)
{
ret.push_back(0);
return ret;
}
for (int i = 0; i < v1.size(); i++)
{
for (int j = 0; j < v2.size(); j++)
{
if (v1[i] + v2[j] + 2 <= distance)
ans++;
}
}
for (int i = 0; i < v1.size(); i++)
{
v1[i]++;
ret.push_back(v1[i]);
}
for (int i = 0; i < v2.size(); i++)
{
v2[i]++;
ret.push_back(v2[i]);
}
return ret;
}
};
64 Medium. Minimum Path Sum
经典dp
class Solution
{
public:
int minPathSum(vector<vector<int>> &grid)
{
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
dp[0][0] = grid[0][0];
for (int i = 1; i < grid.size(); i++)
{
dp[i][0] = grid[i][0] + dp[i - 1][0];
}
for (int i = 1; i < n; i++)
{
dp[0][i] = grid[0][i] + dp[0][i - 1];
}
for (int i = 1; i < m; i++)
{
for (int j = 1; j < n; j++)
{
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[m - 1][n - 1];
}
};
1493 Medium. Longest Subarray of 1's After Deleting One Element
一个0,1数组，将其中一个0改成1之后，最长连续1的长度。
没看懂lee的解答。自己的解法太菜。
1319 Medium. Number of Operations to Make Network Connected
union-find 计算出有多少个不连通的结点，再-1。这里nums[i]=i表示这是一个单独的结点
class Solution
{
public:
vector<int> nums;
int makeConnected(int n, vector<vector<int>> &connections)
{
if (n - 1 > connections.size())
{
return -1;
}
nums.resize(n);
for (int i = 0; i < nums.size(); i++)
{
nums[i] = i;
}
for (auto connection : connections)
{
int v1 = find(connection[0]);
int v2 = find(connection[1]);
if (v1 != v2)
nums[v1] = v2;
}
int count = 0;
for (int i = 0; i < nums.size(); i++)
{
if (nums[i] == i)
count++;
}
return count - 1;
}
int find(int x)
{
if (x != nums[x])
return find(nums[x]);
return x;
}
};
240 Medium. Search a 2D Matrix II
经典题目，从左下角或者右上角开始搜索。
106 Medium. Construct Binary Tree from Inorder and Postorder Traversal
还是递归。宗旨是，后序遍历的最后一个是根节点，利用map找到根节点在中序遍历中的位置，这样可以获得中序遍历的左右两棵子树，以及结点个数。根据个数，可以推出来后续遍历的子树起始点和结束点。
class Solution
{
public:
std::map<int, int> inMap;
TreeNode *helper(vector<int> &inorder, vector<int> &postorder, int l1, int r1, int l2, int r2)
{
if (l1 > r1 || l2 > r2)
return NULL;
// 根节点是后序遍历的最后一个结点
int rootValue = postorder[r2];
int posRootInOrder = inMap[rootValue];
// 左右子树的中序遍历结点
int leftl1 = l1, leftr1 = posRootInOrder - 1;
int rightl1 = posRootInOrder + 1, rightr1 = r1;
// 右子树可以根据左子树算出节点个数
int leftl2 = l2, leftr2 = leftl2 + leftr1 - leftl1;
int rightl2 = leftr2 + 1, rightr2 = r2 - 1;
TreeNode *left = helper(inorder, postorder, leftl1, leftr1, leftl2, leftr2);
TreeNode *right = helper(inorder, postorder, rightl1, rightr1, rightl2, rightr2);
TreeNode *root = new TreeNode(rootValue, left, right);
return root;
}
TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder)
{
for (int i = 0; i < inorder.size(); i++)
inMap[inorder[i]] = i;
return helper(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1);
}
};
1372 Medium. Longest ZigZag Path in a Binary Tree
ZigZag 核心还是递归，dfs。lee的答案太牛了
class Solution
{
public:
int longestZigZag(TreeNode *root)
{
return dfs(root)[2];
}
vector<int> dfs(TreeNode *root)
{
if (!root)
return {-1, -1, -1};
vector<int> left = dfs(root->left), right = dfs(root->right);
int res = max(max(left[1], right[0]) + 1, max(left[2], right[2]));
return {left[1] + 1, right[0] + 1, res};
}
};
863 Medium. All Nodes Distance K in Binary Tree
主要技巧是用map存一下各个结点的parent，然后直接dfs
class Solution
{
public:
vector<int> distanceK(TreeNode *root, TreeNode *target, int K)
{
parent(root);
dfs(target, K);
return ans;
}
unordered_set<TreeNode *> visited;
void dfs(TreeNode *node, int K)
{
if (node == nullptr)
return;
if (visited.count(node))
return;
visited.insert(node);
if (K == 0)
{
ans.push_back(node->val);
return;
}
if (node->left)
{
dfs(node->left, K - 1);
}
if (node->right)
{
dfs(node->right, K - 1);
}
dfs(mmap[node], K - 1);
}
void parent(TreeNode *root)
{
if (root == NULL)
return;
if (root->left)
{
mmap[root->left] = root;
parent(root->left);
}
if (root->right)
{
mmap[root->right] = root;
parent(root->right);
}
}
vector<int> ans;
std::unordered_map<TreeNode *, TreeNode *> mmap;
};
1035 Medium. Uncrossed Lines
经典dp
class Solution
{
public:
int maxUncrossedLines(vector<int>& A, vector<int>& B)
{
int m = A.size(), n = B.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 0; i < A.size(); i++)
{
for (int j = 0; j < B.size(); j++)
{
dp[i + 1][j + 1] = A[i] == B[j] ? 1 + dp[i][j] : max(dp[i][j + 1], dp[i + 1][j]);
}
}
return dp[m][n];
}
};
416 Medium. Partition Equal Subset Sum
dp。很容易将题目转化为求一个子集，和为sum/2，利用sum作为dp的元素。
class Solution
{
public:
bool canPartition(vector<int> &nums)
{
int sum = 0;
for (int i = 0; i < nums.size(); i++)
sum += nums[i];
if (sum == 0 || sum & 1 != 0)
return false;
sum /= 2;
vector<int> dp(sum + 1, 0);
dp[0] = 1;
for (auto num : nums)
for (int i = sum; i >= num; i--)
{
dp[i] = dp[i] || dp[i - num];
}
return dp[sum];
}
};
1209 Medium. Remove All Adjacent Duplicates in String II
重复删除字符串中连续k个相同的字符，求最后剩下的字符串
核心思想是用栈处理，当栈空或者栈顶元素和当前字符不同的时候，入栈，计数+1，如果栈顶计数到达k，直接pop出栈
class Solution
{
public:
string removeDuplicates(string s, int k)
{
stack<pair<char, int>> st;
for (auto ch : s)
{
if (st.empty() || st.top().first != ch)
st.push({ch, 0});
st.top().second++;
if (st.top().second == k)
st.pop();
}
string ret = "";
while (!st.empty())
{
ret += string(st.top().second, st.top().first);
st.pop();
}
reverse(ret.begin(), ret.end());
return ret;
}
};
300 Medium. Longest Increasing Subsequence
最长递增子序列 http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/
int lengthOfLIS(vector<int>& nums)
{
vector<int> res;
for (int i = 0; i < nums.size(); i++)
{
auto it = std::lower_bound(res.begin(), res.end(), nums[i]);
if (it == res.end())
res.push_back(nums[i]);
else
*it = nums[i];
}
return res.size();
}
102 Medium. Binary Tree Level Order Traversal
二叉树的层序遍历，并按层输出。主要是记录每次while循环时，queue的size，即为当前层的结点个数。
class Solution
{
public:
vector<vector<int>> levelOrder(TreeNode *root)
{
vector<vector<int>> ret;
queue<TreeNode *> myqueue;
if (root == NULL)
return ret;
myqueue.push(root);
while (!myqueue.empty())
{
int n = myqueue.size();
ret.resize(ret.size() + 1);
for (int i = 0; i < n; i++)
{
auto node = myqueue.front();
myqueue.pop();
if (node->left)
myqueue.push(node->left);
if (node->right)
myqueue.push(node->right);
ret.back().push_back(node->val);
}
}
return ret;
}
};
1482 Medium. Minimum Number of Days to Make m Bouquets
二分法查找！
class Solution
{
public:
int minDays(vector<int> &bloomDay, int m, int k)
{
if (m * k > bloomDay.size())
return -1;
int maxday = 0;
for (auto day : bloomDay)
maxday = max(day, maxday);
int left = 0, right = maxday;
while (left < right)
{
int mid = (left + right) / 2;
if (can(bloomDay, m, k, mid))
right = mid;
else
left = mid + 1;
}
return right;
}
bool can(vector<int> &bloomDay, int m, int k, int day)
{
int cc = 0;
for (int i = 0; i < bloomDay.size(); i++)
{
if (m == 0)
return true;
if (bloomDay[i] > day)
cc = 0;
else
{
cc++;
if (cc == k)
{
m--;
cc = 0;
}
}
}
return m <= 0;
}
};
583 Medium. Delete Operation for Two Strings
最长公共子序列。经典dp
1749 Medium. Maximum Absolute Sum of Any Subarray
求数组的最大子数组和的绝对值
因为子数组的和 = 前缀和a- 前缀和b，那么绝对值最大的就是 max(前缀和)- min(前缀和)
牛啊
518 Medium. Coin Change 2
比较有技巧的dp
962 Medium. Maximum Width Ramp
给一个数组，求下标(i,j)，满足num[i]<=num[j]，求max(j-i)
用栈保存每个最小数的起始坐标
class Solution
{
public:
int maxWidthRamp(vector<int> &A)
{
stack<int> s;
for (int i = 0; i < A.size(); i++)
if (s.empty() || A[s.top()] > A[i])
s.push(i);
int res = 0;
for (int i = A.size() - 1; i >= 0; i--)
{
while (!s.empty() && A[s.top()] <= A[i])
{
res = max(res, i - s.top());
s.pop();
}
}
return res;
}
};
886 Medium. Possible Bipartition
TODO
1262 Medium. Greatest Sum Divisible by Three
dp可以解。也可以直接贪心再处理边界条件
class Solution
{
public:
int maxSumDivThree(vector<int> &nums)
{
vector<int> dp(3);
for (int i = 0; i < nums.size(); i++)
{
vector<int> pre = dp;
for (int premax : pre)
{
int mod = (premax + nums[i]) % dp.size();
dp[mod] = max(dp[mod], nums[i] + premax);
}
}
return dp[0];
}
};
46 Medium. Permutation
全排列
class Solution
{
public:
vector<vector<int>> ret;
void helper(vector<int> &nums, int index)
{
if (index == nums.size())
{
ret.push_back(nums);
}
for (int i = index; i < nums.size(); i++)
{
swap(nums[index], nums[i]);
helper(nums, index + 1);
swap(nums[index], nums[i]);
}
}
vector<vector<int>> permute(vector<int> &nums)
{
helper(nums, 0);
return ret;
}
};
718 Medium. Maximum Length of Repeated Subarray
最长公共子串
1653 Medium. Minimum Deletions to Make String Balanced
TODO
1248 Medium. Count Number of Nice Subarrays
TODO
435 Medium. Non-overlapping Intervals
重点在于排序
714 Medium. Best Time to Buy and Sell Stock with Transaction Fee
309 Medium. Best Time to Buy and Sell Stock with Cooldown
1695 Medium. Maximum Erasure Value
删掉一个不重复的连续子数组，求子数组最大和。
滑动窗口+set记录是否重复
1722 Medium. Minimize Hamming Distance After Swap Operations
union find 分组之后处理。每个组可以用greed求最小hamming距离，再加起来
class Solution
{
public:
vector<int> v;
int minimumHammingDistance(vector<int> &source, vector<int> &target, vector<vector<int>> &allowedSwaps)
{
int n = source.size();
v.resize(n);
for (int i = 0; i < n; i++)
v[i] = i;
for (auto swap : allowedSwaps)
{
v[find(swap[0])] = find(swap[1]);
}
unordered_map<int, vector<int>> maps;
for (int i = 0; i < n; i++)
{
maps[find(i)].push_back(i);
}
int ret = 0;
for (auto it = maps.begin(); it != maps.end(); it++)
{
auto &vec = it->second;
unordered_map<int, int> count;
for (int i = 0; i < vec.size(); i++)
{
count[source[vec[i]]]++;
count[target[vec[i]]]--;
}
for (auto c : count)
{
ret += abs(c.second);
}
}
return ret / 2;
}
int find(int x)
{
if (x != v[x])
{
return find(v[x]);
}
return x;
}
};
926 Medium. Flip String to Monotone Increasing
分两种情况，以0结尾和以1结尾。可以理解为一种二元dp
class Solution
{
public:
int minFlipsMonoIncr(string s)
{
int c0, c1;
c0 = c1 = 0;
for (int i = 0; i < s.size(); i++)
{
c1 = min(c1, c0) + (s[i] == '1' ? 0 : 1);
c0 += s[i] == '0' ? 0 : 1;
}
return min(c1, c0);
}
};
109 Medium. Convert Sorted List to Binary Search Tree
将一个链表转换为平衡二叉搜索树。递归
class Solution
{
public:
vector<ListNode*> v;
TreeNode* sortedListToBST(ListNode* head)
{
if (head == NULL)
return NULL;
ListNode* p = head;
while (p)
{
v.push_back(p);
p = p->next;
}
return helper(0, v.size() - 1);
}
TreeNode* helper(int left, int right)
{
if (left > right)
return NULL;
int mid = (left + right) / 2;
TreeNode* root = new TreeNode(v[mid]->val);
root->left = helper(left, mid - 1);
root->right = helper(mid + 1, right);
return root;
}
};
560 Medium. Subarray Sum Equals K
经典的subarray题目
752 Medium. Open the Lock
比较有意思的BFS题。 TODO
236 Medium. Lowest Common Ancestor of a Binary Tree
求二叉树中两个节点的最近公共祖先 TODO
452 Medium. Minimum Number of Arrows to Burst Balloons
interval处理的题目 TODO
96 Medium. Unique Binary Search Trees
数学题
1734 Medium. Decode XORed Permutation
数学题。关键在于，可以把nums[0]求出来。
1202 Medium. Smallest String With Swaps
同样是union-find， 这里需要对find的过程做个优化。测试数据集比较大
class Solution
{
public:
vector<int> v;
string smallestStringWithSwaps(string s, vector<vector<int>> &pairs)
{
int n = s.size();
v.resize(n);
for (int i = 0; i < n; i++)
v[i] = i;
for (auto &swap : pairs)
{
int v1 = find(swap[0]);
int v2 = find(swap[1]);
v[swap[0]] = v1;
v[swap[1]] = v2;
v[v1] = v2;
}
unordered_map<int, vector<int>> maps;
for (int i = 0; i < n; i++)
{
maps[find(i)].push_back(i);
}
string ret = s;
for (auto it = maps.begin(); it != maps.end(); it++)
{
auto &vec = it->second;
string str;
for (int i = 0; i < vec.size(); i++)
{
str.push_back(s[vec[i]]);
}
sort(str.begin(), str.end());
for (int i = 0; i < vec.size(); i++)
{
ret[vec[i]] = str[i];
}
}
return ret;
}
int
find(int x)
{
if (x != v[x])
{
return find(v[x]);
}
return x;
}
};
450 Medium. Delete Node in a BST
TODO 删除二叉搜索树中的一个节点。返回删除后的树的根节点
881 Medium. Boats to Save People
class Solution
{
public:
int numRescueBoats(vector<int> &people, int limit)
{
sort(people.begin(), people.end(), greater<int>());
int left = 0, right = people.size() - 1;
while (left <= right)
{
if (people[left] + people[right] <= limit)
right--;
left++;
}
return left;
}
};
103 Medium. Binary Tree Zigzag Level Order Traversal
之字形打印层序遍历。在层序遍历的基础上，加了level
class Solution
{
public:
vector<vector<int>> zigzagLevelOrder(TreeNode *root)
{
vector<vector<int>> ret;
if (root == NULL)
return ret;
queue<TreeNode *> st;
st.push(root);
int height = 1;
while (!st.empty())
{
vector<int> temp;
vector<TreeNode *> seq;
while (!st.empty())
{
seq.push_back(st.front());
temp.push_back(st.front()->val);
st.pop();
}
ret.push_back(temp);
for (int i = 0; i < seq.size(); i++)
{
if (height % 2 == 0)
{
if (seq[i]->left)
st.push(seq[i]->left);
if (seq[i]->right)
st.push(seq[i]->right);
}
else if (height % 2 == 1)
{
if (seq[i]->right)
st.push(seq[i]->right);
if (seq[i]->left)
st.push(seq[i]->left);
}
}
height++;
}
return ret;
}
};
873 Medium. Length of Longest Fibonacci Subsequence
注意，题目中arr是递增的..
class Solution
{
public:
int lenLongestFibSubseq(vector<int> &A)
{
unordered_set<int> s(A.begin(), A.end());
int res = 0;
for (int i = 0; i < A.size(); ++i)
{
for (int j = i + 1; j < A.size(); ++j)
{
int a = A[i], b = A[j], l = 2;
while (s.count(a + b))
b = a + b, a = b - a, l++;
res = max(res, l);
}
}
return res > 2 ? res : 0;
}
};
1049 Medium. Last Stone Weight II
TODO 这道题可以转换成背包问题
494 Medium. Target Sum
TODO 同上一题
1288 Medium. Remove Covered Intervals
interval 题目
class Solution
{
public:
int removeCoveredIntervals(vector<vector<int>> &intervals)
{
sort(intervals.begin(), intervals.end(), [](vector<int> &v1, vector<int> &v2) {
if (v1[0] == v2[0])
return v1[1] > v2[1];
return v1[0] < v2[0];
});
int end = intervals[0][1];
int ret = 0;
for (int i = 1; i < intervals.size(); i++)
{
if (intervals[i][1] <= end)
{
ret++;
}
else
end = intervals[i][1];
}
return intervals.size() - ret;
}
};
207 Medium. Course Schedule
拓扑排序。
1162 Medium. As Far from Land as Possible
每块陆地依次BFS。用队列来保存需要遍历的node
class Solution
{
public:
int maxDistance(vector<vector<int>> &grid)
{
queue<pair<int, int>> q;
int m = grid.size();
int n = grid[0].size();
int ret = 0;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (grid[i][j] == 1)
q.push({i, j});
}
}
while (!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
vector<vector<int>> exps = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (auto dir : exps)
{
int nx = dir[0] + x;
int ny = dir[1] + y;
if (nx < 0 || nx >= m || ny < 0 || ny >= n)
continue;
if (grid[nx][ny] == 0)
{
grid[nx][ny] = grid[x][y] + 1;
ret = max(ret, grid[nx][ny]);
q.push({nx, ny});
}
}
}
return ret - 1;
}
};
148 Medium. Sort List
链表排序
1054 Medium. Distant Barcodes
按出现频率排序，然后相邻放置。贪心
729 Medium. My Calendar I
TODO
235 Easy. Lowest Common Ancestor of a Binary Search Tree
求二叉搜索树的最近公共祖先。技巧就是
def lowestCommonAncestor(self, root, p, q):
while (root.val - p.val) * (root.val - q.val) > 0:
root = (root.left, root.right)[p.val > root.val]
return root
1014 Medium. Best Sightseeing Pair
转换一下，就很简单
945 Medium. Minimum Increment to Make Array Unique
TODO
1631 Medium. Path With Minimum Effort
TODO 解法好多..
210 Medium. Course Schedule II
813 Medium. Largest Sum of Averages
给一组数，分为k组，每组求平均数，再求平均数的sum，求sum最大值。
主要思想：前缀和+dp
class Solution
{
public:
double largestSumOfAverages(vector<int> &nums, int k)
{
vector<int> prefixsum(nums.size() + 1, 0);
prefixsum[0] = 0;
for (int i = 1; i <= nums.size(); i++)
prefixsum[i] = prefixsum[i - 1] + nums[i - 1];
if (k >= nums.size())
{
return prefixsum.back();
}
if (k <= 1)
{
return 1.0 * prefixsum.back() / nums.size();
}
vector<vector<double>> dp(nums.size() + 1, vector<double>(k + 1, 0));
for (int i = 1; i < nums.size(); i++)
{
dp[i][1] = 1.0 * prefixsum[i] / i;
}
for (int x = 2; x <= k; x++)
{
for (int i = x; i <= nums.size(); i++)
{
for (int j = i - 1; j >= x - 1; j--)
{
dp[i][x] = max(dp[i][x], dp[j][x - 1] + 1.0 * (prefixsum[i] - prefixsum[j]) / (i - j));
}
}
}
return dp[nums.size()][k];
}
};
394 Medium. Decode String
经典的题目，递归比较直观，用栈比较有技巧.
1155 Medium. Number of Dice Rolls With Target Sum
背包问题。用dp解。n+1个骰子的结果可以通过n个骰子结果得到
class Solution
{
public:
int numRollsToTarget(int d, int f, int target)
{
vector<int> dp(target + 1, 0);
dp[0] = 1;
for (int i = 0; i < d; i++)
{
vector<int> temp(target + 1, 0);
for (int j = 1; j <= f; j++)
{
for (int k = i; k + j <= target; k++)
{
temp[k + j] += dp[k];
temp[k + j] %= (1000000007);
}
}
dp = temp;
}
return dp[target];
}
};
1438 Medium. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
用一个multiset保存数组中的数，保证最大数-最小数大于limit。最大的就是i-j。
class Solution {
public:
int longestSubarray(vector<int>& nums, int limit) {
multiset<int> myset;
int j = 0 ,i=0;
for( ;i<nums.size();i++)
{
myset.insert(nums[i]);
if( *myset.rbegin() - *myset.begin() > limit)
{
myset.erase(myset.find(nums[j]));
j++;
}
}
return i-j;
}
};
767 Medium. Reorganize String
1024 Medium. Video Stitching
62 Medium. Unique Paths
数学题，或者用dp
作为数学题，是小学奥数难度..使用组合可解。组合一下向下&向上
438 Medium. Find All Anagrams in a String
滑动窗口
1423 Medium. Maximum Points You Can Obtain from Cards
从两端去掉k个数，那么剩下的就是中间的n-k个数，即一个连续子数组的和。滑动窗口求长度为n-k的窗口的和最小值
116 Medium. Populating Next Right Pointers in Each Node
需要充分利用满二叉树。
class Solution
{
public:
Node* connect(Node* root)
{
if (root == NULL)
return root;
Node* pre = root;
Node* cur = NULL;
while (pre->left)
{
cur = pre;
while (cur)
{
cur->left->next = cur->right;
if (cur->next)
cur->right->next = cur->next->left;
cur = cur->next;
}
pre = pre->left;
}
return root;
}
};
525 Medium. Contiguous Array
求0、1个数相等的最长子数组。0:-1,1:+1，转化为sum为0的最长子数组
class Solution
{
public:
int findMaxLength(vector<int>& nums)
{
int sum = 0;
unordered_map<int, int> mymap;
mymap[0] = -1;
int maxret = 0;
for (int i = 0; i < nums.size(); i++)
{
sum += nums[i] ? 1 : -1;
if (!mymap.count(sum))
mymap[sum] = i;
else
maxret = max(maxret, i - mymap[sum]);
}
return maxret;
}
};
554 Medium. Brick Wall
求出最多能经过多少边缘，再用墙高减去这个值即可
class Solution
{
public:
int leastBricks(vector<vector<int>>& wall)
{
for (auto& v : wall)
{
for (int i = 1; i < v.size(); i++)
{
v[i] += v[i - 1];
}
}
int maxret = 0;
unordered_map<int, int> count;
for (auto& v : wall)
{
for (int i = 0; i < v.size() - 1; i++)
{
count[v[i]]++;
maxret = max(maxret, count[v[i]]);
}
}
return wall.size() - maxret;
}
};
1726 Medium. Tuple with Same Product
从数组中取出4个数，求满足a*b=c*d的所有组合。用hashMap保存下乘积，每一组可以通过排列获得8组。
class Solution {
public:
int tupleSameProduct(vector<int>& nums) {
int n = nums.size();
unordered_map<int,int> umap;
int res = 0;
for(int i = 0 ; i < n ; ++i){
for(int j = 0 ; j < i ; ++j){
int prod = nums[i] * nums[j];
/*Every tuple has 8 permutations*/
res += 8 * umap[prod];
++umap[prod];
}
}
return res;
}
};
449 Medium. Serialize and Deserialize BST
424 Medium. Longest Repeating Character Replacement
可以更换k个字符，求最长连续子串。用滑动窗口记录当前的各个字符的个数，求最大值。最大值+k应该小于滑动窗口大小
class Solution
{
public:
int characterReplacement(string s, int k)
{
int maxSameLen = 0;
vector<int> count(26, 0);
int j = 0;
for (int i = 0; i < s.size(); i++)
{
count[s[i] - 'A']++;
maxSameLen = std::max(maxSameLen, count[s[i] - 'A']);
if (i - j + 1 - maxSameLen > k)
{
count[s[j] - 'A']--;
j++;
}
}
return s.size() - j;
}
};
378 Medium. Kth Smallest Element in a Sorted Matrix
求一个每行每列都单调的矩阵第K大的值
用优先队列。先把每列的第一个数塞进队列（最多塞K个即可）。每次pop出队头，因为这一定是小于等于第K个数的。然后把这个数对应的下一列的数赛进队列。
class Solution
{
public:
struct comp
{
bool operator()(const pair<int, pair<int, int>>& p1, const pair<int, pair<int, int>>& p2)
{
return p1.first > p2.first;
};
};
int kthSmallest(vector<vector<int>>& matrix, int k)
{
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, comp> q;
for (int i = 0; i < matrix.size() && i < k; i++)
{
q.push({matrix[i][0], {i, 0}});
}
int count = 0, ret = -1;
while (!q.empty())
{
auto p = q.top();
q.pop();
count++;
if (count == k)
{
return p.first;
}
p.second.second++;
if (p.second.second < matrix[0].size())
{
q.push({matrix[p.second.first][p.second.second], p.second});
}
}
return ret;
}
};
199 Medium. Binary Tree Right Side View
16 Medium. 3Sum Closest
241 Medium. Different Ways to Add Parentheses
1642 Medium. Furthest Building You Can Reach
贪心。先尽量用brick，并记录用了多少块砖。砖不够用的时候上梯子，梯子用来替代用了最多的砖。当梯子和砖都不够用了的时候，返回。
class Solution
{
public:
int furthestBuilding(vector<int>& heights, int bricks, int ladders)
{
int b = 0;
priority_queue<int, vector<int>, less<int>> maxq;
for (int i = 1; i < heights.size(); i++)
{
if (heights[i] > heights[i - 1])
{
int diff = heights[i] - heights[i - 1];
maxq.push(diff);
b += diff;
if (b > bricks)
{
if (ladders > 0)
{
ladders--;
b -= maxq.top();
maxq.pop();
}
else
{
return i - 1;
}
}
}
}
return heights.size() - 1;
}
};
1760 Medium. Minimum Limit of Balls in a Bag
二分法yyfs。看到个评论说求min(max)或者max(min)的题大概率二分
class Solution
{
public:
bool check(vector<int>& nums, int maxop, int num)
{
int count = 0;
for (int i = 0; i < nums.size(); i++)
{
count += (nums[i] - 1) / num;
if (count > maxop)
return false;
}
return true;
}
int minimumSize(vector<int>& nums, int maxOperations)
{
int maxvalue = 0;
for (int i = 0; i < nums.size(); i++)
maxvalue = max(maxvalue, nums[i]);
int l = 1, r = maxvalue;
while (l <= r)
{
int mid = (l + r) / 2;
if (check(nums, maxOperations, mid))
{
r = mid - 1;
}
else
{
l = mid + 1;
}
}
return l;
}
};
75 Medium. Sort Colors
仅含0,1,2的数组排序
void sortColors(std::vector<int>& nums)
{
int small = 0, large = nums.size() - 1;
for (int i = 0; i < nums.size() && i <= large; i++)
{
if (nums[i] == 0)
{
swap(nums[i], nums[small]);
small++;
}
else if (nums[i] == 2)
{
swap(nums[i], nums[large]);
large--;
i--;
}
}
}
486 Medium. Predict the Winner
暴力dp求解。看解答可以简化计算
class Solution
{
public:
bool PredictTheWinner(std::vector<int>& nums)
{
int n = nums.size();
vector<int> prefixSum(n + 1, 0);
for (int i = 1; i <= n; i++)
prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = 0; i < n; i++)
dp[i][i] = nums[i];
for (int len = 2; len <= n; len++)
{
for (int i = 0; i + len - 1 < n; i++)
{
int j = i + len - 1;
int sumij = prefixSum[j + 1] - prefixSum[i];
dp[i][j] = max(sumij - dp[i + 1][j], sumij - dp[i][j - 1]);
}
}
return 2 * dp[0][n - 1] >= prefixSum.back();
}
};
1673 Medium. Find the Most Competitive Subsequence
最具有竞争力的子序列。即长度为k的最小子序列。用单调栈做。当st.size()<k的时候才push。pop的时候注意不要把栈pop空了，导致不足k个
class Solution
{
public:
vector<int> mostCompetitive(vector<int>& nums, int k)
{
int n = nums.size();
stack<int> st;
for (int i = 0; i < nums.size(); i++)
{
while (!st.empty() && st.size() + n - 1 - i >= k && st.top() > nums[i])
st.pop();
if (st.size() < k)
st.push(nums[i]);
}
vector<int> ret(k);
for (int i = 0; i < k; i++)
{
ret[k - 1 - i] = st.top();
st.pop();
}
return ret;
}
};
24 Medium. Swap Nodes in Pairs
380 Medium. Insert Delete GetRandom O(1)
插入，删除，获取随机值都是O(1)复杂度的数据结构。unoreder_map + vector。vector删除的时候，把想删除的元素和最后一个元素交换，再pop_back()，可以达到O(1)复杂度
class RandomizedSet {
public:
// vector删除的时候，把想删除的元素和最后一个元素交换，再pop_back()，可以达到O(1)复杂度
/** 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(map_.count(val))
return false;
map_[val] = values_.size();
values_.push_back(val);
return true;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
bool remove(int val) {
if(!map_.count(val))
return false;
int index = map_[val];
std::swap(values_[index],values_.back());
map_[values_[index]] = index;
values_.pop_back();
map_.erase(val);
return true;
}
/** Get a random element from the set. */
int getRandom() {
if(values_.size()== 0)
return -1;
return values_[rand()%values_.size()];
}
std::unordered_map<int,int> map_;
std::vector<int> values_;
};
1027 Medium. Longest Arithmetic Subsequence
477 Medium. Total Hamming Distance
位运算
875 Medium. Koko Eating Bananas
二分法
1696 Medium. Jump Game VI
这题好难..一个人每次最多跳k步，求从起点到终点，所经过结点的sum最大
class Solution
{
public:
int maxResult(vector<int>& nums, int k)
{
int n = nums.size();
vector<int> dp(n, INT_MIN);
dp[0] = nums[0];
multiset<int> q;
q.insert(dp[0]);
for (int i = 1; i < nums.size(); i++)
{
if (q.size() > k)
{
auto it = q.find(dp[i - k - 1]);
q.erase(it);
}
dp[i] = max(dp[i], *q.rbegin() + nums[i]);
q.insert(dp[i]);
}
return dp[n - 1];
}
};
1334 Medium. Find the City With the Smallest Number of Neighbors at a Threshold Distance
class Solution
{
public:
int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold)
{
vector<vector<int>> dist(n, vector<int>(n, 1000000));
for (auto& edge : edges)
{
dist[edge[0]][edge[1]] = edge[2];
dist[edge[1]][edge[0]] = edge[2];
}
for (int i = 0; i < n; i++)
dist[i][i] = 0;
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
int ret = 0;
int mincount = n + 1;
for (int i = 0; i < n; i++)
{
int count = 0;
for (int j = 0; j < n; j++)
{
if (distanceThreshold >= dist[i][j])
count++;
}
if (count <= mincount)
{
mincount = count;
ret = i;
}
}
return ret;
}
};
1584 Medium. Min Cost to Connect All Points
264 Medium. Ugly Number II
1686 Medium. Stone Game VI
这里拿走i处的point，对方就会少掉对应的point，所以收益是A[i]+B[i]，排序可解。做的时候用的priority_queue
class Solution
{
public:
int stoneGameVI(vector<int> &A, vector<int> &B)
{
int suma = 0, sumb = 0;
for (int i = 0; i < A.size(); i++)
{
suma += A[i];
}
for (int i = 0; i < B.size(); i++)
{
sumb += B[i];
}
priority_queue<pair<int, int>> q;
for (int i = 0; i < A.size(); i++)
{
q.push({abs(A[i] + B[i]), i});
}
for (int i = 0; i < A.size(); i++)
{
int index = q.top().second;
q.pop();
if (i % 2 == 0)
sumb -= B[index];
else
suma -= A[index];
}
if (suma == sumb)
return 0;
else if (suma > sumb)
return 1;
else
return -1;
}
};
543 Easy. Diameter of Binary Tree
求二叉树的半径
class Solution
{
public:
int diameterOfBinaryTree(TreeNode* root)
{
Height(root);
return length;
}
int Height(TreeNode* root)
{
if (root == nullptr)
return 0;
int left = Height(root->left);
int right = Height(root->right);
length = max(length, left + right);
return max(left, right) + 1;
}
int length = 0;
};
1105 Medium. Filling Bookcase Shelves
1218 Medium. Longest Arithmetic Subsequence of Given Difference
dp思想。 dp[i]：以arr[i]作为结尾的subseque。用hashmap保存最大的length
class Solution
{
public:
int longestSubsequence(vector<int>& arr, int difference)
{
unordered_map<int, int> mymap;
int maxret = 0;
for (int i = 0; i < arr.size(); i++)
{
int length = mymap[arr[i] - difference] + 1;
maxret = max(maxret, length);
mymap[arr[i]] = length;
}
return maxret;
}
};
670 Medium. Maximum Swap
求最多交换一次 数字中两位数后，得到的最大值。
用last保留数字 最后一次出现的pos，必定是与最后一个换能得到最大的结果。
然后从头开始找是否有满足条件的last
class Solution
{
public:
int maximumSwap(int num)
{
vector<int> last(10, -1);
string str = to_string(num);
for (int i = str.size() - 1; i >= 0; i--)
{
int v = str[i] - '0';
if (last[v] == -1)
{
last[v] = i;
}
}
for (int i = 0; i < str.size(); i++)
{
for (int v = 9; v >= str[i] - '0' + 1; v--)
{
if (last[v] != -1 && i < last[v])
{
swap(str[i], str[last[v]]);
return stoi(str);
}
}
}
return num;
}
};
870 Medium. Advantage Shuffle
优化的点在于，可以先判断set最大数是否> nums[i]，如果大的话，就不需要upper_bound查找了
class Solution
{
public:
vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2)
{
multiset<int> s(nums1.begin(), nums1.end());
vector<int> ret;
for (int i = 0; i < nums2.size(); i++)
{
auto it = s.upper_bound(nums2[i]);
if (it == s.end())
{
ret.push_back(*s.begin());
s.erase(s.begin());
}
else
{
ret.push_back(*it);
s.erase(it);
}
}
return ret;
}
};
437 Medium. Path Sum III
795 Medium. Number of Subarrays with Bounded Maximum
给一个数组和区间[left,right]，求数组所有满足最大值在区间范围内的连续子数组的个数
count表示以nums[i]作为最后一个数，满足条件的子数组个数
class Solution
{
public:
int numSubarrayBoundedMax(vector<int>& nums, int left, int right)
{
int ret = 0;
int pre = -1;
int count = 0;
for (int i = 0; i < nums.size(); i++)
{
if (nums[i] > right)
{
count = 0;
pre = i;
}
else if (nums[i] < left)
ret += count;
else
{
count = i - pre;
ret += count;
}
}
return ret;
}
};
1048 Medium. Longest String Chain
字符串链，前一个字符串某个位置添加任意字符后能变成后一个字符，那么就说这两个字符是相连的。求字符串数组能组成的最长字符串链
能想到用string来做dp就迎刃而解了
class Solution
{
public:
int longestStrChain(vector<string>& words)
{
auto cmp = [](const string& s1, const string& s2)
{ return s1.size() < s2.size(); };
sort(words.begin(), words.end(), cmp);
unordered_map<string, int> dp;
int res = 0;
for (int i = 0; i < words.size(); i++)
{
for (int j = 0; j < words[i].size(); j++)
{
string sub = words[i].substr(0, j) + words[i].substr(j + 1);
dp[words[i]] = max(dp[words[i]], dp[sub] + 1);
}
res = max(res, dp[words[i]]);
}
return res;
}
};
698 Medium. Partition to K Equal Sum Subsets
把数组分成k组。每组sum相同。dfs。可以先判断最大的数和sum/k的关系
class Solution
{
public:
bool ret = false;
int target;
bool dfs(vector<int>& nums, vector<int>& visited, int temp, int k)
{
if (k == 0)
{
return true;
}
if (temp > target)
{
return false;
}
else if (temp == target)
{
return dfs(nums, visited, 0, k - 1);
}
for (int i = 0; i < nums.size(); i++)
{
if (!visited[i])
{
visited[i] = true;
if (dfs(nums, visited, temp + nums[i], k))
return true;
else
visited[i] = false;
}
}
return false;
}
bool canPartitionKSubsets(vector<int>& nums, int k)
{
int sum = 0;
for (int num : nums)
sum += num;
if (sum % k != 0)
return false;
target = sum / k;
sort(nums.begin(), nums.end(), greater<int>());
if (nums[0] > target)
return false;
vector<int> visited(nums.size(), 0);
return dfs(nums, visited, 0, k);
}
};
792 Medium. Number of Matching Subsequences
给string s和一组string words，求words中有多少word是s的子序列
记录s中每个字符的下标。遍历word的时候用二分查找，看能否找到
class Solution
{
public:
int numMatchingSubseq(string s, vector<string>& words)
{
vector<vector<int>> mmap(26);
for (int i = 0; i < s.length(); i++)
{
mmap[s[i] - 'a'].push_back(i);
}
int count = 0;
for (auto& word : words)
{
int idx = 0;
bool flag = true;
for (int i = 0; i < word.size(); i++)
{
auto& pos = mmap[word[i] - 'a'];
auto it = lower_bound(pos.begin(), pos.end(), idx);
if (it == pos.end())
{
flag = false;
break;
}
else
idx = *it + 1;
}
if (flag)
count++;
}
return count;
}
};
646 Medium. Maximum Length of Pair Chain
区间合并问题
class Solution
{
public:
int findLongestChain(vector<vector<int>>& pairs)
{
int ret = 0;
auto comp = [](vector<int> p1, vector<int> p2)
{ return p1[1] < p2[1]; };
sort(pairs.begin(), pairs.end(), comp);
for (int i = 0, pre = 0; i < pairs.size(); i++)
{
if (i == 0 || pairs[pre][1] < pairs[i][0])
{
ret++;
pre = i;
}
}
return ret;
}
};
692 Medium. Top K Frequent Words
单词出现频率的Topk问题
class Solution
{
public:
struct cmp
{
bool operator()(pair<int, string>& w1, pair<int, string>& w2)
{
if (w1.first == w2.first)
return w1.second < w2.second;
return w1.first > w2.first;
}
};
vector<string> topKFrequent(vector<string>& words, int k)
{
unordered_map<string, int> mmap;
for (string& word : words)
mmap[word]++;
priority_queue<pair<int, string>, vector<pair<int, string>>, cmp> q;
for (auto it = mmap.begin(); it != mmap.end(); ++it)
{
q.push({it->second, it->first});
if (q.size() > k)
q.pop();
}
vector<string> ret;
while (!q.empty())
{
auto tmp = q.top();
q.pop();
ret.push_back(tmp.second);
}
reverse(ret.begin(), ret.end());
return ret;
}
};
110 Easy. Balanced Binary Tree
判断是否是平衡二叉树。左右子树的高差的绝对值<=1
class Solution
{
public:
bool flag = true;
int helper(TreeNode* root)
{
if (root == NULL)
return 0;
int h1 = helper(root->left);
int h2 = helper(root->right);
int h = 1;
if (abs(h1 - h2) > 1)
flag = false;
return max(h1, h2) + 1;
}
bool isBalanced(TreeNode* root)
{
flag = true;
helper(root);
return flag;
}
};
994 Medium. Rotting Oranges
经典bfs
class Solution
{
public:
int orangesRotting(vector<vector<int>>& grid)
{
queue<pair<int, int>> q;
vector<vector<int>> visited(grid.size(), vector<int>(grid[0].size(), 0));
int step = 0;
int tovisit = 0;
for (int i = 0; i < grid.size(); i++)
{
for (int j = 0; j < grid[i].size(); j++)
{
if (grid[i][j] == 2)
{
visited[i][j] = 1;
q.push({i, j});
}
else if (grid[i][j] == 1)
tovisit++;
}
}
if (tovisit == 0 && q.size() == 0)
return 0;
vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!q.empty())
{
if (tovisit == 0)
return step;
int size = q.size();
for (int x = 0; x < size; x++)
{
pair<int, int> pos = q.front();
q.pop();
for (auto dir : dirs)
{
int nx = pos.first + dir[0];
int ny = pos.second + dir[1];
if (nx >= 0 && ny >= 0 && nx < grid.size() && ny < grid[0].size() && !visited[nx][ny] && grid[nx][ny] == 1)
{
visited[nx][ny] = 1;
q.push({nx, ny});
tovisit--;
}
}
}
step++;
}
if (tovisit > 0)
return -1;
return step;
}
};
934 Medium. Shortest Bridge
先用dfs找island，再用bfs拓展。
1419 Medium. Minimum Number of Frogs Croaking
这个题还挺有意思的，状态机。
class Solution
{
public:
int minNumberOfFrogs(string croakOfFrogs)
{
vector<int> status(5, 0);
vector<int> map(256);
string croak = "croak";
for (int i = 0; i < croak.size(); i++)
map[croak[i]] = i;
for (int i = 0; i < croakOfFrogs.size(); i++)
{
int index = map[croakOfFrogs[i]];
status[index]++;
{
if (index != 0 && status[(index + 4) % 5] <= 0)
return -1;
if (index == 0)
{
if (status[4] != 0)
status[4]--;
}
else
status[(index + 4) % 5]--;
}
}
for (int i = 0; i < 4; i++)
if (status[i] < 0)
return -1;
return status.back();
}
};
95 Medium. Unique Binary Search Trees II
1-n 结点能组成的所有二叉搜索树
1657 Medium. Determine if Two Strings Are Close
这题主要是判断所有字符出现次数以及字符，分别相同
650 Medium. 2 Keys Keyboard
class Solution
{
public:
int minSteps(int n)
{
vector<int> dp(n + 1, 0);
dp[1] = 0;
for (int i = 2; i <= n; i++)
{
dp[i] = i;
for (int j = i / 2; j > 1; j--)
{
if (i % j == 0)
{
dp[i] = dp[j] + i / j;
break;
}
}
}
return dp[n];
}
};
516 Medium. Longest Palindromic Subsequence
求最长回文子序列的长度。dp。
dp[i][j]表示substr(i,j)能组成的最大回文序列长度。再判断s[i]==s[j]，容易得出dp公式
class Solution
{
public:
int longestPalindromeSubseq(string s)
{
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = 0; i < n; i++)
dp[i][i] = 1;
for (int l = 1; l < s.size(); l++)
{
for (int i = 0; i + l < s.size(); i++)
{
int j = i + l;
if (s[i] == s[j])
dp[i][j] = dp[i + 1][j - 1] + 2;
else
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
return dp[0][n - 1];
}
};
740 Medium. Delete and Earn
dp
1292 Medium. Maximum Side Length of a Square with Sum Less than or Equal to Threshold
矩阵前缀和+二分搜索
class Solution
{
public:
bool check(vector<vector<int>>& sum, int size, int threshold)
{
if (size == 0)
return true;
int m = sum.size();
int n = sum[0].size();
for (int i = 0; i + size < m; i++)
{
for (int j = 0; j + size < n; j++)
{
int s = sum[i + size][j + size] - sum[i + size][j] - sum[i][j + size] + sum[i][j];
if (s <= threshold)
return true;
}
}
return false;
}
int maxSideLength(vector<vector<int>>& mat, int threshold)
{
int m = mat.size();
int n = mat[0].size();
vector<vector<int>> sum(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + mat[i - 1][j - 1];
}
}
int left = 0, right = min(m, n);
while (left <= right)
{
int mid = (left + right) / 2;
if (check(sum, mid, threshold))
left = mid + 1;
else
right = mid - 1;
}
return right;
}
};
1535 Medium. Find the Winner of an Array Game
class Solution
{
public:
int getWinner(vector<int>& arr, int k)
{
int cur = arr[0], count = 0;
for (int i = 1; i < arr.size(); i++)
{
if (cur > arr[i])
count++;
else
{
cur = arr[i];
count = 1;
}
if (count == k)
return cur;
}
return cur;
}
};
1208 Medium. Get Equal Substrings Within Budget
经典滑动窗口
class Solution
{
public:
int equalSubstring(string s, string t, int maxCost)
{
int temp = 0;
int ret = 0;
int i = 0, j = 0;
while (j < t.size())
{
temp += abs(t[j] - s[j]);
if (temp <= maxCost)
{
ret = max(j - i + 1, ret);
}
else
{
temp -= abs(t[i] - s[i]);
i++;
}
j++;
}
return ret;
}
};
799 Medium. Champagne Tower
class Solution
{
public:
double champagneTower(int poured, int query_row, int query_glass)
{
vector<vector<double>> dp(query_row + 1, vector<double>(query_row + 1, 0));
dp[0][0] = poured;
for (int i = 1; i < dp.size(); i++)
{
for (int j = 0; j < dp[i].size(); j++)
{
if (j - 1 >= 0 && dp[i - 1][j - 1] > 1)
dp[i][j] += (dp[i - 1][j - 1] - 1) / 2;
if (dp[i - 1][j] > 1)
dp[i][j] += (dp[i - 1][j] - 1) / 2;
}
}
if (dp[query_row][query_glass] > 1)
return 1.0;
return dp[query_row][query_glass];
}
};
1718 Medium. Construct the Lexicographically Largest Valid Sequence
530 Easy. Minimum Absolute Difference in BST
611 Medium. Valid Triangle Number
11 Medium. Container With Most Water
974 Medium. Subarray Sums Divisible by K
需要求mod
318 Medium. Maximum Product of Word Lengths
位运算将字符串转为数字，简化计算
class Solution
{
public:
int maxProduct(vector<string> &words)
{
vector<int> nums;
for (const auto &word : words)
{
int v = 0;
for (int i = 0; i < word.size(); i++)
{
v |= 1 << (word[i] - 'a');
}
nums.push_back(v);
}
int ret = 0;
for (int i = 0; i < nums.size(); i++)
{
for (int j = i + 1; j < nums.size(); j++)
{
if ((nums[i] & nums[j]) == 0)
{
int temp = words[i].size() * words[j].size();
ret = max(ret, temp);
}
}
}
return ret;
}
};
462 Medium. Minimum Moves to Equal Array Elements II
最小一维距离。中位数。
445 Medium. Add Two Numbers II
class Solution
{
public:
ListNode *reverse(ListNode *l)
{
ListNode *pre = nullptr;
while (l)
{
ListNode *next = l->next;
l->next = pre;
pre = l;
l = next;
}
return pre;
}
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
{
if (l1 == nullptr)
return l2;
else if (l2 == nullptr)
return l1;
ListNode *r1 = reverse(l1);
ListNode *r2 = reverse(l2);
ListNode *dummy = new ListNode(0);
ListNode *p = dummy;
int carry = 0;
while (r1 || r2)
{
int v1 = r1 ? r1->val : 0;
int v2 = r2 ? r2->val : 0;
p->next = new ListNode((v1 + v2 + carry) % 10);
carry = (v1 + v2 + carry) / 10;
p = p->next;
if (r1)
r1 = r1->next;
if (r2)
r2 = r2->next;
}
if (carry)
p->next = new ListNode(1);
return reverse(dummy->next);
}
};
735 Medium. Asteroid Collision
1404 Medium. Number of Steps to Reduce a Number in Binary Representation to One
1376 Medium. Time Needed to Inform All Employees
自底向上dfs。
785 Medium. Is Graph Bipartite?
222 Medium. Count Complete Tree Nodes
153 Medium. Find Minimum in Rotated Sorted Array
二分法
class Solution
{
public:
int findMin(vector<int> &nums)
{
int left = 0, right = nums.size() - 1;
while (left < right)
{
if (nums[left] < nums[right])
return nums[left];
int mid = (left + right) / 2;
if (nums[left] <= nums[mid])
left = mid + 1;
else
right = mid;
}
return nums[left];
}
};
1053 Medium. Previous Permutation With One Swap
1545 Medium. Find Kth Bit in Nth Binary String
1156 Medium. Swap For Longest Repeated Character Substring
838 Medium. Push Dominoes
1052 Medium. Grumpy Bookstore Owner
滑动窗口
114 Medium. Flatten Binary Tree to Linked List
743 Medium. Network Delay Time
1798 Medium. Maximum Number of Consecutive Values You Can Make
一把硬币，能表示的最长连续数字。
class Solution
{
public:
int getMaximumConsecutive(vector<int> &coins)
{
sort(coins.begin(), coins.end());
int v = 0;
for (int i = 0; i < coins.size(); i++)
{
if (v + 1 >= coins[i])
v += coins[i];
else
return v + 1;
}
return v + 1;
}
};
1552 Medium. Magnetic Force Between Two Balls
二分
1296 Medium. Divide Array in Sets of K Consecutive Numbers
将数组分成K个子数组，每个子数组的数都是连续的。暴力求解
class Solution
{
public:
bool isPossibleDivide(vector<int> &nums, int k)
{
int n = nums.size();
if (n % k != 0)
return false;
map<int, int> count;
for (int i = 0; i < nums.size(); i++)
count[nums[i]]++;
for (int x = 0; x < n / k; x++)
{
auto it = count.begin();
int v = it->first, c = it->second;
for (int i = 0; i < k; i++)
{
if (it == count.end() || it->first != v)
return false;
it->second -= c;
++it;
v++;
}
while (true)
{
if (count.empty())
return true;
auto it = count.begin();
if (it->second == 0)
count.erase(it);
else
break;
}
}
return count.empty();
}
};
1291 Medium. Sequential Digits
先生成所有递增数，然后利用二分查找到上下界。
class Solution
{
public:
vector<int> sequentialDigits(int low, int high)
{
string all = "123456789";
vector<int> nums;
for (int i = 0; i < all.size(); i++)
{
for (int j = 1; i + j <= all.size(); j++)
{
nums.push_back(stoi(all.substr(i, j)));
}
}
sort(nums.begin(), nums.end());
auto start = lower_bound(nums.begin(), nums.end(), low);
auto end = upper_bound(nums.begin(), nums.end(), high);
vector<int> ret(start, end);
return ret;
}
};
641 Medium. Design Circular Deque
设计双端队列deque
421 Medium. Maximum XOR of Two Numbers in an Array
感觉有些hard.求数组中两数XOR最大值
class Solution
{
public:
int findMaximumXOR(vector<int> &nums)
{
int ret = 0;
int mask = 0;
for (int i = 31; i >= 0; i--)
{
mask = mask | (1 << i);
unordered_set<int> m;
for (int num : nums)
m.insert(num & mask);
int wanner = ret | (1 << i);
for (auto it = m.begin(); it != m.end(); ++it)
{
if (m.count(wanner ^ *it))
{
ret = wanner;
break;
}
}
}
return ret;
}
};
395 Medium. Longest Substring with At Least K Repeating Characters
hard
287 Medium. Find the Duplicate Number
565 Medium. Array Nesting
这些数字会构成多个环，求环的最大长度
class Solution
{
public:
int arrayNesting(vector<int> &nums)
{
int maxsize = 0;
for (int i = 0; i < nums.size(); i++)
{
int size = 0;
for (int k = i; nums[k] >= 0; size++)
{
int tmp = nums[k];
nums[k] = -1;
k = tmp;
}
maxsize = max(maxsize, size);
}
return maxsize;
}
};
1443 Medium. Minimum Time to Collect All Apples in a Tree
120 Medium. Triangle
dp问题
class Solution
{
public:
int minimumTotal(vector<vector<int>> &triangle)
{
vector<vector<int>> dp(triangle.size());
dp[0].resize(1);
dp[0][0] = triangle[0][0];
for (int i = 1; i < triangle.size(); i++)
{
dp[i].resize(triangle[i].size());
for (int j = 0; j < triangle[i].size(); j++)
{
if (j == 0)
dp[i][j] = dp[i - 1][j] + triangle[i][j];
else if (j == i)
dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
else
dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j];
}
}
int ret = INT_MAX;
for (int i = 0; i < dp.back().size(); i++)
{
ret = min(ret, dp.back()[i]);
}
return ret;
}
};
73 Medium. Set Matrix Zeroes
1481 Medium. Least Number of Unique Integers after K Removals
class Solution
{
public:
int findLeastNumOfUniqueInts(vector<int> &arr, int k)
{
map<int, int> count;
for (int i = 0; i < arr.size(); i++)
{
count[arr[i]]++;
}
vector<pair<int, int>> ps;
for (auto it = count.begin(); it != count.end(); ++it)
{
ps.push_back({it->second, it->first});
}
sort(ps.rbegin(), ps.rend());
for (int i = ps.size() - 1; i >= 0; i--)
{
if (ps[i].first > k)
return i + 1;
k -= ps[i].first;
}
return 0;
}
};
377 Medium. Combination Sum IV
和coin change类似
1461 Medium. Check If a String Contains All Binary Codes of Size K
981 Medium. Time Based Key-Value Store
1424 Medium. Diagonal Traverse II
class Solution
{
public:
vector<int> findDiagonalOrder(vector<vector<int>> &nums)
{
map<int, vector<int>> mymap;
for (int i = 0; i < nums.size(); i++)
{
for (int j = 0; j < nums[i].size(); j++)
{
mymap[i + j].push_back(nums[i][j]);
}
}
vector<int> ret;
for (auto it = mymap.begin(); it != mymap.end(); ++it)
{
auto vec = it->second;
for (int i = vec.size() - 1; i >= 0; i--)
{
ret.push_back(vec[i]);
}
}
return ret;
}
};