Code – 第149页

LeetCode 60. Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):
“123”
“132”
“213”
“231”
“312”
“321”
Given n and k, return the kth permutation sequence.

题目大意：返回1, 2, 3…n的第k个全排列～

分析：result一开始为1 2 3 4 … n，用C++库函数，当到第k个全排列的时候返回result～

class Solution {
public:
    string getPermutation(int n, int k) {
        string result = "";
        for (int i = 1; i <= n; i++)
            result += to_string(i);
        do {
            k--;
        } while (k > 0 && next_permutation(result.begin(), result.end()));
        return result;
    }
};

class Solution {

public:

string getPermutation(int n, int k) {

string result = "";

for (int i = 1; i <= n; i++)

result += to_string(i);

do {

k--;

} while (k > 0 && next_permutation(result.begin(), result.end()));

return result;

}

};

LeetCode 31. Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

题目大意：实现下一个排列，也就是按照字典序的下一个比它大的排列～

分析：用C++库函数作个弊。。。

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        next_permutation(nums.begin(), nums.end());
    }
};

class Solution {

public:

void nextPermutation(vector<int>& nums) {

next_permutation(nums.begin(), nums.end());

}

};

LeetCode 22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

题目大意：给n对括号，写一个方法，生成所有格式正确的括号组合～

分析：left表示还剩余的左括号个数，right表示目前需要的右括号数～一开始left = n，right = 0；当left还剩余左括号数大于0的时候，添加左括号，并将left – 1，right + 1；当right目前还需要的右括号数大于0的时候，添加右括号，并将right – 1～当left和right都等于0的时候，表示当前是一个符合格式条件的字符串，将该字符串cur放入result数组中，最后返回result～

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        dfs("", n, 0);
        return result;
    }
private:
    vector<string> result;
    void dfs(string cur, int left, int right) {
        if (left == 0 && right == 0) {
            result.push_back(cur);
            return;
        }
        if (left > 0) dfs(cur + "(", left - 1, right + 1);
        if (right > 0) dfs(cur + ")", left, right - 1);
    }
};

class Solution {

public:

vector<string> generateParenthesis(int n) {

dfs("", n, 0);

return result;

}

private:

vector<string> result;

void dfs(string cur, int left, int right) {

if (left == 0 && right == 0) {

result.push_back(cur);

return;

}

if (left > 0) dfs(cur + "(", left - 1, right + 1);

if (right > 0) dfs(cur + ")", left, right - 1);

}

};

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;

}

};