Befighting

排序链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* merge(struct ListNode* pre, struct ListNode* l1,
                       struct ListNode* l2);
struct ListNode* sortList(struct ListNode* head) {
    struct ListNode* dum = (struct ListNode*)malloc(sizeof(struct ListNode));
    dum->next = head;
    struct ListNode* p = head;
    int length = 0;
    while (p) {
        length++;
        p = p->next;
    }

    for (int len = 1; len < length; len = len * 2) {
        struct ListNode* pre = dum;
        struct ListNode* cur = dum->next;
        while (cur) {
            struct ListNode* left = cur;
            for (int i = 1; i < len && cur->next; i++) {
                cur = cur->next;
            }
            struct ListNode* right = cur->next;
            cur->next = NULL;
            cur = right;
            for (int i = 1; i < len && cur && cur->next; i++) {
                cur = cur->next;
            }
            struct ListNode* next = NULL;
            if (cur) {
                next = cur->next;
                cur->next = NULL;
            }

            pre = merge(pre, left, right);
            cur = next;
        }
    }
    return dum->next;
}

struct ListNode* merge(struct ListNode* pre, struct ListNode* l1,
                       struct ListNode* l2) {
    while (l1 && l2) {
        if (l1->val < l2->val) {
            pre->next = l1;
            l1 = l1->next;
        } else {
            pre->next = l2;
            l2 = l2->next;
        }
        pre = pre->next;
    }
    pre->next = l1 ? l1 : l2;
    while (pre->next) {
        pre = pre->next;
    }
    return pre;
}

从前序与中序遍历序列构造二叉树

/**
 * 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:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        stack<TreeNode*> stack;
        TreeNode* root = new TreeNode(preorder[0]);

        int inorderIndex = 0;
        stack.push(root);
        for (int i = 1; i < preorder.size(); i++) {
            TreeNode* par = stack.top();
            TreeNode* newnode = new TreeNode(preorder[i]);
            if (par->val != inorder[inorderIndex]) {
                par->left = newnode;
                stack.push(newnode);
            } else {
                while (!stack.empty() &&
                       stack.top()->val == inorder[inorderIndex]) {
                    par = stack.top();
                    stack.pop();
                    inorderIndex++;
                }
                par->right = newnode;
                stack.push(newnode);
            }
        }
        return root;
    }
};

路径总和 III

/**
 * 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:
    int func(TreeNode* root, int targetSum, long long cur,
             unordered_map<long long, int>& map) {
        if (!root)
            return 0;
        cur = cur + root->val;
        int count = map[cur - targetSum];//不能用targetSum-cur，只有cur - targetSum才是下面的-上面的
        map[cur]++;
        count = count + func(root->left, targetSum, cur, map);
        count = count + func(root->right, targetSum, cur, map);
        map[cur]--;
        return count;
    }
    int pathSum(TreeNode* root, int targetSum) {
        unordered_map<long long, int> map;
        map[0] = 1;
        return func(root, targetSum, 0, map);
    }
};

二叉树中的最大路径和

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
//递归函数返回的当前节点向上延伸的最大路径和
int Max(int a,int b){return a>b?a:b;}
int func(struct TreeNode* root,int *max){
    if(!root) return 0;
    int left=Max(0,func(root->left,max));
    int right=Max(0,func(root->right,max));
    int nowPath=root->val+left+right;
    *max=Max(*max,nowPath);
    return root->val+Max(left,right);
}
int maxPathSum(struct TreeNode* root) {
    int max=-0xffffff;
    func(root,&max);
    return max;
}

实现 Trie (前缀树)

寻找两个正序数组的中位数

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //11
        int m = nums1.length;
        int n = nums2.length;
        if (m > n) {
            return findMedianSortedArrays(nums2, nums1);
        }
        int left = 0;
        int right = m;
        while (left <= right) {
            int i = (left + right) / 2;
            int j = (m + n + 1) / 2 - i;
            int ALeftMax = (i == 0 ? Integer.MIN_VALUE : nums1[i - 1]);
            int ARightMin = (i == m ? Integer.MAX_VALUE : nums1[i]);
            int BLeftMax = (j == 0 ? Integer.MIN_VALUE : nums2[j - 1]);
            int BRightMin = (j == n ? Integer.MAX_VALUE : nums2[j]);
            if (ALeftMax <= BRightMin && BLeftMax <= ARightMin) {
                if ((m + n) % 2 == 1) {
                    return Math.max(ALeftMax, BLeftMax);
                } else {
                    return (Math.max(ALeftMax, BLeftMax) + Math.min(ARightMin, BRightMin)) / 2.0;
                }
            } else if (ALeftMax > BRightMin) {
                right = i - 1;
            } else {
                left = i + 1;
            }
        }
        return -1;
    }
}