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 […]

Path Sum II Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum. For example: Given the below binary tree and sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 […]

Jump Game II Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps. For example: Given […]

Sudoku Solver Write a program to solve a Sudoku puzzle by filling the empty cells. Empty cells are indicated by the character ‘.’. You may assume that there will be only one unique solution. A sudoku puzzle… …and its solution numbers marked in red. 深搜加回溯剪枝。 class Solution { public: void […]

Combination Sum II Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. Each number in C may only be used once in the combination. Note: All numbers (including target) will be positive integers. Elements […]

First Missing Positive Given an unsorted integer array, find the first missing positive integer. For example, Given [1,2,0] return 3, and [3,4,-1,1] return 2. Your algorithm should run in O(n) time and uses constant space. 关键是只允许常数空间。这里要突破思维定势，要改变给定数组的结构。 对于A[i]，如果A[i] > 0 && A[i] <= n，则将它与A[i] – 1 位置的元素互换位置。 遍历一遍后，再从左到右找到第一个A[i] != i + […]

Merge Two Sorted Lists Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. 简单题，归并排序即可。 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * […]

Trapping Rain Water 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. The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units […]

Search Insert Position Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. Here are few examples. [1,3,5,6], 5 → 2 […]

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], ] tag: backtracking 回溯问题，用递归求解就好。 class Solution { public: vector<vector<int> > combine(int […]