关于leetcode:刷题心得-leetcode-704-leetcode-27

leetcode 704 题目链接:
https://leetcode.com/problems/binary-search/

尝试 c++ 写题,搭建架子代码(尝试搭建ACM格调)

class Solution
{
public:
    int search(vector<int> &nums, int target)
    {
    }
};

int main()
{
    Solution sol;
    vector<int> nums = {-1, 0, 3, 5, 9, 12};
    sol.search({-1, 0, 3, 5, 9, 12}, 9);
    // 十分量援用的初始值必须为左值
    // initial value of reference to non-const must be an lvalue
}

https://blog.csdn.net/hou09tian/article/details/80565343
这边文章解释的很分明了,十分量援用传参进去后可能会被批改,如果是个右值显然是不行的

再次运行报不能够初始化,原来vscode默认只反对c++98规范,在.vscode里的task.json增加”-std=c++11“编译参数即可

算法思路文章参考:
https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E…

最终ac代码:(左闭右开)

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int search(vector<int>& nums, int target) {
        size_t start = 0;
        size_t end = nums.size();
        while (start < end) {
            size_t middle = start + ((end - start) >> 1);
            if (nums[middle] == target) {
                return static_cast<int>(middle);
            } else if (nums[middle] > target) {
                end = middle;
            } else {
                start = middle + 1;
            }
        }

        return -1;
    }
};

再次尝试左闭右闭:

class Solution
{
public:
    int search(vector<int> &nums, int target)
    {
        size_t start = 0;
        size_t end = nums.size() - 1;
        while (start <= end)
        {
            size_t middle = start + ((end - start + 1) >> 1);
            if (nums[middle] == target)
            {
                return static_cast<int>(middle);
            }
            else if (nums[middle] > target)
            {
                end = middle - 1;
            }
            else
            {
                start = middle + 1;
            }
        }

        return -1;
    }
};

[5], -5 的用例过不去,tle了,将size_t改为int,通过。
能够看出为什么api之类的都采纳左闭右开,写进去的代码更天然,计算区间什么的也更间接。

leetcode 27 题目链接:
https://leetcode.com/problems/remove-element/

ac代码:

class Solution
{
public:
    int removeElement(vector<int> &nums, int val)
    {
        for (vector<int>::iterator it = nums.begin(); it != nums.end();)
        {
            if (*it == val)
            {
                it = nums.erase(it);// O(n) time complexity
            }
            else
            {
                it++;// prefer pre-increment for post-increment making a temporary copy

            }
        }

        return nums.size();
    }
};

【腾讯云】轻量 2核2G4M,首年65元

阿里云限时活动-云数据库 RDS MySQL  1核2G配置 1.88/月 速抢

本文由乐趣区整理发布,转载请注明出处,谢谢。

您可能还喜欢...

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据