第二天——论循环是怎么被玩huai的~
一、今日知识点总结
一、循环语法重拾：
for(循环初始化表达式; 循环条件表达式; 循环执行表达式)
{
循环体
}
二、运作过程的重新认识
以前曾经傻傻的认为for循环是先执行括号里中三个表达式，然后再执行循环体部分的内容。emmmm，太呆萌了…
对于常用的for循环，它的运作过程为：
1、执行 循环初始化表达式
2、执行循环条件表达式。如果表达式的值为真，则执行循环体，否则结束放弃循环
3、执行完循环体之后，再执行循环执行表达式。也就是对循环变量进行更新。
4、重复上面的步骤2和步骤3，知道控制循环结束与否的循环表达式判断出来，结果为假，那么结束循环。
三、碎碎念
感觉循环是真的挺重要的，但是我很容易忽视它，就像我现在正在准备的暴力杯一样，很多前辈都说会for就好，但是呢，我感觉，我可能是不会for吧…
二、今日做题记录
第一题：剑指 Offer 64. 求1+2+…+n
题目描述
剑指 Offer 64. 求1+2+…+n
求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
示例 1：
输入: n = 3
输出: 6
示例 2：
输入: n = 9
输出: 45
限制：
1 <= n <= 10000
解题报告
题目中说的是不然使用循环和乘法，学数据结构的树这一章的时候，很多小伙伴应该都写过把递归改非递归的习题，那么，我们现在把非递归的循环改为递归。
递归唯一需要注意的是设置递归的边界，对于这个题而言，递归的边界就是进行递归累加的数，是否为0
参考代码(C++)
class Solution {
public:
int sumNums(int n) {
n && (n += sumNums(n-1));
return n;
}
};
第二题：231. 2 的幂
题目描述
231. 2 的幂
给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。
示例 1：
输入：n = 1
输出：true
解释：20 = 1
示例 2：
输入：n = 16
输出：true
解释：24 = 16
示例 3：
输入：n = 3
输出：false
示例 4：
输入：n = 4
输出：true
示例 5：
输入：n = 5
输出：false
提示：
-231 <= n <= 231 - 1
进阶：你能够不使用循环/递归解决此问题吗？
解题报告
这个题倒是常规的可爱枚举了，只是需要注意的是要使用unsigned来处理整数溢出的情况
参考代码(C++版本)
class Solution {
public:
bool isPowerOfTwo(int n) {
//处理特殊情况
if(n <= 0) return false;
if(n == 1) return true;//2的零次方
//用无符号类型处理溢出情况
unsigned int ans = 1;
//常规的枚举,注意整数的边界是2的31-1
for(int i = 1; i <= 31;i++)
{
ans *= 2;
if(ans == n) return true;
}
return false;
}
};
第三题：326. 3 的幂
题目描述
326. 3 的幂
给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。
整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3x
示例 1：
输入：n = 27
输出：true
示例 2：
输入：n = 0
输出：false
示例 3：
输入：n = 9
输出：true
示例 4：
输入：n = 45
输出：false
提示：
-231 <= n <= 231 - 1
进阶：你能不使用循环或者递归来完成本题吗？
解题报告
这个题和上面的例题就没有什么大的区别了，只是要换成3去不断的乘，同时注意边界，算了一下，应该只能枚举到20；
参考代码(C++版本)
class Solution {
public:
bool isPowerOfThree(int n) {
//处理特殊情况
if(n <= 0) return false;
if(n == 1) return true;//3的零次方
//用无符号类型处理溢出情况
unsigned int ans = 1;
//常规的枚举,注意3的21次方大概就超了
for(int i = 1; i <= 20;i++)
{
ans *= 3;
if(ans == n) return true;
}
return false;
}
};
第四题：342. 4的幂
题目描述
342. 4的幂
给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。
整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x
示例 1：
输入：n = 16
输出：true
示例 2：
输入：n = 5
输出：false
示例 3：
输入：n = 1
输出：true
提示：
-231 <= n <= 231 - 1
解题报告
一样的，换汤不换药，注意边界，此时只能到15啦
参考代码(C++版本)
class Solution {
public:
bool isPowerOfFour(int n) {
//处理特殊情况
if(n <= 0) return false;
if(n == 1) return true;//4的零次方
//用无符号类型处理溢出情况
unsigned int ans = 1;
//常规的枚举,注意4的15次方大概就超了
for(int i = 1; i <= 15;i++)
{
ans *= 4;
if(ans == n) return true;
}
return false;
}
};
第五题：1492. n 的第 k 个因子
题目描述
1492. n 的第 k 个因子
给你两个正整数 n 和 k 。
如果正整数 i 满足 n % i == 0 ，那么我们就说正整数 i 是整数 n 的因子。
考虑整数 n 的所有因子，将它们 升序排列 。请你返回第 k 个因子。如果 n 的因子数少于 k ，请你返回 -1 。
示例 1：
输入：n = 12, k = 3
输出：3
解释：因子列表包括 [1, 2, 3, 4, 6, 12]，第 3 个因子是 3 。
示例 2：
输入：n = 7, k = 2
输出：7
解释：因子列表包括 [1, 7] ，第 2 个因子是 7 。
示例 3：
输入：n = 4, k = 4
输出：-1
解释：因子列表包括 [1, 2, 4] ，只有 3 个因子，所以我们应该返回 -1 。
示例 4：
输入：n = 1, k = 1
输出：1
解释：因子列表包括 [1] ，第 1 个因子为 1 。
示例 5：
输入：n = 1000, k = 3
输出：4
解释：因子列表包括 [1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 125, 200, 250, 500, 1000] 。
提示：
1 <= k <= n <= 1000
解题报告
常规枚举，我没有get到这个题的考点，可恶，菜到都不知道人家的题目考什么了😭
参考代码(C++版本)
class Solution {
public:
int kthFactor(int n, int k) {
//升序排列倒是不必太在意，从小到大枚举就好
//直接枚举吧
int cnt = 0;//计数器
for(int i = 1; i <= n;i++)
{
if(n % i == 0)
{
cnt++;
if(cnt == k) return i;
}
}
return -1;
}
};
第六题：279. 完全平方数
题目描述
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 <= 104
解题报告
这个题是一个完全背包。
完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品。
那就直接拿出我可爱的闫式DP分析法吧。
完全背包的背景是如下分析的：
对于这个题而言，只是需要重新定义一下集合 :
f[i]表示和为i的完全平方数的最少数量
参考代码(C++版本)
class Solution {
public:
int numSquares(int n) {
int f[n+1];
//让结果初始化为正无穷
memset(f,0x3f,sizeof f);
//初始化
f[0] = 0;
//开始DP
for(int i = 1; i <= n;i++)
//因为第一维的i是直接可以去的，所以上的优化为一维的完全背包递推公式
for(int j = 1; j *j <= i;j++) f[i] = min(f[i-j*j]+1,f[i]);
//输出结果
return f[n];
}
};
三、今日收获
一、对整数溢出的处理
之前在其他平台做题，也可能是自己做得少，但是通过这两天的Lc写题以后，感觉它考察了很多关于溢出的问题。
二、递归和循环的灵活转换
四、今日疑问
最后一题是动态规划中的背包问题，以为自己之前整理过，会能很快Ac，结果大意了，看以前写的文章，真的糟糕…正在重新整理动态规划~