https://github.com/youngyangyang04/leetcode-master
数组部分
2020.9.8
-
搜索插入位置
一道简单的二分题目，提到有序数组，就可以用二分试一试。我目前用的是C++，在评论区看到一个代码，return lower_bound(nums.begin(),nums.end(),target) - nums.begin();lower_bound适用于排过序的数组，且底层算法的时间复杂度为O(n)
📌与二分查找相关的三个函数，函数内部使用二分查找实现
#include<algorithm>前提：有序数组
1️⃣lower_bound(起始地址，结束地址，查找元素)左闭右开的区间，查找第一个大于等于指定元素的位置（第一个可插入的位置），若无，则返回end（超界）
2️⃣upper_bound(起始地址，结束地址，查找元素)左闭右开，查找第一个大于指定元素的位置（最后一个可插入的位置），若无，则返回end（超界）
3️⃣binary_search(起始地址，结束地址，查找元素)左闭右开区间，返回bool值 -
移除元素
双指针方法，没什么特别的 -
删除排序数组中的重复项
同上题，双指针法 -
长度最小的子数组
双指针或者滑动窗口法，两个指针start、end，end遍历整个数组，求以end为最后一个元素的满足子数组元素之和大于s的数组最小长度，start随着滑动窗口内元素之和进行调整，时间复杂度为O(n)
还有一个O(nlogn)的算法，待补（❓）可能有什么特殊的方法需要学习吧
2020.9.10
-
螺旋矩阵 2
明明是一道很简单的模拟题，被我做出了高考数学最后一个大题的感觉，说到底还是细节把握的不好，编程习惯可能也不好，总之就是都不好，要多练练啊，脑子想的和动手编程的结果真的不一样。
我犯的几个错误：
- 题目输出要求的是vector，我在定义vector的时候没有初始化，后面直接采用数组的形式进行赋值，oh～
- for循环中用于控制循环次数的变量i，我保留了它，用到下一个for循环中，却忘记了上一个循环是因为i不满足循环条件了才退出的，把i当成是符合条件的最后一个数值进行运算，导致数据越界，shift！
基本的思路就是一圈一圈填充，我是用每一圈的宽度来控制计算坐标值，在题解区看到有人定义四个变量来控制边界，真的很简洁，代码也很简洁，需要学习～
class Solution {
public int[][] generateMatrix(int n) {
int l = 0, r = n - 1, t = 0, b = n - 1;
int[][] mat = new int[n][n];
int num = 1, tar = n * n;
while(num <= tar){
for(int i = l; i <= r; i++) mat[t][i] = num++; // left to right.
t++;
for(int i = t; i <= b; i++) mat[i][r] = num++; // top to bottom.
r--;
for(int i = r; i >= l; i--) mat[b][i] = num++; // right to left.
b--;
for(int i = b; i >= t; i--) mat[i][l] = num++; // bottom to top.
l++;
}
return mat;
}
}
2020.9.11
大清早来，我决定先把“螺旋矩阵2”再写一遍，是烦躁的一天还是开心的一天就看它的了——早上比较清醒，一遍过，开心~开始科研
-
二维数组并不是n*m的连续地址空间组成的
二维数组 - 忽然看到了一个熟悉的题目就做了一下 编辑距离
一发A，感觉自己dp基础知识掌握的还不错，这题有点像最长公共子串的长度 - 必须掌握的数组理论知识
2020.9.12
今日份睡觉和科研任务比较重
- 四数之和 和之前做过的三数之和几乎完全一样
-
环形链表 II 双指针法
环形列表需要使用双指针法，两指针相遇则存在环，这题可能不需要数学推导，知道快慢指针由于速度不同终将相遇即可，而对于 II 这道题需要判断环的入口位置，我虽然能想到双指针，但不知道需要数学推导出相遇位置与入口位置之间的关系（吃一堑长一智，我觉得在做题的时候，如果知道了大体的方法，但方法的结束点和最终要达成的目的看似没什么联系，先想想贪心算法蒙一下，实在不行，看看有没有什么数学上的值的关系，当时我能手动模拟一下也好啊，说不定就发现了，后悔）
模拟图
官方题解的公式我觉得有点问题，下面是我的公式：
2(F+a)=F+n(a+b)+a (n表示快指针比慢指针多走的圈数)
F=n(a+b)-a=(n-1)(a+b)+b
也就是说无论n取何值，从head出发的速度为1的指针和从相遇点出发的速度为1的指针，一定会在入口处相遇
/*写给自己：注意fast和low的起点必须一样，和之前的程序有一点小小的不同，之前不用考虑是否起点一致，只要能相遇就行
在这里如果起点不一致的话，不能同时出发然后相遇于入口点，需要添加一些常数来补充*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(head==NULL || head->next==NULL) return NULL;
ListNode* low=head;
ListNode* fast=head;
while(fast!=NULL && fast->next!=NULL){
low=low->next;
fast=fast->next->next;
if(fast==low) break;
}
if(fast==NULL|| fast->next==NULL) return NULL;
ListNode* p=head;
while(p!=low){
p=p->next;
low=low->next;
}
return low;
}
};
2020.9.15
这几天因为科研上的一些问题，没有做题，今天抽出点时间，准备刷leetcode的数组分类下的题目，就从简单的开始吧。
- 转置矩阵 行列交换
- 🎈主要元素
摩尔投票法（默认存在众数的情况下） 本题最后要加上一个循环来进行验证 -
有序数组的平方
一定不要忽略“有序”这个词，使用双指针法 -
三个数的最大乘积
贪心，排序后，最大乘积只可能出现在两种情况下 - 存在连续三个奇数的数组
-
存在重复元素 II
是一个处理不好就会超时的题，O(nlogn)排序后就会超时
解决方法：k的滑动窗口，Set（hashset）
✨总结：
题型：查找是否存在值为x的元素，可能还需要确定它的位置
方法：map——我目前做的题不多，我认为用到map的地方都有一个相似的地方：与数组相比，map将数组的值作为索引，而将数组的下标作为map的数值，这样查找某个元素的速度就会很快。
不能简单的用数组来实现，因为测试样例中可能有负值，例如[-1,-1] -
种花问题
模拟；另一个思路，数连续0的位置，然后直接计算之间可以放多少花 - 翻转图像 听我的，直接翻
- 找出井字棋的获胜者 模拟
2020.9.18
2020.9.21
- ✨所有奇数长度子数组的和
思维方式很重要，考虑如何才能组成一个长度为奇数的数组
2020.9.24
- 至少是其他数字两倍的最大数 除法的时候小心除数可能为0，应该转成乘法
- 剑指 Offer 04. 二维数组中的查找 旋转一下就像一棵二叉搜索树
-
第 k 个缺失的正整数
没什么特别的就是让我体会到了c好快，c++写的时间击败4%，c写的击败100%
另一个方法：二分查找 - 按奇偶排序数组 II 内存可以为O(1)
- 解压缩编码列表
- 两数之和 II - 输入有序数组
- 移动零
2020.9.27
2020.9.28
美丽的早晨从刷几道题开始；用java写几道简单题
- 一维数组的动态和
- 有多少小于当前数字的数字
- 去掉最低工资和最高工资后的工资平均值
- 🎈 面试题 17.04. 消失的数字 有一个很巧妙的方法，希望我下次可以想起来
- 方阵中战斗力最弱的 K 行
- 重新排列数组
- 最小绝对差
- 玩筹码
- 缀点成线
2020.9.29
2020.9.30
数组的解题方法
1、暴力再寻求优化
2、二分（或者需要先自行排序，再使用二分）
3、递归
4、（窗口方法）
5、双指针法（快慢指针法，两个指针的前进速度不同，前进的判断条件不同，在一个for循环中完成两个for循环的工作量） 考虑同时从左边开始，同时从右边开始，一左一右开始，都想一遍，不要限制思维
6、摩尔投票法
（随着刷题持续增加）
7、hash或者数组，更换索引和数值的关系
8、贪心方法：思考如何从当前元素出发，构造出符合题目条件的样子，在这个过程中，再考虑把其他的方法（排列组合等）用进来
hash:
