题解: 记忆化搜索，dp[i][j]代表以(i,j)结点为起点的最长递增路径。记忆化搜索即可。
class Solution {
public:
int dp[1000][1000];
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
int dfs(int x, int y, vector<vector<int>>& matrix ){
if(dp[x][y]) return dp[x][y];
int &ans = dp[x][y];
ans = 1; // 其本身为1
for(int i=0;i<4;i++){
int xx = x+dir[i][0], yy = y+dir[i][1];
if(xx<0||xx>=matrix.size() || yy<0 || yy>=matrix[0].size() || matrix[xx][yy]<=matrix[x][y]) continue;
ans = max(ans, dfs(xx, yy,matrix)+1);
}
return ans;
}
int longestIncreasingPath(vector<vector<int>>& matrix) {
int ans = 0;
for(int i=0;i<matrix.size();i++){
for(int j=0;j<matrix[0].size();j++){
dfs(i,j,matrix);
ans = max(ans , dp[i][j]);
}
}
return ans;
}
};
题解: 动态规划，子数组是连续的(哭出声，周赛以为是不连续...)。 dp[i][0] 代表以arr[i]结尾的和为奇数的子数组个数，dp[i][1] 代表以arr[i]结尾的和为偶数的子数组个数。
则当arr[i]为奇数时， 以arr[i]结尾的奇数组数量等于以arr[i-1]结尾的偶数组数量+1 , 以arr[i]结尾的偶数组数量等于以arr[i-1]结尾的奇数组数量。
则当arr[i]为偶数时， 以arr[i]结尾的偶数组数量等于以arr[i-1]结尾的偶数组数量+1 , 以arr[i]结尾的奇数组数量等于以arr[i-1]结尾的奇数组数量。
class Solution {
public:
int dp[100005][2]; // dp[i][0]代表以arr[i]结尾的子数组中和为奇数的子数组数目，dp[i][1]则为偶数的子数组个数
int numOfSubarrays(vector<int>& arr) {
dp[0][0] = arr[0]%2;
dp[0][1] = !(arr[0]%2);
int ans = dp[0][0];
for(int i=1;i<arr.size();i++){
if(arr[i]%2){
dp[i][0] = dp[i-1][1] + 1;
dp[i][1] = dp[i-1][0];
}else{
dp[i][0] = dp[i-1][0] ;
dp[i][1] = dp[i-1][1] + 1;
}
ans = (ans+dp[i][0])%1000000007;
}
return ans;
}
};
题解: 前缀和+枚举断点。
class Solution {
public:
bool Hash[100005][26],Hash1[100005][26];
int numSplits(string s) {
if(s.size()==1) return 0;
Hash[0][s[0]-'a'] = 1;
for(int i=1;i<s.size();i++){
for(int j=0;j<26;j++) Hash[i][j] = Hash[i-1][j];
Hash[i][s[i]-'a'] = 1;
}
int len = s.size();
Hash1[len-1][s[len-1]-'a'] = 1;
for(int i=len-2;i>=0;i--){
for(int j=0;j<26;j++) Hash1[i][j] = Hash1[i+1][j];
Hash1[i][s[i]-'a'] = 1;
}
int ans = 0;
for(int i=0;i<len-1;i++){
int a = 0;
for(int j=0;j<26;j++){
a += Hash[i][j];
}
int b = 0;
for(int j=0;j<26;j++){
b += Hash1[i+1][j];
}
//printf("%d %d\n",a, b);
if(a==b) ans++;
}
return ans;
}
};
题解: 贪心的去搞了，如果前一个数比后一个数小，那么可以知道肯定后一个数肯定形成了新的一段，然后操作了(后一个数-前一个数)次，如果后一个数与前一个数相等或者比它小，那他们是可以放在一次操作里面搞定的。
class Solution {
public:
int minNumberOperations(vector<int>& target) {
int ans = target[0];
for(int i=1;i<target.size();i++){
if(target[i-1] >= target[i]) continue;
ans += target[i] - target[i-1];
}
return ans;
}
};
题解: 除去前导0不用变，每一次0->1 或者 1->0 都是重新分段引起的，看变化了多少次即可。
class Solution {
public:
int minFlips(string target) {
int i = 0;
while(i<target.size()){
if(target[i]=='0') i++;
else break;
}
target = target.substr(i);
if(target.size()==0) return 0;
int ans = 1;
for(int i=1;i<target.size();i++){
if(target[i]==target[i-1]) continue;
ans++;
}
return ans;
}
};
题解: 我的做法可能不太简洁。。。找到所有的叶子结点，保存所有叶子的父节点，通过枚举每一对叶子，然后计算LCA。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int f[2000], levels[2000];
vector <int> leaf;
int cnt = 0;
void find_leaf(TreeNode* root, int fa,int level){
if(!root) return;
f[++cnt] = fa;
levels[cnt] = level;
int now = cnt;
if(root->left==NULL && root->right==NULL) leaf.push_back(now);
find_leaf(root->left, now, level+1);
find_leaf(root->right,now, level+1);
}
int countPairs(TreeNode* root, int distance) {
find_leaf(root,0,0);
int ans = 0;
for(int i=0;i<leaf.size();i++){
for(int j=i+1;j<leaf.size();j++){
int p = leaf[i], q = leaf[j];
int d = 0;
if (levels[p] >levels[q]) swap(p, q);
while (levels[p] < levels[q]) q = f[q], d++;
while (p != q) {
p = f[p];
q = f[q];
d += 2;
}
if(d <= distance) ans++;
}
}
return ans;
}
};
