【算法】算法笔记

dp -- 三指针法

例题

给你一个整数 n ,请你找出并返回第 n丑数

丑数 就是只包含质因数 23 和/或 5 的正整数。

题解

class Solution {
public:
    int nthUglyNumber(int n) {
        int* dp = (int *)malloc(sizeof(int) * n);
        memset(dp, 0, sizeof(int) * n);
        dp[0] = 1;
        int p2 = 0, p3 = 0, p5 = 0;
        int min1;
        int i = 1;
        while(i < n) {
            min1 = min(min(dp[p2] * 2, dp[p3] * 3), dp[p5] * 5);
            if(dp[p2] * 2 == min1) ++p2;
            if(dp[p3] * 3 == min1) ++p3;
            if(dp[p5] * 5 == min1) ++p5;
            dp[i++] = min1;
        }
        return dp[n - 1];
    }
};

说明

三指针法:因为丑数只是因数只有 2, 3, 5 的数;

所以先设置一个 dp 数组表示当前已经找出并排列好的丑数数组;

再 3 个指针:i, j, k 表示 将当前已经排好的数组元素 *2,*3,*5 所得的数组(实际上,因为所得的数字最终会加入唯一的排序数组,所以并不用真正将 3 个数组建立起来),

因为排序后数组 *2,*3,*5得到的也是已经排序数组,接下来的目的就是从这3个虚拟数组中的头元素中取得最小那个值;(实际上并不会出现 3 个数组)

所以关键就是如何用这3个指针进行选择,

实际上排序并不是在加入排序数组后才整理排序,而是每次用老元素 *2,*3,*5生成新元素的时候,选择最小的加入达到排序目的,这个时候指针移动就起到作用了,如下过程所示:

-----------------------------------------------------

已经排好的数组,先放进第一个丑数 1:[1]

排好数组*2 :[1]*2=2

排好数组*3 :[1]*3=3

排好数组*5 :[1]*5=5

选结果中最小的数加入数组,此时明显是 2,新的排序数组为[1,2];

-----------------------------------------------------

已经排好的数组:[1,2] ------ 此时上次结果中,2,3,5 只用到了 2;但 3 明显是这次需要加入的数;既然 2 已经加入,再去对比 2 没意义了,那么就将 (*2 的指针) [1]转向下一位[2],对比 (下一个元素*2 和 3,5)的大小,取最小的加入;

排好数组*2 :[2]*2=4

排好数组*3 :[1]*3=3

排好数组*5 :[1]*5=5

选结果中最小的数加入数组,此时明显是 2,新的排序数组为[1,2,3];

-----------------------------------------------------

已经排好的数组:[1,2,3] ------ 3 已经加入,移动它的指针到排序数组下一位;

排好数组*2 :[2]*2=4

排好数组*3 :[2]*3=6

排好数组*5 :[1]*5=5

选结果中最小的数加入数组,此时明显是 4,新的排序数组为 [1,2,3,4];

依次类推;可以看到,实际上,只需将指针进行分别移动就可以了;所以要做出 3 个指针;

-----------------------------------------------------

维护 3 个值 val2, val3, val5,表示将当前排列好数组 分别*2,*3,*5所得的结果数;

因为可能 3 组数出现重复现象,所以要判断是否重复后再加入

统计 1 的个数

可以位运算,也可用 cpp 内置函数 __builtin_popcount(n);

类 split 函数的操作

//C++ split
istringstream strs(str);
vector<string> words;
string word;
while(strs >> word){
    words.push_back(word);
}

快速幂

int pow(int a, int k){
    int ans = 1;
    while(k){
        if(k & 1) ans *= a;   //判断奇偶只用判断最后一位比取模快
        a *= a;
        k >>= 1;      //比除法快多了
    }
    return ans;
}

快速幂取余

int pow_mod(int a, int k, int mod) {
    int ans = 1 % mod;
    while(k){
        if(k & 1) ans = (long long)ans * a % mod;  //防止在对P取模前溢出
        a = (long long)a * a % mod;
        k >>= 1;  //比除法快多了
    }
    return ans;
}

快速乘

long long quickMul(long long a, long long b, long long mod){
    a %= mod;
    b %= mod;
    long long  ans = 0;
    while(b){
        if(b & 1){
            ans += a;
            if(ans >= mod)
                ans -= mod;
        }
        b >>= 1;
        a <<= 1;
        if(a >= mod)  a -= mod;
    }
    return ans;
}

double 版

long long quickMul(long long a,long long b,long long mod) {
    a %= mod;
    b %= mod;
    long long c = (long double)a * b / mod;
    long long ans = a * b - c * mod;
    if(ans < 0) ans += mod;
    else if(ans >= mod) ans -= mod;
    return ans;
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注