algorithm

本文最后更新于：1 年前

  1. [[#1.1递归|1.1递归]]
  2. [[#2.1 两数之和|2.1 两数之和]]
  3. [[#2.2 合并两个有序数组|2.2 合并两个有序数组]]
  4. [[#2.3 移动零|2.3 移动零]]
  5. [[#2.4 找到所有数组中消失的数字|2.4 找到所有数组中消失的数字]]
  6. [[#2.1 枚举|2.1 枚举]]
    1. [[#2.1 枚举#1. abc|1. abc]]
    2. [[#2.1 枚举#2. 反序数|2. 反序数]]
    3. [[#2.1 枚举#3. 对称平方数|3. 对称平方数]]
    4. [[#2.1 枚举#4. 与 7 无关的数|4. 与 7 无关的数]]
    5. [[#2.1 枚举#5. 百鸡问题|5. 百鸡问题]]
    6. [[#2.1 枚举#6. Old Bill|6. Old Bill]]
  7. [[#2.2 模拟|2.2 模拟]]
    1. [[#2.2 模拟#1. 图形排版|1. 图形排版]]
      1. [[#1. 图形排版#1. 输出梯形|1. 输出梯形]]
      2. [[#1. 图形排版#2. 叠筐|2. 叠筐]]
    2. [[#2.2 模拟#2. 日期|2. 日期]]
      1. [[#2. 日期#1. 今天是第几天|1. 今天是第几天]]
      2. [[#2. 日期#2. 打印日期|2. 打印日期]]
      3. [[#2. 日期#3. 日期累加|3. 日期累加]]
        1. [[#3. 日期累加#套路|套路]]
        2. [[#3. 日期累加#技巧|技巧]]
        3. [[#3. 日期累加#代码|代码]]
    3. [[#2.2 模拟#3. 其他|3. 其他]]
      1. [[#3. 其他#1. 剩余的树|1. 剩余的树]]
      2. [[#3. 其他#2. 手机键盘|2. 手机键盘]]
      3. [[#3. 其他#3. xxx_定律|3. xxx_定律]]
  8. [[#3.1 排序|3.1 排序]]
    1. [[#3.1 排序#1. 排序|1. 排序]]
      1. [[#1. 排序#大部分排序方法|大部分排序方法]]
    2. [[#3.1 排序#2. 成绩排序|2. 成绩排序]]
    3. [[#3.1 排序#3. 成绩排序 2|3. 成绩排序 2]]
  9. [[#3.2 查找|3.2 查找]]
    1. [[#3.2 查找#1. 找 x|1. 找 x]]
    2. [[#3.2 查找#2. 查找|2. 查找]]
    3. [[#3.2 查找#3. extrenum_index|3. extrenum_index]]
    4. [[#3.2 查找#4. 找位置|4. 找位置]]
  10. [[#4.1 字符串处理|4.1 字符串处理]]
    1. [[#4.1 字符串处理#1. 特殊乘法|1. 特殊乘法]]
    2. [[#4.1 字符串处理#2. 密码翻译|2. 密码翻译]]
    3. [[#4.1 字符串处理#3. 简单密码|3. 简单密码]]
    4. [[#4.1 字符串处理#4. 统计字符|4. 统计字符]]
    5. [[#4.1 字符串处理#5. 字母统计|5. 字母统计]]
  11. [[#4.2 字符串匹配|4.2 字符串匹配]]
  12. [[#5.1 向量|5.1 向量]]
    1. [[#5.1 向量#完数与盈数|完数与盈数]]
  13. [[#5.2 队列|5.2 队列]]
  14. [[#5.3 栈|5.3 栈]]
  15. [[#简单题|简单题]]
    1. [[#简单题#1.数组中重复的数字|1.数组中重复的数字]]
    2. [[#简单题#2.替换空格|2.替换空格]]
    3. [[#简单题#3.从尾到头打印链表|3.从尾到头打印链表]]
    4. [[#简单题#4.用两个栈实现队列|4.用两个栈实现队列]]

1. 基础知识

1.1递归

***自顶向下递归
自底向上迭代

问题特点

  1. 一个问题的解可以分解为几个子问题的解。
  2. 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样。
  3. 存在基线终止条件。

爬楼梯问题：
image.png|200

解法 1：纯递归

1
2
3
4
5
6
7
8
class Solution {
private Map<Integer , Integer> storeMap = new HashMap<>();
public int climbStairs(int n) {
if(n == 1) return 1;
if(n == 2) return 2;
else{
return climbStairs(n-1)+climbStairs(n-2);

解法 2：递归并采用 HashMap 存储已求值

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
private Map<Integer , Integer> storeMap = new HashMap<>();
public int climbStairs(int n) {
if(n == 1) return 1;
if(n == 2) return 2;
if(null != storeMap.get(n))
return storeMap.get(n);
else{
int result = climbStairs(n-1)+climbStairs(n-2);
storeMap.put(n,result);
return result;

解法 3：迭代自底向上循环累加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int climbStairs(int n) {
if(n == 1) return 1;
if(n == 2) return 2;
int result = 0;
int pre = 2;
int prePre = 1;
for(inti=3;i<=n;++i){
result = pre + prePre;
prePre = pre;
pre = result;
}
return result;
}


总结：

对于多次重复出现的值，可以通过 HashMap 存储，后续先扫描 HashMap 是否存在再做行动。

2. LeetCode

2.1 两数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.HashMap;  
  
class Solution {  
public int[] twoSum(int[] nums, int target) {  
HashMap<Integer, Integer> storeNums = new HashMap<Integer, Integer>(nums.length);  
int[] results = new int[2];  
for (int i = 0; i < nums.length; i++) {  
int residue = target - nums[i];  
Integer index = storeNums.get(residue);  
if (index != null) {  
results[0] = index;  
results[1] = i;  
break;  
} else {  
storeNums.put(nums[i], i);  
}  
}  
return results;  
}  
  
};  
//runtime:1 ms  
//memory:42.6 MB

2.2 合并两个有序数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//leetcode submit region begin(Prohibit modification and deletion)  
#include<bits/stdc++.h>  
using namespace std;  
class Solution {  
public:  
// 方法1（直插排序法）  
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {  
auto iter1 = nums1.begin()+m;  
auto iter2 = nums1.end();  
nums1.erase(iter1,iter2);  
for (int i = 0; i < n; ++i) {  
nums1.push_back(nums2[i]);  
}  
// nums1.erase(iter1,iter2);  
// nums1.insert(nums1.end(),nums2.begin(),nums2.end());  
sort(nums1.begin(), nums1.end());  
}  
//方法2（前向双指针法）  
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {  
int l = m+n,j=0,index1 = 0,index2 = 0;  
vector<int> temp(l);  
for (int i = 0; i < l; ++i) {  
if (index1>=m){  
temp[i]=nums2[index2++];  
}  
else if(index2>=n){  
temp[i]=nums1[index1++];  
}  
else if(nums1[index1]<nums2[index2]){  
temp[i]=nums1[index1++];  
}  
else {  
temp[i]=nums2[index2++];  
}  
}  
for(int item:temp){  
nums1[j++]=item;  
}  
}  
//方法3（反向双指针）  
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {  
int l = m+n,index1 = m-1,index2 = n-1;  
for (int i = l-1; i >= 0; i--) {  
if (index1<0){  
nums1[i]=nums2[index2--];  
}  
else if(index2<0){  
// nums1[i]=nums1[index1--];  
break;  
}  
else if(nums1[index1]>=nums2[index2]){  
nums1[i]=nums1[index1--];  
}  
else {  
nums1[i]=nums2[index2--];  
}  
}  
}  
};  
//leetcode submit region end(Prohibit modification and deletion)

2.3 移动零

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//双指针
#include<vector>  
  
using namespace std;  
class Solution {  
public:  
void moveZeroes(vector<int>& nums) {  
if(!nums.size()){  
return;  
}  
int j = 0;  
for(int item:nums){  
if (item!=0)  
nums[j++]=item;  
}  
while (j<nums.size()){  
nums[j++]=0;  
}  
}  
};

2.4 找到所有数组中消失的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//数组 哈希表
#include<vector>  
using namespace std;
class Solution {  
public:  
vector<int> findDisappearedNumbers(vector<int>& nums) {  
vector<int> disnums;  
// for(int item:nums){  
// item = item>0 ? item : -item;  
// nums[item-1] = nums[item-1]>0 ? nums[item-1] : -nums[item-1];  
// nums[item-1]=-nums[item-1];  
// }  
// for(int i=0;i<nums.size();i++){  
// if (nums[i]>0)  
// disnums.push_back(i+1);  
// }  
int n = nums.size();  
for(int item:nums){  
int x = (item-1)%n;  
nums[x]+=n;  
}  
for(int i=0;i<n;i++){  
if (nums[i]<=n)  
disnums.push_back(i+1);  
}  
return disnums;  
}  
};

王道机试指南

第二章暴力求解

2.1 枚举

1. abc

三重循环暴力求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
using namespace std;
int main() {
    int a, b, c;
    for (a = 0; a <= 9; a++) {
        for (b = 0; b <= 9; b++) {
            for (c = 0; c <= 9; c++) {
                if ((a * 100 + b * 10 + c) + (b * 100 + c * 10 + c) == 532) {
                    printf("%d %d %d\n", a, b, c);
                }
            }
        }
    }
}

2. 反序数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>

using namespace std;

  

int main() {

    for (int i = 1000; 9 * i <= 9999; i++) {

        int k = 9 * i;

        if (k / 1000 == i % 10 && k % 1000 / 100 == i % 100 / 10 &&

                k % 100 / 10 == i % 1000 / 100 &&

                k % 10 == i / 1000) {

            printf("%d\n", i);

        }

    }

}

3. 对称平方数

判断一个数是否为对称数核心:
while (j) {
sum = sum * 10 + j % 10;
j /= 10;
}
j 为对称数则 sum 等于 j*j 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>

using namespace std;

  

int main() {

    for(int i = 0;i <= 256 ; i++) {

        int j = i * i, sum = 0;

        while(j) {

            sum = sum * 10 + j % 10;

            j /= 10;

        }

        if(sum == i * i) {

            cout << i << endl;

        }

    }

    return 0;

}

4. 与 7 无关的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>

using namespace std;

  

int main() {

    int b, c, x, sum;

    cin >> x;

    for (int i = 0; i <= x; ++i) {

        b = i % 10;

        c = (i / 10) % 10;

        if (i % 7 != 0 && b != 7 && c != 7) {

            sum = sum + i * i;

        }

    }

    cout << sum << endl;

}

5. 百鸡问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>

using namespace std;

  

int main() {

    int n;

    cin >> n;

    for (int x = 0; x <= 100; ++x) {

        for (int y = 0; y <= 100; ++y) {

            for (int z = 0; z <= 100; ++z) {

                if (x + y + z == 100 && ((5 * x + 3 * y + z / 3.0) <= n)) {

                    printf("x=%d,y=%d,z=%d\n", x, y, z);

                }

            }

        }

    }

}

6. Old Bill

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>  
#include "title.h"  
  
using namespace std;  
  
  
int main() {  
int n, x, y, z;  
vector<int> buff;  
cin >> n;  
cin >> x >> y >> z;  
for (int i = 1; i < 100000.0 / n; ++i) {  
int sum = i * n;  
if (sum < 10000)  
continue;  
int a = sum % 10;  
int z1 = sum / 10 % 10;  
int y1 = sum / 100 % 10;  
int x1 = sum / 1000 % 10;  
int b = sum / 10000;  
if (x == x1 && y == y1 && z == z1) {  
buff.push_back(b);  
buff.push_back(a);  
buff.push_back(i);  
}  
}  
if (buff.empty())  
printf("0");  
else {  
printf("%d %d %d\n", buff[buff.size() - 3], buff[buff.size() - 2], buff[buff.size() - 1]);  
}  
}

方法 2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <cstdio>
using namespace std;
int main(){
    int n, x, y, z;//n火鸡数、xyz原价格中间三位
    while(~scanf("%d", &n)){
        scanf("%d %d %d", &x, &y, &z);
        int tot, f = 0;//tot原价格、f标记是否存在能够整除火鸡数n的价格
        //这里选择从9枚举到1是为了第一次输出就是最高价格
        for(int a = 9; a >= 1; a--){//a控制原价格的万位[1,9]
            for(int b = 9; b >= 0; b--){//b控制原价格的个位[0,9]
                tot = a * 10000 + x * 1000 + y * 100 + z * 10 + b;
                if(tot % n == 0){//如果原价格tot能够整除火鸡数n
                    f = 1;//则将整除标记置1
                    printf("%d %d %d\n", a, b, tot / n);
                    break;
                }          
            }
            if(f) break;//如果已经整除，则跳出枚举
        }
        if(!f) printf("0\n");//如果没有可以整除的价格，则打印0
    }
    return 0;
}

2.2 模拟

1. 图形排版

1. 输出梯形

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>  
#include "title.h"  
  
using namespace std;  
  
  
int main() {  
int h;  
while (scanf("%d", &h) != EOF) //高度h  
{  
int b = h + 2 * (h - 1), t = h; //下底边长，上底边长  
for (int i = 1; i <= h; i++) {  
for (int j = 1; j <= b; j++) {  
if (j > b - t - 2 * (i - 1))  
printf("*");  
else  
printf(" ");  
}  
printf("\n");  
}  
}  
return 0;  
}

2. 叠筐

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
using namespace std;
int main(){
    int n;
    char a,b;
    char S[80][80];
    while(cin>>n>>a>>b){
        int mid=n/2;
        bool flag=true;
        S[mid][mid]=a;
        for(int i=1;i<=mid;i++){
                if(flag){
                    for(int j=0;j<2*i+1;j++){
                    S[mid-i][mid-i+j]=b;
                    S[mid+i][mid-i+j]=b;
                    S[mid-i+j][mid-i]=b;
                    S[mid-i+j][mid+i]=b;
                    flag=false;
                    }
                }
                else{
                    for(int j=0;j<2*i+1;j++){
                    S[mid-i][mid-i+j]=a;
                    S[mid+i][mid-i+j]=a;
                    S[mid-i+j][mid-i]=a;
                    S[mid-i+j][mid+i]=a;
                    flag=true;
                    }
                }
        }
        S[0][0]=S[0][n-1]=S[n-1][0]=S[n-1][n-1]=' ';
        for(int i=0;i<n;i++){
                for(int j=0;j<n;j++)
                    cout<<S[i][j];
                cout<<endl;
            }
 
            cout<<endl;
    }
    return 0;
}

2. 日期

1. 今天是第几天

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//

// Created by alleyf on 2023/6/23.

//

#include<bits/stdc++.h>

using namespace std;

bool isLeap(int year) {

    return (year % 4 == 0 && year % 100 != 0) || year % 400 == 0;

}

int main() {

  

    int year, month, day;

    while (cin >> year >> month >> day) {

        unordered_map<int, int> monthDay{

            {1, 31}, {2, 28}, {3, 31}, {4, 30}, {5, 31}, {6, 30}, {7, 31}, {8, 31}, {9, 30}, {10, 31}, {11, 30}, {12, 31}

        };

        int sum = 0;

        if (isLeap(year)) {

            monthDay[2] = 29;

        }

        for (int i = 1; i < month; i++) {

            sum += monthDay[i];

        }

        sum += day;

        cout << sum << endl;

    }

}

2. 打印日期

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//  
// Created by alleyf on 2023/6/23.  
//  
#include<bits/stdc++.h>  
using namespace std;  
bool isLeap(int year){  
return (year%4==0&&year%100!=0)||year%400==0;  
}  
int main(){  
  
int year,allday;  
string month,day;  
while(cin>>year>>allday){  
unordered_map<int,int> monthDay{  
{1,31},{2,59},{3,90},{4,120},{5,151},{6,181},{7,212},{8,243},{9,273},{10,304},{11,334},{12,365}  
};  
if(isLeap(year)){  
for(int i=2;i<=12;i++){  
monthDay[i]+=1;  
}  
}  
for(int i=1;i<=12;i++){  
if(monthDay[i]>=allday){  
month = i>=10 ? to_string(i): ('0'+to_string(i));  
if(i==1){  
day = allday>=10 ? to_string(allday): ('0'+to_string(allday));  
}else {  
allday = allday - monthDay[i - 1];  
day = allday>=10 ? to_string(allday): ('0'+to_string(allday));  
}  
break;  
};  
}  
cout<<year<<'-'<<month<<'-'<<day<<endl;  
}  
}

3. 日期累加

套路

以前大一的时候面对这个题，就是单纯按月份纯算，算的可谓是焦头烂额。现在学习了新的方法：

  1. 计算是当年的第几天
  2. 这个数值 sum 加上需要累加的天数
  3. 计算进位的多少年，确定年份
  4. 根据剩下的第几天反解出这是几月几日
  5. 输出
技巧

用到的技巧包括打表、巧用 bool。
提前写出来每个月有多少天、每年有多少天。
还有判断是否闰年函数，用它能够得到 bool 值，0 和 1 可以分别对应于平年和闰年，所以上面的可以构造成二维数组。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;

bool isLeap(int year){
    if(year%400==0) return true;
    else if(year%4==0&&year%100!=0) return true;
    return false;
}

int main(){
    int days[2][12]={
        {31,28,31,30,31,30,31,31,30,31,30,31},
        {31,29,31,30,31,30,31,31,30,31,30,31},
    };
    int n;
    scanf("%d",&n);
    for(int current = 0; current<n; current++){
        int year,month,date,plus;
        scanf("%d %d %d %d",&year,&month,&date,&plus);
        int y=0,m=1,d=0;
        int sum=0;
        bool leap = isLeap(year);
        for(int i=1;i<month;i++){
            sum+=days[leap][i-1];
        }
        sum+=date;
        sum+=plus;
        y=year;
        //逐年增加，直到sum<对应天数
        int total[2] = {365,366};
        while(sum>total[isLeap(y)]){
            sum-=total[isLeap(y)];
            y++;    
        } 
        //反解为日期 
        leap = isLeap(y);
        for(int i=1;sum>days[leap][i-1];i++){
            m++;
            sum-=days[leap][i-1];
        }
        d=sum;
        printf("%04d-%02d-%02d\n",y,m,d);
    }
}

3. 其他

1. 剩余的树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//
// Created by alleyf on 2023/6/24.
//
#include<bits/stdc++.h>

using namespace std;
const int MAXL = 100001;
int main() {
    bool flag[MAXL];
    int l, m, num;
    cin >> l >> m;
    num = l + 1;
    for (int i = 0; i <= l; ++i) {
        flag[i] = true;
    };
    while (m--) {
        int left, right;
        cin >> left >> right;
        for (int i = left; i <= right; ++i) {
            if (flag[i]) {
                flag[i] = false;
                num--;
            }
        }
    }
    cout << num;
}

1. 使用一个 l+1 长度的 array 存储所有树的存在状态，初始化所有树的状态为真；
2. 根据区间循环判每棵树的状态，若为真则修改树输出总数的状态为假并将树的总数自减；
3. 输出剩余树的数量。

2. 手机键盘

  1. 用一个数组按顺序保存每个字母所需要的时间段
  2. 循环每个输入的字母求和总次数，判断前后两字符是否在一个按键上，若果是则加两个时间段
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//  
// Created by alleyf on 2023/6/24.  
//  
#include<bits/stdc++.h>  
  
using namespace std;  
  
int main() {  
int letter_num[26] = {1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 4};  
string s;  
while (cin >> s) {  
int allNum = 0;  
for (int i = 0; i < s.size(); ++i) {  
allNum += letter_num[s[i] - 'a'];  
if (i != 0 && s[i] - s[i - 1] == letter_num[s[i] - 'a'] - letter_num[s[i - 1] - 'a']) {  
allNum += 2;  
}  
}  
cout << allNum << endl;  
}  
}

3. xxx_定律

既可递归实现也可 while 迭代迭代实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//  
// Created by alleyf on 2023/6/24.  
//  
#include<bits/stdc++.h>  
  
using namespace std;  
  
int xxx_law(int &num, int &cnt) {  
if (num == 1) {  
return cnt;  
} else if (num % 2 != 0) {  
cnt++;  
num = 3 * num + 1;  
num /= 2;  
return xxx_law(num, cnt);  
} else {  
cnt++;  
num /= 2;  
return xxx_law(num, cnt);  
}  
}  
  
int main() {  
int num;  
while (cin >> num) {  
int cnt = 0;  
cout << xxx_law(num, cnt) << endl;  
}  
}

第三章排序与查找

3.1 排序

1. 排序

> 冒泡排序：
> 1. 升序：外层循环递减，内层循环递增直到外层循环变量；
> 2. 降序：外层循环递增，内层循环从外层循环变量开始递增。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//  
// Created by alleyf on 2023/6/25.  
//  
#include<bits/stdc++.h>  
  
using namespace std;  
  
int main() {  
int n;  
cin >> n;  
int array[n];  
for (int i = 0; i < n; ++i) {  
cin >> array[i];  
}  
for (int i = n; i > 0; --i) {  
for (int j = 0; j < i; ++j) {  
if (array[j] > array[j + 1] && j + 1 < n) {  
int tmp = array[j + 1];  
array[j + 1] = array[j];  
array[j] = tmp;  
}  
}  
}  
for (int value: array) {  
cout << value << ' ';  
}  
return 0;  
}

大部分排序方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
//所有基本的排序方法了，桶排序、基数排序暂不写了  
#include<iostream>  
  
using namespace std;  
const int N = 110, MAX = 1e8;  
int a[N];  
int n;  
int h[N], idx;//heap_sort用  
int tmp[N];//merge_sort用  
int bkt[MAX];//counting_sort用  
  
void buble_sort() {  
for (int i = 0; i < n - 1; i++)  
for (int j = 0; j < n - 1 - i; j++) {  
if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);  
}  
}  
  
void quick_sort(int l, int r) {  
if (l >= r) return;  
int x = a[(l + r) / 2];  
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(l, j);  
quick_sort(j + 1, r);  
}  
  
void selection_sort() {  
for (int i = 0; i < n - 1; i++) {  
int min_pos = i;  
for (int j = i + 1; j < n; j++)  
if (a[j] < a[min_pos]) min_pos = j;  
swap(a[i], a[min_pos]);  
}  
}  
  
void down(int u) {  
int t = u;  
if (u * 2 <= idx && h[u * 2] < h[t]) t = u * 2;  
if (u * 2 + 1 <= idx && h[u * 2 + 1] < h[t]) t = u * 2 + 1;  
if (t != u) {  
swap(h[t], h[u]);  
down(t);  
}  
}  
  
void heap_sort() {  
for (int i = 1; i <= n; i++) h[i] = a[i - 1];  
idx = n;  
for (int i = idx / 2; i > 0; i--) down(i);  
for (int i = 0; i < n; i++) {  
a[i] = h[1];  
h[1] = h[idx--];  
down(1);  
}  
}  
  
void insertion_sort() {  
for (int i = 1; i < n; i++) {  
int cur_idx = a[i];  
int j;  
for (j = i - 1; j >= 0 && a[j] > cur_idx; j--) {  
a[j + 1] = a[j];  
}  
a[j + 1] = cur_idx;  
}  
}  
  
void binary_insertion_sort() {  
for (int i = 1; i < n; i++) {  
int cur_idx = a[i];  
int l = 0, r = i - 1;  
while (l < r) {  
int mid = (l + r + 1) / 2;  
if (a[mid] <= cur_idx) l = mid;  
else r = mid - 1;  
}  
if (a[l] > cur_idx) l = -1;  
int j;  
for (j = i - 1; j > l; j--) a[j + 1] = a[j];  
a[j + 1] = cur_idx;  
}  
}  
  
void shell_sort() {  
for (int gap = n / 2; gap >= 1; gap /= 2) {  
for (int i = gap; i < n; i++) {  
int cur_idx = a[i];  
int j;  
for (j = i - gap; j >= 0 && a[j] > cur_idx; j -= gap) {  
a[j + gap] = a[j];  
}  
a[j + gap] = cur_idx;  
}  
}  
}  
  
void merge_sort(int l, int r) {  
if (l >= r) return;  
int mid = (l + r) / 2;  
merge_sort(l, mid), merge_sort(mid + 1, r);  
int k = 0, i = l, j = mid + 1;  
while (i <= mid && j <= r) {  
if (a[i] <= a[j]) tmp[k++] = a[i++];  
else tmp[k++] = a[j++];  
}  
while (i <= mid) tmp[k++] = a[i++];  
while (j <= r) tmp[k++] = a[j++];  
for (int i = l, j = 0; i <= r; j++, i++) a[i] = tmp[j];  
}  
  
void counting_sort() {  
int max = 0;  
for (int i = 0; i < n; i++) {  
bkt[a[i]]++;  
if (a[i] > max) max = a[i];  
}  
int j = 0;  
for (int i = 0; i < max + 1; i++) {  
while (bkt[i]) {  
a[j++] = i;  
bkt[i]--;  
}  
}  
}  
  
int main() {  
scanf("%d", &n);  
for (int i = 0; i < n; i++) scanf("%d", &a[i]);  
// buble_sort();  
// quick_sort(0, n - 1);  
// selection_sort();  
// heap_sort();  
// insertion_sort();  
// binary_insertion_sort();  
// shell_sort();  
// merge_sort(0, n - 1);  
counting_sort();  
for (int i = 0; i < n; i++) printf("%d ", a[i]);  
return 0;  
}

2. 成绩排序

- 定义一个结构体包含学号与成绩
- 写一个比较器 Compare
- 使用内置 sort 算法，设置迭代头和尾（地址）以及比较规则（比较器）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>  
#include<algorithm>  
  
using namespace std;  
  
//定义学生结构体  
struct Student {  
int number;  
int score;  
  
Student() {}  
  
Student(int n, int s) : number(n), score(s) {}  
};  
  
//定义比较函数  
bool Compare(Student s1, Student s2) {  
//成绩相同比学号  
if (s1.score == s2.score) {  
return s1.number < s2.number; //'<',指按照比较的参数由小到大排序  
} else {  
return s1.score < s2.score; ////'<',指按照比较的参数由小到大排序,同理，如果是'>'，指按照由大到小排序  
}  
}  
  
int main() {  
int n;  
cin >> n;  
//定义数组保存比较学生的基本信息  
Student arr[n];  
for (int i = 0; i < n; ++i) {  
cin >> arr[i].number >> arr[i].score;  
}  
sort(arr, arr + n, Compare);  
for (Student s: arr) {  
cout << s.number << ' ' << s.score << endl;  
}  
return 0;  
}

3. 成绩排序 2

方法 1：
sort 是不稳定排序，stable_sort 才是稳定排序，稳定排序不改变输入的顺序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//  
// Created by alleyf on 2023/6/25.  
//  
#include<bits/stdc++.h>  
#include<algorithm>  
  
using namespace std;  
int num, sort_flag;  
  
struct Student {  
string name;  
int score;  
  
Student() {};  
  
Student(string n, int s) : name(n), score(s) {}  
};  
  
bool Compare(Student s1, Student s2) {  
return sort_flag ? s1.score < s2.score : s1.score > s2.score;//sort_flag为真则升序否则降序  
}  
  
int main() {  
while (cin >> num >> sort_flag) {  
Student arr[num];  
for (int i = 0; i < num; ++i) {  
cin >> arr[i].name >> arr[i].score;  
}  
stable_sort(arr, arr + num, Compare);//重点：sort是不稳定排序，stable_sort才是稳定排序，稳定排序不改变输入的顺序  
for (Student s: arr) {  
cout << s.name << ' ' << s.score << endl;  
}  
}  
return 0;  
}

方法 2：
用一个编号保存每个学生的顺序，排序比较器里成绩相等的按照编号升序排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
#include<algorithm>
#include<cstring> 
using namespace std;
struct student{
	string name;
	int score;
	int num; 
};
int flag; //升序还是降序 
bool cmp(student a,student b){
	if(flag==0) {
		if(a.score==b.score) return a.num<b.num;
		else return a.score>b.score;
	}
	else {
		if(a.score==b.score) return a.num<b.num;
		else return a.score<b.score;	//这里必须写else，否则牛客会编译失败 
	} 
}
int main(){
	int n;
	while(cin>>n){
		cin>>flag;
		student stu[n];
		for(int i=0;i<n;i++){
			cin>>stu[i].name>>stu[i].score;
			stu[i].num=i;
		} 
		sort(&stu[0],&stu[n],cmp); //重点：sort是不稳定排序，stable_sort才是稳定排序 
		for(int i=0;i<n;i++) cout<<stu[i].name<<' '<<stu[i].score<<endl;
	}
	return 0;
}


3.2 查找

1. 找 x

方法 1：
用 flag 标志是否找到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//  
// Created by alleyf on 2023/6/25.  
//  
#include<bits/stdc++.h>  
#include<algorithm>  
  
using namespace std;  
  
int main() {  
int n, t;  
while (cin >> n) {  
int arr[n];  
bool flag = false;  
for (int i = 0; i < n; ++i) {  
cin >> arr[i];  
}  
cin >> t;  
for (int i = 0; i < n; ++i) {  
if (t == arr[i]) {  
cout << i << endl;  
flag = ~flag;  
break;  
}  
}  
if (!flag)  
cout << -1 << endl;  
}  
return 0;  
}

方法 2：
设置初始默认为-1，找到则修改状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<iostream>
#include<cstdio>
using namespace std;
int maxn=200+10;
int main(){
    int arr[maxn];
    int n;
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++){
            scanf("%d",&arr[i]);
        }
        int x;
        int answer=-1;
        scanf("%d",&x);
        for(int i=0;i<n;i++){
            if(arr[i]==x){
                answer=i;
                break;
            }
            }
            printf("%d\n",answer);
        }
    return 0;
}


2. 查找

方法 1：复杂度 O（n）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <map>
using namespace std;

int main() {
    int n;
    int m;
    while(cin>>n) {
        map<int,bool> mp;
        for (int i = 0; i < n; i++) {
            int temp;
            cin>>temp;
            mp[temp] = true;
        }
        cin>>m;
        for (int i = 0; i < m; i++) {
            int temp;
            cin>>temp;
            if (mp.find(temp) != mp.end()) {
                cout<<"YES"<<endl;
            } else {
                cout<<"NO"<<endl;
            }
        }
    }
}

方法 2：复杂度 O（m·n）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//  
// Created by alleyf on 2023/6/25.  
//  
#include<bits/stdc++.h>  
  
using namespace std;  
  
int main() {  
int n, m;  
while (cin >> n) {  
int arr[n];  
for (int i = 0; i < n; ++i) {  
cin >> arr[i];  
}  
cin >> m;  
int tar[m];  
for (int i = 0; i < m; ++i) {  
cin >> tar[i];  
}  
for (int i = 0; i < m; ++i) {  
string status = "NO";  
for (int j = 0; j < n; ++j) {  
if (arr[j] == tar[i]) {  
status = "YES";  
break;  
}  
}  
cout << status << endl;  
}  
}  
return 0;  
}

3. extrenum_index

方法 1：
空间复杂度为 O（1）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
int main() {
	int n, i, left, mid, right;
	while (cin >> n) {
		cin >> mid >> right;
		if (mid != right)
			cout << "0 ";
		for (i = 1; i < n - 1; ++i) {
			left = mid;
			mid = right;
			cin >> right;
			if ((mid - left) * (mid - right) > 0)
				cout << i << ' ';
		}
		if (mid != right)
			cout << i;
		cout << endl;
	}
	return 0;
}

方法 2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>  
  
using namespace std;  
  
int main() {  
int n;  
while (cin >> n) {  
int arr[n];  
for (int i = 0; i < n; ++i) {  
cin >> arr[i];  
}  
for (int i = 0; i < n - 1; ++i) {  
if (i == 0 && arr[i] != arr[i + 1]) {  
cout << i << ' ';  
} else if ((arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) || (arr[i] < arr[i - 1] && arr[i] < arr[i + 1])) {  
cout << i << ' ';  
}  
if (i == n - 2 && arr[i] != arr[i + 1]) {  
cout << i + 1 << ' ';  
}  
}  
cout << endl;  
}  
return 0;  
}

4. 找位置

时间复杂度为 O (n)

1. 用一个额外的矢量 orderS 不重复的添加字符，以保证输出时字符顺序
2. 用 map 的 key 记录字符，value 记录重复出现的次数
3. 最后按照 orderS 的顺序遍历输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>  
  
using namespace std;  
  
int main() {  
string s;  
map<char, vector<int>> sm;  
vector<char> orderS;  
cin >> s;  
for (int i = 0; i < s.length(); ++i) {  
if (sm.find(s[i]) != sm.end()) {  
sm[s[i]].push_back(i);  
} else {  
sm[s[i]] = vector<int>{i};  
orderS.push_back(s[i]);  
}  
}  
for (char item: orderS) {  
auto tmp = sm.find(item);  
if (tmp != sm.end() && tmp->second.size() > 1) {  
for (int index: tmp->second) {  
if (index != tmp->second.back())  
cout << tmp->first << ':' << index << ',';  
else  
cout << tmp->first << ':' << index << endl;  
}  
}  
}  
}

第四章字符串

4.1 字符串处理

1. 特殊乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//  
// Created by alleyf on 2023/6/26.  
//  
#include<bits/stdc++.h>  
#include <string>  
#include <iostream>  
  
using namespace std;  
  
int main() {  
string a, b;  
int sum = 0;  
while (cin >> a >> b) {  
for (char i: a) {  
for (char j: b) {  
sum += (i - '0') * (j - '0');  
}  
}  
cout << sum << endl;  
}  
}

2. 密码翻译

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//  
// Created by alleyf on 2023/6/26.  
//  
#include<bits/stdc++.h>  
  
using namespace std;  
  
int main() {  
string s;  
while (cin >> s) {  
for (int i = 0; i < s.length(); ++i) {  
if ((s[i] >= 'A' && s[i] <= 'Y') || (s[i] >= 'a' && s[i] <= 'y')) {  
s[i] += 1;  
} else if (s[i] == 'z' || s[i] == 'Z') {  
s[i] = s[i] == 'z' ? 'a' : 'A';  
}  
}  
cout << s << ' ';  
}  
}

3. 简单密码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
// 方法1：

//
// Created by alleyf on 2023/6/26.
//
#include<bits/stdc++.h>
using namespace std;
int main() {
    string s;
    while (getline(cin, s)) {
        if (s != "ENDOFINPUT") {
            if (s != "START" && s != "END") {
                int i = 0;
                for (char item : s) {
                    if ((item >= 'A' && item <= 'Z'))
                       s[i] = 'A' + (item - 'A' + 21) % 26;
                    i++;
                }
                cout << s << endl;
            }
        } else {
            break;
        }
    }
    return 0;
}

// 方法2:

//
// Created by alleyf on 2023/6/26.
//
#include<bits/stdc++.h>
using namespace std;
map<char, char> pwd_map{
    {'A', 'V'},
    {'B', 'W'},
    {'C', 'X'},
    {'D', 'Y'},
    {'E', 'Z'},
    {'F', 'A'},
    {'G', 'B'},
    {'H', 'C'},
    {'I', 'D'},
    {'J', 'E'},
    {'K', 'F'},
    {'L', 'G'},
    {'M', 'H'},
    {'N', 'I'},
    {'O', 'J'},
    {'P', 'K'},
    {'Q', 'L'},
    {'R', 'M'},
    {'S', 'N'},
    {'T', 'O'},
    {'U', 'P'},
    {'V', 'Q'},
    {'W', 'R'},
    {'X', 'S'},
    {'Y', 'T'},
    {'Z', 'U'},
};
int main() {
    string s;
    while (getline(cin, s)) {
        if (s != "ENDOFINPUT") {
            if (s != "START" && s != "END") {
                int i = 0;
                for (char item : s) {
                    if ((item >= 'A' && item <= 'Z'))
                       s[i] = pwd_map[item];
                    i++;
                }
                cout << s << endl;
            }
        } else {
            break;
        }
    }
    return 0;
}

4. 统计字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//  
// Created by alleyf on 2023/6/30.  
//  
#include<bits/stdc++.h>  
  
using namespace std;  
  
int main() {  
string ts, s;  
while (getline(cin, ts)) {  
if (ts == "#")  
break;  
getline(cin, s);  
int cnum[ts.length()];  
for (int i = 0; i < ts.length(); ++i) {  
cnum[i] = 0;  
for (char j: s) {  
if (j == ts[i]) {  
cnum[i]++;  
}  
}  
cout << ts[i] << ' ' << cnum[i] << endl;  
}  
}  
  
}  
/**  
* 方法2：  
* using namespace std;  
//1：注意读题，i ng是当四个字符处理，而非i和ng  
//2：如何持续输入？while持续输入第一个字符，循环体内输入第二个  
//如何捕捉结束字符？在第一个字符串输入时识别  
  
int number[128];  
int main()  
{  
string str1,str2;  
while(getline(cin,str1)){  
if(str1=="#") break;  
getline(cin,str2);  
memset(number,0,sizeof(number)); //number数组记录该字符，出现的次数  
for(int i=0;i<str2.size();i++){  
number[str2[i]]++; //长字符串的字符对应ASCII码的下标+1  
}  
for(int i=0;i<str1.size();i++){  
printf("%c %d\n",str1[i],number[str1[i]]);  
}  
}  
}  
//学到的方法：ASCII码不大，想统计每个字符，直接将其对应的ASCII码下标的元素加1即可！  
  
*/

5. 字母统计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
//  
// Created by alleyf on 2023/6/30.  
//  
#include<bits/stdc++.h>  
  
using namespace std;  
map<char, int> c_map{  
{'A', 0},  
{'B', 0},  
{'C', 0},  
{'D', 0},  
{'E', 0},  
{'F', 0},  
{'G', 0},  
{'H', 0},  
{'I', 0},  
{'J', 0},  
{'K', 0},  
{'L', 0},  
{'M', 0},  
{'N', 0},  
{'O', 0},  
{'P', 0},  
{'Q', 0},  
{'R', 0},  
{'S', 0},  
{'T', 0},  
{'U', 0},  
{'V', 0},  
{'W', 0},  
{'X', 0},  
{'Y', 0},  
{'Z', 0},  
};  
  
int main() {  
string s;  
getline(cin, s);  
for (char c: s) {  
if (c_map.find(c) != c_map.end()) {  
c_map[c]++;  
}  
}  
for (auto item: c_map) {  
cout << item.first << ':' << item.second << endl;  
}  
}

4.2 字符串匹配

第五章基础数据结构

5.1 向量

完数与盈数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//  
// Created by alleyf on 2023/8/17.  
//  
#include<bits/stdc++.h>  
  
using namespace std;  
  
int judge_EG(int num) {  
int sum = 0;  
for (int i = 1; i <= num / 2; ++i) {  
if (num % i == 0)  
sum += i;  
}  
if (sum == num)  
return 1;  
else if (sum > num)  
return 2;  
return 0;  
}  
  
int main() {   
// vector<int> E, G;  
string E = "E:", G = "G:";  
for (int i = 2; i <= 60; ++i) {  
if (judge_EG(i) == 1)  
E += " " + to_string(i);  
// E.push_back(i);  
else if (judge_EG(i) == 2)  
G += " " + to_string(i);  
// G.push_back(i);  
}  
cout << E << endl << G;  
// cout << "E:";  
// for (auto e: E) {  
// cout << " " << e;  
// }  
// cout << endl << "G:";  
// for (auto g: G) {  
// cout << " " << g;  
// }  
}
  1. 思路：获取一个数的所有因子可以通过循环取余，判断余数是否为零来获得，若为零则为因子，反之不为因子
  2. 细节：关键在于格式输出的问题

5.2 队列

5.3 栈

剑指offer

简单题

1.数组中重复的数字

桶排序思想

  1. 首先定义一个与输入长度相等的数组，并将所有值置零；
  2. 遍历输入向量，对遇到的值作为数组下标进行自增；
  3. 判断自增后的值是否大于1，若是则为重复数则直接返回。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numbers int整型vector
     * @return int整型
     */
    int duplicate(vector<int>& numbers) {
        if (numbers.size() != 0) {
            int a[numbers.size()];
            //数组元素置零
            for (int i; i < numbers.size(); i++) {
                a[i] = 0;
            }
            //遍历计数
            for (int item : numbers) {
                a[item]++;
                if (a[item] > 1) {
                    return item;
                }
            }
        } else {
            return -1;
        }
        return -1;
    }
};

位置重排

  1. 遍历数组，遇到数组元素与下标相同的不用管。
  2. 遇到数组元素与下标不同，就将其交换到属于它的位置，交换前检查那个位置是否有相同的元素，若有则重复。
  3. 遍历结束完全交换也没重复，则返回-1.

|550

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int duplicate(vector<int>& numbers) {
        for(int i = 0; i < numbers.size(); i++){
            //该位置本来就是对的
            if(numbers[i] == i)
                continue;
            //位置不对，需要换到自己对应的位置
            else{
                //对应位置相等，重复
                if(numbers[i] == numbers[numbers[i]])
                    return numbers[i];
                //交换位置
                else{
                    swap(numbers[i], numbers[numbers[i]]);
                  	i--;
                }
            }
        }
        //没有重复
        return -1;
    }
};

哈希表

  1. 遍历数组，将没有出现过的元素加入哈希表。
  2. 遇到的元素在哈希表中出现过就是重复数组。
  3. 遍历结束也没找到就返回-1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int duplicate(vector<int>& numbers) {
        //哈希表记录重复
        unordered_map<int, int> mp;
        //遍历数组
        for(int i = 0; i < numbers.size(); i++){
            //如果没有出现过就加入哈希表
            if(mp.find(numbers[i]) == mp.end())
                mp[numbers[i]]++;
            //否则就是重复数字
            else
                return numbers[i];
        }
        //没有重复
        return -1;
    }
};


2.替换空格

python直接用字符串函数replace全局替换即可

遍历覆盖法
定义一个新字符串，遍历原字符串，遇到空格新字符串加要求替换的字符，否则添加原字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {

  public:

    /**

     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

     *

     *

     * @param s string字符串

     * @return string字符串

     */

    string replaceSpace(string s) {

        string new_s;

        for (int i; i < s.length(); i++) {

            if (s[i] == ' ') {

                new_s += "%20";

            } else {

                new_s += s[i];

            }

        }

        return new_s;

    }

};

3.从尾到头打印链表

1.数组逆向拷贝

  1. 遍历链表，用一个数组顺序添加节点值
  2. 逆向遍历数组，添加数组值到新数组中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
#include <cmath>
#include <cstddef>
#include <vector>
class Solution {
  public:
     vector<int> printListFromTailToHead(ListNode* head) {
         vector<int> a, b;
         while (head != nullptr) {
             a.push_back(head->val);
             head = head->next;
         }
         for (int i = a.size() - 1; i >= 0; i--) {
             b.push_back(a[i]);
         }
         return b;
     }

};

2.递归

  1. 从表头开始往后递归进入每一个节点。
  2. 遇到尾节点后开始返回，每次返回依次添加一个值进入输出数组。
  3. 直到递归返回表头
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
#include <cmath>
#include <cstddef>
#include <vector>
class Solution {
public:
    //递归函数
    void recursion(ListNode* head, vector<int>& res){ 
        if(head != NULL){
            //先往链表深处遍历
            recursion(head->next, res); 
            //再填充到数组就是逆序
            res.push_back(head->val); 
        }
    }
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> res;
        //递归函数打印
        recursion(head, res); 
        return res;
    }
};


3.栈

  1. 我们可以顺序遍历链表，将链表的值push到栈中。
  2. 然后再依次弹出栈中的元素，加入到数组中，即可实现链表逆序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cmath>
#include <cstddef>
#include <vector>
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> res;
        stack<int> s;
        //正序输出链表到栈中
        while(head != NULL){ 
            s.push(head->val);
            head = head->next;
        }
        //输出栈中元素到数组中
        while(!s.empty()){ 
            res.push_back(s.top());
            s.pop();
        }
        return res;
    }
};

4.用两个栈实现队列

解题思路：

借助栈的先进后出规则模拟实现队列的先进先出

  1. **当插入时，直接插入 stack1
  2. 当弹出时，当 stack2 不为空，弹出 stack2 栈顶元素，如果 stack2 为空，将 stack1 中的全部数逐个出栈入栈 stack2，再弹出 stack2 栈顶元素

图解：

代码展示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public:
    void push(int node) {
        stack1.push(node);
    }
    int pop() {
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        int node = stack2.top();
        stack2.pop();
        return node;
    }
 
  private:
    stack<int> stack1;
    stack<int> stack2;
};

复杂度分析：

  • 时间复杂度：对于插入和删除操作，时间复杂度均为 O(1)。插入不多说，对于删除操作，虽然看起来是 O(n) 的时间复杂度，但是仔细考虑下每个元素只会「至多被插入和弹出 stack2 一次」，因此均摊下来每个元素被删除的时间复杂度仍为 O(1)。

  • 空间复杂度O(N)：辅助栈的空间，最差的情况下两个栈共存储N个元素.

5.旋转数组的最小数字

求解思路：

  1. 暴力法
  • 特殊情况，如果数组为空，则直接返回0
  • 创建最小值 min
  • 遍历数组每一个元素nums，并更新最小值 min = min(min，num)
  • 遍历结束，直接返回 min

时间复杂度O(N)：N表示数组的长度，遍历整个数组O(N)
空间复杂度O(1)：仅使用一个额外空间变量O(1)

1
2
3
4
5
6
7
8
9
10
11
class Solution {
  public:
    int minNumberInRotateArray(vector<int>& nums) {
         int min = 10000;
         for (int item : nums) {
             if (min >= item)
                 min = item;
         }
         return min;
    }
};
  1. 二分法
  • 初始化：定义二分端点双指针i，j，m=（i+j）/ 2为每次二分的中点（ “/“ 代表向下取整除法）
  • 循环二分：循环不成立则按照以下规则更新双指针：
    1. 当 array[m] > array[j] 时： m 一定在左排序数组中，即旋转点 x 一定在 [m + 1, j] 闭区间内，因此执行 i = m + 1；
    2. 当 array[m] < array[j] 时： m 一定在右排序数组中，即旋转点 x 一定在[i, m]闭区间内，因此执行 j = m；
    3. 当 array[m] = array[j] 时： 无法判断 mm 在哪个排序数组中，即无法判断旋转点 x 在 [i, m] 还是 [m + 1, j] 区间中。解决方案： 执行 j = j - 1 缩小判断范围
  • 返回值： 当 i = j 时跳出二分循环，并返回旋转点的值 array[i] 即可。

|500

时间复杂度O(logN)：N表示数组的长度，二分查找O(logN)
空间复杂度O(1)：仅使用常数（i, j, m）额外空间变量O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
  public:
    int minNumberInRotateArray(vector<int>& nums) {
        int i = 0, j = nums.size() - 1;
        while (i != j) {
            int m = (i + j) / 2;
            if (nums[m] > nums[j])
                i = m + 1;
            else if (nums[m] < nums[j])
                j = m;
            else
                j -= 1;
        }
        return nums[i];
    }
};

6.二进制中1的个数

求解思路：

  1. 循环按位比较法（推荐使用）

知识点：位运算

计算机的数字由二进制表示，我们平常的运算是对整个数字进行运算，但是还可以按照二进制的每一位分别进行运算。常见运算有位与、位或、移位、位异或等。

思路：

我们可以检查该数字的二进制每一位是否为1，如果遍历二进制每一位呢？可以考虑移位运算，每次移动一位就可以。至于怎么统计到1呢？我们都只知道数字1与数字相位与运算，其实只是最后一位为1就是1，最后一位为0就是0，这样我们只需要将数字1移位运算，就可以遍历二进制的每一位，再去做位与运算，结果为1的就是二进制中为1的。

具体做法：

  • 遍历二进制的32位，通过移位0-31次实现。
  • 将移位后的1与数字进行位与运算，从而判断数字的二进制每一位结果，结果为1就记录一次。

复杂度分析：

  • 时间复杂度：O(k)O(k)O(k)，kkk为int型的32位，一次遍历
  • 空间复杂度：O(1)O(1)O(1)，常数级变量，没有额外辅助空间
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int  NumberOf1(int n) {
        int res = 0;
        //遍历32位
        for(int i = 0; i < 32; i++){
            //按位比较
            if((n & (1 << i)) != 0)   
                res++;
        }
        return res;
     }
};
  1. 暴力法
  • 判断数n是否为负数，负数则转化为相同二进制表示的正数（$P_b = 2^N+n,N为二进制位数$）
  • 通过连除法，用结果累加n%2的余数，并更新n=n/2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
  public:
    int NumberOf1(int n) {
        int sum = 0;
        long m = n;
        if (n < 0)
            m = n + pow(2, 32);
        while (m != 0) {
            sum += m % 2;
            m /= 2;
        }
        return sum;
    }
};
  1. 位运算优化法（扩展思路）

思路：

有一个性质：$n&(n−1)$，会将n的二进制中最低位由1变成0

我们可以不断让当前的 n与 n−1做位与运算，直到 n的二进制全部变为 0 停止。因为每次运算会使得 n 的最低位的 1 被翻转成0，因此运算次数就等于 n 的二进制位中 1 的个数，由此统计1的个数。

具体做法：

  • 使用循环检查n是否为0.
  • 不为0就与n−1做位与运算，去掉二进制最后一位的1，并统计次数。

图示：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int NumberOf1(int n) {
        int res = 0;
        //当n为0时停止比较
        while(n){  
            n &= n - 1;
            res++;
        }
        return res;
     }
};
算法学习
#Algorithm
algorithm
https://alleyf.github.io/2023/03/56d5f0383564.html
作者
alleyf
发布于
2023年3月17日
更新于
2023年8月27日
许可协议