对我来说做好题并总结是很好的方式。。。在看力扣那个题之前先问问题一把一个数组移动n个单位如何实现这是我上个学期学C语言的时候没搞懂的题目看上个学期的课后作业作业6-9题目描述生产线上有 n 个产品编号排列需要循环左移 k 个位置。例如 [1,2,3,4,5] 左移 2 位 → [3,4,5,1,2]。输出移动后的序列。输入格式第一行 n k第二行 n 个整数输出格式移动后的数组输入样例在这里给出一组输入。例如5 2 1 2 3 4 5输出样例在这里给出相应的输出。例如3 4 5 1 2代码如下//其实要移动本质就是我们可以分两部分来看我要右移K个位置就是从末尾拿出k个元素把他放到数组的开头就可以了 #include stdio.h #include stdlib.h int main() { int n,m; scanf(%d %d,n,m); int *arr(int *) malloc(n * sizeof(int)); for (int i 0; i n; i) { scanf(%d,arri); } int km%n;//我一个数组移他的长度位就会变为原样了防止K太大所以要取余 // 从末尾开始打印,就是取后面K个数 for(int i n - k; i n; i){ printf(%d , arr[i]); } // 从开头开始打印,就是取前面n-k个数 for(int i 0; i n - k; i){ printf(%d , arr[i]); } free(arr); return 0; }引用力扣153寻找排序数组中的最小值已知一个长度为n的数组预先按照升序排列经由1到n次旋转后得到输入数组。例如原数组nums [0,1,2,4,5,6,7]在变化后可能得到若旋转4次则可以得到[4,5,6,7,0,1,2]若旋转7次则可以得到[0,1,2,4,5,6,7]注意数组[a[0], a[1], a[2], ..., a[n-1]]旋转一次的结果为数组[a[n-1], a[0], a[1], a[2], ..., a[n-2]]。给你一个元素值互不相同的数组nums它原来是一个升序排列的数组并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。你必须设计一个时间复杂度为O(log n)的算法解决此问题。示例 1输入nums [3,4,5,1,2]输出1解释原数组为 [1,2,3,4,5] 旋转 3 次得到输入数组。示例 2输入nums [4,5,6,7,0,1,2]输出0解释原数组为 [0,1,2,4,5,6,7] 旋转 4 次得到输入数组。示例 3输入nums [11,13,15,17]输出11解释原数组为 [11,13,15,17] 旋转 4 次得到输入数组。提示n nums.length1 n 5000-5000 nums[i] 5000nums中的所有整数互不相同nums原来是一个升序排序的数组并进行了1至n次旋转说实话我在看到这个题目的时候要是没有那句你必须设计一个时间复杂度为 O(log n) 的算法解决此问题我直接优先队列直接秒事实上优先队列其实至少是ON)了所以这个题的数据就算水一点能过但不是最优解那该如何思考呢其实和上面的那个数组右移k个位置是一个道理我把它分为两个部分看其实这个题它的提示很明显O(log n)数组有序等那能想到啥就是说我原数组有序那我右移了多少位那就是说分开的两段是分开有序的中间有一个断点那么我要的最小值不在左边那一段就在右边那一段举个例子//5 2 // 1 2 3 4 5 //移了后是4 5 1 2 3因为题目给的数组是升序的那么我们可以肯定我要的最小值一定是断点位置 //所以结合题目给的那我们可以二分查找就是说我取的中间值mid不一定是断点那我往两边二分查找 //一开始我left0,right4,mid2,我发现nums[mid]nums[right],那我的mid就有可能是断点 //那么我们应该往左边去看有没更小的但我的左右指针相逢的时候就停下说明找到了。代码如下#include bits/stdc.h using namespace std; class Solution { public: int findMin(vectorint nums) { int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] nums[right]) { right mid;//因为mid可能是答案 } else { left mid 1;//而我发现nums[mid]nums[right],很显然right下标的数字已经比mid小那向右边找更小的 } } return nums[right];//这里输出nums[left],nums[right]都一样 } };问题二咋求两个数的最大公约题和最小公倍数又要引用上个学期的作业题6-20题目描述本题要求两个给定正整数的最大公约数和最小公倍数。输入格式输入在一行中给出两个正整数M和N(0M,N1000)。输出格在一行中顺序输出M和N的最大公约数和最小公倍数两数字间以1空格分隔。输入样例在这里给出一组输入。例如511 292输出样例在这里给出相应的输出。例如73 2044递归辗转相除法#include stdio.h int gcd(int a,int b) { //为啥要用辗转相除法 //举个例子6和21 while (b!0) { int tempa%b;//首先temp21%63 ab;//把a的值赋为b,就是a6 btemp;//把b的值赋为temp,就是b3 //继续操作temp6%30 所求为3 } return a; } int lcm(int a,int b) { return a*b/gcd(a,b); } int main() { int m,n; scanf(%d %d,m,n); printf(%d %d,gcd(m,n),lcm(m,n)); return 0; }引用洛谷P1029 [NOIP 2001 普及组] 最大公约数和最小公倍数问题## 题目描述输入两个正整数 x_0, y_0求出满足下列条件的 P, Q 的个数1. P,Q 是正整数。2. 要求 P, Q 以 x_0 为最大公约数以 y_0 为最小公倍数。试求满足条件的所有可能的 P, Q 的个数。## 输入格式一行两个正整数 x_0, y_0。## 输出格式一行一个数表示求出满足条件的 P, Q 的个数。## 输入输出样例 #1### 输入 #13 60### 输出 #14## 说明/提示P,Q 有 4 种1. 3, 60。2. 15, 12。3. 12, 15。4. 60, 3。对于 100% 的数据2 x_0, y_0 10^5。**【题目来源】**NOIP 2001 普及组第二题这个题一看是个规律题就用到上面的的一个规律任何两个数MN有M*Ngcd(M,N)*lcm(M,N),而又因为Mgcd(M*N)*x,Ngcd(M*N)*y,在这里要满足一个条件就是x,y要互质就是说如果不互质那我之间就存在一个可除关系那M,N的最小公倍数就只能更大所以gcd(x,y)一定为1而我们的lcm(M,N)M*N/gcd(M,N)代入我们的Mgcd(M,N)*x,Ngcd(M,N)*y就可得lcm(M,N)gcd(M,N)*x*y也就是x*ylcm(M,N)/gcd(M,N),对于这个题就是要求y_0/x_0的质因数分解的对数所以代码如下#include bits/stdc.h using namespace std; int gcd(int a,int b) { while (b!0) { int tempa%b; ab; btemp; } return a; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int m,n; cinmn; // 根据公式LCM(M,N) * GCD(M,N) M * N // 设 M m * x N m * y // 则 LCM m * x * y → n m * x * y // 所以 x*y n/m //本质上我们的推导公式就是求x*y n/m中的x和y的个数那要是都除不尽那肯定没解 if(n%m!0){ cout0\n; return 0; } int kn/m;//用一个数来替代x*y int count0; for (int i1;ik;i) { if (k%i0) { int resk/i; if (gcd(i,res)1) {//为啥分解出来的x,y一定要是互质其实他们如果不互质 //如果不互质那我之间就存在一个可除关系那M,N的最小公倍数就只能更大 count; } } } coutcount\n; return 0; }问题三求质数问题还是看上个学期的一道作业题6-6题目描述编程求出大于m的最小素数。输入格式直接输入一个正整数输出格式直接输出结果,行末无换行输入样例在这里给出一组输入。例如12输出样例在这里给出相应的输出。例如13代码如下#include stdio.h int isPrime(int n) { // 小于等于1的数一定不是素数 if (n 1) return 0; // 2 是最小的素数也是唯一的偶素数 else if (n 2) return 1; // 大于2的偶数一定不是素数能被2整除 else if (n % 2 0) return 0; // 剩下的都是奇数只需判断从 3 开始 到 sqrt(n) 的奇数能否整除 n // 因为因子都是成对出现的所以只需检查到 i*i n else for (int i 3; i * i n; i 2) { // 如果能被整除说明有因子不是素数 if (n % i 0) return 0; } // 所有可能的因子都试过了都不能整除说明是素数 return 1; } int main() { int m; scanf(%d,m); for (int i2;;i) { if (isPrime(i)im) { printf(%d,i); break; } } return 0; }其实求质数有多种方法①试除法int isPrime(int n) { if (n1) return 0; else if (n2) return 1; else if (n%20) return 0; else for (int i3;i*in;i2) { if (n%i0) return 0; } return 1; }②埃式筛法它是靠啥来筛就是说我们先把2~n间的所有数都视为质数那我们已经知道2是个质数那我们就可以说它的倍数就一定不是质数接着不断遍历一样的方法来比如我已经筛出3是质数那6912.....等都不是质数最后就可得到答案。#define MAX 100005 int prime[MAX]; void sieve(int n){ // 初始化先将所有数标记为 1表示默认是素数 for (int i 2; i n; i) { prime[i] 1; } // 从 2 开始枚举筛掉素数的所有倍数 for (int i 2; i * i n; i) {//为啥是i*in因为比如说我n20那我如果要验证大于4的数的话6912它们一定有个因子在2~n^(1/2)之间所以没必要验了 // 如果当前数 i 是素数 if (prime[i] 1) { // 将 i 的所有倍数标记为非素数 for (int j i * 2; j n; j i) { prime[j] 0; } } } }但是埃式筛会有重复验证的情况就是一个数可能会被验多次比如2的倍数有46等等这些数在后面遍历的啥时候还会被验证所以它的时间复杂度偏慢为O(n log log n)不如欧拉筛。③欧拉筛欧拉筛靠啥只对每个数筛一次我们知道埃式筛慢的原因是一个数被多个因数验证就是比如12会被23等都验证一次那我怎么只筛一次呢其实我们可以用前面的找到的质数去验证后面的数比如说我知道2是质数那我就去那我就去看当前这个数 × 2 是不是合数如果是就标记一次然后立刻停止不让更大的质数再来标记。代码如下#define MAX 1000005 // isPrime[i] 1 表示 i 是素数0 表示合数 int isPrime[MAX]; // 存储所有筛出来的素数 int prime[MAX]; // 记录已经筛出多少个素数 int prime_count; void euler_sieve(int n) { // 初始化先把所有数暂时标记为素数 for (int i 2; i n; i) { isPrime[i] 1; } // 初始时素数个数为 0 prime_count 0; // 遍历 2~n逐个判断与筛除 for (int i 2; i n; i) { //如果i没被筛掉说明是素数那就加入素数数组 if (isPrime[i]) { prime[prime_count] i; } for (int j 0; j prime_count; j) { int p prime[j]; // 当前素数 p // 防止越界i*p 超过 n 就不用筛了 if ((long long)i * p n) { break; } // i*p是合数标记为非素数 isPrime[i * p] 0; // 保证每个合数只被最小质因子筛一次 // 就是说如果p是i的因子那么i后面的素数更大会造成重复直接 break if (i % p 0) { break; } } } }总结一下上个学期的C语言学习其实我明白是为了现在学习其他语言而来的所以多回顾其实可以对基础进一步加深也希望大佬们可以多多评价更加深我学习的回补性。
基础方法从入门到深入（一）
对我来说做好题并总结是很好的方式。。。在看力扣那个题之前先问问题一把一个数组移动n个单位如何实现这是我上个学期学C语言的时候没搞懂的题目看上个学期的课后作业作业6-9题目描述生产线上有 n 个产品编号排列需要循环左移 k 个位置。例如 [1,2,3,4,5] 左移 2 位 → [3,4,5,1,2]。输出移动后的序列。输入格式第一行 n k第二行 n 个整数输出格式移动后的数组输入样例在这里给出一组输入。例如5 2 1 2 3 4 5输出样例在这里给出相应的输出。例如3 4 5 1 2代码如下//其实要移动本质就是我们可以分两部分来看我要右移K个位置就是从末尾拿出k个元素把他放到数组的开头就可以了 #include stdio.h #include stdlib.h int main() { int n,m; scanf(%d %d,n,m); int *arr(int *) malloc(n * sizeof(int)); for (int i 0; i n; i) { scanf(%d,arri); } int km%n;//我一个数组移他的长度位就会变为原样了防止K太大所以要取余 // 从末尾开始打印,就是取后面K个数 for(int i n - k; i n; i){ printf(%d , arr[i]); } // 从开头开始打印,就是取前面n-k个数 for(int i 0; i n - k; i){ printf(%d , arr[i]); } free(arr); return 0; }引用力扣153寻找排序数组中的最小值已知一个长度为n的数组预先按照升序排列经由1到n次旋转后得到输入数组。例如原数组nums [0,1,2,4,5,6,7]在变化后可能得到若旋转4次则可以得到[4,5,6,7,0,1,2]若旋转7次则可以得到[0,1,2,4,5,6,7]注意数组[a[0], a[1], a[2], ..., a[n-1]]旋转一次的结果为数组[a[n-1], a[0], a[1], a[2], ..., a[n-2]]。给你一个元素值互不相同的数组nums它原来是一个升序排列的数组并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。你必须设计一个时间复杂度为O(log n)的算法解决此问题。示例 1输入nums [3,4,5,1,2]输出1解释原数组为 [1,2,3,4,5] 旋转 3 次得到输入数组。示例 2输入nums [4,5,6,7,0,1,2]输出0解释原数组为 [0,1,2,4,5,6,7] 旋转 4 次得到输入数组。示例 3输入nums [11,13,15,17]输出11解释原数组为 [11,13,15,17] 旋转 4 次得到输入数组。提示n nums.length1 n 5000-5000 nums[i] 5000nums中的所有整数互不相同nums原来是一个升序排序的数组并进行了1至n次旋转说实话我在看到这个题目的时候要是没有那句你必须设计一个时间复杂度为 O(log n) 的算法解决此问题我直接优先队列直接秒事实上优先队列其实至少是ON)了所以这个题的数据就算水一点能过但不是最优解那该如何思考呢其实和上面的那个数组右移k个位置是一个道理我把它分为两个部分看其实这个题它的提示很明显O(log n)数组有序等那能想到啥就是说我原数组有序那我右移了多少位那就是说分开的两段是分开有序的中间有一个断点那么我要的最小值不在左边那一段就在右边那一段举个例子//5 2 // 1 2 3 4 5 //移了后是4 5 1 2 3因为题目给的数组是升序的那么我们可以肯定我要的最小值一定是断点位置 //所以结合题目给的那我们可以二分查找就是说我取的中间值mid不一定是断点那我往两边二分查找 //一开始我left0,right4,mid2,我发现nums[mid]nums[right],那我的mid就有可能是断点 //那么我们应该往左边去看有没更小的但我的左右指针相逢的时候就停下说明找到了。代码如下#include bits/stdc.h using namespace std; class Solution { public: int findMin(vectorint nums) { int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] nums[right]) { right mid;//因为mid可能是答案 } else { left mid 1;//而我发现nums[mid]nums[right],很显然right下标的数字已经比mid小那向右边找更小的 } } return nums[right];//这里输出nums[left],nums[right]都一样 } };问题二咋求两个数的最大公约题和最小公倍数又要引用上个学期的作业题6-20题目描述本题要求两个给定正整数的最大公约数和最小公倍数。输入格式输入在一行中给出两个正整数M和N(0M,N1000)。输出格在一行中顺序输出M和N的最大公约数和最小公倍数两数字间以1空格分隔。输入样例在这里给出一组输入。例如511 292输出样例在这里给出相应的输出。例如73 2044递归辗转相除法#include stdio.h int gcd(int a,int b) { //为啥要用辗转相除法 //举个例子6和21 while (b!0) { int tempa%b;//首先temp21%63 ab;//把a的值赋为b,就是a6 btemp;//把b的值赋为temp,就是b3 //继续操作temp6%30 所求为3 } return a; } int lcm(int a,int b) { return a*b/gcd(a,b); } int main() { int m,n; scanf(%d %d,m,n); printf(%d %d,gcd(m,n),lcm(m,n)); return 0; }引用洛谷P1029 [NOIP 2001 普及组] 最大公约数和最小公倍数问题## 题目描述输入两个正整数 x_0, y_0求出满足下列条件的 P, Q 的个数1. P,Q 是正整数。2. 要求 P, Q 以 x_0 为最大公约数以 y_0 为最小公倍数。试求满足条件的所有可能的 P, Q 的个数。## 输入格式一行两个正整数 x_0, y_0。## 输出格式一行一个数表示求出满足条件的 P, Q 的个数。## 输入输出样例 #1### 输入 #13 60### 输出 #14## 说明/提示P,Q 有 4 种1. 3, 60。2. 15, 12。3. 12, 15。4. 60, 3。对于 100% 的数据2 x_0, y_0 10^5。**【题目来源】**NOIP 2001 普及组第二题这个题一看是个规律题就用到上面的的一个规律任何两个数MN有M*Ngcd(M,N)*lcm(M,N),而又因为Mgcd(M*N)*x,Ngcd(M*N)*y,在这里要满足一个条件就是x,y要互质就是说如果不互质那我之间就存在一个可除关系那M,N的最小公倍数就只能更大所以gcd(x,y)一定为1而我们的lcm(M,N)M*N/gcd(M,N)代入我们的Mgcd(M,N)*x,Ngcd(M,N)*y就可得lcm(M,N)gcd(M,N)*x*y也就是x*ylcm(M,N)/gcd(M,N),对于这个题就是要求y_0/x_0的质因数分解的对数所以代码如下#include bits/stdc.h using namespace std; int gcd(int a,int b) { while (b!0) { int tempa%b; ab; btemp; } return a; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int m,n; cinmn; // 根据公式LCM(M,N) * GCD(M,N) M * N // 设 M m * x N m * y // 则 LCM m * x * y → n m * x * y // 所以 x*y n/m //本质上我们的推导公式就是求x*y n/m中的x和y的个数那要是都除不尽那肯定没解 if(n%m!0){ cout0\n; return 0; } int kn/m;//用一个数来替代x*y int count0; for (int i1;ik;i) { if (k%i0) { int resk/i; if (gcd(i,res)1) {//为啥分解出来的x,y一定要是互质其实他们如果不互质 //如果不互质那我之间就存在一个可除关系那M,N的最小公倍数就只能更大 count; } } } coutcount\n; return 0; }问题三求质数问题还是看上个学期的一道作业题6-6题目描述编程求出大于m的最小素数。输入格式直接输入一个正整数输出格式直接输出结果,行末无换行输入样例在这里给出一组输入。例如12输出样例在这里给出相应的输出。例如13代码如下#include stdio.h int isPrime(int n) { // 小于等于1的数一定不是素数 if (n 1) return 0; // 2 是最小的素数也是唯一的偶素数 else if (n 2) return 1; // 大于2的偶数一定不是素数能被2整除 else if (n % 2 0) return 0; // 剩下的都是奇数只需判断从 3 开始 到 sqrt(n) 的奇数能否整除 n // 因为因子都是成对出现的所以只需检查到 i*i n else for (int i 3; i * i n; i 2) { // 如果能被整除说明有因子不是素数 if (n % i 0) return 0; } // 所有可能的因子都试过了都不能整除说明是素数 return 1; } int main() { int m; scanf(%d,m); for (int i2;;i) { if (isPrime(i)im) { printf(%d,i); break; } } return 0; }其实求质数有多种方法①试除法int isPrime(int n) { if (n1) return 0; else if (n2) return 1; else if (n%20) return 0; else for (int i3;i*in;i2) { if (n%i0) return 0; } return 1; }②埃式筛法它是靠啥来筛就是说我们先把2~n间的所有数都视为质数那我们已经知道2是个质数那我们就可以说它的倍数就一定不是质数接着不断遍历一样的方法来比如我已经筛出3是质数那6912.....等都不是质数最后就可得到答案。#define MAX 100005 int prime[MAX]; void sieve(int n){ // 初始化先将所有数标记为 1表示默认是素数 for (int i 2; i n; i) { prime[i] 1; } // 从 2 开始枚举筛掉素数的所有倍数 for (int i 2; i * i n; i) {//为啥是i*in因为比如说我n20那我如果要验证大于4的数的话6912它们一定有个因子在2~n^(1/2)之间所以没必要验了 // 如果当前数 i 是素数 if (prime[i] 1) { // 将 i 的所有倍数标记为非素数 for (int j i * 2; j n; j i) { prime[j] 0; } } } }但是埃式筛会有重复验证的情况就是一个数可能会被验多次比如2的倍数有46等等这些数在后面遍历的啥时候还会被验证所以它的时间复杂度偏慢为O(n log log n)不如欧拉筛。③欧拉筛欧拉筛靠啥只对每个数筛一次我们知道埃式筛慢的原因是一个数被多个因数验证就是比如12会被23等都验证一次那我怎么只筛一次呢其实我们可以用前面的找到的质数去验证后面的数比如说我知道2是质数那我就去那我就去看当前这个数 × 2 是不是合数如果是就标记一次然后立刻停止不让更大的质数再来标记。代码如下#define MAX 1000005 // isPrime[i] 1 表示 i 是素数0 表示合数 int isPrime[MAX]; // 存储所有筛出来的素数 int prime[MAX]; // 记录已经筛出多少个素数 int prime_count; void euler_sieve(int n) { // 初始化先把所有数暂时标记为素数 for (int i 2; i n; i) { isPrime[i] 1; } // 初始时素数个数为 0 prime_count 0; // 遍历 2~n逐个判断与筛除 for (int i 2; i n; i) { //如果i没被筛掉说明是素数那就加入素数数组 if (isPrime[i]) { prime[prime_count] i; } for (int j 0; j prime_count; j) { int p prime[j]; // 当前素数 p // 防止越界i*p 超过 n 就不用筛了 if ((long long)i * p n) { break; } // i*p是合数标记为非素数 isPrime[i * p] 0; // 保证每个合数只被最小质因子筛一次 // 就是说如果p是i的因子那么i后面的素数更大会造成重复直接 break if (i % p 0) { break; } } } }总结一下上个学期的C语言学习其实我明白是为了现在学习其他语言而来的所以多回顾其实可以对基础进一步加深也希望大佬们可以多多评价更加深我学习的回补性。
