算法--2023.1.14

1.力扣435--无重叠区间

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals,(o1,o2)->(o1[1]-o2[1]));
        int res = 1;
        int n = intervals.length;
        int start = intervals[0][0], end = intervals[0][1];
        for(int i = 1; i < n; i++){
            int l = intervals[i][0], r = intervals[i][1];
            if(l<end){
                continue;
            }else{
                start = l;
                end = r;
                res++;
            }
        }
        return n-res;
        
    }
}

2.力扣152--乘积最大子数组

class Solution {
    //思路：动态规划
    //在每个节点，保留遍历到当前节点的最大值和最小值
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int[] dp1 = new int[n+1];
        int[] dp2 = new int[n+1];
        int res = nums[0];
        dp1[0] = 1;dp2[0] = 1;
        for(int i = 1;i<=n;i++){
            //temp1：遍历到上一个节点最大值与当前节点的乘积
            int temp1 = dp1[i-1] * nums[i-1];
            //temp2：遍历到上一个节点最小值与当前节点的乘积
            int temp2 = dp2[i-1] * nums[i-1];
            //最大值：temp1,temp2，当前节点中选择一个最大的（因为序列中可能会存在零，所以当前节点的最大值可能是该节点的值）
            dp1[i] = Math.max(nums[i-1],Math.max(temp1,temp2));
            //最小值：同理
            dp2[i] = Math.min(nums[i-1],Math.min(temp1,temp2));
            res = Math.max(res,dp1[i]);
        }
        return res;
    }
}

3.力扣151--最小栈

class MinStack {

    //两个数组。一个按照栈的逻辑后进先出，另一个保存当前节点的最小值
    public static int[] nums1, nums2;
    public static int N, cnt;  
    
    public MinStack() {
        N = 100010;
        nums1 = new int[N];
        nums2 = new int[N];
        nums1[0] = Integer.MAX_VALUE;
        nums2[0] = Integer.MAX_VALUE;
        cnt = 1;
    }
    
    public void push(int val) {
        nums1[cnt] = val;
        if(val<nums2[cnt-1]){
            nums2[cnt] = val;
        }else{
            nums2[cnt] = nums2[cnt-1];
        }
        cnt++;
    }
    
    public void pop() {
        cnt--;
    }
    
    public int top() {
        return nums1[cnt-1];
    }
    
    public int getMin() {
        return nums2[cnt-1];
    }
}

4.力扣160--相交链表

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p = headA, q = headB;
        while(true){
            if(p == q){
                return p;
            }else{
                if(p!=null){
                    p = p.next;
                }else{
                     p =headB;
                }
                if(q!=null){
                    q = q.next;
                }else{
                    q = headA;
                }
            }
        }
        //return p;
    }
}

5.力扣169--多数元素

class Solution {
    //两个变量temp，cnt，temp相当于一个容器但里面只有一个数据,保存的是当前的数据，cnt保存的是当前数据的个数，如果遍历下一个数据与当前
    //数据不相同，则cnt--，否则cnt++；如果cnt == 0 ，则temp保存当前的值
    public int majorityElement(int[] nums) {
        int temp = 0, cnt = 0;
        for(int t : nums){
            if(cnt == 0){
                temp = t;
                cnt++;
            }else{
                if(temp == t){
                    cnt++;
                }else{
                    cnt--;
                }
            } 
            //System.out.println(temp);
        }
        return temp;
    }
}