LeetCode Hot150 本人题解

这里记录一下本人刷Hot150的记录把。我会把自己AC的思路以及官方最优解同时放上来，如果自己没有AC则只放官方最优解，如果AC记录与官方最优解一致或思路几乎相同，只放本人题解。

官方最优解的定义指的是官方题解中时空复杂度最低的一个题解。

合并两个有序数组

AC思路 & 官方最优解

两个指针p1和p2，分别指向两个数组的末尾，指针p指向结果数组的末尾。每次从两个数组中取最大的一个赋值到指针p，然后移动指针。

为什么不会覆盖数组？最初时指针p和指针p1的差值为数组2的长度n，当一次操作选取数组2的元素时，这个差值会减1；当选取数组1的元素，指针p和指针p1同时移动，差值没有发生变化。由于使差值发生变化的操作最多只有n次，因此两个指针差值始终大于等于0，不会发生覆盖问题。

时间O(m + n)，额外空间O(1)

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1, p2 =  n - 1, p = m + n - 1;
        while (p >= 0) {
            if (p1 < 0 || (p2 >= 0 && nums2[p2] >= nums1[p1])) {
                nums1[p] = nums2[p2];
                p--;
                p2--;
            } else if (p2 < 0 || nums1[p1] > nums2[p2]) {
                nums1[p] = nums1[p1];
                p--;
                p1--;
            } else {
                throw new IllegalArgumentException();
            }
        }
    }
}

移除元素

AC思路 & 官方最优解

双指针，左指针遍历元素，如果遇见了一个要移除的元素则从右指针找到第一个不是要移除的元素，进行交换。两个指针相遇时，右指针即为数组长度。

时间O(n)，额外空间O(1)

class Solution {
    public int removeElement(int[] nums, int val) {
        int p = nums.length;
        for (int i = 0; i < p; i++) {
            if (nums[i] == val) {
                while(i < p && nums[--p] == val);
                // swap
                nums[i] = nums[i] ^ nums[p];
                nums[p] = nums[i] ^ nums[p];
                nums[i] = nums[i] ^ nums[p];
            }
        }
        return p;
    }
}

为什么两层循环时间复杂度仍然为O(n)？因为nums数组的每一个元素只会被访问一次。

删除有序数组中的重复项

AC思路 & 官方最优解

双指针，pr指针用来读数组元素，pw指针用来写数组元素。pr指针每次读取连续元素的最后一个位置，然后将值写到pw指针处。

时间O(n)，额外空间O(1)

class Solution {
    public int removeDuplicates(int[] nums) {
        final int n = nums.length;
        int pr = 0, pw = 0;
        while (pr < n) {
            while(pr + 1 < n && nums[pr] == nums[pr + 1]) pr++;
            nums[pw] = nums[pr];
            pw++;
            pr++;
        }
        return pw;
    }
}

删除有序数组中的重复项 II

AC思路 & 官方最优解

与上题思路一致，引入一个变量记录一下出现次数，如果大于1则多写一次即可。

时间O(n)，额外空间O(1)

class Solution {
    public int removeDuplicates(int[] nums) {
        final int n = nums.length;
        int pr = 0, pw = 0;
        while (pr < n) {
            int cnt = 1;
            while(pr + 1 < n && nums[pr] == nums[pr + 1]) {
                pr++;
                cnt++;
            }
            nums[pw] = nums[pr];
            pw++;
            pr++;
            if(cnt > 1) {
                nums[pw] = nums[pr - 1];
                pw++;
            }
        }
        return pw;
    }
}

多数元素

AC思路

最直接的思路：用哈希表记录元素或者排序后返回中位数，前者时空O(n)，后者时间O(nlogn)，空间O(1)。实际上用Arrays.sort()是最简单且最靠谱的，如果面试时闲太简单可以手写一下快排。

class Solution {

    private final Random random = new Random();

    // 左闭右开
    private int randint(int l, int r) {
        return random.nextInt(r - l) + l;
    }

    private void swap(int[] nums, int p1, int p2) {
        if(p1 == p2) return;
        nums[p1] = nums[p1] ^ nums[p2];
        nums[p2] = nums[p1] ^ nums[p2];
        nums[p1] = nums[p1] ^ nums[p2];
    }

    private void quickSort(int[] nums, int l, int r) {
        if(r - l <= 1) return;
        final int p = randint(l, r);
        final int val = nums[p];
        // p2指向右区间的第一个元素，p1-1指向左区间的最后一个元素
        int p1 = l, p2 = r;
        for(int i = l; i < p2; ) {
            if(nums[i] == val) {
                // nop
                i++;
            } else if(nums[i] > val) {
                p2--;
                swap(nums, i, p2);
            } else {
                swap(nums, i, p1);
                p1++;
                i++;
            }
        }
        quickSort(nums, l, p1);
        quickSort(nums, p2, r);
    }

    public int majorityElement(int[] nums) {
        quickSort(nums, 0, nums.length);
        return nums[nums.length / 2];
    }
}

时间复杂度O(nlogn)，空间复杂度O(1)。

官方最优解

随机化确实是一种方法，之前我也遇见过类似用随机数判断答案的，而且确实有道理。然而遇见一道新题目是很难直接想到这个方法的。

本题目期望概率收敛于2。

class Solution {
    private int randRange(Random rand, int min, int max) {
        return rand.nextInt(max - min) + min;
    }

    private int countOccurences(int[] nums, int num) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == num) {
                count++;
            }
        }
        return count;
    }

    public int majorityElement(int[] nums) {
        Random rand = new Random();

        int majorityCount = nums.length / 2;

        while (true) {
            int candidate = nums[randRange(rand, 0, nums.length)];
            if (countOccurences(nums, candidate) > majorityCount) {
                return candidate;
            }
        }
    }
}

时间复杂度O(n)，空间复杂度O(1)。

轮转数组

AC思路 & 官方最优解

首先可以对k进行模n处理，结果仍然赋值给k。因为旋转n次数组与原先相同没有变化。然后可以模拟一下从元素0开始的搬运过程，被搬运的地方需要腾出空间，所以这个元素也需要跟着搬运。且会形成gcd(n, k)个搬运环。（结论是直觉出来的，不会证明这个…）

我直接把官方题解贴上了：

时间复杂度O(n)，空间复杂度O(1)。

class Solution {

    private int gcd(int a, int b) {
        return b != 0 ? gcd(b, a % b) : a;
    }

    private void func(int[] nums, final int n, final int ps, final int k) {
        int t = nums[ps];
        int p1 = (ps + k) % n;
        while(p1 != ps) {
            int t1 = nums[p1];
            nums[p1] = t;
            t = t1;
            p1 = (p1 + k) % n;
        }
        nums[ps] = t;
    }

    public void rotate(int[] nums, int k) {
        final int n = nums.length;
        k = k % n;
        if(k == 0) {
            return;
        }
        for(int i = 0; i < gcd(n, k); i++) {
            func(nums, n, i, k);
        }
    }
}

如果没有想到搬运环具体有多少个，可以通过记录已搬运元素个数的方式来避开这个问题：

class Solution {
    public void rotate(int[] nums, int k) {
        final int n = nums.length;
        k = k % n;
        if(k == 0) {
            return;
        }
        int cnt = 0;
        for(int p = 0; cnt < n; p++) {
            int t = nums[p];
            int p0 = (p + k) % n;
            int p1 = p;
            while(p != p0) {
                int t1 = nums[p0];
                nums[p0] = t;
                t = t1;
                p1 = p0;
                p0 = (p0 + k) % n;
                cnt++;
            }
            nums[p] = t;
            cnt++;
        }
    }
}

不过我觉得官方题解三更加通俗易懂，先整体翻转一下，再两个子数组翻转。

class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }

    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start += 1;
            end -= 1;
        }
    }
}

买卖股票的最佳时机

AC思路 & 官方最优解

每一天都可以选择作为售出日，因此对于每一天来说的最优方案就是选择当前日之前的最低价格买入，当天售出。所以只需要维护价格最低值，然后用每天的价格减去之前的最低值，取最大值即为题目要求的最优方式。

时间复杂度O(n)，空间复杂度O(1)

class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0;
        int min = prices[0];
        for(int i = 0; i < prices.length; i++) {
            ans = Math.max(ans, prices[i] - min);
            min = Math.min(min, prices[i]);
        }
        return ans;
    }
}

买卖股票的最佳时机 II

AC 思路 & 官方题解

可以想一次买入和卖出的操作，买入花了x元，卖出y元，利润y-x元。假设存在买入x元，卖出z元（z大于y）可能比刚才的操作更优。但有z - x == z - y + y - x恒成立，也就是说可以在卖出y元那天在以y元买入。故整体最大利润就是能卖出的时候就直接卖出。

class Solution {
    public int maxProfit(int[] prices) {
        final int n = prices.length;
        int min = prices[0];
        int ans = 0;
        for(int i = 0; i < n; i++) {
            if(prices[i] > min) {
                ans += prices[i] - min;
                min = prices[i];
            } else {
                min = prices[i];
            }
        }
        return ans;
    }
}

时间复杂度O(n)，空间复杂度O(1)。

跳跃游戏

AC思路 & 官方最优解

维护一个最远达到位置的变量，判断其是否大于n-1即可。

class Solution {
    public boolean canJump(int[] nums) {
        final int n = nums.length;
        int p = 0;
        for(int i = 0; i < n && i <= p; i++) {
            p = Math.max(p, i + nums[i]);
        }
        return p >= n - 1;
    }
}

跳跃游戏 II

AC思路 & 官方最优解

可以把[0, nums[0]]这个区间看作第一个跳跃区间，然后求出这个区间内其他点可以跳到的最远距离，再把[nums[0], maxPos0]这个区间作为第二个区间，计算可以跳到的最远距离，直到覆盖了终点，区间个数也就是最终答案。

时间复杂度O(n)，空间复杂度O(1)。

class Solution {
    public int jump(int[] nums) {
        final int n = nums.length;
        int maxPos = 0;
        int ans = 0;
        int curPos = 0;
        int p = 0;
        while(curPos < n - 1) {
            while(p <= curPos) {
                maxPos = Math.max(maxPos, p + nums[p]);
                p++;
            }
            ans++;
            curPos = maxPos;
        }
        return ans;
    }
}

H 指数

AC思路 & 官方最优解

设答案为x，则显然数字[0, x]都满足答案的定义。所以可以使用二分来解决这个问题。二分解题时要注意一些细节。

时间复杂度O(nlogn)，空间复杂度O(1)。

class Solution {

    private boolean check(int[] nums, int n, int h) {
        int cnt = 0;
        for(int i = 0; i < n; i++) {
            if(nums[i] >= h) cnt++;
        }
        return cnt >= h;
    }

    public int hIndex(int[] citations) {
        final int n = citations.length;
        int l = 0, r = 1001;
        while(l < r) {
            int mid = (l + r + 1) >> 1;
            if(check(citations, n, mid)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }
}

O(1) 时间插入、删除和获取随机元素

AC思路 & 官方最优解

对于哈希表来说，插入和删除平均是O1的，对于数组来说，随机寻址是O1的。因此本体需要结合这两种数据结构的特性，在插入时放到哈希表和数组末尾中，在删除的时候从哈希表获取该元素所在数组索引，将当前索引与数组最后元素进行交换然后从数组删除。随机寻址使用数组访问元素即可。

class RandomizedSet {

    private final Map<Integer, Integer> map;
    private final List<Integer> arr;
    private final Random random;

    public RandomizedSet() {
        map = new HashMap<>();
        arr = new ArrayList<>();
        random = new Random();
    }
    
    public boolean insert(int val) {
        if(map.containsKey(val)) {
            return false;
        }
        arr.add(val);
        map.put(val, arr.size() - 1);
        return true;
    }
    
    public boolean remove(int val) {
        if(!map.containsKey(val)) {
            return false;
        }
        int idx = map.remove(val);
        if(idx == arr.size() - 1) {
            arr.remove(arr.size() - 1);
            return true;
        }
        int last = arr.get(arr.size() - 1);
        arr.set(idx, last);
        map.put(last, idx);
        arr.remove(arr.size() - 1);
        return true;
    }
    
    public int getRandom() {
        int idx = random.nextInt(arr.size());
        return arr.get(idx);
    }
}

除了自身以外数组的乘积

AC思路 & 官方最优解

使用一个临时变量t，用于记录当前遍历过元素的乘积结果，并与ans元素相乘。之后再反向遍历一次即可。

时间复杂度O(n)，额外空间复杂度O(1)。

class Solution {
    public int[] productExceptSelf(int[] nums) {
        final int n = nums.length;
        int[] ans = new int[n];
        for(int i = 0; i < n; i++) {
            ans[i] = 1;
        }
        int t = 1;
        for(int i = 0; i < n; i++) {
            ans[i] *= t;
            t *= nums[i];
        }
        t = 1;
        for(int i = n - 1; i >= 0; i--) {
            ans[i] *= t;
            t *= nums[i];
        }
        return ans;
    }
}

加油站

AC思路 & 官方最优解

不妨假设从0号位置开始，每次向前走一步，如果剩余油是大于0的，则可以继续向前走，直到剩余油变成小于0。这个时候说明假设不成立，尝试从0号位置的前驱，也就是n-1的位置开始假设。使用双指针，一个指针代表开始位置，一个指针代表结束位置。如果两个指针相碰而剩余油仍然小于0说明无解。

时间复杂度O(n)，空间复杂度O(1)。

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        final int n = gas.length;
        int left = 0;
        int ps = 0; // start pos
        int p = 0;  // cur pos
        do {
            left += gas[p] - cost[p];
            p = (p + 1) % n;
            while(left < 0 && ps != p) {
                ps = (ps - 1 + n) % n;
                left += gas[ps] - cost[ps];
            }
        } while(ps != p);
        return left >= 0 ? ps : -1;
    }
}

分发糖果

AC思路

考虑两个方向的贪心，从某个方向遍历的时候，如果当前元素比前一个元素大，则说明当前位置需要比前一个位置对答案多贡献1。每一个位置对答案多贡献的值则为两个方向的最大值。需要新开一个cnt数组用来记录每个位置对答案多贡献的值。

时间复杂度O(n)，空间复杂度O(n)，非最优题解。

class Solution {
    public int candy(int[] ratings) {
        final int n = ratings.length;
        int[] cnt = new int[n];
        for(int i = 1; i < n; i++) {
            if(ratings[i] > ratings[i - 1]) {
                cnt[i] = cnt[i - 1] + 1;
            }
        }
        int t = 0;
        for(int i = n - 2; i >= 0; i--) {
            if(ratings[i] > ratings[i + 1]) {
                cnt[i] = Math.max(cnt[i], t + 1);
                t++;
            } else {
                t = 0;
            }
        }
        int ans = n;
        for(int x : cnt) ans += x;
        return ans;
    }
}

官方最优解

记录当前位置的前驱分配了pre个糖果，那么如果当前位置rate大于前一个rate，说明出于上升序列，直接分配pre + 1个糖果即可满足条件；当rate小于前一个rate的时候，说明出于下降序列，分配当前位置为1个糖果，并把之前的位于递减序列上的位置多分配一个糖果。递减序列个数增加到与前一个递增序列相同的时候，需要把前一个递增序列的最后一个元素也算进递减序列中。

时间复杂度O(n)，空间复杂度O(1)。

class Solution {
    public int candy(int[] ratings) {
        final int n = ratings.length;
        int ans = 1;
        int inc = 1, dec = 0, pre = 1;
        for(int i = 1; i < n; i++) {
            if(ratings[i] >= ratings[i - 1]) {
                dec = 0;
                pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1;
                ans += pre;
                inc = pre;
            } else {
                dec++;
                if(dec == inc) dec++;
                ans += dec;
                pre = 1;
            }
        }
        return ans;
    }
}

接雨水

AC思路

考虑每一个位置上雨水高可以为多少，答案就是这些雨水高的和乘上宽度。一个位置上的雨水的高是左侧遇到的最大高度和右侧遇到的最大高度取最小。用两个数组分别维护当前位置左侧最高柱子和右侧最高柱子。

时间复杂度O(n)，空间复杂度O(n)。

class Solution {
    public int trap(int[] height) {
        final int n = height.length;
        int[] left = new int[n];
        int[] right = new int[n];
        int lh = height[0], rh = height[n - 1];
        for(int i = 1; i < n; i++) {
            left[i] = lh;
            lh = Math.max(lh, height[i]);
        }
        for(int i = n - 2; i >= 0; i--) {
            right[i] = rh;
            rh = Math.max(rh, height[i]);
        }
        int ans = 0;
        for(int i = 0; i < n; i++) {
            ans += Math.max(0, Math.min(left[i], right[i]) - height[i]);
        }
        return ans;
    }
}

罗马数字转整数

AC思路 & 官方最优解

直接模拟即可。时间复杂度O(n)，空间复杂度O(1)。

class Solution {

    private int val(char a, char b) {
        if(a == 'I') {
            if(b == 'V') return 4;
            else if(b == 'X') return 9;
        } else if(a == 'X') {
            if(b == 'L') return 40;
            else if(b == 'C') return 90;
        } else if(a == 'C') {
            if(b == 'D') return 400;
            else if(b == 'M') return 900;
        }
        return 0;
    }

    private int val(char a) {
        final Map<Character, Integer> map = Map.of(
            'I', 1, 'V', 5, 'X', 10, 'L', 50,
            'C', 100, 'D', 500, 'M', 1000
        );
        return map.getOrDefault(a, 0);
    }

    public int romanToInt(String s) {
        final int n = s.length();
        int ans = 0;
        for(int i = 0; i < n; i++) {
            if(i != n - 1) {
                int v = val(s.charAt(i), s.charAt(i + 1));
                if(v != 0) {
                    ans += v;
                    i++;
                    continue;
                }
            }
            ans += val(s.charAt(i));
        }
        return ans;
    }
}

整数转罗马数字

AC思路

直接if-else编代码，时间复杂度O(num)，空间复杂度O(1)

class Solution {
    public String intToRoman(int num) {
        StringBuilder sb = new StringBuilder();
        if(num >= 1000) {
            int t = num / 1000;
            num %= 1000;
            while(t-- != 0) sb.append("M");
        }
        if(num >= 900) {
            num -= 900;
            sb.append("CM");
        }
        if(num >= 500) {
            sb.append("D");
            num -= 500;
        }
        if(num >= 100) {
            int t = num / 100;
            num %= 100;
            if(t == 4) {
                sb.append("CD");
            } else {
                while(t-- != 0) sb.append("C");
            }
        }
        if(num >= 90) {
            num -= 90;
            sb.append("XC");
        }
        if(num >= 50) {
            num -= 50;
            sb.append("L");
        }
        if(num >= 10) {
            int t = num / 10;
            num %= 10;
            if(t == 4) {
                sb.append("XL");
            } else {
                while(t-- != 0) sb.append("X");
            }
        }
        if(num >= 9) {
            num -= 9;
            sb.append("IX");
        }
        if(num >= 5) {
            num -= 5;
            sb.append("V");
        }
        if(num >= 1) {
            int t = num;
            num = 0;
            if(t == 4) {
                sb.append("IV");
            } else {
                while(t-- != 0) sb.append("I");
            }
        }
        return sb.toString();
    }
}

官方最优解

硬编码数字这个思路确实比较巧妙，值得学习，也算是常见的时间换空间的思路。时间复杂度O(1)，空间复杂度O(1)。

class Solution {
    String[] thousands = {"", "M", "MM", "MMM"};
    String[] hundreds  = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
    String[] tens      = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
    String[] ones      = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};

    public String intToRoman(int num) {
        StringBuffer roman = new StringBuffer();
        roman.append(thousands[num / 1000]);
        roman.append(hundreds[num % 1000 / 100]);
        roman.append(tens[num % 100 / 10]);
        roman.append(ones[num % 10]);
        return roman.toString();
    }
}

最后一个单词的长度

AC思路

直接遍历即可，遇见新的单词清空计数器，最后计数器计算的长度就是答案所求。

时间复杂度O(n)，空间复杂度O(1)。

class Solution {
    public int lengthOfLastWord(String s) {
        int ans = 0;
        final int n = s.length();
        int p = 0;
        while(p < n) {
            boolean flag = false;
            while(p < n && s.charAt(p) == ' ') {
                flag = true;
                p++;
            }
            if(p >= n) break;
            if(flag) ans = 0;
            ans++;
            p++;
        }
        return ans;
    }
}

官方最优解

官方题解是反向遍历，获取到第一个单词的长度。时空复杂度和正向遍历一样，这里就不贴代码了。

最长公共前缀

AC思路 & 官方最优解

维护一个pos变量，每次都比较一下各个字符串pos处的字符是否一致即可。

时间复杂度O(mn)，空间O(1)。这题官方题解的分治法和二分法不仅没有降低时间复杂度，还增大了编码难度，感觉纯粹是为了写题而写题。

class Solution {
    public String longestCommonPrefix(String[] strs) {
        final int n = strs.length;
        if(n == 0) return "";
        int pos = 0;
        while(true) {
            for(int i = 0; i < n; i++) {
                if(strs[i].length() <= pos) {
                    return strs[0].substring(0, pos);
                }
            }
            char c = strs[0].charAt(pos);
            for(int i = 1; i < n; i++) {
                if(c != strs[i].charAt(pos)) {
                    return strs[0].substring(0, pos);
                }
            }
            pos++;
        }
    }
}

反转字符串中的单词

AC思路 & 官方最优解

直接反向遍历获取单词，然后保存即可。Java中String类型是不可变的，因此不能使用原地算法。时间复杂度O(n)，空间复杂度O(1)

class Solution {
    public String reverseWords(String s) {
        final int n = s.length();
        StringBuilder sb = new StringBuilder();
        int pos = n - 1;
        while(pos >= 0) {
            while(pos >= 0 && s.charAt(pos) == ' ') pos--;
            if(pos < 0) break;
            int p = pos;
            while(p >= 0 && s.charAt(p) != ' ') p--;
            p++;
            if(sb.isEmpty()) {
                sb.append(s.substring(p, pos + 1));
            } else {
                sb.append(" ").append(s.substring(p, pos + 1));
            }
            pos = p - 1;
        }
        return sb.toString();
    }
}

对于可以原地修改字符串的语言，可以分三步走，先把每个单词反转一下，再整体反转一下，最后压缩空格，就可以达到相同的效果，时间复杂度O(n)，空间复杂度O(1)。

void reverse(char* s, int p1, int p2) {
    while(p1 < p2) {
        char c = *(s + p1);
        *(s + p1) = *(s + p2);
        *(s + p2) = c;
        p1++;
        p2--;
    }
}

char* reverseWords(char* s) {
    const int n = strlen(s);
    int pos = n - 1;
    while(pos >= 0) {
        while(pos >= 0 && *(s + pos) == ' ') pos--;
        if(pos < 0) break;
        int t = pos;
        while(t >= 0 && *(s + t) != ' ') t--;
        t++;
        reverse(s, t, pos);
        pos = t - 1;
    }
    int p1 = 0, p2 = n - 1;
    reverse(s, 0, n - 1);
    int pr = 0, pw = 0;
    int isFirst = 1;
    while(pr < n) {
        while(pr < n && *(s + pr) == ' ') pr++;
        if(pr >= n) break;
        if(!isFirst) *(s + (pw++)) = ' ';
        else isFirst = 0;
        while(pr < n && *(s + pr) != ' ') *(s + (pw++)) = *(s + (pr++));
    }
    if(pw < n) *(s + pw) = '\0';
    return s;
}

Z 字形变换

AC思路 & 官方最优解

可以从n为4和5分析一下每一行元素下标的规律，可以发现对于第一行，其下标都是相差2n - 2的，对于第二行，下标一个相差2n - 4另一个相差2，对于第三行，下标一个相差2n - 6另一个相差4…对于倒数第一行则下标一个相差2另一个相差2n - 4，最后一行则相差2n - 2。可以用两个变量维护这个交替关系。

每次只取一个字符，时间复杂度O(n)，额外空间复杂度O(1)。

class Solution {
    public String convert(String s, int numRows) {
        // 2n - 2
        if(numRows == 1) return s;
        StringBuilder sb = new StringBuilder();
        final int n = s.length();
        int p1 = 2 * numRows - 2, p2 = 0;
        for(int i = 0; i < numRows; i++) {
            int pos = i;
            int cnt = 0;
            while(pos < n) {
                sb.append(s.charAt(pos));
                if(p1 == 0) pos += p2;
                else if(p2 == 0) pos += p1;
                else pos += cnt % 2 == 0 ? p1 : p2;
                cnt++;
            }
            p1 -= 2;
            p2 += 2;
        }
        return sb.toString();
    }
}

找出字符串中第一个匹配项的下标(KMP板子题目)

找出字符串中第一个匹配项的下标

AC思路 & 官方最优解

这题是KMP的板子题目，引用一下我大一时写的文章，不过这里也会重新说一下思路。

这里需要维护一个失配数组fail[m]，用于处理串t各个位置的最长公共前后缀。fail[i]代表的是以i结尾的子字符串的最长公共前后缀的长度（刨除子字符串本身，即fail[i] != i + 1且t.substring(0, fail[i]) == t.substring(t.length() - fail[i], t.length())）。求解fail[i]时会利用到fail[i - 1]的值，当t[i] == t[fail[i - 1]]时说明fail[i] == fail[i - 1] + 1。如果t[i] != t[fail[i - 1]]，那么就缩短这个公共前后缀的长度，从长度为fail[i - 1]的子串里再找最大的公共前后缀（也就是fail[fail[i - 1] - 1]的值）然后再比较i处字符和这个位置的字符是否相同，直到公共前后缀长度为0。

接下来从字符串s中寻找t时会使用到上面维护的fail数组，维护两个指针p和q分别指向两个字符串，当s[p] == t[q]的时候则同时前进，当失配的时候，则令q = fail[q - 1]而p不动。因为s串以p为长度的前缀子串中的某个后缀等于t串中的某个前缀，这个前缀的长度就是fail[q - 1]。如果q已经为0，则需要p进行前进操作。

时间复杂度O(m + n)，空间复杂度O(m)。

class Solution {

    private int kmp(String s, String t) {
        final int n = s.length();
        final int m = t.length();
        int[] fail = new int[m];
        fail[0] = 0;
        for(int i = 1; i < m; i++) {
            int j = fail[i - 1];
            while(j != 0 && t.charAt(i) != t.charAt(j)) {
                j = fail[j - 1];
            }
            if(t.charAt(i) == t.charAt(j)) {
                fail[i] = j + 1;
            }
        }
        int p = 0, q = 0;
        while(p < n) {
            if(s.charAt(p) == t.charAt(q)) {
                p++;
                q++;
                if(q == m) {
                    return p - m;
                }
            } else {
                if(q == 0) p++;
                else {
                    q = fail[q - 1];
                }
            }
        }
        return -1;
    }

    public int strStr(String haystack, String needle) {
        return kmp(haystack, needle);
    }
}

文本左右对齐

AC思路 & 官方最优解

纯构思模拟题，按要求做就行。先给字符串分组，计算加入一个字符串到当前分组的时候，长度是否会超限（注意要把单词间至少一个空格算进去），如果超限那么说明这个字符串不能加入当前分组，要开一个新的分组。分完组后，除了最后一个分组外，其他的分组需要先计算一下空格有多少，每个单词之间可以平分多少个空格，空格的余数则尽量给左侧的空格使用。

class Solution {

    private record Node(int lenCount, int num) {}

    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> ans = new ArrayList<>();
        Queue<Node> group = new ArrayDeque<>();
        int lenCount = 0, numCount = 0;
        int lastIndex = -1;
        for(int i = 0; i < words.length; i++) {
            if(lenCount + words[i].length() + numCount > maxWidth) {
                group.offer(new Node(lenCount, numCount));
                lenCount = words[i].length();
                numCount = 1;
            } else {
                lenCount += words[i].length();
                numCount++;
            }
        }
        group.offer(new Node(lenCount, numCount));
        int pos = 0;
        while(!group.isEmpty()) {
            Node node = group.poll();
            if(group.isEmpty() || node.num() == 1) {
                int len = 0;
                StringBuilder sb = new StringBuilder();
                for(int i = 0; i < node.num(); i++) {
                    if(i == 0) {
                        len += words[pos].length();
                        sb.append(words[pos]);
                    } else {
                        len += words[pos].length() + 1;
                        sb.append(" ").append(words[pos]);
                    }
                    pos++;
                }
                for(int i = 0; i < maxWidth - len; i++) sb.append(" ");
                ans.add(sb.toString());
            } else {
                final int spaceSize = (maxWidth - node.lenCount()) / (node.num() - 1);
                int spaceLeft = (maxWidth - node.lenCount()) % (node.num() - 1);
                StringBuilder sb = new StringBuilder();
                for(int i = 0; i < node.num(); i++) {
                    sb.append(words[pos]);
                    pos++;
                    if(i == node.num() - 1) break;
                    for(int j = 0; j < spaceSize; j++) sb.append(" ");
                    if(spaceLeft-- > 0) sb.append(" ");
                }
                ans.add(sb.toString());
            }
        }
        return Collections.unmodifiableList(ans);
    }
}

验证回文串

AC思路 & 官方最优解

双指针，判断两个指针的字符是否相同，直到两指针相遇。注意需要忽略掉不符合题目要求的字符。

时间复杂度O(n)，空间复杂度O(1)。

class Solution {

    private boolean check(char c) {
        return (c >= 'a' && c <= 'z') || (c >= '0' && c <= '9');
    }

    public boolean isPalindrome(String s) {
        s = s.toLowerCase();
        final int n = s.length();
        int p = 0, q = n - 1;
        while(p < q) {
            while(p < q && !check(s.charAt(p))) p++;
            while(p < q && !check(s.charAt(q))) q--;
            if(s.charAt(p) != s.charAt(q)) return false;
            p++;
            q--;
        }
        return true;
    }
}

判断子序列

AC思路 & 官方最优解

维护一个指针p代表当前t遍历到的位置。依次从s中取字符，判断是否存在于从p开始的t的后缀串中。如果s的所有字符都能这样取到则说明可以。

对于一次判断来说，时间复杂度O(m + n)，空间复杂度O(1)。

class Solution {
    public boolean isSubsequence(String s, String t) {
        int p = 0;
        for(int i = 0; i < s.length(); i++) {
            while(p < t.length() && s.charAt(i) != t.charAt(p)) p++;
            if(p == t.length()) return false;
            p++;
        }
        return true;
    }
}

以上算法在请求次数不多时性能较好，但如果请求次数非常多时则会因为每次都现场在t上寻找字符的后继而浪费时间，可以先使用t预处理一下信息，后续请求则可以复用这个信息。设dp[i][j]代表以i开头的后缀串中字符为j所在的下标，如果不存在字符j，则值设置为-1。对于t[i]来说，如果j == t[i]那么dp[i][j] = i，否则dp[i][j] = dp[i + 1][j]。

预处理字符串t的时间复杂度为O(n * 26)，空间复杂度为O(n * 26)，其中n为t的长度。之后每次请求处理s（且t命中了预处理过的缓存）所需要的时间复杂度是O(n)，其中n为s的长度。

class Solution {

    final Map<String, int[][]> map = new HashMap<>();

    private int[][] getOrCal(String t) {
        if(map.containsKey(t)) return map.get(t);
        final int m = t.length();
        int[][] dp = new int[m][26];
        for(int i = m - 1; i >= 0; i--) {
            for(int j = 0; j < 26; j++) {
                if(t.charAt(i) == 'a' + j) {
                    dp[i][j] = i;
                } else if(i == m - 1) {
                    dp[i][j] = -1;
                } else {
                    dp[i][j] = dp[i + 1][j];
                }
            }
        }
        map.put(t, dp);
        return dp;
    }

    public boolean isSubsequence(String s, String t) {
        int[][] dp = getOrCal(t);
        int p = 0;
        for(int i = 0; i < s.length(); i++) {
            if(p == t.length()) return false;
            int offset = s.charAt(i) - 'a';
            p = dp[p][offset];
            if(p == -1) return false;
            p++;
        }
        return true;
    }
}

两数之和 II - 输入有序数组

AC思路

看到有序就要想到二分。这题可以先确定一个位置，然后使用二分去寻找目标是否在后面的数组中即可。

时间复杂度O(nlogn)，空间复杂度O(1)。

class Solution {

    private int find(final int[] num, final int val, final int start, final int end) {
        int l = start, r = end;
        while(l < r) {
            int mid = (l + r) >> 1;
            if(num[mid] == val) return mid;
            else if(num[mid] < val) l = mid + 1;
            else r = mid;
        }
        return -1;
    }

    public int[] twoSum(int[] numbers, int target) {
        final int n = numbers.length;
        for(int i = 0; i < n; i++) {
            int p = find(numbers, target - numbers[i], i + 1, n);
            if(p != -1) {
                return new int[]{i + 1, p + 1};
            }
        }
        throw new IllegalArgumentException("数据不符合题目要求，做个🥚！");
    }
}

官方最优解

使用两个指针，初始的时候分别指向数组的第一个元素和最后一个元素。由于数组是非递减的，左指针右移一定会使得两个指针指向的元素和变大或者不变，右指针左移一定会使得两个指针指向的元素和变小或者不变。因此可以每次比较两个指针的元素和以及目标值的关系，移动指针直到两个指针相遇。

时间复杂度O(n)，空间复杂度O(1)。

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        final int n = numbers.length;
        int p1 = 0, p2 = n - 1;
        while(p1 < p2) {
            if(numbers[p1] + numbers[p2] == target) {
                return new int[]{p1 + 1, p2 + 1};
            } else if(numbers[p1] + numbers[p2] < target) {
                p1++;
            } else {
                p2--;
            }
        }
        return new int[]{-1, -1};
    }
}

盛最多水的容器

AC思路 & 官方最优解

使用双指针，最初时指向数组的第一个元素和最后一个元素。每次在移动指针的时候，移动较矮的那个指针。这是因为每一次区间面积都是由较矮的指针决定的，如果移动较高的指针，则新形成的空间面积一定小于等于刚才形成的空间面积，而移动矮指针则有可能让新形成的空间面积大于原来形成的空间面积，因为移动后的矮指针可能比原来的高指针还要高，使得原来的高指针变成了短板。

时间复杂度O(n)，空间复杂度O(1)。

class Solution {
    public int maxArea(int[] height) {
        final int n = height.length;
        int p1 = 0, p2 = n - 1;
        int ans = 0;
        while(p1 < p2) {
            ans = Math.max(ans, (p2 - p1) * Math.min(height[p1], height[p2]));
            if(height[p1] < height[p2]) p1++;
            else p2--;
        }
        return ans;
    }
}

三数之和

首先要对输入的数组进行一下排序，然后每次枚举第一个元素，剩下的部分就可以用双指针按照有序两数之和来寻找。不过需要解决答案重复的问题。首先第一个元素应该每次都使用不一样的值，因为如果第二次循环使用和第一个一样的值，则会得到上次解集的子集。之后再使用双指针求解两数之和的时候，要保证j指针指向的元素也为重复元素的第一个元素（注意子数组应该为[i + 1, n)的范围），由于第一个元素和第二个元素都已经被确定了，那么第三个元素的值也会被确定，直接从数组末尾寻找即可。

时间复杂度O(n2)，空间复杂度O(n)。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        nums = Arrays.copyOf(nums, nums.length);
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        final int n = nums.length;
        for(int i = 0; i < n; i++) {
            while(i != 0 && i < n && nums[i] == nums[i - 1]) i++;
            if(i == n) break;
            int j = i + 1;
            int k = n - 1;
            while(j < k) {
                while(j != i + 1 && j < k && nums[j] == nums[j - 1]) j++;
                while(j < k && nums[j] + nums[k] > -nums[i]) k--;
                if(j >= k) break;
                if(nums[j] + nums[k] == -nums[i]) {
                    ans.add(List.of(nums[i], nums[j], nums[k]));
                }
                j++;
            }
        }
        return Collections.unmodifiableList(ans);
    }
}

长度最小的子数组

AC思路 & 官方最优解

使用滑动窗口，每一次都尝试将右面的元素加入到窗口，直到窗口内的和满足了要求，然后尝试从左面移除元素缩小窗口，直到窗口内的和不满足要求。重复这个过程直到右面没有元素。

时间复杂度O(n)，空间复杂度O(1)。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        final int n = nums.length;
        int l = 0, r = 0;
        int sum = 0;
        int ans = n + 1;
        while(r <= n) {
            while(l < r && sum >= target) {
                ans = Math.min(ans, r - l);
                sum -= nums[l++];
            }
            if(sum < target && r == n) break;
            while(r < n && sum < target) sum += nums[r++];
        }
        return ans == n + 1 ? 0 : ans;
    }
}

无重复字符的最长子串

AC思路 & 官方最优解

滑动窗口，每次都尝试将右面的新字符加入到窗口中，如果无法加入则不断的将左侧元素从窗口中移除。

时间复杂度O(n)，空间复杂度为哈希表的占用。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        final int n = s.length();
        int l = 0, r = 0;
        Set<Character> set = new HashSet<>();
        int ans = 0;
        while(r < n) {
            while(l < r && set.contains(s.charAt(r))) {
                set.remove(s.charAt(l++));
            }
            while(r < n && !set.contains(s.charAt(r))) {
                set.add(s.charAt(r++));
                ans = Math.max(ans, r - l);
            }
        }
        return ans;
    }
}

串联所有单词的子串

AC思路 & 官方最优解

设字符串s的长度为n，字符串数组的长度为m，字符串数组每一个字符串长度为k。满足题目要求的子字符串的长度一定为mk，因此可以把字符串s以k为单位进行分割，从索引0到索引k-1开始进行分割操作。之后可以在分割的字符串数组上做滑动窗口，看新加进来的字符串是否是words中存在的，如果在原数组中根本不存在，则窗口长度直接回退到0，因为包含该字符串的子串一定不满足答案。若新加进来的字符串确实在words中存在，但次数已被使用完毕，则移动左指针，尝试缩短窗口。当窗口的长度为mk时则匹配到一个答案。

时间复杂度O(nk)，空间复杂度O(mk)。

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        final int n = s.length();
        final int m = words.length;
        final int k = words[0].length();
        List<Integer> ans = new ArrayList<>();
        Map<String, Integer> wordMap = new HashMap<>();
        for (String word : words) {
            wordMap.compute(word, (ke, v) -> v == null ? 1 : v + 1);
        }
        wordMap = Collections.unmodifiableMap(wordMap);
        for(int offset = 0; offset < k; offset++) {
            List<String> subStrs = new ArrayList<>();
            for(int i = offset; i < n && i + k <= n; i += k) {
                subStrs.add(s.substring(i, i + k));
            }
            int l = 0, r = 0;
            Map<String, Integer> diffMap = new HashMap<>(wordMap);
            int cnt = m;
            while(r < subStrs.size()) {
                while(r < subStrs.size() && cnt > 0) {
                    if(diffMap.getOrDefault(subStrs.get(r), 0) > 0) {
                        diffMap.compute(subStrs.get(r), (ke, v) -> v - 1);
                        r++;
                        cnt--;
                    } else {
                        if(!wordMap.containsKey(subStrs.get(r))) {
                            while(r < subStrs.size() && !wordMap.containsKey(subStrs.get(r))) r++;
                            l = r;
                            cnt = m;
                            diffMap = new HashMap<>(wordMap);
                        }
                        while(l < r && diffMap.getOrDefault(subStrs.get(r), 0) == 0) {
                            diffMap.compute(subStrs.get(l), (ke, v) -> v + 1);
                            l++;
                            cnt++;
                        }
                    }
                }
                if(cnt == 0) {
                    ans.add(offset + l * k);
                    diffMap.compute(subStrs.get(l), (ke, v) -> v + 1);
                    l++;
                    cnt++;
                }
            }
        }
        return ans;
    }
}

有效的数独

AC思路 & 官方最优解

按要求判断就是了，时空复杂度与输入数组的大小有关，本题固定为9x9，因此可以看作是O(1)。

class Solution {

    public boolean isValidSudoku(char[][] board) {
        final boolean[][] row = new boolean[9][10];
        final boolean[][] col = new boolean[9][10];
        final boolean[][] rid = new boolean[9][10];
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                if(board[i][j] == '.') continue;
                int v = board[i][j] - '0';
                if(row[i][v] || col[j][v] || rid[(i / 3) * 3 + (j / 3)][v]) {
                    return false;
                }
                row[i][v] = true;
                col[j][v] = true;
                rid[(i / 3) * 3 + (j / 3)][v] = true;
            }
        }
        return true;
    }
}

螺旋矩阵

AC思路 & 官方最优解

可以用分治的思路，每一次只处理最外围一圈，然后就成为一个一模一样的子问题。注意要特殊判断二维数组行或者列为1的情况。

时间复杂度O(mn)，空间复杂度O(1)。

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        final int n = matrix.length;
        final int m = matrix[0].length;
        int row = 0, col = 0;
        while(row * 2 < n && col * 2 < m) {
            if(row == n - row - 1) {
                for(int j = col; j < m - col; j++) {
                    ans.add(matrix[row][j]);
                }
                break;
            } else if(col == m - col - 1) {
                for(int i = row; i < n - row; i++) {
                    ans.add(matrix[i][col]);
                }
                break;
            }
            for(int j = col; j < m - col; j++) {
                ans.add(matrix[row][j]);
            }
            for(int i = row + 1; i < n - row; i++) {
                ans.add(matrix[i][m - col - 1]);
            }
            for(int j = m - col - 2; j >= col; j--) {
                ans.add(matrix[n - row - 1][j]);
            }
            for(int i = n - row - 2; i > row; i--) {
                ans.add(matrix[i][col]);
            }
            row++;
            col++;
        }
        return Collections.unmodifiableList(ans);
    }
}

旋转图像

AC思路 & 官方最优解

可以从任意一个元素开始，尝试移动到它应该在的位置，然后把被占据格子的元素再移动。可以发现这样的移动规律是以4个元素为一组的，也就是在(i, j)位置的元素，会被移动到(j, n - i - 1)处。接下来考虑分组，当n为偶数的时候，n * n / 4可以被整除，也就是枚举0 - n / 2行0 - n / 2列的元素进行操作即可；当n为奇数时，可以发现其中心是不需要旋转的，[(n * n) - 1] / 4 == (n - 1) * (n + 1) / 4可以被整除，也就是枚举0 - (n - 1) / 2行0 - (n + 1) / 2列的元素进行操作。编码时可以直接借助整除的性质，以跳过n的奇偶性的判断。

时间复杂度O(mn)，空间复杂度O(1)。

class Solution {
    public void rotate(int[][] matrix) {
        // (i, j) -> (j, n - i - 1)
        // (j, n - i - 1) -> (n - i - 1, n - j - 1)
        // (n - i - 1, n - j - 1) -> (n - j - 1, i)
        // (n - j - 1, i) -> (i, j)
        final int n = matrix.length;
        for(int i = 0; i < (n + 1) / 2; i++) {
            for(int j = 0; j < n / 2; j++) {
                int t = 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] = t;
            }
        }
    }
}

矩阵置零

AC思路 & 官方最优解

最直观的想法就是开两个数组，用来存储行状态和列状态，然后再根据状态数组进行操作。为了节省状态数组这部分内存，我们可以直接先提前记录一下第一行和第一列是否需要被处理的状态，然后再拿第一行和第一列的空间作为子二维数组的状态数组进行记录行列状态，最后再根据提前记录的两个标志变量判断第一行和第一列是否需要处理。

时间复杂度O(mn)，空间复杂度O(1)。

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

生命游戏

AC思路 & 官方最优解

由于输入数组只有0和1，所以我们可以自定义额外的状态，比如定义2是打赢复活赛的细胞，3是突然寄了的细胞。这样我们在遍历到某个细胞时确定周围八个格子细胞原来状态的时候，就可以把状态1和3当作存活细胞。处理完之后再把状态2和3变成1和0即可。

时间复杂度为O(mn)，空间复杂度为O(1)。

class Solution {

    private int lifeCell(int[][] board, int i, int j, int n, int m) {
        int cnt = 0;
        for(int dx = -1; dx <= 1; dx++) {
            for(int dy = -1; dy <= 1; dy++) {
                if(dx == 0 && dy == 0) continue;
                int x = i + dx;
                int y = j + dy;
                if(x < 0 || x >= n || y < 0 || y >= m) continue;
                if(board[x][y] == 1 || board[x][y] == 3) cnt++;
            } 
        }
        return cnt;
    }

    public void gameOfLife(int[][] board) {
        // 0 dead, 1 life
        // 2 dead -> life
        // 3 life -> dead
        final int n = board.length;
        final int m = board[0].length;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                int cnt = lifeCell(board, i, j, n, m);
                if(board[i][j] == 0 && cnt == 3) board[i][j] = 2;
                else if(board[i][j] == 1 && (cnt < 2 || cnt > 3)) board[i][j] = 3;
            }
        }
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(board[i][j] == 2) board[i][j] = 1;
                else if(board[i][j] == 3) board[i][j] = 0;
            }
        }
    }
}

赎金信

AC思路 & 官方最优解

用哈希表记录第二个串的每个字符的数量，然后遍历第一个字符串的字符。

时间复杂度O(m + n)，空间复杂度为哈希表的占用，本题字符种类很少，可以看作是O(1)。

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character, Integer> map = new HashMap<>();
        for(int i = 0; i < magazine.length(); i++) {
            map.compute(magazine.charAt(i), (k, v) -> v == null ? 1 : v + 1);
        }
        for(int i = 0; i < ransomNote.length(); i++) {
            Integer cnt = map.get(ransomNote.charAt(i));
            if(cnt == null || cnt == 0) return false;
            map.put(ransomNote.charAt(i), cnt - 1);
        }
        return true;
    }
}

同构字符串

AC思路

对于本题目，如果字符串A与字符串B满足题目所述的同构关系，字符串B与字符串C同构，则可以推导出A与C同构。因此我们可以构造这么一个模式串C，C中第一个字符为ASCII的'\0'，每次新出现的字符都是已出现过的最大字符的后继字符。然后判断两个输入串转换后是否是同一个字符串即可。

时间复杂度和空间复杂度都是O(m + n)，其中m和n为两个字符串的长度。

class Solution {

    private String simpify(String s) {
        Map<Character, Character> map = new HashMap<>();
        char sp = '\0';
        StringBuilder sb = new StringBuilder();
        final int n = s.length();
        for(int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if(!map.containsKey(c)) {
                map.put(c, sp++);
            }
            sb.append(map.get(c));
        }
        return sb.toString();
    }

    public boolean isIsomorphic(String s, String t) {
        return simpify(s).equals(simpify(t));
    }
}

官方最优解

如果串A同构于B，那么串B同构于A。可以发现两个字符串需要长度相同且每一个字符都构成双射关系。因此可以用两个哈希表来维护映射关系，如果遍历字符串时发现无法满足先前的映射关系则说明两个字符串不同构。

时间复杂度O(m + n)，空间复杂度O(1)。

class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character, Character> hs = new HashMap<>();
        Map<Character, Character> ht = new HashMap<>();
        final int n = s.length();
        if(n != t.length()) return false;
        for(int i = 0; i < n; i++) {
            char cs = s.charAt(i);
            char ct = t.charAt(i);
            if(hs.containsKey(cs) && ht.containsKey(ct)) {
                if(hs.get(cs) != ct || ht.get(ct) != cs) {
                    return false;
                }
            } else if(hs.containsKey(cs) || ht.containsKey(ct)) {
                return false;
            } else {
                hs.put(cs, ct);
                ht.put(ct, cs);
            }
        }
        return true;
    }
}

单词规律

AC思路 & 官方最优解

这道题目与上一个题目一样，字符和单词字符串构成双射关系。

时间复杂度O(m + n)，空间复杂度O(m + n)。

class Solution {

    public boolean wordPattern(String pattern, String s) {
        String[] arr = s.split(" ");
        if(pattern.length() != arr.length) return false;
        final int n = arr.length;
        Map<Character, String> map1 = new HashMap<>();
        Map<String, Character> map2 = new HashMap<>();
        for(int i = 0; i < n; i++) {
            char c = pattern.charAt(i);
            String t = arr[i].trim();
            if(map1.containsKey(c) && map2.containsKey(t)) {
                if(!map1.get(c).equals(t) || map2.get(t) != c) {
                    return false;
                }
            } else if(map1.containsKey(c) || map2.containsKey(t)) {
                return false;
            } else {
                map1.put(c, t);
                map2.put(t, c);
            }
        }
        return true;
    }
}

有效的字母异位词

AC思路 & 官方最优解

记录每一个字符出现的次数，然后比对字符串a中每个字符的频次是否与b中一致，以及字符串b中每个字符频次是否与a中一致。可以在比较前先看一下字符串是否长度相同，这样可以省略一次比较。为了兼容Unicode字符，在Java中使用码点（CodePoint）代替字符（Char）。

时间复杂度O(m + n)，空间复杂度O(1)。

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()) return false;
        Map<Integer, Integer> map1 = new HashMap<>();
        Map<Integer, Integer> map2 = new HashMap<>();
        s.codePoints().forEach(cp -> map1.compute(cp, (k, v) -> v == null ? 1 : v + 1));
        t.codePoints().forEach(cp -> map2.compute(cp, (k, v) -> v == null ? 1 : v + 1));
        for(var e : map1.entrySet()) {
            if(!map2.getOrDefault(e.getKey(), 0).equals(e.getValue())) {
                return false;
            }
        }
        return true;
    }
}

字母异位词分组

AC思路 & 官方最优解

用哈希表记录每一个字符串中每一个字符出现的频次，然后把这个哈希表当作这个字符串的特征，如果两个字符串的字符统计哈希表一致的话，则放到一个分组。官方题解是把一个字符串转换为一个特征字符串，其原理相同。

时间和空间复杂度O(mn)。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<Set<Map.Entry<Character, Integer>>, List<String>> ansMap = new HashMap<>();
        for(String s : strs) {
            Map<Character, Integer> map = new HashMap();
            s.chars().forEach(i -> map.compute((char) i, (k, v) -> v == null ? 1 : v + 1));
            final String fs = s;
            ansMap.compute(map.entrySet(), (k, v) -> {
                List<String> ans = v == null ? new ArrayList<>() : v;
                ans.add(fs);
                return ans;
            });
        }
        return List.copyOf(ansMap.values());
    }
}

两数之和

AC思路 & 官方最优解

使用哈希表，维护之前已经出现过的元素的索引，然后判断哈希表中是否存在target - nums[i]，如果存在则找到了答案。哈希表用Map<Integer, Integer>而不是用Map<Integer, List<Integer>>，是因为题目要求只找到一组答案即可，且当前位置nums[i]的信息没有存放在哈希表中，即使target - nums[i] == nums[i]且map.get(nums[i]) != null，那么仍然有map.get(nums[i]) != i。

时间复杂度O(n)，空间复杂度O(n)。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            if(map.containsKey(target - nums[i])) {
                return new int[]{map.get(target - nums[i]), i};
            }
            map.put(nums[i], i);
        }
        return null;
    }
}

快乐数

AC思路 & 官方最优解

即使拿一个大的数字9999999999（已经超过了int上限）进行一次操作，结果仍然为一个比较小的数字810，这说明我们可以直接模拟题目定义的方式，去找下一个数字，直到遇见1或者之前出现过的数字。如果把数字n经过题目这样的操作记作func(n)，那么就可以把func(n)看作是n的后继，因此会有一个逻辑链表，题目转换为判断这样的链表是否存在环，可以使用快慢指针判断。

时间复杂度O(logn)，空间复杂度O(1)。

class Solution {

    private int func(int n) {
        int ans = 0;
        while(n > 0) {
            ans += (n % 10) * (n % 10);
            n /= 10;
        }
        return ans;
    }

    public boolean isHappy(int n) {
        int p1 = n, p2 = n;
        do {
            p1 = func(p1);
            p2 = func(func(p2));
        } while(p1 != p2);
        return p2 == 1;
    }
}

存在重复元素 II

AC思路 & 官方最优解

使用哈希表维护某个数字最后出现的索引位置是多少，然后拿当前位置索引与最后出现的位置做差，看是否小于等于k即可。

时间复杂度和空间复杂度都为O(n)。

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            if(!map.containsKey(nums[i]) || i - map.get(nums[i]) > k) {
                map.put(nums[i], i);
            } else if(i - map.get(nums[i]) <= k) {
                return true;
            }
        }
        return false;
    }
}

汇总区间

AC思路 & 官方最优解

题目明确数组有序，直接模拟即可。时间复杂度O(n)，空间复杂度O(1)。

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> ans = new ArrayList<>();
        final int n = nums.length;
        for(int i = 0; i < n;) {
            int p = i + 1;
            while(p < n && nums[p] == nums[p - 1] + 1) p++;
            p--;
            ans.add(i == p ? "" + nums[i] : nums[i] + "->" + nums[p]);
            i = p + 1;
        }
        return ans;
    }
}

有效的括号

AC思路 & 官方最优解

括号序列的验证一般都可以使用栈来解决。当遇见左括号时，则把左括号入栈；遇见右括号时则看是否与栈顶的左括号匹配，如果不匹配则说明为非法括号序列。最后遍历完需要注意，当栈为空时才为合法序列。由于栈的原理比较简单且最大栈长已知，用Java编写代码可以直接用基本类型数组模拟，省去拆箱和包箱的消耗。

时间复杂度和空间复杂度都是O(n)。

class Solution {
    public boolean isValid(String s) {
        final int n = s.length();
        char[] stack = new char[n];
        int top = -1;
        for(int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if(c == '(' || c == '{' || c == '[') {
                stack[++top] = c;
            } else if(top >= 0 && (
                        (c == ')' && stack[top] == '(') ||
                        (c == '}' && stack[top] == '{') ||
                        (c == ']' && stack[top] == '['))
                ) {
                top--;
            } else {
                return false;
            }
        }
        return top == -1;
    }
}

简化路径

AC思路 & 官方最优解

可以先将字符串按照分隔符进行分割成字符串数组（正则表达式/+），然后遍历字符串数组，当遇见空串或者.时则跳过，遇见..时移除栈顶元素（栈非空时），遇见其他字符串时则推进栈顶。在Java中可以使用双端队列Deque来实现栈，Deque#pollLast在队列为空时返回null而不是抛出异常，因此我们可以在编码时不对队列进行判空，~~不过写上可以体现出思维的严谨度。~~

时间复杂度和空间复杂度都是O(n)。

class Solution {
    public String simplifyPath(String path) {
        String[] paths = path.split("/+");
        Deque<String> stack = new ArrayDeque<>();
        for(String p : paths) {
            if(p.isEmpty() || ".".equals(p)) {
                continue;
            }
            else if("..".equals(p)) {
                if(!stack.isEmpty()) stack.pollLast();
            } else {
                stack.offerLast(p);
            }
        }
        return "/" + stack.stream().collect(Collectors.joining("/"));
    }
}

最小栈

AC思路 & 官方最优解

引入一个单调不递增的栈，当一个新的元素被放入栈中，跟这个栈顶元素比较大小，如果小于当前的最小值，说明当前元素是新的最小值，放入这个栈中；否则仍然把该栈的栈顶元素重新放入栈中，以维护两个栈的大小相同。原栈栈顶就是当前元素，最小栈栈顶就是当前栈中最小元素。

每次操作的时间复杂度和空间复杂度都是O(1)。

class MinStack {

    private final Deque<Integer> stack;
    private final Deque<Integer> minStack;

    public MinStack() {
        stack = new ArrayDeque<>();
        minStack = new ArrayDeque<>();
    }
    
    public void push(int val) {
        stack.offerLast(val);
        if(minStack.isEmpty() || val < minStack.peekLast()) {
            minStack.offerLast(val);
        } else {
            minStack.offerLast(minStack.peekLast());
        }
    }
    
    public void pop() {
        stack.pollLast();
        minStack.pollLast();
    }
    
    public int top() {
        return stack.peekLast();
    }
    
    public int getMin() {
        return minStack.peekLast();
    }
}

逆波兰表达式求值

AC思路 & 官方最优解

直接按照要求模拟即可，当遇见符号时，从栈中取两个数字进行运算，运算结果再放入栈中，如果遇到数字则放入栈中。

时间复杂度和空间复杂度都为O(n)。

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
        for(String s : tokens) {
            if("+".equals(s)) {
                int y = stack.pollLast();
                int x = stack.pollLast();
                stack.offerLast(x + y);
            } else if("-".equals(s)) {
                int y = stack.pollLast();
                int x = stack.pollLast();
                stack.offerLast(x - y);
            } else if("*".equals(s)) {
                int y = stack.pollLast();
                int x = stack.pollLast();
                stack.offerLast(x * y);
            } else if("/".equals(s)) {
                int y = stack.pollLast();
                int x = stack.pollLast();
                stack.offerLast(x / y);
            } else {
                int x = Integer.valueOf(s);
                stack.offerLast(x);
            }
        }
        return stack.pollLast();
    }
}