283. 移动零

发表于2024-12-25|更新于2025-01-27|LeetCode热题100

|总字数:93|阅读时长:1分钟|浏览量:|评论数:

【题目】：283. 移动零

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        for(int l = 0, r = 0; r < nums.size(); ++r) {
            if(nums[r] != 0) {
                swap(nums[l++], nums[r]);
            }
        }
    }
};

时间复杂度: O(n)
空间复杂度: O(1)

先把非0的元素移到前边，后边剩下的就是0了。
l：非0元素的末尾
r：0元素的开头

文章作者: 小林

文章链接: http://example.com/post/c150202b.html

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源欢迎来到小林的博客！

算法 LeetCode热题100 双指针

相关推荐

11. 盛最多水的容器

【题目】：11. 盛最多水的容器 class Solution {public: int maxArea(vector<int>& height) { int n = height.size(); int res = (n - 1) * min(height[0], height[n - 1]); for(int l = 0, r = n - 1; r > l;) { if(height[l] < height[r]) { // 移动更短的木棍 l++; }else { --r; } res = max(res, (r - l) * min(height[l], height[r])); // 每次记录当前遍历过的最大值 } return...

15. 三数之和

【题目】：15. 三数之和 class Solution {public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> res; sort(nums.begin(), nums.end()); for(int i = 0; i < nums.size(); ++i) { if(nums[i] > 0) { break;// 因为是升序排列，如果当前数>0，三数值和一定>0，后边的数字都可以做剪枝 } if(i != 0 && nums[i] == nums[i - 1]) { continue; // 去除重复的三元组 ...

128. 最长连续序列

【题目】：128. 最长连续序列 class Solution {public: int longestConsecutive(vector<int>& nums) { unordered_set<int> ss(nums.begin(), nums.end()); int res = 0; for(int s : ss) { if(ss.find(s - 1) != ss.end()) { continue; // 说明s一定不是开头 } // s是开头 int y = s + 1; while(ss.find(y) != ss.end()) { y++; } res = max(y - s, res); ...

49. 字母异位词分组

【题目】：49. 字母异位词分组方法1：直接对字符串进行排序后使用map存储相同的字母异位词，再把map的value依次存放到结果中。 class Solution {public: vector<vector<string>> groupAnagrams(vector<string>& strs) { vector<vector<string>> res; unordered_map<string, vector<string>> mp; for(string str : strs) { string temp = str; sort(str.begin(), str.end()); mp[str].push_back(temp); } for(auto [key, value] : mp)...

1052. 爱生气的书店老板

【题目】：1052. 爱生气的书店老板 class Solution {public: int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) { int maxAddCount = 0; // 在minutes长度内，还能增加的最大顾客满意人数 int curAddCount = 0; // 当前窗口内还能增加的顾客满意数 int curCount = 0; // 原本有的顾客满意数 int n = customers.size(); for(int l = 0, r = 0; r < n; ++r) { if(grumpy[r] == 1) { // 把老板从生气变成不生气 curAddCount += customers[r]; ...

114. 二叉树展开为链表

【题目】：114. 二叉树展开为链表这题要将一个二叉树转成单链表，且展开后的单链表应该和二叉树的先序遍历相同。如果直接正向思考：能不能先序遍历，先处理当前节点（把当前遍历到的节点插入到单链表中），但是这样存在一个问题，此时当前节点的右孩子还没有被遍历到，这样会出现孩子丢失的情况。考虑逆向思考：题目要求先序遍历（根左右）的结果，那能不能用后序遍历（左右根）呢？这样就不会出现孩子丢失的问题，因为当去更新当前的右指针时，已经遍历过他的右节点了。但是如果是后序遍历的话，结点的顺序应该怎么处理呢？目前节点的顺序是和题目所求的节点顺序相反，因此可以考虑头插法。 class Solution {public: TreeNode* res = nullptr; void help(TreeNode* root) { if(root == nullptr) { return; } // 右 help(root->right); // 左 ...

评论