算法|数组

9. 回文数

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) return false;
        int y = x;
        int z = 0;
        while (y > 0){
            int k = y % 10;
            z = z * 10 + k;
            y = y / 10;
        }
        return x == z;
    }
}

88. 合并两个有序数组

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1;
        int p2 = n - 1;
        for (int i = m + n - 1; i >= 0; i--){
            if (p1 >= 0 && p2 >= 0) {
                if (nums1[p1] > nums2[p2]) {
                   nums1[i] = nums1[p1--];
                } else {
                    nums1[i] = nums2[p2--];
                }
            } else if (p2 >= 0) {
                nums1[i] = nums2[p2--];
            } else {
                break;
            }
        }
    }
}.

128. 最长连续序列

class Solution {
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> hashSet = new HashSet<>();
        for (int num:nums){
            hashSet.add(num);
        }
        int maxCount = 0;
        for (int num:hashSet){
            //不是最小的
            if (!hashSet.contains(num - 1)) {
                int cur = num;
                int count = 1;
                while (hashSet.contains(cur + 1)) {
                    cur++;
                    count++;
                }
                maxCount = Math.max(maxCount, count);
            }
        }
        return maxCount;
    }
}

217. 存在重复元素

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> hashSet = new HashSet<>();
        for (int num:nums){
            if (hashSet.contains(num)) return true;
            hashSet.add(num);
        }
        return false;
    }
}

238. 除自身以外数组的乘积

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int left = 1;
        int length = nums.length;
        int[] result = new int[length];
        for (int i = 0; i < length; i++){
            result[i] = left;
            left = left * nums[i];
        }
        int right = 1;
        for (int i = length - 1; i >= 0; i--){
            result[i] = result[i] * right;
            right = right * nums[i];
        }
        return result;
    }
}

657. 机器人能否返回原点

class Solution {
    public boolean judgeCircle(String moves) {
        int j = 0;
        int k = 0;
        for (int i = 0; i < moves.length(); i++){
            char c = moves.charAt(i);
            if (c == 'R') {
                j++;
            } else if (c == 'L') {
                j--;
            } else if (c == 'U') {
                k++;
            } else {
                k--;
            }
        }
        return j == 0 && k == 0;
    }
}

面试题61. 扑克牌中的顺子

class Solution {
    public boolean isStraight(int[] nums) {
       
        int maxValue = Integer.MIN_VALUE;
        int minValue = Integer.MAX_VALUE;
        HashSet<Integer> hashSet = new HashSet<>();
        for (int i = 0; i < nums.length; i++){
            if (nums[i] == 0) continue;
            if (maxValue < nums[i]) {
                maxValue = nums[i];
            } 
            if (minValue > nums[i]) {
                minValue = nums[i];
            }
            if (hashSet.contains(nums[i])) return false;
            hashSet.add(nums[i]);
        }
        // System.out.println(maxValue + " " + minValue);
        return maxValue - minValue < 5;
    }
}

class Solution {
    public boolean isStraight(int[] nums) {
        Arrays.sort(nums);
        int zeroIndex = 0; 
        for (int i = 0; i < nums.length - 1; i++){
            if (nums[i] == 0) {
                zeroIndex++;
                continue;
            }
            if (nums[i] == nums[i + 1]) return false;
        }
        // System.out.println(nums[nums.length - 1] + " " + nums[zeroIndex]);
        return nums[nums.length -1] - nums[zeroIndex] < 5; 
    }
}

48. 旋转图像

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        int[][] result = new int[n][n];
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                result[j][n - 1 - i] = matrix[i][j];
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = result[i][j];
            }
        }
        
    }
}

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        //对角线转置
        for (int i = 0; i < n; i++) {
            int index = i;
            while (index < n) {
                int temp = matrix[i][index];
                matrix[i][index] = matrix[index][i];
                matrix[index][i] = temp;
                index++;
            }
        }
        //镜像交换
        for (int i = 0; i < n; i++) {
            int left = 0;
            int right = n - 1;
            while (left < right) {
                int temp = matrix[i][left];
                matrix[i][left] = matrix[i][right];
                matrix[i][right] = temp;
                left++;
                right--;
            }
        }

    }
}

54. 螺旋矩阵

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix == null || matrix.length == 0) return result;
        int left = 0;
        int right = matrix[0].length - 1;
        int up = 0;
        int down = matrix.length - 1;
        while (true) {
            for (int col = left; col <= right; col++) {
                result.add(matrix[up][col]);
            }
            if (++up > down) {
                break;
            }
            for (int row = up; row <= down; row++) {
                result.add(matrix[row][right]);
            }
            
            if (--right < left) {
                break;
            }

            for (int col = right; col >= left; col--) {
                result.add(matrix[down][col]);
            }
            if (--down < up) {
                break;
            }
            for (int row = down; row >= up; row--) {
                result.add(matrix[row][left]);
            }
            if (++left > right) {
                break;
            }
        }
        return result;
    }
}

59. 螺旋矩阵 II

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] result = new int[n][n];
        int left = 0;
        int right = n - 1;
        int up = 0;
        int down = n - 1;
        int index = 1;
        while (true) {
            for (int col = left; col <= right; col++) {
                // System.out.println(col);
                result[up][col] = index++;
            }
            if (++up > down) break;
            for (int row = up; row <= down; row++) {
                result[row][right] = index++;
            }
            if (--right < left) break;
            for (int col = right; col >= left; col--) {
                result[down][col] = index++;
            }
            if (--down < up) break;
            for (int row = down; row >= up; row--) {
                result[row][left] = index++;
            }
            if (++left > right)break;
        }
        return result;
    }
}

73. 矩阵置零

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean[] cols = new boolean[n];
        boolean[] rows = new boolean[m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    rows[i] = true;
                    cols[j] = true;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (cols[j] || rows[i]) matrix[i][j] = 0;
            }
        }
    }
}

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean col = false;
        boolean row = false;
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                col = true;
                break;
            }
        }
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                row = true;
                break;
            }
        }
        //扫描标记
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
            }
        }

        if (col) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
        if (row) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }

    }
}

36. 有效的数独

class Solution {
    public boolean isValidSudoku(char[][] board) {
        boolean[][] rows = new boolean[9][9];
        boolean[][] cols = new boolean[9][9];
        boolean[][] grids = new boolean[9][9];
        for (int i = 0; i < 9; i++){
            for (int j = 0; j < 9; j++){
                char c = board[i][j];
                if (c != '.') {
                    int index = c - '1';
                    int gridIndex = i / 3 * 3 + j / 3;
                    if (rows[i][index] || cols[j][index] || grids[gridIndex][index]) {
                        return false;
                    } else {
                        rows[i][index] = true;
                        cols[j][index] = true;
                        grids[gridIndex][index] = true;
                    }
                }
                
            }
        }
        return true;
    }
}

class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[][] rows = new int[9][9];
        int[][] cols = new int[9][9];
        int[][][] grids = new int[3][3][9];
        for (int i = 0; i < 9; i++){
            for (int j = 0; j < 9; j++){
                char c = board[i][j];
                if (c != '.') {
                    int index = c - '1';
                    rows[i][index]++;
                    cols[j][index]++;
                    grids[i / 3][j / 3][index]++;
                    if (rows[i][index] > 1 || cols[j][index] > 1 || grids[i / 3][j / 3][index] > 1) return false;
                }
            }
        }
        return true;
    }
}

289. 生命游戏

class Solution {
    public void gameOfLife(int[][] board) {
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                //统计四周活细胞数量
                int count = 0;
                for (int k = -1; k <= 1; k++){
                    for (int g = -1; g <= 1; g++){
                        int ii = i + k;
                        int jj = j + g;
                        if (ii == i && jj == j) continue;
                        if ((ii >= 0 && ii < m) && (jj >= 0 && jj < n) && Math.abs(board[ii][jj]) == 1) count++;
                    }
                }
                if (board[i][j] == 1 && (count < 2 || count > 3)) board[i][j] = -1;
                if (board[i][j] == 0 && count == 3) board[i][j] = 2; 
            }
        }
        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                if (board[i][j] == -1) board[i][j] = 0;
                else if (board[i][j] == 2) board[i][j] = 1;
            }
        }
    }
}

419. 甲板上的战舰

class Solution {
    public int countBattleships(char[][] board) {
        int m = board.length;
        int n = board[0].length;
        int result = 0;
        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                if (board[i][j] == 'X') {
                    if (i > 0 && board[i - 1][j] == 'X') continue;
                    if (j > 0 && board[i][j - 1] == 'X') continue;
                    result++;
                }
            }
        }
        return result;
    }
}

463. 岛屿的周长

class Solution {
    public int islandPerimeter(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int result = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    result += 4;
                    if (i > 0 && grid[i - 1][j] == 1) result -= 2;
                    if (j > 0 && grid[i][j - 1] == 1) result -= 2;
                }
            }
        }
        return result;
    }
}

498. 对角线遍历

class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int i = 0;
        int j = 0;
        int index = 0;
        int[] result = new int[m * n];
        //右上角
        int dir = 1;
        while (index < m * n) {
            result[index++] = mat[i][j];
            int ni = i;
            int nj = j;
            if (dir == 1) {
                ni = i - 1;
                nj = j + 1;
            } else {
                ni = i + 1;
                nj = j - 1;
            }
            //超过边界处理
            if (index < m * n && (ni < 0 || ni >= m || nj < 0 || nj >= n)) {
                if (dir == 1) {
                    ni = j + 1 < n ? i : i + 1;
                    nj = j + 1 < n ? j + 1 : j;
                } else {
                    ni = i + 1 < m ? i + 1 : i;
                    nj = i + 1 < m ? j : j + 1;
                }
                
                dir = dir == 1 ? -1 : 1;
            }
            i = ni;
            j = nj;
        }
        return result;
    }
}

48. 旋转图像

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        //水平反转
        for (int i = 0; i < n / 2; i++) {
            for (int j = 0; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - i][j];
                matrix[n - 1 - i][j] = temp;
            }
        }
        //主对角线
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }
}