刷题记录

Problem: 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. Example 1: Input: "3+2*2" Output: 7 Example 2: Input: " 3/2 " Output: 1 Example 3: Input: " 3+5 / 2 " Output: 5 Analysis: Very similar to Basic Calculator I. The idea is to calculate the temp result whenever a sign is met and push into stack. If the prev sign is * or /, grab the stack top calc together. For instance 3 + 2* 2. +: calc +3 push into stack *: calc +2 push into stack string end: calc 2*2 push into stack Solution: Beware that the number might over 1 digit. class Solution { public int calculate ( String s) { Stack< Integer > stack = new Stack<> (); char sign = '+' ; int num = 0 ; for ( int i = 0 ; i < s . leng...

Problem: Write an algorithm to determine if a number is "happy". A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers. Example:  Input: 19 Output: true Explanation: 1 2 + 9 2 = 82 8 2 + 2 2 = 68 6 2 + 8 2 = 100 1 2 + 0 2 + 0 2 = 1 Analysis: Use hash set to cache the sum, if sum exists in set, then the algorithm falls into cycle. So its not happy number. Solution: class Solution { public boolean isHappy ( int n) { Set< Integer > set = new HashSet<> (); int sum = 0 ; while (set . add(sum)) { sum = 0 ; while (n > 0 ) { sum += (n % 10 ) * (n % 10 ); ...

Problem: Reverse bits of a given 32 bits unsigned integer. Example: Input: 43261596 Output: 964176192 Explanation: 43261596 represented in binary as 00000010100101000001111010011100 ,   return 964176192 represented in binary as 00111001011110000010100101000000 . Analysis: skip Solution: public class Solution { // you need treat n as an unsigned value public int reverseBits ( int n) { int res = 0 ; for ( int i = 0 ; i < 32 ; i ++ ) { if ((n & 1 ) == 1 ) { res = (res << 1 ) + 1 ; } else { res = res << 1 ; } n = n >> 1 ; } return res; } }

Problem: Given a list of  unique  words, find all pairs of  distinct  indices  (i, j)  in the given list, so that the concatenation of the two words, i.e.  words[i] + words[j]  is a palindrome. Example 1: Given  words  =  ["bat", "tab", "cat"] Return  [[0, 1], [1, 0]] The palindromes are  ["battab", "tabbat"] Example 2: Given  words  =  ["abcd", "dcba", "lls", "s", "sssll"] Return  [[0, 1], [1, 0], [3, 2], [2, 4]] The palindromes are  ["dcbaabcd", "abcddcba", "slls", "llssssll"] Analysis: Tire tree is not the optimal approach here. For example. the string "ab cdc "   the right part is palindrome. We want to find another string in words that is the reverse of  the left part. So we can compose a palindrome "ab cdc ba". Use hashtable to store the index of each string. Solution: It's important to check s2.len...

Problem: Given a 2D board and a list of words from the dictionary, find all words in the board. Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word. For example, Given  words  =  ["oath","pea","eat","rain"]  and  board  = [ [' o ',' a ','a','n'], ['e',' t ',' a ',' e '], ['i',' h ','k','r'], ['i','f','l','v'] ] Return  ["eat","oath"] . Analysis: 6/6/3028 update: 这道题的思想很简答，但是写成bug free各种情况都考虑到很难。这一遍保存word考虑到了，去重没想到。 ------------------- ------------------- ------------------- ------------------- ------------------- ------------------- ------------------- ------- 3/6/0218 update: The problem is how to validate the ...