LeetCode 495. Teemo Attacking

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.

Example 1:
Input: [1,4], 2
Output: 4
Explanation: At time point 1, Teemo starts attacking Ashe and makes Ashe be poisoned immediately.
This poisoned status will last 2 seconds until the end of time point 2.
And at time point 4, Teemo attacks Ashe again, and causes Ashe to be in poisoned status for another 2 seconds.
So you finally need to output 4.
Example 2:
Input: [1,2], 2
Output: 3
Explanation: At time point 1, Teemo starts attacking Ashe and makes Ashe be poisoned.
This poisoned status will last 2 seconds until the end of time point 2.
However, at the beginning of time point 2, Teemo attacks Ashe again who is already in poisoned status.
Since the poisoned status won’t add up together, though the second poisoning attack will still work at time point 2, it will stop at the end of time point 3.
So you finally need to output 3.
Note:
You may assume the length of given time series array won’t exceed 10000.
You may assume the numbers in the Teemo’s attacking time series and his poisoning time duration per attacking are non-negative integers, which won’t exceed 10,000,000.

题目大意:给一个数组和一个数字,数组中元素是升序的,每一个元素代表释放毒气的时间点,数字duration表示释放毒气能够中毒的时间,比如时间点1开始攻击,持续2秒,则在第2秒结束后才会恢复不中毒~如果前一次中毒ing而后一次提早又被攻击,那就是后一次攻击后+持续时间才会恢复不中毒~现在要求这个人一共中毒了多少秒~

分析:oldEnd表示这一次攻击之前的攻击导致的最晚中毒结束时间,首先初值是-1表示刚开始的时候不是中毒的(也就是中毒结束时间是-1,不能是0因为有一个测试用例时间点是从0开始的。。)
遍历数组,对于每一个timeSeries[i], 这次攻击导致的中毒结束时间是newEnd = timeSeries[i] + duration – 1:
如果新的结束时间比之前的结束时间长,就取duration, newEnd – oldEnd)中较小的一个,因为如果oldEnd早就结束了,那就是duration让他中毒了duration秒,如果oldEnd结束的比较晚,晚于这一次攻击开始的时间,那么累计的中毒事件就应该是newEnd – oldEnd也就是新的攻击造成的结束时间减去旧的攻击结束时间~并且让oldEnd更新为newEnd的这个较大的值~
如果新的结束时间比之前的结束时间短,那么不需要累加,反正这次攻击不攻击都没什么用因为反正是中毒ing…最后返回result累加的结果即可~

LeetCode 498. Diagonal Traverse

Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.

Example:
Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output: [1,2,4,7,5,3,6,8,9]
Explanation:

Note:
The total number of elements of the given matrix will not exceed 10,000.

题目大意:按照如图所示方向遍历一个m*n的二维数组,将元素按序放入一维数组中返回~

分析:先假设所有的方向都是斜向上的,也就是从matrix[0][0]开始,matrix[1][0]、matrix[2, 0]…matrix[m-1][0]也就是第一列的所有数为开头,然后还有最后一行的所有数为开头,寻找matrix[i-1][j+1]是否存在,存在就将它放入temp数组中,temp的每一行表示斜着的一行元素的序列。
这样当temp数组的行数是奇数的时候,就从后往前一次放入到result数组中,如果是偶数就从前往后依次放入result数组中,返回result数组即为所求~

 

LeetCode 516. Longest Palindromic Subsequence

Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.

Example 1:
Input:

“bbbab”
Output:
4
One possible longest palindromic subsequence is “bbbb”.
Example 2:
Input:

“cbbd”
Output:
2
One possible longest palindromic subsequence is “bb”.

题目大意:给一个字符串s,找最长回文子串~返回这个最长回文子串的长度~

分析:使用动态规划解决~设立一个len行len列的dp数组~dp[i][j]表示字符串i~j下标所构成的子串中最长回文子串的长度~最后我们需要返回的是dp[0][len-1]的值~

dp数组这样更新:首先i指针从尾到头遍历,j指针从i指针后面一个元素开始一直遍历到尾部~一开始dp[i][i]的值都为1,如果当前i和j所指元素相等,说明能够加到i~j的回文子串的长度中,所以更新dp[i][j] = dp[i+1][j-1] + 2; 如果当前元素不相等,那么说明这两个i、j所指元素对回文串无贡献,则dp[i][j]就是从dp[i+1][j]和dp[i][j-1]中选取较大的一个值即可~

 

LeetCode 500. Keyboard Row

Given a List of words, return the words that can be typed using letters of alphabet on only one row’s of American keyboard like the image below.
Example 1:
Input: [“Hello”, “Alaska”, “Dad”, “Peace”]
Output: [“Alaska”, “Dad”]
Note:
You may use one character in the keyboard more than once.
You may assume the input string will only contain letters of alphabet.

题目大意:给一个单词数组,判断哪些单词是可以由键盘的一行中的字母构成的,返回这些单词~

分析:设立一个集合数组,v[0]、v[1]、v[2]集合分别插入键盘的第1~3行的所有字母的集合(大小写都包括),接着遍历每一个单词,首先判断单词的第一个字母是处于哪一行的,tag表示其所属行数的下标,接着对于单词的每一个字母,判断是否在v[tag]这个集合里面,如果所有的都存在就将这个单词放入result数组中返回~