LeetCode OJ – 第15页

LeetCode 230. Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:
You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

Hint:

Try to utilize the property of a BST.
What if you could modify the BST node’s structure?
The optimal runtime complexity is O(height of BST).

题目大意：给一个二叉搜索树，返回它的第k小的数～

分析：二叉搜索树的中序遍历是从小到大排序的，将前k个遍历结果放入nums中，当nums.size() >= k的时候返回nums[k-1]～

class Solution {
public:
    vector<int> nums;
    int kthSmallest(TreeNode* root, int k) {
        if (root == NULL || nums.size() >= k) return nums[k - 1];
        if (root->left != NULL) kthSmallest(root->left, k);
        nums.push_back(root->val);
        if (root->right != NULL) kthSmallest(root->right, k);
        return nums[k - 1];
    }
};

class Solution {

public:

vector<int> nums;

int kthSmallest(TreeNode* root, int k) {

if (root == NULL || nums.size() >= k) return nums[k - 1];

if (root->left != NULL) kthSmallest(root->left, k);

nums.push_back(root->val);

if (root->right != NULL) kthSmallest(root->right, k);

return nums[k - 1];

}

};

LeetCode 402. Remove K Digits

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note:
The length of num is less than 10002 and will be ≥ k.
The given num does not contain any leading zero.
Example 1:

Input: num = “1432219”, k = 3
Output: “1219”
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
Example 2:

Input: num = “10200”, k = 1
Output: “200”
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
Example 3:

Input: num = “10”, k = 2
Output: “0”
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

题目大意：给一个以字符串形式表示的非负整数，从字符串中移除k位，使得剩下的数字尽可能的小～

分析：将字符串中每一个元素放入栈中，如果当前要放入的元素比栈顶元素大，而且k > 0（还需要移除数字），则将栈顶元素弹出后再放入新的元素，因为前面的数字越小越好～等到所有数字都加入栈中后，如果k依旧>0，也就是说还有需要弹栈的数字，那就将最后几位移除，因为前面的数字肯定比后面的数字小～将栈中所有元素放入result字符串中，然后再用index判断第一个不为0的下标为多少，然后截取result为result.substr(index)去除了前导0，如果最后发现result为空则返回”0″，否则返回result～

class Solution {
public:
    string removeKdigits(string num, int k) {
        string result = "";
        stack<char> s;
        for (int i = 0; i < num.size(); i++) {
            while (k > 0 && !s.empty() && s.top() > num[i]) {
                k--;
                s.pop();
            }
            s.push(num[i]);
        }
        while (k > 0 && !s.empty()) {
            k--;
            s.pop();
        }
        while (!s.empty()) {
            result = s.top() + result;
            s.pop();
        }
        int index = 0;
        while (result[index] == '0') index++;
        result = result.substr(index);
        if (result == "") return "0";
        return result;
        
    }
};

class Solution {

public:

string removeKdigits(string num, int k) {

string result = "";

stack<char> s;

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

while (k > 0 && !s.empty() && s.top() > num[i]) {

k--;

s.pop();

}

s.push(num[i]);

}

while (k > 0 && !s.empty()) {

k--;

s.pop();

}

while (!s.empty()) {

result = s.top() + result;

s.pop();

}

int index = 0;

while (result[index] == '0') index++;

result = result.substr(index);

if (result == "") return "0";

return result;

}

};

LeetCode 109. Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

题目大意：给一个升序单链表，把它转换成一个高度平衡的二叉搜索树～

分析：递归求解，找到中点，将中点的值赋值给根结点，中点之前的链表为根结点的左子树，中点之后的链表为根结点的右子树～中点以这种方式确定：设立两个指针fast和slow，它们分别从head开始，fast走两步slow走一步，当fast走到最后一个结点的时候slow正好走到中点～

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        return func(head, NULL);
    }
    TreeNode* func(ListNode* head, ListNode* tail) {
        ListNode *fast = head, *slow = head;
        if (head == tail) return NULL;
        while (fast != tail && fast->next != tail) {
            fast = fast->next->next;
            slow = slow->next;
        }
        TreeNode* root = new TreeNode(slow->val);
        root->left = func(head, slow);
        root->right = func(slow->next, tail);
        return root;
    }
};

class Solution {

public:

TreeNode* sortedListToBST(ListNode* head) {

return func(head, NULL);

}

TreeNode* func(ListNode* head, ListNode* tail) {

ListNode *fast = head, *slow = head;

if (head == tail) return NULL;

while (fast != tail && fast->next != tail) {

fast = fast->next->next;

slow = slow->next;

}

TreeNode* root = new TreeNode(slow->val);

root->left = func(head, slow);

root->right = func(slow->next, tail);

return root;

}

};

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;

}

};