[C++知识库]【day4】备战蓝桥杯 - 每日刷题解析

题目链接：

奇数倍数

第几个幸运数字

四平方和

迷宫

🐬奇怪的奇数

题目难度：??

🌤解题思路

对于这类题目，从小到大枚举所有2019的整数倍数，判断枚举数的每一位是否为奇数，返回第一个满足条件的数。过程不过多赘述，直接上代码：

#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
  int i=2019;
  int x=0;
  int n=0;
  int num;
  for(;i<1000000;i+=2019){
      num=i;
      // 判断是否为奇数
    for(;num>0;num=num/10){
        n=num%10;
        if(n%2==0){
            break;
        }
    }
    if(num!=0){
        continue;
    }else{
        printf("%d\n",i);
        break;
    }
  }
  return 0;
}

🌀第几个幸运数字

题目难度：??????

🐤解题思路

方法有很多，能够使用最小堆解题，时间复杂度是$O(nlgn)$，其中n代表所求数字时第$n$个幸运数字。不过这里我推荐使用三指针+动态规划的做法，具体方法如下：

定义数组数组$dp$从小到大存储所有的幸运数字，我们知道幸运数字一定是只有$3、5、7$为因子的数字，因此任意一个幸运数字一定能够将其乘以$3、5、7$，得到新的幸运数字，也就是说幸运数字一定能够由比它小的幸运数字乘以$3或5或7$推算出来。

那么既然这样对于第$i$位的幸运数字究竟由哪一位推算出来呢？此时可以定义$idx3idx5idx7$ 分别存储供应位，表示该位的值提供新的幸运数字，提供的幸运数字分别是$dp[idx3]?3，dp[idx5]?5，dp[idx7]?7$。开始时值都为0，$dp[0]=1$，此时提供幸运数字分别是：

$1?3=3，1?5=5，1?7=7$

获取这三位供应幸运数字的最小值，就是当前位上的幸运数字，如果当前位上的幸运数字大于等于某一个供应位提供的幸运数字，那么表示该位供应的幸运数字已经出现在数组中，该供应位向后移动一位。

循环直到出现最小值也就是当前位幸运数字与所求相等时，返回当前位数$i$。时间复杂度：$O(N)$

如果还是没有思路可以移步这道题的题解丑数 ，观摩大佬们的理解😻。

#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;
#define ll long long
#define M 10000
#define Target 59084709587505
int main()
{
    int arr[3]{ 3,5,7 };
    int idx3, idx5, idx7;
    idx3 = idx5 = idx7 = 0;
    ll dp[M];
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for (ll  i = 1; i < M; ++i) {
        ll val1 = dp[idx3] * 3;
        ll val2 = dp[idx5] * 5;
        ll val3 = dp[idx7] * 7;
        ll m = min(val1, min(val2, val3));
        if (val1<=m) {
            dp[i] = m;
            ++idx3;
        }
        if (val2<=m) {
            dp[i] = m;
            ++idx5;
        }
        if (val3<=m) {
            ++idx7;
            dp[i] = m;
        }
        if (m == Target) {
            cout << i << endl;
            break;
        }
    }
    return 0;
}

🌴四平方和

题目难度：????

🎇解题思路

核心思路按照从小到大枚举所有可能出现的情况，要注意：所选的值平方之和不能超过n，且满足a<=b<=c<=d

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner cin=new Scanner(System.in);
        int n = cin.nextInt();
        for (int a1 = 0; a1 * a1 <= n; ++a1) {
            for (int a2 = a1; a2 * a2 + a1 * a1 <= n; ++a2) {
                for (int a3 = a2; a3 * a3 + a2 * a2 + a1 * a1 <= n; ++a3) {
                    int red = n - a1 * a1 - a2 * a2 - a3 * a3;
                    int sq = (int) Math.sqrt(red);
                    if (sq * sq == red) {
                        System.out.println(a1 + " " + a2 + " " + a3 + " " + sq);
                        return;
                    }
                }
            }
        }
    }
}

🌊迷宫

??解题思路

剖析题目关键字：步数最少 返回结果的字典序最小

• 对于迷宫问题常规解法是 bfs或 dfs算法，为了尽快得到最少的步数，这里使用 bfs 算法
• 为了返回的字典序最小，bfs遍历时依次按照：D、L、R、U的顺序遍历，返回的结果一定是字典序最小的。

为了不重复到达一个点影响程序性能，可以使用used数组将遍历过的点进行标记，同样也可以将遍历过的点由0该为1防止重复遍历。

??注意：

我的代码中使用了Java流读取同路径下的file.txt文件，如果没有创建该文件写入数据请先创建文件!!!

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static class Node{
        StringBuilder paths;
        int x;
        int y;

        Node(int x, int y,StringBuilder str) {
            this.x = x;
            this.y = y;
            paths = str;
        }
    }
    static char[][] arr = new char[100][100];
    static int[][] directs = new int[][]{{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
    static char[] directChar = new char[]{'D', 'L', 'R', 'U'};
    static int n, m;
    public static void main(String[] args) throws IOException {
        BufferedReader stream = new BufferedReader(new FileReader("file.txt"));
        String str;
        while ((str = stream.readLine()) != null) {
            m = str.length();
            arr[n++] = str.toCharArray();
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(0, 0, new StringBuilder()));
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            int curx = cur.x;
            int cury = cur.y;
            StringBuilder s = cur.paths;
            if (curx == n - 1 && cury == m - 1) {
                System.out.println(s);
                return;
            }
            arr[curx][cury] = '1';
            for (int i = 0; i < 4; i++) {
                int nx = curx + directs[i][0];
                int ny = cury + directs[i][1];
                if (nx < 0 || ny < 0 || nx >= n || ny >= m || arr[nx][ny] == '1') {
                    continue;
                }
                StringBuilder ss = new StringBuilder(s);
                ss.append(directChar[i]);
                queue.add(new Node(nx, ny, ss));
            }
        }
    }
}