基础方法从入门到深入（一）

对我来说，做好题，并总结是很好的方式。。。

在看力扣那个题之前先问：

问题一：

把一个数组移动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",arr+i); } int k=m%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.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• nums中的所有整数互不相同
• nums原来是一个升序排序的数组，并进行了1至n次旋转

说实话，我在看到这个题目的时候，要是没有那句你必须设计一个时间复杂度为 O(log n) 的算法解决此问题，我直接优先队列直接秒，事实上，优先队列其实至少是O（N)了，所以这个题的数据就算水一点，能过，但不是最优解，那该如何思考呢？其实和上面的那个数组右移k个位置是一个道理，我把它分为两个部分看，其实这个题它的提示很明显，O(log n)，数组有序等，那能想到啥？就是说我原数组有序，那我右移了多少位，那就是说分开的两段是分开有序的，中间有一个断点，那么我要的最小值不在左边那一段就在右边那一段，举个例子：

//5 2 // 1 2 3 4 5 //移了后是4 5 1 2 3，因为题目给的数组是升序的，那么我们可以肯定我要的最小值一定是断点位置 //所以结合题目给的，那我们可以二分查找，就是说我取的中间值mid不一定是断点，那我往两边二分查找 //一开始我left=0,right=4,mid=2,我发现nums[mid]<nums[right],那我的mid就有可能是断点 //那么我们应该往左边去看有没更小的，但我的左右指针相逢的时候，就停下说明找到了。

代码如下：

#include <bits/stdc++.h> using namespace std; class Solution { public: int findMin(vector<int>& 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(0<M,N<=1000)。

输出格

在一行中顺序输出M和N的最大公约数和最小公倍数，两数字间以1空格分隔。

输入样例

在这里给出一组输入。例如：

511 292

输出样例

在这里给出相应的输出。例如：

73 2044

递归辗转相除法：

#include <stdio.h> int gcd(int a,int b) { //为啥要用辗转相除法？ //举个例子：6和21， while (b!=0) { int temp=a%b;//首先temp=21%6=3 a=b;//把a的值赋为b,就是a==6 b=temp;//把b的值赋为temp,就是b==3 //继续操作，temp=6%3=0 ==> 所求为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

### 输入 #1
3 60

### 输出 #1
4

## 说明/提示

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 普及组第二题

这个题，一看是个规律题，就用到上面的的一个规律：任何两个数M，N，有M*N=gcd(M,N)*lcm(M,N),而又因为M=gcd(M*N)*x,N=gcd(M*N)*y,在这里要满足一个条件就是x,y要互质，就是说如果不互质那我之间就存在一个可除关系，那M,N的最小公倍数就只能更大，所以gcd(x,y)一定为1，而我们的lcm(M,N)=M*N/gcd(M,N)==>代入我们的M=gcd(M,N)*x,N=gcd(M,N)*y

就可得lcm(M,N)=gcd(M,N)*x*y也就是x*y=lcm(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 temp=a%b; a=b; b=temp; } return a; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int m,n; cin>>m>>n; // 根据公式：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){ cout<<"0"<<"\n"; return 0; } int k=n/m;//用一个数来替代x*y int count=0; for (int i=1;i<=k;i++) { if (k%i==0) { int res=k/i; if (gcd(i,res)==1) {//为啥分解出来的x,y一定要是互质，其实他们如果不互质 //如果不互质那我之间就存在一个可除关系，那M,N的最小公倍数就只能更大 count++; } } } cout<<count<<"\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 i=2;;i++) { if (isPrime(i)&&i>m) { printf("%d",i); break; } } return 0; }

其实求质数有多种方法：

①试除法：

int isPrime(int n) { if (n<=1) return 0; else if (n==2) return 1; else if (n%2==0) return 0; else for (int i=3;i*i<=n;i+=2) { if (n%i==0) return 0; } return 1; }

②埃式筛法：

它是靠啥来筛？就是说我们先把2~n间的所有数都视为质数，那我们已经知道2是个质数，那我们就可以说它的倍数就一定不是质数，接着不断遍历，一样的方法来比如我已经筛出3是质数，那6，9，12.....等都不是质数，最后就可得到答案。

#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*i<=n，因为比如说我n=20，那我如果要验证大于4的数的话，6，9，12它们一定有个因子在2~n^(1/2)之间，所以没必要验了 // 如果当前数 i 是素数 if (prime[i] == 1) { // 将 i 的所有倍数标记为非素数 for (int j = i * 2; j <= n; j += i) { prime[j] = 0; } } } }

但是埃式筛会有重复验证的情况，就是一个数可能会被验多次，比如2的倍数有4，6等等，这些数在后面遍历的啥时候还会被验证，所以它的时间复杂度偏慢，为O(n log log n)，不如欧拉筛。

③欧拉筛：

欧拉筛靠啥只对每个数筛一次？我们知道埃式筛慢的原因是一个数被多个因数验证，就是比如12，会被2，3等都验证一次，那我怎么只筛一次呢？其实我们可以用前面的找到的质数去验证后面的数，比如说我知道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语言学习其实我明白是为了现在学习其他语言而来的，所以多回顾其实可以对基础进一步加深，也希望大佬们可以多多评价，更加深我学习的回补性。