Remove Nth Node from End of List

Problem

Given a linked list, remove the nth node from the end of list and return its head.

For example,

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Try to do this in one pass.

---

Idea

• 创建一个node 使得node->next = head
• 创建两个指针frontP和rearP,初始值都为node
• 先让rearP往前移动n次，然后再同时移动frontP和rearP，直到rearP到的链表尾
• 这时frontP->next就是你要删除的节点了

---

Solution

---

Rotate List

Problem

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

---

Idea

k有可能超过链表的长度，所以先扫一遍得到链表的长度len，然后rotate的实际值是k%len

还是构造一个新的list, 先在旧list中找到新list的第一个node (pivotNode)

然后把从pivotNode 到 最后的所有节点挪到新list里

再把旧list中head到pivotNode的所有节点挪到新List里

---

Solution

---

Partition List

Problem

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.

You should 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.

---

Idea

• Create another linked list. Firstly, put all node < x into the new list. Then put all nodes >x into the new list.

---

Solution

---

Reverse Linked List 2

Problem

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

---

Idea

用两个pointer front 和 rear 分别指向 第m和第n元素，思路就是把m到n-1的元素加到n后面，然后把m到n-1删掉。 用个例子说明吧
1->2->3->4->5 m=2,n=4

• 1->2->3->4->2->5
• 1->2->3->4->3->2->5
• 1->4->3->2->5

---

Solution

---

Add Two Numbers

Problem

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

---

Idea

• 要考虑到两个Number可能长短不一
• 要考虑到最高位可能产生的进位

---

Solution

---

Special Cases

• {2,8,9,9,9,9,8,9,9,9}, {8,1,2} // 有可能不一样长啊

Single Number ||

Problem

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

---

Idea

这是个数学题，使用两个变量one和two 的各个位来映射数组中每个元素的各个位，one代表出现1次，two代表出现了2次。See the following code

---

Solution

---

Candy

Problem

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?

---

Idea

• 第一步: 给每个小孩一个糖
• 第二步: 从左往右，只比较child i 和 child i-1， 如果 rating[i] > rating[i-1] && candy[i] < candy[i-1] 那么 candy[i] = candy[i-1]+1
• 第三步: 从右往佐, 只比较child i和child+1, 如果rating[i] > rating[i+1] && candy[i] < candy[i+1] 那么candy[i] = candy[i+1]+1

---

Solution

---

Gas Station

Problem

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

Note:
The solution is guaranteed to be unique.

---

Idea

• 暴力解法， 对于每一个起点，用两个变量curInde和nextIndex来跑，看看能不能跑到起点

---

Solution

---

Set Matrix Zeroes

Problem

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

---

Idea

• 先扫一边矩阵，然后用数组记录每一行是否有非0元素，再按照数组存储的情况来update矩阵 (可是这个方法需要O(m+n)的空间)
• 一个更省空间的方法是使用matrix的第一行和第一列来记录该行与该列是否需要被清零。但是首先要扫描第一行与第一列是否要清零，然后当其他行都处理完以后，再回来处理第一行与第一列。

---

Note

• 多维vector如何判断行的大小和列的大小

Solution

---

Gray Code

Problem

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2
Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

---

Idea

• 自然二进制码转换为格雷码:g0 = b0 , gi = bi ⊕ bi−1

保留自然二进制码的最高位作为格雷码的最高位,格雷码次高位为二进制码的高位与次高位异 或,其余各位与次高位的求法类似。例如,将自然二进制码 1001,转换为格雷码的过程是:保留最 高位;然后将第 1 位的 1 和第 2 位的 0 异或,得到 1,作为格雷码的第 2 位;将第 2 位的 0 和第 3 位 的 0 异或,得到 0,作为格雷码的第 3 位;将第 3 位的 0 和第 4 位的 1 异或,得到 1,作为格雷码的 第 4 位,最终,格雷码为 1101。

• 格雷码转换为自然二进制码:b0 = g0 , bi = gi ⊕ bi−1

保留格雷码的最高位作为自然二进制码的最高位,次高位为自然二进制高位与格雷码次高位异 或,其余各位与次高位的求法类似。例如,将格雷码 1000 转换为自然二进制码的过程是:保留最高 位 1,作为自然二进制码的最高位;然后将自然二进制码的第 1 位 1 和格雷码的第 2 位 0 异或,得 到 1,作为自然二进制码的第 2 位;将自然二进制码的第 2 位 1 和格雷码的第 3 位 0 异或,得到 1, 作为自然二进制码的第 3 位;将自然二进制码的第 3 位 1 和格雷码的第 4 位 0 异或,得到 1,作为 自然二进制码的第 4 位,最终,自然二进制码为 1111。
• 格雷码有数学公式,整数 n 的格雷码是 n ⊕ (n/2)。
• 其实这题让求n bit的所有格雷码,也就是算0-2^n-1里所有整数转换成的格雷码。

---

Solution

---

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

Rotate Image

Problem

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

---

Idea

The idea is to swap the matrix twice. Check here for how to swap.

---

Solution

3Sum

Problem

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

Note:
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.

For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)

---

Idea

• 先排序，然后假定第一个元素，让这个元素start从num[0]到num[n-2]遍历。
• 采用两边夹逼的方法，定义两个变量，mid 和 end. 比较start+mid+end和0的关系，若小于0则mid++，大于0则end--

---

Note

• vector<vector<int> > a的用法
首先这个多维的数组被写做 vector<vector<int>空格>. 其实是描述了一个二维数组/矩阵 a。其初始化可以参考下面的代码
• Sort the vector by STL

---

Solution

---

Permutation Sequence

Problem

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3):
"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

---

Idea

• 这个题目的思路就是对于这个n位数的排列组合，从最高位到最低位分别确定第kth个数的每一位分别是多少，然后将每一位整合起来。得到那个kth数。可是如何判断每一位是多少呢？
• 以最高位（第n位）为例，最高位有n种情况，每一种情况中，从1到n-1位有（n-1)!种情况，这样，这个n位数的排列组合就被分成了n份，每一份包含了（n-1)!种组合。依次类推若第n位和第n-1都确定，则剩下的排列组合被分成了（n-2)!种情况。
• 若n=6 [1,2,3...,6] k=250, 首先确定最高位，此时排列组合可被分为6份，每份有5!=120. k/120= 250/120 = 2, 所以k在第三组，我们可以得出最高位为3.剩下的set为[1,2,4,5,6]，这时我们要更新k，因为剩下的数是在[1-120]之间了， k=k%5!＝10. 接下来确定第5位，每份有4!=24个组合，则10/24=0，所以k在第1组，这时set中第一个元素为1，所以第5位为1.接下来更新k然后继续上面的步骤，直到确定所有位。

---

Note

• How to add a digit number into string

Solution

---

Two Sum

Problem

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

---

Idea

• Hash Table
• Use a hashtable to record the index for each element in numbers[]
• For each element number[i] check if target-number[i] is in the hashtable
• Must be sure number[i] appear twice in numbers[] when number[i] == target-number[i]
• Sort

---

Solution

---

Special Cases

• [0,4,3,0], target = 0
• [3,2,4], target = 6
（3 must be checked if another 3 is in numbers[])

---

Remove Element

Problem

Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn't matter what you leave beyond the new length

---

Ideas

The problem is a little difficult to understand (my poor English - -!). if A[]={1,2,2,3} elem:2, you should return 2 and A[] = {1,3}.

---

Solution

---

Longest Consecutive Sequence

Problem

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

---

Idea

• Use a hash map to record each element in array num. The value is bool that indicates if the num[i] is checked
• If the element is checked, then continue.
• For each unchecked element in hash map, we change any consecutive elements (both > num[i] and < num[i]) as checked.
• Use local and global parameter to record the longest consecutive sequence

---

Notes

• A method to traverse the array
• A similar method to traverse the vector

---

Solution

Search in Rotated Sorted Array II

Problem

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

---

Idea

允许重复元素,则上一题中如果 A[m]>=A[l], 那么 [l,m] 为递增序列的假设就不能成立了,比如 [1,3,1,1,1]。
如果 A[m]>=A[l] 不能确定递增,那就把它拆分成两个条件:

• 若 A[m]>A[l],则区间 [l,m] 一定递增
• 若 A[m]==A[l] 确定不了,那就 l++,往下看一步即可。

---

Solution

---

Special Cases

• {1,3,1,1,1} 3
• {1} 0

Remove Duplicates from Sorted Array II

Problem

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],
Your function should return length = 5, and A is now [1,1,2,2,3].

---

Idea

The idea is the same as Remove Duplicates from Sorted Array. We just use one parameter to record how many duplicates have happen.

---

Solution

Median of Two Sorted Arrays

Problem

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

---

Idea1

• If m+n is old (奇数), the median is the number located in position (m+n)/2 of the array (A+B)
• If m+n is even (偶数), the median is the average of element in (m+n)/2 -1 and element in (m+n)/2
• So you need to judge if the m+n is old or even. Then, The problem is find the kth biggest element in array(A+B).
• After you decide the old and even of m+n, the idea of solution is to find the kth element in the array (A+B).

---

Idea2

• The idea is like Merge operation in CLRS. Retrieve the minimal element in A[] and B[] until you reach the median (Maybe two numbers for even case). Complexity is O(m+n)
• We need to carefully treat the cases when A[] is empty or B[] is empty at the beginning
• Use two parameter "front" , "rear" to record two elements for even case. And "rear" for old case.
• During the procedure to find the minimal element in A[]+B[]. You may meet the following cases
• Either A[] or B[] become empty, we just use the other sequence
• If A[] and B[] are non-empty, we will choose the smaller one.

---

Solution

This solution is for Idea2:

Remove Duplicates from Sorted Array

Problem

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

---

Idea

• Index always point to the last element without duplicates
• Use another index traverse the array from 1

---

Solution

---

Search in Rotated Sorted Array

Problem

Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.

---

Ideas

• http://www.cnblogs.com/TenosDoIt/p/3465240.html

这个思路关注于搜索rotated的subarray. 思路是使用二分查找：在常规情况下，当target > A[mid]时， 应该开始查找数组的后半段，即left = mid+1; 当target < A[mid]时，应该查找数组的前半段，即right = mid-1; 而此题中，当target > A[mid]时，也可能搜索数组的前半段，如：7 8 1 2 3 4 5 （target：8）当target < A[mid]时，也可能搜索数组的后半段，如： 4 5 6 7 8 1 2 （target:2)。下面来分类讨论这两种特殊情况出现的条件。 这两种情况中target都在rotated的数组中。

• target < A[mid]时，搜索后半段必须同时满足以下条件
• A[left] > A[right]          // 表明搜索的边界落在rotated subarray
• target <= A[right]          // target 可能在unrotated的数组的前半部分
• A[right] < A[mid]          // A[mid]在unrotated数组的后半部分,换言之,rotate的点靠近left
我们可以根据上述条件还原rotated前的数组 ... target... A[right].... Middle.... A[mid], 仔细看其实条件就是 A[left] > A[right] (rotated) && target <= A[right] < A[mid]
• target > A[mid]时，搜索前半段
• A[left] > A[right]          // 表明搜索的边界落在rotated subarray
• target > A[right]          // 表明target在unrotated数组的后半部分
• A[mid] < A[right]          // 表明A[mid]在unrotated数组的前半部分，换言之，rotate的点靠近right
unrotated的数组应该是 ... A[mid].... Middle....A[right]....target.....

---

Solution

Another easy idea to understand. This method only focus on searching the unsorted subarray.

---

Special Cases

---

Remove Duplicates from Sorted List II

Problem

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

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

---

Idea

• Add a dummy node before head
• We operate on Node "head"
• head and head->next is always pointing the node without any duplicates.

---

Note

Data Structure Definition

---

Solution

---

Special Cases

• {1,1}
• {1,1,1}
• {1,1,2,2}

---

Remove Duplicates from Sorted List

Prbolem

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3

---

Ideas

Use nested loops to solve the problem. One loop is used to find the different node.

---

Note

Data Structure Definition

• Don't use delete to remove useless node.
• Don't define two pointer for current node and next node because it's difficult to handle the last node.

---

Solution

---

Special Case

• {1,1}
• {1,1,1}
• {1}