刷题日记 - 5

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] res = new int[2];  // 用于存放结果的数组
        
        int head = 0;  // 初始化头指针
        int tail = numbers.length - 1;  // 初始化尾指针

        // 使用双指针法查找两个数的和等于目标值
        while (head < tail && (numbers[head] + numbers[tail]) != target) {
            if (numbers[head] + numbers[tail] < target) {
                head++;  // 如果当前和小于目标值，移动头指针
            } else {
                tail--;  // 如果当前和大于目标值，移动尾指针
            }
        }

        // 找到目标值后，将结果存入数组，并返回
        res[0] = head + 1;  // 题目要求返回的索引是从1开始的，所以加1
        res[1] = tail + 1;

        return res;  // 返回结果数组
    }
}

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int INF = Integer.MAX_VALUE;  // 定义一个常量表示无穷大
        int len = nums.length;  // 数组长度
        int p = 0;  // 右指针，表示当前窗口的右边界
        int q = 0;  // 左指针，表示当前窗口的左边界
        int windowVal = 0;  // 当前窗口内的元素和
        int res = INF;  // 结果，初始化为无穷大

        // 遍历数组
        while (p < len) {
            windowVal += nums[p];  // 将右指针指向的元素加入当前窗口和
            // 如果当前窗口和大于等于目标值
            while (windowVal >= target) {
                // 更新结果为当前窗口长度和之前结果的最小值
                res = Math.min(res, p - q + 1);
                windowVal -= nums[q];  // 将左指针指向的元素移出当前窗口
                q++;  // 左指针右移，缩小窗口
            }
            p++;  // 右指针右移，扩大窗口
        }

        // 如果结果未更新，返回0，否则返回结果
        return res == INF ? 0 : res;
    }
}

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>(); // 存放结果的列表
        int len = s.length(); // 字符串 s 的长度
        
        // 记录 words 中每个单词的出现次数
        HashMap<String, Integer> patternMap = new HashMap<>();
        for (String word : words) {
            patternMap.put(word, patternMap.getOrDefault(word, 0) + 1);
        }
        
        int STEP = words[0].length();  // 单个单词的长度
        int SIZE = words.length * STEP;  // 所有单词拼接后的总长度

        // 从 0 到 STEP-1 的每个起始位置开始检查
        for (int i = 0; i < STEP; i++) {
            int idx = i; // 当前窗口的起始位置
            int p = i; // 当前扫描位置
            HashMap<String, Integer> windowMap = new HashMap<>(); // 当前窗口中单词的出现次数
            while (p + STEP <= len) { // 保证窗口不越界
                String cur = s.substring(p, p + STEP); // 当前扫描的单词
                if (patternMap.containsKey(cur)) { // 如果当前单词在 words 中
                    windowMap.put(cur, windowMap.getOrDefault(cur, 0) + 1); // 记录当前单词在窗口中的出现次数
                    while (windowMap.get(cur) > patternMap.get(cur)) { // 如果当前单词在窗口中的出现次数超过了模板中的次数
                        String tmp = s.substring(idx, idx + STEP); // 移除窗口最左边的单词
                        idx += STEP; // 窗口起始位置右移
                        windowMap.put(tmp, windowMap.get(tmp) - 1); // 更新窗口中单词的出现次数
                    }
                    if (p - idx + STEP == SIZE) { // 如果窗口大小等于所有单词拼接后的总长度
                        res.add(idx); // 记录当前窗口的起始位置
                        String tmp = s.substring(idx, idx + STEP); // 移除窗口最左边的单词
                        windowMap.put(tmp, windowMap.get(tmp) - 1); // 更新窗口中单词的出现次数
                        idx += STEP; // 窗口起始位置右移
                    }
                    p += STEP; // 扫描位置右移
                } else { // 如果当前单词不在 words 中
                    windowMap.clear(); // 清空当前窗口记录
                    p += STEP; // 扫描位置右移
                    idx = p; // 窗口起始位置更新为当前扫描位置
                }
            }
        }
        
        return res; // 返回所有匹配子串的起始位置
    }
}

// 从 0 到 STEP-1 的每个起始位置开始检查
for (int i = 0; i < STEP; i++) {
    int idx = i; // 当前窗口的起始位置
    int p = i; // 当前扫描位置

class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[][] row = new int[9][9];  // 用于记录每行中数字出现的情况
        int[][] col = new int[9][9];  // 用于记录每列中数字出现的情况
        int[][] block = new int[9][9];  // 用于记录每个 3x3 宫格中数字出现的情况

        int m = board.length;  // 数独棋盘的行数
        int n = board[0].length;  // 数独棋盘的列数
        boolean res = true;  // 用于记录数独是否合法的标志

        for(int i = 0; i < m; i++) {  // 遍历每一行
            for(int j = 0; j < n; j++) {  // 遍历每一列
                char curChar = board[i][j];  // 当前遍历到的字符
                if(curChar == '.') continue;  // 如果当前格子是空的，跳过
                int cur = board[i][j] - '1';  // 将字符转换为对应的数字索引（0-8）
                int blockIdx = (i / 3) * 3 + j / 3;  // 计算当前格子所属的 3x3 宫格索引 ⭐ 映射
                if(row[i][cur] == 1 || col[j][cur] == 1 || block[blockIdx][cur] == 1) {
                    res = false;  // 如果当前数字在当前行、列或宫格中已出现过，数独不合法
                    break;  // 退出内层循环
                }
                row[i][cur] = 1;  // 标记当前数字在当前行中已出现
                col[j][cur] = 1;  // 标记当前数字在当前列中已出现
                block[blockIdx][cur] = 1;  // 标记当前数字在当前宫格中已出现
            }
            if(!res) break;  // 如果已确定数独不合法，退出外层循环
        }
        return res;  // 返回数独是否合法的结果
    }
}

class Solution {
    public void gameOfLife(int[][] board) {
        int m = board.length;  // 行数
        int n = board[0].length;  // 列数

        int[][] state = new int[m][n];  // 用于存储每个细胞周围活细胞的数量

        // 计算每个细胞周围活细胞的数量
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(board[i][j] == 0) continue;  // 如果当前细胞是死细胞，跳过
                // 更新周围8个格子的状态计数
                if((0 <= i - 1) && (0 <= j - 1)) state[i - 1][j - 1] += 1;
                if(0 <= i - 1) state[i - 1][j] += 1;
                if((0 <= i - 1) && (n > j + 1)) state[i - 1][j + 1] += 1;
                if(0 <= j - 1) state[i][j - 1] += 1;
                if(n > j + 1) state[i][j + 1] += 1;
                if((m > i + 1) && (0 <= j - 1)) state[i + 1][j - 1] += 1;
                if(m > i + 1) state[i + 1][j] += 1;
                if((m > i + 1) && (n > j + 1)) state[i + 1][j + 1] += 1;
            }
        }

        // 根据状态更新细胞的存活情况
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(board[i][j] == 1){
                    if(state[i][j] < 2) board[i][j] = 0;  // 活细胞少于2个活邻居死亡
                    if(state[i][j] > 3) board[i][j] = 0;  // 活细胞多于3个活邻居死亡
                } else {
                    if(state[i][j] == 3) board[i][j] = 1;  // 死细胞恰好有3个活邻居复活
                }
            }
        }
    }
}

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        boolean res = true;  // 结果标志，初始设为true
        
        int[] cnt = new int[26];  // 用于存储杂志中每个字母的数量
        int[] need = new int[26];  // 用于存储赎金信中每个字母的需求量

        // 遍历赎金信，将每个字母的需求量存储在need数组中
        for(char ch : ransomNote.toCharArray()) {
            need[ch - 'a']++;
        }

        // 遍历杂志，将每个字母的数量存储在cnt数组中
        for(char ch : magazine.toCharArray()) {
            cnt[ch - 'a']++;
        }

        // 比较两个数组中每个字母的数量
        for(int i = 0; i < 26; i++) {
            // 如果某个字母的需求量大于杂志中的数量，则无法构造赎金信
            if(need[i] > cnt[i]) {
                res = false;
                break;
            }
        }

        return res;  // 返回结果
    }
}