↓ 跳过正文
111qqz的小窝
111qqz的小窝
  1. Posts/

leetcode 495. Teemo Attacking

·251 字·1 分钟
ACM Leetcode

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.

题意：若干长度相同的区间，升序给出区间左端点，以及区间长度。问区间被覆盖的长度总和。

思路：。。。。随便写。这题哪里有medium难度了啊。。

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2017年04月12日 星期三 23时42分25秒
 4File Name :495.cpp
 5************************************************ */
 6class Solution {
 7
 8public:
 9
10    int findPoisonedDuration(vector<int>& a, int t) {
11	int n = a.size();
12	int res = 0;
13	for ( int i = 0 ; i < n ; i++)
14	{
15	    if (i==n-1)
16	    {
17		res+=t;
18		continue;
19	    }
20	    if (a[i]+t<=a[i+1]) res+=t;
21	    else res = res + a[i+1]-a[i];
22	}
23	return res;
24
25
26    }
27
28};

相关文章

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

·234 字·1 分钟
ACM Leetcode
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? 思路：还是一个映射，如果某个位置要映射的时候已经为负了，就说明之前映射过该位置，那么该位置对应的元素就是出现了两个的元素。

leetcode 48. Rotate Image (旋转方阵(in place))

·575 字·2 分钟
ACM Leetcode
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的环，保护一个节点，然后顺次做就好了。

leetcode 54. Spiral Matrix (矩阵蛇形取数)

·291 字·1 分钟
ACM Leetcode
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};

leetcode 55. Jump Game (dp)

·165 字·1 分钟
ACM Leetcode
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};

leetcode 56. Merge Intervals (模拟，求相交区间)

·270 字·1 分钟
ACM Leetcode
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};