Code – 第150页

LeetCode 108. Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

题目大意：给一个升序数组，把它转化为一个高度平衡的二叉搜索树～

分析：设立left和right，mid = (left + right) / 2，每次将数组的中点mid的值为根结点的值，中点左边为根结点的左子树，右边为根结点的右子树～递归求解～

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return func(nums, 0, nums.size() - 1);
    }
private:
    TreeNode* func(vector<int>& nums, int left, int right) {
        if (left > right) return NULL;
        int mid = (left + right) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = func(nums, left, mid - 1);
        root->right = func(nums, mid + 1, right);
        return root;
    }
};

class Solution {

public:

TreeNode* sortedArrayToBST(vector<int>& nums) {

return func(nums, 0, nums.size() - 1);

}

private:

TreeNode* func(vector<int>& nums, int left, int right) {

if (left > right) return NULL;

int mid = (left + right) / 2;

TreeNode* root = new TreeNode(nums[mid]);

root->left = func(nums, left, mid - 1);

root->right = func(nums, mid + 1, right);

return root;

}

};

LeetCode 486. Predict the Winner

Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.

Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score.

Example 1:
Input: [1, 5, 2]
Output: False
Explanation: Initially, player 1 can choose between 1 and 2.
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2).
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5.
Hence, player 1 will never be the winner and you need to return False.
Example 2:
Input: [1, 5, 233, 7]
Output: True
Explanation: Player 1 first chooses 1. Then player 2 have to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.
Note:
1 <= length of the array <= 20.
Any scores in the given array are non-negative integers and will not exceed 10,000,000.
If the scores of both players are equal, then player 1 is still the winner.

题目大意：给一个整型数组，两个人依次从数组中的头或者尾拿一个数，判断是否player1拿到的总数大于或者等于player2～如果是就返回true，否则返回false～

分析：动态规划解决～建立dp[len][len]数组，dp[i][j]表示nums数组中i～j下标间player1能够获得的分数-player2能够获得的分数～最后dp[0][len-1]的正负性即可表明player1是否能赢～
dp[0][len-1]的值通过递归动态规划可得：func(begin, end)返回dp[begin][end]的值，当begin和end相等的时候，dp[begin][end]的值即为nums[begin]（或者nums[end]），如果begin和end不等，那么如果取begin，结果为nums[begin] – dp[begin+1][end]; 如果取end，结果为nums[end] – dp[begin][end-1]，dp[begin][end]取它俩中较大的一个～

class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        this->nums = nums;
        int len = nums.size();
        dp.resize(len, vector<int>(len));
        return func(0, len-1) >= 0;
    }
private:
    vector<int> nums;
    vector<vector<int>> dp;
    int func(int begin, int end) {
        dp[begin][end] = begin == end ? nums[begin] : max(nums[begin] - func(begin+1, end), nums[end] - func(begin, end-1));
        return dp[begin][end];
    }
};

class Solution {

public:

bool PredictTheWinner(vector<int>& nums) {

this->nums = nums;

int len = nums.size();

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

return func(0, len-1) >= 0;

}

private:

vector<int> nums;

vector<vector<int>> dp;

int func(int begin, int end) {

dp[begin][end] = begin == end ? nums[begin] : max(nums[begin] - func(begin+1, end), nums[end] - func(begin, end-1));

return dp[begin][end];

}

};

LeetCode 367. Valid Perfect Square

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:

Input: 16
Returns: True
Example 2:

Input: 14
Returns: False

题目大意：判断所给的数是否正好是某数的平方～

分析：二分查找法，假设它是某数的平方，将该数的结果控制在left和right之间，不断循环，每次令mid为left和right的中间值，如果mid的平方等于num说明返回true；如果mid的平方小于num并且mid+1的平方大于num，说明num不是任何数的平方，夹在mid和mid+1之间～如果mid的平方小于num说明结果在mid的右边，令left = mid + 1；否则某数就是在mid的左边，right = mid – 1～～

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

class Solution {

public:

bool isPerfectSquare(int num) {

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

while (true) {

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

if (mid * mid == num)

return true;

if (mid * mid < num && (mid + 1) * (mid + 1) > num)

return false;

if (mid * mid < num)

left = mid + 1;

else

right = mid - 1;

}

};

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;

}

};