Day20260311#

1
class Solution {
2
public:
3
    int gcd(int l,int r){
4
        if(r%l == 0){
5
            return l;
6
        }
7
        return gcd(r%l,l);
8
    }
9
    void rotate(vector<int>& nums, int k) {
10
        if(k==0) return;
11
        int len = nums.size();
12
        int g = gcd(min(len,k),max(len,k));
13
        int count = len;
14
        int p = 0;
15
        int tmp;
16
        while(count > 0){
17
            tmp = nums[p];
18
            for(int i=0;i<len/g;i++){
19
                int target = (p+k) % len;
20
                swap(nums[target],tmp);
21
                p = target;
22
                count--;
23
            }
24
            p = (p+1) %len;
25
        }
26

27
    }
28
};

1
/**
2
 * Definition for a binary tree node.
3
 * struct TreeNode {
4
 *     int val;
5
 *     TreeNode *left;
6
 *     TreeNode *right;
7
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10
 * };
11
 */
12
class Solution {
13
public:
14
    int ans = -1e9;
15
    int findMax(TreeNode* node){
16
        if(node == nullptr) return -1e9;
17
        vector<int> tmp;
18
        int leftVal = findMax(node->left);
19
        int rightVal = findMax(node->right);
20

21
        tmp.push_back(leftVal);
22
        tmp.push_back(rightVal);
23
        tmp.push_back(rightVal+node->val);
24
        tmp.push_back(leftVal+node->val);
25
        tmp.push_back(node->val);
26
        tmp.push_back(leftVal+rightVal+node->val);
27
        sort(tmp.begin(),tmp.end());
28
        ans = max(ans,tmp[5]);
29

30
        return max(max(rightVal,leftVal),0)+node->val;
31
    }
32
    int maxPathSum(TreeNode* root) {
33
        findMax(root);
34
        return ans;
35
    }
36
};