LeetCode Cheat Sheet – 50 Problems

  • Misc, Python
Tags:

Concepts

Sliding Window

Give n element and k window size, try to get max sum.

Bindary Search

  • Only work when data is sorted

Step:

  1. Use the left and right element as 2 pointers
  2. Find the middle pointer between 2 pointers
  3. Compare the middle element to search term
  4. If middle > search term, replace left pointer with middle pointer + 1
  5. If middle < search term, replace right pointer with middle pointer – 1

Hash Table

  • hash function
  • collusion

collusion handling

  • chaining: make each key point to a linked list, -> easy, never get full, use extra space and search O(N)
  • open addressing: if key exists, probe until available -> more computation(probing), can get full, better performance

If number of keys is unknown, use chain; other wise use open addressing.

probe methods

  • linear probing: probe to next slot
  • quadratic probing
  • double hashing

Linked List

  • head, tail

Compare to array:

  • O(n) searching vs O(1) random access
  • Cheaper insert/delete operation vs shift items

Stack & Queue

  • stack: LIFO, think abount dish plates
  • queue: FIFO, think abount get in line for a concert

Graph

  • direct
  • undirect, bi-directional

Implement with hash map

Implement with adjacency matrixes, The size is restricted.

e.g. number of nodes = 3

Set edge using graph[v1][v2] = 1

DFS

Implement with stack or recursion

BFS

Implement with stack or recursion

Tree

A tree is a 1) connective, 2) acyclic, 3) undirected graph

  • acyclic graph: having no cycles

Terminologies:

  • root

  • parent, child

  • path

  • leaf: no children

  • tree height

  • in-order: left -> root -> right

  • pre-order: root -> left -> right

  • post-order: left -> right -> root

Do know how to implement traversal using stack except recursion.

Binary Tree

  • balance: height of two subtrees never differ by more than 1

Binary Search Tree

  • left < root < right
  • deletion
    • leaf: direct delete
    • node has one child: connect parent to child
    • node has two child: replace with the minimal node which greater than the delete node

Deletion implementation:

Math Problems

Missing Numbers

Find the missing number for given array.

Three approachs:

  1. sort the array and use 2 pointer, if current – previous > 1, the missing number is current – 1
  2. hash map, first iteration to construct true/false values, second iteration to find the false one.
  3. Gauss formula: sum([1,2,..n]) = n*(n+1)/2

Count Primes

A prime is:

  • Greater than 1
  • Non-divisible by anything except 1 and itself

Assume the array is sorted and continuous e.g. [0, 1, 2, 3 … n], the approach:

  1. Construct a boolean array with default value: true
  2. Iter over array until n^2 > array size, update elements to false if the mod n is 0

Single Number

Find the number only appear once.

The approach:

  1. unique the arr items
  2. 2*(a+b+c)-(a+a+b+b+c)=c

Space complexity: O(N), due to usage of set

Add Binary

The approach: seperate pointer for each input

String Problems

Move Zeros (in-place)

Move all 0’s to the end and maintain the order.

The approach: Think abount moving the non-zeros to front.

Boats to Save People

The approach:

  1. sort the array
  2. group the heaviest and lightest together using 2 pointer

Time complexity: O(N*Log(N))

Space complexity: O(N), sorting

Valid Mountain Array

Find if there is an increasing subarray followed by a decreasing subarray.

The approach: Construct a pointer start from index 1, compare to previous element.

Container with Most Water

The approach: 2 pointer (left, right), compare the left and right height, the smaller moves.

Longest Substring without Repeat Characters

The approach: 2 pointer start at 0 and a hash map to track character last shown position.

Move the right pointer if character does not exists, else move the left pointer to last shown position + 1.

Find First and Last Position of Element in Sorted Array

“When you see sorted array, think abount binary search.”

First Bad Version

“When you see sorted array, think abount binary search.”

Hash Map Problems

Two Sum

Majarity Element

Group Anagrams

Hash function: sorted string

Time Complexity: O(N * M * Log(M)), M * Log(M) is sorting effort

  • N: input array
  • M: Longest word in array

4 Sum 2

Time complexity: O(N^2)

LRU Cache

  • move key to front for all operations: get / put

Linked List Problems

Merge Two Sorted Lists

Linked List Cycle

The approach: turtle and hare

Reverse Linked List

The approach: keep tracking the previous node

Add Two Numbers

Remove Nth Node from Linked List

The approach: Use two pointer (left, right), the distance between left and right is given n.

The trick is set left pointer start from NULL.

e.g. n=2

Odd Even Linked List

Backtracking / Recursion Problems

Subset

A set contains n items has 2^n subset (each pick or not pick)

Letter Combinations of Phone Number

Word Search

Graph / Tree Problems

Is Symmetric Tree

Max Depth

Path Sum

Stack / Queue Problems

Level Order Traversal

“When you see level by level, think abount BFS.”

Binary Tree Zigzag Level Order Traversal

Binary Tree Post Order Traversal (with stack)

Dynamic Programming Problems

How do you know it is a DP problem?

  1. if problem is recursive
  2. a lot of repeated states

Two approachs:

  1. top down
  2. button top

House Robber

The approach: Calculate max amount from button-top.

Best Time to Buy and Sell Stock

Climbing Stairs

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。