第九日集训：循环结构与递归算法

知识点概览

本节主要介绍了C++中循环控制结构的使用，特别是for循环：

for (初始化表达式; 条件表达式; 更新表达式) {
    循环体
}

题目解析

题目一：剑指 Offer 64 - 不用加减乘除运算求和

题目要求在不使用循环和条件语句的情况下计算1+2+...+n。解决方案采用了递归的方法，通过函数自身调用来实现累加功能。

class Solution {
public:
    int sumNums(int n) {
        return n == 1 ? 1 : n + sumNums(n - 1);
    }
};

为了满足题目要求，还可以利用逻辑运算符&&的短路特性来避免显式的条件判断：

class Solution {
public:
    int sumNums(int n) {
        bool dummy = (n > 1) && (n += sumNums(n - 1));
        return n;
    }
};

题目二：231. 判断2的幂

此题的关键在于理解2的幂次方在二进制表示下的特点，即除了最高位为1外，其余位均为0。因此，可以通过检查n & (n - 1) == 0来判断一个数是否为2的幂，同时需要注意处理n=0的情况。

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
};

题目三：326. 判断3的幂

对于3的幂，可以利用对数变换将问题转化为判断对数结果是否为整数。具体来说，如果n=3^x，则log(n)/log(3)应为整数。需要注意的是，由于浮点数运算可能存在误差，需要设置一个小阈值来判断结果是否接近整数。

class Solution {
public:
    bool isPowerOfThree(int n) {
        if (n <= 0) return false;
        double logResult = log(n) / log(3);
        return fabs(logResult - round(logResult)) <1e-10;
    }
};

题目四：342. 判断4的幂

4的幂同样可以通过对数变换来解决，但还需要额外判断该数是否为2的幂以及是否为完全平方数。

class Solution {
public:
    bool isPowerOfFour(int n) {
        if (n <= 0) return false;
        int root = sqrt(n);
        return root * root == n && (n & (n - 1)) == 0;
    }
};

题目五：1492. 寻找第k个因子

此题要求找到给定整数n的第k个正因子。可以通过遍历1至n的所有整数，统计每个数是否为n的因子，并在计数达到k时返回当前数。

class Solution {
public:
    int kthFactor(int n, int k) {
        int count = 0;
        for (int i = 1; i <= n; ++i) {
            if (n % i == 0) {
                if (++count == k) return i;
            }
        }
        return -1;
    }
};

题目六：367. 判断有效完全平方数

此题可通过二分查找法高效解决。基本思想是在1至num之间进行搜索，寻找是否存在某个数的平方等于num。

class Solution {
public:
    bool isPerfectSquare(int num) {
        if (num == 1) return true;
        int left = 1, right = num;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (mid == num / mid && num % mid == 0) return true;
            else if (mid             else right = mid - 1;
        }
        return false;
    }
};

总结

今天的练习涵盖了循环结构和递归的基本应用，涉及了数学运算、逻辑判断等多个方面。通过这些练习，不仅加深了对循环和递归的理解，也提高了解决实际问题的能力。