发表于 | 更新于 | 分类于

题目

1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && !(n&(n-1));
    }
};

考虑：

  • num > 0时，才会是一个数的幂。负数和0不会是一个正整数的幂。

  • !(num&(num-1))时，用来判断num是不是2的幂，

    • 因为一个数是2的幂的话，则它2进制的第一位必然是1，与num-1与运算后，结果必然为0

Reference

https://leetcode-cn.com/problems/power-of-four/solution/e-you-shi-yi-dao-zhuang-bi-jie-fa-de-suan-fa-ti-2/

https://www.geeksforgeeks.org/program-to-find-whether-a-no-is-power-of-two/

发表于 | 更新于 | 分类于

题目

非位运算解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool isPowerOfFour(int num) {
        
        if (num == 0) return false;

        int mod;

        while (num != 1)
        {
            mod = num % 4;
            num /= 4;
            
            if (mod != 0)
            {
                return false;
            }
        }

        return true;
    }
};

位运算：

1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfFour(int num) {
        return num > 0 && !(num&(num-1)) && !(num & 0xAAAAAAAA);
    }
};

考虑：

  • num > 0时，才会是一个数的幂。负数和0不会是一个正整数的幂。
  • !(num&(num-1))时，用来判断num是不是2的幂，
    • 因为一个数是2的幂的话，则它2进制的第一位必然是1，与num-1与运算后，结果必然为0
  • !(num & 0xAAAAAAAA), 用来判断num是不是4的幂，
    • 因为一个数是4的幂的话，则它2进制必然第一位是1且第一位是奇数位，0xA=1010，则4的幂与其求与运算后，则为0，求反得1

总结

位运算小技巧：

  • !(n&(n-1))，用于判断n是不是2的幂
  • !(num&(num-1)) && !(num & 0xAAAAAAAA), 用于判断n是不是4的幂
  • 对于n的幂，可以先枚举一定的例子，然后对枚举结果进行归纳找到规律。

Reference

https://leetcode-cn.com/problems/power-of-four/solution/e-you-shi-yi-dao-zhuang-bi-jie-fa-de-suan-fa-ti-2/

https://www.geeksforgeeks.org/program-to-find-whether-a-no-is-power-of-two/

https://www.geeksforgeeks.org/find-whether-a-given-number-is-a-power-of-4-or-not/

发表于 | 更新于 | 分类于

背包问题总共有9种，称为背包9讲。

  1. 01背包问题
  2. 完全背包问题
  3. 多重背包问题
  4. 混合背包问题
  5. 二维费用的背包问题
  6. 分组背包问题
  7. 背包问题求方案数
  8. 求背包问题的方案
  9. 有依赖的背包问题

有\(N\)件物品和一个容量是\(V\)的背包。

不同背包问题的条件：每件物品只能使用一次。

第\(i\)件物品的体积是 \(v_i\)，价值是 \(w_i\)。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。

输入格式

第一行两个整数，\(N, V\)用空格隔开，分别表示物品数量和背包容积。

接下来有 \(N\) 行，每行两个整数 \(v_i, w_i\)，用空格隔开，分别表示第 \(i\) 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

\(0<N,V≤10000\) \(0<v_i,w_i≤10000\)

输入样例

1
2
3
4
5
4 5
1 2
2 4
3 4
4 5

输出样例：

1
8

01背包问题

题目描述

有\(N\)件物品和一个容量是\(V\)的背包。

每件物品只能使用一次。

第\(i\)件物品的体积是 \(v_i\)，价值是 \(w_i\)。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。

输入格式

第一行两个整数，\(N, V\)用空格隔开，分别表示物品数量和背包容积。

接下来有 \(N\) 行，每行两个整数 \(v_i, w_i\)，用空格隔开，分别表示第 \(i\) 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

\(0<N,V≤10000\) \(0<v_i,w_i≤10000\)

输入样例

1
2
3
4
5
4 5
1 2
2 4
3 4
4 5

输出样例：

1
8

解

状态：

状态\(f[i][j]\)表示前\(i\)个物品的总体积\(j\)下，总价值为\(f[i][j]\).

\(result = f[i][j]\)

初始状态：\(f[0][0] = 0\)

终止状态：\(f[n][m]\)

状态转移方程：

考虑第\(i\)个状态和\(i-1\)个状态间的递推关系:

  • 不选第\(i\)个物品，\(f[i][j] = f[i-1][j]\)

  • 选第\(i\)个物品，\(f[i][j] = f[i-1][j-v[i]] + w[i]\)

  • \(f[i][j] = max(f[i-1][j], f[i-1][j-v[i]]+ w[i])\)

    其中\(v[i]\)是第\(i\)个物品的体积, \(w[i]\)是第\(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
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int f[N][N];
int V[N], w[N];

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i];
	
	for (int i = 1; i <= n; ++i)
		for (int j = 0; j <= m; ++j)
		{
			f[i][j] = f[i-1][j];
			if (j >= m)
			{
				f[i][j] = max(f[i][j], f[i-1][j-v[i]] + w[i]);
			}
		}
		
	cout << f[n][m] << endl;
    
    return 0;
}

因为状态\(i\)每次都仅依赖状态\(i-1\)，故可以优化额外空间复杂度为\(O(logN)\)

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 <iostream>
#include <string>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int f[N];
int v[N], w[N];

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)	cin >> v[i] >> w[i];
	
	for (int i = 1; i <= n; ++i)
		for (int j = m; j >= v[i]; --j)
			f[j] = max(f[j], f[j-v[i]] + w[i]);
			
    /*
    所有f[i] = 0, 则输出f[m];
    假如仅f[0] = 0, 则需要遍历一遍枚举出最小值;
    */
	cout << f[m] << endl;
	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
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int f[N];

int main()
{
	cin >> n >> m;
    for (int i = 0; i < n; ++i)
    {
        int v, w;
        cin >> v >> w;
        for (int j = m; j >=v; ++j)
        {
            f[j] = max(f[j], f[j-v] + w);
		}
	}

	cout << f[n] << endl;
    
    return 0;
}

  • 因为要依赖dp表中上一层的状态，要先更新下标比较大的dp数组元素，此时通过状态转移方程求最大值的时候还未更新下标较小的dp数组元素，即下标较小的dp数组元素还是上一层的值，所以要逆序遍历。

  • 要保证在1维DP中计算\(f[j]\)状态时，用的是\(f[i-1][j-v[i]]\)而不是\(f[i][j-v[i]]\)的

  • ！不能理解的时候再去看dp表，因为要保证这一层的状态依赖于上一层的状态。

    • e.g. 若顺序计算的话

      对于 \(i=2, j=6, v[2] = 3\)，

      \(dp[6]=max(dp[6], dp[6-v[2]]+w[2]) = max(dp[6], dp[3] + w[2])\)

      因为动态规划是第\(i\)层的状态依赖于第\(i-1\)层的。

      这时，要计算\(max\)外的\(dp[6]\)，要用到\(max\)内的\(dp[6], dp[3]\)。

      其中\(max\)内的\(dp[6]\)是第\(i-1\)层的，是\(dp[3]\)是第\(i\)层的，故使得状态转移不满足要求，所以得逆序。

      可以见 此处例子

完全背包问题

有\(N\)件物品和一个容量是\(V\)的背包。

每件物品都有无限件可用。

第\(i\)件物品的体积是 \(v_i\)，价值是 \(w_i\)。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。

输入格式

第一行两个整数，\(N, V\)用空格隔开，分别表示物品数量和背包容积。

接下来有 \(N\) 行，每行两个整数 \(v_i, w_i\)，用空格隔开，分别表示第 \(i\) 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

\(0<N,V≤10000\) \(0<v_i,w_i≤10000\)

输入样例

1
2
3
4
5
4 5
1 2
2 4
3 4
4 5

输出样例：

1
10

解：

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
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int f[N];

int main()
{
	cin >> n >> m;
    for (int i = 0; i < n; ++i)
    {
        int v, w;
        cin >> v >> w;
        
        // 要累加每一次的结果
        for (int j = v; j <= m; ++j)
        {
            f[j] = max(f[j], f[j-v] + w);
		}
	}
		
    cout << f[m];
	return 0;
}

从代码上看就是，把 01背包 的代码的二重循环，由重后往前遍历，改成了重前往后遍历。

从状态转移方程上来看，通过二维DP表的形式:

  • \(f[i][j] = max(f[i-1][j], f[i-1][j-v[i]]+ w[i])\)

    \(max(不选第i个物品，\ 选了第i个物品)\)

  • \(if\ j-v[i]*k <= 0 \\f[i][j] = max(f[i-1][j], f[i][j-v[i]]+ w[i], f[i][j-v[i]*2]+w[i]*2+...)\)

    \(max(不选第i个物品，\ 选了第i个物品1次, \ 选了第i个物品2次, ...)\)

    现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果f[i][v-c[i]]，所以就可以并且必须采用v= 0..V的顺序循环。

    或者由这个2维动态转移方程得来。

混合背包问题

References

https://www.cnblogs.com/jbelial/articles/2116074.html

https://www.bilibili.com/video/av33930433?p=1

https://www.acwing.com/solution/acwing/content/3982/

发表于 | 更新于 | 分类于

题目

  1. 用STL实现小根堆

按理说应该实现些其它功能，比如：

  • vecotor中是否包含multiple elements
  • 堆的一些常用功能，如：heapify
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
class Solution {
public:
    int nthUglyNumber(long n) {
        vector<long> vi = {1};

        make_heap(vi.begin(), vi.end(), greater<>());
        long top;
        for (long i = 0; i < n; ++i)
        {
            pop_heap(vi.begin(), vi.end(), greater<>());
            
            top = vi.back();
            vi.pop_back();

            if (find(vi.begin(), vi.end(), top*2) == vi.end())
            {
                vi.push_back(top*2);
            }
            if (find(vi.begin(), vi.end(), top*3) == vi.end())
            {
                vi.push_back(top*3);
            }
            if (find(vi.begin(), vi.end(), top*5) == vi.end())
            {
                vi.push_back(top*5);
            }

            make_heap(vi.begin(), vi.end(), greater<>());
        }

        return top;
    }
};

实际上效率低了，因为用原生的make_heap需要重新构造一次堆，但是用heapify这种调整堆结构会快很多。

  1. DP实现

状态转移方程： \[ dp[i] = min(2*dp[l_2], 3*dp[l_3], 5*dp[l_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
class Solution {
public:
    int nthUglyNumber(long n) {
        vector<long> dp(n+1);

        dp[1] = 1;
        long l2 = 1, l3 = 1, l5 = 1;

        for (long i = 2; i <= n; ++i)
        {
            dp[i] = min(2*dp[l2], min(3*dp[l3], 5*dp[l5]));

            if (dp[i] >= 2*dp[l2])
            {
                l2 += 1;
            }
            if (dp[i] >= 3*dp[l3])
            {
                l3 += 1;
            }
            if (dp[i] >= 5*dp[l5])
            {
                l5 += 1;
            }
        }

        return dp[n];
    }
};

Reference

powcai解

发表于 | 更新于 | 分类于

题目

最佳思路，Sieve of Eratosthenes 又或者叫 数筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int countPrimes(int n) {
    boolean[] isPrim = new boolean[n];
    Arrays.fill(isPrim, true);
    for (int i = 2; i * i < n; i++) 
        if (isPrim[i]) 
            for (int j = i * i; j < n; j += i) 
                isPrim[j] = false;
    
    int count = 0;
    for (int i = 2; i < n; i++)
        if (isPrim[i]) count++;
    
    return count;
    }
}

C++实现

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
class Solution {
    public int countPrimes(int n)
    {
        bool isPrime[n];
        memset(isPrime, true, sizeof(isPrime));
        
        for (int i = 2; i*i < n; ++i)
        {
            if(isPrime[i])
            {
                for (int j = i*i; j < n; j += i)
                {
					isPrim[j] = false;
                }
            }
		}
        
        int count = 0;
        for (int i = 2; i < n; ++i)
        {
            if (isPrime[i]) ++count;
		}
        
        return count;
	}
}

总结

  • 质数的判断上的条件优化
    • 只用判断到\(\sqrt{n}\)即可，我之前都是判断到\(n/2\)
  • 我对于数筛法的理解是：
  • 一种 记忆化搜索， 减少了重复子过程的计算。
    • 非质数 = 质数 * 质数
    • 非质数 = 非质数 * 非质数/质数

References

labuladong 解

发表于 | 更新于 | 分类于

题目

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:
    bool isUgly(int num) {

        while (num != 1)
        {
            int ori = num;
            if (num % 2 == 0)
            {
                num /= 2;
            }
            if (num % 3 == 0)
            {
                num /= 3;
            }
            if (num % 5 == 0)
            {
                num /= 5;
            }

            if (ori == num)
            {
                return false;
            }
        }

        return true;
    }
};

思路：

丑数： 因数包括 1，2， 3， 5的数。

所以考虑 非丑数 的2种情况：

  1. 除了1，2，3，5的质数
  2. 因数除了 1，2，3，5外，还有质数的非质数
  • 模2， 3，5后，这个数还是原来的值 => 非丑数
  • 模2， 3，5后，这个数为1 => 丑数
  • 模2， 3，5后，这个数为一个不为1的数，继续模2，3，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
class Solution {
public:
    int numRollsToTarget(int d, int f, int target) 
    {
        if (d < 1 || f < 1 || target < 1 || target > d*f)
        {
            return 0;
        }

        // 1.
        int MOD = 1000000007;
        // 2.
        int MIN = min(f, target);
        // 3.
        int MAX = d*f;

        vector<vector<int>> dp(d+1, vector<int>(MAX+1, 0));

        for (int j = 1; j <= MIN; ++j)
        {
            dp[1][j] = 1;
        }

        for (int i = 2; i <= d; ++i)
        {
            // 因为每个筛子至少丢出来的值是 >=1 的
            for (int j = i; j <= MAX; ++j)
            {
                for (int k = 1; j - k >= 0 && k <= f; ++k)
                {
                    dp[i][j] = (dp[i][j] + dp[i-1][j-k]) % MOD;
                }
            }
        }


        return dp[d][target];
    }

};

发表于 | 更新于 | 分类于

题目

My way

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
class Solution {
public:
    bool canCross(vector<int>& stones) {
        return helper(stones, 0, 0);
    }

    bool helper(const vector<int>& stones, int curPos, int jumpSize)
    {
        for (int nextPos = curPos+1; nextPos < stones.size(); ++nextPos)
        {
        	// gap值表示curPos位置 跳到 i位置 的跳跃距离
            int gap = stones[nextPos] - stones[curPos];
            if (gap >= jumpSize - 1 && gap <= jumpSize + 1)
            {
            	// 能跳到i位置，则递归下去
                if (helper(stones, nextPos, gap))
                {
                    return true;
                }
            }
        }

        return curPos == stones.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
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {

    bool helper(const vector<int>& stones, int curPos, int jumpSize, vector<vector<int>>& mem)
    {
        // 已有的计算结果则提前跳出
        if (mem[curPos][jumpSize] >= 0)
        {
            return mem[curPos][jumpSize];
        }

        for (int nextPos = curPos+1; i < stones.size(); ++i)
        {
            // gap值表示curPos位置 跳到 i位置 的跳跃距离
            int gap = stones[nextPos] - stones[curPos];
            if (gap >= jumpSize - 1 && gap <= jumpSize + 1)
            {
                // 能从curPos位置 跳到 i位置上，则记录为1
                if (helper(stones, nextPos, gap, mem) == 1)
                {
                    mem[nextPos][gap] = 1;
                    return 1;
                }
            }
        }
		
        // 假如能跳到最后一个位置上，则记录下，反之同理
        mem[curPos][jumpSize] = (curPos == stones.size()-1) ? 1 : 0;
        return mem[curPos][jumpSize];
    }
public:
    bool canCross(vector<int>& stones) {
        int n = stones.size();
        vector<vector<int>> mem(n, vector<int>(n, -1));

        return (helper(stones, 0, 0, mem) == 1);
    }
};

3.DP

在思考怎么通过已有的递归中的依赖关系 <=> dp的状态转移方程上去。

发现假如是使用2维DP表的话，是不可成立的，因为一个i值需要对应多个j值，所以无从下手。

官方解

1.记忆化搜索 + 二分查找

在检索位置curPos + jumpSize时候，使用二分搜索来查找位置上是否有石头

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
public class Solution {
    public boolean canCross(int[] stones) {
        int[][] memo = new int[stones.length][stones.length];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return can_Cross(stones, 0, 0, memo) == 1;
    }
    public int can_Cross(int[] stones, int ind, int jumpsize, int[][] memo) {
        if (memo[ind][jumpsize] >= 0) {
            return memo[ind][jumpsize];
        }
        int ind1 = Arrays.binarySearch(stones, ind + 1, stones.length, stones[ind] + jumpsize);
        if (ind1 >= 0 && can_Cross(stones, ind1, jumpsize, memo) == 1) {
            memo[ind][jumpsize] = 1;
            return 1;
        }
        int ind2 = Arrays.binarySearch(stones, ind + 1, stones.length, stones[ind] + jumpsize - 1);
        if (ind2 >= 0 && can_Cross(stones, ind2, jumpsize - 1, memo) == 1) {
            memo[ind][jumpsize - 1] = 1;
            return 1;
        }
        int ind3 = Arrays.binarySearch(stones, ind + 1, stones.length, stones[ind] + jumpsize + 1);
        if (ind3 >= 0 && can_Cross(stones, ind3, jumpsize + 1, memo) == 1) {
            memo[ind][jumpsize + 1] = 1;
            return 1;
        }
        memo[ind][jumpsize] = ((ind == stones.length - 1) ? 1 : 0);
        return memo[ind][jumpsize];
    }
}

2.DP

在动态规划方法中，我们会利用散列表 mapmap，对于散列表中的 key:valuekey:value，keykey 表示当前石头的位置，valuevalue 是一个包含 jumpsizejumpsize 的集合，其中每个 jumpsizejumpsize 代表可以通过大小为 jumpysizejumpysize 的一跳到达当前位置。

首先我们对散列表初始化，keykey 为所有石头的位置，除了位置 0 对应的 valuevalue 为包含一个值 0 的集合以外，其余都初始化为空集。接下来，依次遍历每个位置上的石头。对于每个 currentPositioncurrentPosition，遍历 valuevalue 中每个 jumpsizejumpsize，判断位置 currentPosition + newjumpsizecurrentPosition+newjumpsize 是否存在于 mapmap 中，对于每个 jumpsizejumpsize，newjumpsizenewjumpsize 分别为 jumpsize-1jumpsize−1，jumpsizejumpsize，jumpsize+1jumpsize+1。如果找到了，就在对应的 valuevalue 集合里新增 newjumpsizenewjumpsize。重复这个过程直到结束。如果在结束的时候，最后一个位置对应的集合非空，那也就意味着我们可以到达终点，如果还是空集那就意味着不能到达终点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public boolean canCross(int[] stones) {
        HashMap<Integer, Set<Integer>> map = new HashMap<>();
        for (int i = 0; i < stones.length; i++) {
            map.put(stones[i], new HashSet<Integer>());
        }
        map.get(0).add(0);
        for (int i = 0; i < stones.length; i++) {
            for (int k : map.get(stones[i])) {
                for (int step = k - 1; step <= k + 1; step++) {
                    if (step > 0 && map.containsKey(stones[i] + step)) {
                        map.get(stones[i] + step).add(step);
                    }
                }
            }
        }
        return map.get(stones[stones.length - 1]).size() > 0;
    }
}

总结

  • 暴力递归解总是有的，不过要找出一个靠谱的递归实现，然后可以通过其优化为 用一个数组存好结果的记忆化搜索的方式；
  • dp数组可以是 hash散列 这种存储方式，不一定是 数组 的存储方式。

Reference

官方解

发表于 | 更新于 | 分类于

题目

My way

题目有提到 大礼包以优惠的价格捆绑销售一组物品 <=> 大礼包价格更优惠，优先级更高。