分享程序员开发的那些事...
更新时间：2022-10-02 20:59:54
求n的连加之和，有以下思路
int sum = 0; int i = 1; for(i = 1;i <= n;i++) sum += i; return sum;
使用for循环完成连加操作
int sumNums(int n){ return (1 + n) * n / 2; }
使用前n项和的求和公式 n * (n + 1) / 2;
以逻辑运算符&&为例，对于 A && B这个表达式，如果A的返回值为 False ,此时不会去执行表达式B。
利用这个特性，我们可以将判断是否为递归的出口看做 A && B 中的 A 部分，递归的主体函数看成是 B 部分。如果不是递归出口，则返回 True ，并继续执行表达式的 B部分，否则递归结束。
int sumNums(int n){ n && (n += sumNums(n - 1)); return n; }
考虑 A 和 B 两数相乘的时候我们将利用加法和位运算来模拟，其实就是将 B 二进制展开，如果 B 的二进制下表示第 i 位为 1，那这一位对最后结果的贡献就是 A * ( 1 << i) ,即 A << i
我们遍历 B 二进制下展开的每一位，将所以贡献累加起来就是 最后的答案，这个方法也被称为 【俄罗斯农民乘法】。经常被用于两数相乘取模的场景，感兴趣的读者可以自行去了解一下。
相关代码实现：
int quickMulti(int A ,int B) { int ans = 0; for(; B ;B >> 1) { if(B & 1) ans += A; A << 1; } return ans; }
我们可以利用这个方法来拆位取模计算，保证每次运算都在数据范围内。
由数列求和公式我们可知 ： （n + 1） * n / 2
等价于 n (n + 1) >> 1
我们可以将两个数相乘用加法和位运算来实现，但是还是需要循环语句，由于题目所给的范围是【1 ， 10000】，即二进制展开不会超过14位，所以我们可以自己手动展开 。
class Solution { public: int sumNums(int n) { int ans = 0, A = n, B = n + 1; (B & 1) && (ans += A); A <<= 1; B >>= 1; (B & 1) && (ans += A); A <<= 1; B >>= 1; (B & 1) && (ans += A); A <<= 1; B >>= 1; (B & 1) && (ans += A); A <<= 1; B >>= 1; (B & 1) && (ans += A); A <<= 1; B >>= 1; (B & 1) && (ans += A); A <<= 1; B >>= 1; (B & 1) && (ans += A); A <<= 1; B >>= 1; (B & 1) && (ans += A); A <<= 1; B >>= 1; (B & 1) && (ans += A); A <<= 1; B >>= 1; (B & 1) && (ans += A); A <<= 1; B >>= 1; (B & 1) && (ans += A); A <<= 1; B >>= 1; (B & 1) && (ans += A); A <<= 1; B >>= 1; (B & 1) && (ans += A); A <<= 1; B >>= 1; (B & 1) && (ans += A); A <<= 1; B >>= 1; return ans >> 1; } };
使用for循环进行判断
bool isPowerOfTwo(int n){ int i; unsigned int k = 1; if(n < 0) return false; if(n == 1) return true; for(i = 1;i <= 31;i++) { k *= 2; if(k == n) return true; } return false; }
bool isPowerOfTwo(int n){ if(n == 0) return false; int x = (int)(log2(n) / log2(2) + 1e-8); return fabs(n - pow(2,x)) < 1e-8; }
将原式进行对数运算，得到如上结果，进行浮点数判断
一个数n是2的幂，当且仅当n是正整数，并且n的二进制表示中仅含一个1
我们可以考虑使用位运算，将n的二进制中表示最低位的那个1提取出来，再判断剩下的数是否为0即可
（1），n & （n - 1）== 0
（2），n & ( -n ) == n
bool isPowerOfTwo(int n){ return n > 0 && (n & (n - 1)) == 0; }
类比上面的二次幂，可以使用穷举法
对原式进行数学运算，然后进行浮点数精度判断
bool isPowerOfThree(int n){ if(n == 0) return false; int x = (int)(log(n) / log(3) + 1e-8); return fabs(n - pow(3,x)) < 1e-8; }
如果一个数是4的幂，也一定是2的幂
int kthFactor(int n, int k){ int i = 0; for(i = 1;i <= n;i++) { if(n % i == 0) k--; if(k == 0) return i; } return -1; }
#include <math.h> bool isPerfectSquare(int num){ if(sqrt(num) == (int)sqrt(num)) return true; return false; }
bool isPerfectSquare(int num){ long x = 1,square = 1; while(square <= num) { if(square == num) return true; ++x; square = x * x; } return false; }
考虑使用二分查找来优化搜索过程。因为num是正整数，所以若 x * x = num ,则 x 一定满足
1 《 x 《 num。所以我们将1 和 num 作为 二分查找搜索区间的初始边界。
因为我们在移动左侧边界left和右侧边界right时，新的搜索区间的边界始终是我们没有搜索过的，所以当 left == right 时，我们还需要检查 mid = （right + left ） / 2
bool isPerfectSquare(int num){ int left = 0,right = num; while(left <= right) { int mid = (right + left) / 2; long square = (long) mid * mid; if(square < num) { left = mid + 1; } else if(square > num) { right = mid - 1; } else return true; } return false; }