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;