刷题总结

本文最后更新于：1 年前

算法刷题（思路，错误点，数据结构知识点）

个人总结与整理

零钱兑换问题：

【动态规划，递归】 Coins change

1
2
3
4
5
6
7
8
9
10
11
12
13
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1
Example 2:

Input: coins = [2], amount = 3
Output: -1
Note:
You may assume that you have an infinite number of each kind of coin.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/coin-change

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#思路一：动态规划迭代（直接简单的套路）
class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        dp=[amount+1 for i in range(amount+1)] #初始化记录数组,
        #思考：为什么是数值一开始都是amount+1,首先这样设置的目的是方便比较，相当于设置为无穷大，其次在动态规划的过程中，向下寻找dp[i-coin]时，若找不到最少值就能保持dp[i]==amount+1即最初的最大值状态
        dp[0]=0 #最低价格为0时的答案
        for i in range(len(dp)):
            for coin in coins:
                if i<coin:
                    continue
                dp[i]=min(dp[i],1+dp[i-coin])#dp[i]更新为零钱兑换所需最小值
                print(dp[i])
        print(dp)
        if dp[amount]==amount+1: #如果更新完所有的数值后dp[-1]无解，则返回-1
            return -1
        return dp[amount]

采用递归解题时，常见的缺陷是：函数调用的参数是通过栈空间来传递的，在调用过程中会占用线程的栈资源。而递归调用，只有走到最后的结束点后函数才能依次退出，而未到达最后的结束点之前，占用的栈空间一直没有释放，如果递归调用次数过多，就可能导致占用的栈资源超过线程的最大值，从而导致栈溢出，导致程序的异常退出；

而大部分的递归问题，都可以通过栈实现递归转化为非递归

DFS深度优先搜索，在二叉树的题目中，其实与二叉树的前序遍历是一致的

当结合栈的运用时，要注意左子树后入栈（后进先出）

散列函数Hash与回溯算法

典型问题：

  • N-Queen puzzle
    n*n取n
    对于每行列举1~n确定位于哪一列即为N×N量级
    研究棋盘，有（X,Y表示行，列）：
    abs(x1-x2)=abs(y1-y2) 表示两个点之间在同一对角线上的关系
    由此作为判断能否进一步列举的条件
    主要的思路是，先分析好一个子问题再演化成子问题集的合并
    回溯模板
    hashtable[index]=true;
    dfs(index+1,res);
    HashTable[index]=false;
    二分查找

  • 若二分上界超过int型数据范围的一般，在查询较靠后的数据时可能导致
    mid=(left+right)/2 结果溢出，一般改用：mid= left + (right-left)/2

  • 快速幂：要点

    • 幂的分解，奇偶数次项对应不同的分解方式，并利用递归
快速排序与随机选择

  • 分析快速排序的时间复杂度

  • 由此，如何高效的在每次递归使用快速排序开始前选好pivot能够带来优化，于是研究随机选择与two pointers思想结合

    • tips algorithm中的sort函数运用的就是快速排序，如果能用sort尽量就直接用利于提高效率减少代码量
最大公约数与最小公倍数

  • gcd(a,b) 

    1
    2
    3
    4
    int gcd(int a, int b)
    {
        return !b ? a : gcd(b, a % b);
    }
  • lcm(a,b)= (a/gcd(a,b))*b [括号只是为了更明显的区分计算步骤，先除以最大公约数防止计算溢出]
    1
    return a/gcd(a,b)*b
    动态规划 two pointers
  • 动态规划模板：
素数的判断
  • 算法的依据 ：
    • 设 k为n的约数（在 1至n-1之间）
    • n%k=0 , k * (n / k ) == n; n/k与k都小于n
    • 且能满足一个小于sqrt(n)另一个大于，因此只需要在2~sqrt(n)的向下取整范围内进行素数的判断即可
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      #include <cstdio>
      #include <math.h>
      //基本的素数判断算法
      bool isPrime(int n)
      {
          int sqr = (int)sqrt(1.0 * n);
          //对开根号的结果向下取整，sqrt函数的参数为浮点数
          if (n <= 1)
              return false;
          else
          {
              for (int i = 2; i <= sqrt; i++)
              {
                  if (n % i == 0)
                      return false;
              }
          }
          return true;
      }
      常用于素数表的建立，以及寻找某数值范围内所有的素数。

  • 筛法求素数表 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
    34
    35
    #include <cstdio>
    #include <math.h>
    //该算法求的是100内的素数
    const int maxn = 101;
    int prime[maxn];
    int pNum = 0;
    bool p[maxn] = {0};

    void findPrime()
    { //在[2,maxn)区间遍历判断
        for (int i = 2; i < maxn; i++)
        {
            if (p[i] == false) //若i是素数
            {
                prime[pNum++] = i;
                //将该素数存进表中
                for (int j = i + i; j < maxn; j += i)
                { //筛去所有j的倍数
                    p[j] = true;
                }
            }
        }
        //题2: 先制表，再输出第i个素数,数组空间的大小尽量设置的比需求大一些
    }

    int main()
    {

        findPrime();
        for (int i = 0; i < pNum; i++)
        {
            printf("%d ", prime[i]);
        }
        return 0;
    }
质因子分解

  • 依据，结合素数判断部分的知识得出结论

    • 对一个正整数n来说，若在它[2,n]范围内有质因子，则质因子的分布情况无非两种

      • 全部在sqrt(n)左侧即<=sqrt(n)

      • 一个质因子>sqrt(n),其余全部<=sqrt(n)

        [若有两个以上大于根号n，则p1*p2>n不符合实际，因此最多只有一个在右侧]

  • 算法 PAT A1059

    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
    #include <cstdio>
    #include <math.h>
    const int maxn = 100010;
    int prime[maxn];
    int pNum = 0;
    bool p[maxn] = {0};
    void findPrime()
    { //在[2,maxn)区间遍历判断
        for (int i = 2; i < maxn; i++)
        {
            if (p[i] == false) //若i是素数
            {
                prime[pNum++] = i;
                //将该素数存进表中
                for (int j = i + i; j < maxn; j += i)
                { //筛去所有j的倍数
                    p[j] = true;
                }
            }
        }
    }

    struct factor
    {
        int x, cnt;
        //x is factor,cnt present numbers of factor
    } fac[10];
    int main()
    {
        findPrime(); //打表
        int n, num = 0;
        scanf("%d", &n);
        if (n == 1)
            printf("1=1");
        else
        {
            printf("%d=", n);
            int sqr = (int)sqrt(1.0 * n);
            for (int i = 0; i < pNum && prime[i] <= sqr; i++)
            {
                if (n % prime[i] == 0) //若当前数为n的质因子
                {
                    fac[num].x = prime[i];
                    fac[num].cnt = 0;
                    while (n % prime[i] == 0)
                    {
                        fac[num].cnt++;
                        n /= prime[i];
                    }
                    num++;
                }
                if (n == 1)
                    break;
            }
            if (n != 1)
            {
                fac[num].x = n;
                fac[num++].cnt = 1;
                //存在>sqrt(n)的质因子
            }
            //print
            for (int i = 0; i < num; i++)
            {
                if (i > 0)
                    printf("*");
                printf("%d", fac[i].x);
                if (fac[i].cnt > 1)
                {
                    printf("^%d", fac[i].cnt);
                }
            }
        }
        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
    #include <iostream>
    #include <cmath>

    using namespace std;
    int main(void)
    {
    	int n = 0;
    	cin >> n;
    	cout << n << "=";
    	
    	int sqrtn = sqrt(n), count = 0;
    	for (int i = 2;i <= sqrtn && n > 1;++i) {
    		if (count) cout << "*";
    		for (count = 0;!(n % i) && n > 1;n /= i, ++count);
    		if (count >= 1) {
    			cout << i;
    			if (count > 1) cout << "^" << count;
    		}
    	}
    	if (!count) cout << n;
    	
    	return 0;
    }
大数运算问题
C++ STL 标准模板库

  • vector 可变长数组

    • 二维数组定义用法:
        1. vector vi[100];如此定义仅二维上为可变长，一维为定长 100；
        1. vector> vi 一维和二维都是变长数组
    • 访问数组
      • 下标访问 vi[0]

  • 迭代器(iterator)访问 vector::iterator it=vi.begin();

    it指向数组起始地址，类似指针，可通过*it来访问向量组中的元素

    1
    vi[i]=*(vi.begin()+i)=*(it+i);

  • end()函数并不指的是尾元素地址而是其下一地址，左闭右开这么理解，该地址不存储任何元素

  • 支持自加自减操作；it++，++it
    拓展变形： 

    1
    2
    3
    for(vector<int>:: iterator it=vi.begin();it!=vi.end();it++){
        printf("%d ",*it);
    }

  • size()函数返回的是unsigned类型，但一般用%d取整型结果问题不大

  • vector用处：对于不确定输入样本的按照一定格式输出的问题，利用vector来存储输入的结果再遍历输出；邻接表

set 集合
排序题

  • 解题思路基本都是差不多的

  • 涉及存储量大的数据或者说以结构体的形式来进行比较

  • 例题： A1012

    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
    #include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    const int length = 1000000;
    struct student
    {
        int id;
        int rank[4]; //0-3:A,C,M,E
    } stu[2005];

    int ans[length][4] = {0}; //保存每个id下每个成绩对应的排名
    int now;

    bool cmp(student a, student b)
    { //cmp只能带两个参数
        return a.rank[now] > b.rank[now];
    }
    int main()
    {
        int n, m;
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++)
        {
            scanf("%d %d %d %d", &stu[i].id, &stu[i].rank[1], &stu[i].rank[2], &stu[i].rank[3]);
            stu[i].rank[0] = round((stu[i].rank[3] + stu[i].rank[1] + stu[i].rank[2]) / 3.0) + 0.5;
        }

        for (now = 0; now < 4; now++)
        { //依次排序
            sort(stu, stu + n, cmp);
            //第一名先设置好
            ans[stu[0].id][now] = 1;
            for (int j = 1; j < n; j++)
            {
                if (stu[j].rank[now] == stu[j - 1].rank[now])
                {
                    //则排名一样
                    ans[stu[j].id][now] = ans[stu[j - 1].id][now];
                }
                else
                {
                    ans[stu[j].id][now] = j + 1;
                }
            }
        }

        char map[4] = {'A', 'C', 'M', 'E'};
        int query;
        for (int i = 0; i < m; i++)
        {
            scanf("%d", &query);
            if (ans[query][0] == 0)
            {
                printf("N/A\n");
            }
            else
            {
                int k = 0;
                for (int j = 1; j < 4; j++)
                { //选出最小的数值，若大小相同则输出优先级最高的字母
                    if (ans[query][j] < ans[query][k])
                    {
                        k = j;
                    }
                }
                printf("%d %c\n", ans[query][k], map[k]);
            }
        }
        return 0;
    }

  • 首先不要被大量的数据吓到了，要把题目理解清除，找到排序的对应要求，拆分成多个步骤来解题循序渐进

刷题 C++算法
C++

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！