leetcode解题思路分析（一百三十一）1103 - 1109 题

1103. 分糖果 II
      返回一个长度为 num_people、元素之和为 candies 的数组，以表示糖果的最终分发情况（即 ans[i] 表示第 i 个小朋友分到的糖果数）。

等差数列求和

class Solution {
public:
    vector<int> distributeCandies(int candies, int num_people) {
        int n = num_people;
        // how many people received complete gifts
        int p = (int)(sqrt(2 * candies + 0.25) - 0.5);
        int remaining = (int)(candies - (p + 1) * p * 0.5);
        int rows = p / n, cols = p % n;

        vector<int> d(n, 0);
        for (int i = 0; i < n; ++i) {
            // complete rows
            d[i] = (i + 1) * rows + (int)(rows * (rows - 1) * 0.5) * n;
            // cols in the last row
            if (i < cols) d[i] += i + 1 + rows * n;
        }
        // remaining candies 
        d[cols] += remaining;
        return d;
    }
};


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

1104. 二叉树寻路
      给你树上某一个节点的标号 label，请你返回从根节点到该标号为 label 节点的路径，该路径是由途经的节点标号所组成的。

主要利用一个特性：子节点除以二取下限就是父节点的标号，但是这里因为做了一个之字形的修改，所以对偶数行需要处理，取反即可

class Solution {
public:
    int getReverse(int label, int row) {
        return (1 << row - 1) + (1 << row) - 1 - label;
    }

    vector<int> pathInZigZagTree(int label) {
        int row = 1, rowStart = 1;
        while (rowStart * 2 <= label) {
            row++;
            rowStart *= 2;
        }
        if (row % 2 == 0) {
            label = getReverse(label, row);
        }
        vector<int> path;
        while (row > 0) {
            if (row % 2 == 0) {
                path.push_back(getReverse(label, row));
            } else {
                path.push_back(label);
            }
            row--;
            label >>= 1;
        }
        reverse(path.begin(), path.end());
        return path;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

1105. 填充书架
      以这种方式布置书架，返回书架整体可能的最小高度。

动态规划：对每本书都尝试能否将后面的书放在同一排

class Solution {
public:
int minHeightShelves(vector<vector<int>>& books, int shelf_width) {
    vector<int> dp(books.size() + 1, INT_MAX);
    dp[books.size()] = 0;
    for (int i = books.size() - 1; i >= 0; --i) {
        int max_book_height = 0;
        int left_width = shelf_width;
        // 把第 j 本书拿到第 i 本书后面
        for (int j = i; j < books.size() && left_width >= books[j][0]; ++j) {
            max_book_height = max(max_book_height, books[j][1]);
            dp[i] = min(dp[i], max_book_height + dp[j+1]);
            left_width -= books[j][0];
        }
    }
    return dp[0];
}

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1106. 解析布尔表达式
      给你一个以字符串形式表述的 布尔表达式（boolean） expression，返回该式的运算结果。

class Solution {
public:
    bool parseBoolExpr(string expression) {
        if(expression == "f") return false;
        if(expression == "t") return true;
        if(expression[0] == '!'){
            expression.pop_back();
            return !parseBoolExpr(expression.substr(2));
        }
        int i = 0; while(expression[i] != '(') i++;
        int j = expression.size() - 1; while(expression[j] != ')') j--;
        string ev;
        int cnt = 0;
        if(expression[0] == '&'){
            for(int k = i + 1; k < j; ++k){
                if(expression[k] == '(') cnt++;
                else if(expression[k] == ')') cnt--;
                if(expression[k] == ','){
                    if(cnt != 0) ev += expression[k];
                    else {
                        if(!parseBoolExpr(ev)) return false;
                        ev.clear();
                    }
                }
                else ev += expression[k];
            }
            if(!parseBoolExpr(ev)) return false;
            return true;
        }
        else if(expression[0] == '|'){
            for(int k = i + 1; k < j; ++k){
                if(expression[k] == '(') cnt++;
                else if(expression[k] == ')') cnt--;
                if(expression[k] == ','){
                    if(cnt != 0) ev += expression[k];
                    else {
                        if(parseBoolExpr(ev)) return true;
                        ev.clear();
                    }
                }
                else ev += expression[k];
            }
            if(parseBoolExpr(ev)) return true;
            return false;
        }
        // impossible
        return false;
    }
};


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

1108. IP 地址无效化
      给你一个有效的 IPv4 地址 address，返回这个 IP 地址的无效化版本。所谓无效化 IP 地址，其实就是用 “[.]” 代替了每个 “.”。

将字符串address 中‘.’ 替换为"[.]" 即可

class Solution {
public:
    string defangIPaddr(string address) {
        string ans;
        for (auto & c : address) {
            if (c == '.') {
                ans.append("[.]");
            } else {
                ans.push_back(c);
            }
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1109. 航班预订统计
      这里有 n 个航班，它们分别从 1 到 n 进行编号。有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。

类似于公交车下车及加油问题，对起始位置++，最终位置–，然后最后累加即可。

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> nums(n);
        for (auto& booking : bookings) {
            nums[booking[0] - 1] += booking[2];
            if (booking[1] < n) {
                nums[booking[1]] -= booking[2];
            }
        }
        for (int i = 1; i < n; i++) {
            nums[i] += nums[i - 1];
        }
        return nums;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1110. 删点成林
      给出二叉树的根节点 root，树上每个节点都有一个不同的值。如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。返回森林中的每棵树。你可以按任意顺序组织答案。

很容易想到用递归解题，关键是判断好递归的条件：如果找到set中的删除点，则至空、加入返回集并且访问左右子树，如果是叶子节点删除，则仅删除

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> forest;
    unordered_set<int> delete_set;
    TreeNode* delHelper(TreeNode* root, TreeNode* parent) {
        if(!root) return nullptr;
        root->left = delHelper(root->left, root);
        root->right = delHelper(root->right, root);
        //情况一
        if(delete_set.find(root->val) != delete_set.end()) {
            if(root->left) forest.push_back(root->left);
            if(root->right) forest.push_back(root->right);
            root = nullptr;
        }
        //情况二
        else if(!parent) forest.push_back(root);
        return root;
    }
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
        for(auto val : to_delete) delete_set.insert(val);
        delHelper(root, nullptr);
        return forest;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37