前言

今天家里亲戚吃饭三桌饭好忙啊啊啊，累死了，在家里都走了1.5w步，然后碰了点Django框架，准备在放假前把那个三创赛基础搞出来，就是后台连接一个数据库就好了。

题目

leetcode 17. 电话号码的字母组合

题目

电话号码的字母组合

思路

其实就是一个暴力的dfs，直接O(N·4^N)

代码

class Solution {
public:
    vector<string> ans;
    string strs[10]={
        "", "", "abc", "def",
        "ghi", "jkl", "mno",
        "pqrs", "tuv", "wxyz",
    };
    vector<string> letterCombinations(string digits) {
        if(digits.empty()) return ans;
        dfs(digits, 0, "");
        return ans;
    }
    void dfs(string& digits, int index, string path){
        if(index == digits.size()) ans.emplace_back(path);
        else{
            for(auto&c : strs[digits[index] - '0']){
                dfs(digits, index + 1,path + c);
            }
        }
    }
};

注意我们需要遍历的是每一个数字所映射的字符，所以是strs[digits[index] - '0']

leetcode 263. 丑数

题目

丑数

思路

由于丑数是有2或3或5的数，所以我们可以把所有的2，所有的3，所有5去掉后，看看最后结果是否为1即可。

代码

class Solution {
public:
    bool isUgly(int n) {
        if(n <= 0) return false;
        while(n % 2 == 0) n /= 2;
        while(n % 3 == 0) n /= 3;
        while(n % 5 == 0) n /= 5;
        return n == 1;
    }
};

leetcode 264. 丑数 II

题目

丑数 II

思路

我们直接采用暴力模拟法是会超时的。
其实我们可以这样看，丑数可以分为3类数，S2(含有2的丑数)，S3(含有3的丑数)，S5(含有5的丑数)。显然S2，S3，S5是会有重叠的数的。
S2： 12 22 32 ······
S3： 13 23 33 ······
S5： 15 25 3*5 ······
很显然我们发现，S2除以2以后所得到的数组仍然全部都是丑数，所以它们其实可以由一个数组得到，完成三路归并。

代码

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> temp(1,1);
        for(int i = 0, j = 0, k = 0; temp.size() < n;){
            int r = min(temp[i] * 2, min(temp[j] * 3, temp[k] * 5));
            //找到当前3个指针所对应的三路数中的最小数
            temp.emplace_back(r);//塞进temp中
            if(r == temp[i] * 2) ++i;
            if(r == temp[j] * 3) ++j;
            if(r == temp[k] * 5) ++k;
        }
        return temp.back();
    }
};

acwing 842 排列数字

题目

842 排列数字

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i ++ ){
        arr[i] = i + 1;
    }do{
        for (int i = 0; i < n; i ++ ){
            cout << arr[i] << " ";
        }
        cout << endl;        
    }while(next_permutation(arr, arr + n));
}

这是用c++17的next_permutation的赖皮方法

#include <iostream>
using namespace std;

const int N = 10;

int n;
int arr[N];
bool check[N];

void dfs(int index){
    if(index == n){
        for(int i = 0; i < n; ++ i) printf("%d ",arr[i]);
        printf("\n");
    }
    for(int i = 1; i <= n; ++ i){
        if(!check[i]){
            //如果i没被用过
            arr[index] = i;
            check[i] = true;
            dfs(index + 1);
            check[i] = false;
        }
    }
}
int main(){
    cin >> n;
    
    dfs(0);
}

有点回溯算法，回溯算法一般需要恢复现场.
check数组是记录当前数i有没有被使用，arr数组是操作的数组。有个很好理解的说法：dfs(index + 1)是进入下一层递归，所以出来后check[i] = false