21xrx.com
2024-09-17 03:43:41 Tuesday
登录
文章检索 我的文章 写文章
Java常用的数据结构和算法：探究
2023-06-15 14:34:15 深夜i     --     --
Java 数据结构 算法

Java是一种流行的编程语言，它支持多种数据结构和算法。在本文中，我们将了解Java中常用的数据结构和算法，并提供一些代码示例。

数据结构

1. 数组

数组是Java中最基本的数据结构之一。它是一个具有相同数据类型的元素集合，在内存中以连续的方式存储。使用数组，可以按照下标随机访问元素。下面是一个创建和访问数组的示例：

int[] arr = new int[5];

arr[0] = 1;

arr[1] = 2;

arr[2] = 3;

arr[3] = 4;

arr[4] = 5;

System.out.println(arr[2]); //输出3

2. 链表

链表是一种动态数据结构，它可以动态增长和缩小。每个节点都包含数据和一个指向下一个节点的引用。在Java中，链表可以通过定义节点类来实现。下面是一个单向链表的例子：

class ListNode {

  int val;

  ListNode next;

  public ListNode(int val)

    this.val = val;

    this.next = null;

}

ListNode head = new ListNode(1);

head.next = new ListNode(2);

head.next.next = new ListNode(3);

System.out.println(head.val); //输出1

3. 栈

栈是一种后进先出（LIFO）的数据结构，可以用数组或链表实现。在Java中，我们可以使用Stack类来实现栈。下面是一个使用Stack类的例子：

Stack stack = new Stack ();

stack.push(1);

stack.push(2);

stack.push(3);

System.out.println(stack.pop()); //输出3

4. 队列

队列是一种先进先出（FIFO）的数据结构。在Java中，我们可以使用Queue接口来实现队列。LinkedList类实现了Queue接口，因此我们可以使用它来创建队列。下面是一个使用LinkedList类的例子：

Queue queue = new LinkedList ();

queue.offer(1);

queue.offer(2);

queue.offer(3);

System.out.println(queue.poll()); //输出1

算法

1. 排序算法

排序算法是解决排序问题的算法。Java中有许多种排序算法，包括冒泡排序、选择排序、插入排序、快速排序等。下面是一个使用快速排序的例子：

public void quickSort(int[] arr, int low, int high) {

  if (low < high) {

    int pivot = partition(arr, low, high);

    quickSort(arr, low, pivot - 1);

    quickSort(arr, pivot + 1, high);

  }

}

public int partition(int[] arr, int low, int high) {

  int pivot = arr[high];

  int i = low - 1;

  for (int j = low; j < high; j++) {

    if (arr[j] <= pivot) {

      i++;

      int temp = arr[i];

      arr[i] = arr[j];

      arr[j] = temp;

    }

  }

  int temp = arr[i + 1];

  arr[i + 1] = arr[high];

  arr[high] = temp;

  return i + 1;

}

2. 搜索算法

搜索算法是解决搜索问题的算法。Java中有许多种搜索算法，包括深度优先搜索、广度优先搜索、二分搜索等。下面是一个使用二分搜索的例子：

public int binarySearch(int[] arr, int target) {

  int left = 0;

  int right = arr.length - 1;

  while (left <= right) {

    int mid = (left + right) / 2;

    if (arr[mid] == target)

      return mid;

     else if (arr[mid] < target) {

      left = mid + 1;

    } else

      right = mid - 1;

  }

  return -1;

}

3. 动态规划

动态规划是解决最优化问题的算法。Java中可以使用递归和记忆化搜索来实现动态规划。下面是一个使用记忆化搜索的例子：

public int fib(int n) {

  int[] memo = new int[n + 1];

  return fibHelper(memo, n);

}

public int fibHelper(int[] memo, int n) {

  if (n == 0 || n == 1) {

    return n;

  }

  if (memo[n] != 0) {

    return memo[n];

  }

  memo[n] = fibHelper(memo, n - 1) + fibHelper(memo, n - 2);

  return memo[n];

}

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复