@Author：清秋橘 Autumn_Tangerine
@Date：2022/10/9
@Last Modified：2022/10/9
@Connect：775786777
序言
为了参加明年的蓝桥杯竞赛（PS：其实是想去打ICPC或者更高级别的算法竞赛的，但是无奈没有参加实验室也没有更好地资源，只好去蓝桥杯水一水了），从这个礼拜开始每天刷两道力扣题，一个礼拜总结一次，写笔记浅浅记录一下，就当做是题解了吧
这篇文章包括LeetCode以下内容的算法题：
- 1.两数之和
- 26.删除有序数组中的重复项
- 27.移除元素
- 35.搜索插入位置
- 66.加一
- 88.合并两个有序数组
- 108.将有序数组转化为二叉搜索树
- 118.杨辉三角
- 119.杨辉三角II
阅读这篇文章可以学到哪些算法知识
- 双指针
- 递归
- 哈希表
- 二分法
正文
两数之和
题目的要求是给定一个整数数组 nums 和一个整数目标值 target，在该数组中找出 和为target的那两个整数，并返回它们的数组下标，数组无序且只有一种答案
很经典的力扣第一题，刚开始刷题的时候试过暴力破解法，时间复杂度自然是双重循环O（n²），意料之中的超时，所以查看题解，发现题解采用了哈希表，达到了O(n)的时间效率
大概的思路是先将所有的数先存在一个Map里面(Map里的不可重复)，然后使用元素遍历这个Map，再从Map里搜索target-这个元素，刚开始的时候很奇怪，既然在第一层循环里还要再进行一遍搜索操作，那不时间复杂度又是O(n²)了吗？后来问了度娘才知道，类似Map这种结构在实现的时候，会实现一个哈希表或者红黑树，然后实现一种类似于索引的查询，所以在搜索的时候并不需要遍历整个数组，所以时间复杂度可以理解成O(N)
所以一开始根据哈希值搜索，刚于是用C语言手写了一个哈希表出来(代码很长就不贴了)，后来发现官方题解C++的代码很少，只有几行，原来是C++的Map就已经实现了类似的结构，最关键的是C++的map结构可以根据key-value进行匹配搜索，于是照着写了一个，成功AC
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int,int> hashTable;
for(int i =0; i < nums.size(); i++){ //遍历这个Map
vector<int> f(2,-1);
if(hashTable.count(target-nums[i])){ //如果Map中存在这个元素
f[0] = hashTable[target-nums[i]]; //Map可以按照key-value搜索
f[1] = i;
return f;
}
hashTable[nums[i]] = i;
}
return {}; //返回一个空Map
}
};
其实这道题最关键的还是key-value的匹配搜索方式以及建立一个Map再把元素放进去的思路吧
删除数组中的重复项
题目要求是给出一个 升序排列 的数组 nums ，原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致
根据上一题的思路的话，第一次想到的也是建立一个不允许重复的数组，然后把元素一个一个放进去，但是后面发现题目要求是原地删除，然后换了一种思路，就是遍历这个数组，然后比较前一个元素和下一个元素的值，因为是升序排列，所以相等的元素肯定会在一起排列，遇到相等的就把他删除掉，可是这样的话，有个问题，就是每次删除之后，需要把之后的元素全部前移一位，本来O(N)的时间复杂度瞬间暴增为O(N²)
于是又一次的查看题解(滑稽)，发现题解采用了一种更为巧妙的思路——双指针法
大概思路是记录两个位置，一个位置i用于遍历数组，一个位置j记录元素保存的位置。或者说检查过的元素位置，然后遍历这个数组的 同时，遇到不相等的就把元素保存在j的位置，因为j的位置肯定在i之前，所以并不会对i的遍历造成影响
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int x = 0; //指针1
for(int i = 0; i < nums.size(); i++){ //指针2
if(i == nums.size()-1){
nums[x] = nums[i];
}
else if(nums[i+1] != nums[i]){
nums[x] = nums[i];
x++;
}
else{
length--;
}
}
return length;
}
};
其实与比起双指针法，我更愿意将其理解为双位置法或者双进度法，因为它的实现并不一定非要借助C语言中狭义的指针，甚至可以只用一个int记录位置，但是关键的是遍历数组的同时有两个进度正在向前推进
### 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置
第一时间想到的还是根据Map的key-value搜索，但是后来一想，这样做的，首先放入Map的操作就已经是O(N)了，在此之上还要进行搜索的操作，采用最原始的遍历搜索也才O(N)的复杂度，这不脱了裤子放屁吗
所有换成了一种在搜索有序数组中常用的方法——二分法
大概思路是一个left指针，一个right指针，然后两个指针不断二分从而向目标值靠近，这样搜索的时间复杂度由于是一次减少一般元素，所以时间复杂度是O(log2N)，元素越多效率越快
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0;
int right = nums.size()-1;
while(left <= right){ //截止条件
int mid = (right + left) / 2;
if(nums[mid] >= target) right = mid - 1;
else if (nums[mid] < target) left = mid + 1;
}
return left;
};
};
二分法的关键是截止条件 左面指针的值 <= 右面指针的值，还有两个关键的点就是进行二分操作时，左面换到中间时应该在原mid的基础上-1，右面应该在原mid的基础上+1，否则循环会无法终止
这里有个小插曲是，本来我想着，如果一开始mid的值就是要寻找的值，但是按上面这种算法的话，其实还需要进行一遍循环，于是我把算法改为了下面这样，在while里面增加了一个if判断
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0;
int right = nums.size()-1;
while(left <= right){
int mid = (right + left) / 2;
if(nums[mid] > target) right = mid - 1;
else if (nums[mid] < target) left = mid + 1;
else return mid;
}
return left;
};
};
结果奇怪的是，执行效率从4ms暴增到8ms，直接翻了一倍，具体原因不太清楚，可能是加了个判断在每次while时都需要执行一遍比偶尔多执行一遍while要麻烦多了
加一
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一
算是我认为目前为止遇到的，比较难的一道题吧，但是通过率确比其他题要高不少，我果然和一般人菜的不在一个点上
没有涉及到什么其他算法知识，重要的是思路，比如在末尾+1的时候，如果末尾是9，那么此时应该怎么处理，如果末尾和末二位是99，又怎么处理，所以关键其实是找到末尾如果是9的话，向前到首位有多少个连续的9
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int i = digits.size()-1;
digits[i]++; //先把末尾+1
while(digits[i] == 10){ //如果当前位置变成10的话
if(i == 0){ //这里主要处理比如[9，9]这种情况，需要把数组扩大一位然后首位放1，其他位置0
vector<int> ans(digits.size() + 1);
ans[0] = 1;
return ans;
}
digits[i] = 0; //把当前位置变为0
digits[i-1]++; //前一位+1
i--; //向前推进一位
}
return digits;
};
};
感觉没什么意义的一道题…
合并两个有序数组
给出两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目， 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列
很简单的一道题。关键是看你想手写一个排序，还是用他库自带的排序
自己以前做的时候手写过一个归并和快排，这里只贴一个用库自带的排序的吧
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
for(auto x : nums2){
nums1[m] = x;
m++;
}
sort(nums1.begin(), nums1.end());
}
};
嗯，还有就是auto真的好用
将有序数组转化为二叉搜索树
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树
首先得弄明白高度平衡二叉搜索树是个什么东西
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
个人感觉算是简单难度里难度中上的一道题
一般涉及到树结构的题，往往解题思路里都会有一种，就是递归，因为二叉树本身的结构就符合递归这种由大到小都采用类似的结构，这道题要求是高度平衡树，所以把根节点设为构成这个数的元素的中值，因为这样的话，对于每个根节点，其左右树的元素个数都是相等或者最多相差1，也就是每一个子树都是高度平衡树，这样最后合在一起构建出来的树结构自然是一个高度平衡树
一般来说树的递归函数思路，都是先设置截止条件，然后设置根节点，然后对左子树进行处理，再对右子树进行处理
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return arrayToBSTHelper(nums, 0, nums.size()-1);
}
TreeNode* arrayToBSTHelper(vector<int>& nums, int start, int end){
if(end < start) //截止条件
return nullptr;
int mid = (start + end) / 2;
TreeNode* root = new TreeNode(nums[mid]); //设置根节点
root->left = arrayToBSTHelper(nums, start, mid-1); //处理左子树
root->right = arrayToBSTHelper(nums, mid+1, end); //处理右子树
return root;
}
};
这里的截止条件参考了之前二分法的截止思路，就是start与end不断靠近，然后end<start的时候截止
杨辉三角
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行
下面这个图就是杨辉三角，是算法里相当经典的一个图形了
在做这道题的时候，一开始是用C写的，但是在写的时候，发现力扣给我构造的soluation函数里面有两个非常奇怪的参数
int** generate(int numRows, int* returnSize, int** returnColumnSizes)
函数返回一个二维数组，numRows为需要传入的行参数，但是那时候并不能太理解returnSize和returnColumnSizes是干什么用的，最后就这个问题，在电脑面前呆坐了两个多小时，还是在百度的帮助下，想了快半个下午，终于想明白了，returnSize是你的答案，即返回的二维数组，它有几行，而returnColumnSizes是对于每一行，分别有多少列
那么，这里就出现了两个新的问题，一个是returnSize不是肯定和numRows相等吗，为什么要多此一举，第二个问题是returnColumnSizes为什么要使用一个二重指针，既然是返回每一行的列数，用一个一维数组指针不就好了吗？
对于第一个问题，思考后个人认为，其实这一道题是没要必要非得返回returnSize的，但是力扣应该是对于这类题都有一个统一的模板去测试答案是否正确，当然不可能为每一道题都设计一个测试的主函数，所有对于这道题，它的行数可能是确定的 ，就是numRows，但是，对于其他的题，可能就不一定了，不可能说这道题测试的时候用numRows，但是其他题又用returnSize去测试，所以，力扣干脆让你不管实际上有没有用，都返回一个returnSize，这样就可以用一个统一的测试程序去测试了
至于第二个问题，其实我一直想不通，为此我还以为是我对二重指针的理解出了问题，还又翻过头去去把二重指针，二维指针数组，二维数组指针这些全都复习了一遍，但是结果发现，按传入一个一重指针，比如*returnSizes，然后再在这个函数里对returnSize分配内存并修改也是完全可行的，而且官方题解里面，也只是对*returnColumnSizes进行了操作，也就是只把数据放在了这个 二维数组里第一行里面，而其他行并没有存放数据，所以，很迷惑，很可能和第一个问题的原因有点关系吧…
说回这个问题，因为想练习一下自己对于指针的操作，所以尝试用C写了一个
int** generate(int numRows, int* returnSize, int** returnColumnSizes){
int **ret;
ret = (int**)malloc(sizeof(int*)*numRows);
*returnSize = numRows;
*returnColumnSizes = (int*)malloc(sizeof(int)*numRows);
for(int i = 0; i < numRows; i++){
(*returnColumnSizes)[i] = i + 1;
ret[i] = (int*)malloc(sizeof(int)*(i+1));
ret[i][0] = 1;
for(int j = 1; j < i; j++ ){
ret[i][j] = ret[i-1][j-1] + ret[i-1][j];
}
ret[i][i] = 1;
}
return ret;
}