[leetcode] 题型整理之数字加减乘除乘方开根号组合数计算取余

需要注意overflow,特别是Integer.MIN_VALUE这个数字。

需要掌握二分法。

不用除法的除法,分而治之的乘方

2. Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

基本等于合并数组,记得要最后加上carry位。

不需要考虑overflow,但是记得当输入两个空链表的时候输出0而不是空链表。

29. Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

不能使用除法的除法,让除数不停地乘以二直到会大于被除数为止。

核心代码如下:

while (x >= y) {
int a = 0;
while (x >= (y << a)) {
a++;
}
a--;
result += (long)1 << a;
x -= y << a;
}

其中,x是被除数,y是除数,这段代码里,还需注意x,y都是long。1要被强制转换为long

这道题有很多corner case,具体见

[leetcode] 29. divide two integers

43. Multiply Strings

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note:

  • The numbers can be arbitrarily large and are non-negative.
  • Converting the input string to integer is NOT allowed.
  • You should NOT use internal library such as BigInteger.
  • 按照我目前的解法没有什么corner case需要考虑,只要把输出数字前面多余的0去掉就可以了。但是现在的解法比较慢。有空的时候再改进吧。

50. Pow(x, n)

Implement pow(xn).

1. 0的0次方是1

2. 判断x是否为0,n是否为0,x是否是1

3. 判断x的正负性,判断n的正负性。

4. 注意n是Integer.MIN_VALUE的情况,这种情况下取绝对值的时候会overflow

BTW,Double.MIN_VALUE定义的是大于0的最小正数哦~

leetcode的testcase没有涉及到double overflow的情况,double overflow的时候直接返回MAX_VALUE了?

69. Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

用二分法做,因为测试 mid * mid 时得到的结果可能超过int的范围,所以,这一步需要用long来做。

int相乘overflow的时候,得到的结果有可能是一个正整数,无法判别overflow(得到的结果甚至可能大于mid真的无法判别啊)。

62. Unique Paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

[leetcode] 题型整理之数字加减乘除乘方开根号组合数计算取余

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

这道题其实是求组合数。Cm-1m+n-1

注意由于起点和终点一个在1一个在m,所以两者之间需要的步数是m - 1而不是m。

372. Super Pow

Your task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.

Example1:

a = 2
b = [3] Result: 8

Example2:

a = 2
b = [1,0] Result: 1024

Credits:
Special thanks to @Stomach_ache for adding this problem and creating all test cases.

public class Solution {
private static final int N = 1337;
public int superPow(int a, int[] b) {
int size = b.length;
int result = 1;
for (int i = 0; i < size; i++) {
result = helper(result, 10) * helper (a, b[i]) % N;
}
return result;
}
private int helper(int a, int b) {
if (b == 0) {
return 1;
} else if (b == 1) {
return a % N;
}
return helper (a, b / 2) * helper(a, b - b / 2) % N;
}
}
上一篇:没有找到cxcore100.dll,因此这个应用程序未能启动,重新安装应用程序可能会修复此问题


下一篇:神奇的 CURL 命令