LeetCode

Question 1

(31) Decode Ways

Answer 1

DP. Check previous 1 and previous 2 positions.

Question 2

(39) Remove Nth Node From End of List

Answer 2

two pointer, faster one is N position beyond the slower one, move both pointer until faster reach the end, then remove the element the slower one points at

Question 3

(41) Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

Answer 3

O(N): minus divisor and compare with dividend
log(N):
1. divisor bit shift left (consider the shifted value as radix, store it to vector) until just less than dividend
2. iterate the vector and find the result

Question 4

(42) Search in Rotated Sorted Array

No duplicates

Answer 4

binary search, need to compare A[mid] to A[first].
if current item == target item: return
elif first item < current item:
if first item < target item < current item: search left
else: search right
else:
if current item < target item < last item: search right
else: search left

Question 5

(43) Search for a Range
Given a sorted array of integers, find the starting and ending position of a given target value in O(log n).

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

Answer 5

implement Binary search upper and lower bound

func: upper bound
if A[mid]==target, make sure A[mid+1]>target.
func: lower bound
if A[mid]==target, make sure A[mid-1]

Question 6

(44) Combination Sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Given A=[2,3,6,7] and target is 7, solution set is [[7], [2,2,3]]

Answer 6

dfs(Candidate, target, intermediate, result, currVal)

intermediate: track the current solution
result: store the final result
currVal: make sure ascending order

Question 7

(83) Combination Sum

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

For example, given candidate set 10,1,2,7,6,1,5 and target 8,
Solution: [[1, 7], [1, 2, 5], [2, 6], [1, 1, 6]]

Answer 7

sort + dfs
dfs(Candidate, target, intermediate, result, nextIdx)

nextIdx: make sure Candidate number is used only once

Question 8

(45) Multiply Strings

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

Answer 8

big int multiplication, be careful with overflow

1. reverse string, work from least significant digit
2. maintain a vector cumulating the product of current digit: d[i+j] = n1[i] * n2[j]
3. scan d and obtain final digit with carry over
4. trim leading zeros

Question 9

(47) N-Queens

Answer 9

dfs 
    vector of current state of quees: A[row] = col
    isValid method:
        def isValid(self, r, c):
            for j in range(self.N):
                # for every item in A, check if it is valid w.r.t. (r,c)
                if self.A[j] == c or abs(c - self.A[j]) == abs(r - j):
                    return False
            return True
    core dfs 
    def nQueens(self, r):
        for i in range(self.N):
            if self.isValid(r, i):
                self.A[r] = i
                if r == self.N - 1: 
                    self.saveResult()
                else:
                    self.nQueens(r + 1)
                # backtracking: return to the previous state
                self.A[r] = sys.maxint

Question 10

(54) Search a 2D Matrix

This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
Given target = 3, return true.

Answer 10

consider the matrix as a sorted list, binary search, compute the row and col from mid

Question 11

(55) Search in Rotated Sorted Array II

List has duplicates

Answer 11

compare A[left] to A[mid]:
if A[left] < A[mid]: (left half is sorted)
check if A[left] < A[mid]:
elif A[left] > A[mid]: (right half is sorted)
check if A[mid] < A[right]:
else: (we don’t know which half is sorted, just drop first item of the list, re-search)
left += 1

Question 12

(57) Remove Duplicates from Sorted List

Given 1->1->2, return 1->2.

Answer 12

2 pointers

Question 13

(56) Given 1->1->1->2->3, return 2->3.

Answer 13

recursion

Question 14

(58) Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

Answer 14

leftDummy and rightDummy are init to be floating ListNode

    for every node that curr points at:
        if curr.val

Question 15

(59) Restore IP Addresses

Given “25525511135”,

return [“255.255.11.135”, “255.255.111.35”]. (Order does not matter)

Answer 15

dfs(s, currRes, res, step):
only 4 step is permitted

    def isValid(self, s):
        if s == '0': return True
        elif s[0] != '0' and (0 < int(s) and int(s) <= 255): return True
        else: return False