LeetCode第 292 场周赛

模拟即可

// shiran
#include 
using namespace std;

#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, n, a) for (int i = n - 1; i >= a; i--)
#define sz(x) (int)size(x)
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define pb push_back
typedef long long ll;
typedef pair PII;
const int mod = 1e9+7;
const int N = 40010, M = 300010;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
class Solution {
public:
    string largestGoodInteger(string num) {
    	string ans = "";
        for (int i = 0; i + 2 < sz(num); i ++ ) {
        	if (num[i] == num[i + 1] && num[i + 1] == num[i + 2])
        	{
        		if (sz(ans)==0) ans = num.substr(i,3);
        		else if (num[i] > ans[0])
        			ans = num.substr(i,3);
			}
		}
		return ans;
    }
};

深度优先遍历先遍历子树返回权值和和结点数量，每个结点比较计数

// shiran
#include 
using namespace std;

#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, n, a) for (int i = n - 1; i >= a; i--)
#define sz(x) (int)size(x)
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define pb push_back
#define mk make_mair
typedef long long ll;
typedef pair PII;
const int mod = 1e9+7;
const int N = 40010, M = 300010;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};


class Solution {
public:
	int res=0;
    int averageOfSubtree(TreeNode* root) {
        dfs(root);
        return res;
    }
    
    PII dfs(TreeNode* root) {
    	if (!root) return {0, 0};
    	auto l = dfs(root->left), r = dfs(root->right);
        int sum = l.x + r.x + root->val, cnt = l.y+r.y+1;
    	if ((floor)(sum / cnt) == root->val) res ++;
    	return {sum, cnt};
	}
};

DP，考虑最近的几个字符构成一个字母，f[j]表示前j个字符方案数量，考虑最近的k个字符构成一个字母，显然k最大值应该是3或者是4，答案应该加上除了最近的这k个字母，前面的方案数量f[j]+=f[j-k]，递推得到结果。

// shiran
#include 
using namespace std;

#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, n, a) for (int i = n - 1; i >= a; i--)
#define sz(x) (int)size(x)
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define pb push_back
#define mk make_mair
typedef long long ll;
typedef pair PII;
const int mod = 1e9+7;
const int N = 100010, M = 300010;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

class Solution {
public:
    int countTexts(string s) {
        int n = sz(s);
        s = " " + s;
        ll f[N];
        memset(f, 0, sizeof f);
        f[0] = 1;
        for (int i = 1; i <= n; i ++ ) {
        	for (int j = i; j >= max(1, i - 2 - (s[i] == '7' || s[i] == '9')); j -- )
        		if (s[i] == s[j])
        			f[i] = (f[i] + f[j - 1]) % mod;
                else
                    break;
		}
		return f[n];
    }
};

DP，合法括号序列左括号-右括号数量实时非负，那么DP第三维表示左括号比右括号多的数量。

// shiran
#include 
using namespace std;

#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, n, a) for (int i = n - 1; i >= a; i--)
#define sz(x) (int)size(x)
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define pb push_back
#define mk make_mair
typedef long long ll;
typedef pair PII;
const int mod = 1e9+7;
const int N = 110, M = 300010;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

bool f[N][N][2 * N];

class Solution {
public:
	int n, m;
    bool hasValidPath(vector>& s) {
        memset(f, false, sizeof f);
        int n = s.size();
        int m = s[0].size();
        f[1][0][0] = true;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (s[i - 1][j - 1] == '(')
                {
                    for (int k = 1; k < n + m; k++)
                    {
                        f[i][j][k] |= f[i - 1][j][k - 1];
                        f[i][j][k] |= f[i][j - 1][k - 1];
                    }
                }
                else // ')'
                {
                    for (int k = 0; k + 1 < n + m; k++)
                    {
                        f[i][j][k] |= f[i - 1][j][k + 1];
                        f[i][j][k] |= f[i][j - 1][k + 1];
                    }
                }
            }
        }
        return f[n][m][0];
    }
};