class Solution {
public:
int fib(int n) {
int a = 0 , b = 1, c;
for(int i = 1; i <= n;i++)
{
c = a + b;
b = a;
a = c;
}
return a;
}
};
活动打卡代码
LeetCode 509. 斐波那契数
新鲜事
原文
做算法题的第一个要突破的问题就在于直觉和代码之间的距离问题。
我不由得想到华罗庚先生讲：
数缺形时少直观，形少数时难入微，数形结合百般好，隔离分家万事休。
算法同样如此，算法本就是数学的一部分，加之是离散的，以机器语言表达的。
代码本身就是代数的表达，对什么的表达呢？对状态空间的表达。
我们通过代数讲状态几何空间进行表达。
为什么会存在直觉和代码之间的距离问题？
因为数缺形时少直观,答案华罗庚先生已经告诉我们了。
如何解决？回答已经显然，再做一个总结：将每一句代码对应到符合逻辑的状态空间的几何意义之上。将状态空间几何化，实例化。
具体如何应用呢？
我也引流了许多我校的学生来到acwing学习，往往都是从基础课的第一道题目
quick sort 快速排序开始的。
```
//quick sort 的模板贴过来
void quick_sort(int a[],int l,int r)
{
if(l >= r) return;
int x = a[l + r >> 1];
int i = l - 1, j = r + 1;
while(i < j)
{
do(i++); while(a[i] < x);
do(j--);while(a[j] > x);
if(i < j) swap(a[i],a[j]);
}
quick_sort(a,l,j);
quick_sort(a,j+1,r);
}
```
一步一步来看
第一步是递归边界，最后再看，是指分治的边界；
第二步是选定主元；
第三步是确定双指针；
第四步是双指针移动，每次当指向的元素不满足条件时停下
第五步是如果双指针没有相遇，两个元素交换。
第六步是对整个数组进行分治。
如果在纸上画出对应的图就会发现：
最后形成的状态就在于 双指针相遇的位置分割开，左侧的所有元素都小于等于主元，而右侧的所有元素都大于等于主元。
这个想法和结果都是极其自然的。
进而分治下去最后形成了有序的序列也就很自然了。分治的意义也就在这里
不会有丝毫的迷惑性。
可以轻而易举的回答初学者的所有问题 ：
常见的有为什么不加等号？
加了等号就不能保证几何意义要求的满足了。
如果等于没有停下 等待交换 而后面的元素全部是小于这个元素的就无法分治了
还有什么为什么分治的边界是 a l j 和 a j + 1 r
这些问题都是很自然的。
这是我多年学习算法的感悟，当运用到dp和图论等问题的时候效果更为明显
分享给大家共勉。
新鲜事
原文
acwing推动了整个计算机相关就业升学的内卷啊
如果acwing某天真的家喻户晓人人注册刷题。。可能必须要进阶课滚瓜烂熟 + codeforces每次div1都补题才能卷过别人了= =
活动打卡代码
AcWing 532. 数组中的 k-diff 数对
//method 1
class Solution {
public:
int findPairs(vector<int>& nums, int k) {
int res = 0;
sort(nums.begin(),nums.end());
int n = nums.size();
for(int i = 0, j = 0; i < n;i++)
{
while(i > 0 && i < n - 1 && nums[i + 1] == nums[i]) i++;
while(j < i && nums[i] - nums[j] > k) j++;
if(j < i && nums[i] - nums[j] == k) res++;
}
return res;
}
};\
//method 2
class Solution {
public:
unordered_map<int,int> less;
unordered_map<int,int> greater;
int findPairs(vector<int>& nums, int k) {
int n = nums.size();
int res = 0;
for(int i = 0; i < n;i++)
{
if(less.count(nums[i] - k))
{
if(!greater.count(nums[i])) greater[nums[i]]++;
}
if(less.count(nums[i] + k))
{
if(!greater.count(nums[i] + k)) greater[nums[i]+k]++;
}
if(!less.count(nums[i])) less[nums[i]]++;
}
res = greater.size();
return res;
}
};
活动打卡代码
AcWing 756. 蛇形矩阵
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n,k;
int g[N][N];
bool st[N][N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k;
int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};
int a = 0, b = 0, m = 0;
for(int i = 0; i < n * k; i++ )
{
g[a][b] = i + 1;
st[a][b] = true;
int ta = a, tb = b;
a = a + dx[m], b = b + dy[m];
if(a < 0 || a > n - 1 || b < 0 || b > k - 1 || st[a][b])
{
m = (m + 1) % 4;
a = ta + dx[m], b = tb + dy[m];
}
}
for(int i = 0; i < n;i++)
{
for(int j = 0; j < k;j++)
{
cout << g[i][j] << " " ;
}
cout << endl;
}
return 0;
}
分享
排序算法的稳定性问题
排序算法的稳定性
九大排序
计数排序 基数排序 桶排序
选择排序 插入排序 冒泡排序
堆排序 归并排序 快速排序
什么是排序的稳定性
如果元素大小相同
排序后的相对位置不变
不稳定
堆排序 快速排序 选择排序 不是稳定的
稳定
基数排序 冒泡排序 插入排序 归并排序 计数排序 桶排序
选择排序
在每次将最小的元素拿到最前面和未排序的序列的第一个元素进行交换的时候发生了对原序列的破坏 失去了稳定性
快速排序
Swap的时候有可能让两个本来相等的元素交换位置 破坏了原序列的稳定性
堆排序
比如：3 27 36 27，
如果堆顶3先输出，则，第三层的27（最后一个27）跑到堆顶，然后堆稳定，继续输出堆顶，是刚才那个27，这样说明后面的27先于第二个位置的27输出，不稳定。
基数排序 计数排序 桶排序
基数 进入每个桶的顺序和一开始相对位置相同
计数 下标映射偏移和相对位置相同
桶 和基数同理
冒泡排序 基于比较换到一侧 相等的话不会交换位置 保证相对的有序
插入排序 因为如果两个元素相等不会发生交换 先插入的放在前面 保证相对位置不变
归并排序 相等则不发生交换 保证相对位置不变
活动打卡代码
AcWing 92. 递归实现指数型枚举
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> chosen;
void calc(int x)
{
if(x == n + 1)
{
for(int i = 0; i < chosen.size();i++) cout << chosen[i] << ' ';
cout << endl;
return;
}
calc(x+1); // not choose
chosen.push_back(x);
calc(x+1);
chosen.pop_back();
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
calc(1);
return 0;
}
活动打卡代码
AcWing 154. 滑动窗口
#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
int q[N],a[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n,k;
cin >> n >> k;
for(int i = 0; i < n; i++) cin >> a[i];
int hh = 0, tt = -1;
for(int i = 0; i < n;i++)
{
if(hh <= tt && q[hh] < i - k + 1) hh++;
while(hh <= tt && a[q[tt]] >= a[i]) tt--;
q[++ tt] = i;
if(i >= k - 1) cout << a[q[hh]] << ' ';
}
cout << endl;
hh = 0, tt = -1;
for(int i = 0; i < n;i++)
{
if(hh <= tt && q[hh] < i - k + 1) hh++;
while(hh <= tt && a[q[tt]] <= a[i]) tt--;
q[++ tt] = i;
if(i >= k - 1) cout << a[q[hh]] << ' ';
}
return 0;
}
活动打卡代码
AcWing 154. 滑动窗口
#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
int q[N],a[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n,k;
cin >> n >> k;
for(int i = 0; i < n; i++) cin >> a[i];
int hh = 0, tt = -1;
for(int i = 0; i < n;i++)
{
if(hh <= tt && q[hh] < i - k + 1) hh++;
while(hh <= tt && a[q[tt]] >= a[i]) tt--;
q[++ tt] = i;
if(i >= k - 1) cout << a[q[hh]] << ' ';
}
cout << endl;
hh = 0, tt = -1;
for(int i = 0; i < n;i++)
{
if(hh <= tt && q[hh] < i - k + 1) hh++;
while(hh <= tt && a[q[tt]] <= a[i]) tt--;
q[++ tt] = i;
if(i >= k - 1) cout << a[q[hh]] << ' ';
}
return 0;
}
活动打卡代码
AcWing 830. 单调栈
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int stk[N],tt;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n; cin >> n;
for(int i = 1; i <= n;i++)
{
int x;
cin >> x;
while(tt && stk[tt] >= x) tt--;
if(tt) cout << stk[tt] << ' ';
else cout << "-1" << ' ';
stk[++tt] = x;
}
return 0;
}
