刷题记录

Problem: Given a positive integer  n  and you can do operations as follow: If  n  is even, replace  n  with  n /2 . If  n  is odd, you can replace  n  with either  n  + 1  or  n  - 1 . What is the minimum number of replacements needed for  n  to become 1? Example 1: Input: 8 Output: 3 Explanation: 8 -> 4 -> 2 -> 1 Example 2: Input: 7 Output: 4 Explanation: 7 -> 8 -> 4 -> 2 -> 1 or 7 -> 6 -> 3 -> 2 -> 1 Analysis: User recursion.  Not fit for dp, because if n is odd, n can add 1. Solution: n + 1 might overflow, use long in recursion instead of int. class Solution { public int integerReplacement ( int n) { return ( int )longReplacement(n); } private int longReplacement ( long n) { if (n == 1 ) return 0 ; if (n % 2 == 0 ) return longReplacement(n / 2 ) + 1 ; else re...

Problem: Given a positive integer  num , write a function which returns True if  num  is a perfect square else False. Note:   Do not  use any built-in library function such as  sqrt . Example 1: Input: 16 Returns: True Example 2: Input: 14 Returns: False Analysis: Be careful with int/int, if num is 5, 5/2=2. Solution: To include 1, use start <= end as while condition. Easy but not trivial. class Solution { public boolean isPerfectSquare ( int num) { long start = 1 , end = num; while (start <= end) { long mid = start + (end - start) / 2 ; if (mid * mid == num) return true; else if (mid * mid < num) { start = mid + 1 ; } else { end = mid - 1 ; } } return false; } }

Problem: Given two binary strings, return their sum (also a binary string). The input strings are both  non-empty  and contains only characters  1  or  0 . Example 1: Input: a = "11", b = "1" Output: "100" Example 2: Input: a = "1010", b = "1011" Output: "10101" Analysis: Skip Solution: class Solution { 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 x = i < 0 ? 0 : a . charAt(i) - '0' ; int y = j < 0 ? 0 : b . charAt(j) - '0' ; int cur = x + y + carry; sb . append(cur & 1 ); carry = cur >> 1 ; i -- ; j -- ; } if (carry == 1 ) sb . append(carry); re...

Problem: According to the  Wikipedia's article : "The  Game of Life , also known simply as  Life , is a cellular automaton devised by the British mathematician John Horton Conway in 1970." Given a  board  with  m  by  n  cells, each cell has an initial state  live  (1) or  dead  (0). Each cell interacts with its  eight neighbors  (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article): Any live cell with fewer than two live neighbors dies, as if caused by under-population. Any live cell with two or three live neighbors lives on to the next generation. Any live cell with more than three live neighbors dies, as if by over-population.. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction. Write a function to compute the next state (after one update) of the board given its current state.  The next state is created ...

Problem: Given an integer (signed 32 bits), write a function to check whether it is a power of 4. Example: Given num = 16, return true. Given num = 5, return false. Analysis: 类似于power of three。 Solution: class Solution { public boolean isPowerOfFour ( int num) { if (num <= 0 ) return false; while (num % 4 == 0 ) { num /= 4 ; } return num == 1 ; } }

Problem: Given an integer, write a function to determine if it is a power of three. Analysis: 判断一个数是否是3的次方。用数学公式那是不现实的。。。 如果一个数是3的次方，一直除以3最后结果是1. 不是3的次方，但是是3的倍数比如6，6/3=2. 2/3=0. 最后结果是0. Solution: class Solution { public boolean isPowerOfThree ( int n) { if (n <= 0 ) return false; while (n % 3 == 0 ) { n /= 3 ; } return n == 1 ; } }

Problem: Given two strings  A  and  B  of lowercase letters, return  true  if and only if we can swap two letters in  A  so that the result equals  B . Example 1: Input: A = "ab" , B = "ba" Output: true Example 2: Input: A = "ab" , B = "ab" Output: false Example 3: Input: A = "aa" , B = "aa" Output: true Example 4: Input: A = "aaaaaaabc" , B = "aaaaaaacb" Output: true Example 5: Input: A = "" , B = "aa" Output: false Analysis: Buddy string qualifies the following conditoin: 1. Length equal 2. If exact equal, A must have duplicate, since swap is required. 3. A and B only have 2 chars diff, and these 2 chars can swap. Solution: class Solution { public boolean buddyStrings ( String A , String B ) { // compare length if ( A . length() != B . length()) return false; // equals, find duplicates ...