526互联

分治法LeetCode经典例题（c语言解法）

发布时间 2024-01-05 22:54:58作者: xue79
  1. 多数元素https://leetcode.cn/problems/majority-element/description/
    `//计数
    int count(int* nums,int target,int left,int right){
    int cnt = 0;
    for(int i = left;i <= right;i++){
    if(nums[i] == target)
    cnt++;
    }
    return cnt;
    }

int mergeSort(int* nums,int left,int right){
if(left == right){
return nums[left];
}
int mid = (left + right) / 2;
int le = mergeSort(nums,left,mid);
int ri = mergeSort(nums,mid+1,right);
if(le == ri){
return le;
}
int leftCount = count(nums,le,left,right);
int rightCount = count(nums,ri,left,right);
return leftCount > rightCount ? le : ri;
}

int majorityElement(int* nums, int numsSize) {
return mergeSort(nums,0,numsSize - 1);
}105. 从前序与中序遍历序列构造二叉树[https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/]()/**

  • Definition for a binary tree node.
  • struct TreeNode {
  • int val;

  • struct TreeNode *left;

  • struct TreeNode *right;
  • };
    */

struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
if(!preorderSize)
return NULL;
struct TreeNode root = (struct TreeNode)malloc(sizeof(struct TreeNode));
root->val = preorder[0];
root->left = root->right = NULL;
if(preorderSize == 1)
return root;
int index; //查找中序遍历中根结点的位置
for(index = 0;index < inorderSize;index++){
if(inorder[index] == root->val){
break;
}
}
//划分中序序列的数据
int leftNum = index;
int rightNum = inorderSize - index - 1;

int *leftInorder = inorder;
int *rightInorder = inorder + index + 1;

int *leftPreorder = preorder + 1;
int *rightPreorder = preorder + leftNum + 1;

root->left = buildTree(leftPreorder,leftNum,leftInorder,leftNum);
root->right = buildTree(rightPreorder,rightNum,rightInorder,rightNum);
return root;

}23.合并k个有序链表[https://leetcode.cn/problems/merge-k-sorted-lists/description/]()/**

  • Definition for singly-linked list.
  • struct ListNode {
  • int val;

  • struct ListNode *next;
  • };
    /
    //二路归并
    struct listNode     mergeSort(struct ListNode* list1,struct ListNode* list2){
    if(!list1){
    return list2;
    }
    if(!list2){
    return list1;
    }
    if(list1->val < list2->val){
    list1->next = mergeSort(list1->next,list2);
    return list1;
    }
    else{
    list2->next = mergeSort(list1,list2->next);
    return list2;
    }
    }

struct ListNode* mergeList(struct ListNode** lists,int left ,int right){

if(left == right){
    return lists[left];
}
struct ListNode *leftChain = NULL;
struct ListNode *rightChain = NULL;
int mid = (left + right) / 2;
leftChain = mergeList(lists,left,mid);
rightChain = mergeList(lists,mid + 1,right);
return mergeSort(leftChain,rightChain);

}
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
if(!listsSize)
return NULL;
return mergeList(lists,0,listsSize - 1);
}`