据华为数据存储公众号发布,华为公布了2024年奥林帕斯难题悬红。“奥林帕斯奖”(OlympusMons Awards)由华为公司于2019年起设立,奖金100万人民币/个。
![](http://dingyue.ws.126.net/2024/0606/e739a9d7p00senc0u000gd200bc0038g00bc0038.png)
华为2024年发布了两个问题,一是每比特极致性价比的存储技术,二是面向AI时代的新型数据底座。两个加起来就是200万,有兴趣的可以挑战一下,机会留给你们,我就不参与了。
![](http://dingyue.ws.126.net/2024/0606/8a959383j00senc0v001hd200gm008pg00gm008p.jpg)
--------------下面是今天的算法题--------------
来看下今天的算法题,这题是LeetCode的第279:完全平方数。
问题描述
来源:LeetCode第279题
难度:中等
给你一个整数 n ,返回和为 n 的完全平方数的最少数量 。完全平方数是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。
示例1:
输入:n = 12 输出:3 解释:12 = 4 + 4 + 4
示例2:
输入:n = 13 输出:2 解释:13 = 4 + 9
1 <= n <= 10^4
问题分析
这题让使用最少的完全平方数,让他们的和等于 n 。我们来把这题转换一下。
给你一个数组nums=[1,2……,sqrt(n)],从数组中选择任意数字让他们平方的和等于 n ,问所需要的最少数字是多少,并且每个数字没有次数限制。转换 之后我们发现它就是一个完全背包问题。
关于完全背包问题以及代码优化在 中有过详细介绍。不过背包问题求的是最大值,而这里求的是最小值,我们默认每一个数字都给一个最大值,最大值就是全部由 1 的平方组成,代码如下。
JAVA:
// 在nums=[1,2.....sqrt(n)]中选任意数平方和为n的数字
public int numSquares(int n) {
int sqrt = (int) Math.sqrt(n);
int[] dp = new int[n + 1];
Arrays.fill(dp, n);//dp[i]:和为i的完全平方数的最小数量
dp[0] = 0;
for (int i = 1; i <= sqrt; i++) {// 物品
for (int j = 1; j <= n; j++) {// 背包容量
if (j >= i * i)// 选当前数字和不选当前数字,取最小值
dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
}
}
return dp[n];
}
C++:
// 在nums=[1,2.....sqrt(n)]中选任意数平方和为n的数字
public:
int numSquares(int n) {
int sqrtN = (int) sqrt(n);
vector
dp(n + 1, n);//dp[i]:和为i的完全平方数的最小数量 dp[0] = 0; for (int i = 1; i <= sqrtN; i++) {// 物品 for (int j = 1; j <= n; j++) {// 背包容量 if (j >= i * i)// 选当前数字和不选当前数字,取最小值 dp[j] = min(dp[j], dp[j - i * i] + 1); } } return dp[n]; }
C:
// 在nums=[1,2.....sqrt(n)]中选任意数平方和为n的数字
int numSquares(int n) {
int sqrtN = (int) sqrt(n);
int dp[n + 1];
for (int i = 0; i <= n; i++)
dp[i] = n; // dp[i]:和为i的完全平方数的最小数量
dp[0] = 0;
for (int i = 1; i <= sqrtN; i++) {// 物品
for (int j = 1; j <= n; j++) {// 背包容量
if (j >= i * i)// 选当前数字和不选当前数字,取最小值
dp[j] = fmin(dp[j], dp[j - i * i] + 1);
}
}
return dp[n];
}
Python:
# 在nums=[1,2.....sqrt(n)]中选任意数平方和为n的数字
def numSquares(self, n: int) -> int:
sqrt = int(math.sqrt(n))
dp = [n] * (n + 1) # dp[i]:和为i的完全平方数的最小数量
dp[0] = 0
for i in range(1, sqrt + 1): # 物品
for j in range(1, n + 1): # 背包容量
if j >= i * i: # 选当前数字和不选当前数字,取最小值
dp[j] = min(dp[j], dp[j - i * i] + 1)
return dp[n]
笔者简介
博哥,真名:王一博,毕业十多年, 作者,专注于 数据结构和算法 的讲解,在全球30多个算法网站中累计做题2000多道,在公众号中写算法题解800多题,对算法题有自己独特的解题思路和解题技巧,喜欢的可以给个关注,也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴