我的算法刷题笔记(3.18-3.22)

我的算法刷题笔记(3.18-3.22)

    • 1. 螺旋矩阵
        • 1. total是总共走的步数
        • 2. int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};方位
        • 3. visited[row][column] = true;用于判断是否走完一圈
    • 2. 生命游戏
        • 1. 使用额外的状态2
        • 2. 再复制一份数组
    • 3. 旋转图像
        • 观察规律,只需四分之一
    • 4. 矩阵置零
        • 1. 用第一列存储状态,但是需要从后往前
    • 5. 有效的括号
        • 1. Map存储 put('{','}'); put('[',']'); put('(',')'); put('?','?')
    • 6. 二叉树的中序遍历
    • 7. 移掉 K 位数字
        • 用12345 54321 15324 作为找规律
    • 8. 去除重复字母
        • 先拼接到答案,看后面逻辑是否回删
        • 如何遇到重复,那么跳过即可
    • 9. 字符串中的第一个唯一字符
    • 10. 最近的请求次数
    • 11. 数组中的第K个最大元素
        • 1. 小根堆创建
        • 前k个入队列,然后与剩下的对比
    • 12. 查找和最小的 K 对数字
        • 堆中的第一个元素一定是答案
    • 13. 丑数Ⅱ
    • 14. 删除有序数组中的重复项
    • 15.下一个排列
    • 16. 合并两个有序数组
    • 17. 轮转数组
    • 18. 比较版本号
    • 19. 验证回文串
    • 20. 重复的DNA序列
    • 21. 找到 K 个最接近的元素
    • 22. 两数相加
    • 23. 旋转链表
    • 24. 删除排序链表中的重复元素 II
    • 25. 反转链表 II
    • 26. 两两交换链表中的节点
    • 27. 重排链表
    • 28. 相交链表
    • 29. 存在重复元素 II

1. 螺旋矩阵

原题链接

1. total是总共走的步数
2. int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};方位
3. visited[row][column] = true;用于判断是否走完一圈
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> order = new ArrayList<Integer>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return order;
        }
        int rows = matrix.length, columns = matrix[0].length;
        boolean[][] visited = new boolean[rows][columns];
        int total = rows * columns;
        int row = 0, column = 0;
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int directionIndex = 0;
        for (int i = 0; i < total; i++) {
            order.add(matrix[row][column]);
            visited[row][column] = true;
            int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
            if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) {
                directionIndex = (directionIndex + 1) % 4;
            }
            row += directions[directionIndex][0];
            column += directions[directionIndex][1];
        }
        return order;
    }
}

2. 生命游戏

原题链接

1. 使用额外的状态2
class Solution {
    public void gameOfLife(int[][] board) {
        int[] neighbors = {0, 1, -1};

        int rows = board.length;
        int cols = board[0].length;

        // 遍历面板每一个格子里的细胞
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {

                // 对于每一个细胞统计其八个相邻位置里的活细胞数量
                int liveNeighbors = 0;

                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {

                        if (!(neighbors[i] == 0 && neighbors[j] == 0)) {
                            // 相邻位置的坐标
                            int r = (row + neighbors[i]);
                            int c = (col + neighbors[j]);

                            // 查看相邻的细胞是否是活细胞
                            if ((r < rows && r >= 0) && (c < cols && c >= 0) && (Math.abs(board[r][c]) == 1)) {
                                liveNeighbors += 1;
                            }
                        }
                    }
                }

                // 规则 1 或规则 3 
                if ((board[row][col] == 1) && (liveNeighbors < 2 || liveNeighbors > 3)) {
                    // -1 代表这个细胞过去是活的现在死了
                    board[row][col] = -1;
                }
                // 规则 4
                if (board[row][col] == 0 && liveNeighbors == 3) {
                    // 2 代表这个细胞过去是死的现在活了
                    board[row][col] = 2;
                }
            }
        }

        // 遍历 board 得到一次更新后的状态
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (board[row][col] > 0) {
                    board[row][col] = 1;
                } else {
                    board[row][col] = 0;
                }
            }
        }
    }
}

作者:力扣官方题解
链接:https://leetcode.cn/problems/game-of-life/solutions/179750/sheng-ming-you-xi-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
2. 再复制一份数组
class Solution {
    public void gameOfLife(int[][] board) {
        int[] neighbors = {0, 1, -1};

        int rows = board.length;
        int cols = board[0].length;

        // 创建复制数组 copyBoard
        int[][] copyBoard = new int[rows][cols];

        // 从原数组复制一份到 copyBoard 中
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                copyBoard[row][col] = board[row][col];
            }
        }

        // 遍历面板每一个格子里的细胞
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {

                // 对于每一个细胞统计其八个相邻位置里的活细胞数量
                int liveNeighbors = 0;

                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {

                        if (!(neighbors[i] == 0 && neighbors[j] == 0)) {
                            int r = (row + neighbors[i]);
                            int c = (col + neighbors[j]);

                            // 查看相邻的细胞是否是活细胞
                            if ((r < rows && r >= 0) && (c < cols && c >= 0) && (copyBoard[r][c] == 1)) {
                                liveNeighbors += 1;
                            }
                        }
                    }
                }

                // 规则 1 或规则 3      
                if ((copyBoard[row][col] == 1) && (liveNeighbors < 2 || liveNeighbors > 3)) {
                    board[row][col] = 0;
                }
                // 规则 4
                if (copyBoard[row][col] == 0 && liveNeighbors == 3) {
                    board[row][col] = 1;
                }
            }
        }
    }
}

3. 旋转图像

原题链接

观察规律,只需四分之一
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 + 1) / 2; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = temp;
            }
        }
    }
}

4. 矩阵置零

1. 用第一列存储状态,但是需要从后往前

原题链接

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean flagCol0 = false;
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                flagCol0 = true;
            }
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        for (int i = m - 1; i >= 0; i--) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
            if (flagCol0) {
                matrix[i][0] = 0;
            }
        }
    }
}

5. 有效的括号

1. Map存储 put(‘{’,‘}’); put(‘[’,‘]’); put(‘(’,‘)’); put(‘?’,‘?’)

原题链接

class Solution {
    private static final Map<Character,Character> map = new HashMap<Character,Character>(){{
        put('{','}'); put('[',']'); put('(',')'); 
    }};
    public boolean isValid(String s) {
        if(s.length() > 0 && !map.containsKey(s.charAt(0))) return false;
        Stack<Character> stack = new Stack<Character>(){};
        for(Character c : s.toCharArray()){
            if(map.containsKey(c)) stack.add(c);
            else if(stack.isEmpty() == true || map.get(stack.pop()) != c) return false;
        }
        return stack.size() == 0;
    }
}

6. 二叉树的中序遍历

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }

    public void inorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }
}

7. 移掉 K 位数字

用12345 54321 15324 作为找规律

原题链接


class Solution {
class Solution {
    public String removeKdigits(String num, int k) {
        Deque<Character> stk = new ArrayDeque<>();
        for (char c : num.toCharArray()) {
            while (!stk.isEmpty() && c < stk.getLast() && k > 0) {
                stk.pollLast();
                k--;
            }
            stk.addLast(c);
        }
        String res = stk.stream().map(Object::toString).collect(Collectors.joining());
        res = res.substring(0, res.
上一篇:界面组件Telerik UI for Winforms 2024 Q1新版亮点 - 全新的Win 11主题


下一篇:【C语言】指针基础-1. 指针的概念