LeetCode OJ – 第16页

LeetCode 69. Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

题目大意：实现sqrt函数，返回x的sqrt结果（int型）

分析：二分法，令left = 0， right为int最大值，mid为left和right的中间值。始终保持要求的值在left和right之间。进入循环——如果mid的平方小于等于x并且mid+1的平方大于等于x则返回mid～否则：如果mid的平方小于x，说明答案在mid的右边，left = mid + 1，mid的平方大于x，说明答案在mid的左边，right = mid – 1～
注意：令left、right、mid都是long型因为为了避免mid*mid的结果超出整型范围～

class Solution {
public:
    int mySqrt(int x) {
        long left = 0, right = INT_MAX, mid = 0;
        while (true) {
            long mid = left + (right - left) / 2;
            if (mid * mid <= x && (mid + 1) * (mid + 1) > x)
                return (int)mid;
            if (mid * mid < x)
                left = mid + 1;
            else
                right = mid - 1;
        }
    }
};

class Solution {

public:

int mySqrt(int x) {

long left = 0, right = INT_MAX, mid = 0;

while (true) {

long mid = left + (right - left) / 2;

if (mid * mid <= x && (mid + 1) * (mid + 1) > x)

return (int)mid;

if (mid * mid < x)

left = mid + 1;

else

right = mid - 1;

}

};

LeetCode 491. Increasing Subsequences

Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2 .

Example:
Input: [4, 6, 7, 7]
Output: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
Note:
The length of the given array will not exceed 15.
The range of integer in the given array is [-100,100].
The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence.

题目大意：给一个整型数组nums，寻找它的所有满足条件的子数组：每一个子数组内的元素都是递增的（允许包含重复元素，所以其实是不递减的）～以二维数组的方式返回～

分析：row为结果集的每一行的结果，深度优先搜索，两个参数：lastNum：表示当前row中最后一个元素的值，（即后面想要加进来的值必须大于等于lastNum），index：表示当前已加入row的元素中的最后一位的index，一开始lastNum = -101表示最小值，而index = -1。这样下一次就让i从index + 1开始遍历是否有比它大的或者等于它的元素，有就加入row并且dfs(nums[i], i)，最后记得将row的最后一个元素pop出来。当row中的元素大于等于2个的时候，就可以称为一个满足条件的结果，因为为了避免有重复元素，就将row插入一个集合中。最后遍历集合将所有一维数组都放入result二维数组中，返回result即可～

class Solution {
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        vector<vector<int>> result;
        this->nums = nums;
        dfs(-101, -1);
        for (auto it = s.begin(); it != s.end(); it++)
            result.push_back(*it);
        return result;
    }
private:
    set<vector<int>> s;
    vector<int> nums, row;
    void dfs(int lastNum, int index) {
        if (row.size() >= 2) s.insert(row);
        if (index == nums.size()) return ;
        for (int i = index + 1; i < nums.size(); i++) {
            if (nums[i] >= lastNum) {
                row.push_back(nums[i]);
                dfs(nums[i], i);
                row.pop_back();
            }
        }
    }
};

class Solution {

public:

vector<vector<int>> findSubsequences(vector<int>& nums) {

vector<vector<int>> result;

this->nums = nums;

dfs(-101, -1);

for (auto it = s.begin(); it != s.end(); it++)

result.push_back(*it);

return result;

}

private:

set<vector<int>> s;

vector<int> nums, row;

void dfs(int lastNum, int index) {

if (row.size() >= 2) s.insert(row);

if (index == nums.size()) return ;

for (int i = index + 1; i < nums.size(); i++) {

if (nums[i] >= lastNum) {

row.push_back(nums[i]);

dfs(nums[i], i);

row.pop_back();

}

};

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累加的结果即可～

class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        int result = 0, oldEnd = -1;
        for (int i = 0; i < timeSeries.size(); i++) {
            int newEnd = timeSeries[i] + duration - 1;
            if (newEnd > oldEnd) {
                result += min(duration, newEnd - oldEnd);
                oldEnd = newEnd;
            }
        }
        return result;
    }
};

class Solution {

public:

int findPoisonedDuration(vector<int>& timeSeries, int duration) {

int result = 0, oldEnd = -1;

for (int i = 0; i < timeSeries.size(); i++) {

int newEnd = timeSeries[i] + duration - 1;

if (newEnd > oldEnd) {

result += min(duration, newEnd - oldEnd);

oldEnd = newEnd;

}

return 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数组即为所求～

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
        vector<int> result;
        int m = matrix.size();
        if (m == 0) return result;
        int n = matrix[0].size(), index = 0;
        vector<vector<int>> temp(m + n - 1);
        for (int i = 0; i < m; i++, index++) {
            temp[index].push_back(matrix[i][0]);
            for (int x = i, y = 0; x - 1 >= 0 && y + 1 < n; x--, y++)
                temp[index].push_back(matrix[x-1][y+1]);
        }
        for (int j = 1; j < n; j++, index++) {
            temp[index].push_back(matrix[m-1][j]);
            for (int x = m - 1, y = j; x - 1 >= 0 && y + 1 < n; x--, y++)
                temp[index].push_back(matrix[x-1][y+1]);
        }
        for (int i = 0; i < m + n - 1; i++) {
            if (i % 2 == 1) {
                for (int j = temp[i].size() - 1; j >= 0; j--)
                    result.push_back(temp[i][j]);
            } else {
                for (int j = 0; j < temp[i].size(); j++)
                result.push_back(temp[i][j]);
            }
        }
        return result;
    }
};

class Solution {

public:

vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {

vector<int> result;

int m = matrix.size();

if (m == 0) return result;

int n = matrix[0].size(), index = 0;

vector<vector<int>> temp(m + n - 1);

for (int i = 0; i < m; i++, index++) {

temp[index].push_back(matrix[i][0]);

for (int x = i, y = 0; x - 1 >= 0 && y + 1 < n; x--, y++)

temp[index].push_back(matrix[x-1][y+1]);

}

for (int j = 1; j < n; j++, index++) {

temp[index].push_back(matrix[m-1][j]);

for (int x = m - 1, y = j; x - 1 >= 0 && y + 1 < n; x--, y++)

temp[index].push_back(matrix[x-1][y+1]);

}

for (int i = 0; i < m + n - 1; i++) {

if (i % 2 == 1) {

for (int j = temp[i].size() - 1; j >= 0; j--)

result.push_back(temp[i][j]);

} else {

for (int j = 0; j < temp[i].size(); j++)

result.push_back(temp[i][j]);

}

return 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]中选取较大的一个值即可～

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int len = s.length();
        vector<vector<int>> dp(len, vector<int>(len));
        for (int i = len - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i + 1; j < len; j++) {
                if (s[i] == s[j])
                    dp[i][j] = dp[i+1][j-1] + 2;
                else
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
            }
        }
        return dp[0][len-1];
    }
    
};

class Solution {

public:

int longestPalindromeSubseq(string s) {

int len = s.length();

vector<vector<int>> dp(len, vector<int>(len));

for (int i = len - 1; i >= 0; i--) {

dp[i][i] = 1;

for (int j = i + 1; j < len; j++) {

if (s[i] == s[j])

dp[i][j] = dp[i+1][j-1] + 2;

else

dp[i][j] = max(dp[i+1][j], dp[i][j-1]);

}

return dp[0][len-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数组中返回～

class Solution {
public:
    vector<string> findWords(vector<string>& words) {
        vector<string> result;
        vector<set<char>> v(3);
        string s1 = "QWERTYUIOPqwertyuiop", s2 = "ASDFGHJKLasdfghjkl", s3 = "ZXCVBNMzxcvbnm";
        for (int i = 0; i < s1.length(); i++) v[0].insert(s1[i]);
        for (int i = 0; i < s2.length(); i++) v[1].insert(s2[i]);
        for (int i = 0; i < s3.length(); i++) v[2].insert(s3[i]);
        for (int i = 0; i < words.size(); i++) {
            int tag = -1;
            bool flag = true;
            if (words[i].length() == 0) continue; 
            if (v[0].find(words[i][0]) != v[0].end()) tag = 0;
            if (v[1].find(words[i][0]) != v[1].end()) tag = 1;
            if (v[2].find(words[i][0]) != v[2].end()) tag = 2;
            for (int j = 1; j < words[i].length(); j++) {
                if (v[tag].find(words[i][j]) == v[tag].end()) {
                    flag = false;
                    break;
                }
            }
            if (flag == true)
                result.push_back(words[i]);
        }
        return result;
    }
};

class Solution {

public:

vector<string> findWords(vector<string>& words) {

vector<string> result;

vector<set<char>> v(3);

string s1 = "QWERTYUIOPqwertyuiop", s2 = "ASDFGHJKLasdfghjkl", s3 = "ZXCVBNMzxcvbnm";

for (int i = 0; i < s1.length(); i++) v[0].insert(s1[i]);

for (int i = 0; i < s2.length(); i++) v[1].insert(s2[i]);

for (int i = 0; i < s3.length(); i++) v[2].insert(s3[i]);

for (int i = 0; i < words.size(); i++) {

int tag = -1;

bool flag = true;

if (words[i].length() == 0) continue;

if (v[0].find(words[i][0]) != v[0].end()) tag = 0;

if (v[1].find(words[i][0]) != v[1].end()) tag = 1;

if (v[2].find(words[i][0]) != v[2].end()) tag = 2;

for (int j = 1; j < words[i].length(); j++) {

if (v[tag].find(words[i][j]) == v[tag].end()) {

flag = false;

break;

}

if (flag == true)

result.push_back(words[i]);

}

return result;

}

};