数组 – CheungQ

class Solution { public boolean validMountainArray(int[] arr) { int l = 0; int r = arr.length-1; while (l<r && arr[l+1] > arr[l]){ l++; } while (r>0 && arr[r-1] > arr[r]){ r--; } return l==r && l!=0 && l != arr.length-1; } }

class Solution { public int findRadius(int[] houses, int[] heaters) { Arrays.sort(heaters); int ans = 0; for (int house : houses) { int l = 0; int r = heaters.length-1; int tmp = (int) 1e9+1; while (l<=r){ int mid = (l + r)/2; //怕遗漏边缘情况不好处理就每次二分的结果都比较下 tmp = Math.min(tmp, Math.abs(heaters[mid] - house)); if (heaters[mid] > house){ r = mid-1; }else if (heaters[mid] < house){ l = mid+1; }else { break; } } ans = Math.max(ans,tmp); } return ans; } }

输入：points = [[2,1],[2,2],[3,3]], angle = 90, location = [1,1] 输出：3 解释：阴影区域代表你的视野。在你的视野中，所有的点都清晰可见，尽管 [2,2] 和 [3,3]在同一条直线上，你仍然可以看到 [3,3] 。

代码

class Solution { public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) { double x1 = (double) location.get(0); double y1 = (double) location.get(1); double[] radianList = new double[points.size()]; double radianWin = angle * Math.PI / 180; int alwaysSee = 0; int idx = -1; for (List<Integer> point : points) { double x2 = (double) point.get(0); double y2 = (double) point.get(1); if (x1 == x2 && y1 == y2){ alwaysSee++; continue; } radianList[++idx] = Math.atan2(y2-y1,x2-x1); if (radianList[idx] < 0){ radianList[idx] += Math.PI * 2; } } Arrays.sort(radianList); if (alwaysSee>0){ double[] tmp = new double[radianList.length-alwaysSee]; System.arraycopy(radianList,alwaysSee,tmp,0,radianList.length-alwaysSee); radianList = tmp; } //开始滑窗统计 int l = 0; int r = 0; int max = 0 ; //窗口初始化 while (r + 1 < radianList.length && radianList[r+1] <= radianList[l] + radianWin ){ r++; max = r-l+1; } //在原来的radianList数组之后,在拼上一段radianWin弧度的数据，这段数据为从弧度0开始到弧度radianWin之内的所有数据 //而这里得0到滑窗弧度范围内的点的值 if (radianList.length>0 && radianList[l] <= radianWin){ double[] tmp = new double[radianList.length + max]; System.arraycopy(radianList,0,tmp,0,radianList.length); System.arraycopy(radianList,0,tmp,radianList.length,max); for (int i = radianList.length; i < tmp.length; i++) { tmp[i] += Math.PI * 2; } radianList = tmp; } //开始滑动 while (l<radianList.length && radianList[l]+ radianWin <= radianList[radianList.length-1]){ l++; while (r + 1 < radianList.length && radianList[r+1] <= radianList[l]+radianWin ){ r++; } max = Math.max(max,r-l+1); } return max+alwaysSee; } }

根据百度百科， 生命游戏 ，简称为生命，是英国数学家约翰·何顿·康威在 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; } }

输入：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); }); } } }

输入：grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]] 输出：35 解释：建筑物的高度如上图中心所示。用红色绘制从不同方向观看得到的天际线。在不影响天际线的情况下，增加建筑物的高度： gridNew = [ [8, 4, 8, 7], [7, 4, 7, 7], [9, 4, 8, 7], [3, 3, 3, 3] ]

class Solution { public int maxIncreaseKeepingSkyline(int[][] grid) { int[] rowMin = new int[grid.length]; int[] colMin = new int[grid[0].length]; for (int row = 0; row < grid.length; row++) { for (int col = 0; col < grid[row].length; col++) { int height = grid[row][col]; rowMin[row] = Math.max(rowMin[row],height); colMin[col] = Math.max(colMin[col],height); } } int ans = 0; for (int row = 0; row < grid.length; row++) { for (int col = 0; col < grid[row].length; col++) { ans += Math.min(rowMin[row],colMin[col]) - grid[row][col]; } } return ans; } }

近期文章

分类

文章归档

标签：数组

LeetCode刷题【941】有效的山脉数组

代码

LeetCode刷题【475】供暖器

代码

LeetCode刷题【1610】可见点的最大数目

代码

LeetCode刷题【289】生命游戏

数组复制的方法代码

原地修改

原地修改代码

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

代码

LeetCode刷题【851】喧闹和富有

代码

LeetCode刷题【807】保持城市天际线

代码