leetcode-7.整数反转
如果反转后整数超过 32 位的有符号整数的范围 [−231 , 231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
int reverse ( int x) {
long res = 0 ;
int last = 0 ;
while ( x != 0 ) {
res = res * 10 + x % 10 ;
x = x / 10 ;
}
return ( int ) res == res ? ( int ) res : 0 ;
}
leetcode-29.两数相除
返回被除数 dividend 除以除数 divisor 得到的商。
整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
int divide ( int dividend, int divisor) {
if ( dividend == 0 )
return 0 ;
if ( divisor == 1 )
return dividend;
if ( dividend == INT_MIN && divisor == - 1 )
return INT_MAX;
int sign = ( dividend < 0 ) ^ ( divisor < 0 ) == 0 ? 1 : - 1 ;
long m = labs ( dividend) ;
long n = labs ( divisor) ;
long p = 1 ;
long t = 0 ;
long res = 0 ;
while ( m >= n) {
t = n;
p = 1 ;
while ( m >= ( t<< 1 ) ) { // 找最大倍数
t = t<< 1 ;
p = p<< 1 ;
}
m = m - t;
res = res + p;
}
return sign == 1 ? res : - res;
}
时间复杂度 ：O(logn)，与两个操作数的相对大小有关，时间复杂度的级别为 O(logn)，不是严格的二分。空间复杂度 ：O(1)。
leetcode-62.不同路径（动态规划）
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
int uniquePaths ( int m, int n) {
int f[ m] [ n] ;
for ( int i = 0 ; i < m; i++ ) {
f[ i] [ 0 ] = 1 ;
}
for ( int j = 0 ; j < n; j++ ) {
f[ 0 ] [ j] = 1 ;
}
for ( int i = 1 ; i < m; i++ ) {
for ( int j = 1 ; j < n; j++ ) {
f[ i] [ j] = f[ i - 1 ] [ j] + f[ i] [ j - 1 ] ;
}
}
return f[ m - 1 ] [ n - 1 ] ;
}
时间复杂度 ：O(mn)。空间复杂度 ：O(mn)。
用组合数学做的时间复杂度和空间复杂度好像更好一点，这里先放着吧。
leetcode-96.不同的二叉搜索树（卡特兰数） 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
int numTrees ( int n) {
long long c = 1 ;
for ( int i = 0 ; i < n; i++ ) {
c = 2 * c * ( 2 * i + 1 ) / ( i + 2 ) ;
}
return ( int ) c;
}
时间复杂度 ：O(n)，其中 n 表示二叉搜索树的节点个数。我们只需要循环遍历一次即可。空间复杂度 ：O(1)。我们只需要常数空间存放若干变量。
leetcode-118.杨辉三角
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
int * * generate ( int numRows, int * returnSize, int * * returnColumnSizes) {
int * * ret = malloc ( sizeof ( int * ) * numRows) ;
* returnSize = numRows;
* returnColumnSizes = malloc ( sizeof ( int ) * numRows) ;
for ( int i = 0 ; i < numRows; i++ ) {
ret[ i] = malloc ( sizeof ( int ) * ( i + 1 ) ) ;
( * returnColumnSizes) [ i] = i + 1 ;
ret[ i] [ 0 ] = ret[ i] [ i] = 1 ;
for ( int j = 1 ; j < i; j++ ) {
ret[ i] [ j] = ret[ i - 1 ] [ j] + ret[ i - 1 ] [ j - 1 ] ;
}
}
return ret;
}
时间复杂度 ：O(numRows2 )。空间复杂度 ：O(1)。不考虑返回值的空间占用。
leetcode-119.杨辉三角 II
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
int * getRow ( int rowIndex, int * returnSize) {
* returnSize = rowIndex + 1 ;
int * row = malloc ( sizeof ( int ) * ( * returnSize) ) ;
row[ 0 ] = 1 ;
for ( int i = 1 ; i <= rowIndex; i++ ) {
row[ i] = 1LL * row[ i - 1 ] * ( rowIndex - i + 1 ) / i;
}
return row;
}
时间复杂度 ：O(rowIndex)。空间复杂度 ：O(1)O(1)。不考虑返回值的空间占用。
leetcode-121.买卖股票的最佳时机
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
int maxProfit ( int * prices, int pricesSize) {
int minPrcie = INT_MAX, maxPro = 0 ;
for ( int i = 0 ; i < pricesSize; i++ ) {
maxPro = fmax ( maxPro, prices[ i] - minPrcie) ;
minPrcie = fmin ( minPrcie, prices[ i] ) ;
}
return maxPro;
}
时间复杂度 ：O(n)，只需要遍历一次。空间复杂度 ：O(1)，只使用了常数个变量。
leetcode-122. 买卖股票的最佳时机 II
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
int maxProfit ( int * prices, int pricesSize) {
int ans = 0 ;
for ( int i = 0 ; i < pricesSize - 1 ; i++ ) {
ans += fmax ( 0 , prices[ i + 1 ] - prices[ i] ) ;
}
return ans;
}
时间复杂度 ：O(n)，其中 n 为数组的长度。我们只需要遍历一次数组即可。空间复杂度 ：O(1)。只需要常数空间存放若干变量。
leetcode-136.只出现一次的数字 非空 整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明 ：
// 位运算
int singleNumber ( int * nums, int numsSize) {
int ans = 0 ;
for ( int i = 0 ; i < numsSize; i++ ) {
ans ^= nums[ i] ;
}
return ans;
}
时间复杂度 ：O(n)，其中 n 是数组长度。只需要对数组遍历一次。空间复杂度 ：O(1)。
leetcode-201.数字范围按位与 按位与 的结果（包含 left 、right 端点）。
int rangeBitwiseAnd ( int left, int right) {
int shift = 0 ;
// 找到公共前缀
while ( left < right) {
left = left >> 1 ;
right = right >> 1 ;
shift += 1 ;
}
return left << shift;
}
时间复杂度 ：O(logn)。算法的时间复杂度取决于 m 和 n 的二进制位数，由于 m ≤ n，因此时间复杂度取决于 n 的二进制位数。空间复杂度 ：O(1)。我们只需要常数空间存放若干变量。
leetcode-258.各位相加
int addDigits ( int num) {
return ( num - 1 ) % 9 + 1 ;
}
时间复杂度 ：O(1)。空间复杂度 ：O(1)。
leetcode-260.只出现一次的数字 III 任意顺序 返回答案。
你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
int * singleNumber ( int * nums, int numsSize, int * returnSize) {
int xorsum = 0 ;
for ( int i = 0 ; i < numsSize; i++ ) {
xorsum ^= nums[ i] ;
}
// 防止溢出
int lsb = ( xorsum == INT_MIN ? xorsum : xorsum & ( - xorsum) ) ;
int type1 = 0 , type2 = 0 ;
for ( int i = 0 ; i < numsSize; i++ ) {
if ( nums[ i] & lsb) {
type1 ^= nums[ i] ;
}
else {
type2 ^= nums[ i] ;
}
}
int * answer = ( int * ) malloc ( sizeof ( int ) * 2 ) ;
answer[ 0 ] = type1;
answer[ 1 ] = type2;
* returnSize = 2 ;
return answer;
}
时间复杂度 ：O(n)，其中 n 是数组 nums 的长度。空间复杂度 ：O(1)。
leetcode-263.丑数 丑数 就是只包含质因数 2、3 和 5 的正整数。
给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。
bool isUgly ( int n) {
if ( n <= 0 )
return false;
int factors[ ] = { 2 , 3 , 5 } ;
for ( int i = 0 ; i < 3 ; i++ ) {
while ( n % factors[ i] == 0 ) {
n /= factors[ i] ;
}
}
return n == 1 ;
}
时间复杂度 ：O(logn)。时间复杂度取决于对 n 除以 2,3,5 的次数，由于每次至少将 n 除以 2，因此除法运算的次数不会超过 O(logn)。空间复杂度 ：O(1)。
leetcode-268.丢失的数字
int missingNumber ( int * nums, int numsSize) {
int xor = 0 ;
for ( int i = 0 ; i < numsSize; i++ ) {
xor ^= nums[ i] ;
}
for ( int i = 0 ; i <= numsSize; i++ ) {
xor ^= i;
}
return xor;
}
时间复杂度 ：O(n)，其中 n 是数组 nums 的长度。需要对 2n+1 个数字计算按位异或的结果。空间复杂度 ：O(1)。
leetcode-279.完全平方数（动态规划）
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
int numSquares ( int n) {
int f[ n + 1 ] ;
f[ 0 ] = 0 ;
for ( int i = 1 ; i <= n; i++ ) {
int mn = INT_MAX;
for ( int j = 1 ; j * j <= i; j++ ) {
mn = fmin ( mn, f[ i - j * j] ) ;
}
f[ i] = mn + 1 ;
}
return f[ n] ;
}
时间复杂度 ：
O
(
n
n
)
O(n\sqrt{n})
O ( n n
)
O
(
n
)
O(\sqrt{n})
O ( n
)
O
(
n
n
)
O(n\sqrt{n})
O ( n n
) 空间复杂度 ：O(n)。我们需要 O(n) 的空间保存状态。
leetcode-292.Nim 游戏
桌子上有一堆石头。
你们轮流进行自己的回合， 你作为先手 。
每一回合，轮到的人拿掉 1 - 3 块石头。
拿掉最后一块石头的人就是获胜者。
假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。
bool canWinNim ( int n) {
return n % 4 != 0 ;
}
时间复杂度 ：O(1)。空间复杂度 ：O(1)。
leetcode-326.3 的幂
整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3x
bool isPowerOfThree ( int n) {
while ( n && n % 3 == 0 ) {
n /= 3 ;
}
return n == 1 ;
}
时间复杂度 ：O(logn)。当 n 是 3 的幂时，需要除以 3 的次数为 log3 n = O(logn)；当 n 不是 3 的幂时，需要除以 3 的次数小于该值。空间复杂度 ：O(1)。
给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。
整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x
bool isPowerOfFour ( int n) {
return n > 0 && ( n & ( n - 1 ) ) == 0 && n % 3 == 1 ;
}
时间复杂度 ：O(1)。空间复杂度 ：O(1)。
leetcode-367.有效的完全平方数 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
进阶 ：不要 使用任何内置的库函数，如 sqrt 。
bool isPerfectSquare ( int num) {
int left = 0 , right = num;
while ( left <= right) {
int mid = left + ( 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;
}
时间复杂度 ：O(logn)，其中 n 为正整数 num 的最大值。空间复杂度 ：O(1)。
leetcode-374.猜数字大小
每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：
-1：我选出的数字比你猜的数字小 pick < num
1：我选出的数字比你猜的数字大 pick > num
0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num
返回我选出的数字。
int guessNumber ( int n) {
int left = 1 , right = n;
while ( left < right) {
int mid = left + ( right - left) / 2 ;
if ( guess ( mid) <= 0 ) {
right = mid;
}
else {
left = mid + 1 ;
}
}
return left;
}
时间复杂度 ：O(logn)。时间复杂度即为二分的次数，每次二分我们将区间的长度减小一半，直至区间长度为 1 时二分终止，而区间初始长度为 n，因此二分次数为 O(logn)。空间复杂度 ：O(1)。
