Haiyang Yu's Blog

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Note:

• Division between two integers should truncate toward zero.
• The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation.

Example 1:

1
2
3

Input: ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

1
2
3

Input: ["4", "13", "5", "/", "+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

1
2
3
4
5
6
7
8
9
10

Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
Output: 22
Explanation: 
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

1
2
3
4
5
6
7
8

1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB 
...

Example 1:

1
2

Input: 1
Output: "A"

Example 2:

1
2

Input: 28
Output: "AB"

Example 3:

1
2

Input: 701
Output: "ZY"

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

• The same word in the dictionary may be reused multiple times in the segmentation.
• You may assume the dictionary does not contain duplicate words.

Example 1:

1
2
3

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

1
2
3
4

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
             Note that you are allowed to reuse a dictionary word.

Example 3:

1
2

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

Given two strings s\ and t\, determine if they are isomorphic.

Two strings are isomorphic if the characters in s\ can be replaced to get t\.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

Example 1:

1
2

Input: s = "egg", t = "add"
Output: true

Example 2:

1
2

Input: s = "foo", t = "bar"
Output: false

Example 3:

1
2

Input: s = "paper", t = "title"
Output: true

Note:
You may assume both s\ and t\ have the same length.

Given an integer n, write a function to determine if it is a power of two.

Example 1:

1
2
3

Input: n = 1
Output: true
Explanation: 20 = 1

Example 2:

1
2
3

Input: n = 16
Output: true
Explanation: 24 = 16

Example 3:

1
2

Input: n = 3
Output: false

Example 4:

1
2

Input: n = 4
Output: true

Example 5:

1
2

Input: n = 5
Output: false

Constraints:

• -231 <= n <= 231 - 1

Given a binary tree, return all root-to-leaf paths.

Note: A leaf is a node with no children.

Example:

1
2
3
4
5
6
7
8
9
10
11

Input:

   1
 /   \
2     3
 \
  5

Output: ["1->2->5", "1->3"]

Explanation: All root-to-leaf paths are: 1->2->5, 1->3

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

Example 1:

1
2

Input: 2
Output: [0,1,1]

Example 2:

1
2

Input: 5
Output: [0,1,1,2,1,2]

Follow up:

• It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
• Space complexity should be O(n).
• Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

Given a singly linked list L: L0→L1→…→L**n-1→Ln,
reorder it to: L0→L**n→L1→L**n-1→L2→L**n-2→…

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example 1:

1

Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

1

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

Given the head of a linked list, return the list after sorting it in ascending order.

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

Example 1:

1
2

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Example 2:

1
2

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Example 3:

1
2

Input: head = []
Output: []

Constraints:

• The number of nodes in the list is in the range [0, 5 * 104].
• -105 <= Node.val <= 105

Sort a linked list using insertion sort.

A graphical example of insertion sort. The partial sorted list (black) initially contains only the first element in the list.
With each iteration one element (red) is removed from the input data and inserted in-place into the sorted list

Algorithm of Insertion Sort:

1. Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.
2. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there.
3. It repeats until no input elements remain.

Example 1:

1
2

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

1
2

Input: -1->5->3->4->0
Output: -1->0->3->4->5