4月 21日
1 7 Reverse Integer 先算新结果,与旧结果比较,如果不等 返回0
public int reverse(int x) { int result = 0; while (x != 0) { int tail = x % 10; int newR = result * 10 + tail; if ((newR - tail)/10!= result) { return 0; } result = newR; x /= 10; } return result; }
2 8 String to Integer 去空格,找符号 转大小
public int myAtoi(String str) { int index = 0, sign = 1, sum = 0; if (str == null || str.length() == 0) return 0; while (index < str.length() && str.charAt(index) == ' ') { index++; } if (str.charAt(index) == '+' || str.charAt(index) == '-') { sign = str.charAt(index) == '+' ? 1:-1; index++; } while (index < str.length()) { if (!Character.isDigit(str.charAt(index))) return sign * sum; int digit = str.charAt(index) - '0'; if (Integer.MAX_VALUE / 10 < sum || Integer.MAX_VALUE / 10 == sum && Integer.MAX_VALUE % 10 < digit) { return sign == 1? Integer.MAX_VALUE : Integer.MIN_VALUE; } sum = sum * 10 + digit; index++; } return sign * sum; }
3 9 Palindrome Number 检测小于0 或 10的倍数 当rev < x
public boolean isPalindrome(int x) { if (x < 0 || x != 0&&x % 10 == 0) return false; int rev = 0; while (x > rev) { rev = rev * 10 + x%10; x/=10; } return (x==rev || x==rev/10); }
4 12 Integer to Roman 写出各个位的10位表示 相加
public String intToRoman(int num) { String M[] = {"", "M", "MM", "MMM"}; String C[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"}; String X[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"}; String I[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"}; return M[num/1000] + C[(num%1000)/100] + X[(num%100)/10] + I[num%10]; }
4 月 22 日
5 13 Roman to Integer 比较俩个相邻字符大小
public int romanToInt(String s) { int sum = 0; for (int i = 0; i < s.length() - 1; i++) { int i1 = get(s.charAt(i)), i2 = get(s.charAt(i + 1)); if (i1 < i2) { sum -= i1; }else { sum += i1; } } return sum + get(s.charAt(s.length()-1)); } public int get(char c) { switch(c) { case 'M': return 1000; case 'D': return 500; case 'C': return 100; case 'L': return 50; case 'X' : return 10; case 'V': return 5; case 'I': return 1; default: return 0; } }
6 29 Divide Two Integer 除数 <= 被除数 >> 1 找到digit 和除数界限 比较除数和被除数和最小值之间关系
public int divide(int dividend, int divisor) { if (divisor == 0) return Integer.MAX_VALUE; boolean isN = (dividend ^ divisor) >>> 31 == 1; int res = 0; if (dividend == Integer.MIN_VALUE) { dividend += Math.abs(divisor); if (divisor == -1) { return Integer.MAX_VALUE; } res++; } if (divisor == Integer.MIN_VALUE) return res; dividend = Math.abs(dividend); divisor = Math.abs(divisor); int digit = 0; while (divisor <= (dividend >> 1)) { digit++; divisor <<= 1; } while(digit >= 0) { if (dividend >= divisor) { res += 1 << digit; dividend -= divisor; } digit--; divisor >>= 1; } return isN? -res:res; }
7 43 Multiply Strings i+j, i+j+1 按照乘法规律 从后往前
public String multiply(String num1, String num2) { int m = num1.length(), n = num2.length(); int[] res = new int[m + n]; for (int i = m - 1; i >= 0; i--) { for (int j = n - 1; j >= 0; j--) { int num = (num1.charAt(i) - '0')*(num2.charAt(j) - '0'); int p1 = i + j, p2 = i + j + 1; num += res[p2]; res[p1] += num / 10; res[p2] = num % 10; } } StringBuilder sb = new StringBuilder(); for (int i : res) { if (!(sb.length() == 0 && i == 0)) sb.append(i); } return sb.length() == 0? "0" :sb.toString(); }
8 50 Pow(x,n) n >0 x平方
public double myPow(double x, int n) { if (n == 0) return 1.0; double res = 1.0; if (n < 0) { if (x >= 1/Double.MAX_VALUE || x <= -1/Double.MAX_VALUE) { x = 1/x; }else { return Double.MAX_VALUE; } if (n == Integer.MIN_VALUE) { res *= x; n++; } } n = Math.abs(n); boolean isN = false; if (n % 2 == 1 && x < 0) isN = true; x = Math.abs(x); while (n > 0) { if ((n & 1) == 1) { if (Double.MAX_VALUE / x < res) { return Double.MAX_VALUE; } res *= x; } x *= x; n >>= 1; } return isN ? -res: res; }
4月 23 日
9 60 Permutation Sequence 先减1,除(n-1)找索引,迭代
public String getPermutation(int n, int k) { if (n < 0) return ""; k--; List<Integer> num = new ArrayList<>(); StringBuilder res = new StringBuilder(); for (int i = 1; i <= n; i++) { num.add(i); } int count = n - 1, f = 1; for (int i = 2; i < n; i++) { f *= i; } while (count >= 0) { int index = k / f; k = k % f; res.append(num.get(index)); num.remove(index); if (count > 0) { f /= count; } count --; } return res.toString(); }
10 65 Valid Number 四个标记数 e . num在e后 几个判段
public boolean isNumber(String s) { s = s.trim(); boolean numsee = false; boolean pointsee = false; boolean esee = false; boolean numaftere = true; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (c >= '0' && c <= '9') { numsee = true; numaftere = true; } else if (c == '.') { if (pointsee || esee) { return false; } pointsee = true; } else if (c == 'e') { if (esee || !numsee) { return false; } esee = true; numaftere = false; } else if (c == '+' || c == '-') { if (i != 0 && s.charAt(i - 1)!= 'e') { return false; } } else { return false; } } return numaftere && numsee; }
11 Add Binary 从后计算 反转
public String addBinary(String a, String b) { int i = a.length() - 1, j = b.length() - 1, carry = 0; StringBuilder sb = new StringBuilder(); while (i >= 0 || j >= 0) { int sum = carry; if (i >= 0) sum += (a.charAt(i--) - '0'); if (j >= 0) sum += (b.charAt(j--) - '0'); sb.append(sum%2); carry = sum/2; } if (carry != 0) sb.append(carry); return sb.reverse().toString(); }
12 Sprt(x) 二分查找
public int mySqrt(int x) { if (x < 0) return -1; if (x == 0) return 0; int l = 1, r = x / 2 + 1; while (l <= r) { int m = (r - l) / 2 + l; if (m <= x/m && (m + 1) > x /(m + 1)) { return m; } else if (m > x / m) { r = m - 1; } else { l = m + 1; } } return 0; }
4 月 24 日
13 166 Frction to Recurring Decimal 按除法操作 维护map 和 stringbuilder
public String fractionToDecimal(int numerator, int denominator) { if (numerator == 0) return "0"; StringBuilder sb = new StringBuilder(); sb.append(((numerator > 0) ^ (denominator > 0)) ? "-":""); long num = Math.abs((long)numerator); long den = Math.abs((long)denominator); sb.append(num/den); num %= den; if (num == 0) return sb.toString(); sb.append("."); HashMap<Long, Integer> res = new HashMap<>(); res.put(num, sb.length()); while (num != 0) { num *= 10; sb.append(num / den); num %= den; if (res.containsKey(num)) { sb.insert(res.get(num), "("); sb.append(")"); break; } res.put(num, sb.length()); } return sb.toString(); }
14 168 Excel Sheet Column Title n-- 对26取余 并+A
public String convertToTitle(int n) { return n == 0? "" : convertToTitle(--n/26) + (char)('A'+(n%26)); }
15 171 Excel Sheet Column Number res * 26 + 余
public int titleToNumber(String s) { int res = 0; for (int i = 0; i < s.length(); res = res * 26 + (int)(s.charAt(i) - 'A'+1), i++); return res; }
16 172 Factorial Trailing Zerses 除5
public int trailingZeroes(int n) { return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5); }
17 202 Happy Number
public boolean isHappy(int n) { int fast = n, slow = n; do { fast = cal(fast); fast = cal(fast); slow = cal(slow); if (fast == 1) return true; }while (fast != slow); return false; } public int cal(int n) { int res = 0; while (n != 0) { res += (n % 10) * (n % 10); n/= 10; } return res; }
4 月 25 号
18 204 Count Primes boolean数组 ,遍历
public int countPrimes(int n) { boolean[] isP = new boolean[n]; int count = 0; for (int i = 2; i < n; i++) { if (!isP[i]) { count ++; for (int j = 2; j * i < n; j++) { isP[j * i] = true; } } } return count; }
19 223 Rectangle Area 两大面积减小面积
public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) { int left = Math.max(A,E), right = Math.max(left, Math.min(C,G)); int bottom = Math.max(B,F), top = Math.max(bottom, Math.min(D,H)); return (C-A)*(D-B) - (right - left)*(top - bottom) + (G-E)*(H-F); }
20 224 Basic Calculator 用一个栈维护,每遇到(数放入栈中
public int calculate(String s) { int res = 0, sign = 1; Stack<Integer> stack = new Stack<>(); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (Character.isDigit(c)) { int sum = c - '0'; while (i + 1 < s.length()&& Character.isDigit(s.charAt(i + 1))) { sum = sum * 10 + (s.charAt(i + 1) - '0'); i++; } res += sum * sign; } else if(c == '+') { sign = 1; } else if(c == '-') { sign = -1; } else if(c == '(') { stack.push(res); stack.push(sign); res = 0; sign = 1; }else if (c == ')') { res = res * stack.pop()+stack.pop(); } } return res; }
21 Power of Two
public boolean isPowerOfTwo(int n) { return ((n &(n - 1))==0 && n > 0); }
4月26 号
22 233 Number of Digit One 公式
public int countDigitOne(int n) { int ones = 0; for (long m = 1; m <= n; m *= 10) ones += (n/m + 8) / 10 * m + (n/m % 10 == 1 ? n%m + 1 : 0); return ones; }
23 246 Strobogrammtic number 把数放入map,比较左右
public boolean isStrobogrammatic(String num) { HashMap<Character, Character> map = new HashMap<>(); map.put('0','0'); map.put('1','1'); map.put('6','9'); map.put('8','8'); map.put('9','6'); int l = 0, r = num.length() - 1; while (l <= r) { if (!map.containsKey(num.charAt(l)) || map.get(num.charAt(l))!=num.charAt(r)) { return false; } l++;r--; } return true; }
24 247 Strobogrammtic number II 递归
public class Solution { public List<String> helper(int n, int m) { if (n == 0) return new ArrayList<String>(Arrays.asList("")); if (n == 1) return new ArrayList<String>(Arrays.asList("0", "1", "8")); List<String> list = helper(n - 2, m); List<String> result = new ArrayList<String>(); for (int i = 0; i < list.size(); i++) { String s = list.get(i); if (n != m) result.add("0" + s + "0"); result.add("1" + s + "1"); result.add("8" + s + "8"); result.add("6" + s + "9"); result.add("9" + s + "6"); } return result; } public List<String> findStrobogrammatic(int n) { return helper(n, n); } }
25 248 Strobogrammtic number III
public int strobogrammaticInRange(String low, String high) { int count = 0; List<String> res = new ArrayList<>(); for (int i = low.length(); i <= high.length(); i++) { res.addAll(help(i,i)); } for (String str : res) { if (str.length() == low.length() && str.compareTo(low) < 0 || str.length() == high.length() && str.compareTo(high) > 0) { continue; } count++; } return count; } private List<String> help(int m, int n) { // TODO Auto-generated method stub if (m == 0) return new ArrayList<String>(Arrays.asList("")); if (m == 1) return new ArrayList<String>(Arrays.asList("0", "1", "8")); List<String> list = help(n - 2, n); List<String> res = new ArrayList<>(); for (int i = 0; i < list.size(); i++) { String s = list.get(i); if (m != n) res.add("0" + s + "0"); res.add("1" + s + "1"); res.add("6" + s + "9"); res.add("8" + s + "8"); res.add("9" + s + "6"); } return res; }