代码随想录第一天-Toy模板网

这篇具有很好参考价值的文章主要介绍了代码随想录第一天。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

（一）基础知识

（1）c++基础知识

1.1 class solution

class表示声明一个类，solution表示解决方案。那么class Solution就是声明一个解决方案的类，类中用来存放关于解决这一问题所需要的各种函数和变量。
这样做的好处有：

生成若干实例互不干扰，每个类的实例内部的（非静态）成员变量是独立的。
对主函数没有任何干扰，不会污染到其他地方的代码，而void定义一种函数定义的变量是全局状态下的，比如变量的命名。

1.2 vector

vector是向量类型，可以容纳许多类型的数据，故称为容器（可以类比为动态数组，是封装好的类）

初始化
代码

vector<int> v1;
vector<string> v2;
vector<vector<int> >;  //注意空格。这里相当于二维数组int a[n][n];
vector<int> v3 = {1,2,3,4,5}; //列表初始化
vector<string> v4 = {"hi","my","name","is","lee"};
vector<int> v5(3,1); //初始化为1,1,1。第一个参数是数目，第二个参数是要初始化的值
vector<string> v6(3, "hi");
vector<int> v7(5); //默认初始化为0
vector<int> v8(5); //默认初始化为空字符串

1.3 vector& nums

带&表示传入函数的是vector的引用（即物理位置），函数内部对vector改动，vector就会改变；
不带&表示传入的是vector的复制品（开辟了另一块位置），函数内部对其改动，不会影响原本的vector。

1.4 其他问题

当在DevC++敲完代码后，代码如下：

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
class Solution {
public:
	int search(vector<int> &nums,int target){
		int left=0;
		int right=nums.size() - 1;
		while(left <= right)
		{
			int middle = (left + right) / 2;
			if(target < nums[middle])
				right = middle - 1;
			else if(target > nums[middle])
				left = middle + 1;
			else
				return middle;
			return -1;	
		}
	}
};

int main()
{
	Solution s;
	vector<int> nums={1,2,3,4,5,6};
	int target = 3;
	cout << s.search(nums,target) << endl;
	return 0;
}

编译失败，出现如下图的问题：
代码随想录第一天
通过查询CSDN找到了解决办法，对DevC++进行设置后，成功编译运行，方法见以下链接：
链接: 成功解决C++编译器报错[Error]in C++98 ‘arr‘ must be initialized by constructor, not by‘{…}‘

（2）数组

数组是存放在连续内存空间上的相同类型数据的集合。

数组下标都是从0开始的。
数据内存空间的地址是连续的，在删除或者添加元素的时候，需要移动其他元素的地址

（二）二分查找

题目: 二分查找

（1）二分查找思想

2.1 左闭右闭[left,right]

while (left <= right) 要使用 <= ，因为left == right是有意义的（如[1,1]中，1是合法的），所以使用 <=
if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1
if (nums[middle] < target) left要赋值为 middle+1，因为当前这个nums[middle]一定不是target，那么接下来要查找的右区间开始下标位置就是 middle + 1

2.2 左闭右开[left,right)

while (left < right)， ,因为left == right在区间[left, right)是没有意义的（如[1,1)中，1不是合法的），所有使用 <
if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]
if (nums[middle] < target) left要赋值为 middle+1，因为当前这个nums[middle]一定不是target，那么接下来要查找的右区间开始下标位置就是 middle + 1（和左闭右闭相同）

（2）代码实现

class Solution {
public:
	int search(vector<int>& nums,int target){
		int left=0;
		int right=num.size() - 1;
		while(left <= right)
		{
			int middle = (left + right) / 2;
			if(target < nums[middle])
				right = middle - 1;
			else if(target > nums[middle])
				left = middle + 1;
			else
				return middle;
			return -1;	
		}
	}
};

（三）移除元素

题目: 移除元素文章来源地址https://www.toymoban.com/news/detail-459103.html

（1） erase函数

时间复杂度O(n)
a.erase（p）: 删除p指向的元素
a.erase（p,q）：删除区间（p,q）中的元素

（2）暴力解法

时间复杂度O(n^2)
空间复杂度O(1)
代码实现：

// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size = nums.size();
        for (int i = 0; i < size; i++) {
            if (nums[i] == val) { // 发现需要移除的元素，就将数组集体向前移动一位
                for (int j = i + 1; j < size; j++) {
                    nums[j - 1] = nums[j];
                }
                i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
                size--; // 此时数组的大小-1
            }
        }
        return size;

    }
};

（3）双指针法

双指针法（快慢指针法）：通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
快指针：寻找新数组的元素，新数组就是不含有目标元素的数组
慢指针：指向更新新数组下标的位置
代码实现：

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
class Solution{
public:
	int removeElement(vector<int>& nums,int val)
	{
		int slowIndex = 0;//慢指针
		for(int fastIndex = 0;fastIndex < nums.size();fastIndex++)
		{
			if(val != nums[fastIndex])
				nums[slowIndex++] = nums[fastIndex];
				//这里也可以写成两步:
				//nums[slowIndex] = nums[fastIndex];
				//slowIndex ++ ; 
		 } 
		 //按照逻辑来说应该返回slowIndex+1，但是slowIndex ++。
		 //举个例子，如果nums={1,3}，val=3，那么1满足，这个时候slowIndex++变为1,3不满足,不对val进行操作，slowIndex=1，返回值为1，也就是正确长度 
		return slowIndex ;
	}
};
int main()
{
	Solution s;
	vector<int> nums = {1,2,3,4,3,5,3};
	int val = 3;
	cout << s.removeElement(nums,val) << endl; 
}