@Yano 2015-12-30T03:24:05.000000Z 字数 20897 阅读 6600

# LeetCode之Math题目汇总

LeetCode

LeetCode 题目汇总

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

1. public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
2. if (l1 == null && l2 == null) {
3. return null;
4. }
5. if (l1 == null) {
6. return l2;
7. }
8. if (l2 == null) {
9. return l1;
10. }
11. ListNode p1 = l1;
12. ListNode p2 = l2;
13. int carry = 0;
14. ListNode head = new ListNode(0);
16. while (carry != 0 || p1 != null || p2 != null) {
17. int v1 = 0;
18. if (p1 != null) {
19. v1 = p1.val;
20. p1 = p1.next;
21. }
22. int v2 = 0;
23. if (p2 != null) {
24. v2 = p2.val;
25. p2 = p2.next;
26. }
27. int tmp = v1 + v2 + carry;
28. carry = tmp / 10;
29. head.next = new ListNode(tmp % 10);
31. }
32. return result.next;
33. }

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 111 + 1 = 2. Since 2 has only one digit, return it.

Could you do it without any loop/recursion in O(1) runtime?

Hint:

1. A naive implementation of the above process is trivial. Could you come up with other methods?
2. What are all the possible results?
3. How do they occur, periodically or randomly?
4. You may find this Wikipedia article useful.

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

1. public int addDigits(int num) {
2. return 1 + (num - 1) % 9;
3. }

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

1. public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
2. if (l1 == null && l2 == null) {
3. return null;
4. }
5. if (l1 == null) {
6. return l2;
7. }
8. if (l2 == null) {
9. return l1;
10. }
11. ListNode p1 = l1;
12. ListNode p2 = l2;
13. int carry = 0;
14. ListNode head = new ListNode(0);
16. while (carry != 0 || p1 != null || p2 != null) {
17. int v1 = 0;
18. if (p1 != null) {
19. v1 = p1.val;
20. p1 = p1.next;
21. }
22. int v2 = 0;
23. if (p2 != null) {
24. v2 = p2.val;
25. p2 = p2.next;
26. }
27. int tmp = v1 + v2 + carry;
28. carry = tmp / 10;
29. head.next = new ListNode(tmp % 10);
31. }
32. return result.next;
33. }

# Basic Calculator

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

Note: Do not use the eval built-in library function.

1. 如果是数字，则一直遍历到非数字字符，把数字找出，并与结果相加
2. 如果是+-符号，将sign设置成对应的值
3. 如果是(，将rt和sign压入栈中，重置rt和sign
4. 如果是)，将sign和rt弹出栈，并计算结果
1. public int calculate(String s) {
2. if (s == null || s.length() == 0) {
3. return 0;
4. }
5. Stack<Integer> stack = new Stack<Integer>();
6. int sign = 1;// 符号位，1表示+，-1表示-
7. int rt = 0;
8. for (int i = 0; i < s.length(); i++) {
9. char c = s.charAt(i);
10. if (Character.isDigit(c)) {
11. int val = c - '0';
12. // 将数字取出
13. while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
14. val = val * 10 + s.charAt(++i) - '0';
15. }
16. rt += sign * val;
17. } else if (c == '-') {
18. sign = -1;
19. } else if (c == '+') {
20. sign = 1;
21. } else if (c == '(') {
22. // 按照数字、符号的顺序，压入栈
23. stack.push(rt);
24. stack.push(sign);
25. rt = 0;
26. sign = 1;
27. } else if (c == ')') {
28. rt = rt * stack.pop() + stack.pop();
29. sign = 1;
30. }
31. }
32. return rt;
33. }

# Basic Calculator II

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +-*/ operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

Note: Do not use the eval built-in library function.

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

1. public int calculate(String s) {
2. if (s == null || s.length() == 0) {
3. return 0;
4. }
5. Stack<Integer> stack = new Stack<Integer>();
6. for (int i = 0; i < s.length(); i++) {
7. char c = s.charAt(i);
8. if (Character.isDigit(c)) {
9. int val = c - '0';
10. // 将数字取出
11. while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
12. val = val * 10 + s.charAt(++i) - '0';
13. }
14. // 栈顶是 * / 运算符，计算
15. if (!stack.isEmpty()
16. && (stack.peek() == 2 || stack.peek() == 3)) {
17. int sign = stack.pop();
18. int op = stack.pop();
19. int rt = 0;
20. if (sign == 2) {
21. rt = op * val;
22. } else {
23. rt = op / val;
24. }
25. stack.push(rt);
26. } else {
27. stack.push(val);
28. }
29. } else if (c == ' ') {
30. continue;
31. } else {
32. switch (c) {
33. case '+':
34. stack.push(0);
35. break;
36. case '-':
37. stack.push(1);
38. break;
39. case '*':
40. stack.push(2);
41. break;
42. case '/':
43. stack.push(3);
44. break;
45. }
46. }
47. }
48. if (stack.isEmpty()) {
49. return 0;
50. }
51. // 因为要从左向右计算，所以要reverse
52. Collections.reverse(stack);
53. // 计算+-
54. int rt = stack.pop();
55. while (!stack.isEmpty()) {
56. int sign = stack.pop();
57. int op = stack.pop();
58. if (sign == 0) {
59. rt += op;
60. } else {
61. rt -= op;
62. }
63. }
64. return rt;
65. }

# Divide Two Integers

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

If it is overflow, return MAX_INT.

1. public int divide(int dividend, int divisor) {
2. if (divisor == 0) {
3. return Integer.MAX_VALUE;
4. }
5. int result = 0;
6. if (dividend == Integer.MIN_VALUE) {
7. result = 1;
8. if (divisor == -1) {
9. return Integer.MAX_VALUE;
10. }
11. dividend += Math.abs(divisor);
12. }
13. if (divisor == Integer.MIN_VALUE) {
14. return result;
15. }
16. boolean isNeg = ((dividend ^ divisor) >>> 31 == 1) ? true : false;
17. dividend = Math.abs(dividend);
18. divisor = Math.abs(divisor);
19. int c = 0;
20. while (divisor <= (dividend >> 1)) {
21. divisor <<= 1;
22. c++;
23. }
24. while (c >= 0) {
25. if (dividend >= divisor) {
26. dividend -= divisor;
27. result += 1 << c;
28. }
29. divisor >>= 1;
30. c--;
31. }
32. System.out.println(result);
33. return isNeg ? -result : result;
34. }

# Excel Sheet Column Number

Related to question Excel Sheet Column Title

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28

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

1. public int titleToNumber(String s) {
2. int n = 0;
3. int p = 1;
4. for (int i = s.length() - 1; i >= 0; i--) {
5. n += (s.charAt(i) - 'A' + 1) * p;
6. p *= 26;
7. }
8. return n;
9. }

# Excel Sheet Column Title

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB

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

1. public String convertToTitle(int n) {
2. if (n < 27) {
3. return (char) ('A' + (n - 1)) + "";
4. }
5. if (n % 26 == 0) {
6. return convertToTitle(n / 26 - 1) + 'Z';
7. }
8. return convertToTitle(n / 26) + convertToTitle(n % 26);
9. }

# Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

**Note: **Your solution should be in logarithmic time complexity.

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

30!结果转换成3进制，结尾有多少个连续的0？

3， 6， 9， 12， 15 ，18， 21， 24， 27， 30

1. 3 = 3 * 1
2. 6 = 3 * 2
3. 12 = 3 * 4
4. 15 = 3 * 5
5. 21 = 3 * 7
6. 24 = 3 * 8
7. 30 = 3 * 10

1. 9 = 3 * 3
2. 18 = 3 * 3 * 2

1. 27 = 3 * 3 * 3

30/3+30/9+30/27所代表的，就是最终结果。

30/9则计算了一次9、18、27，但是27中还有一个因子没有算。

30/27计算了一次27，至此，所有的因子都计算完毕。

n!中，结尾有多少个连续的0

1. 100！中，结尾有多少个连续的0
2. 100/5 + 100/25 + 100/125 = 20 + 4 + 0 = 24

1. public static int trailingZeroes2(int n) {
2. int rt = 0;
3. for (int i = 5; i <= n; i *= 5) {
4. rt += n / i;
5. }
6. return rt;
7. }

1. public int trailingZeroes(int n) {
2. int rt = 0;
3. long N = n;
4. for (long i = 5; i <= N; i *= 5) {
5. rt += N / i;
6. }
7. return rt;
8. }

# Fraction to Recurring Decimal

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

For example,

• Given numerator = 1, denominator = 2, return "0.5".
• Given numerator = 2, denominator = 1, return "2".
• Given numerator = 2, denominator = 3, return "0.(6)".

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

1. 首先判断符号，使用Math.signum()。如果是正数，返回1；负数，返回-1；是0，返回0。

Returns the signum function of the argument; zero if the argument is zero, 1.0f if the argument is greater than zero, -1.0f if the argument is less than zero.

2. 考虑到溢出，辅助变量定义成long。这是因为如果：

numerator = Integer.MAX_VALUE;
denominator = Integer.MAX_VALUE - 1;

那么在numerator * 10 后，就溢出了。

3. 要取绝对值，因为 -2 % 3 = -2， -2 % -3 = -2

4. 分析57，余数分别是 5 1 3 2 6 4 5，到5处就出现了循环。因为余数必然在[0,7)范围内，如果不能除尽，必然是无限循环小数。循环的位置，就是某余数第一次出现的位置，至当前该余数出现的位置（该余数是所有余数中，第一个出现2次的）。

1. · ·
2. 0.7 1 4 2 8 5
3. - - - - - - -
4. 7 5 0
5. 4 9
6. - - - - - - -
7. 1 0
8. 7
9. - - - - -
10. 3 0
11. 2 8
12. - - - - -
13. 2 0
14. 1 4
15. - - - -
16. 6 0
17. 5 6
18. - - -
19. 4 0
20. 3 5
21. - -
22. 5

如上图所示（希望没画错）。在程序中，就是用Map来表示，key是n/10，也就是整数部分除完后，剩下的余数。余数肯定比被除数小；value是key出现的位置。

map中key和value出现的顺序：

1. key value
2. 5 0
3. 1 1
4. 3 2
5. 2 3
6. 6 4
7. 4 5

下一个n/10是5，map中存在，即可在0处插入“(”，在最后插入“)”。

1. public String fractionToDecimal(int numerator, int denominator) {
2. String sign = "";
3. if (Math.signum(numerator) * Math.signum(denominator) < 0) {
4. sign = "-";
5. }
6. long n = Math.abs(numerator);
7. long d = Math.abs(denominator);
8. String intPart = Math.abs(n / d) + "";
9. // 如果整除，直接返回结果
10. if (n % d == 0) {
11. return sign + intPart;
12. }
13. // 计算小数部分
14. n %= d;
15. n *= 10;
16. StringBuilder sb = new StringBuilder();
17. Map<Long, Integer> mod = new HashMap<Long, Integer>();
18. for (int i = 0; n != 0; i++) {
19. long q = n / d;
20. Integer start = mod.get(n / 10);
21. if (start != null) {
22. sb.insert(start, "(");
23. sb.append(")");
24. break;
25. }
26. sb.append(Math.abs(q));
27. mod.put(n / 10, i);
28. n %= d;
29. n *= 10;
30. }
31. String fractionalPart = sb.toString();
32. return sign + intPart + "." + fractionalPart;
33. }

# Integer to Roman

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

1. 相同的数字连写，所表示的数等于这些数字相加得到的数，如：Ⅲ = 3；
2. 小的数字在大的数字的右边，所表示的数等于这些数字相加得到的数， 如：Ⅷ = 8；Ⅻ = 12；
3. 小的数字，（限于Ⅰ、X 和C）在大的数字的左边，所表示的数等于大数减小数得到的数，如：Ⅳ= 4；Ⅸ= 9；
4. 正常使用时，连写的数字重复不得超过三次。（表盘上的四点钟“IIII”例外）；
5. 在一个数的上面画一条横线，表示这个数扩大1000倍。
1. public String intToRoman(int num) {
2. final int[] values = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5,
3. 4, 1 };
4. final String[] symbol = { "M", "CM", "D", "CD", "C", "XC", "L", "XL",
5. "X", "IX", "V", "IV", "I" };
6. StringBuilder result = new StringBuilder();
7. for (int i = 0; num > 0; i++) {
8. int count = num / values[i];
9. num %= values[i];
10. for (; count > 0; count--) {
11. result.append(symbol[i]);
12. }
13. }
14. return new String(result);
15. }

# 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.

1. public String multiply(String num1, String num2) {
2. if (num1 == null || num2 == null) {
3. return "";
4. }
5. int[] paper = new int[num1.length() + num2.length()];
6. char[] _num1 = num1.toCharArray();
7. char[] _num2 = num2.toCharArray();
8. for (int i = 0; i < _num1.length; i++) {
9. for (int j = 0; j < _num2.length; j++) {
10. paper[paper.length - (i + j + 2)] += (_num1[i] - '0')
11. * (_num2[j] - '0');
12. }
13. }
15. for (int i = 0; i < paper.length - 1; i++) {
16. paper[i + 1] += paper[i] / 10;
17. paper[i] %= 10;
18. }
19. String s = "";
20. for (int i = paper.length - 1; i > 0; i--) {
21. if ("" == s && paper[i] == 0) {
22. continue;
23. }
24. s += paper[i];
25. }
26. s += paper[0];
27. return s;
28. }
29. // can't be accepted in leetcode
30. public String multiply2(String num1, String num2) {
31. if (num1 == null || num2 == null) {
32. return "";
33. }
34. BigInteger n1 = new BigInteger(num1);
35. BigInteger n2 = new BigInteger(num2);
36. return n1.multiply(n2).toString();
37. }

# Number of Digit One

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

Hint:

1. Beware of overflow.

1. public int countDigitOne(int n) {
2. int ones = 0;
3. for (long m = 1; m <= n; m *= 10) {
4. long a = n / m, b = n % m;
5. ones += (a + 8) / 10 * m;
6. if (a % 10 == 1)
7. ones += b + 1;
8. }
9. return ones;
10. }

# Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

click to show spoilers.

Some hints:

Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

1. public boolean isPalindrome(int x) {
2. if (x < 0) {
3. return false;
4. }
5. if (x >= 0 && x < 10) {
6. return true;
7. }
8. int d = 1;
9. while (x / d >= 10) {
10. d *= 10;
11. }
12. while (x != 0) {
13. if (x % 10 != x / d) {
14. return false;
15. }
16. x = x % d / 10;
17. d /= 100;
18. }
19. return true;
20. }

# Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

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

1. public int numSquares(int n) {
2. int[] dp = new int[n + 1];
3. Arrays.fill(dp, Integer.MAX_VALUE);
4. // 将所有平方数置1
5. for (int i = 0; i * i <= n; i++) {
6. dp[i * i] = 1;
7. }
8. for (int a = 1; a <= n; a++) {
9. for (int b = 1; a + b * b <= n; b++) {
10. // 取较小值，a + b * b也可能是平方数
11. dp[a + b * b] = Math.min(dp[a] + 1, dp[a + b * b]);
12. }
13. }
14. return dp[n];
15. }

# Permutation Sequence

The set [1,2,3,…,_n_] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

k1/(n−1)!

k1=k

k2/(n−2)!

k2=k1

1. public String getPermutation(int n, int k) {
2. if (n <= 0 || k <= 0) {
3. return "";
4. }
5. String result = "";
6. List<Integer> list = new ArrayList<Integer>();
7. int fact = 1;
8. for (int i = 1; i <= n; i++) {
10. fact *= i;
11. }
12. k--;
13. for (int i = 0; i < n; i++) {
14. fact /= (n - i);
15. int index = k / fact;
16. result += list.get(index);
17. list.remove(index);
18. k %= fact;
19. }
20. return result;
21. }

# Plus One

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

1. public int[] plusOne(int[] digits) {
2. if (digits == null || digits.length == 0) {
3. return null;
4. }
5. int[] rt = new int[digits.length + 1];
6. digits[digits.length - 1]++;
7. for (int i = digits.length - 1; i >= 0; i--) {
8. rt[i + 1] += digits[i];
9. rt[i] += rt[i + 1] / 10;
10. rt[i + 1] %= 10;
11. }
12. if (rt[0] == 0) {
13. return Arrays.copyOfRange(rt, 1, rt.length);
14. } else {
15. return rt;
16. }
17. }

# Power of Two

Given an integer, write a function to determine if it is a power of two.

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

1. public boolean isPowerOfTwo(int n) {
2. if (n <= 0) {
3. return false;
4. }
5. return (n & (n - 1)) == 0;
6. }

# Pow(x, n)

Implement pow(xn).

1. public double myPow(double x, int n) {
2. if (n < 0) {
3. return 1 / pow(x, -n);
4. } else {
5. return pow(x, n);
6. }
7. }
8. private double pow(double x, int n) {
9. if (n == 0) {
10. return 1;
11. }
12. double v = pow(x, n / 2);
13. if (n % 2 == 0) {
14. return v * v;
15. } else {
16. return v * v * x;
17. }
18. }
19. }

# Rectangle Area

Find the total area covered by two rectilinear rectangles in a 2D plane.

Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.

Assume that the total area is never beyond the maximum possible value of int.

Credits:
Special thanks to @mithmatt for adding this problem, creating the above image and all test cases.

1. 不考虑两个矩形相交，分别求出每个矩形的面积，相加
2. 如果两个矩形不相交，直接返回结果
3. 如果两个矩形相交，减去相交部分面积
1. public int computeArea(int A, int B, int C, int D, int E, int F, int G,
2. int H) {
3. int area = (C - A) * (D - B) + (G - E) * (H - F);
4. if (A >= G || B >= H || C <= E || D <= F) {
5. return area;
6. }
7. int top = Math.min(D, H);
8. int bottom = Math.max(B, F);
9. int left = Math.max(A, E);
10. int right = Math.min(C, G);
11. return area - (top - bottom) * (right - left);
12. }

# Reverse Integer

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

click to show spoilers.

Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!

If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.

Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?

For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Update (2014-11-10):

1. public int reverse(int x) {
2. if (x == Integer.MIN_VALUE) {
3. return 0;
4. }
5. if (x < 0) {
6. return -reverse(-x);
7. }
8. int rt = 0;
9. do {
10. // y * 10 + x % 10 > Integer.MAX_VALUE
11. if (rt > (Integer.MAX_VALUE - x % 10) / 10) {
12. return 0;
13. }
14. rt = rt * 10 + x % 10;
15. x = x / 10;
16. } while (x > 0);
17. return rt;
18. }

# Roman to Integer

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

1. 相同的数字连写，所表示的数等于这些数字相加得到的数，如：Ⅲ = 3；
2. 小的数字在大的数字的右边，所表示的数等于这些数字相加得到的数， 如：Ⅷ = 8；Ⅻ = 12；
3. 小的数字，（限于Ⅰ、X 和C）在大的数字的左边，所表示的数等于大数减小数得到的数，如：Ⅳ= 4；Ⅸ= 9；
4. 正常使用时，连写的数字重复不得超过三次。（表盘上的四点钟“IIII”例外）；
5. 在一个数的上面画一条横线，表示这个数扩大1000倍。
1. public String intToRoman(int num) {
2. final int[] values = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5,
3. 4, 1 };
4. final String[] symbol = { "M", "CM", "D", "CD", "C", "XC", "L", "XL",
5. "X", "IX", "V", "IV", "I" };
6. StringBuilder result = new StringBuilder();
7. for (int i = 0; num > 0; i++) {
8. int count = num / values[i];
9. num %= values[i];
10. for (; count > 0; count--) {
11. result.append(symbol[i]);
12. }
13. }
14. return new String(result);
15. }

# Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

1. public int mySqrt(int x) {
2. // 首先对负数和0进行处理
3. if (x < 0) {
4. return -1;
5. } else if (x == 0) {
6. return 0;
7. }
8. int start = 1;
9. int end = x;
10. while (start < end) {
11. // 不能直接相加除以2，因为两个数相加可能溢出
12. int m = start + (end - start) / 2;
13. // 不能用m^2，(m+1)^2，因为可能溢出
14. int m1 = x / m;
15. int m2 = x / (m + 1);
16. // m*2 == x
17. if (m == m1) {
18. return m;
19. }
20. // (m+1)^2 == x
21. if (m + 1 == m2) {
22. return m + 1;
23. }
24. // m*2 <= x && (m+1)^2 > x
25. if (m < m1 && m + 1 > m2) {
26. return m;
27. }
28. // m*2 > x
29. if (m1 < m) {
30. end = m;
31. } else {
32. // (m+1)^2 < x
33. start = m + 1;
34. }
35. }
36. return 1;
37. }

# String to Integer (atoi)

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Update (2015-02-10):
The signature of the C++ function had been updated. If you still see your function signature accepts a const char * argument, please click the reload button  to reset your code definition.

spoilers alert... click to show requirements for atoi.

Requirements for atoi:

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

1. 无效的格式，如：”+-1234”, “+-c1234”；
2. 有效的格式，如：”-123c4”, “+1234”；
3. 数据溢出，如：”2147483648”；
4. 注意字符串首尾的空格。
1. public int myAtoi(String str) {
2. if (str == null || str.length() == 0) {
3. return 0;
4. }
5. char[] c = str.toCharArray();
6. int i = 0, flag = 1, rt = 0;
7. for (; i < c.length; i++) {
8. if (c[i] == ' ') {
9. continue;
10. } else {
11. break;
12. }
13. }
14. if (c[i] == '+') {
15. i++;
16. } else if (c[i] == '-') {
17. flag = -1;
18. i++;
19. }
20. for (; i < c.length; i++) {
21. if (c[i] > '9' || c[i] < '0') {
22. break;
23. }
24. if (rt > Integer.MAX_VALUE / 10
25. || (rt == Integer.MAX_VALUE / 10 && (c[i] - '0') > Integer.MAX_VALUE % 10)) {
26. return (flag == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
27. }
28. rt = rt * 10 + c[i] - '0';
29. }
30. return rt * flag;
31. }

# Ugly Number

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.

Note that 1 is typically treated as an ugly number.

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

1. public boolean isUgly(int num) {
2. if (num < 1) {
3. return false;
4. }
5. while (num != 1) {
6. if (num % 2 == 0) {
7. num /= 2;
8. } else if (num % 3 == 0) {
9. num /= 3;
10. } else if (num % 5 == 0) {
11. num /= 5;
12. } else {
13. return false;
14. }
15. }
16. return true;
17. }

# Ugly Number II

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number.

Hint:

1. The naive approach is to call isUgly for every number until you reach the nth one. Most numbers are not ugly. Try to focus your effort on generating only the ugly ones.
2. An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.
3. The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L1, L2, and L3.
4. Assume you have Uk, the kth ugly number. Then Uk+1 must be Min(L1 * 2, L2 * 3, L3 * 5).

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

1. public int nthUglyNumber(int n) {
2. int[] nums = new int[n];
3. nums[0] = 1;
4. int i = 0, j = 0, k = 0, t = 1;
5. while (t < n) {
6. int min = Math.min(Math.min(nums[i] * 2, nums[j] * 3), nums[k] * 5);
7. nums[t++] = min;
8. if (nums[i] * 2 == min) {
9. i++;
10. }
11. if (nums[j] * 3 == min) {
12. j++;
13. }
14. if (nums[k] * 5 == min) {
15. k++;
16. }
17. }
18. return nums[n - 1];
19. }

# Valid Number

Validate if a given string is numeric.

Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

Update (2015-02-10):
The signature of the C++ function had been updated. If you still see your function signature accepts a const char * argument, please click the reload button  to reset your code definition.

1. public boolean isNumber(String s) {
2. if (s == null || s.length() == 0) {
3. return false;
4. }
5. char[] chars = s.toCharArray();
6. int start = 0, end = chars.length - 1;
7. // 除去前后的空格
8. while ((start < end) && chars[start] == ' ') {
9. start++;
10. }
11. while ((start < end) && chars[end] == ' ') {
12. end--;
13. }
14. // 因为while的循环条件是start < end，s为空格时，会剩下一个空格
15. if (chars[start] == ' ') {
16. return false;
17. }
18. boolean dot = false;
19. boolean num = false;
20. boolean ex = false;
21. for (int i = start; i <= end; i++) {
22. char c = chars[i];
23. if (c >= '0' && c <= '9') {
24. num = true;
25. } else if (c == 'e') {
26. if (ex)
27. return false;
28. if (!num)
29. return false;
30. ex = true;
31. num = false;
32. dot = false;
33. } else if (c == '.') {
34. if (dot) {
35. return false;
36. }
37. if (ex) {
38. return false;
39. }
40. dot = true;
41. } else if (c == '+' || c == '-') {
42. if (num || dot) {
43. return false;
44. }
45. } else {
46. return false;
47. }
48. }
49. return num;
50. }

• 私有
• 公开
• 删除