Posts

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water. Note: You may not slant the container and n is at least 2. 题意：n条竖直的线段 (i,0)->(i,a[i])，从中选2条，和x轴共同组成一个开口的容器，问容器的最大面积。

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution. 思路： 排序，然后two pointer，复杂度 O(n^2) 1/* *********************************************** 2Author :111qqz 3Created Time :2017年04月13日 星期四 16时24分28秒 4File Name :16.cpp 5************************************************ */ 6class Solution { 7 8public: 9 10 int n; 11 int threeSumClosest(vector<int>& nums, int target) { 12 n = nums.size(); 13 sort(nums.begin(),nums.end()); 14 int mn = 0x3f3f3f3f; 15 int x,y,z; 16 for ( int i = 0 ; i <=n-3 ; i++) 17 { 18 int head = i+1; 19 int tail = n-1; 20 int tar = target - nums[i]; 21 while (head<tail) 22 { 23 int cur = target-nums[i]-nums[head]-nums[tail]; 24 if (abs(cur)<mn) 25 { 26 mn = abs(cur); 27 x = nums[i]; 28 y = nums[head]; 29 z = nums[tail]; 30 } 31 if (nums[head]+nums[tail]==tar) return target; 32 if (nums[head]+nums[tail]<tar) head++; 33 else tail--; 34 } 35 } 36 return x + y + z; 37 38 39 40 41 } 42 43};

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target. Note: The solution set must not contain duplicate quadruplets. 思路： O(n^2)枚举两个元素，变成2-sum问题，总体复杂度O(n^3)

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: The solution set must not contain duplicate triplets. 思路：排序O(nlgn)，然后枚举一个元素O(n)，对于每个元素，在剩下的区间中 two pointer O(n)

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers. 题意：1..9个数，从中选择k个，和为n，要求输出所有满足题意的集合。 思路：枚举子集，根据sum和集合元素个数剪枝即可。

Given two integers n and k, return all possible combinations of k numbers out of 1 … n. 思路：就是枚举子集，根据集合的大小剪枝。。。最后只要集合大小为k的集合 1/* *********************************************** 2Author :111qqz 3Created Time :2017年04月13日 星期四 15时25分37秒 4File Name :77.cpp 5************************************************ */ 6class Solution { 7public: 8 set<vector<int> >se; 9 int B[1005]; 10 vector<vector<int> >res; 11 void get_subset(int n,int *B,int cur,int cnt,int k) 12 { 13 if (cur==n) 14 { 15 vector<int>tmp; 16 for ( int i = 0 ; i < n ; i++) 17 if (B[i]) tmp.push_back(i+1); 18 if (tmp.size()==k) 19 se.insert(tmp); 20 return ; 21 } 22 if (cnt<k) 23 { 24 B[cur] = 1; 25 get_subset(n,B,cur+1,cnt+1,k); 26 } 27 B[cur] = 0 ; 28 get_subset(n,B,cur+1,cnt,k); 29 } 30 vector<vector<int>> combine(int n, int k) { 31 get_subset(n,B,0,0,k); 32 for (auto &it:se) 33 { 34 res.push_back(it); 35 } 36 return res; 37 } 38};

The set [1,2,3,…,_n_] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3): 1. `"123"` 2. `"132"` 3. `"213"` 4. `"231"` 5. `"312"` 6. `"321"` Given n and k, return the _k_th permutation sequence. Note: Given n will be between 1 and 9 inclusive. 思路：还是根据leetcode 31 解题报告 中的算法搞一下就好了。。

Given a collection of numbers that might contain duplicates, return all possible unique permutations.__ 思路：和leet code 46 类似，最后用set去个重即可。。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2017年04月13日 星期四 15时00分48秒 4File Name :47.cpp 5************************************************ */ 6class Solution { 7 8public: 9 void solve( vector<int>&nums) 10 { 11 int n = nums.size(); 12 if (n==0) return; 13 int k = -1; 14 for ( int i = n-2 ; i >= 0 ; i--) 15 { 16 if (nums[i]<nums[i+1]) 17 { 18 k = i; 19 break; 20 } 21 } 22 if (k==-1) 23 { 24 reverse(nums.begin(),nums.end()); 25 return; 26 } 27 int l = -1; 28 for ( int i = n-1 ; i >k ; i--) 29 { 30 if (nums[k]<nums[i]) 31 { 32 l = i; 33 break; 34 } 35 } 36 swap(nums[l],nums[k]); 37 reverse(nums.begin()+k+1,nums.end()); 38 } 39 40 void pr (vector<int> &nums) 41 { 42 int siz = nums.size(); 43 for ( int i = 0 ; i < siz; i++) 44 printf("%d%c",nums[i],i==siz-1?'\n':' '); 45 } 46 vector<vector<int>> permuteUnique(vector<int>& nums) { 47 set<vector<int> >se; 48 vector<vector<int> >res; 49 int n = nums.size(); 50 int total = 1 ; 51 for ( int i = 2 ; i <= n ; i++) total*=i; 52 53 for ( int i = 1 ; i <= total ; i++) 54 { 55 se.insert(nums); 56// pr(nums); 57 solve(nums); 58 } 59 for ( auto &it :se) 60 { 61 res.push_back(it); 62 } 63 return res; 64 } 65 66};

Given a collection of distinct numbers, return all possible permutations. 思路：调用n-1次 leetcode 31 解题报告 中提到的算法即可。。。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2017年04月13日 星期四 14时49分34秒 4File Name :46.cpp 5 ************************************************ */ 6class Solution { 7 8 public: 9 10 void solve(vector<int> &nums) 11 { 12 int n = nums.size(); 13 if (n==0) return; 14 int k = -1; 15 for ( int i = n-2 ; i >= 0 ; i--) 16 { 17 if (nums[i]<nums[i+1]) 18 { 19 k = i ; 20 break; 21 } 22 } 23 if (k==-1) 24 { 25 reverse(nums.begin(),nums.end()); 26 return; 27 } 28 int l = -1; 29 for ( int i = n-1 ; i > k ; i-- ) 30 { 31 if (nums[k]<nums[i]) 32 { 33 l = i ; 34 break; 35 } 36 } 37 swap(nums[l],nums[k]); 38 reverse(nums.begin()+k+1,nums.end()); 39 } 40 vector<vector<int>> permute(vector<int>& nums) { 41 vector<vector<int> >res; 42 int n = nums.size(); 43 int total = 1; 44 for ( int i = 2 ; i <= n ; i++) total*=i; 45 for ( int i = 1 ; i <= total; i++) 46 { 47 res.push_back(nums); 48 solve(nums); 49 } 50 51 return res; 52 } 53 54};

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). The replacement must be in-place, do not allocate extra memory. Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column. 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1 思路： 参考了wiki_Permutation

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. 思路：找规律。。。二分。。。 0 1 2 3 4 5 6 1 2 3 4 5 6 0 2 3 4 5 6 0 1 3 4 5 6 0 1 2 4 5 6 0 1 2 3 5 6 0 1 2 3 4 6 0 1 2 3 4 5 观察发现。。。a[mid]<a[r]的时候，后半段有序；

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value. Your algorithm’s runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1]. For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4]. 思路：二分。。。 我好像根本不会二分啊？？？ 二分查找

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. The same repeated number may be chosen from C unlimited number of times. Note: * All numbers (including target) will be positive integers. * The solution set must not contain duplicate combinations. 题意：给n个数，求所有的组合，和为定值，每个数可以重复用)

* Total Accepted: **106670** * Total Submissions: **329718** * Difficulty: **Medium** * Contributor: **LeetCode** 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. * The solution set must not contain duplicate combinations. 题意：若干正数，求所有和为target的组合。

In LLP world, there is a hero called Teemo and his attacking can make his enemy Ashe be in poisoned condition. Now, given the Teemo’s attacking ascending time series towards Ashe and the poisoning time duration per Teemo’s attacking, you need to output the total time that Ashe is in poisoned condition. You may assume that Teemo attacks at the very beginning of a specific time point, and makes Ashe be in poisoned condition immediately. 题意：若干长度相同的区间，升序给出区间左端点，以及区间长度。问区间被覆盖的长度总和。

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements that appear twice in this array. Could you do it without extra space and in O(n) runtime? 思路：还是一个映射，如果某个位置要映射的时候已经为负了，就说明之前映射过该位置，那么该位置对应的元素就是出现了两个的元素。

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? 题意：给一个n*n的方阵，要求顺时针旋转90度。 思路：(x,y)->(y,n-1-x); 要求in-place的做法的话，其实是若干长度为4的环，保护一个节点，然后顺次做就好了。

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order. 思路：。。。再次让我回想起高一的暑假。。。。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2017年04月11日 星期二 19时42分05秒 4File Name :54.cpp 5************************************************ */ 6class Solution { 7public: 8 int n,m; //0右，1下，2左，3上 9 int cal( int &x,int &y,int dir,vector<vector<bool> > & vis) 10 { 11 if (dir==0) 12 { 13 if (y<=n-2&&!vis[x][y+1]) y++; 14 else 15 { 16 dir++; 17 x++; 18 } 19 return dir; 20 } 21 if (dir==1) 22 { 23 if (x<=m-2&&!vis[x+1][y]) x++; 24 else 25 { 26 dir++; 27 y--; 28 } 29 return dir; 30 } 31 if (dir==2) 32 { 33 if (y>=1&&!vis[x][y-1]) y--; 34 else 35 { 36 dir++; 37 x--; 38 } 39 return dir; 40 } 41 if (dir==3) 42 { 43 if (x>=1&&!vis[x-1][y]) x--; 44 else 45 { 46 dir = 0 ; 47 y++; 48 } 49 return dir; 50 } 51 } 52 vector<int> spiralOrder(vector<vector<int>>& matrix) { 53 vector<int>res; 54 m = matrix.size(); 55 if (m==0) return res; 56 n = matrix[0].size(); 57 if (n==0) return res; 58 vector<vector<bool> >vis(m,vector<bool>(n,false)); 59 int x,y,dir; 60 x = y = dir = 0 ; 61 for ( int i = 0 ; i < n*m ; i++) 62 { 63 printf("x:%d y:%d\n",x,y); 64 res.push_back(matrix[x][y]); 65 vis[x][y] = true; 66 dir = cal(x,y,dir,vis); 67 } 68 return res; 69 } 70};

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]. 思路：dp[i]表示能否到达位置i…无脑dp即可。。。 1/* *********************************************** 2Author :111qqz 3Created Time :2017年04月11日 星期二 19时33分51秒 4File Name :55.cpp 5************************************************ */ 6class Solution { 7 8public: 9 10 bool canJump(vector<int>& nums) { 11 int n = nums.size(); 12 if (n==0) return false; 13 vector<int>dp(n,false); 14 dp[0] = true; 15 for ( int i = 0 ; i < n ; i++) 16 { 17 if (dp[i]) 18 { 19 int r = min(i+nums[i],n-1); 20 for ( int j = i+1 ; j <=r ; j++) 21 dp[j] = true; 22 } 23 } 24 return dp[n-1]; 25 26 27 } 28 29};

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]. 思路：扫一遍即可。。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2017年04月11日 星期二 19时15分30秒 4File Name :56.cpp 5************************************************ */ 6/** 7 8 * Definition for an interval. 9 10 * struct Interval { 11 12 * int start; 13 14 * int end; 15 16 * Interval() : start(0), end(0) {} 17 18 * Interval(int s, int e) : start(s), end(e) {} 19 20 * }; 21 22 */ 23 24class Solution { 25 26public: 27 28 int n; 29 static bool cmp(Interval A,Interval B) 30 { 31 return A.start<B.start; 32 } 33 vector<Interval> merge(vector<Interval>& pi) { 34 vector<Interval>res; 35 n = pi.size(); 36 if (n==0) return res; 37 sort(pi.begin(),pi.end(),cmp); 38 int l = -1,r = -1; 39 for ( int i = 0 ; i < n ; i++) 40 { 41 if (l==-1&&r==-1) 42 { 43 l = pi[0].start; 44 r = pi[0].end; 45 continue; 46 } 47 if (pi[i].start<=r) 48 { 49 r = max(r,pi[i].end); 50 continue; 51 } 52 if (pi[i].start>r) 53 { 54 res.push_back(Interval(l,r)); 55 l = pi[i].start; 56 r = pi[i].end; 57 continue; 58 } 59 } 60 //最后一组不要忘记 61 res.push_back(Interval(l,r)); 62 int siz = res.size(); 63 for ( int i = 0 ; i < siz ;i++) printf("%d ",res[i].start,res[i].end); 64 65 66 return res; 67 68 } 69 70};