CheungQ

输入：n = 2 输出：6 解释：所有可能的序列包括： (P1,P2,D1,D2)，(P1,P2,D2,D1)，(P1,D1,P2,D2)，(P2,P1,D1,D2)，(P2,P1,D2,D1) 和 (P2,D2,P1,D1)。 (P1,D2,P2,D1) 是一个无效的序列，因为物品 2 的收件服务（P2）不应在物品 2 的配送服务（D2）之后。

class Solution { public int countOrders(int n) { long ans = 1; long mod = (long) (1e9+7); for (int i = 2; i <= n; i++) { ans *= (2 * i * i - i); ans %= mod; } return (int)ans; } }

这里有 n 个一样的骰子，每个骰子上都有 k 个面，分别标号为 1 到 k 。

给定三个整数 n , k 和 target ，返回可能的方式(从总共 kⁿ 种方式中)滚动骰子的数量，使正面朝上的数字之和等于 target 。

答案可能很大，你需要对 10⁹ + 7 取模。

示例 1：

输入：n = 1, k = 6, target = 3
输出：1
解释：你扔一个有6张脸的骰子。
得到3的和只有一种方法。

示例 2：

输入：n = 2, k = 6, target = 7
输出：6
解释：你扔两个骰子，每个骰子有6个面。
得到7的和有6种方法1+6 2+5 3+4 4+3 5+2 6+1。

示例 3：

输入：n = 30, k = 30, target = 500
输出：222616187
解释：返回的结果必须是对 10⁹ + 7 取模。

提示：

1 <= n, k <= 30
1 <= target <= 1000

Related Topics

动态规划

class Solution { /** * dp[i][target] = dp[i-1][target-1] + .... + dp[i-1][target-k] */ public int numRollsToTarget(int n, int k, int target) { int mod = (int) 1e9 + 7; int[][] dp = new int[n][target+1]; for (int i = 1; i <= k && i <= target; i++) { dp[0][i] = 1; } for (int row = 1; row < n; row++) { for (int col = row+1; col <= target; col++) { for (int i = 1; i <= k; i++) { if (i>col){ continue; } dp[row][col] += dp[row-1][col-i]; dp[row][col] %= mod; } } } return dp[n-1][target]; } }

根据百度百科， 生命游戏 ，简称为生命，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为 活细胞 （live），或 0 即为 死细胞 （dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
如果死细胞周围正好有三个活细胞，则该位置死细胞复活；

下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。

示例 1：

输入：board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
输出：[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

示例 2：

输入：board = [[1,1],[1,0]]
输出：[[1,1],[1,1]]

提示：

m == board.length
n == board[i].length
1 <= m, n <= 25
board[i][j] 为 0 或 1

进阶：

你可以使用原地算法解决本题吗？请注意，面板上所有格子需要同时被更新：你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子。
本题中，我们使用二维数组来表示面板。原则上，面板是无限的，但当活细胞侵占了面板边界时会造成问题。你将如何解决这些问题？

数组复制的方法代码

class Solution {
    public void gameOfLife(int[][] board) {
        int m = board.length;
        int n = board[0].length;
        int[][] ans = new int[m][n];
        int[][] dir = new int[][]{{1,0},{-1,0},{0,1},{0,-1},{1,-1},{1,1},{-1,1},{-1,-1}};

        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                int cnt = 0;
                for (int i = 0; i < dir.length; i++) {
                    int x = row+dir[i][0];
                    int y = col+dir[i][1];
                    if (x<0||y<0||x>=m||y>=n){
                        continue;
                    }
                    cnt += board[x][y];
                }

                if (board[row][col] == 1){
                    //如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
                    ans[row][col] = (cnt == 2 || cnt == 3)?1:0;
                    //如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
                    //如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
                }else{
                    //如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
                    ans[row][col] = cnt==3?1:0;
                }
            }
        }

        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                board[row][col] = ans[row][col];
            }
        }
    }
}

原地修改

而原地修改大佬们用的方法略高端，用二进制位的状态来标记。我这有个简化版的原理一样。
思路如下，也许可以帮到你更加容易的来理解这个过程

因为周围最多只有8个格子，所以周围最多活细胞数量只有8个，这个数字小于10，那么我们可以活用这个关系
讲当前格子状态进一位，变成10或者00，第一位表示当前格子的状态
后面一位的0我们更新为周围8个格子的活细胞数量，
比如更新后当前格子的值为14，第一位1表示当前格子是活细胞，周围8个格子中有4个活细胞
又比如更新后当前格子的值为5,第一位的10位数上没有，即为0，那么表明当前格子为死细胞，周围有5个活细胞
一遍更新完了之后，我们就可以根据更新后的结果值来重新换算下当前格子的下一步状态值是死细胞还是活细胞了
又，因为是从左往右，从上往下的更新的，所以，在计算周围8个格子中活细胞数量的时候需要注意一下以下情况
- 当前行的上一行对应的3个格子中的结果是已经计算过之后的结果，所以判断细胞死活情况需要判断的是10位数的值
- 当前格子当前行左边一个格子也是已经计算过的结果，所以也需要根据10位数的值来判断死活情况

原地修改代码

class Solution {
    public void gameOfLife(int[][] board) {
        int m = board.length;
        int n = board[0].length;
        int[][] dir = new int[][]{{1,0},{-1,0},{0,1},{0,-1},{1,-1},{1,1},{-1,1},{-1,-1}};
        int cnt = 0;
        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                cnt = 0;
                for (int i = 0; i < dir.length; i++) {
                    int x = row+dir[i][0];
                    int y = col+dir[i][1];
                    if (x<0||y<0||x>=m||y>=n){
                        continue;
                    }
                    if (dir[i][0]<0 || (dir[i][0]==0 && dir[i][1]<0)){
                        cnt += board[x][y]/10;
                    }else{
                        cnt += board[x][y];
                    }
                }
                board[row][col] = board[row][col]*10 + cnt;
            }
        }

        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                cnt = board[row][col] % 10;
                int status = board[row][col]/10;
                if (status==1){
                    board[row][col] = (cnt == 2 || cnt == 3)?1:0;
                }else{
                    board[row][col] =  cnt==3?1:0;
                }
            }
        }
    }
}

class Solution { public int numIdenticalPairs(int[] nums) { int[] arr = new int[101]; int ans = 0; for (int num : nums) { arr[num]++; ans += arr[num]-1; } return ans; } }

class Solution { public int reachNumber(int target) { if (target==0)return 0; target = Math.abs(target); int k = (int) Math.sqrt(2 * target); k--; while ((1 + ++k) * k / 2 < target){} int d = (1 + k) * k / 2 - target; while (d%2!=0) { d += ++k; } return k; } }

输入：richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0] 输出：[5,5,2,5,4,5,6,7] 解释： answer[0] = 5， person 5 比 person 3 有更多的钱，person 3 比 person 1 有更多的钱，person 1 比 person 0 有更多的钱。唯一较为安静（有较低的安静值 quiet[x]）的人是 person 7，但是目前还不清楚他是否比 person 0 更有钱。 answer[7] = 7，在所有拥有的钱肯定不少于 person 7 的人中（这可能包括 person 3，4，5，6 以及 7），最安静（有较低安静值 quiet[x]）的人是 person 7。其他的答案也可以用类似的推理来解释。

class Solution { // richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], // quiet = [3,2,5,4,6,1,7,0] // 6 5 // ↓ ↙ // 2 3 ← 4 // ↓ ↙ ↘ // 1 7 // ↓ // 0 HashMap<Integer, HashSet<Integer>> map = new HashMap<>(); int[] ans; int[] quiet; int[] quietToPerson; public int[] loudAndRich(int[][] richer, int[] quiet) { this.quiet = quiet; ans = new int[quiet.length]; Arrays.fill(ans,501); quietToPerson = new int[quiet.length]; for (int i = 0; i < quiet.length; i++) { quietToPerson[quiet[i]] = i; } HashSet<Integer> starter = new HashSet<>(); for (int[] ints : richer) { if (!map.containsKey(ints[0])){ map.put(ints[0],new HashSet<>()); } map.get(ints[0]).add(ints[1]); starter.remove(ints[1]); starter.add(ints[0]); } starter.forEach(i -> { dfs(i,quiet[i]); }); for (int i = 0; i < ans.length; i++) { ans[i]= quietToPerson[ans[i]>500?quiet[i]:ans[i]]; } return ans; } public void dfs(int num, int min){ if (min > quiet[num]){ min = quiet[num]; } if (ans[num] > min){ ans[num] = min; }else{ return; } if (map.containsKey(num)){ int finalMin = min; map.get(num).forEach(integer -> { dfs(integer, finalMin); }); } } }

class Solution { public int nthMagicalNumber(int n, int a, int b) { long mod = (long)(1e9 + 7); long l = 2; long r = (long) n * Math.min(a,b); while (l < r){ long mid = l + ((r-l)>>1); if(f(a,b,mid) < n){ l = mid + 1; }else{ r = mid; } } return (int)(l % mod); } long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); } long lcm(long a, long b) { return (a * b) / gcd(a, b); } long f(long a, long b, long x) { return (x / a) + (x / b) - (x / lcm(a, b)); } }

近期文章

分类

文章归档

Page 8 of 61

LeetCode刷题【1359】有效的快递序列数目

代码

LeetCode刷题【1155】掷骰子的N种方法

代码

LeetCode刷题【289】生命游戏

数组复制的方法代码

原地修改

原地修改代码

LeetCode刷题【1512】好数对的数目

代码

LeetCode刷题【754】到达终点数字

代码

LeetCode刷题【851】喧闹和富有

代码

LeetCode刷题【878】第 N 个神奇数字

代码