leetcode刷题记录——2024年2月-能不能吃完饭再说

2641、二叉树的堂兄弟节点 Ⅱ——哈希表、层序遍历

使用队列进行层序遍历，sameparent记录每个节点的兄弟节点的值，同时sum用于存储当前遍历层的下一层节点总和。当遍历到下一层时，每个节点的val等于sum-兄弟节点的val。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution
{
public:
    TreeNode *replaceValueInTree(TreeNode *root)
    {
        unordered_map<TreeNode *, int> sameparent;
        queue<TreeNode *> q;
        q.push(root);
        sameparent[root] = 0;
        int sum = root->val;
        while (!q.empty())
        {
            int level_size = q.size();
            int tmp = sum;
            sum = 0;
            for (size_t i = 0; i < level_size; i++)
            {
                TreeNode *cur = q.front();
                cur->val = tmp - cur->val - sameparent[cur];

                if (cur->left)
                {
                    q.push(cur->left);
                    sameparent[cur->left] = cur->right ? cur->right->val : 0;
                    sum += cur->left->val;
                }
                if (cur->right)
                {
                    q.push(cur->right);
                    sameparent[cur->right] = cur->left ? cur->left->val : 0;
                    sum += cur->right->val;
                }
                q.pop();
            }
        }
        return root;
    }
};

993、二叉树的堂兄弟节点——层序遍历

略

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isCousins(TreeNode* root, int x, int y) {
        queue<TreeNode *> q;
        q.push(root);
        while(!q.empty()){
            int level_size = q.size();
            unordered_map<int, int> mp;
            for(int i=0;i<level_size;i++){
                TreeNode *cur = q.front();
                if(cur != nullptr){
                    mp[cur->val] = i;
                    q.push(cur->left);
                    q.push(cur->right);
                }
                q.pop();
            }
            if(mp.find(x)!=mp.end() && mp.find(y)!=mp.end()){
                int min_idx = min(mp[x], mp[y]);
                if(abs(mp[x]-mp[y]) != 1 || min_idx%2 == 1){
                    return true;
                }
            }
        }
        return false;
    }
};

LCR 125、图书整理Ⅱ——栈、队列

直接用队列

class CQueue
{
private:
    list<int> books;

public:
    CQueue()
    {
    }

    void appendTail(int value)
    {
        books.push_back(value);
    }

    int deleteHead()
    {
        if (books.empty())
        {
            return -1;
        }
        int ret = books.front();
        books.pop_front();
        return ret;
    }
};

用两个栈模拟队列

class CQueue
{
private:
    stack<int> r_books;
    stack<int> l_books;

public:
    CQueue()
    {
    }

    void appendTail(int value)
    {
        r_books.push(value);
    }

    int deleteHead()
    {
        if (l_books.empty())
        {
            if (r_books.empty())
            {
                return -1;
            }
            while (!r_books.empty())
            {
                l_books.push(r_books.top());
                r_books.pop();
            }
        }
        int ret = l_books.top();
        l_books.pop();
        return ret;
    }
};

LCR 126、斐波那契数列——动态规划

动态规划

class Solution
{
public:
    int fib(int n)
    {
        if (n == 0)
        {
            return 0;
        }
        vector<int> dp(2);
        dp[0] = 0;
        dp[1] = 1;
        int tmp = 0;
        for (size_t i = 2; i <= n; i++)
        {
            tmp = (dp[0] + dp[1]) % 1000000007;
            dp[0] = dp[1];
            dp[1] = tmp;
        }
        return dp[1];
    }
};

LCR 120、寻找文件副本——哈希表

略

class Solution
{
public:
    int findRepeatDocument(vector<int> &documents)
    {
        unordered_set<int> doc_set;
        for (size_t i = 0; i < documents.size(); i++)
        {
            if (doc_set.find(documents[i]) != doc_set.end())
            {
                return documents[i];
            }
            doc_set.insert(documents[i]);
        }
        return -1;
    }
};

LCR 121、寻找目标值——二分查找

先缩小范围，再来遍历，比直接遍历效率提高了一些

class Solution
{
public:
    bool findTargetIn2DPlants(vector<vector<int>> &plants, int target)
    {
        int h = plants.size();
        if (h == 0)
        {
            return false;
        }
        int w = plants[0].size();
        if (w == 0)
        {
            return false;
        }
        int h_end = h;
        int w_end = upper_bound(plants[0].begin(), plants[0].end(), target) - plants[0].begin();
        for (size_t i = 0; i < h; i++)
        {
            if (plants[i][0] > target)
            {
                h_end = i;
                break;
            }
        }
        for (size_t i = 0; i < h_end; i++)
        {
            for (size_t j = 0; j < w_end; j++)
            {
                if (plants[i][j] == target)
                {
                    return true;
                }
            }
        }
        return false;
    }
};

优化

将矩阵逆时针旋转 45° ，并将其转化为图形式，发现其类似于二叉搜索树，即对于每个元素，其左分支元素更小、右分支元素更大。

class Solution
{
public:
    bool findTargetIn2DPlants(vector<vector<int>> &plants, int target)
    {
        int h = plants.size();
        if (h == 0)
        {
            return false;
        }
        int w = plants[0].size();
        if (w == 0)
        {
            return false;
        }
        int m = 0, n = w - 1;
        while (m < h && n >= 0)
        {
            if (target > plants[m][n])
            {
                m++;
            }
            else if (target < plants[m][n])
            {
                n--;
            }
            else
            {
                return true;
            }
        }

        return false;
    }
};

LCR 128、库存管理Ⅰ——二分查找

三种情况，右边有序（mid<right，缩小右边范围）、右边无序（mid>right，缩小左边范围）、无法确定（mid==right，两种情况，1、右边无序情况：mid在左边开头处，right在右边末尾；2、右边有序情况：mid和right都在右边。小范围移动right）。

class Solution
{
public:
    int stockManagement(vector<int> &stock)
    {
        int low = 0;
        int high = stock.size() - 1;
        while (low < high)
        {
            int pivot = low + (high - low) / 2;
            // 右边有序
            if (stock[pivot] < stock[high])
            {
                high = pivot;
            }
            // 右边无序
            else if (stock[pivot] > stock[high])
            {
                low = pivot + 1;
            }
            else
            {
                high -= 1;
            }
        }
        return stock[low];
    }
};

LCR 129、字母迷宫——深度优先搜索、Java

遍历网格中的每个字符，并将其与目标单词的第一个字符进行比较。如果匹配成功，则调用 dfs 方法进行深度优先搜索，尝试在相邻的字符中继续匹配下一个字符。

dfs 方法递归地进行搜索。它首先检查递归终止条件，即匹配到了目标单词的最后一个字符，如果是，则返回 true 表示找到了目标单词。然后，它检查当前位置是否越界、已经访问过、或者与目标单词的当前字符不匹配，如果是，则返回 false 表示无法继续匹配。

如果当前位置是一个合法且匹配的字符，那么将其标记为已访问，并递归地尝试在相邻的字符中继续匹配下一个字符。如果在任意一个方向上找到了目标单词，则返回 true 表示成功找到。在递归返回之前，还需要将当前位置的访问状态恢复，并继续在其他方向上进行搜索。

最终，如果在整个网格中都无法找到目标单词的匹配，则返回 false。

class Solution {
    public boolean wordPuzzle(char[][] grid, String target) {
        int height = grid.length;
        int width = grid[0].length;
        boolean[][] visited = new boolean[height][width];
        for(int i = 0; i < height; i++){
            for(int j = 0; j < width; j++){
                if(grid[i][j] == target.charAt(0)){
                    if(dfs(target, 0, grid, i, j, height, width, visited)){
                        return true;
                    }
                }
            }
        }
        return false;
    }

    boolean dfs(String target, int index, char[][] grid, int m, int n, int h, int w, boolean[][] visited){
        if(index == target.length()){
            return true;
        }
        if(m < 0 || n < 0|| m >= h || n >= w || visited[m][n] || grid[m][n] != target.charAt(index)){
            return false;
        }else{
            visited[m][n] = true;
            boolean upper = dfs(target, index + 1, grid, m + 1, n, h, w, visited);
            if (upper) {
                visited[m][n] = false;
                return true;
            }
            boolean left = dfs(target, index + 1, grid, m, n + 1, h, w, visited);
            if (left) {
                visited[m][n] = false;
                return true;
            }
            boolean lower = dfs(target, index + 1, grid, m - 1, n, h, w, visited);
            if (lower) {
                visited[m][n] = false;
                return true;
            }
            boolean right = dfs(target, index + 1, grid, m, n - 1, h, w, visited);
            visited[m][n] = false;
            return upper || left || lower || right;
        }
    }
}

LCR 122、路径加密——Java

略

class Solution {
    public String pathEncryption(String path) {
        String result = "";
        for(int i=0;i<path.length();++i){
            if(path.charAt(i) == '.'){
                result += ' ';
            }else{
                result += path.charAt(i);
            }
        }
        return result;
    }
}

LCR 130、衣橱整理——深度优先搜索、Java

每次从队列中取出一个格子，并获取其坐标（curM、curN）。然后，分别判断向下移动和向右移动的格子是否满足以下条件：1）未越界；2）衣物上的数字之和不超过给定的 cnt；3）未访问过。如果满足条件，将该格子加入队列，并标记为已访问，同时将结果数量加一。

最终，循环结束后，返回结果数量，即为能放入袋子的衣物数量。

class Solution {
    public int wardrobeFinishing(int m, int n, int cnt) {
        int result = 1;
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.add(new int[]{0, 0});
        boolean[][] visited = new boolean[m][n];
        visited[0][0] = true;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int curM = cur[0], curN = cur[1];
            if (curM + 1 < m && get(curM + 1) + get(curN) <= cnt && !visited[curM + 1][curN]) {
                queue.add(new int[]{curM + 1, curN});
                visited[curM + 1][curN] = true;
                result++;
            }
            if (curN + 1 < n && get(curM) + get(curN + 1) <= cnt && !visited[curM][curN + 1]) {
                queue.add(new int[]{curM, curN + 1});
                visited[curM][curN + 1] = true;
                result++;
            }
        }
        return result;
    }

    private int get(int x) {
        int res = 0;
        while (x != 0) {
            res += x % 10;
            x /= 10;
        }
        return res;
    }
}

LCR 123、图书整理Ⅰ——Java

略

class Solution {
    public int[] reverseBookList(ListNode head) {
        ListNode cur = head;
        ArrayList<Integer> list = new ArrayList<>();
        while (cur != null) {
            list.add(cur.val);
            cur = cur.next;
        }
        Collections.reverse(list);
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}

LCR 124、推理二叉树——Java、递归

首先，检查前序遍历数组的长度，如果为 0，说明当前子树为空，直接返回 null。
创建一个新的 TreeNode 对象 tree，其值为前序遍历数组的第一个元素 preorder[0]。
在中序遍历数组 inorder 中找到 preorder[0] 的索引 index，以确定左子树和右子树的范围。
使用 Arrays.copyOfRange 方法，将前序遍历数组和中序遍历数组切分为左子树和右子树的子数组。
递归调用 deduceTree 方法，传入左子树的前序和中序遍历数组，将返回的结果赋值给 tree 的左子树。
递归调用 deduceTree 方法，传入右子树的前序和中序遍历数组，将返回的结果赋值给 tree 的右子树。
最后，返回构造好的二叉树 tree。

class Solution {
    public TreeNode deduceTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0){
            return null;
        }
        TreeNode tree = new TreeNode(preorder[0]);
        int index = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == preorder[0]) {
                index = i;
                break;
            }
        }
        tree.left = deduceTree(Arrays.copyOfRange(preorder, 1, 1 + index),
                Arrays.copyOfRange(inorder, 0, index));
        tree.right = deduceTree(Arrays.copyOfRange(preorder, 1 + index, preorder.length),
                Arrays.copyOfRange(inorder, index + 1, inorder.length));
        return tree;
    }
}

LCR 131、砍竹子——Java、数学、动态规划

动态规划的思路很简单，主要在于推导为什么dp计算只计算之前三个状态。

根据算术几何均值不等式，将竹子 以相等的长度等分为多段 ，得到的乘积最大。将竹子按照x长度划分为n段，总长度为l=nx，乘积为x^n，n=l/x，则x^n=x^(l/x)，所以当x^(1/x)取得最大值时，乘积达到最大值。求导易得驻点为

class Solution {
    public int cuttingBamboo(int bamboo_len) {
        int[] dp = new int[bamboo_len + 1];
        int tmp = 0;
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i < bamboo_len + 1; i++) {
            dp[i] = Math.max(dp[i - 1], i - 1);
            tmp = Math.max(dp[i - 2] * 2, 2 * i - 4);
            dp[i] = Math.max(dp[i], tmp);
            tmp = Math.max(dp[i - 3] * 3, 3 * i - 9);
            dp[i] = Math.max(dp[i], tmp);
        }
        return dp[bamboo_len];
    }
}

基于上面的分析，可以稍微简化一下

class Solution {
    public int cuttingBamboo(int n) {
        if(n < 3) {return 1;}
        if(n == 3) {return 2;}
        int res = 1;
        while(n > 4) {
            res *= 3;
            n -= 3;
        }
        return n * res;
    }
}

LCR 132、砍竹子Ⅱ——Java、数学、贪心

循环取余

class Solution {
    public int cuttingBamboo(int n) {
        if(n < 3) {return 1;}
        if(n == 3) {return 2;}
        long res = 1;
        while(n > 4) {
            res *= 3;
            res %= 1000000007;
            n -= 3;
        }
        return (int)(n * res % 1000000007);
    }
}

987、二叉树的垂序遍历——深度优先搜索、哈希表、Java

在先序遍历的过程中，使用两个字典 map 和 nodeIndex 进行节点的索引和记录。

在 preOrderTravel 方法中，首先判断当前节点 root 是否为空，如果为空则直接返回。

然后，在遍历过程中，记录每个节点的行号和列号，并将节点添加到 map 字典中以列号为键，将节点列表存储为值。如果当前列号比 minCol 小，则更新 minCol。

同时，将节点 root 和对应的行号和列号组成的列表存储到 nodeIndex 字典中，以节点为键，行号和列号组成的列表为值。

遍历完二叉树后，map 中存储了按列号分组的节点列表，nodeIndex 中存储了每个节点对应的行号和列号。

接下来，根据 map 中的键值对进行遍历，对每个节点列表进行排序。排序的规则是首先根据节点的列号升序排序，如果列号相同，则根据行号升序排序。如果行号和列号都相同，则根据节点的值升序排序。

在排序后，创建一个新的列表 result，根据 map 的大小初始化 result 的大小，并将每个节点列表中的节点值按顺序添加到对应的位置。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private Map<Integer, List<TreeNode>> map = new HashMap<>();
    private Map<TreeNode, List<Integer>> nodeIndex = new HashMap<>();
    private int minCol;
    public void preOrderTravel(TreeNode root, int row, int col){
        if(root == null) {
            return;
        }
        if(col < minCol){
            minCol = col;
        }
        List<TreeNode> list = map.get(col);
        if(list == null){
            list = new ArrayList<>();
            list.add(root);
            map.put(col, list);
        }else{
            list.add(root);
        }
        nodeIndex.put(root, Arrays.asList(row, col));
        preOrderTravel(root.left, row+1, col-1);
        preOrderTravel(root.right, row+1, col+1);
    }

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        preOrderTravel(root, 0, 0);
        List<List<Integer>> result = new ArrayList<>(map.size());
        for (int i = 0; i < map.size(); i++) {
            result.add(new ArrayList<>());
        }
        map.forEach((k,v)->{
            Collections.sort(v, (o1, o2) -> {
                List<Integer> pair1 = nodeIndex.get(o1);
                List<Integer> pair2 = nodeIndex.get(o2);
                int ret =  pair1.get(1) - pair2.get(1) == 0 ? pair1.get(0) - pair2.get(0) : pair1.get(1) - pair2.get(1);
                if(ret == 0){
                    return o1.val - o2.val;
                }
                return ret;
            });
            List<Integer> tmp = new ArrayList<>();
            // 将v所有TreeNode的val放入tmp
            for (TreeNode node: v) {
                tmp.add(node.val);
            }
            result.set(k - minCol, tmp);
        });
        return result;
    }
}

107、二叉树的层序遍历——Java、队列、双向链表

跟普通层序遍历一样，只不过每一层遍历结果直接加入链表头部

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> result = new LinkedList<>();
        if (root == null) {
            return result;
        }
        queue.add(root);
        int levelSize = 0;
        while (!queue.isEmpty()) {
            levelSize = queue.size();
            List<Integer> level = new LinkedList<>();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            result.addFirst(level);
        }
        return result;
    }
}

LCR 142、训练计划Ⅳ——链表、Java

合并两个有序链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode trainningPlan(ListNode l1, ListNode l2) {
        ListNode result = new ListNode();
        ListNode cur = result;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        if (l1 != null) {
            cur.next = l1;
        } else if (l2 != null) {
            cur.next = l2;
        }
        return result.next;
    }
}

LR 143、子结构判断——Java、DFS

subStruct，用于判断以节点A为根的子树是否包含树B的结构。方法的返回值为布尔类型。

如果B为空，表示B的部分结构在A中已经匹配完成，返回true。
如果A为空，表示A的节点已经遍历完，但B中的节点还没有完全匹配，返回false。
如果A节点的值等于B节点的值，分别判断A的左子树和B的左子树、A的右子树和B的右子树是否匹配。如果都匹配，返回true；否则，返回false。
如果A节点的值不等于B节点的值，返回false。

dfs，用于进行深度优先搜索遍历A的所有节点。（找到A中与B的根相等的节点进行判断）

如果A为空，表示已经遍历完了，直接返回。
如果A节点的值等于B节点的值，调用 subStruct 方法判断以A为根的子树是否包含B的结构。如果是，将 result 设置为true。
递归遍历A的左子树和右子树。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private boolean result;

    private boolean subStruct(TreeNode A, TreeNode B) {
        if (B == null) {
            return true;
        }
        if (A == null) {
            return false;
        }
        boolean left = false;
        boolean right = false;
        if (A.val == B.val) {
            left = subStruct(A.left, B.left);
            right = subStruct(A.right, B.right);
            return left && right;
        } else {
            return false;
        }
    }

    private void dfs(TreeNode A, TreeNode B) {
        if (A == null) {
            return;
        }
        if (A.val == B.val) {
            result = subStruct(A, B);
        }
        dfs(A.left, B);
        dfs(A.right, B);
    }

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (B == null) {
            return false;
        }
        dfs(A, B);
        return result;
    }
}

103、二叉树的锯齿形层序遍历——Java

cnt为奇数每次加在LinkedList头部，否则加在尾部

// @lc code=start
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) {
            return res;
        }
        queue.add(root);
        int cnt = 0;
        int levelSize = 0;
        while (!queue.isEmpty()) {
            List<Integer> tmp = new LinkedList<>();
            levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                if (cnt % 2 == 0) {
                    tmp.add(node.val);
                } else {
                    tmp.addFirst(node.val);
                }
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            cnt++;
            res.add(tmp);
        }
        return res;
    }
}

226、翻转二叉树——Java、递归

递归让左边等于右边，右边等于左边

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        TreeNode right = mirrorTree(root.left);
        TreeNode left = mirrorTree(root.right);
        root.right = right;
        root.left = left;
        return root;
    }
}

LCR 145、判断对称二叉树——Java、递归

同步移动两个指针来遍历这棵树，p 指针和 q 指针一开始都指向这棵树的根，随后 p 右移时，q 左移，p 左移时，q 右移。每次检查当前 p 和 q 节点的值是否相等，如果相等再判断左右子树是否对称。

class Solution {
    public boolean checkSymmetricTree(TreeNode root) {
        return check(root, root);
    }

    public boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
    }
}

LCR 138、有效数组——作弊写法、正则

\\s*: 匹配零个或多个空格。
[+-]?: 匹配零个或一个正负号。
(\\d+\\.?|\\.\\d+|\\d+\\.\\d+): 这是小数的匹配部分，分为三种情况：
- \\d+\\.?: 匹配至少一位数字，后面可跟一个点（整数部分）。
- \\.\\d+: 匹配一个点，后面至少跟一位数字（小数部分）。
- \\d+\\.\\d+: 匹配至少一位数字，后面跟一个点，再跟至少一位数字（整数部分和小数部分）。
([eE][+-]?\\d+)?: 这是指数的匹配部分，包含一个 'e' 或 'E'，后面可跟一个正负号，再跟至少一位数字。这部分是可选的，所以用 ? 表示。
\\s*: 匹配零个或多个空格，以结束整个字符串。

class Solution {
    public boolean validNumber(String s) {
        String pattern = "\\s*[+-]?(\\d+\\.?|\\.\\d+|\\d+\\.\\d+)([eE][+-]?\\d+)?\\s*";
        return s.matches(pattern);
    }
}

429、N叉树的层序遍历——Java、BFS

跟普通的层序遍历差不多

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        Queue<Node> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        queue.add(root);
        int levelSize = 0;
        while (!queue.isEmpty()) {
            levelSize = queue.size();
            Node node = null;
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < levelSize; i++) {
                node = queue.poll();
                level.add(node.val);
                for (int j = 0; j < node.children.size(); j++) {
                    queue.add(node.children.get(j));
                }
            }
            res.add(level);
        }
        return res;
    }
}

LCR 139、训练计划Ⅰ——双指针、Java

慢指针指向最前面的偶数，快指针寻找第一个奇数，找到后交换位置，然后移动慢指针。

class Solution {
    public int[] trainingPlan(int[] actions) {
        int fast = 0, slow = 0;
        while (fast < actions.length) {
            if (actions[fast] % 2 == 1) {
                int tmp = actions[fast];
                actions[fast] = actions[slow];
                actions[slow] = tmp;
                slow++;
            }
            fast++;
        }
        return actions;
    }
}

LCR 133、位1的个数——Java、位运算

最基础的位运算

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            if ((n & 1) == 1) {
                result++;
            }
            n = n >> 1;
        }
        return result;
    }
}

43、字符串相乘——Java、模拟

在乘法过程中，将每一位的乘积结果存储在result数组中，每一位乘积的有效非零数字最多两个，因此可以得到高位和低位的索引，同时处理进位。最后，构建乘积字符串。

class Solution {
    public String multiply(String num1, String num2) {
        int m = num1.length();
        int n = num2.length();
        // 保存每位相乘的结果
        int[] result = new int[m + n];

        // 从个位数开始逐位相乘
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                // 相乘结果
                int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                // 乘积的高位索引
                int p1 = i + j;
                // 乘积的低位索引
                int p2 = i + j + 1;

                // 加上相乘结果和原来的值
                int sum = mul + result[p2];
                // 个位数
                result[p2] = sum % 10;
                // 进位
                result[p1] += sum / 10;
            }
        }

        // 构建乘积字符串
        StringBuilder sb = new StringBuilder();
        for (int digit : result) {
            // 跳过前导0
            if (sb.length() == 0 && digit == 0) {
                continue;
            }
            sb.append(digit);
        }

        // 处理结果为0的情况
        if (sb.length() == 0) {
            return "0";
        }

        return sb.toString();
    }
}

100211、进行操作使字符串为空——Java、哈希表、LinkedHashMap

分析一下题目要求，其实就是接收一个字符串 s 作为输入，并返回字符串中具有最高频率的最后一个字符（或字符组合），同时需要保持出现顺序。

初始化一个空字符串result，用于存储最终的结果。
创建一个名为cnt的LinkedHashMap，用于存储字符串中每个字符的出现次数。
初始化一个变量max，用于跟踪最大的出现频率。
遍历输入字符串s中的每个字符。
- 如果字符已经在cnt映射中，更新其计数和max频率（需要先删除，目的是为了保证出现顺序正确）。
- 如果字符不在映射中，将其添加到映射并将计数设置为1，并更新max频率。
遍历cnt映射的条目。
- 如果字符的计数等于max频率，将该字符附加到result字符串。
返回最终的result字符串。

class Solution {
    public String lastNonEmptyString(String s) {
        String result = "";
        Map<Character, Integer> cnt = new LinkedHashMap<>();
        int max = 0;
        for(int i=0;i<s.length();i++){
            if(cnt.containsKey(s.charAt(i))){
                int tmp = cnt.get(s.charAt(i))+1;
                max = Math.max(max, tmp);
                cnt.remove(s.charAt(i));
                cnt.put(s.charAt(i), tmp);
            }else{
                cnt.put(s.charAt(i), 1);
                max = Math.max(max, 1);
            }
        }
        for(Map.Entry<Character, Integer> entry:cnt.entrySet()){
            if(entry.getValue() == max){
                result += entry.getKey();
            }
        }
        return result;
    }
}

589、N叉树的前序遍历——Java

略

class Solution {
    private List<Integer> list;

    private void func(Node root){
        if(root == null){
            return;
        }
        list.add(root.val);
        for(Node node : root.children){
            func(node);
        }
    }

    public List<Integer> preorder(Node root) {
        list = new ArrayList<>();
        func(root);
        return list;
    }
}

LCR 146、螺旋遍历二维数组——Java、模拟

top、bottom、left、right，分别表示当前螺旋遍历的上边界、下边界、左边界和右边界。

进入循环，条件是top小于等于bottom且left小于等于right。这个条件保证了当前螺旋遍历的区域是有效的。在每一次循环中，首先从左到右遍历上边界，将遍历到的元素依次存入res数组，并将cnt加1。然后将top加1，表示上边界向下收缩一行。检查top是否大于bottom，如果是，则跳出循环，因为已经遍历完成。

然后从上到下遍历右边界，将遍历到的元素依次存入res数组，并将cnt加1。然后将right减1，表示右边界向左收缩一列。检查left是否大于right，如果是，则跳出循环。

接着从右到左遍历下边界，将遍历到的元素依次存入res数组，并将cnt加1。然后将bottom减1，表示下边界向上收缩一行。

从下到上遍历左边界，将遍历到的元素依次存入res数组，并将cnt加1。然后将left加1，表示左边界向右收缩一列。

class Solution {
    public int[] spiralArray(int[][] array) {
        if (array == null || array.length == 0 || array[0].length == 0) {
            return new int[0];
        }
        int h = array.length;
        int w = array[0].length;
        int[] res = new int[h * w];
        int top = 0, bottom = h - 1, left = 0, right = w - 1;
        int cnt = 0;
        while (top <= bottom && left <= right) {
            for (int i = left; i <= right; i++) {
                res[cnt++] = array[top][i];
            }
            top++;
            if (top > bottom) {
                break;
            }
            for (int i = top; i <= bottom; i++) {
                res[cnt++] = array[i][right];
            }
            right--;
            if (left > right) {
                break;
            }
            for (int i = right; i >= left; i--) {
                res[cnt++] = array[bottom][i];
            }
            bottom--;
            for (int i = bottom; i >= top; i--) {
                res[cnt++] = array[i][left];
            }
            left++;
        }
        return res;
    }
}

LCR 140、训练计划Ⅱ——快慢指针

快指针先移动到第cnt个，然后快慢指针一起移动，快指针到末尾了即慢指针在倒数第cnt个。

class Solution {
    public ListNode trainingPlan(ListNode head, int cnt) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && cnt-- > 0) {
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

590、N叉树的后序遍历——Java

略

class Solution {
    private List<Integer> res;

    private void func(Node root) {
        if (root == null) {
            return;
        }
        for (Node node : root.children) {
            func(node);
        }
        res.add(root.val);
    }

    public List<Integer> postorder(Node root) {
        res = new ArrayList<>();
        func(root);
        return res;
    }
}

LCR 134、Pow(x, n)——递归、Java

快速幂算法通过将指数分解为二进制形式，以减少计算的次数。

接收一个底数 x 和一个长整型指数 N。
递归计算 y = quickMul(x, N / 2)，这是将指数 N 划分为两半。
根据指数 N 的奇偶性，返回 N % 2 == 0 ? y * y : y * y * x。
- 如果 N 是偶数，则返回 y * y。
- 如果 N 是奇数，则返回 y * y * x。
递归的基本情况是当 N 等于 0 时，直接返回1.0。

快速幂算法采用分治的策略，每次将指数减半，时间复杂度为 O(log N)，空间复杂度是 O(log N)。

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }

    public double quickMul(double x, long N) {
        if (N == 0) {
            return 1.0;
        }
        double y = quickMul(x, N / 2);
        return N % 2 == 0 ? y * y : y * y * x;
    }
}

LCR 137、模糊搜索验证——Java、动态规划

二维布尔数组 dp，其中 dp[i][j] 表示字符串 s 的前 i 个字符与模式 p 的前 j 个字符是否匹配。将 dp[0][0] 设置为 true，表示空字符串和空模式是匹配的。

在遍历过程中，如果模式中当前字符是 *，则存在两种情况：

匹配0次，即 dp[i][j] = dp[i][j - 2]。
如果当前字符之前的字符能够匹配当前字符串字符或为 .，表示匹配多次，则 dp[i][j] = dp[i][j] || dp[i - 1][j]。

非通配符的处理：

如果当前字符不是 *，并且当前字符串字符能够与模式字符匹配，则 dp[i][j] = dp[i - 1][j - 1]。

class Solution {
    public boolean articleMatch(String s, String p) {
        int articleLen = s.length();
        int inputLen = p.length();
        boolean[][] dp = new boolean[articleLen + 1][inputLen + 1];
        dp[0][0] = true;
        for (int i = 0; i < articleLen + 1; i++) {
            for (int j = 1; j < inputLen + 1; j++) {
                // 为通配符
                if (p.charAt(j - 1) == '*') {
                    // 至少匹配到0个
                    dp[i][j] = dp[i][j - 2];
                    if (i > 0) {
                        if (p.charAt(j - 2) == s.charAt(i - 1) || p.charAt(j - 2) == '.') {
                            dp[i][j] = dp[i][j] || dp[i - 1][j];
                        }
                    }
                    // 不为通配符
                } else if (i > 0) {
                    // 如果元素能匹配
                    if (p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '.') {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                }
            }
        }
        return dp[articleLen][inputLen];
    }
}

105、从前序与中序遍历序列构造二叉树——Java、递归

略

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    private static int findIndex(int[] array, int target) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == target) {
                return i;
            }
        }
        return -1;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0 || inorder.length == 0) {
            return null;
        } else if (preorder.length == 1) {
            return new TreeNode(preorder[0]);
        }
        TreeNode root = new TreeNode(preorder[0]);
        int index = findIndex(inorder, root.val);

        root.left = buildTree(Arrays.copyOfRange(preorder, 1, 1 + index),
                Arrays.copyOfRange(inorder, 0, index));
        root.right = buildTree(Arrays.copyOfRange(preorder, 1 + index, preorder.length),
                Arrays.copyOfRange(inorder, 1 + index, inorder.length));
        return root;
    }
}

LCR 141、训练计划Ⅲ——Java、递归

反转链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    private ListNode res;

    private ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            res = head;
            return head;
        }
        ListNode node = reverseList(head.next);
        node.next = head;
        head.next = null;
        return head;
    }

    public ListNode trainningPlan(ListNode head) {
        reverseList(head);
        return res;
    }
}

LCR 154、复杂链表的复制——Java、哈希表

nodes Map 来建立原链表节点和新链表节点之间的映射关系。这样可以通过原节点找到对应的新节点。

rands Map 的key表示旧链表的节点Node，value表示以Node对应的新节点为随机节点的新链表的节点。

在遍历过程中创建新的节点同时建立映射关系，最后遍历哈希表简历随机节点的连接即可。

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        Node dummy = new Node(0);
        Map<Node, List<Node>> rands = new HashMap<>();
        Map<Node, Node> nodes = new HashMap<>();
        Node pre = dummy;
        while (head != null) {
            Node tmp = new Node(head.val);
            pre.next = tmp;
            pre = tmp;
            // 添加新旧节点映射
            nodes.put(head, tmp);
            // 如果该节点有随机指针
            if (head.random != null) {
                if (rands.containsKey(head.random)) {
                    List<Node> randomList = rands.get(head.random);
                    randomList.add(tmp);

                } else {
                    List<Node> randomList = new ArrayList<>();
                    randomList.add(tmp);
                    rands.put(head.random, randomList);
                }

            }
            head = head.next;
        }
        Node cur = dummy.next;

        for (Map.Entry<Node, List<Node>> entry : rands.entrySet()) {
            List<Node> randomList = entry.getValue();
            Node randomNode = entry.getKey();
            for (Node node : randomList) {
                node.random = nodes.get(randomNode);
            }
        }

        return dummy.next;
    }
}

106、从中序与后序遍历序列构造二叉树——递归、Java

略

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private static int findIndex(int[] array, int target) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == target) {
                return i;
            }
        }
        return -1;
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder.length == 0){
            return null;
        }
        if(inorder.length == 1){
            return new TreeNode(inorder[0]);
        }
        int inorderLen = inorder.length;
        int postorderLen = postorder.length;
        TreeNode node = new TreeNode(postorder[postorderLen-1]);
        int index = findIndex(inorder, postorder[postorderLen-1]);
        node.left = buildTree(Arrays.copyOfRange(inorder, 0, index),
                    Arrays.copyOfRange(postorder, 0, index));
        node.right = buildTree(Arrays.copyOfRange(inorder, index+1, inorderLen),
                    Arrays.copyOfRange(postorder, index, postorderLen-1));
        return node;
    }
}

LCR 159、库存管理Ⅲ——快排、分治、Java

快速排序思路：

left、right和index，其中left和right表示待排序的数组的左右边界，index表示当前比较的元素的索引。

首先以left为基准元素indexNum，将其与right位置的元素进行比较。如果小于indexNum，则交换二者位置并以right作为下一次比较的基准位置同时将left向右移动。如果大于indexNum则只向左移动右指针。

如果以right为基准元素indexNum，将其与left位置的元素进行比较。如果大于indexNum，则交换二者位置并以left作为下一次比较的基准位置同时将right向左移动。如果大于indexNum则只向右移动左指针。

以某一基准对该数组进行左右划分后，右边的元素均大于基准元素，左边的元素均小于基准元素，继续对左右子数组进行上述步骤。

class Solution {
    private void quickSort(int left, int right, int[] stock){
        if(left >= right){
            return;
        }
        int start = left;
        int end = right;
        int index = left;
        int indexNum;
        while(left < right){
            indexNum = stock[index];
            if(index == left){
                if(stock[right] < indexNum){
                    stock[left] = stock[left] ^ stock[right];
                    stock[right] = stock[left] ^ stock[right];
                    stock[left] = stock[left] ^ stock[right];
                    index = right;
                    left++;
                }else{
                    right--;
                }
            }else if(index == right){
                if(stock[left] > indexNum){
                    stock[left] = stock[left] ^ stock[right];
                    stock[right] = stock[left] ^ stock[right];
                    stock[left] = stock[left] ^ stock[right];
                    index = left;
                    right--;
                }else{
                    left++;
                }
            }
        }
        quickSort(start, left-1, stock);
        quickSort(left+1, end, stock);
    }

    public int[] inventoryManagement(int[] stock, int cnt) {
        quickSort(0, stock.length - 1, stock);
        return Arrays.copyOfRange(stock, 0, cnt);
    }
}

LCR 147、最小栈——栈、哈希表、Java

List用来模拟栈，index存储最小元素的下标，Map用于存储某一时刻的最小元素的前一个最小元素下标，当该时刻的最小元素被移除能够恢复index。

class MinStack {
    private List<Integer> stack;
    private Map<Integer, Integer> map;
    private int size;
    private int index;

    /** initialize your data structure here. */
    public MinStack() {
        size = 0;
        index = -1;
        stack = new ArrayList<>();
        map = new HashMap<>();
    }
    
    public void push(int x) {
        stack.add(x);
        size++;
        if(index == -1 || x < stack.get(index)){
            map.put(size - 1, index);
            index = size - 1;
        }
    }
    
    public void pop() {
        if(index == size - 1){
            index = map.get(size - 1);
        }
        stack.remove(--size);
    }
    
    public int top() {
        return stack.get(size - 1);
    }
    
    public int getMin() {
        return stack.get(index);
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

------本页内容已结束，喜欢请分享------

文章作者

能不能吃完饭再说

隐私政策

PrivacyPolicy

用户协议

UseGenerator

许可协议

NC-SA 4.0

文章版权归作者所有，未经允许请勿转载。

THE END

leetcode刷题记录——2024年2月