[置顶]小程序: 查询退出美国国籍的人
你是不是一直怀疑李开复或者谷爱凌到底有没有退出美国国籍?
你是不是看到各种退出美国国籍的人的数字, 却无法得知事情真相?
我写了一个小程序, 可以查询退出美国国籍的人名和总数.
线性求逆元
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;
}Domino and Tromino Tiling
多米诺题，找规律.
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;
}
};Maximize Total Tastiness of Purchased Fruits
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;
}
};Largest Local Values in a Matrix
就是挨个找最大
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;
}
}Calculate Amount Paid in Taxes
算税
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;
}
}1-bit and 2-bit Characters
这题好煞笔
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;
}
}Best Poker Hand
扑克判断， 没啥可说的
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;
}
}Redundant Connection
并查集模板题
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;
}
}Swim in Rising Water
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;
}
}