区间和的个数

区间和的个数
统计区间和位于[lower,upper]范围内的区间个数
通过归并排序进行统计

最大小和

最大小和

package org.example.lc11;

public class Test05 {
    public static void main(String[] args) {
        int smallSum = getSmallSum(new int[]{1, 3, 5, 2, 4,6});
        System.out.println(smallSum);
    }

    //最大小和
    public static int getSmallSum(int[] nums){
        int[] temp=new int[nums.length];
        int res=mergeSort(nums,0,nums.length-1,temp);
        return res;
    }

    //通过归并排序
    public static int mergeSort(int[] nums,int left,int right,int[] temp){
        int res=0;
        if (left < right) {
            int mid=(left+right)/2;
            int lcnt=mergeSort(nums,left,mid,temp);
            int rcnt=mergeSort(nums,mid+1,right,temp);
            int c=merge(nums,left,mid,right,temp);
            res=lcnt+rcnt+c;
        }
        return res;
    }

    public static int merge(int[] nums,int left,int mid,int right,int[] temp){
        int res=0;
        int l=left;int r=mid+1;int index=0;
        while (l <= mid && r <= right) {
            if(nums[l]<nums[r]){
                res+=(nums[l]*(right-r+1));
                temp[index++]=nums[l++];
            }else{
                temp[index++]=nums[r++];
            }
        }
        while(l<=mid){
            temp[index++]=nums[l++];
        }
        while(r<=right){
            temp[index++]=nums[r++];
        }
        index=0;
        for(int i=left;i<=right;i++){
            nums[i]=temp[index++];
        }
        return res;
    }

}

逆序对 等价表述，给定一个数组，需要进行多少次交换使数组有序

逆序对
相对于数组小和，只需要修改merge过程中；如果 nums[l]>nums[r]; [l,mid]区间所有的元素都是逆序对

也可以定义全局变量进行逆序对计数

 package org.example.lc11;

public class Test05 {
    public static void main(String[] args) {
        int smallSum = getSmallSum(new int[]{1,2,3});
        System.out.println(smallSum);
    }

    //最大小和
    public static int getSmallSum(int[] nums){
        int[] temp=new int[nums.length];
        int res=mergeSort(nums,0,nums.length-1,temp);
        return res;
    }

    //通过归并排序
    public static int mergeSort(int[] nums,int left,int right,int[] temp){
        int res=0;
        if (left < right) {
            int mid=(left+right)/2;
            int lcnt=mergeSort(nums,left,mid,temp);
            int rcnt=mergeSort(nums,mid+1,right,temp);
            int c=merge(nums,left,mid,right,temp);
            res=lcnt+rcnt+c;
        }
        return res;
    }

    public static int merge(int[] nums,int left,int mid,int right,int[] temp){
        int res=0;
        int l=left;int r=mid+1;int index=0;
        while (l <= mid && r <= right) {
            if(nums[r]<nums[l]){
                temp[index++]=nums[r++];
                res+=mid-l+1;
            }else{
                temp[index++]=nums[l++];
            }
        }
        while(l<=mid){
            temp[index++]=nums[l++];
        }
        while(r<=right){
            temp[index++]=nums[r++];
        }
        index=0;
        for(int i=left;i<=right;i++){
            nums[i]=temp[index++];
        }
        return res;
    }

}

归并排序使链表有序

归并排序使链表有序

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        ListNode res=mergeSort(head,null);
        return res;
    }

    public ListNode mergeSort(ListNode head,ListNode tail){
        //通过归并方式
        if(head==null){
            return head;
        }
        if(head.next==tail){//对应的只有一个节点
            head.next=null;
            return head;
        }
        // //通过快慢指针获得中间节点
        ListNode slow=head;ListNode fast=head;
        while(fast!=tail&&fast.next!=tail){
            slow=slow.next;
            fast=fast.next.next;
        }

        // ListNode fast=head;ListNode slow=head;
        // while(fast!=tail){
        //     fast=fast.next;
        //     slow=slow.next;
        //     if(fast!=tail){
        //         fast=fast.next;
        //     }
        // }
        ListNode mid=slow;
        ListNode node1=mergeSort(head,mid);//对应的区间是左闭右开区间
        ListNode node2=mergeSort(mid,tail);
        ListNode res=merge(node1,node2);
        return res;
    }

    public ListNode merge(ListNode l1,ListNode l2){
        ListNode l=l1;ListNode r=l2;
        ListNode dummy=new ListNode(0);
        ListNode res=dummy;
        while(l!=null&&r!=null){
            if(l.val<r.val){
                res.next=l;
                l=l.next;
            }else{
                res.next=r;
                r=r.next;
            }
            res=res.next;
        }
        if(l!=null){
            res.next=l;
        }
        if(r!=null){
            res.next=r;
        }
        return dummy.next;
    }

}