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; * […]
Rotate Image 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? 在o(1)space中把题解掉。 思路是每次计算一个像素旋转后所到达的位置，发现四个像素构成了一个旋转的回路。于是只要存储这些像素的值，进行旋转即可。 需要注意循环的起止点。 class Solution { public: void rotate(vector<vector<int> > &matrix) { int n = matrix.size(); for(int i = 0; i < […]
Anagrams Given an array of strings, return all groups of strings that are anagrams. Note: All inputs will be in lower-case. anagrams变位词。 如：eat和tea，字母相同，只是排列顺序不同。 思路，用hashtable，先对string中的字母进行排序，这样所有的变位词都会变得相同。在hashtable中为一个入口，再利用unordered_map<string, MyStr>进行构建，需要注意，如果是第一次遇见相同的变位词的话，需要把当前str和在hashtable中的str都压入结果vector中。 class MyStr{ public: string str; bool isVisited; MyStr(string s, bool a):str(s),isVisited(a){} MyStr(){} }; class Solution { public: vector<string> anagrams(vector<string> &strs) { unordered_map<string, MyStr> h; vector<string> […]
Unique Binary Search Trees Given n, how many structurally unique BST’s (binary search trees) that store values 1…n? For example, Given n = 3, there are a total of 5 unique BST’s. 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / […]
Subsets Given a set of distinct integers, S, return all possible subsets. Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets. For example, If S = [1,2,3], a solution is: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ] 深搜DFS。 […]
Word Search Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once. For example, […]
Partition List 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 […]
