Insert Interval Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times. Example 1: Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9]. Example 2: Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and […]
Merge Intervals Given a collection of intervals, merge all overlapping intervals. For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18]. 10/7/2015 update Runtime error, quite strange. I don’t figure out why yet. /** * Definition for an interval. * struct Interval { * int start; * int end; * Interval() : start(0), end(0) […]
Substring with Concatenation of All Words You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters. For […]
Jump Game 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. Determine if you are able to reach the last index. For example: A = [2,3,1,1,4], return true. A […]
Spiral Matrix Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order. For example, Given the following matrix: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] You should return [1,2,3,6,9,8,7,4,5]. […]
Sqrt(x) Implement int sqrt(int x). Compute and return the square root of x. 惭愧，看了tag才知道需要用binary search。 二分查找，需要注意把x改为long long以免数据溢出。 另外，一个正数的平方根只能在[1, x / 2 + 1)之间变动。 class Solution { public: int sqrt(int x) { if(x < 2) return x; return _sqrt(x, 1, x / 2 + 1); } //[start, end) int _sqrt(int x, […]
Maximum Subarray Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has the largest sum = 6. click to show more practice. More practice:If you have figured out the O(n) solution, try […]
Permutations II Given a collection of numbers that might contain duplicates, return all possible unique permutations. For example, [1,1,2] have the following unique permutations: [1,1,2], [1,2,1], and [2,1,1]. 跟PermutionsI类似，不过需要去重。 思路是先对原数组排序，然后在循环开始时，跳过重复元素。 class Solution { public: vector<vector<int> > permuteUnique(vector<int> &num) { vector<vector<int>> re; vector<int> thisRe; sort(num.begin(), num.end()); DFS(num, re, thisRe); return re; […]
Permutations Given a collection of numbers, return all possible permutations. For example, [1,2,3] have the following permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1]. 深搜DFS。注意参数需要传引用。 class Solution { public: vector<vector<int> > permute(vector<int> &num) { vector<vector<int>> re; vector<int> thisRe; DFS(num, re, thisRe); return re; } void DFS(vector<int> &num, vector<vector<int>> &re, vector<int> […]
Convert Sorted Array to Binary Search Tree Given an array where elements are sorted in ascending order, convert it to a height balanced BST.a 简单的深搜问题。 每次取mid=(start + end) / 2; 然后以num[mid]为root，深搜root->left, 和root->right。 复杂度o(n) /** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * […]
