class Solution {
public:
int countOfPairs(vector<int>& nums) {
vector<vector<int>> dp(nums.size() + 1, vector<int>(51, 0));
for (int i = 0; i <= nums[0]; i++) {
dp[0][i] = 1;
}
for (int i = 0; i < nums.size() - 1; i++) {
for (int j = 0; j <= nums[i]; j++) {
for (int k = j; k <= nums[i + 1]; k++) {
if (nums[i] - j >= nums[i + 1] - k) {
dp[i + 1][k] += dp[i][j];
dp[i + 1][k] %= int(1e9 + 7);
}
}
}
}
int sum = 0;
for (int i = 0; i < dp[nums.size() - 1].size(); i++) {
sum += dp[nums.size() - 1][i];
sum %= int(1e9 + 7);
}
return sum;
}
};class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string> > ans;
unordered_map<string, int> mp;
unordered_map<int, vector<string> > mp_ans;
for(int i = 0; i < strs.size(); i++){
string newstr = strs[i];
sort(newstr.begin(), newstr.end());
if(mp[newstr]){
mp_ans[mp[newstr]].push_back(strs[i]);
} else {
vector<string> new_v;
new_v.push_back(strs[i]);
mp[newstr] = mp_ans.size() + 1;
mp_ans[mp_ans.size() + 1] = new_v;
}
}
for(auto i : mp_ans){
ans.push_back(i.second);
}
return ans;
}
};class Solution {
public:
unordered_map<int, bool> init;
unordered_map<int, int> mp;
unordered_map<int, int> ans_mp;
int find(int x){
int fa = x;
while(fa != mp[fa]){
fa = mp[fa];
}
mp[x] = fa;
return fa;
}
int longestConsecutive(vector<int>& nums) {
int ans = 0;
for(int i = 0; i < nums.size(); i++){
mp[nums[i]] = nums[i];
ans_mp[nums[i]] = 1;
init[nums[i]] = true;
}
for(int i = 0; i < nums.size(); i++){
vector<int> fas;
vector<int> pos;
if(init[nums[i] - 1]) pos.push_back(nums[i] - 1);
pos.push_back(nums[i]);
if(init[nums[i] + 1]) pos.push_back(nums[i] + 1);
int max_num = 0;
int max_pos = 1e9 + 8;
for(int i = 0; i < pos.size(); i++){
int fa = find(pos[i]);
if(ans_mp[fa] > max_num){
max_pos = fa;
max_num = ans_mp[fa];
}
}
cout<<max_pos<<" "<<max_num<<endl;
if(init[nums[i] - 1] && find(mp[nums[i] - 1]) != max_pos){
ans_mp[max_pos] += ans_mp[find(mp[nums[i] - 1])];
mp[find(mp[nums[i] - 1])] = max_pos;
}
if(mp[find(mp[nums[i]])] != max_pos){
ans_mp[max_pos] += ans_mp[find(mp[nums[i]])];
mp[find(mp[nums[i]])] = max_pos;
}
if(init[nums[i] + 1] && mp[find(mp[nums[i] + 1])] != max_pos){
ans_mp[max_pos] += ans_mp[mp[find(mp[nums[i] + 1])]];
mp[find(mp[nums[i] + 1])] = max_pos;
}
cout<<ans_mp[max_pos]<<endl;
ans = max(ans, ans_mp[max_pos]);
}
return ans;
}
};class Solution {
public:
void moveZeroes(vector<int>& nums) {
int b = 0;
for(int i = 0; i < nums.size(); i++){
if(nums[i] == 0){
for(int j = max(i + 1, b); j < nums.size(); j++){
if(nums[j] != 0){
swap(nums[i], nums[j]);
break;
}
b = max(b, j);
}
}
}
return;
}
};两端的指针每次移动较小的那个，因为可以证明的是如果移动较大的一端，之后的任何情况都不可能比现在的情况好。
这道题最开始可以考虑暴力的情况，也就是如果全搜索，应该是两端的指针每次有两种选择，移动左边或者右边，然后再根据上面说的问题考虑是否可以剪枝。
class Solution {
public:
int maxArea(vector<int>& height) {
int l = 0, r = height.size() - 1;
int ans = 0;
while(l < r){
ans = max(ans, min(height[l], height[r]) * (r - l));
if(height[l] < height[r]){
l = l + 1;
} else {
r = r - 1;
}
}
return ans;
}
};class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
unordered_map<string, bool> st;
unordered_map<int, int> ext;
for (int i = 0; i < nums.size(); i++) {
ext[nums[i]] += 1;
}
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
for (int i = 0; i < nums.size(); i++) {
if(nums[i] > 0) break;
if(i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < nums.size(); j++) {
int c = -(nums[i] + nums[j]);
if (ext[c]) {
if (!((c == nums[i] || c == nums[j]) && ext[c] < 2) &&
!((c == nums[i] && c == nums[j]) && ext[c] < 3)) {
vector<int> nv;
nv.push_back(nums[i]);
nv.push_back(nums[j]);
nv.push_back(c);
sort(nv.begin(), nv.end());
string k = to_string(nv[0]) + "/" + to_string(nv[1]) +
"/" + to_string(nv[2]);
if (!st[k]) {
ans.push_back(nv);
}
st[k] = true;
}
}
}
}
return ans;
}
};