LeetCode面试经典150题

目录

力扣80. 删除有序数组中的重复项 II

代码解析

力扣274. H 指数

代码解析

力扣151. 反转字符串中的单词

解析代码

力扣12. 整数转罗马数字

解析代码

力扣28. 找出字符串中第一个匹配项的下标

解析代码1（暴力模拟）

解析代码2（KMP算法待续）

力扣392. 判断子序列

解析代码

力扣167. 两数之和 II - 输入有序数组

解析代码

---

本专栏是LeetCode面试经典150题中本人未刷过的题，其它刷过的题应该在之前的专栏发过了。

力扣80. 删除有序数组中的重复项 II

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

难度 中等

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

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

说明：

为什么返回数值是整数，但输出的答案是数组呢？

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {print(nums[i]);
}

示例 1：

输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。 不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前七个元素被修改为 0, 0, 1, 1, 2, 3, 3。不需要考虑数组中超出新长度后面的元素。

提示：

• 1 <= nums.length <= 3 * 10^4
• -10^4 <= nums[i] <= 10^4
• nums 已按升序排列

class Solution {
public:int removeDuplicates(vector<int>& nums) {}
};

---

代码解析

瑕疵代码：

class Solution {
public:int removeDuplicates(vector<int>& nums) {int left = 0, mid = 1, right = 2, sz = nums.size();if(sz <= 2)return sz;while(right < sz){if(nums[right] != nums[left] || nums[right] != nums[mid]){nums[++mid] = nums[right];++left;}++right;}nums.resize(mid + 1);return mid + 1;}
};

修改代码：

class Solution {
public:int removeDuplicates(vector<int>& nums) {int left = 0, right = 2, sz = nums.size();if(sz <= 2)return sz;while(right < sz){if(nums[right] != nums[left]){nums[left + 2] = nums[right];++left;}++right;}nums.resize(left + 2);return left + 2;}
};

---

力扣274. H 指数

274. H 指数

难度 中等

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

根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且 至少 有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值，h 指数 是其中最大的那个。

示例 1：

输入：citations = [3,0,6,1,5]输出：3 
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。

示例 2：

输入：citations = [1,3,1]
输出：1

提示：

• n == citations.length
• 1 <= n <= 5000
• 0 <= citations[i] <= 1000

class Solution {
public:int hIndex(vector<int>& citations) {}
};

---

代码解析

        所谓的 h 指数是指一个具体的数值，该数值为“最大”的满足「至少发表了 x 篇论文，且每篇论文至少被引用 x 次」定义的合法数，重点是“最大”。所以当遇到第一个无法满足的数时，更大的数值就没必要找了。

排序代码：时间O（N*logN）

class Solution {
public:int hIndex(vector<int>& citations) {sort(citations.begin(), citations.end());int h = 0;for(int i = citations.size() - 1; i >= 0; --i){if(citations[i] > h)++h;}return h;}
};

计数代码：时间O（N），网上题解：

class Solution {
public:int hIndex(vector<int>& citations) {int sz = citations.size(), sum = 0;vector<int> cnt(sz + 1);for(auto& e : citations){cnt[min(sz, e)]++;}for(int i = sz; i >= 0; --i){sum += cnt[i];if(sum >= i)return i;}return 0;}
};

---

力扣151. 反转字符串中的单词

151. 反转字符串中的单词

难度 中等

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

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

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

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

示例 1：

输入：s = "the sky is blue"输出："blue is sky the"

示例 2：

输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

提示：

• 1 <= s.length <= 10^4
• s 包含英文大小写字母、数字和空格 ' '
• s 中 至少存在一个 单词

进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。

class Solution {
public:string reverseWords(string s) {}
};

---

解析代码

class Solution {
public:string reverseWords(string s) {vector<string> arr;int left = 0, right = 0, sz = s.size();while(s[sz - 1] == ' ') // 移除尾部空格{sz--;}for(int i = 0; i < sz; ++i){if(s[i] != ' '){left = i;while(i < sz && s[i] != ' '){++i;}if(i == sz - 1)right = sz;elseright = i;// cout << sz << " " << left << " " << right << endl;arr.push_back(s.substr(left, right - left)); // substr里是起始位置和长度}}string ret;for(int i = arr.size() - 1; i >= 0; --i){cout << arr[i] << "*";ret += arr[i];if(i != 0)ret += ' ';}return ret;}
};

---

力扣12. 整数转罗马数字

12. 整数转罗马数字

难度 中等

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

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

罗马数字是通过添加从最高到最低的小数位值的转换而形成的。将小数位值转换为罗马数字有以下规则：

• 如果该值不是以 4 或 9 开头，请选择可以从输入中减去的最大值的符号，将该符号附加到结果，减去其值，然后将其余部分转换为罗马数字。
• 如果该值以 4 或 9 开头，使用 减法形式，表示从以下符号中减去一个符号，例如 4 是 5 (V) 减 1 (I): IV ，9 是 10 (X) 减 1 (I)：IX。仅使用以下减法形式：4 (IV)，9 (IX)，40 (XL)，90 (XC)，400 (CD) 和 900 (CM)。
• 只有 10 的次方（I, X, C, M）最多可以连续附加 3 次以代表 10 的倍数。你不能多次附加 5 (V)，50 (L) 或 500 (D)。如果需要将符号附加4次，请使用 减法形式。

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

示例 1：

输入：num = 3749

输出： "MMMDCCXLIX"

解释：

3000 = MMM 由于 1000 (M) + 1000 (M) + 1000 (M)700 = DCC 由于 500 (D) + 100 (C) + 100 (C)40 = XL 由于 50 (L) 减 10 (X)9 = IX 由于 10 (X) 减 1 (I)
注意：49 不是 50 (L) 减 1 (I) 因为转换是基于小数位

示例 2：

输入：num = 58

输出："LVIII"

解释：

50 = L8 = VIII

示例 3：

输入：num = 1994

输出："MCMXCIV"

解释：

1000 = M900 = CM90 = XC4 = IV

提示：

• 1 <= num <= 3999

class Solution {
public:string intToRoman(int num) {}
};

---

解析代码

const pair<int, string> p_i_str[] =
{{1000, "M"},{900, "CM"},{500, "D"},{400, "CD"},{100, "C"},{90, "XC"},{50, "L"},{40, "XL"},{10, "X"},{9, "IX"},{5, "V"},{4, "IV"},{1, "I"},
};class Solution {
public:string intToRoman(int num) {string ret;for(auto &[val, str] : p_i_str){while(num >= val){num -= val;ret += str;}if(num == 0)break;}return ret;}
};

---

力扣28. 找出字符串中第一个匹配项的下标

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

难度 简单

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

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

提示：

• 1 <= haystack.length, needle.length <= 10^4
• haystack 和 needle 仅由小写英文字符组成

class Solution {
public:int strStr(string haystack, string needle) {}
};

---

解析代码1（暴力模拟）

class Solution {
public:int strStr(string haystack, string needle) {int sz1 = haystack.size(), sz2 = needle.size();for(int i = 0; i <= sz1 - sz2; ++i){if(haystack.substr(i, sz2) == needle)return i;}return -1;}
};

---

解析代码2（KMP算法待续）

---

力扣392. 判断子序列

392. 判断子序列

难度 简单

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

致谢：

特别感谢 @pbrother 添加此问题并且创建所有测试用例。

示例 1：

输入：s = "abc", t = "ahbgdc"
输出：true

示例 2：

输入：s = "axc", t = "ahbgdc"
输出：false

提示：

• 0 <= s.length <= 100
• 0 <= t.length <= 10^4
• 两个字符串都只由小写字符组成。

class Solution {
public:bool isSubsequence(string s, string t) {}
};

---

解析代码

从前往后匹配，可以发现每次贪心地匹配靠前的字符是最优决策。类似双指针：

class Solution {
public:bool isSubsequence(string s, string t) {int n1 = s.size(), n2 = t.size();int index1 = 0;for(int index2 = 0; index2 < n2; ++index2){if(s[index1] == t[index2])++index1;}return index1 == n1;}
};

---

力扣167. 两数之和 II - 输入有序数组

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

难度 中等

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列  ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

示例 1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

示例 2：

输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。

示例 3：

输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

提示：

• 2 <= numbers.length <= 3 * 10^4
• -1000 <= numbers[i] <= 1000
• numbers 按 非递减顺序 排列
• -1000 <= target <= 1000
• 仅存在一个有效答案

class Solution {
public:vector<int> twoSum(vector<int>& numbers, int target) {}
};

---

解析代码

        初始时两个指针分别指向第一个元素位置和最后一个元素的位置。每次计算两个指针指向的两个元素之和，并和目标值比较。如果两个元素之和等于目标值，则发现了唯一解。如果两个元素之和小于目标值，则将左侧指针右移一位。如果两个元素之和大于目标值，则将右侧指针左移一位。移动指针之后，重复上述操作，直到找到答案。

class Solution {
public:vector<int> twoSum(vector<int>& numbers, int target) {int left = 0, right = numbers.size() - 1;while(left < right){int sum = numbers[left] + numbers[right];if(sum == target)break;else if(sum > target)--right;else++left;}return {left + 1, right + 1};}
};

---

哈希

力扣383. 赎金信

383. 赎金信

难度 简单

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1：

输入：ransomNote = "a", magazine = "b"
输出：false

示例 2：

输入：ransomNote = "aa", magazine = "ab"
输出：false

示例 3：

输入：ransomNote = "aa", magazine = "aab"
输出：true

提示：

• 1 <= ransomNote.length, magazine.length <= 10^5
• ransomNote 和 magazine 由小写英文字母组成

class Solution {
public:bool canConstruct(string ransomNote, string magazine) {}
};

---

解析代码

class Solution {
public:bool canConstruct(string ransomNote, string magazine) {vector<int> arr(26, 0);for(auto& e : magazine){arr[e - 'a']++;}for(auto& e : ransomNote){if(--arr[e - 'a'] == -1)return false;}return true;}
};

---

力扣205. 同构字符串

205. 同构字符串

难度 简单

给定两个字符串 s 和 t ，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

示例 1:

输入：s = "egg", t = "add"输出：true

示例 2：

输入：s = "foo", t = "bar"输出：false

示例 3：

输入：s = "paper", t = "title"输出：true

提示：

• 1 <= s.length <= 5 * 10^4
• t.length == s.length
• s 和 t 由任意有效的 ASCII 字符组成

class Solution {
public:bool isIsomorphic(string s, string t) {}
};

---

解析代码

        字符串没有说都是小写字母之类的，所以用数组不合适了，用map来做映射。 使用两个map 保存 s[i] 到 t[j] 和 t[j] 到 s[i] 的映射关系，如果发现对应不上，立刻返回 false。

class Solution {
public:bool isIsomorphic(string s, string t) {unordered_map<char, char> map1, map2;int n1 = s.size(), n2 = t.size();if(n1 != n2)return false;for(int i = 0; i < n1; i++){if(map1.find(s[i]) == map1.end())map1[s[i]] = t[i];  // map1保存s[i]到t[i]的映射if(map2.find(t[i]) == map2.end())map2[t[i]] = s[i];  // map2保存t[i]到s[i]的映射if(map1[s[i]] != t[i] || map2[t[i]] != s[i])return false; // 映射对应不上}return true;}
};

---