目录
2024-03-08 leetcode写题记录
27. 移除元素
题目链接
题意
给你一个数组\(nums\)和一个值\(val\)，你需要原地移除所有数值等于\(val\)的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用\(O(1)\)额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
解法
遍历一遍，把不等于\(val\)的值都\(swap\)到前面即可。
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int n = nums.size(), idx = 0;
for (int i = 0; i < n; ++i) {
if (nums[i] == val)
continue;
swap(nums[idx], nums[i]);
idx++;
}
return idx;
}
};
179. 最大数
题目链接
题意
给定一组非负整数\(nums\)，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。
解法
用贪心的想法想一下，两个数的比较其实就是在比哪个数在前时能让整个数变得更大。
注意，\(f()\)会爆\(int\)。
class Solution {
public:
int f(int x) {
long long res = 10;
while(x >= res) res *= 10;
return res;
}
string largestNumber(vector<int>& nums) {
sort(nums.begin(), nums.end(), [&](int& x, int& y) {
int xx = f(x), yy = f(y);
return 1ll * x * yy + y > 1ll * y * xx + x;
});
if (nums[0] == 0) return "0";
string res = "";
for (int x : nums)
res += to_string(x);
return res;
}
};
75. 颜色分类
题目链接
- 颜色分类
题意
给定一个包含红色、白色和蓝色、共\(n\)个元素的数组\(nums\)，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数\(0、1\)和\(2\)分别表示红色、白色和蓝色。
必须在不使用库内置的\(sort\)函数的情况下解决这个问题。
解法
遍历一遍，是\(0\)就扔左边，是\(2\)就扔右边，处理好边界就行了。
class Solution {
public:
void sortColors(vector<int>& nums) {
int n = nums.size(), l = 0, r = n - 1;
for (int i = l; i <= r; ++i) {
if (nums[i] == 0)
swap(nums[l++], nums[i--]);
else if (nums[i] == 2)
swap(nums[r--], nums[i--]);
if (i < l - 1) i = l - 1;
}
}
};