刷题记录

Problem: Given a non-empty string  s , you may delete  at most  one character. Judge whether you can make it a palindrome. Example 1: Input: "aba" Output: True Example 2: Input: "abca" Output: True Explanation: You could delete the character 'c'. Note: The string will only contain lowercase characters a-z. The maximum length of the string is 50000. Analysis: leetcode 面经真准。这道题是fb最近的电面原题。 Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public boolean validPalindrome ( String s ) { if ( s == null || s . length () == 0 ) return false; int l = 0 , r = s . length () - 1 ; while ( l < r ) { if ( s . charAt ( l ) == s . charAt ( r )) { l ++; r --; } else return isPalindrome ( s , l + 1 , r ) || isPalindrome ( s , l , r -...

Problem: Given a  non-empty  string  s  and an abbreviation  abbr , return whether the string matches with the given abbreviation. A string such as  "word"  contains only the following valid abbreviations: ["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"] Notice that only the above abbreviations are valid abbreviations of the string  "word" . Any other string is not a valid abbreviation of  "word" . Note: Assume  s  contains only lowercase letters and  abbr  contains only lowercase letters and digits. Example 1: Given s = "internationalization", abbr = "i12iz4n": Return true. Example 2: Given s = "apple", abbr = "a2e": Return false. Analysis: 这道题的坑爹程度也只是稍微比isNumber Val...

Problem: Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. getMin() -- Retrieve the minimum element in the stack. Example: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> Returns -3. minStack.pop(); minStack.top(); --> Returns 0. minStack.getMin(); --> Returns -2. Analysis: 每当有极小数的时候，先把次小数push进stack,然后把极小数push进stack。当pop的数是当前min的时候，连续pop 2次，第二次的就是pop后的min. push -2     stack -2, max] min: -2 push 0     stack 0, -2, max] min: -2 push -3     stack -3, -2, 0, -2, max] min: -3 pop:     这里先pop-3出去，发现-3刚好是最小值，所以把 -2也pop出去，-2就是去除-3后的最小值。 Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class MinStack { ...

Probelm: A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Write a function to determine if a number is strobogrammatic. The number is represented as a string. Example 1: Input: "69" Output: true Example 2: Input: "88" Output: true Example 3: Input: "962" Output: false Analysis: 列举出可以rotate的数对，然后用同向双指针检查是否匹配。 Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public boolean isStrobogrammatic ( String num ) { Map < Character , Character > map = new HashMap < Character , Character >(); map . put ( '6' , '9' ); map . put ( '9' , '6' ); map . put ( '0' , '0' ); map . put ( '1' , '1' ); map . put ( '8' , '8' ); int l = 0 , r = num . length () - 1 ; while ( l <= r ) { ...

Problem: Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree  [1,2,2,3,4,4,3]  is symmetric: 1 / \ 2 2 / \ / \ 3 4 4 3 But the following  [1,2,2,null,3,null,3]  is not: 1 / \ 2 2 \ \ 3 3 Analysis: 如果当前对比的node1 和node 2相等，要符合symmetric tree我们需要比较node1.left == node2.right && node1.right == node2.left. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution { public boolean isSymmetric ( TreeNode root ) { return root == null || helper ( root . left , root . right ); } private boolean helper ( TreeNode left , TreeNode right ) { if ( left == null && right == null) return true; if (( left != null && right == null) || ( left == null && right != null) || left . val != right . val ) return false; r...

Problem: You're given strings  J  representing the types of stones that are jewels, and  S  representing the stones you have.  Each character in  S is a type of stone you have.  You want to know how many of the stones you have are also jewels. The letters in  J  are guaranteed distinct, and all characters in  J  and  S  are letters. Letters are case sensitive, so  "a"  is considered a different type of stone from  "A" . Example 1: Input: J = "aA", S = "aAAbbbb" Output: 3 Example 2: Input: J = "z", S = "ZZ" Output: 0 Note: S  and  J  will consist of letters and have length at most 50. The characters in  J  are distinct. Analysis: skip Soluiton: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public int numJewelsInStones(String J, String S) { Set<Character> set = new HashSet<>(); for ( char c: J.toCharArray()) { s...

Problem: Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST. Example: Input: The root of a Binary Search Tree like this: 5 / \ 2 13 Output: The root of a Greater Tree like this: 18 / \ 20 13 Analysis: Reverse traversal from right to root to left. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 class Solution { int sum = 0; public TreeNode convertBST(TreeNode root) { if (root == null ) return null ; convertBST(root.right); int val = root.val; root.val += sum; sum += val; convertBST(root.left); return root; } }

Problem: Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000. Example 1: Input: "abab" Output: True Explanation: It's the substring "ab" twice. Example 2: Input: "aba" Output: False Example 3: Input: "abcabcabcabc" Output: True Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.) Analysis: The qualified substring must start from index 0. And its length <= s.length/2. So we find all candidate substrings and test whether they can fit s. Solution: class Solution { public boolean repeatedSubstringPattern ( String s ) { if ( s = = null | | s . length ( ) = = 0 ) return false ; int len = s . length (...

Problem: Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1. Examples: s = "leetcode" return 0. s = "loveleetcode", return 2. Analysis: The idea is two pass. First pass count currency in map. Second path, find the first count == 1's char in map. Solution: class Solution { public int firstUniqChar ( String s ) { if ( s = = null | | s . length ( ) = = 0 ) return - 1 ; int res = 0 ; Set < Character > checkSet = new HashSet < > ( ) ; Set < Character > dupSet = new HashSet < > ( ) ; for ( char c : s . toCharArray ( ) ) { if ( ! checkSet . add ( c ) ) { dupSet . add ( c ) ; } } for ( int i = 0 ; i < s . length ( ) ; i + + ) { if ( ! dupSet . contains ( s . charAt ( i ) ) ) return i ; } return - 1 ; } }

Analysis : First divide the array (red) until reaches single number. Then starting merge(green). Need a temp array to store the sorted elements while merging.  Solution : If start  == end, then the first mergeSort， start to mid, will fell into infinite recursive call.  public class Solution { /** * @param A: an integer array * @return : nothing */ public void sortIntegers2 ( int [] A ) { // write your code here mergeSort( A , new int [ A . length], 0 , A . length - 1 ); } private void mergeSort ( int [] A , int [] temp, int start, int end) { if (start >= end) { return ; } int mid = start + (end - start) / 2 ; mergeSort( A , temp, start, mid); mergeSort( A , temp, mid + 1 , end); merge( A , temp, start, end, mid); } private void merge ( int [] A , int [] temp, int start, int end, int mid) { int p1 = start, p2 = mid + 1 , p = s...

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