🖍
🖍
🖍
🖍
int-collections
Search…
🖍
🖍
🖍
🖍
int-collections
int-collections
int-experience
int-ml-prepare
int-ml
int-summary
int
Powered By GitBook
int-summary

概述

主要是leetcode相关的题
参考1：【medium常见题】[https://leetcode-cn.com/leetbook/detail/top-interview-questions-medium/](https://leetcode-cn.com/leetbook/detail/ top-interview-questions-medium/)

数组和字符串

罗马数字转整数

罗马数字包含以下七种字符: 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 到 3999 的范围内。
示例 1:
​
输入: "III"
输出: 3
示例 2:
​
输入: "IV"
输出: 4
示例 3:
​
输入: "IX"
输出: 9
示例 4:
​
输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.
示例 5:
​
输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.
解答：
  • 第一，如果当前数字是最后一个数字，或者之后的数字比它小的话，则加上当前数字
  • 第二，其他情况则减去这个数字(例如，IV，看到I的时候就是减去I，然后到V就是加V; XL，看到X的时候就是-X，然后到L就是加L)
class Solution {
public:
int romanToInt(string s) {
unordered_map<char, int> x_map;
x_map.insert(std::make_pair('I', 1));
x_map.insert(std::make_pair('V', 5));
x_map.insert(std::make_pair('X', 10));
x_map.insert(std::make_pair('L', 50));
x_map.insert(std::make_pair('C', 100));
x_map.insert(std::make_pair('D', 500));
x_map.insert(std::make_pair('M', 1000));
int res = 0;
for (int i = 0; i < s.size(); ++i) {
cout << i << s[i] << endl;
int val = x_map[s[i]];
if (i == s.size() - 1 || x_map[s[i+1]] <= x_map[s[i]]) {
res += val;
} else {
res -= val;
}
}
return res;
}
};

【top100】两数之和

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
解法：
用一个map，key是元素值，value是idx 看新来的这个元素的目标值（tgt - nums[i]）在不在map里，在的话把它的value拿出来就行了。。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> res;
unordered_map<int, int> map;
for (int i = 0; i < nums.size(); ++i) {
const int& tgt_val = target - nums[i];
if (map.find(tgt_val) != map.end()) {
res.push_back(map[tgt_val]);
res.push_back(i);
return res;
} else {
map.insert(std::make_pair(nums[i], i));
}
}
}
};

【top100】三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
vector<vector<int>> threeSum(vector<int>& nums)
{
int size = nums.size();
vector<vector<int> >res; // 保存结果（所有不重复的三元组）
if (size < 3) {
return res; // 特判
}
std::sort(nums.begin(), nums.end());// 排序（默认递增）
for (int i = 0; i < size; i++) // 固定第一个数，转化为求两数之和
{
if (nums[i] > 0) { // ！！！容易漏掉
return res; // 第一个数大于 0，后面都是递增正数，不可能相加为零了
}
// 去重：如果此数已经选取过，跳过
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// 双指针在nums[i]后面的区间中寻找和为0-nums[i]的另外两个数
int left = i + 1;
int right = size - 1;
while (left < right)
{
if (nums[left] + nums[right] > -nums[i]) {
right--; // 两数之和太大，右指针左移
} else if (nums[left] + nums[right] < -nums[i]) {
left++; // 两数之和太小，左指针右移
} else {
// 找到一个和为零的三元组，添加到结果中，左右指针内缩，继续寻找
vector<int> tmp {nums[i], nums[left], nums[right]};
res.push_back(tmp);
left++;
right--;
// 去重：第二个数和第三个数也不重复选取 ！！！容易漏掉
// 例如：[-4,1,1,1,2,3,3,3], i=0, left=1, right=5
while (left < right && nums[left] == nums[left-1]) {
left++;
}
while (left < right && nums[right] == nums[right+1]) {
right--;
}
}
}
}
return res;
}

矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
void setZeroes(vector<vector<int>>& matrix) {
int row = matrix.size();
int col = matrix[0].size();
// 用两个辅助数组，存这行和这列是否要变成0，
// 然后再遍历原矩阵，如果二者有一个要变0，那就变成0
vector<bool> rows(row, false);
vector<bool> cols(col, false);
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (matrix[i][j] == 0) {
rows[i] = true;
cols[j] = true;
}
}
}
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (rows[i] || cols[j]) {
matrix[i][j] = 0;
}
}
}
}

【top100】字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
其实就是个倒排
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string> > xmap;
for (auto& it: strs) {
string xit = it;
// 对string进行sort，搞成一个词，扔进map
sort(xit.begin(), xit.end());
xmap[xit].emplace_back(it);
}
vector<vector<string>> res;
for (auto& it: xmap) {
res.emplace_back(it.second);
}
return res;
}

【top100】无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
双指针
int lengthOfLongestSubstring(string s) {
set<char> set_char;
int res = 0;
// 双指针，两个指针都从头开始
for (int i = 0, j = 0; i < s.size() && j < s.size(); ) {
if (set_char.find(s[j]) != set_char.end()) {
//找到重复了，那就把起始的扔了
set_char.erase(s[i]);
++i;
} else {
if (j - i + 1 > res) {
res = j - i + 1;
}
set_char.insert(s[j]);
//没重复的，右指针继续往前找
++j;
}
}
return res;
}

【top100】寻找两个正序数组的中位数

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。
请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。
你可以假设 nums1 和 nums2 不同时为空。
示例 1:
​
nums1 = [1, 3]
nums2 = [2]
​
中位数是 2.0
​
示例 2:
​
nums1 = [1, 2]
nums2 = [3, 4]
​
中位数是 (2 + 3)/2 = 2.5
解答：
方法1(复杂度O(m+n))：
先归并两个数组，再取中点，归并的复杂度是O(m+n)，参考第88题https://leetcode-cn.com/problems/merge-sorted-array/description/​
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
vector<int> tmp;
int m = nums1.size();
int n = nums2.size();
int total_size = n + m;
tmp.resize(total_size);
// 倒着来
int i = m - 1;
int j = n - 1;
// 如果有重复的，也要复制两遍
while (j >= 0) {
if (i < 0) {
// 如果i数组遍历完了，要把j数据剩下的全部拷过来,记住是<j+1
for(int k = 0; k < j + 1; ++k) {
tmp[k] = nums2[k];
}
break;
}
if (nums2[j] > nums1[i]) {
// 留大的下来，留谁的就谁的指针--
// 注意是i + j + 1
tmp[i + j + 1] = nums2[j];
j--;
} else {
tmp[i + j + 1] = nums1[i];
i--;
}
}
if (j < 0) {
// 同理，j遍历完了就把i剩下的搞过来
for(int k = 0; k < i + 1; ++k) {
tmp[k] = nums1[k];
}
}
// 以上是归并两个数组的方法
if (total_size % 2 != 0) {
return tmp[total_size / 2];
} else {
return (tmp[total_size / 2 - 1] + tmp[total_size / 2]) *1.0 / 2;
}
}
方法2：二分查找

最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1：
​
输入：strs = ["flower","flow","flight"]
输出："fl"
示例 2：
​
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
注意这里说的是前缀，不是子序列，所以两个str都从0开始，同一个指针一起移动就行。。可以只遍历短的长度
另外，随着遍历的字符串变多，公共前缀是会变短的，变成0就可以return，如果完了还不是0，那就是要的了
另外，不用str[i]和str[i+1]比较再和prefix，直接str[i]和prefix比较就行，这样循环简单点
string longestCommonPrefix(vector<string>& strs) {
string comm_prefix = strs[0];
for (int i = 0; i < strs.size(); ++i) {
lcp_sub(strs[i], comm_prefix);
if (comm_prefix == "") {
return comm_prefix;
}
}
return comm_prefix;
}
void lcp_sub(const string &a, string& b) {
int len = min(a.length(), b.length());
int i = 0;
while(i < len) {
if (a[i] != b[i]) {
break;
}
++i;
}
if (a[i] != b[i]) {
b = b.substr(0, i);
} else {
b = b.substr(0, i + 1);
}
}
有点绕，还是抄答案吧：
string longestCommonPrefix(vector<string>& strs) {
string comm_prefix = strs[0];
for (int i = 0; i < strs.size(); ++i) {
lcp_sub(strs[i], comm_prefix);
if (comm_prefix == "") {
return comm_prefix;
}
}
return comm_prefix;
}
void lcp_sub(const string &a, string& b) {
int len = min(a.length(), b.length());
int i = 0;
// while一起判断了，就不用再对i i+1处理了。。
while (i < len && a[i] == b[i]) {
++i;
}
b = b.substr(0, i);
}

存在重复元素

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> xset;
for(auto& i: nums) {
if (xset.count(i)) {
return true;
}
xset.emplace(i);
}
return false;
}

整数反转

给定一个 32 位有符号整数，将整数中的数字进行反转。
示例：
示例 1:
输入: 123
输出: 321
​
示例 2:
输入: -123
输出: -321
​
示例 3:
输入: 120
输出: 21
注意:
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1]。根据这个假设，如果反转后的整数溢出，则返回 0。
解答
写一个valid函数，记得参数变成long，然后去看这个long是不是在int32的范围里
class Solution {
public:
bool valid(long x) { // 注意，这里要是long
if (x > 0) {
if (x >= pow(2, 31) -1)
return false;
}
if (x < 0) {
if (x <= -pow(2, 31)) {
return false;
}
}
return true;
}
​
int reverse(int x) {
long tmp = 0;
// 开始判断一下范围
if (!valid(x)) {
return 0;
}
bool flag = true;
// 统一变成正数，处理完如果原来是负的再变回去
if (x < 0) {
x = -x;
flag = false;
}
while (x != 0) {
tmp *= 10; // tmp向左移一位
tmp += x % 10; // 取出x的最低位
x /= 10; // x往右移一位
}
if (flag == false) {
tmp = -tmp;
}
// 结束再判断一下范围
if (valid(tmp)) {
return tmp;
}
return 0;
};

【top100】只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
异或：
  • 任何数和 0 做异或运算，结果仍然是原来的数
  • 任何数和其自身做异或运算，结果是 0
  • 异或运算满足交换律和结合律
所以
a^b^a=a^a^b=(a^a)^b=0^b=b
所以把所有数异或一遍就是那个只出现一次的数了。。
int singleNumber(vector<int>& nums) {
int res = 0; // 初始化为0
for (auto& i: nums) {
res ^= i;
}
return res;
}

【top100】有效的括号

给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串，判断字符串是否有效。
有效字符串需满足：
  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。
  • 注意空字符串可被认为是有效字符串。
示例 1:
​
输入: "()"
输出: true
示例 2:
​
输入: "()[]{}"
输出: true
示例 3:
​
输入: "(]"
输出: false
示例 4:
​
输入: "([)]"
输出: false
示例 5:
​
输入: "{[]}"
输出: true
解答：
注意一定要先判断st.size()>0再取top，不然会出错
class Solution {
public:
bool isValid(string s) {
stack<char> st;
unordered_map<char, char> mp;
// 先用map存一下左右括号的映射关系，
// 因为是栈，遇到右括号才想着pop，所以key是右括号！！
mp.insert(std::make_pair('}', '{'));
mp.insert(std::make_pair(']', '['));
mp.insert(std::make_pair(')', '('));
for (int i = 0; i < s.size(); i++) {
if (mp.find(s[i]) != mp.end() &&
st.size() > 0 &&
mp[s[i]] == st.top()) {
st.pop();
} else {
st.push(s[i]);
}
}
if (st.size() == 0) return true;
return false;
}
};

基础的括号匹配

假设一个表达式有英文字母（小写）、运算符（+，—，*，/）和左右小（圆）括号构成，以“@”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“YES”；否则返回“NO”。表达式长度小于255，左圆括号少于20个。
输入格式
一行：表达式
​
输出格式
一行：“YES” 或“NO”
解答：
栈的思想，可以不用栈，用一个变量top，遇到左括号++,右括号--，看最后是不是0
注意：
如果先出现了右括号，前面没有左括号的时候（top=0时出现了右括号），直接是NO
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
char c;
int top = 0;
int main()
{
for(; ; )
{
cin >> c;
if (c == '@') break;
if (c == '(') top++;
else if( c==')' && top > 0) {
top--;
} else if(c==')') {
cout << "NO";
return 0;
}
}
if(top == 0) {
cout<<"YES";
} else {
cout<<"NO";
}
return 0;
}

回文数

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1:
​
输入: 121
输出: true
示例 2:
​
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
​
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
解答
为了避免数字反转可能导致的溢出问题，为什么不考虑只反转 数字的一半？毕竟，如果该数字是回文，其后半部分反转后应该与原始数字的前半部分相同。
例如，输入 1221，我们可以将数字“1221”的后半部分从“21”反转为“12”，并将其与前半部分“12”进行比较，因为二者相同，我们得知数字 1221 是回文。
  • 特判
所有负数都不可能是回文，例如：-123 不是回文，因为 - 不等于 3
!!!!尾数能被10整除，即尾数是0的也不行，因为首位不是0
  • 反转
对于数字 1221，如果执行 1221 % 10，我们将得到最后一位数字 1，要得到倒数第二位数字，我们可以先通过除以 10 把最后一位数字从 1221 中移除，1221 / 10 = 122，再求出上一步结果除以10的余数，122 % 10 = 2，就可以得到倒数第二位数字。如果我们把最后一位数字乘以10，再加上倒数第二位数字，1 * 10 + 2 = 12，就得到了我们想要的反转后的数字。 如果继续这个过程，我们将得到更多位数的反转数字。
所以，每次把上一次的数字*10，加上这一次的最后一位数字，然后x/=10，把这次的尾数扔掉
现在的问题是，我们如何知道反转数字的位数已经达到原始数字位数的一半？
  • 终止
我们将原始数字除以 10，然后给反转后的数字乘上 10，所以，当除完的原始数字不大于反转后的数字时，就意味着我们已经处理了一半位数的数字。
例如，原数字是4123，反转到321>41的时候，就到一半了；如果原数字是412，反转到21>4的时候也到一半了。也就是反转的位数比剩下的多，肯定到一半了。或者，原数字是1234，反转到34>12
举个是回文数的例子，原数字是3223，32==32，break了；原数字121，12>1，break掉
当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123
由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。所以对于奇数位，就是判断x==revertedNumber/10
class Solution {
public:
bool isPalindrome(int x) {
if(x < 0 || (x % 10 == 0 && x != 0)) { //边界！！
return false;
}
int revertedNumber = 0;
while(x > revertedNumber) { // 大于
revertedNumber = revertedNumber * 10 + x % 10; // 这么判断
x /= 10;
}
return (x == revertedNumber || x == revertedNumber / 10);
}
};

【top100】盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
双指针！！
对于i，j两个点，能接的水量是min(num[i],num[j]) * (j - i)
这个时候应该移动的是num[i]和num[j]中较小的那个，因为j-i肯定会变小，
而想要变大，只能min(num[i],num[j])变大，所以要把小的移一下试试，如果小的在左边那就右移，否则同理
int maxArea(vector<int>& height) {
// 对于i，j两个点，能接的水量是min(num[i],num[j]) * (j - i)
// 这个时候应该移动的是num[i]和num[j]中较小的那个，因为j-i肯定会变小，
// 而想要变大，只能min(num[i],num[j])变大，所以要把小的移一下试试，如果小的在左边那就右移，否则同理
int max_res = 0;
int i = 0, j = height.size() - 1;
while (i < j) {
int cur_water = min(height[i], height[j]) * (j - i);
max_res = max(max_res, cur_water);
if (height[i] >= height[j]) {
--j;
} else {
++i;
}
}
return max_res;
}

最接近的三数之和

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
解法
「最接近」即为差值的绝对值最小
类似三数之和，双指针，固定第一个数，希望剩下b+c最接近target
int threeSumClosest(vector<int>& nums, int target) {
int n = nums.size();
if (n < 3) {
return -1;
}
sort(nums.begin(), nums.end());
int dist = INT_MAX;
int res = INT_MIN;
for (int i = 0; i < n; ++i) {
int left = i + 1;
int right = n - 1;
// 保证和上一次枚举的元素不相等
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum < target) {
++left;
// 注意，这个和三数之和那题的位置不一样
while (left < right && nums[left] == nums[left - 1]) {
left++;
}
} else if(sum > target) {
--right;
// 注意，这个和三数之和那题的位置不一样
while (left < right && nums[right] == nums[right + 1]) {
--right;
}
} else {
return sum;
}
if (dist > abs(sum - target)) {
res = sum;
dist = abs(sum - target);
}
}
}
return res;
}

Z 字形变换

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
P A H N
A P L S I I G
Y I R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
请你实现这个将字符串进行指定行数变换的函数：
示例 2：
输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P I N
A L S I G
Y A H R
P I
画个图，直接找出新字符串每一位对应原来的下标
会向下填写 r 个字符，然后向右上继续填写 r−2 个字符(斜线的r扣掉最后一行，和新的第一行的各一个字符)，所以变换周期是t=2r-2。
所以第一行的下标都是2r-2的倍数即0+kt，而最后一行就应该是r-1 + kt
而中间的第i行，除了k个数外，每一轮间还有一个数，那个数是(k + 1)t-i
string convert(string s, int numRows) {
int t = 2 * numRows - 2;
int i = 0;
if (t == 0) {
return s;
}
int round = s.length() / t;
string res;
while (i < numRows) {
int k = 0;
int idx = 0;
if (i == 0) {
while (k <= round) {
idx = k * t;
if (idx < s.length()) {
res.push_back(s[idx]);
}
k++;
}
} else if (i < numRows -1) {
k = 0;
while (k <= round) {
idx = i + k * t;
if (idx < s.length()) {
res.push_back(s[idx]);
}
idx = (k + 1) * t - i;
if (idx > 0 && idx < s.length()) {
res.push_back(s[idx]);
}
++k;
}
} else {
k = 0;
while (k <= round) {
idx = numRows - 1 + k * t;
if (idx < s.length()) {
res.push_back(s[idx]);
}
k++;
}
}
++i;
}
return res;
}
标准答案简单很多：
其实就是。。而中间的第i行，除了k个数外，每一轮间还有一个数，那个数是(k + 1)t-i = kt + t-i
这样，就都有kt了
所以就是每个周期塞两个数（不越界的情况下），
第一个数是每个周期的起始下标kt + i
第二个数是kt+t-i
限制一下最后一行和第一行只插入一个数，不然会出问题！！
string convert(string s, int numRows) {
int t = 2 * numRows - 2;
int i = 0;
if (t == 0) {
return s;
}
int round = s.length() / t;
string res;
while (i < numRows) {
for (int j = 0; j + i < s.length(); j += t) {
// 循环k轮，枚举每轮的起始下标
res.push_back(s[j + i]); // 当前周期第一个字符
// 注意，这里要限制0<i < numRows -1，因为第一行和最后一行只加一个数！！！！！
if (0 < i && i < numRows - 1 && j + t - i < s.length()) {
res.push_back(s[j + t - i]);
}
}
++i;
}
return res;
}

删除有序数组中的重复项

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
解法
双指针，一快一慢，如果遇到不相等的，那就把快的值复制到慢的下一位，两个指针继续移动。
int removeDuplicates(vector<int>& nums) {
if (nums.size() == 0) return 0;
int i = 0;
for (int j = 1; j < nums.size(); j++) {
if (nums[j] != nums[i]) {
// 不相等，且j比i快，那就说明ij中间可能是一串重复的数，
// 就把num[j]赋值给num[i+1],然后两个指针都往后移
nums[i + 1] = nums[j];
++i;
}
}
return i + 1;
}

螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
  • 首先设定上下左右边界
  • 其次向右移动到最右，此时第一行因为已经使用过了，可以将其从图中删去，体现在代码中就是重新定义上边界
  • 判断若重新定义后，上下边界交错，表明螺旋矩阵遍历结束，跳出循环，返回答案
  • 若上下边界不交错，则遍历还未结束，接着向下向左向上移动，操作过程与第一，二步同理
  • 不断循环以上步骤，直到某两条边界交错，跳出循环，返回答案
vector<int> spiralOrder(vector<vector<int>>& matrix) {
// 首先设定上下左右边界
// 其次向右移动到最右，此时第一行因为已经使用过了，可以将其从图中删去，体现在代码中就是重新定义上边界
// 判断若重新定义后，上下边界交错，表明螺旋矩阵遍历结束，跳出循环，返回答案
// 若上下边界不交错，则遍历还未结束，接着向下向左向上移动，操作过程与第一，二步同理
// 不断循环以上步骤，直到某两条边界交错，跳出循环，返回答案
vector<int> res;
if (matrix.empty()) {
return res;
}
int up = 0;
int right = matrix[0].size() - 1;
int down = matrix.size() - 1;