Java面试必问——数据结构与算法 |21xrx.com

Java面试必问——数据结构与算法

2023-06-15 11:03:22 深夜i 10 0

Java 面试数据结构算法单链表二分查找快速排序

在Java的面试中，数据结构与算法一直是重点考察的领域之一。掌握好数据结构与算法不仅有助于我们在面试中表现亮眼，同时也能帮助我们更好地解决问题。下面将结合实例介绍几道经典的数据结构与算法面试题。

1. 用Java实现单链表

单链表是一个常见的数据结构，其基本操作包括添加、删除、查找等。下面是用Java实现的单链表代码：

public class ListNode {
  int val;
  ListNode next;
  public ListNode(int val)
    this.val = val;
    this.next = null;
  
}
public class LinkedList {
  public ListNode head;
  // 添加节点
  public void add(int val) {
    ListNode node = new ListNode(val);
    if (head == null)
      head = node;
     else {
      ListNode cur = head;
      while (cur.next != null)
        cur = cur.next;
      
      cur.next = node;
    }
  }
  // 删除节点
  public void delete(ListNode node) {
    ListNode cur = head;
    while (cur.next != null && cur.next != node)
      cur = cur.next;
    
    cur.next = cur.next.next;
  }
  // 遍历链表
  public void traverse() {
    ListNode cur = head;
    while (cur.next != null) {
      System.out.print(cur.val + "->");
      cur = cur.next;
    }
    System.out.println(cur.val);
  }
}
// 测试代码
public class TestLinkedList {
  public static void main(String[] args) {
    LinkedList list = new LinkedList();
    list.add(1);
    list.add(2);
    list.add(3);
    list.traverse();
    ListNode node = list.head.next;
    list.delete(node);
    list.traverse();
  }
}

2. 二分查找

二分查找是一种常见的查找算法，其思想是将查找区间不断缩小，最终找到目标值。下面是一个用Java实现的二分查找代码：

public class BinarySearch {
  // 在有序数组中查找元素x，返回下标
  public static int search(int[] arr, int x) {
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
      int mid = left + (right - left) / 2;
      if (arr[mid] == x)
        return mid;
       else if (arr[mid] < x) {
        left = mid + 1;
      } else
        right = mid - 1;
      
    }
    return -1;
  }
  // 测试代码
  public static void main(String[] args) {
    int[] arr = 7;
    int x = 5;
    int index = search(arr, x);
    System.out.println(index);
  }
}

3. 快速排序

快速排序是一种高效的排序算法，其思想是先选择一个基准值，然后将数组分成两个部分，一部分小于基准值，一部分大于基准值，再对这两个部分进行递归排序。下面是一个用Java实现的快速排序代码：

public class QuickSort {
  // 快速排序
  public static void sort(int[] arr) {
    int n = arr.length;
    if (n <= 1)
      return;
    
    quickSort(arr, 0, n - 1);
  }
  // 快速排序实现
  private static void quickSort(int[] arr, int left, int right) {
    if (left >= right)
      return;
    
    int i = left;
    int j = right;
    int pivot = arr[left];
    while (i < j) {
      while (i < j && arr[j] >= pivot)
        j--;
      
      arr[i] = arr[j];
      while (i < j && arr[i] <= pivot) {
        i++;
      }
      arr[j] = arr[i];
    }
    arr[i] = pivot;
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
  }
  // 测试代码
  public static void main(String[] args) {
    int[] arr = 5;
    sort(arr);
    for (int num : arr) {
      System.out.print(num + " ");
    }
  }
}

上一篇: idea打包java可执行jar包

下一篇: Java开发者的最高薪资是多少？

评论区

相似文章