Climbing Stairs

Problem

You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

---

Idea

For each step i, step[i] = step[i-1]+step[i-2];

---

Solution

---

Plus One

Problem

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

---

Idea

From the digits.end() to digits.begin(), check each digit if it is above 10.

---

Note

• How to use .insert() to insert a value in from of position

---

Solution

---

Valid Sudoku

Problem

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules. The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

---

Idea

• Each row must have the numbers 1-9 occuring just once.
• Each column must have the numbers 1-9 occuring just once.
• And the numbers 1-9 must occur just once in each of the 9 sub-boxes of the grid.
• 先检查行，再检查列，再检查每个3*3的cube
• 判断是否重复的方法是讲一行或者一列或者1个3*3放入vector中。 然后再存入hash_map中，利用hash_map的find()!=hash_map.end()来判断是否有重复的 复杂度O(n)

---

Notes

• How to insert hash map
• How to find an element in the hash_map
• How to push/pop an element by vector

Solution

---

Trapping Rain Water

Problem

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

---

Idea

• 找到数组的最高点，并讲数组分成左右两部分
• 左边部分：从左往右扫描，并设置变量记录左边的最大值leftPeak
• 每一条bar的水 ＝ 当前leftPeak - bar
• 右边部分同理，不同的是从右往左扫描

---

Solution

---

Special Case

• (4,2,3)

4Sum

Problem

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)

The solution set must not contain duplicate quadruplets.

For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

A solution set is:
(-1, 0, 0, 1)
(-2, -1, 1, 2)
(-2, 0, 0, 2)

---

Idea

---

Solution

---

3Sum Closet

Problem

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

---

idea

• 仍然采用两边夹逼的方法，即确定一个数start,然后指定end=num.size()-1和mid和start+1.然后根据num[start]+num[mid]+num[end]与target的关系来改变mid和end.让start循环遍历整个num.
• 使用1个变量来记录当前距离target最小的组合
• 不能跳过duplicates的element.

---

Solution

---

Next Permutation

Problem

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

---

Note

• STL 中vector找最小元素

---

Idea

搞清楚输入顺序和数组的顺序 1 2 3 ===> 1 (a[2]), 2(a[1]) 3(a[0])

递归来解. 从最后两个元素开始，如果a[i-1] > =a[i]那么检查再往前的。如果找到a[i-1] < a[i] 找到子树组(a[i] - a.end()) 中第一个大于a[i-1]的元素a[j]，交换 a[j]和a[i-1]， 最后a[i] - a.end()重新排序.

---

Solution