面试经典 150 题-数组/字符串

LeetCode 面试经典 150 题-数组/字符串

移出元素

双指针

初始化左右指针指向首尾，如果右指针指向val，就不断左移，如果左指针指向val，就和右指针交换，然后左指针右移，右指针左移，直到两者相遇。最后left所指向的位置就是第一个为val的下标，也就是非val元素的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int removeElement(int[] nums, int val) {
        int n = nums.length;
        int left = 0, right = n - 1;
        while (left <= right) {
            // 右指针必须指向非val元素
            while (right >= left && nums[right] == val){
                right--;
            }
            // 左指针找到指向val的元素
            while (left <= right && nums[left] != val) {
                left++;
            }
            // 如果左指针小于等于右指针，说明可以交换
            if (left <= right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
            }
        }
        return left;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

优化：实际上我们并不在乎放到right位置的值是多少，所以可以将right的值赋值给left，然后更新right指针，而不用管right的值是多少。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int removeElement(int[] nums, int val) {
        int n = nums.length;
        int left = 0, right = n - 1;
        while (left <= right) {
            if (nums[left] == val) {
                nums[left] = nums[right];
                right--;
            } else {
                left++;
            }
        }
        return left;
    }
}

类似颜色分类时用到的方法

一边遍历，一边填入，k指向是为val的下标，i指向的是不为val的下标。

  1. 初始化要填入的下标 k=0。
  2. 从左到右遍历 nums，如果 nums[i]!=val，则更新 nums[k]=nums[i]，然后把 k 加一。
  3. 遍历结束，返回 k。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int removeElement(int[] nums, int val) {
        int n = nums.length;
        int k = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] != val) {
                nums[k++] = nums[i];
            }
        }
        return k;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

删除有序数组中的重复项

双指针

  1. 初始化指针k指向0，i用来遍历。
  2. 如果nums[i] != nums[k]，先k++，再交换两元素，然后继续遍历。
  3. 最后返回k+1。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        int k = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] != nums[k]) {
                k++;
                nums[k] = nums[i];
            }
        }
        return k + 1;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

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

双指针

  1. 处理特殊情况，n<2可以直接返回。
  2. 初始化左右指针都为2，枚举右指针。
  3. 如果nums[left-2]!=nums[right]，就可以更新nums[left]，然后左指针左移。
  4. 最后返回left。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return n;
        }

        int left = 2;
        for (int right = 2; right < n; right++) {
            if (nums[left-2] != nums[right]) {
                nums[left++] = nums[right];
            }
        }
        
        return left;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

对于上面的题目可以总结为：左指针永远指向待更新的位置，右指针枚举每一个元素，当满足条件时，就将右指针元素放在左指针位置，然后左指针右移。

轮转数组

反转

先将数组反转，然后反转数组的前k的数，再反转后n-k个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;  // n次旋转就会旋转到最初的数组
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }

    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

H指数

排序

首先我们可以将初始的 H 指数 h 设为 0，然后将引用次数排序，并且对排序后的数组从大到小遍历。

根据 H 指数的定义，如果当前 H 指数为 h 并且在遍历过程中找到当前值 citations[i]>h，则说明我们找到了一篇被引用了至少 h+1 次的论文，所以将现有的 h 值加 1。继续遍历直到 h 无法继续增大。最后返回 h 作为最终答案。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int h = 0, i = citations.length - 1;
        while (i >= 0 && citations[i] > h) {
            h++;
            i--;
        }
        return h;
    }
}
  • 时间复杂度：O(nlogn)
  • 空间复杂度：O(logn)

计数排序

设 n 为 citations 的长度，即这名研究者发表的论文数。根据题意，h 不可能超过 n，所以对于引用次数大于 n 的论文，我们在统计的时候，可以看成是引用次数等于 n 的论文。

创建一个长为 n+1 的 cnt 数组，统计 min(citations[i],n) 的出现次数。设 s 为引用次数 ≥i 的论文数，我们需要算出满足 s≥i 的最大的 i。

从 i=n 开始倒序循环，每次循环，把 cnt[i] 加到 s 中。由于我们是倒序循环的，只要 s≥i 成立，此时的 i 就是满足 s≥i 的最大的 i，直接返回 i 作为答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int hIndex(int[] citations) {
        // 计算引用次数为i的文章数
        int n = citations.length;
        int[] cnt = new int[n + 1]; // 最多引用次数为n，因为即使大于n，h也不可能大于n
        for (int citation : citations) {
            cnt[Math.min(citation, n)]++;
        }
        // 从后向前找到最大的文章数（文章数要大于等于引用次数）
        int s = 0;
        for (int i = n; ; i--) {
            s += cnt[i];    // 引用次数大于等于i的文章数
            if (s >= i) {
                return i;
            }
        }
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

二分查找

设查找范围的初始左边界 left 为 0，初始右边界 right 为 n。每次在查找范围内取中点 mid，同时扫描整个数组，判断是否至少有 mid 个数大于 mid。如果有，说明要寻找的 h 在搜索区间的右边，反之则在左边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int left = 0, right = n;    
        // 二分查找
        while (left < right) {
            int mid = (left + right + 1) >> 1;
            // 统计大于等于引用次数mid的文章数cnt
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                if (citations[i] >= mid) {
                    cnt++;
                }
            }
            // h还可能更大
            if (cnt >= mid) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}
  • 时间复杂度：O(nlogn)
  • 空间复杂度：O(1)

复习一下股票和跳跃游戏。

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

变长数组+哈希表

变长数组中存储元素，哈希表中存储每个元素在变长数组中的下标。

  • 插入：
    • 判断是否存在于哈希表，不存在则插入；
    • 插入变长数组末尾；
    • 将元素值和下标插入哈希表；
  • 删除：
    • 判断是否存在于哈希表，存在则获取其下标删除；
    • 将变长数组的最后一个元素 last 移动到下标 index 处，在哈希表中将 last 的下标更新为 index；
    • 在变长数组中删除最后一个元素，在哈希表中删除 val；
  • 获取随机数：
    • 限制下标范围在n以内；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class RandomizedSet {
    List<Integer> nums;
    Map<Integer, Integer> hash;
    Random random;

    public RandomizedSet() {
        nums = new ArrayList<Integer>();
        hash = new HashMap<Integer, Integer>();
        random = new Random();
    }
    
    public boolean insert(int val) {
        // 检查是否存在于哈希表
        if (hash.containsKey(val)) {
            return false;
        }
        // 插入
        int index = nums.size();
        nums.add(val);
        hash.put(val, index);
        return true;
    }
    
    public boolean remove(int val) {
        // 判断是否存在于哈希表中
        if (!hash.containsKey(val)) {
            return false;
        }
        // 删除
        int index = hash.get(val);
        int n = nums.size();
        int last = nums.get(n - 1);
        nums.set(index, last);
        hash.put(last, index);
        nums.remove(n - 1);
        hash.remove(val);
        return true;
    }
    
    public int getRandom() {
        int randomIndex = random.nextInt(nums.size());
        return nums.get(randomIndex);
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */
  • 时间复杂度：所有操作的时间复杂度都是O(1)
  • 空间复杂度：O(n)，存储元素的数组和哈希表需要 O(n) 的空间。

除自身以外数组的乘积

前缀积+后缀积

题目要求不能用除法，考虑前缀和的思想，prefix保存前缀积，suffix保存后缀积，对于每一个元素它最终的结果都是prefix[i] * suffix[i]。

  • prefix[i] = prefix[i-1] * nums[i-1]
  • suffix[i] = prefix[i+1] * nums[i+1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] prefix = new int[n];
        int[] suffix = new int[n];
        // 计算前缀积
        prefix[0] = 1;
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i-1] * nums[i-1];
        }
        // 计算后缀积
        suffix[n-1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            suffix[i] = suffix[i+1] * nums[i+1];
        }
        // 计算结果
        for (int i = 0; i < n; i++) {
            prefix[i] *= suffix[i];
        }
        return prefix;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

空间优化

由于输出数组不算在空间复杂度内，那么我们可以将前后缀数组用输出数组来计算。先把输出数组当作前缀数组来计算，然后再动态构造后缀数组得到结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];

        // 计算前缀积
        answer[0] = 1;
        for (int i = 1; i < n; i++) {
            answer[i] = answer[i-1] * nums[i-1];
        }
        // 计算后缀积的同时更新结果
        int suf = 1;
        for (int i = n - 1; i >= 0; i--) {
            answer[i] *= suf;
            suf *= nums[i];
        }

        return answer;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

复习昨天做的题目。

加油站

贪心

计算从每个站点出发能否完成一圈，找到最优的起点，避免直接从每个站点暴力判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int spare = 0;
        int minSpare = Integer.MAX_VALUE, minIndex = 0;

        for (int i = 0; i < n; i++) {
            spare += gas[i] - cost[i];
            if (spare < minSpare) {
                minSpare = spare;
                minIndex = i;
            }
        }

        return spare < 0 ? -1 : (minIndex + 1) % n;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

分发糖果

两次遍历

初始化答案数组每个都是1：

  • 当ratings[i] > ratings[i-1]时，第 i 个孩子的糖果数量比第i - 1个孩子的糖果数量多；
  • 当ratings[i] > ratings[i+1]时，第 i 个孩子的糖果数量比第i + 1个孩子的糖果数量多。

因此分别从左到右遍历一次，再从右向左遍历一次，更新状态方式：

  • 从左到右：如果ratings[i] > ratings[i-1]，则sweets[i] = sweets[i-1] + 1；
  • 从右到左：如果ratings[i] > ratings[i+1]，则sweets[i] = max(sweets[i], sweets[i+1] + 1)；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] sweets = new int[n];
        Arrays.fill(sweets, 1);

        // 左规则
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i-1]) {
                sweets[i] = sweets[i-1] + 1;
            }
        }
        // 右规则
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i+1]) {
                sweets[i] = Math.max(sweets[i], sweets[i+1] + 1);
            }
        }

        // 求和
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += sweets[i];
        }
        return ans;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

常数空间遍历

翻译了一下别人的python代码，不太理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int res = 1;  // 初始化结果为 1, 因为第一个孩子至少分配一个糖果
        int pre = 1;  // 记录当前递增区间的糖果数
        int desNum = 0;  // 记录递减区间的长度

        for (int i = 1; i < n; i++) {
            if (ratings[i] >= ratings[i-1]) {
                if (desNum > 0) {
                    res += (1 + desNum) * desNum / 2;
                    // 递减长度比先前值大,所以我们要把先前值补充
                    if (pre <= desNum) {
                        res += desNum- pre + 1;
                    }
                    pre = 1;
                    desNum = 0;
                }
                if (ratings[i] == ratings[i - 1]) {
                    pre = 1;
                } else {
                    pre += 1;
                }
                res += pre;
            } else {
                desNum++;
            }
        }
        if (desNum > 0) {
            res += ((1 + desNum) * desNum) / 2;
            if (pre <= desNum) {
                res += desNum - pre + 1;
            }
        }
        return res;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

复习接雨水等单调栈问题。

罗马数字转整数

分析

  • 设 x=s[i−1],y=s[i]，这是两个相邻的罗马数字。
  • 如果 x 的数值小于 y 的数值，那么 x 的数值要取相反数。例如 IV 中的 I 相当于 −1，CM 中的 C 相当于 −100。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    private static final Map<Character, Integer> ROMAN = Map.of(
        'I', 1,
        'V', 5,
        'X', 10,
        'L', 50,
        'C', 100,
        'D', 500,
        'M', 1000
    );

    public int romanToInt(String s) {
        int n = s.length();
        int ans = 0;
        for (int i = 1; i < n; i++){
            int x = ROMAN.get(s.charAt(i-1));
            int y = ROMAN.get(s.charAt(i));
            ans += x < y ? -x : x;
        }
        return ans + ROMAN.get(s.charAt(n-1));
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

整数转罗马数字

分析

硬编码：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    private static final String[][] R = new String[][]{
        {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"}, // 个位
        {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"}, // 十位
        {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"}, // 百位
        {"", "M", "MM", "MMM"}, // 千位
    };

    public String intToRoman(int num) {
        return R[3][num / 1000] + R[2][num / 100 % 10] + R[1][num / 10 % 10] + R[0][num % 10];
    }
}
  • 时间复杂度：O(1)
  • 空间复杂度：O(1)

最后一个单词的长度

分析

从后往前找到第一个不为空格的字符，从此开始计数，然后找到为空格的位置，计数结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int lengthOfLastWord(String s) {
        int n = s.length();
        int ans = 0;
        int i = n - 1;
        while (s.charAt(i) == ' ') {
            i--;
        }
        // 单词起始
        while (i >= 0 && s.charAt(i) != ' ') {
            ans++;
            i--;
        }
        return ans;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

最长公共前缀

按列遍历

即外层循环枚举字符串的每一位，内层循环枚举每一个字符串，当遇到不符合条件的就可以直接返回结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public String longestCommonPrefix(String[] strs) {
        int n = strs.length;
        for (int i = 0; i < strs[0].length(); i++) {
            String s0 = strs[0];
            for (String s : strs) {
                if (i == s.length() || s.charAt(i) != s0.charAt(i)) {
                    return s.substring(0, i);
                }
            }
        }
        return strs[0];
    }
}
  • 时间复杂度：O(mn)
  • 空间复杂度：O(1)

反转字符串中的单词

分析

首先用replaceAll和trim方法去除多余的空格，然后逆转字符串，再按照逐个单词进行翻转。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public String reverseWords(String s) {
        // 去除多余空格，并将字符串转换为字符数组
        s = s.replaceAll("\\s+", " ").trim();
        char[] charArray = s.toCharArray(); // 将字符串转换为字符数组
        int n = charArray.length;
        
        // 反转整个字符串
        reverse(charArray, 0, n - 1);
        
        // 按空格进行反转每个单词
        int start = 0, end = 0;
        while (end < n) {
            if (charArray[end] == ' ') {
                reverse(charArray, start, end - 1);
                start = end + 1;
            }
            end++;
        }
        
        // 反转最后一个单词
        reverse(charArray, start, n - 1);
        
        return new String(charArray); // 将字符数组转换回字符串并返回
    }

    private void reverse(char[] charArray, int start, int end) {
        while (start < end) {
            // 交换字符
            char temp = charArray[start];
            charArray[start] = charArray[end];
            charArray[end] = temp;
            start++;
            end--;
        }
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

使用语言特性

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public String reverseWords(String s) {
        // 去除开头结尾空格
        s = s.trim();
        // 正则匹配空格作为分隔符
        List<String> wordList = Arrays.asList(s.split("\\s+"));
        // 反转
        Collections.reverse(wordList);
        // 拼接
        return String.join(" ", wordList);
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

双端队列

由于双端队列支持从队列头部插入的方法，因此我们可以沿着字符串一个一个单词处理，然后将单词压入队列的头部，再将队列转成字符串即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public String reverseWords(String s) {
        int n = s.length();
        // 去除开头结尾空格
        int left = 0, right = n - 1;
        while (left <= right && s.charAt(left) == ' ') {
            left++;
        }
        while (right >= left && s.charAt(right) == ' ') {
            right--;
        }
        // 定义双端队列
        Deque<String> que = new ArrayDeque<>();
        StringBuilder word = new StringBuilder();

        while (left <= right) {
            Character ch = s.charAt(left);
            if (word.length() != 0 && ch == ' ') {
                // push到头部
                que.offerFirst(word.toString());
                word.setLength(0);
            } else if (ch != ' ') {
                word.append(ch);
            }
            left++;
        }
        que.offerFirst(word.toString());

        return String.join(" ", que);
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

z字形变换

分析

模拟这个行索引的变化，在遍历 s 中把每个字符填到正确的行。

  1. res[i] += c： 把每个字符 c 填入对应行；
  2. i += flag： 更新当前字符 c 对应的行索引；
  3. flag = - flag： 在达到 Z 字形转折点时，执行反向。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public String convert(String s, int numRows) {
        // 处理边界
        if (numRows < 2) {
            return s;
        }
        int n = s.length();
        // 初始化数组
        List<StringBuilder> rows = new ArrayList<StringBuilder>();
        for (int i = 0; i < numRows; i++) {
            rows.add(new StringBuilder());
        }
        // 遍历字符串
        int r = 0, flag = -1;
        for (int i = 0; i < n; i++) {
            rows.get(r).append(s.charAt(i));
            // 变向
            if (r == 0 || r == numRows - 1) {
                flag = -flag;
            }
            // 更新row
            r += flag;
        }
        // 合并结果
        StringBuilder res = new StringBuilder();
        for (StringBuilder sb : rows) {
            res.append(sb);
        }
        return res.toString();
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

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

暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int strStr(String haystack, String needle) {
        int m = haystack.length();
        int n = needle.length();
        if (n > m) {
            return -1;
        }

        for (int i = 0; i + n <= m; i++) {
            if (haystack.substring(i, i + n).equals(needle)) {
                return i;
            }
        }

        return -1;
    }
}
  • 时间复杂度：O(mn)
  • 空间复杂度：O(1)

KMP算法

  • next[i] 表示在模式串的前 i 个字符中，模式串的前缀和后缀的最大匹配长度（不包括 i 本身）。
  • 当遇到不匹配的字符时，next 数组决定我们应当将模式串向右移动多少个字符，而不需要从头开始匹配。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0) {
            return 0; // 如果needle为空，返回0
        }

        int n = haystack.length();
        int m = needle.length();
        
        // next数组，长度为m
        int[] next = new int[m];
        
        // 计算next数组
        next[0] = 0;  // next[0]始终为0
        int j = 0;  // 模式串指针
        for (int i = 1; i < m; i++) {
            while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];  // 回退到next[j-1]
            }
            if (needle.charAt(i) == needle.charAt(j)) {
                j++;
            }
            next[i] = j;
        }

        // 开始匹配
        int i = 0;  // 文本串指针
        j = 0;  // 模式串指针
        while (i < n) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
                // 如果模式串完全匹配，返回起始位置
                if (j == m) {
                    return i - j;
                }
            } else {
                // 如果匹配失败，根据next数组跳转
                if (j != 0) {
                    j = next[j - 1];  // 回溯模式串的指针
                } else {
                    i++;  // 如果j为0，文本串指针前进
                }
            }
        }

        // 如果没有匹配，返回-1
        return -1;
    }
}
  • 时间复杂度：O(m + n)
  • 空间复杂度：O(m)，m为模式串的长度。

KMP不太好想，之后再看看好好理解一下，然后结合马拉车算法一起看一下。

文本左右对齐

贪心

  • 当前行是最后一行：单词左对齐，且单词之间应只有一个空格，在行末填充剩余空格；
  • 当前行不是最后一行，且只有一个单词：该单词左对齐，在行末填充空格；
  • 当前行不是最后一行，且不只一个单词：设当前行单词数为 numWords，空格数为 numSpaces，我们需要将空格均匀分配在单词之间，则单词之间应至少有$\frac{numSpaces}{numWords-1}$个空格。对于多出来的$extraSpaces=numSpacesmod(numWords−1)$个空格，应填在前 extraSpaces 个单词之间。因此，前 extraSpaces 个单词之间填充 avgSpaces+1 个空格，其余单词之间填充 avgSpaces 个空格。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> result = new ArrayList<>();
        int index = 0;
        
        // 遍历每个单词
        while (index < words.length) {
            // lineStart 和 index 标记当前行的起始和结束单词
            int lineStart = index;
            int lineLength = 0;

            // 每次确定一行能容纳的单词数量
            while (index < words.length && lineLength + words[index].length() + (index - lineStart) <= maxWidth) {
                lineLength += words[index].length();
                index++;
            }

            // Build the line
            StringBuilder line = new StringBuilder();
            int numWords = index - lineStart;
            int totalSpaces = maxWidth - lineLength;

            // 特殊处理最后一行或单词只有一个的行
            if (index == words.length || numWords == 1) {
                for (int i = lineStart; i < index; i++) {
                    line.append(words[i]);
                    if (i < index - 1) {
                        line.append(" ");
                    }
                }
                while (line.length() < maxWidth) {
                    line.append(" ");
                }
            } else {
                // 常规行的空格分配
                int spacesPerWord = totalSpaces / (numWords - 1);
                int extraSpaces = totalSpaces % (numWords - 1);

                for (int i = lineStart; i < index; i++) {
                    line.append(words[i]);
                    if (i < index - 1) {
                        for (int j = 0; j < spacesPerWord; j++) {
                            line.append(" ");
                        }
                        if (extraSpaces > 0) {
                            line.append(" ");
                            extraSpaces--;
                        }
                    }
                }
            }

            result.add(line.toString());
        }

        return result;
    }
}
  • 时间复杂度：O(m)，其中 m 是数组 words 中所有字符串的长度之和。
  • 空间复杂度：O(m)

总结

字符串的很多题目并不难，但具体分析起来会有多种情况，每一种思考起来并不容易，只能多做多复习。

算法笔记 > 数组
#数组 #双指针 #贪心
面试经典 150 题-数组/字符串
http://example.com/2024/12/25/posts/hot150-1/
作者
Xuan Yang
发布于
2024年12月25日
许可协议