21xrx.com
2024-12-23 01:41:41 Monday
登录
文章检索 我的文章 写文章
Java面试必备:经典算法详解及代码实现
2023-06-17 13:01:20 深夜i     --     --
Java面试 算法实现 摩尔投票法 反转链表 快速排序

介绍

随着Java编程日益成为许多公司的必备技能,Java面试也成为了求职者们不可忽略的一环。在Java面试中,算法成为了考察求职者能力的常见方式。本文将介绍Java面试中常见的几种经典算法,包括其思路、代码实现以及优化措施,以帮助读者在面试中更好的回答相关问题。

算法1:数组中出现次数超过一半的数字

这是一道常规问题,求给定数组中出现次数超过一半的数字。我们可以使用HashMap来较为轻松地解决该问题,但是这里介绍另一种方法:摩尔投票法。

摩尔投票法的基本思想是:选出某一个候选数字,然后遍历整个数组,如果遇到相同的数字则将计数器加1,否则将计数器减1。如果计数器已经减到了0,则更换新的候选数字。最后被选出的候选数字就是出现次数超过一半的数字。

代码实现:

public int findNum(int[] nums) {

  int candidate = nums[0];

  int count = 1;

  for (int i = 1; i < nums.length; i++) {

    if (candidate == nums[i]) {

      count++;

    } else {

      count--;

      if (count == 0) {

        candidate = nums[i+1];

      }

    }

  }

  return candidate;

}

算法2:反转链表

反转一个单链表的思路很好理解,就是从头到尾遍历链表,每次将当前节点的next指向前一个节点即可。但是,在实现的时候需要注意一些细节问题。比如,我们需要三个指针进行遍历,分别指向当前节点、前一个节点以及临时节点,遍历的时候遍历的是当前节点,但是将next指向前一个节点。

代码实现:

public ListNode reverseList(ListNode head) {

  ListNode cur = head;

  ListNode pre = null;

  while (cur != null)

    ListNode temp = cur.next;

    cur.next = pre;

    pre = cur;

    cur = temp;

  return pre;

}

算法3:快速排序

快速排序是一种基于分治思想的排序算法,其核心在于通过一系列的操作将待排序数组分割成若干个子数组,先排序左右子数组,然后通过将左右子数组分别放在支点的左右进行合并。这里实现的是基于递归的快速排序算法。

代码实现:

public void quickSort(int[] nums, int left, int right) {

  if (left >= right)

    return;

  int pivot = partition(nums, left, right);

  quickSort(nums, left, pivot-1);

  quickSort(nums, pivot+1, right);

}

public int partition(int[] nums, int left, int right) {

  int pivot = nums[left];

  int i = left;

  int j = right;

  while (i < j) {

    while (i < j && nums[j] >= pivot)

      j--;

    nums[i] = nums[j];

    while (i < j && nums[i] <= pivot) {

      i++;

    }

    nums[j] = nums[i];

  }

  nums[i] = pivot;

  return i;

}

  
  

评论区

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