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

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