Leetcode1501 - 1600

Posted on

Leetcode1502. Can Make Arithmetic Progression From Sequence

Given an array of numbers arr. A sequence of numbers is called an arithmetic progression if the difference between any two consecutive elements is the same.

Return true if the array can be rearranged to form an arithmetic progression, otherwise, return false.

Example 1:

1
2
3
Input: arr = [3,5,1]
Output: true
Explanation: We can reorder the elements as [1,3,5] or [5,3,1] with differences 2 and -2 respectively, between each consecutive elements.

Example 2:
1
2
3
Input: arr = [1,2,4]
Output: false
Explanation: There is no way to reorder the elements to obtain an arithmetic progression.

判断是否可以组成等差数列，将数组排序后，比较两两数字差是否一致。
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool canMakeArithmeticProgression(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        int cha = arr[1] - arr[0];
        for(int i = 2; i < arr.size(); i ++)
            if(arr[i] - arr[i-1] != cha)
                return false;
        return true;
    }
};

Leetcode1507. Reformat Date

Given a date string in the form Day Month Year, where:

  • Day is in the set {“1st”, “2nd”, “3rd”, “4th”, …, “30th”, “31st”}.
  • Month is in the set {“Jan”, “Feb”, “Mar”, “Apr”, “May”, “Jun”, “Jul”, “Aug”, “Sep”, “Oct”, “Nov”, “Dec”}.
  • Year is in the range [1900, 2100].

Convert the date string to the format YYYY-MM-DD, where:

  • YYYY denotes the 4 digit year.
  • MM denotes the 2 digit month.
  • DD denotes the 2 digit day.

Example 1:

1
2
Input: date = "20th Oct 2052"
Output: "2052-10-20"

Example 2:
1
2
Input: date = "6th Jun 1933"
Output: "1933-06-06"

时间格式转换，很麻烦。
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
class Solution {
public:
    string reformatDate(string date) {
        string res;
        int count = 0;
        int day, month, year;
        vector<string> mon{"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"};
        for(int i = 0; i < date.length();) {
            if(date[i] == ' ') {
                count ++;
                i ++;
            }
            else if(count == 0) {
                day = 0;
                while('0' <= date[i] && date[i] <= '9') {
                    day = day * 10 + (date[i] - '0');
                    i ++;
                }
                i += 2;
            }
            else if(count == 1) {
                string months = "";
                int ii;
                while(date[i] != ' ') 
                    months += date[i ++];
                for(ii = 0; ii < mon.size(); ii ++)
                    if(months == mon[ii])
                        break;
                month = ii + 1;
            }
            else if(count == 2) {
                year = 0;
                while('0' <= date[i] && date[i] <= '9') {
                    year = year * 10 + (date[i] - '0');
                    i ++;
                }
            }
        }
        res = to_string(year) + "-" + (month >= 10 ? "" : "0") + to_string(month)  + "-" + (day >= 10 ? "" : "0") + to_string(day);
        return res;
    }
};

Leetcode1512. Number of Good Pairs

Given an array of integers nums. A pair (i,j) is called good if nums[i] == nums[j] and i < j. Return the number of good pairs.

Example 1:

1
2
3
Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.

Example 2:
1
2
3
Input: nums = [1,1,1,1]
Output: 6
Explanation: Each pair in the array are good.

遍历一遍即可。
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        int res = 0;
        for(int i = 0; i < nums.size(); i ++)
            for(int j = i + 1; j < nums.size(); j ++)
                if(nums[i] == nums[j])
                    res ++;
        return res;
    }
};

Leetcode1530. Number of Good Leaf Nodes Pairs

You are given the root of a binary tree and an integer distance. A pair of two different leaf nodes of a binary tree is said to be good if the length of the shortest path between them is less than or equal to distance.

Return the number of good leaf node pairs in the tree.

Example 1:

1
2
3
Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.

Example 2:

1
2
3
Input: root = [1,2,3,4,5,6,7], distance = 3
Output: 2
Explanation: The good pairs are [4,5] and [6,7] with shortest path = 2. The pair [4,6] is not good because the length of ther shortest path between them is 4.

Example 3:

1
2
3
Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3
Output: 1
Explanation: The only good pair is [2,5].

Constraints:

  • The number of nodes in the tree is in the range [1, 210].
  • 1 <= Node.val <= 100
  • 1 <= distance <= 10

如果二叉树中两个 叶 节点之间的 最短路径长度 小于或者等于 distance ，那它们就可以构成一组 好叶子节点对。这个题让找好叶子节点对的数量。注意到这个题的数据量很小，可以遍历找到。

因为是找左右子树的数量，所以可以对左右子树分别算一个数组，数组里计算了距离本节点距离为i的节点有几个，例如如果这个点是叶子，那cnt数组中只有cnt[0]为1。在算这两个节点的距离时，如下边的代码所示，要s+1 + t+1，s是node的左子树到node->left的距离，t是node的右子树到node->right的距离。起始条件是0，因为是叶子到node的子节点的距离，是可能为0的；而终止条件应该是d-1，因为两端的叶子的路径是经过node的，不能算上根节点。

计算结果时把左右子树的数组对应值乘起来。

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
class Solution {
public:
    int ret;
    int d;
    
    vector<int> dfs(TreeNode* node) {
        vector<int> cnt(d);
        if (!node) 
            return cnt;
        
        vector<int> lcnt = dfs(node->left);
        vector<int> rcnt = dfs(node->right);
        
        for (int s = 0; s <= d-2; s ++)
            for (int t = 0; t <= d-2; t ++) {
                if (s + t + 2 > d)
                    continue;
                ret += lcnt[s] * rcnt[t];
            }
        for (int i = 0; i < d-1; i ++)
            cnt[i+1] = lcnt[i] + rcnt[i];
        
        if (!node->left && !node->right)
            cnt[0] = 1;
        return cnt;
    }
    
    int countPairs(TreeNode* root, int distance) {
        ret = 0;
        d = distance;
        
        dfs(root);
        return ret;
    }
};

另一种做法：

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
class Solution {
public:
    int countPairs(TreeNode* root, int distance) {
        numPairs = 0;
        targetDistance = distance;
        countPairsHelper(root, 1);
        return numPairs;
    }
 
private:
    int numPairs;
    int targetDistance;
    
    vector<int> countPairsHelper(TreeNode* root, int level) {
        if (root == NULL)
            return {};
        if (root->left == NULL && root->right == NULL)
            return {level};
        
        vector<int> leftLeaves = countPairsHelper(root->left, level + 1);
        vector<int> rightLeaves = countPairsHelper(root->right, level + 1);
        for (auto left: leftLeaves) {
            for (auto right: rightLeaves) {
                if (left + right - 2 * level <= targetDistance)
                    numPairs++;
            }
        }
 
        for (auto right: rightLeaves)
            leftLeaves.push_back(right);
        return leftLeaves;
    }
};