刷题DAY10

雨点打透心脏的1/2处 2023-10-13 23:56 51阅读 0赞

## 第一题 ##

小和问题

![96e0e9926fb6420cbfdcd2bc7d38976b.png][]

本质上是归并排序的思想拉

先来一个小小的归并排序

public static void Mergesort(int [] arr) {
    		Process(arr,0,arr.length-1);
    	}
    	public static void Process(int [] arr,int L,int R) {
    		if(L>=R) {
    			return;
    		}
    		int mid = (L+R)/2;
    		Process(arr,L,mid);
    		Process(arr,mid+1,R);
    		Merge(arr,L,R,mid);
    	}
    	public static void Merge(int [] arr,int L,int R,int mid) {
    		int [] tmp = new int [R-L+1];
    		int p1 = L;
    		int p2 = mid+1;
    		int index = 0;
    		while(p1<=mid&&p2<=R) {
    			if(arr[p1]==arr[p2]) {
    				tmp[index++] = arr[p1++];
    			}else if(arr[p1]>arr[p2]){
    				tmp[index++] = arr[p2++];
    			}else {
    				tmp[index++] = arr[p1++];
    			}
    		}
    		if(p1>mid) {
    			while(p2<=R) {
    				tmp[index++] = arr[p2++];
    			}
    		}else {
    			while(p1<=mid) {
    				tmp[index++] = arr[p1++];
    			}
    		}
    		for (int i : tmp) {
    			arr[L++] = i;
    		}
    	}

我们削微改写一下 我们归并排序思想的流程里面 有一个很重要的点 就是所有的左侧点和所有的右侧点都会进行比较 且对于两个数来说 不会进行重复的比较 所以我们只要抓住这个比较时机累加小和就可以了

static int sum = 0;
    	public static void Mergesort(int [] arr) {
    		Process(arr,0,arr.length-1);
    	}
    	public static void Process(int [] arr,int L,int R) {
    		if(L>=R) {
    			return;
    		}
    		int mid = (L+R)/2;
    		Process(arr,L,mid);
    		Process(arr,mid+1,R);
    		Merge(arr,L,R,mid);
    	}
    	public static void Merge(int [] arr,int L,int R,int mid) {
    		int [] tmp = new int [R-L+1];
    		int p1 = L;
    		int p2 = mid+1;
    		int index = 0;
    		while(p1<=mid&&p2<=R) {
    			if(arr[p1]==arr[p2]) {
    				tmp[index++] = arr[p1++];
    			}else if(arr[p1]>arr[p2]){
    				tmp[index++] = arr[p2++];
    				for(int i = p1-1;i>=L;i--) {
    					sum += arr[i];
    				}
    			}else {
    				tmp[index++] = arr[p1++];
    				
    			}
    		}
    		if(p1>mid) {
    			while(p2<=R) {
    				tmp[index++] = arr[p2++];
    				for(int i = p1-1;i>=L;i--) {
    					sum += arr[i];
    				}
    			}
    		}else {
    			while(p1<=mid) {
    				tmp[index++] = arr[p1++];
    			}
    		}
    		for (int i : tmp) {
    			arr[L++] = i;
    		}
    	}
    	public static void main(String[] args) {
    		int [] arr = {1,3,4,2,5};
    		Mergesort(arr);
    		System.out.println(sum);
    	}

## 第二题 ##

给定一个单链表的头节点head，请判断该链表是否为回文结构。

最暴力的 过一遍哈希表

最优解 快慢指针 找到中间点(当个数为偶数时要求找到中下结点) 然后开始反转链表

public boolean isPalindrome(ListNode head) {
       if(head.next==null||head==null) {
    			return true;
    		}
    		if(head.next.next==null) {
    			return head.val==head.next.val?true:false;
    		}
    		ListNode fast = head.next;
    		ListNode slow = head.next;
    		while(fast.next!=null&&fast.next.next!=null) {
    			fast = fast.next.next;
    			slow = slow.next;
    		}
    		ListNode pre = slow;
    		ListNode pos = slow.next.next;
    		slow = slow.next;
    		while(slow!=null) {
    			slow.next = pre;
    			pre = slow;
    			slow = pos;
    			if(pos!=null) {//这个很关键 老是得考虑它会不会越界 包括当前有两个结点的情况
    				pos = pos.next;
    			}		
    		}
    		ListNode p1 = head;
    		while(p1!=pre&&p1.next!=pre) {
    			if(p1.val!=pre.val) {
    				return false;
    			}
    			p1 = p1.next;
    			pre = pre.next;
    			if(p1.next==pre) {
    				return p1.val==pre.val?true:false;//这个basecase也很关键 
    			}
    		}
    		return true;
    	   }

## 第三题 ##

给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 `next` 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 `null`。

为了表示给定链表中的环，我们使用整数 `pos` 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 `pos` 是 `-1`，则在该链表中没有环。**注意，`pos` 仅仅是用于标识环的情况，并不会作为参数传递到函数中。**

**说明：**不允许修改给定的链表。

public ListNode detectCycle(ListNode head) {
            HashSet<ListNode> set = new HashSet<ListNode>();
          while(head!=null) {
        	  
        	  if(set.contains(head)) {
        		  return head;
        	  }
              set.add(head);
        	  head = head.next;
          }
          return null;
        }

好水啊这个中等难度 是因为不是最优解的原因吗

[96e0e9926fb6420cbfdcd2bc7d38976b.png]: https://img-blog.csdnimg.cn/96e0e9926fb6420cbfdcd2bc7d38976b.png