数组 / 字符串

数组 and 字符串是面试中最基础也是考察频率最高的部分。常用技巧包括双指针、原地修改、前缀积、状态机等。

88. 合并两个有序数组 (Merge Sorted Array)

题目描述

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的有效元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意： 最终合并后的数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

解题思路

逆向双指针。从数组末尾开始比较，谁大就放到 nums1 的最后。这样可以避免额外的空间开销。

Java 代码实现

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1, j = n - 1, k = m + n - 1;
        while (i >= 0 && j >= 0) {
            nums1[k--] = nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
        }
        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }
}

---

27. 移除元素 (Remove Element)

题目描述

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

解题思路

快慢指针。fast 遍历数组，如果 nums[fast] != val，将其赋值给 nums[slow] 并移动 slow。

Java 代码实现

class Solution {
    public int removeElement(int[] nums, int val) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != val) {
                nums[slow++] = nums[fast];
            }
        }
        return slow;
    }
}

---

26. 删除有序数组中的重复项 (Remove Duplicates from Sorted Array)

题目描述

给你一个 非递减有序 数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的相对顺序应该保持一致。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

1. 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
2. 返回 k 。

解题思路

快慢指针。如果 nums[fast] != nums[slow]，令 slow = slow + 1 并更新 nums[slow] = nums[fast]。

Java 代码实现

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        int slow = 0;
        for (int fast = 1; fast < nums.length; fast++) {
            if (nums[fast] != nums[slow]) {
                nums[++slow] = nums[fast];
            }
        }
        return slow + 1;
    }
}

---

80. 删除有序数组中的重复项 II (Remove Duplicates from Sorted Array II)

题目描述

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素 最多出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。

解题思路

快慢指针。判断 nums[fast] 是否与 nums[slow - 2] 相等。如果不等，则可以放入 nums[slow]。

Java 代码实现

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length <= 2) return nums.length;
        int slow = 2;
        for (int fast = 2; fast < nums.length; fast++) {
            if (nums[fast] != nums[slow - 2]) {
                nums[slow++] = nums[fast];
            }
        }
        return slow;
    }
}

---

169. 多数元素 (Majority Element)

题目描述

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

解题思路

摩尔投票法 (Boyer-Moore)。维护一个候选人 candidate 和计数器 count。遍历数组，如果 count 为 0，更新候选人为当前数。如果当前数等于候选人，count++，否则 count--。

Java 代码实现

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = nums[0], count = 0;
        for (int num : nums) {
            if (count == 0) candidate = num;
            count += (num == candidate) ? 1 : -1;
        }
        return candidate;
    }
}

---

189. 轮转数组 (Rotate Array)

题目描述

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

解题思路

三次翻转。

1. 翻转整个数组。
2. 翻转前 k % n 个元素。
3. 翻转后 n - k % n 个元素。

Java 代码实现

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);
    }
    private void reverse(int[] nums, int l, int r) {
        while (l < r) {
            int tmp = nums[l];
            nums[l++] = nums[r];
            nums[r--] = tmp;
        }
    }
}

---

121. 买卖股票的最佳时机 (Best Time to Buy and Sell Stock)

题目描述

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定的股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

如果你不能获取任何利润，返回 0 。

解题思路

一次遍历，维护 minPrice 为之前遇到的最低价格，计算 price - minPrice 并更新 maxProfit。

Java 代码实现

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE, maxProfit = 0;
        for (int p : prices) {
            minPrice = Math.min(minPrice, p);
            maxProfit = Math.max(maxProfit, p - minPrice);
        }
        return maxProfit;
    }
}

---

122. 买卖股票的最佳时机 II (Best Time to Buy and Sell Stock II)

题目描述

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回你能获得的 最大 利润。

解题思路

贪心算法。累加所有相邻两天的利润（只要利润为正）。

Java 代码实现

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                profit += prices[i] - prices[i - 1];
            }
        }
        return profit;
    }
}

---

55. 跳跃游戏 (Jump Game)

题目描述

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

解题思路

贪心算法。维护最远能到达的距离 maxReach。遍历数组，如果 i <= maxReach，更新 maxReach = max(maxReach, i + nums[i])。

Java 代码实现

class Solution {
    public boolean canJump(int[] nums) {
        int maxReach = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > maxReach) return false;
            maxReach = Math.max(maxReach, i + nums[i]);
        }
        return true;
    }
}

---

45. 跳跃游戏 II (Jump Game II)

题目描述

给你一个非负整数数组 nums ，你最初位于数组的第一个下标。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

解题思路

贪心算法。在当前能跳到的范围内，找一个能跳得最远的位置作为下一次跳跃的目标。

Java 代码实现

class Solution {
    public int jump(int[] nums) {
        int steps = 0, currentEnd = 0, maxReach = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            maxReach = Math.max(maxReach, i + nums[i]);
            if (i == currentEnd) {
                steps++;
                currentEnd = maxReach;
            }
        }
        return steps;
    }
}

---

274. H 指数 (H-Index)

题目描述

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。

根据维基百科上 h 指数的定义：h 代表“高引用次数”，一名科研人员的 h 指数是指他（她）至少有 h 篇论文分别被引用了至少 h 次。

解题思路

计数排序。用数组统计引用次数对应的论文数量。或者排序后倒序遍历。

Java 代码实现

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int[] counter = new int[n + 1];
        for (int c : citations) {
            counter[Math.min(c, n)]++;
        }
        int total = 0;
        for (int i = n; i >= 0; i--) {
            total += counter[i];
            if (total >= i) return i;
        }
        return 0;
    }
}

---

380. O(1) 时间插入、删除和获取随机元素 (Insert Delete GetRandom O(1))

题目描述

实现 RandomizedSet 类：

• RandomizedSet() 初始化 RandomizedSet 对象
• bool insert(int val) 当元素 val 不存在时，向集合中插入该项目，并返回 true ；否则，返回 false 。
• bool remove(int val) 当元素 val 存在时，从集合中移除该项目，并返回 true ；否则，返回 false 。
• int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。

你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

解题思路

数组 + 哈希表。数组存储元素，哈希表存储元素到下标的映射。删除时，将要删除的元素与数组末尾元素交换，然后删除末尾元素，实现 O(1)。

Java 代码实现

class RandomizedSet {
    List<Integer> nums = new ArrayList<>();
    Map<Integer, Integer> map = new HashMap<>();
    Random rand = new Random();

    public boolean insert(int val) {
        if (map.containsKey(val)) return false;
        map.put(val, nums.size());
        nums.add(val);
        return true;
    }

    public boolean remove(int val) {
        if (!map.containsKey(val)) return false;
        int index = map.get(val);
        int last = nums.get(nums.size() - 1);
        nums.set(index, last);
        map.put(last, index);
        nums.remove(nums.size() - 1);
        map.remove(val);
        return true;
    }

    public int getRandom() {
        return nums.get(rand.nextInt(nums.size()));
    }
}

---

238. 除了自身以外数组的乘积 (Product of Array Except Self)

题目描述

给你一个整数数组 nums，返回数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums 之中任意元素的全部前缀乘积和后缀乘积都在 32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

解题思路

左右缀积。第一次遍历计算左缀积，第二次遍历（逆向）计算并结合右缀积。

Java 代码实现

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

---

134. 加油站 (Gas Station)

题目描述

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

解题思路

如果总油量减去总消耗大于等于 0，则一定存在起点。从 0 开始出发，如果中途油量不够了，说明 [0, i] 都不可能是起点，将起点设为 i+1。

Java 代码实现

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int total = 0, current = 0, start = 0;
        for (int i = 0; i < gas.length; i++) {
            total += gas[i] - cost[i];
            current += gas[i] - cost[i];
            if (current < 0) {
                start = i + 1;
                current = 0;
            }
        }
        return total >= 0 ? start : -1;
    }
}

---

135. 分发糖果 (Candy)

题目描述

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。
• 相邻两个孩子评分更高的孩子会获得更多的糖果。

请弄清楚需要准备多少颗糖果，并返回需要准备的糖果 最少 数量。

解题思路

两次遍历。

1. 从左向右，如果 nums[i] > nums[i-1]，则 c[i] = c[i-1] + 1。
2. 从右向左，如果 nums[i] > nums[i+1]，则 c[i] = max(c[i], c[i+1] + 1)。

Java 代码实现

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] left = new int[n];
        Arrays.fill(left, 1);
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) left[i] = left[i - 1] + 1;
        }
        int right = 1, sum = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (i < n - 1 && ratings[i] > ratings[i + 1]) right++;
            else right = 1;
            sum += Math.max(left[i], right);
        }
        return sum;
    }
}

---

42. 接雨水 (Trapping Rain Water)

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

解题思路

双指针。维护 leftMax 和 rightMax。谁的小就处理谁，因为更小的那个决定了高度。

Java 代码实现

class Solution {
    public int trap(int[] height) {
        int l = 0, r = height.length - 1, lMax = 0, rMax = 0, res = 0;
        while (l < r) {
            lMax = Math.max(lMax, height[l]);
            rMax = Math.max(rMax, height[r]);
            if (lMax < rMax) res += lMax - height[l++];
            else res += rMax - height[r--];
        }
        return res;
    }
}

---

13. 罗马数字转整数 (Roman to Integer)

题目描述

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

字符	数值
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。27 写做 XXVII , 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数减小数得到的值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

• I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
• X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
• C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。

解题思路

哈希映射 + 逆向遍历。

1. 建立罗马字母到数字的映射。
2. 遍历字符串。如果当前字符对应的数值小于右侧相邻字符的数值，则减去当前数值（如 IV 表示 4, 即 5 - 1）；否则加上。

Java 代码实现

class Solution {
    public int romanToInt(String s) {
        Map<Character, Integer> map = new HashMap<>();
        map.put('I', 1); map.put('V', 5); map.put('X', 10);
        map.put('L', 50); map.put('C', 100); map.put('D', 500); map.put('M', 1000);
        int res = 0, n = s.length();
        for (int i = 0; i < n; i++) {
            int value = map.get(s.charAt(i));
            if (i < n - 1 && value < map.get(s.charAt(i + 1))) res -= value;
            else res += value;
        }
        return res;
    }
}

---

12. 整数转罗马数字 (Integer to Roman)

题目描述

七个不同的符号代表罗马数字，其值如下：

符号	值
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

罗马数字可以通过添加从最高到最低符号的转换值来形成。将转换值添加在一起。例如，数字 3 是 III，即三个 1 相加。数字 4 不是 IIII。相反，数字 4 是 IV，因为 1 在 5 之前，所以减去它得出 4。同样的原理也适用于数字 9，它是 IX。共有六个特殊的减法情况：

• I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
• X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
• C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给你一个整数，将其转换成罗马数字。

解题思路

硬编码所有映射 + 贪心匹配。

1. 将所有特殊的组合（如 4, 9, 40, 90 等）和基本罗马数字按降序存入两个对应的数组。
2. 遍历数组，尝试用当前罗马数字去匹配整数，直到整数变为 0。

Java 代码实现

class Solution {
    public String intToRoman(int num) {
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < values.length && num > 0; i++) {
            while (num >= values[i]) {
                num -= values[i];
                sb.append(symbols[i]);
            }
        }
        return sb.toString();
    }
}

---

58. 最后一个单词的长度 (Length of Last Word)

题目描述

给你一个字符串 s，由若干单词组成，单词前后用一些空格隔开。返回字符串中 最后一个 单词的长度。

单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

解题思路

反向遍历。

1. 首先过滤掉字符串末尾的空格。
2. 然后从后往前计算第一个非空格字符序列的长度。

Java 代码实现

class Solution {
    public int lengthOfLastWord(String s) {
        int index = s.length() - 1;
        while (s.charAt(index) == ' ') index--;
        int end = index;
        while (index >= 0 && s.charAt(index) != ' ') index--;
        return end - index;
    }
}

---

14. 最长公共前缀 (Longest Common Prefix)

题目描述

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

解题思路

纵向扫描。

1. 以第一个字符串为基准。
2. 比较每一个字符串的第 i 位是否相同。
3. 一旦不匹配或某个字符串到达结尾，则返回前半部分。

Java 代码实现

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

---

151. 反转字符串中的单词 (Reverse Words in a String)

题目描述

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意： 输入字符串 s中可能会在前导、尾随或者单词间包含多余的空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不应该包含任何额外的空格。

解题思路

双端队列 + 分割字符串。

1. 修剪前后空格。
2. 按照空格分割（连续空格视为一个），将单词放入双端队列头部以实现反向。
3. 重新拼接。

Java 代码实现

class Solution {
    public String reverseWords(String s) {
        String[] words = s.trim().split("\\s+");
        Collections.reverse(Arrays.asList(words));
        return String.join(" ", words);
    }
}

---

6. Z 字形变换 (ZigZag Conversion)

题目描述

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

解题思路

模拟行移动。

1. 每一行维护一个 StringBuilder。
2. 用 curRow 记录当前所在行号，goingDown 记录当前方向。
3. 遇到第一行或最后一行时，反转方向。

Java 代码实现

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) return s;
        List<StringBuilder> rows = new ArrayList<>();
        for (int i = 0; i < Math.min(numRows, s.length()); i++) rows.add(new StringBuilder());
        int curRow = 0;
        boolean goingDown = false;
        for (char c : s.toCharArray()) {
            rows.get(curRow).append(c);
            if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
            curRow += goingDown ? 1 : -1;
        }
        StringBuilder res = new StringBuilder();
        for (StringBuilder row : rows) res.append(row);
        return res.toString();
    }
}

---

28. 找出字符串中第一个匹配项的下标 (Find the Index of the First Occurrence in a String)

题目描述

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

解题思路

Java String built-ins 或者 滑动窗口匹配。

Java 代码实现

class Solution {
    public int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);
    }
}

---

68. 文本左右对齐 (Text Justification)

题目描述

给定一个单词数组 words 和一个长度 maxWidth ，重新排版文本，使得每行恰好有 maxWidth 个字符，且左右两端对齐。

你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。

要求尽可能均匀分配单词间的空格数量。如果某一行空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。

文本的最后一行应为左对齐，且单词之间不插入额外的空格。

解题思路

贪心模拟。

1. 确定每行包含哪些单词。
2. 计算每行所需的空格并平均分配。
3. 处理左对齐（只有一词或最后一行）。

Java 代码实现

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> res = new ArrayList<>();
        int i = 0, n = words.length;
        while (i < n) {
            int j = i + 1, len = words[i].length();
            while (j < n && len + 1 + words[j].length() <= maxWidth) {
                len += 1 + words[j++].length();
            }
            StringBuilder sb = new StringBuilder(words[i]);
            int count = j - i - 1; // 间隔数
            if (j == n || count == 0) { // 最后一行或只有一个单词
                for (int k = i + 1; k < j; k++) sb.append(" ").append(words[k]);
                while (sb.length() < maxWidth) sb.append(" ");
            } else {
                int spaces = (maxWidth - (len - count)) / count;
                int extra = (maxWidth - (len - count)) % count;
                for (int k = i + 1; k < j; k++) {
                    for (int s = 0; s < spaces + (k - i <= extra ? 1 : 0); s++) sb.append(" ");
                    sb.append(words[k]);
                }
            }
            res.add(sb.toString());
            i = j;
        }
        return res;
    }
}