乐趣区

关于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();}
};
退出移动版