每日打卡刷题记录

2/5/2018 开始刷题第一轮预计三个月
主要先完成Amazon，LinkedIn和Facebook标记的题，然后再看其他高频题，最后集中强化系统设计题。
每日打卡督促刷题

2/5/2018
Amazon Questions 10题easy Array & String

1 Two Sum
HashMap<Integer, Integer>, (key: num, value: index)
if containsKey(nums[index]), get(nums[i])
else put (target - nums[index], index)
Time: O(n), Space: O(n)

20 Valid Parentheses
Stack<Character>
Time: O(n), Space: O(n)

242 Valid Anagram
use ASCII array as a hashmap, iterate through both strings, values in the array should be 0 at the end
Time: O(n), Space: O(1)

771 Jewels and Stones
Use ASCII array as a hashmap, A-65 to z-122
Time: O(n), Space: O(1)

189 Rotate Array
Split the array into two arrays at index k, reverse both arrays, combine and reverse the whole array
if(k>=len){
    k = k % len;
}
Time: O(n), Space: O(1)

387 First Unique Character in a String
Use ASCII array as a hash map, the value of the array is the count number of the character.
Time: O(n), Space: O(1)

167 Two Sum II - Input array is sorted
Use two pointers
Time: O(n), Space: O(1)

118 Pascal's Triangle
Use two List to store previous row and current row of the triangle
List<List<Integer>> result = new ArrayList<> ();
Time: O(k^2), Space: O(k^2)

119 Pascal's Triangle II
Use two array, Same as 118 Pascal's Triangle
Note: Could you optimize your algorithm to use only O(k) extra space?
1
11
121
1331
14641
Use only one array, add 1 at the end for each round, iterate through the array from right to left, add the previous two number row[j] =  row[j] + row[j-1]
Time: O(k^2), Space: O(k)

682. Baseball Game
Use an array to store the previous round’s point, use an index to keep track of current round
string to int: Integer.parseInt(ops[i]);
Time: O(n), Space: O(n)

2/5/2018
Amazon Questions 5题easy Linked List

206 Reverse Linked List

Use current, prev and next to reverse

while(current != null){

    next = current.next;

    current.next = prev;

    prev = current;

    current = next;

}

Time: O(n), Space: O(1)

21 Merge Two Sorted Lists

Create a extra node for the head of the merged list

Time: O(n), Space: O(1)

141 Linked List Cycle

Two pointers

while(fast != null && fast.next != null){

    slow = slow.next;

    fast = fast.next.next;

    if(fast == slow){

        return true;

    }

}

Time: O(n), Space: O(1)

234 Palindrome Linked List

Get the length of the linked list, split in half, reverse the second half, compare with the first to see if the lists are identical

Time: O(n), Space: O(1)

160 Intersection of Two Linked Lists

Solution 1: Get the length of both linked lists, if different, move the start pointer forward to the same length, check if the node are the same node

Solution 2: Iterate both linked lists, so the total length should be the same

For the end of first iteration, we just reset the pointer to the head of another linked list

For the second iteration, the pace is the same, as they are the same length and compare the node and find the intersection

If no intersection, after iterating both list and it will stop at null.

Time: O(n), Space: O(1)