当前位置：首页 > news >正文

java-数据结构

news 2025/1/11 7:43:50

一.链表

单向链表

/单向链表
public class SinglyLinkedList implements Iterable<Integer> {//头节点private Node head =null;//头指针//节点类private static   class  Node{int value;//值Node next;//下一个节点的指针public Node(int value, Node next) {this.value = value;this.next = next;}}
}

addFirst方法

 public  void  addFirst(int value){//1.链表为空//  head =new Node(value,null);//2.链表非空head =new Node(value,head

遍历链表

一

public  void  loop1(Consumer<Integer> consumer){Node p =head;while (p!=null){consumer.accept(p.value);p=p.next;}}

二

  public  void  loop2(Consumer<Integer> consumer){for (Node p =head;p!=null;p=p.next){consumer.accept(p.value);}}

三

@Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {SinglyLinkedList.Node p = head;@Overridepublic boolean hasNext() {//是否有下一个元素return p != null;}@Overridepublic Integer next() {//返回当前值，并指向下一个元素int v = p.value;p = p.next;return v;}};}

Test类e

 SinglyLinkedList LinkedList = new SinglyLinkedList();LinkedList.addFirst(1);LinkedList.addFirst(2);LinkedList.addFirst(3);LinkedList.addFirst(4);LinkedList.addFirst(5);LinkedList.loop1(value->{System.out.println(value);});System.out.println("------------------------");LinkedList.loop2(value->{System.out.println(value);});//使用迭代器去遍历链表for (Integer value : LinkedList) {System.out.println(value);}}

二分查找

1.基础版

 public  static String binarysearch(int []arr, int data){//1.定义两个变量，一个站左边，一个站右边int left=0;int right=arr.length-1;while (left<=right){int middle=(left+right)/2;if (data<arr[middle]){right=middle-1;}else if(data>arr[middle]){left=middle+1;}else {return  String.valueOf(middle);}}return "该数组没有该数字";}

1.关于为什么在中间值不使用middle=（left+right）/2；

因为Java中使用在Java中，进行二分查找时，直接使用 middle = (left + right) / 2 可能会遇到整数溢出的问题。这是因为当 left 和 right 都非常大且接近 Integer.MAX_VALUE 时，它们的和可能会超过 int 类型的最大值，从而导致溢出。

改进版

int middle = left + (right - left) / 2;

无符号右移一位相当于除以2向下取整

那么

int middle = left +right >>> 1;

2.关于为什么使用left<=right去作为判断跳出循环的条件而不是去用left<right去作为判断的条件

如果使用 left < right 作为条件，那么在最后一次迭代中，当 left 和 right 相邻时（即 left = right - 1），循环就会提前终止，从而可能错过目标元素（如果它正好位于 left 或 right 指向的位置）。

left ==right 意味着它们指向的元素也会参与比较，left < right 只意味着middle指向的元素参与比较

2.改进版

核心为将right不作为比较元素

public  static String binarysearch(int [] arr,int target){int left =0, right =arr.length;while (left<right){int  middle =left+right >>> 1;if(target<arr[middle]){right=middle;}else if(arr[middle]<target){left =middle +1;}else {return  String.valueOf(middle);}}return "没有找到该数字" ;}

该写法的特点：

i,j 对应着搜索区间 [0,a.length)（注意是左闭右开的区间），i<j 意味着搜索区间内还有未比较的元素，j 指向的一定不是查找目标

思考：为啥这次不加 i==j 的条件了？

回答：这回 j 指向的不是查找目标，如果还加 i==j 条件，就意味着 j 指向的还会再次比较，找不到时，会死循环

1）令right为arr.length是确定right为数组边界外一值并不是数组中的值不希望right参与比较，在其中left是参加比较的值而right是不参与比较的值

使得在target在小于arr[middle]时令right=middle

2）关于循环跳出条件为left<right的原因

当查找的数没有在数组中时会进行死循环报错

3.平衡版

问题切入点：

l为总循环次数，当元素在最右边与最左边时的循环次数不一致。在最右边要进行2*l次比较

时间复杂度都为log（n）。

核心为进行两分支（if else），比较一次，在循环中只是缩小范围不进行返回值

注意判断循环条件为（left+1<right）

  public  static String binarysearch(int [] arr,int target) {int left =0, right=arr.length;while (1<right-left){int middle =(left+right)>>>1;if(target<arr[middle]){right=middle;}else {left=middle;}}if(arr[left]==target){return  String.valueOf(left);}else {return  "没有该数字";}}

4.java版二分查找

private static int binarySearch0(long[] a, int fromIndex, int toIndex,long key) {int low = fromIndex;int high = toIndex - 1;while (low <= high) {int mid = (low + high) >>> 1;long midVal = a[mid];if (midVal < key)low = mid + 1;else if (midVal > key)high = mid - 1;elsereturn mid; // key found}return -(low + 1);  // key not found.}

关于使用Java自身提供的区别在于返回值当查询不到数据时返回的是-（插入值+1）

return -(low + 1); // key not found.

eg 当我的数组为{1，23，45，77，123}时我查找12时就会返回-2（因为12拍数组第二所以-（1+1）=-2）

 int arr2[]={12,14,123,434,56};System.out.println(Arrays.binarySearch(arr2, 13));

返回-2

5.leftmost与rightmost

实现查找重复数字中最左边序号

  public static int binarySearchLeftMost(int arr[], int target) {int left = 0, right = arr.length - 1;int candidate = -1;while (left <= right) {int middle = (left + right) >>> 1;if (target < arr[middle]) {right = middle - 1;} else if (arr[middle] < target) {left = middle + 1;} else {//记录候选者位置candidate = middle;right = middle - 1; // 继续向左搜索}}return candidate;}

实现查找重复数字中最右边序号

区别：在边界处不同

// 继续向右搜索，直到找到最右边的位置
left = middle + 1;

public static int binarySearchRightMost(int arr[], int target) {  int left = 0, right = arr.length - 1;  int candidate = -1;  while (left <= right) {  int middle = (left + right) >>> 1;  if (target < arr[middle]) {  right = middle - 1;  } else if (arr[middle] < target) {  left = middle + 1;  } else {  candidate = middle;  // 继续向右搜索，直到找到最右边的位置  left = middle + 1;  }  }

6.几个名词

范围查询

查询x＜4，0...leftmost(4) - 1
查询x ≤ 4，0...rightmost(4)
查询4 ＜ x，rightmost(4) + 1 ... infty
查询4 ≤ x，leftmost(4) ... infty
查询4 ≤ x ≤ 7，leftmost(4) ... rightmost(7)
查询4 ＜ x ＜ 7，rightmost(4) + 1 ... leftmost(7) - 1