实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。思路1：最简单的方法就是把n个x相乘，考虑n=0和n<0的情况，n=0，结果为1，n<0,结果为1/x-n。这个思路的时间复杂度为O(n),空间复杂度为O(1)。代码：class Solution { public: double myPow(double x, int n) { if(x == 0) return 0; if(n == 0) return 1; if(n < 0) { return 1 / myPow(x,-n); } double result = 1; for(int i = 1;i <=n;i++) { result *= x; } return result; } };思路2:考虑公式：an = an/2 * an/2 (n是偶数),an

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为 汉明重量).）。思路1:按位枚举因为无符号整数有32位，从右到左按位统计1的个数。代码：class Solution { public: int hammingWeight(uint32_t n) { int ans = 0; for(int i = 0;i < 32;i++) { if(n&(1 << i)) { ans++; } } return ans; } };思路2:二进制规律记a = 1,则a&(a-1) = 0,a = 1110则a - 1 = 1101,a&(a-1)= 1100, 一个数a和它的减一做与运算，结果把a最后一个1消掉了。重复这个过程，可以统计出1的个数。代码class Solution { public: int hammingWeight(uint3

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。思路1：动态规划记dp[n]表示长度为n的绳子剪完之后得到的最大乘积，则dp[n] = max(i*dp[n-i]),0<i<n。当n=2时，最大乘积为1,因为剪为两段长度为1的绳子。当n=3时，最大乘积为2，剪为一段为1，一段为2的绳子。但是dp[2]不能等于1，dp[3]不能等于2。因为计算的过程中dp[2]和dp[3]都是作为一个乘积因子出现的，即dp[2]和dp[3]都是和其他长度相乘的，不需要再剪了。所以dp[2] = 2,dp[3] = 3。代码：class Solution { public: int cuttingRope(int n) { if(n <= 0) return 0; if(

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？示例 1：输入：m = 2, n = 3, k = 1输出：3示例 2：输入：m = 3, n = 1, k = 0输出：1提示：1 <= n,m <= 1000 <= k <= 20思路一：dfs,深度优先遍历每一个格子，如果当前格子满足条件，则计数加1。运动的过程中，可以只考虑向下和向右，因为向上的格子，要么被向下方向走过，要么会被向右方向走过。向右同理。所以只需要考虑向下和向右。代码class Solution { private: int ans = 0; vector<vector<int>> visited;

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。思路：遍历二维字符网格，以当前位置(i,j)为起点，判断board[i][j]与word[index]（index从i,j起点开始为0，后面一次加1）是否相等，如果不等，则查看下个位置。如果相等以(i,j)为中心向四周四个位置扩散，(i+1,j)、（i-1,j）、(i,j+1)、（i,j-1）与index+1位置的word字符是否相等，如果相等，则继续进行下一轮比较。递归。代码：class Solution { private: vector<vector<bool>> visited; public: bool hasWord(vector<vector<char>>& board,int row,int col , str