77. Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

For example,
If n = 4 and k = 2, a solution is:
[
　　[2,4],
　　[3,4],
　　[2,3],
　　[1,2],
　　[1,3],
　　[1,4],
]

76. Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = “ADOBECODEBANC”
T = “ABC”
Minimum window is “BANC”.

Note:
If there is no such window in S that covers all characters in T, return the empty string “”.
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

75. Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library’s sort function for this problem.

74. Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n 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.

For example,
Consider the following matrix:
[
　　[1, 3, 5, 7],
　　[10, 11, 16, 20],
　　[23, 30, 34, 50]
]
Given target = 3, return true.

73. Set Matrix Zeroes

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

Follow up:
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?

72. Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character

71. Simplify Path

Given an absolute path for a file(Unix - style), simplify it.

For example,
path = “/home/“, = > “/home”
path = “/a/./b/../../c/“, = > “/c”

67. Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = “11”
b = “1”
Return “100”.

66. Plus One

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.

64. Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.