LeetCode刷题记（一）：1~30题

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
只会存在一个有效答案

#include <iostream>
#include <vector>
#include <map>
using namespace std;vector<int> twoSum(vector<int>& nums, int target) {map<int, int> map;vector<int> result;for (int i = 0; i < nums.size(); i++) {int complement = target - nums[i];  // 差值if (map.find(complement) != map.end()) {result.push_back(map[complement]);result.push_back(i);return result;}map[nums[i]] = i;}return result;
}int main() {vector<int> nums;int target;int temp;while(cin>>temp){nums.push_back(temp);if(cin.get() == '\n')break;}cin>>target;vector<int> result = twoSum(nums, target);for (int i = 0; i < result.size(); i++) {cout << result[i] << " ";}return 0;
}

2. 两数相加

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

#include<iostream>
using namespace std;struct ListNode {int val;ListNode *next;ListNode() : val(0), next(NULL) {}ListNode(int x) : val(x), next(NULL) {}ListNode(int x, ListNode *next) : val(x), next(next) {}
};class Solution {public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* dummy = new ListNode(0);ListNode* curr = dummy;int carry = 0;  // 进位while(l1 != NULL || l2 != NULL) {int x = (l1 != NULL) ? l1->val : 0;  int y = (l2 != NULL) ? l2->val : 0;int sum = x + y + carry;carry = sum / 10;curr->next = new ListNode(sum % 10);curr = curr->next;if(l1 != NULL) l1 = l1->next;if(l2 != NULL) l2 = l2->next;} // 增添1位 if(carry > 0) {curr->next = new ListNode(carry);}return dummy->next;}
};ListNode* createList() {ListNode* head = NULL;ListNode* current = NULL;int val;while(cin >> val) {ListNode* newNode = new ListNode(val);if(head == NULL) {head = newNode;current = newNode;} else {current->next = newNode;current = current->next;}if(cin.get() == '\n')break;}return head;
}void printList(ListNode* head) {ListNode* current = head;while(current != NULL) {cout << current->val << " ";current = current->next;}
}int main() {Solution solution;ListNode* list1 = createList();ListNode* list2 = createList();ListNode* result = solution.addTwoNumbers(list1, list2);printList(result);return 0;
}

3. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是子串的长度，"pwke"是一个子序列，不是子串。

提示：

0 <= s.length <= 5 * 10^4
s 由英文字母、数字、符号和空格组成

#include<iostream>
#include<vector>
using namespace std;class Solution {public:int lengthOfLongestSubstring(string s) {// 使用滑动窗口来找出最长的不含重复字符的子串 int n = s.length();int res = 0;  // 记录最长子串的长度 vector<int> index(128, -1);  // 记录每个字符在字符串s中最近出现的位置 for(int i = 0, j = 0; j < n; j++) {i = max(i, index[s[j]] + 1);  // 当遇到重复的字符时，将左边界i移动到该重复字符的下一个位置，确保窗口内没有重复字符 res = max(res, j - i + 1);  // 每次更新窗口长度并与res比较，取较大者 index[s[j]] = j;  // 更新字符在index数组中的位置为当前位置 }return res;}
};int main() {Solution solution;string s;cin >> s;cout << solution.lengthOfLongestSubstring(s);return 0;
}

4. 寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
^

提示：

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-10^6 <= nums1[i], nums2[i] <= 10^6

解法一：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;class Solution {public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {vector<int> curr;int m = nums1.size();int n = nums2.size();for(int i = 0; i < m; i++) {curr.push_back(nums1[i]);}for(int i = 0; i < n; i++) {curr.push_back(nums2[i]);}sort(curr.begin(), curr.end());if((m + n) % 2 == 0) {return (curr[(m + n) / 2] + curr[(m + n) / 2 - 1] ) / 2.0; } else {return curr[(m + n) / 2];}}
};int main() {Solution solution;vector<int> nums1, nums2;int tmp;cout << "请输入nums1数组的元素：" << endl;while(cin >> tmp) {nums1.push_back(tmp);if(cin.get() == '\n')break;}cout << "请输入nums2数组的元素：" << endl;while(cin >> tmp) {nums2.push_back(tmp);if(cin.get() == '\n')break;}cout << solution.findMedianSortedArrays(nums1, nums2);return 0;
}

解法二：

class Solution {public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {vector<int> curr;int m = nums1.size();int n = nums2.size();int i = 0, j = 0;while(i < m && j < n) {if(nums1[i] < nums2[j]) {curr.push_back(nums1[i]);i++;}else {curr.push_back(nums2[j]);j++;}}while(i < m) {curr.push_back(nums1[i]);i++;}while(j < n) {curr.push_back(nums2[j]);j++;}if((m + n) % 2 == 0) {return (curr[(m + n) / 2] + curr[(m + n) / 2 - 1] ) / 2.0; } else {return curr[(m + n) / 2];}}
};

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

// C++
#include<iostream>
#include<vector>
#include<string>
using namespace std;class Solution {public:string longestPalindrome(string s) {int n = s.size();if(n < 2) {return s;}int maxLen = 1;int begin = 0;//dp[i][j]表示s[i··j]是否为回文串vector<vector <int> > dp(n,vector<int>(n, true));//递归开始//先枚举子串长度for(int L = 2; L <= n; L++) {//枚举左边界，左边界的上限设置可以宽松一些for(int i = 0; i < n; i++) {int j = L + i - 1;//如果右边界越界，就可以退出当前循环if(j >= n) {break;}if(s[i] != s[j]) {dp[i][j] = false;} else {if(j-i < 3) {dp[i][j] = true;} else {dp[i][j] = dp[i + 1][j - 1];}}// 只要dp[i][j] == true成立，就表示子串s[i···L]是回文，此时记录回文长度和起始位置。if(dp[i][j] && j - i + 1 > maxLen) {maxLen = j - i + 1;begin = i;}}}return s.substr(begin,maxLen);}
};int main() {string s = "";cin>>s;Solution solution;cout<<solution.longestPalindrome(s)<<endl;return 0;
}

解法二：

// C++
#include<iostream>
#include<vector>
#include<string>
using namespace std;class Solution {public:string longestPalindrome(string s) {if(s.empty()) {return "";}int start = 0, end = 0;for(int i = 0; i < s.size(); i++) {int len1 = expandAroundCenter(s, i, i);int len2 = expandAroundCenter(s, i, i + 1);int len = max(len1, len2);if(len > end - start) {start = i - (len - 1) / 2;end = i + len / 2;}}return s.substr(start, end - start + 1);}int expandAroundCenter(string s, int left, int right) {while(left >= 0 && right < s.size() && s[left] == s[right]) {left--;right++;}return right - left - 1;}
};int main() {string s = "";cin>>s;Solution solution;cout<<solution.longestPalindrome(s)<<endl;return 0;
}

6. Z字型变换

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

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

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

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

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1：

输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

示例 2：

输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

示例 3：

输入：s = "A", numRows = 1
输出："A"

提示：

1 <= s.length <= 1000
s 由英文字母（小写和大写）、',' 和 '.' 组成
1 <= numRows <= 1000

#include<iostream>
#include<vector> 
#include<algorithm>
using namespace std;class Solution {public:string covert(string s, int numRows) {if(numRows == 1) return s;int n = s.size();int k = 2 * numRows - 2;  // 计算 Z 字形的周期长度，即每个完整的 Z 字形有多少个字符vector<string> a(numRows);// 创建一个长度为 numRows 的字符串数组 a，用于存储 Z 字形排列后的每一行字符串for(int i = 0; i < n; i++) {a[min(k - i % k, i % k)] += s[i];// k - i % k 和 i % k 分别表示当前字符在 Z 字形周期中的上半部分和下半部分的位置}return accumulate(a.begin(), a.end(), string(""));  // 拼接}
};int main() {string s;cin >> s;int numRows;cin >> numRows; Solution solution;cout << solution.covert(s, numRows);return 0;
}

7. 整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−2^31, 2^31 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

示例 1：

输入：x = 123
输出：321

示例 2：

输入：x = -123
输出：-321

示例 3：

输入：x = 120
输出：21

示例 4：

输入：x = 0
输出：0

提示：

-2^31 <= x <= 2^31 - 1

#include<iostream>
#include<vector>
using namespace std;class Solution {public:int reverse(int x) {
//			if(x == 0)	return 0;int res = 0;while(x != 0) {if(res < INT_MIN / 10 || res > INT_MAX / 10) {return 0;}res = res * 10 + x % 10;x /= 10;}return res;}
};int main() {int x;cin >> x;Solution solution;cout << solution.reverse(x) << endl;return 0;
}

8. 字符串转换正数(atoi)

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。确定最终结果是负数还是正数。如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
返回整数作为最终结果。

注意：

本题中的空白字符只包括空格字符 ' ' 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。

示例 1：

输入：s = "42"
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
第 1 步："42"（当前没有读入字符，因为没有前导空格）^
第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）^
第 3 步："42"（读入 "42"）^
解析得到整数 42 。
由于 "42" 在范围 [-231, 231 - 1] 内，最终结果为 42 。

示例 2：

输入：s = "   -42"
输出：-42
解释：
第 1 步："   -42"（读入前导空格，但忽视掉）^
第 2 步："   -42"（读入 '-' 字符，所以结果应该是负数）^
第 3 步："   -42"（读入 "42"）^
解析得到整数 -42 。
由于 "-42" 在范围 [-231, 231 - 1] 内，最终结果为 -42 。

示例 3：

输入：s = "4193 with words"
输出：4193
解释：
第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格）^
第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）^
第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止）^
解析得到整数 4193 。
由于 "4193" 在范围 [-231, 231 - 1] 内，最终结果为 4193 。

提示：

0 <= s.length <= 200
s 由英文字母（大写和小写）、数字（0-9）、' '、'+'、'-' 和 '.' 组成

#include<iostream>
#include<ctype.h>
using namespace std;class Solution {public:int myAtoi(string s) {int i = 0;  // 索引 int sign = 1;  // 符号位long long result = 0;// 跳过前面的空格字符while(i < s.size() && s[i] == ' ') {i++;} // 检查最终结果为正数还是负数if(i < s.size() && (s[i] == '+' || s[i] == '-')) {sign = (s[i++] == '-' ? -1 : 1);} // 把字符串转换成数字 while(i < s.size() && isdigit(s[i])) {result = result * 10 + (s[i++] - '0');if(result * sign > INT_MAX) {return INT_MAX;} if(result * sign < INT_MIN) {return INT_MIN;}} return result * sign;}
};int main() {string s;cin >> s;Solution solution;cout << solution.myAtoi(s);return 0;
}

9. 回文数

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

例如，121 是回文，而 123 不是。

示例 1：

输入：x = 121
输出：true

示例 2：

输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3：

输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。

提示：

-2^31 <= x <= 2^31 - 1

#include<iostream>
using namespace std;bool isPalindrome(int num){if(num < 0){ return false;} int original = num;long long reversed = 0;while(num > 0) {reversed = reversed * 10 + num % 10;num /= 10;}return original == reversed;
}int main()
{int num;cin>>num;cout<<boolalpha<<isPalindrome(num)<<endl;return 0;
}

10. 正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖整个字符串 s的，而不是部分字符串。

示例 1：

输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

示例 2:

输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3：

输入：s = "ab", p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

提示：

1 <= s.length <= 20
1 <= p.length <= 20
s 只包含从 a-z 的小写字母。
p 只包含从 a-z 的小写字母，以及字符 . 和 *。
保证每次出现字符 * 时，前面都匹配到有效的字符

#include<iostream>
#include<vector>
using namespace std;class Solution {
public:bool isMatch(string s, string p) {int m = s.size();int n = p.size();vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));dp[0][0] = true;/*使用两层循环遍历dp数组，其中i表示s的长度，j表示p的长度。在内层循环中，分情况讨论：如果p[j-1]为''，则dp[i][j]为dp[i][j-2]（''匹配0次）或者（s的第i个字符和p的第j-1个字符匹配，并且dp[i-1][j]为true）。如果p[j-1]不为'*'，则dp[i][j]为dp[i-1][j-1]（s的第i个字符和p的第j个字符匹配）。*/for (int i = 0; i <= m; i++) {for (int j = 1; j <= n; j++) {if (p[j - 1] == '*') {dp[i][j] = dp[i][j - 2] || (i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j]);} else {dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');}}}return dp[m][n];}
};int main() {string s, p;cin >> s >> p;Solution solution;cout << boolalpha << solution.isMatch(s, p);return 0;
}

11. 盛最多的水

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

提示：

n == height.length
2 <= n <= 10^5
0 <= height[i] <= 10^4

#include<iostream>
#include<vector>
using namespace std;class Solution {public:int maxArea(vector<int>& height) {int n = height.size();int left = 0;int right = n - 1;int result = 0;while(left < right) {result = max(result, (right - left) * min(height[left], height[right]));if(height[left] > height[right]) {--right;} else {++left;}}return result;}
}; int main() {Solution solution;vector<int> height;int tmp;while(cin >> tmp) {height.push_back(tmp);if(cin.get() == '\n')break;}cout << solution.maxArea(height);return 0;
}

12. 整数转罗马数字

罗马数字包含以下七种字符： 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 的左边，所表示的数等于大数 5 减小数 1 得到的数值 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:

输入: num = 3
输出: "III"

示例 2:

输入: num = 4
输出: "IV"

示例 3:

输入: num = 9
输出: "IX"

示例 4:

输入: num = 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.

示例 5:

输入: num = 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示：

1 <= num <= 3999

解法一：

#include<iostream>
#include<map>
#include<vector>
using namespace std;class Solution {public:string intToRoman(int num) {vector<int> values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};vector<string> symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};string result = "";for(int i = 0; i < values.size(); i++) {while(num >= values[i]) {num -= values[i];result += symbols[i];}}return result;}
};int main() {Solution solution;int num;cin >> num;cout << solution.intToRoman(num);return 0;
}

解法二：

#include<iostream>
#include<map>
#include<vector>
using namespace std;class Solution {public:string intToRoman(int num) {map<int, string> romanMap;romanMap[1] = "I";romanMap[4] = "IV";romanMap[5] = "V";romanMap[9] = "IX";romanMap[10] = "X";romanMap[40] = "XL";romanMap[50] = "L";romanMap[90] = "XC";romanMap[100] = "C";romanMap[400] = "CD";romanMap[500] = "D";romanMap[900] = "CM";romanMap[1000] = "M";string result = "";for(auto it = romanMap.rbegin(); it != romanMap.rend(); ++it) {while(num >= it->first) {result += it->second;num -= it->first;}}return result;}
};int main() {Solution solution;int num;cin >> num;cout << solution.intToRoman(num);return 0;
}

13. 罗马数字转整数

罗马数字包含以下七种字符: 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 。

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

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

示例 1:

输入: s = "III"
输出: 3

示例 2:

输入: s = "IV"
输出: 4

示例 3:

输入: s = "IX"
输出: 9

示例 4:

输入: s = "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5:

输入: s = "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示：

1 <= s.length <= 15
s 仅含字符 ('I', 'V', 'X', 'L', 'C', 'D', 'M')
题目数据保证 s 是一个有效的罗马数字，且表示整数在范围 [1, 3999] 内
题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。
关于罗马数字的详尽书写规则，可以参考罗马数字 - Mathematics 。

#include<iostream>
#include<map>
using namespace std;int romanToInt(string s){map<char, int> romanMap;romanMap['I'] = 1;romanMap['V'] = 5;romanMap['X'] = 10;romanMap['L'] = 50;romanMap['C'] = 100;romanMap['D'] = 500;romanMap['M'] = 1000;int result = 0;for(int i = 0; i < s.length(); i++) {if(i < s.length() - 1 && romanMap[s[i]] < romanMap[s[i + 1]]) {result -= romanMap[s[i]];} else {result += romanMap[s[i]];}}return result;
} int main(){string romanNum;cin>>romanNum;cout<<romanToInt(romanNum);return 0;
}

14. 最长公共前缀

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

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

示例 1：

输入：strs = ["flower","flow","flight"]
输出："fl"

示例 2：

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

提示：

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;string longestCommonPrefix(vector<string>& strs) {if(strs.empty()) {return "";} string ans = strs[0];for(int i = 1; i < strs.size(); i++) {int j = 0;for(; j < ans.length() && j < strs[i].length(); j++) {if(ans[j] != strs[i][j])break;}ans = ans.substr(0, j);if(ans == "")return ans;} return ans;
}int main() {vector<string> strs;string tmp;while(cin>>tmp) {strs.push_back(tmp);if(cin.get() == '\n') break;}cout<<longestCommonPrefix(strs)<<endl;return 0;
}

15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

3 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;class Solution {public:vector<vector<int> > threeSum(vector<int>& nums) {vector<vector<int> > result;sort(nums.begin(), nums.end());for(int i = 0; i < nums.size(); i++) {if(i > 0 && nums[i] == nums[i - 1]) {continue;  // 重复 }int target = -nums[i];int left = i + 1;int right = nums.size() - 1;while(left < right) {int sum = nums[left] + nums[right];if(sum < target) {  // 小于0 left++;} else if(sum > target) {  // 大于0 right--;} else {  // 等于0 result.push_back({nums[i], nums[left], nums[right]});while(left < right && nums[left] == nums[left + 2]) {left++;}while(left < right &&nums[right] == nums[right - 1]) {right--;}left++;right--;}}}return result;}
};int main() {int tmp;vector<int> nums;while(cin >> tmp) {nums.push_back(tmp);if(cin.get() == '\n')break;}Solution solution;vector<vector<int>> result = solution.threeSum(nums);
//	for(const auto& triplet : result) {
//		cout << "[";
//		for(int i = 0; i < 3; i++) {
//			cout << triplet[i];
//			if(i < 2) {
//				cout << ", ";
//			}
//		}
//		cout << "] ";
//	}cout << "[";for(vector<vector<int> >::iterator it = result.begin(); it != result.end(); ++it) {cout << "[";for(int i = 0; i < 3; ++i) {cout << (*it)[i];if(i < 2) {cout << ",";}}if(it == result.end() - 1) {cout << "]";} else {cout << "], ";}}cout << "]";return 0; 
}

16. 最接近的三数之和

给你一个长度为 n 的整数数组 nums 和一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例 1：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

示例 2：

输入：nums = [0,0,0], target = 1
输出：0

提示：

3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-10^4 <= target <= 10^4

#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>
using namespace std;class Solution {public:int threeSumClosest(vector<int>& nums, int target) {sort(nums.begin(), nums.end());int closestSum = INT_MAX;int minDiff = INT_MAX;for(int i = 0; i < nums.size() - 2; i++) {int left = i + 1;int right = nums.size() - 1;while(left < right) {int sum = nums[i] + nums[left] + nums[right];int diff = abs(sum - target);if(diff < minDiff) {  // 更新最小差值 minDiff = diff;closestSum = sum;}if(sum < target) {++left;  // 偏小 } else if(sum > target) {--right;  // 偏大 } else {return sum;   // 相等 }}}return closestSum;}
};int main() {int target;vector<int> nums;while(cin >> target) {nums.push_back(target);if(cin.get() == '\n')break;}cin >> target;Solution solution;cout << solution.threeSumClosest(nums, target);return 0;
}

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

提示：

0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>using namespace std;class Solution {
public:vector<string> letterCombinations(string digits) {vector<string> result;if (digits.empty()) {return result;}unordered_map<char, string> digitToLetters = {{'2', "abc"},{'3', "def"},{'4', "ghi"},{'5', "jkl"},{'6', "mno"},{'7', "pqrs"},{'8', "tuv"},{'9', "wxyz"}};string current;backtrack(digits, 0, current, result, digitToLetters);return result;}void backtrack(string& digits, int index, string& current, vector<string>& result, unordered_map<char, string>& digitToLetters) {if (index == digits.length()) {result.push_back(current);return;}char digit = digits[index];string letters = digitToLetters[digit];for (char letter : letters) {current.push_back(letter);backtrack(digits, index + 1, current, result, digitToLetters);current.pop_back();}}
};int main() {string digits;cin >> digits;Solution solution;vector<string> result = solution.letterCombinations(digits);for (string& combination : result) {cout << combination << " ";}return 0;
}

18. 四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示：

1 <= nums.length <= 200
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;class Solution {public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> result;int n = nums.size();if(n < 4) {return result;}sort(nums.begin(), nums.end());for(int i = 0; i < n - 3; i++) {if(i > 0 && nums[i] == nums[i - 1]) {continue;}for(int j = i + 1; j < n - 2; j++) {if(j > i + 1 && nums[j] == nums[j - 1]) {continue;}int left = j + 1;int right = n - 1;while(left < right) {long sum = static_cast<long>(nums[i]) + nums[j] + nums[left] + nums[right];if(sum < target) {++left;} else if(sum > target) {--right;} else {result.push_back({nums[i], nums[j], nums[left], nums[right]});while(left < right && nums[left] == nums[left + 1]) {++left;}while(left < right && nums[right] == nums[right - 1]) {--right;}++left;--right;}}}}return result;}
};int main() {int target;vector<int> nums;while(cin >> target) {nums.push_back(target);if(cin.get() == '\n')break;}cin >> target;Solution solution;vector<vector<int>> result = solution.fourSum(nums, target);for(vector<int>& quadruplet : result) {cout << "[";for(int num : quadruplet) {cout << num << " ";}cout << "] ";}return 0;}

19. 删除链表的倒数第N个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

进阶：你能尝试使用一趟扫描实现吗？

解题思路：要删除链表的倒数第n个结点，可以使用双指针技巧。首先定义两个指针，分别为快指针和慢指针，初始时均指向头节点。然后让快指针先向后移动n + 1步，这样快指针和慢指针之间就会相隔n个节点。接着同时移动快指针和慢指针，直到快指针指向链表末尾。此时慢指针指向的节点就是要删除的节点的前一个结点。

#include<iostream>
using namespace std;// Definition for single-linked list
struct ListNode {int val;ListNode *next;ListNode() : val(0), next(NULL) {}ListNode(int x) : val(x), next(NULL) {}ListNode(int x, ListNode *next) : val(x), next(next) {}
};class Solution {public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy = new ListNode(0);dummy->next = head;ListNode* fast = dummy;ListNode* slow = dummy;// 向后移动n + 1步 for(int i = 0; i < n + 1; i++) {fast = fast->next;}while(fast != NULL) {fast = fast->next;slow = slow->next;}// 删除结点 ListNode * q = slow->next;slow->next = slow->next->next;delete q;return dummy->next;}
};ListNode* createList() {ListNode* head = NULL;ListNode* current = NULL;int val;while(cin >> val) {ListNode* newNode = new ListNode(val);if(head == NULL) {head = newNode;current = newNode;} else {current->next = newNode;current = newNode;}if(cin.get() == '\n')break;}return head;
}void printList(ListNode* head) {ListNode* current = head;while(current != NULL) {cout << current->val << " ";current = current->next;}
}int main() {ListNode* head = createList();int n;cin >> n;Solution solution;ListNode* result = solution.removeNthFromEnd(head, n);printList(result);return 0;
}

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

提示：

1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成

#include<iostream>
#include<stack>
#include<map>
using namespace std;bool isValid(string s) {stack<char> stk;map<char, char> brackets;brackets.insert(make_pair(')', '('));brackets.insert(make_pair('}', '{'));brackets.insert(make_pair(']', '['));for(string::iterator it = s.begin(); it != s.end(); ++it) {char c = *it;// 如果是右括号if(brackets.find(c) != brackets.end()) {// 栈为空或者栈顶元素与当前右括号不匹配，返回falseif(stk.empty() || stk.top() != brackets[c]) {return false;}stk.pop(); } else {stk.push(c);  // 左括号 }}return stk.empty();
}int main() {string s;cin>>s;cout<<boolalpha<<isValid(s)<<endl;return 0;
}

21. 合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

#include<iostream>
using namespace std;struct ListNode {int val;ListNode *next;ListNode() : val(0), next(NULL) {}ListNode(int x) : val(x), next(NULL) {}ListNode(int x, ListNode *next) : val(x), next(next) {}
};class Solution {public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {  // 递归if(list1 == NULL) return list2;if(list2 == NULL)return list1;if(list1->val < list2->val) {list1->next = mergeTwoLists(list1->next, list2);return list1;}else {list2->next = mergeTwoLists(list1, list2->next);return list2;}}
};int main() {ListNode* list1 = NULL;ListNode* list2 = NULL;cout << "Enter elements for list1 (enter -1 to stop): ";int val;while (cin >> val && val != -1) {ListNode* node = new ListNode(val);if (list1 == NULL) {list1 = node;} else {ListNode* temp = list1;while (temp->next != NULL) {temp = temp->next;}temp->next = node;}}cout << "Enter elements for list2 (enter -1 to stop): ";while (cin >> val && val != -1) {ListNode* node = new ListNode(val);if (list2 == NULL) {list2 = node;} else {ListNode* temp = list2;while (temp->next != NULL) {temp = temp->next;}temp->next = node;}}Solution solution;ListNode* mergedList = solution.mergeTwoLists(list1, list2);// Print the merged listListNode* temp = mergedList;cout << "Merged list: ";while (temp != NULL) {cout << temp->val << " ";temp = temp->next;}cout << endl;return 0;
}

22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示：

1 <= n <= 8

#include<iostream>
#include<vector>
using namespace std;class Solution {public:void helper(vector<string>& result, string current, int open, int close, int n) {if(current.size() == 2 * n) {result.push_back(current);return;  // 递归结束 }if(open < n) {helper(result, current + "(", open + 1, close, n);}if(close < open) {helper(result, current + ")", open, close + 1, n);}}vector<string> generateParenthesis(int n) {vector<string> result;helper(result, "", 0, 0, n);return result;}
}; int main() {int n;cin >> n;Solution solution;vector<string> result = solution.generateParenthesis(n);cout << "[";for(auto it = result.begin(); it != result.end(); ++it) {if(it == result.end() - 1) {cout << *it;} else {cout << *it <<", ";}}cout << "]";return 0;
}

23. 合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[1->4->5,1->3->4,2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按升序排列
lists[i].length 的总和不超过 10^4

解题思路：要合并K个升序链表，可以使用优先队列（最小堆）来实现。首先将每个链表的头节点加入到优先队列中，然后不断从优先队列中取出最小的节点，将其加入到结果链表中，并将该节点的下一个节点加入到优先队列中。重复这个过程直到优先队列为空。

#include<iostream>
#include<vector>
#include<queue>
using namespace std;// Definition for singly-linked list
struct ListNode {int val;ListNode *next;ListNode() : val(0), next(NULL) {}ListNode(int x) : val(x), next(NULL) {}ListNode(int x, ListNode *next) : val(x), next(next) {}
};struct compare {bool operator()(ListNode* a, ListNode* b) {return a->val > b->val;}
};class Solution {public:ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode*, vector<ListNode*>, compare> pq;for(ListNode* list : lists) {  // 添加各个链表的头节点 if(list) {pq.push(list);}}ListNode* dummy = new ListNode(0);ListNode* tail = dummy;while(!pq.empty()) {ListNode* node = pq.top();  // 获取堆顶元素pq.pop();tail->next = node;tail = tail->next;if(node->next) {// 把堆顶元素所在链表的下一个节点入队 pq.push(node->next);} }return dummy->next; }
};ListNode* createList() {ListNode* head = NULL;ListNode* current = NULL;int val;while(cin >> val) {ListNode* newNode = new ListNode(val);if(head == NULL) {head = newNode;current = newNode;} else {current->next = newNode;current = newNode;}if(cin.get() == '\n')break;}return head;
}void printList(ListNode* head) {ListNode* current = head;while(current != NULL) {cout << current->val << " ";current = current->next;}
}int main() {vector<ListNode*> lists;int flag = 0;while(true) {cout << "请输入链表元素：";ListNode* head = createList();lists.push_back(head);cout << "是否需要继续创建链表数组：0（继续）， 1（结束）："; cin >> flag;if(flag == 1) {  // flag = 1时，结束创建链表数组 break;}}cout << "Merged List: ";Solution solution;ListNode* mergedList = solution.mergeKLists(lists);printList(mergedList);return 0;
}

24. 两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

提示：

链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100

#include<iostream>
using namespace std;// Definition for singly-linked list
struct ListNode {int val;ListNode *next;ListNode() : val(0), next(NULL) {}ListNode(int x) : val(x), next(NULL) {}ListNode(int x, ListNode *next) : val(x), next(next) {}
};class Solution {public:ListNode* swapPairs(ListNode* head) {if(!head || !head->next) {return head;}ListNode *dummy = new ListNode(0);dummy->next = head;ListNode *prev = dummy;while(prev->next && prev->next->next) {ListNode *first = prev->next;ListNode *second = prev->next->next;prev->next = second;first->next = second->next;second->next = first;prev = first;}return dummy->next;}
};ListNode* createList() {ListNode *head = NULL;ListNode *current = NULL;int val;while(cin >> val) {ListNode *newNode = new ListNode(val);if(head == NULL) {head = newNode;current = newNode;} else {current->next = newNode;current = current->next;}if(cin.get() == '\n') {break;}}return head;
}void printList(ListNode *head) {ListNode *current = head;while(current != NULL) {cout << current->val << " ";current = current->next;}
}int main() {Solution solution;ListNode *head = createList();ListNode *result = solution.swapPairs(head);printList(result);return 0;}

25. K个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

示例 2：

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

提示：

链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000

进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

#include<iostream>
using namespace std;// Definition for singly-linked list
struct ListNode {int val;ListNode *next;ListNode() : val(0), next(NULL) {}ListNode(int x) : val(x), next(NULL) {}ListNode(int x, ListNode *next) : val(x), next(next) {}
}; class Solution {public:ListNode* reverseKGroup(ListNode* head, int k) {if(!head || k == 1) {return head;}ListNode* dummy = new ListNode(0);dummy->next = head;ListNode* pre = dummy;int count = 0;ListNode* cur = head;while(cur) {count++;ListNode* nextNode = cur->next;if(count == k) {pre = reverse(pre, nextNode);  // 翻转 count = 0;}cur = nextNode;}return dummy->next;}ListNode* reverse(ListNode* pre, ListNode* end) {if(!pre || !pre->next || !pre->next->next) {return pre->next;}ListNode* head = pre->next;ListNode* cur = head->next;while(cur != end) {head->next = cur->next;cur->next = pre->next;pre->next = cur;cur = head->next;}return head;}
};ListNode* createList() {ListNode *head = NULL;ListNode *current = NULL;int val;while(cin >> val) {ListNode *newNode = new ListNode(val);if(head == NULL) {head = newNode;current = newNode;} else {current->next = newNode;current = current->next;}if(cin.get() == '\n') {break;}}return head;
}void printList(ListNode *head) {ListNode *current = head;while(current != NULL) {cout << current->val << " ";current = current->next;}
}int main() {Solution solution;ListNode *head = createList();int k;cin >> k;ListNode *result = solution.reverseKGroup(head, k);printList(result);return 0;
}

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

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

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

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

判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案int k = removeDuplicates(nums); // 调用assert k == expectedNums.length;
for (int i = 0; i < k; i++) {assert nums[i] == expectedNums[i];
}

如果所有断言都通过，那么您的题解将被通过。

示例 1：

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

示例 2：

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

提示：

1 <= nums.length <= 3 * 10^4
-10^4 <= nums[i] <= 10^4
nums 已按 非严格递增 排列

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;class Solution {public:int removeDuplicates(vector<int>& nums) {int size = nums.size();int left = 0, right = 1;while(--size) {if(nums[left] == nums[right]) {right++;} else {nums[left + 1] = nums[right];right++;left++;}}return left + 1;}
};int main() {vector<int> nums;int temp;while(cin >> temp) {nums.push_back(temp);if(cin.get() == '\n')break;}Solution solution;cout<<solution.removeDuplicates(nums);return 0;
}

解法2：使用STL中的unique函数进行优化。unique函数可以将重复的元素移动到数组的末尾，并返回指向不重复部分的尾后迭代器。我们可以利用这个特性来简化代码。只需要调用unique函数，并返回结果与数组起始位置之间的距离，即为不重复元素的个数。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;class Solution {public:int removeDuplicates(vector<int>& nums) {return distance(nums.begin(), unique(nums.begin(), nums.end()));}
};int main() {vector<int> nums;int temp;while(cin >> temp) {nums.push_back(temp);if(cin.get() == '\n')break;}Solution solution;cout<<solution.removeDuplicates(nums);return 0;
}

解法3：在这个优化后的代码中，我们使用了两个指针left和right，其中left指针指向不重复部分的最后一个元素，right指针用于遍历数组。当遇到一个与left指针指向的元素不相同的元素时，将该元素移动到left指针的下一个位置，并将left指针后移一位。遍历完成后，left指针的位置加1即为不重复元素的个数。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;class Solution {public:int removeDuplicates(vector<int>& nums) {int n = nums.size();if(n < 2) {return n;}int left = 0;for(int right = 1; right < n; right++) {if(nums[left] != nums[right]) {left++;nums[left] = nums[right];}}return left + 1;}
};int main() {vector<int> nums;int temp;while(cin >> temp) {nums.push_back(temp);if(cin.get() == '\n')break;}Solution solution;cout<<solution.removeDuplicates(nums);return 0;
}

27. 移除元素

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

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

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

说明:

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

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

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

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

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,3,0,4]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示：

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

#include<iostream>
#include<vector>
using namespace std;class Solution {public:int removeElement(vector<int>& nums, int val) {int j = 0;for(int i = 0; i < nums.size(); i++) {if(nums[i] != val) {nums[j++] = nums[i];  // 不需要考虑数组中超出新长度后面的元素}}return j;}
};int main() {int val;int temp;vector<int> nums;while(cin >> temp) {nums.push_back(temp);if(cin.get() == '\n') {break;}}cin>>val;Solution solution;int len = solution.removeElement(nums, val);cout << len;return 0;
}

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 仅由小写英文字符组成

#include<iostream>
#include<vector>
using namespace std;class Solution {public:int strStr(string haystack, string needle) {return haystack.find(needle);}
};int main() {string haystack, needle;cin >> haystack >> needle;Solution solution;cout<<solution.strStr(haystack, needle);return 0;
}

注：在C++中，string类的find()函数用于在一个字符串中查找子字符串，并返回第一次出现的位置。find()函数有多种重载形式，常用的形式包括：

size_t find(const string& str, size_t pos = 0) const: 在当前字符串中从指定位置pos开始查找子字符串str，返回第一次出现的位置。如果未找到则返回string::npos。
size_t find(const char* s, size_t pos = 0) const: 在当前字符串中从指定位置pos开始查找C风格字符串s，返回第一次出现的位置。如果未找到则返回string::npos。
size_t find(char c, size_t pos = 0) const: 在当前字符串中从指定位置pos开始查找字符c，返回第一次出现的位置。如果未找到则返回string::npos。

示例用法：

#include <iostream>
#include <string>
using namespace std;int main() {string str = "Hello, World!";// 查找子字符串size_t found = str.find("World");if (found != string::npos) {cout << "Found at position: " << found << endl;} else {cout << "Not found" << endl;}// 查找字符size_t foundChar = str.find(',');if (foundChar != string::npos) {cout << "Found character at position: " << foundChar << endl;} else {cout << "Character not found" << endl;}return 0;
}

29. 两数相除

给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求 不使用 乘法、除法和取余运算。

整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。

返回被除数 dividend 除以除数 divisor 得到的商。

注意：假设我们的环境只能存储 32 位 有符号整数，其数值范围是 [−231, 231 − 1] 。本题中，如果商 严格大于 231 − 1 ，则返回 231 − 1 ；如果商 严格小于 -231 ，则返回 -231 。

示例 1:

输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = 3.33333.. ，向零截断后得到 3 。

示例 2:

输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = -2.33333.. ，向零截断后得到 -2 。

提示：

-2^31 <= dividend, divisor <= 2^31 - 1
divisor != 0

#include<iostream>
#include<climits>
using namespace std;class Solution {public:int divide(int dividend, int divisor) {if(dividend == INT_MIN && divisor == -1) {return INT_MAX;}long dvd = labs(dividend);long dvs = labs(divisor);int sign = (dividend > 0) ^ (divisor > 0) ? -1 : 1;long res = 0;while(dvd >= dvs) {long temp = dvs, m = 1;while(temp<<1 <= dvd) {temp <<= 1;m <<= 1;  // 左移一位 }dvd = -= temp;res += m;}return sign * res;}
}; int main() {int dividend, divisor;cin >> dividend >> divisor;Solution solution;cout << solution.divide(dividend, divisor);return 0;
}

30. 串联所有单词的子串

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

例如，如果 words = ["ab","cd","ef"]，那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"，和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例 1：

输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

示例 2：

输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

示例 3：

输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]
解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。

提示：

1 <= s.length <= 104
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] 和 s 由小写英文字母组成

解法一：超时版

#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
using namespace std;class Solution {public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> result;if(s.empty() || words.empty()) {return result;}int wordLen = words[0].length();int wordCount = words.size();int totalLen = wordLen * wordCount;unordered_map<string, int> wordFreq;for(const string& word : words) {wordFreq[word]++;}for(int i = 0; i <= (int)s.length() - totalLen; ++i) {unordered_map<string, int> seen;int j = 0;for(; j < wordCount; ++j) {string word = s.substr(i + j * wordLen, wordLen);if(wordFreq.find(word) == wordFreq.end()) {break;}seen[word]++;if(seen[word] > wordFreq[word]) {break;}}if(j == wordCount) {result.push_back(i);}}return result;}
};int main() {string s;vector<string> words;string tmp;cin >> s;while(cin >> tmp) {words.push_back(tmp);if(cin.get() == '\n')break;} Solution solution;vector<int> result = solution.findSubstring(s, words);for(auto num : result) {cout << num << " ";}return 0;
}

解法二：在每个可能的位置只遍历一次，使用滑动窗口来优化时间复杂度。

#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
using namespace std;class Solution {public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> result;if(s.empty() || words.empty()) {return result;}int wordLen = words[0].length();int wordCount = words.size();int totalLen = wordLen * wordCount;unordered_map<string, int> wordFreq;for(const string& word : words) {wordFreq[word]++;}for(int i = 0; i < wordLen; i++) {int left = i, count = 0;unordered_map<string, int> seen;for(int j = i; j <= (int)s.length() - totalLen; j += wordLen) {string word = s.substr(j, wordLen);if(wordFreq.find(word) != wordFreq.end()) {seen[word]++;count++;while(seen[word] > wordFreq[word]) {string temp = s.substr(left, wordLen);seen[temp]--;count--;left += wordLen;}if(count == wordCount) {result.push_back(left);string temp = s.substr(left, wordLen);seen[temp]--;count--;left += wordLen;}} else {seen.clear();count = 0;left = j + wordLen;}}}return result;}
};int main() {string s;vector<string> words;string tmp;cin >> s;while(cin >> tmp) {words.push_back(tmp);if(cin.get() == '\n')break;} Solution solution;vector<int> result = solution.findSubstring(s, words);for(auto num : result) {cout << num << " ";}return 0;
}