MyBlog4月6日
LeetCode 026重排链表
import java.util.ArrayList;
import java.util.List;
/**
* 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 void reorderList(ListNode head) {
/*
if (head == null || head.next == null) return;
List<ListNode> list = new ArrayList<>(); //构建一个集合存储所有链表节点
while (head != null) {
list.add(head);
head = head.next;
}
int len = list.size();
for (int i = 0; i < len / 2; i++) {
list.get(i).next = list.get(len - 1 - i);
list.get(len - 1 - i).next = list.get(i + 1);
}
list.get(len / 2).next = null; //最后一个元素会自己指向自己构成环，所以得设置为null
}
*/
//3大步 : 1,找到中间节点 2,反转中间节点后面的那些节点 3,左边一个右边一个这么连起来，最后别忘了中间节点的next置为null
if(head == null || head.next == null)return;
ListNode slow = head;
ListNode fast = head.next;
while(fast!= null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
ListNode mid = slow;
ListNode r = reverse(mid.next); //经过反转后的 r 现在是右边部分的第一个元素 即原来的末尾元素
mid.next = null;
ListNode l = head; // l是左边部分的第一个元素
merge(l,r);
}
public void merge(ListNode l , ListNode r){
int i = 0;
ListNode head = new ListNode();
while( r!= null){
if(i++ % 2 == 0){
head.next = l;
l = l.next;
}else {
head.next = r;
r = r.next;
}
head = head.next;
}
head.next = l; //因为奇数节点的时候，左边多一个，所以右边肯定先退出，所以这里l可能为null,也可能为中间节点的值
}
public ListNode reverse(ListNode midNext){
ListNode head = null;
ListNode temp = null;
while(midNext != null){
temp = midNext.next; // 将新插入的节点的后面节点先保存起来
midNext.next = head;
head = midNext; //head 永远指向 新插入的元素，那些早先插入的元素会渐渐的移动到后边去
midNext = temp;
}
return head;
}
}
//leetcode submit region end(Prohibit modification and deletion)
LeetCode 077链表排序
/**
* 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) {
if (head == null || head.next == null) return head; //如果传进来的head是null 或者只有 head一个节点，返回head
return recursion(head);
}
public ListNode recursion(ListNode head) {
if (head.next == null) return head; //head后面没有节点了,意味着递归划分问题规模到一个节点了
ListNode slow = head;
ListNode fast = head.next; //上面的if不成立，那么这里fast就会是有效节点
while (fast != null && fast.next != null) { //虽然跳出循环的时候fast可能是null也可能是最后一个节点，但不重要，slow肯定是中间位置
slow = slow.next; //一个一个节点移动
fast = fast.next.next;
}
ListNode midAfter1 = slow.next; //中间节点后一个
slow.next = null; // 断链，不断链 就无法分成独立的两部分
ListNode leftPart = recursion(head);
ListNode rightPart = recursion(midAfter1);
return merge(leftPart,rightPart);
}
public ListNode merge(ListNode leftPart, ListNode rightPart) {
ListNode head = new ListNode(); //新建一个头节点
ListNode cur = head; //cur 也指向 head
while (leftPart != null && rightPart != null) {
if (leftPart.val <= rightPart.val) {
cur.next = leftPart; //该节点连在cur节点后面
cur = leftPart; //cur指向当前新连上节点
leftPart = leftPart.next; //左部分的节点往后移动
} else {
cur.next = rightPart;
cur = rightPart;
rightPart = rightPart.next;
}
}
//跳出while 后，肯定 左右 有一部分的节点还没有连上
if (leftPart!= null) cur.next = leftPart;
else if (rightPart!= null) cur.next = rightPart;
return head.next;
}
}
归并排序
import java.util.Arrays;
/**
* @Author: 幸幸
* @Date: 2023/04/06/14:56
* @Description:
*/
public class MergeSort {
public static void main(String[] args) {
int[]arr = {1,3,5,7,2,4,6};
recursion(arr, 0 , arr.length -1);
System.out.println(Arrays.toString(arr));
}
public static void recursion(int[] arr, int l, int r) {
if (l == r) return;
int mid = l + ((r - l) >> 1);
recursion(arr, l, mid);
recursion(arr, mid + 1, r);
merge(arr, l, mid, r); //分析递归的最后一次，应该是左边一个元素 ， 右边一个元素，将它们 并起来
}
public static void merge(int[] arr, int l, int mid, int r) {
int[] help = new int[r - l + 1];
int helpIndex = 0;
//用 一个指针标记左边那一队 ， 用另一个指针标记 右边那一队
int leftPoint = l;
int rightPoint = mid+1;
while (leftPoint <= mid && rightPoint <= r){ //如果某一个指针超出了界限，只要把剩下那一队的剩余元素直接加入help数组中
help[helpIndex++] = arr[leftPoint]<=arr[rightPoint]?arr[leftPoint++]:arr[rightPoint++];
}
while(leftPoint<=mid) help[helpIndex++] = arr[leftPoint++];
while(rightPoint<=r)help[helpIndex++] = arr[rightPoint++];
//别忘了对原数组操作
for(int i = 0 ; i < help.length ; i++){
arr[l + i] = help[i]; //l + i 很重要，l是相对的
}
}
}
顺序表
/**
* @Author: 幸幸
* @Date: 2023/04/06/9:29
* @Description:
*/
public class SqList<E> {
private int size;
private final int initCapacity = 10;
private int capacity;
private E[] data;
public SqList() {
data = (E[]) new Object[initCapacity];
capacity = initCapacity;
size = 0;
}
private void updateCapacity(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
capacity = newCapacity;
}
public void createList(E[] a) { //将数组a的元素放进线性表中
size = 0; //在这要清零。
for (int i = 0; i < a.length; i++) {
if (size == capacity) updateCapacity(2 * size);
data[i] = a[i];
size++;
}
}
public void add(E e) {
if (size == capacity) updateCapacity(2 * size);
data[size++] = e; //新加的元素的下标为size没问题，加完后还要size++，因为0-size 有size+1 个元素
}
public int size() {
return size;
}
public void remove(int index) {
if (index < 0 || index >= size) throw new IllegalArgumentException("索引不正确");
for (int i = index; i < size - 1; i++) {
data[i] = data[i + 1];
}
size--;
if (size > initCapacity && size == capacity / 4) updateCapacity(capacity / 2);
}
public void printSqList() {
for (int i = 0; i < size; i++) {
System.out.print(data[i] + " ");
}
}
public void setSize(int len) { //设置线性表的size大小
if (len < 0 || len > size) throw new IllegalArgumentException("长度不允许小于0 或大于当前长度");
size = len;
}
//根据索引设置线性表的元素
public void setElem(int index, E e) {
if (index < 0 || index >= size) throw new IllegalArgumentException("索引不正确");
data[index] = e;
}
public E getElem(int index) {
if (index < 0 || index >= size) throw new IllegalArgumentException("索引不正确");
return data[index];
}
public int getNo(E e) {
int i = 0;
while (i < size && data[i] != e) { //不满足循环条件，i会一直增加，满足就退出，此刻i为第一个出现位置
i++;
}
if (i >= size) return -1;
return i;
}
public void swap(int indexA, int indexB) {
if (indexA < 0 || indexA >= size || indexB < 0 || indexB >= size) throw new IllegalArgumentException("索引取值不对");
var temp = data[indexA];
data[indexA] = data[indexB];
data[indexB] = temp;
}
public void insert(int index, E e) {
if (size == capacity) updateCapacity(2 * size); //如果容量此刻满了扩容
if (index < 0 || index >= size) throw new IllegalArgumentException("索引不正确");
for (int i = size; i > index; i--) {
data[i] = data[i - 1];
}
data[index] = e;
size++;
}
public String toString() {
String ans = "";
for (int i = 0; i < size; i++) {
ans += data[i];
}
return ans;
}
public void reverse(SqList<Integer> sqList) { //将整型数据的线性表所有元素逆置。
int i = 0;
int j = sqList.size - 1;
while (i < j) {
swap(i, j);
i++;
j--;
}
}
public void swapMaxAndMin(SqList<Integer> sqList) { //传进来一个整型顺序表，交换内部的最大最小值位置
int maxIndex = 0, minIndex = 0;
for (int i = 0; i < sqList.size; i++) {
if (sqList.getElem(i) > sqList.getElem(maxIndex)) maxIndex = i;
else if (sqList.getElem(i) < sqList.getElem(minIndex)) minIndex = i;
}
sqList.swap(maxIndex, minIndex); //小心有可能识别的对象调用sqList
}
public boolean deleteKElements(SqList<Integer> sqList, int startIndex, int k) {
if (startIndex < 0 || startIndex >= sqList.size || k < 0 || k + startIndex > size)
return false; //如果起始索引小于0或者大于sqList的长度，或者删除负数个或删除的最大元素大于size
for (int i = startIndex; i < startIndex + k; i++) { //这里的删除方式并不是删除指针在移动，删除指针一直是一个位子
sqList.remove(startIndex); //remove方法中会改变size的
}
return true;
}
public boolean deleteKElements2(SqList<Integer> sqList, int startIndex, int k) { //删除从startIndex（包括本身的）之后的共k个元素，最后要删除的元素下标为i+k-1，那只要将i+k --size-1 的元素从startIndex摆放即可
if (startIndex < 0 || startIndex >= sqList.size || k < 0 || k + startIndex > sqList.size) return false;
for (int i = startIndex + k; i < sqList.size; i++) {
sqList.setElem(i - k, sqList.getElem(i));
}
sqList.setSize(sqList.size - k);
return true;
}
}
今天下雨，晚上再看一会，今天心情感觉还可以