leetcode 442. Find All Duplicates in an Array（找出出现两次的元素）

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};

Given an integer n, generate a square matrix filled with elements from 1 to _n_2 in spiral order. 思路：仿佛回到高一的那个暑假。。。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2017年04月11日 星期二 18时52分15秒 4File Name :59.cpp 5************************************************ */ 6class Solution { 7 8public: 9 10 11 int ok (int dir, int &x,int &y,int n,vector<vector<int> >&res) // 0右，1下，2左，3上 12 { 13 if (dir==0) 14 { 15 if (y<=n-2&&res[x][y+1]==0) y++; 16 else 17 { 18 dir++; 19 x++; 20 } 21 return dir; 22 } 23 if (dir==1) 24 { 25 if (x<=n-2&&res[x+1][y]==0) x++; 26 else 27 { 28 dir++; 29 y--; 30 } 31 return dir; 32 } 33 if (dir==2) 34 { 35 if (y>=1&&res[x][y-1]==0) y--; 36 else 37 { 38 dir++; 39 x--; 40 } 41 return dir; 42 } 43 if (dir==3) 44 { 45 if (x>=1&&res[x-1][y]==0) x--; 46 else 47 { 48 dir = 0 ; 49 y++; 50 } 51 return dir; 52 } 53 } 54 55 56 57 58 vector<vector<int>> generateMatrix(int n) { 59 60 vector<vector<int> >res(n,vector<int>(n,0)); 61 int dir = 0; 62 int x,y; 63 x = y = 0 ; 64 for ( int i = 0 ; i < n*n ; i++) 65 { 66 res[x][y] = i+1; 67// printf(" x:%d y: %d\n",x,y); 68 dir = ok (dir,x,y,n,res); 69 } 70 return res; 71 72 73 } 74 75};