https://leetcode.com/problems/count-the-number-of-good-subsequences/description/

求[1,n]的所有数逆元在模p下的逆元， 用pow(n,p – 2,p)太慢了。所有用下面代码

inv[1] = 1;
for (int i = 2; i <= n; ++i) {
  inv[i] = (long long)(p - p / i) * inv[p % i] % p;
}

多米诺题，找规律.

class Solution {
public:
    int dp[1001][1001] = {};
    int M = 1e9+7;
    int N;
    int numTilings(int n) {
        N = n;
        return dfs(0,0);
    }
    long long dfs(int t, int b) {
        if(t > N || b > N){
            return 0;
        }
        if(t == N && b == N){
            return 1;
        }
        if(dp[t][b])
            return dp[t][b];
        long long res = 0; 
        if(t == b)
            res += dfs(t + 1, b + 1) + dfs(t + 2, b + 1) + dfs(t + 1, b + 2) + dfs(t + 2, b);
        else if(t + 1 == b)
            res += dfs(t + 2, b) + dfs(t + 2, b + 1);
        else if(t == b + 1)
            res += dfs(t, b + 2) + dfs(t + 1, b + 2);
        else if (t == b + 2)
            res += dfs(t, b + 2);
        return dp[t][b] = res % M;
    }
};

dp好题

class Solution {
public:
    int dp[101][1001][6] = {};
    int maxTastiness(vector<int>& price, vector<int>& tastiness, int maxAmount, int maxCoupons) {
        return dfs(price, tastiness, maxAmount, maxCoupons, 0);
    }
    int dfs(vector<int>& p, vector<int>& t, int A, int C, int i) {
        if(i >= p.size())
            return 0;
        if(dp[i][A][C])
            return dp[i][A][C];
        int res = 0;
        int buyWithCoupons = C && (A - (p[i] / 2) >= 0) ? dfs(p, t, A - (p[i] / 2), C - 1, i + 1) + t[i] : 0;
        int buyWithOutCoupons = A - (p[i]) >= 0 ? dfs(p, t, A - p[i], C, i + 1) + t[i] : 0;
        int noBuy = dfs(p, t, A, C, i + 1);
        res = max({buyWithCoupons, buyWithOutCoupons, noBuy});
        return dp[i][A][C] = res;
    }
};

就是挨个找最大

class Solution {
    public int[][] largestLocal(int[][] grid) {
        int n = grid.length;
        int[][] res = new int[n - 2][n - 2];
        for(int i = 1; i < n - 1; i++) {
            for(int j = 1; j < n - 1; j++) {
                res[i - 1][j - 1] = val(grid,i,j);
            }
        }
        return res;
    }
    
    public int val(int[][] g, int a, int b) {
        int res = Integer.MIN_VALUE;
        for(int i = a - 1; i <= a + 1; i++){
            for(int j = b - 1; j <= b + 1; j++){
                res = Math.max(res, g[i][j]);
            }
        }
        return res;
    }
}

算税

class Solution {
    public double calculateTax(int[][] brackets, int income) {
        int prev = 0;
        double tax = 0d;
        for(int[] b : brackets){ 
            int d = b[0] - prev;
            if(d <= income)
                tax += ((double)b[1] / 100d) * d;
            else
                tax += ((double)b[1] / 100d) * (double)income;
            income -= d;
            if(income <= 0)
                break;
            prev = b[0];
        }
        return tax;
    }
}

这题好煞笔

class Solution {
    public boolean isOneBitCharacter(int[] bits) { 
        int i = 0;
        while(i < bits.length - 1) {
            if(bits[i] == 1) 
                i+=2;
            else
                i++;
        }
        return i == bits.length - 1;
    }
}

扑克判断， 没啥可说的

class Solution {
    public String bestHand(int[] ranks, char[] suits) { 
        if(flush(ranks, suits))
            return "Flush";
        if(three(ranks, suits))
            return "Three of a Kind";
        if(pair(ranks, suits))
            return "Pair";
        return "High Card";        
    }
    public boolean pair(int[] r, char[] s) {
        int[] rk = new int[15];
        for(int rr : r){
            rk[rr - 1]++;
        }
        for(int rrk : rk){
            if(rrk >= 2)
                return true;
        }
        return false;
    }
    
    public boolean flush(int[] r, char[] s) {
        int[] c = new int[6];
        for(char ss : s) {
            c[ss - 'a']++;
        }
        for(int cc : c){
            if(cc == 5)
                return true;
        }
        return false;
    }
    
    public boolean three(int[] r, char[] s){
        int[] rk = new int[15];
        for(int rr : r){
            rk[rr - 1]++;
        }
        for(int rrk : rk){
            if(rrk >= 3)
                return true;
        }
        return false;
    }
}

并查集模板题

class Solution {
    class uf{
        int[] p;
        int n;
        public uf(int n){
            this.n = n + 1;
            this.p = new int[n + 1];
            for(int i = 1; i <= n; i++)
                this.p[i] = i;
        }
        public int find(int n){
            if(p[n] == n)
                return n;
            p[n] = find(p[n]);
            return p[n];
        }
        
        public void union(int a, int b){
            int ra = find(a);
            int rb = find(b);
            if(ra == rb)
                return;
            if(ra < rb)
                p[ra] = rb;
            else
                p[rb] = ra;
        }
    }
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        uf u = new uf(n);
        for(int[] e : edges){
            if(u.find(e[0]) != u.find(e[1]))
                u.union(e[0], e[1]);
            else
                return e;
        }
        return null;
    }
}

class Solution {
    int[][] dirs = new int[][]{
        {-1,0},
        {1,0},
        {0, 1},
        {0, -1}
    };
    public int swimInWater(int[][] grid) {
        boolean[][] v = new boolean[grid.length][grid[0].length];
        int res = 0;
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b) -> (a[2] - b[2]));
        q.add(new int[]{0,0,grid[0][0]});
        while(!q.isEmpty()){
            int[] cur = q.poll();
            if(v[cur[0]][cur[1]])
                continue;
            res = Math.max(res, cur[2]);
            if(cur[0] == grid.length - 1 && cur[1] == grid[0].length - 1)
                break;
            v[cur[0]][cur[1]] = true;
            for(int[] d : dirs){
                int nr = d[0] + cur[0];
                int nc = d[1] + cur[1];
                if(0 <= nr && nr < grid.length && 0 <= nc && nc < grid[0].length && !v[nr][nc]){
                    q.add(new int[]{nr, nc,grid[nr][nc]});
                }
            }
        }
        return res;
    }
}

给一个rooms的列表, 里面只有第一个room是开锁的, 其他room的锁的钥匙在各个房间, 求是否能访问所有的room

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int n = rooms.size();
        boolean[] visited = new boolean[n];
        Queue<Integer> q = new LinkedList<>();
        visited[0] = true;
        for(int nn : rooms.get(0)){
            q.add(nn);
        }
        while(!q.isEmpty()){
            int t = q.poll();
            if(!visited[t]){
                visited[t] = true;
                for(int nn : rooms.get(t))
                    q.add(nn);
            }
        }
        for(boolean b : visited)
            if(!b)
                return false;
        return true;
    }
}