樊轶群的个人网站

// 1662. Check If Two String Arrays are Equivalent
class Solution {
    public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
        StringBuilder words1 = new StringBuilder();
        for (String word : word1) {
            words1.append(word);
        }
        StringBuilder words2 = new StringBuilder();
        for (String word : word2) {
            words2.append(word);
        }
        char[] chars1 = words1.toString().toCharArray();
        char[] chars2 = words2.toString().toCharArray();
        if (chars1.length != chars2.length) {
            return false;
        }
        for (int i = 0; i < chars1.length; ++i) {
            if (chars1[i] != chars2[i]) {
                return false;
            }
        }
        return true;
    }
}

学习笔记：
这是月初的第一道题目，也是一道水题。
用StringBuilder拼接比较快，然后转char[]遍历比较快。

// 0481. Magical String
class Solution {
    public int magicalString(int n) {
        if (n <= 3) return 1;
        int ans = 1;
        int[] magical = new int[n + 1];
        magical[0] = 1;
        magical[1] = magical[2] = 2;
        int slow = 2;
        int fast = 3;
        int fill = 1;
        while (fast < n) {
            for (int i = 0; i < magical[slow]; ++i) {
                magical[fast] = fill;
                if (fill == 1 && fast < n) ++ans;
                ++fast;
            }
            fill = 3 - fill;
            ++slow;
        }
        return ans;
    }
}

学习笔记：
这道题是双指针算法的题目。
快指针写，慢指针读。

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

// 0784. Letter Case Permutation
class Solution {
    public List<String> letterCasePermutation(String s) {
        char[] charArray = s.toCharArray();
        int n = charArray.length;
        Queue<StringBuilder> queue = new LinkedList<>();
        queue.offer(new StringBuilder());
        for (char c : charArray) {
            char fill1;
            char fill2;
            int size = queue.size();
            if (c <= '9') {
                fill1 = c;
                for (int j = 0; j < size; ++j) {
                    queue.offer(queue.poll().append(fill1));
                }
            } else {
                if (c > 'Z') {
                    fill1 = c;
                    fill2 = (char) (c - 32);
                } else {
                    fill1 = (char) (c + 32);
                    fill2 = c;
                }
                for (int j = 0; j < size; ++j) {
                    StringBuilder sb1 = queue.poll();
                    StringBuilder sb2 = new StringBuilder(sb1.toString());
                    sb1.append(fill1);
                    queue.offer(sb1);
                    sb2.append(fill2);
                    queue.offer(sb2);
                }
            }
        }
        List<String> ans = new LinkedList<>();
        for (StringBuilder sb : queue) {
            ans.add(sb.toString());
        }
        return ans;
    }
}

学习笔记：
这是一道字符串大小写相关的题目，用到搜索算法。
就是数字不变，字母各种变。
本来打算写深度优先搜索，但是一想不对啊，这深度也太深了会崩溃的。
于是用了宽度优先搜索算法来完成。

import java.util.List;

// 1773. Count Items Matching a Rule
class Solution {
    public int countMatches(List<List<String>> items, String ruleKey, String ruleValue) {
        int ans = 0;
        int n = items.size();
        if ("type".equals(ruleKey)) {
            for (List<String> item : items) {
                if (item.get(0).equals(ruleValue)) {
                    ++ans;
                }
            }
        } else if ("color".equals(ruleKey)) {
            for (List<String> item : items) {
                if (item.get(1).equals(ruleValue)) {
                    ++ans;
                }
            }
        } else {
            for (List<String> item : items) {
                if (item.get(2).equals(ruleValue)) {
                    ++ans;
                }
            }

        }
        return ans;
    }
}

学习笔记：
这是一道简单题，一道水题。
就是根据关键字遍历数组统计一下。

import java.util.Stack;

// 0907. Sum of Subarray Minimums
class Solution {
    public int sumSubarrayMins(int[] arr) {
        final long MOD = 1000000007;
        int n = arr.length;
        int[] arr_0 = new int[n + 1];
        System.arraycopy(arr, 0, arr_0, 0, n);
        arr_0[n] = 0;
        Stack<Integer> stack = new Stack<>();
        long ans = 0L;
        for (int i = 0; i <= n; ++i) {
            while (!stack.isEmpty() && arr_0[stack.peek()] > arr_0[i]) {
                int mid = stack.pop();
                int left = stack.isEmpty() ? -1 : stack.peek();
                ans = (ans + (long) (i - mid) * (mid - left) * arr_0[mid]) % MOD;
            }
            stack.push(i);
        }
        return (int) ans;
    }
}

学习笔记：
这是一道单调栈的题目。
我使用了和0312类似的动态规划做了老半天，不是超空间就是超时。
实在没办法了只好看了单调栈的解法。

// 1822. Sign of the Product of an Array
class Solution {
    public int arraySign(int[] nums) {
        int ans = 1;
        for (int num : nums) {
            if (num < 0) {
                ans *= -1;
            } else if (num == 0) {
                return 0;
            }
        }
        return ans;
    }
}

学习笔记：
这是一道简单的数组题目。
真的是一个大水题，没有任何科技含量。

import java.util.ArrayDeque;
import java.util.Deque;

// 0862. Shortest Subarray with Sum at Least K
class Solution {
    public int shortestSubarray(int[] nums, int K) {
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; ++i) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        Deque<Integer> deque = new ArrayDeque<>();
        int ans = n + 1;
        for (int i = 0; i < n + 1; ++i) {
            while (!deque.isEmpty() && prefix[i] - prefix[deque.peekFirst()] >= K) {
                ans = Math.min(ans, i - deque.pollFirst());
            }
            while (!deque.isEmpty() && prefix[i] <= prefix[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }
        return ans <= n ? ans : -1;
    }
}

学习笔记：
这是一道困难题。需要用到前缀和和单调队列的思想。
需要连续的一串数字也就是子数组的和大于k，那么就相当于两个前缀和的差大于k。
把所有单调递增（相等也行）的前缀和放入队列，
然后难点是再走一圈判断互相之间有没有得到最小长度。
那我们可以保证队尾和队首之间的差，一旦大于等于k了，就判断是否是最短，判断完把队首也弹出了。

import java.util.LinkedList;
import java.util.Queue;

// 0934. Shortest Bridge
class Solution {
    public int shortestBridge(int[][] grid) {
        Queue<Land> queue = new LinkedList<>();
        Queue<Land> land1 = new LinkedList<>();
        int n = grid.length;
        boolean[][] visited = new boolean[n][n];
        outer:
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    Land land = new Land(i, j);
                    queue.add(land);
                    land1.add(land);
                    visited[i][j] = true;
                    break outer;
                }
            }
        }
        int[][] direction = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                Land front = queue.poll();
                for (int j = 0; j < 4; ++j) {
                    int newX = front.x + direction[j][0];
                    int newY = front.y + direction[j][1];
                    if (newX >= 0 && newX < n && newY >= 0 && newY < n && grid[newX][newY] == 1 && !visited[newX][newY]) {
                        visited[newX][newY] = true;
                        Land land = new Land(newX, newY);
                        queue.add(land);
                        land1.add(land);
                    }
                }
            }
        }
        int ans = 0;
        while (!land1.isEmpty()) {
            int size = land1.size();
            for (int i = 0; i < size; ++i) {
                Land front = land1.poll();
                for (int j = 0; j < 4; ++j) {
                    int newX = front.x + direction[j][0];
                    int newY = front.y + direction[j][1];
                    if (newX >= 0 && newX < n && newY >= 0 && newY < n && !visited[newX][newY]) {
                        if (grid[newX][newY] == 1) {
                            return ans;
                        } else {
                            visited[newX][newY] = true;
                            Land land = new Land(newX, newY);
                            land1.add(land);
                        }
                    }
                }
            }
            ++ans;
        }
        return -1;
    }
}

class Land {
    int x;
    int y;

    public Land(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

学习笔记：
这道题是宽度搜索题。
先确定一个岛，然后往外扩展几圈，确定桥的长度是几。
一开始可以使用深搜、宽搜。
后面扩展的时候只可以使用宽搜。

// 0915. Partition Array into Disjoint Intervals
class Solution {
    public int partitionDisjoint(int[] nums) {
        int n = nums.length;
        int leftMax = nums[0];
        int alternate = nums[0];
        int bound = 0;
        for (int i = 1; i < n; ++i) {
            if (nums[i] < leftMax) {
                leftMax = alternate;
                bound = i;
            } else {
                alternate = Math.max(alternate, nums[i]);
            }
        }
        return bound + 1;
    }
}

学习笔记：
这是一道中等难度的题目，不过还是有点困难的。
要保证左边比右边的每一个元素小。
只需要三个变量其实就可以维护住了：左边最大值、备胎值、左边界。
遇到比左边的大的，那么就需要更新备胎值，暂时不把他放进来。
遇到比左边最大值小的，那肯定要把小数字吸收进来，所以之前遇到的备胎必须转正了。
遇到相等怎么办呢？得好好考虑，应该题目说要让左半尽可能元素少。那么相等就不应该放进来。
最终要注意，求的是元素个数，所以我们算的bound边界需要加1才是答案。

// 1768. Merge Strings Alternately
class Solution {
    public String mergeAlternately(String word1, String word2) {
        StringBuilder sb = new StringBuilder();
        int length1 = word1.length();
        int length2 = word2.length();
        if (length1 < length2) {
            for (int i = 0; i < length1; ++i) {
                sb.append(word1.charAt(i));
                sb.append(word2.charAt(i));
            }
            sb.append(word2.substring(length1));
        } else {
            for (int i = 0; i < length2; ++i) {
                sb.append(word1.charAt(i));
                sb.append(word2.charAt(i));
            }
            sb.append(word1.substring(length2));
        }
        return sb.toString();
    }
}

学习笔记：
这是一道字符串的简单题，就是合并字符串，多的接上去就行了。