月度归档： 2022年4月

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。

示例 1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

示例 2：

输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false

提示：

• 1 <= board.length <= 200
• 1 <= board[i].length <= 200
• board 和 word 仅由大小写英文字母组成

注意：本题与主站 79 题相同：https://leetcode-cn.com/problems/word-search/

回溯模板题了已经相当

回溯模板题了已经相当于。

1. 找一个开头匹配的
2. 往四个方向开始匹配下一个字符
3. 中途标记已经访问过的节点
4. 退出递归的时候记得要把访问过的节点标记为未访问过

class Solution {
    boolean[][] visited;

    char[][] board;

    int[][] dist = {{1,0},{-1,0},{0,1},{0,-1}};

    public boolean exist(char[][] board, String word) {
        visited = new boolean[board.length][board[0].length];
        this.board = board;

        for (int row = 0; row < board.length; row++) {
            for (int col = 0; col < board[row].length; col++) {
                if (board[row][col] == word.charAt(0) && searchWord(word,0, row, col)){
                    return true;
                }
            }
        }
        return false;
    }

    boolean searchWord(String word, int idx, int row,int col){
        if (idx == word.length()-1 && word.charAt(idx) == board[row][col]){
            return true;
        }
        if (word.charAt(idx) != board[row][col]){
            return false;
        }
        visited[row][col] = true;

        for (int[] ints : dist) {

            int x = row + ints[0];
            int y = col + ints[1];
            if ( x<0 || y<0 || x >= board.length || y >= board[0].length || visited[x][y] ){
                continue;
            }

            if (searchWord(word,idx+1,x,y)){
                return true;
            }
        }
        visited[row][col] = false;
        return false;
    }
}

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

示例 1：

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例 2：

输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。

提示：

1. 0 <= pushed.length == popped.length <= 1000
2. 0 <= pushed[i], popped[i] < 1000
3. pushed 是 popped 的排列。

注意：本题与主站 946 题相同：https://leetcode-cn.com/problems/validate-stack-sequences/

Java 栈模拟，分步分析理解

直接模拟

1. 构造一个Stack，以及两个下标位置标记idxPop，idxPush
2. 一开始为空，先压入一个pushed
3. 判断栈顶元素是否和popped当前下标的的值一样，如果一样，则说明当前应该进行弹出操作，给stack.pop();同时idxPop++;
4. 持续执行步骤3，直到不需要弹出为止
5. 再次回到步骤2，继续往栈内压入元素，记得同时idxPush++，标记执行到哪一步了
6. 步骤2至5是是一个完整准确的栈压入、弹出过程、只要按照这个步骤就可以顺利执行到结束
7. 最终判断idxPop，idxPush这两个指针是否都指向了popped，pushed两个数组的结尾，如果都指向了结尾则表明所有数据都进行过了压入栈操作，同时所有数据都进行了弹出栈操作。

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int idxPop = 0;
        int idxPush = -1;
        while ( ++idxPush < pushed.length){
            stack.add(pushed[idxPush]);
            while (!stack.isEmpty() && stack.peek() == popped[idxPop]){
                idxPop++;
                stack.pop();
            }
        }
        return idxPush == pushed.length && idxPop == popped.length;
    }
}

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。

请写一个函数，求任意第n位对应的数字。

示例 1：

输入：n = 3
输出：3

示例 2：

输入：n = 11
输出：0

限制：

• 0 <= n < 2^31

注意：本题与主站 400 题相同：https://leetcode-cn.com/problems/nth-digit/

模拟分析

按图分析

1. 0-9的时候都可以直接返回自己
2. 10-99一共有90个数字，每个数字两个字符
3. 100-999一共有900个数字，每个数字三个字符
4. 1000-9999一共有9000个数字，每个数字四个字符
5. 后续雷同

按照这个规律分析，我们只需从头开始，依次从头开始

1. 减去10个字符
2. 减去90 * 2 个字符
3. 减去900 * 3个字符
4. 减去9000 * 4个字符
5. 如果不够减了则从这一档的1 x 10^pow 开始，

• 首先除一下当前档位的字符长度，就知道当前档位的第某个数字，在加上这个档位的开始值1 x 10^pow ，就能得到当前是在哪个数字
• 再于一下当前档位的数字的长度，就知道了是刚刚求得的结果中的数字，从左往右从下标0开始的第某个数字

问题

1. 运算中间的值

 cur + 9 * powOf10 * ( pow+1 ) 

会超过int型上限，所以最简单的处理办法中间的运算过程用了long型数据

2. 取最后结果的某一位数字也可以用数学方法，不过偷懒了下直接转字符串了

代码

class Solution {
    public int findNthDigit(int n) {
        if (n < 10){
            return n;
        }
        long cur = 10;
        long powOf10 = 10;
        long pow = 1;
        while (cur + 9 * powOf10 * ( pow+1 )< n){
            cur += 9 * powOf10 * (pow+1);
            powOf10 *= 10;
            pow++;
        }
        long order = powOf10 + (n-cur) / (pow+1);
        long idx = (n - cur) % (pow+1);
        String orderStr = Long.toString(order);
        return orderStr.charAt((int)idx)-'0';
    }
}

你在和朋友一起玩 猜数字（Bulls and Cows）游戏，该游戏规则如下：

写出一个秘密数字，并请朋友猜这个数字是多少。朋友每猜测一次，你就会给他一个包含下述信息的提示：

• 猜测数字中有多少位属于数字和确切位置都猜对了（称为 “Bulls”，公牛），
• 有多少位属于数字猜对了但是位置不对（称为 “Cows”，奶牛）。也就是说，这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字。

给你一个秘密数字 secret 和朋友猜测的数字 guess ，请你返回对朋友这次猜测的提示。

提示的格式为 "xAyB" ，x 是公牛个数， y 是奶牛个数，A 表示公牛，B 表示奶牛。

请注意秘密数字和朋友猜测的数字都可能含有重复数字。

示例 1：

输入：secret = "1807", guess = "7810"
输出："1A3B"
解释：数字和位置都对（公牛）用 '|' 连接，数字猜对位置不对（奶牛）的采用斜体加粗标识。
"1807"
  |
"7810"

示例 2：

输入：secret = "1123", guess = "0111"
输出："1A1B"
解释：数字和位置都对（公牛）用 '|' 连接，数字猜对位置不对（奶牛）的采用斜体加粗标识。
"1123"        "1123"
  |      or     |
"0111"        "0111"
注意，两个不匹配的 1 中，只有一个会算作奶牛（数字猜对位置不对）。通过重新排列非公牛数字，其中仅有一个 1 可以成为公牛数字。

提示：

• 1 <= secret.length, guess.length <= 1000
• secret.length == guess.length
• secret 和 guess 仅由数字组成

题目有点绕，看的有点懵。还是简单点处理

第一次遍历要做的事情，

1. 统计某个数字出现了几次
2. 如果当前数字在secret和guess中有位置对应的，则减去一个，表示待匹配数量减少一个，同时countA++
3. 本次遍历结束map中留下的是待匹配的数字未被匹配中的数量

进行第二次遍历

1. 根据之前匹配的结果，本次遍历只处理未被匹配中的情况
2. 如果当前guess中这个位置的字符有待匹配的数量，则countB++，表示有一个匹配位置错了
3. 同时map[guess.charAt(idx)-'0']--表示处理过了一个未被匹配中的情况

最终输出结果

代码

class Solution {
    public String getHint(String secret, String guess) {
        int countA = 0;
        int countB = 0;
        int[] map = new int[10];
        int idx = -1;
        while (++idx < secret.length()){
            map[secret.charAt(idx)-'0']++;
            if (secret.charAt(idx) == guess.charAt(idx)){
                countA++;
                map[secret.charAt(idx)-'0']--;
            }
        }
        idx=-1;
        while (++idx < secret.length()){
            if (secret.charAt(idx) != guess.charAt(idx) && map[guess.charAt(idx)-'0'] > 0){
                countB++;
                map[guess.charAt(idx)-'0']--;
            }
        }
        return countA + "A" + countB + "B";
    }
}

给你一个 m x n 的矩阵 M ，初始化时所有的 0 和一个操作数组 op ，其中 ops[i] = [ai, bi] 意味着当所有的 0 <= x < ai 和 0 <= y < bi 时， M[x][y] 应该加 1。

在 执行完所有操作后 ，计算并返回 矩阵中最大整数的个数 。

示例 1:

输入: m = 3, n = 3，ops = [[2,2],[3,3]]
输出: 4
解释: M 中最大的整数是 2, 而且 M 中有4个值为2的元素。因此返回 4。

示例 2:

输入: m = 3, n = 3, ops = [[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3]]
输出: 4

示例 3:

输入: m = 3, n = 3, ops = []
输出: 9

提示:

• 1 <= m, n <= 4 * 104
• 0 <= ops.length <= 104
• ops[i].length == 2
• 1 <= ai <= m
• 1 <= bi <= n

class Solution {
    public int maxCount(int m, int n, int[][] ops) {
        for (int[] op : ops) {
            m = Math.min(m,op[0]);
            n = Math.min(n,op[1]);
        }
        return m * n;
    }
}