介绍

随着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;

}

相似文章
• 实现链表的反转。
  实现链表的反转。
  
  

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客
• 雅圣洁家政