本文最后更新于:9 个月前

学习了那么多的数据结构和算法,到了检验学习成果的时刻了!!😎

关于数组和链表的几个必知必会的代码实现

数组

  • 实现一个支持动态扩容的数组

  • 实现一个大小固定的有序数组,支持动态增删改操作

  • 实现两个有序数组合并为一个有序数组

链表

  • 实现单链表、循环链表、双向链表,支持增删操作

  • 实现单链表反转

  • 实现两个有序的链表合并为一个有序链表

  • 实现求链表的中间结点

数组题目

Three Sum(求三数之和)

题目:

给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 abc ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。

注意:答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]

满足要求的三元组集合为:

[
  [-1, 0, 1],
  [-1, -1, 2]
]

思路:

最外层控制一个元素的循环,内层用双指针,一个从头到尾扫描,另一个从尾到头扫描,判断三个元素的值之和是否为零。

注意:相同的元素需要跳过

代码:

public List<List<Integer>> threeSum(int[] nums) {
    if (nums.length < 3) {
        return new ArrayList<>();
    }
    //排序
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] > 0) {
            break; // 如果当前数字大于0,则三数之和一定大于0,所以结束循环(没有0或负数怎么加也不会等于0)
        }
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue; // 去重
        }
        int left = i + 1;
        int right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if(sum == 0){
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                while (left < right && nums[left] == nums[left+1]) {
                    left++; // 去重
                }
                while (left < right && nums[right] == nums[right-1]) {
                    right--; // 去重
                }
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right --;
            }
        }
    }
    return result;
}

Majority Element(求众数)

题目:

给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ $\frac n 2$ ⌋ 的元素。

你可以假设数组是非空的,并且给定的数组总是存在众数
示例 1:

输入: [3,2,3]
输出: 3
示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

思路:

根据题意,众数是指在数组中出现次数大于 ⌊ $\frac n 2$ ⌋ 的元素,因此可以先把数组排序,数组$\frac n 2$下标处就是众数。

代码:

public int majorityElement(int[] nums) {
    if (nums.length < 1) {
        return 0;
    }
    Arrays.sort(nums);
    return nums[nums.length/2];
}

然而你以为这样就完了吗?通过官方题解,还看到了一种更厉害的解法,那就是 Boyer-Moore 投票算法,思路如下:

如果我们把众数记为 $+1$ ,把其他数记为 $−1$ ,将它们全部加起来,显然和大于 0 ,从结果本身我们可以看出众数比其他数多。

本质上,Boyer-Moore 算法就是找 nums 的一个后缀 $suf$ ,其中 $suf[0]$ 就是后缀中的众数。我们维护一个计数器,如果遇到一个我们目前的候选众数,就将计数器加一,否则减一。只要计数器等于 0 > > ,我们就将 nums 中之前访问的数字全部忘记 ,并把下一个数字当做候选的众数。直观上这个算法不是特别明显为何是对的,我们先看下面这个例子(竖线用来划分每次计数器归零的情况)

[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]

首先,下标为 07 被当做众数的第一个候选。在下标为 5 处,计数器会变回 0。所以下标为 65 是下一个众数的候选者。由于这个例子中 7 是真正的众数,所以通过忽略掉前面的数字,我们忽略掉了同样多数目的众数和非众数。因此,7 仍然是剩下数字中的众数。

[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 5, 5, 5, 5]

现在,众数是 5 (在计数器归零的时候我们把候选从 7 变成了 5)。此时,我们的候选者并不是真正的众数,但是我们在遗忘前面的数字的时候,要去掉相同数目的众数和非众数(如果遗忘更多的非众数,会导致计数器变成负数)。

因此,上面的过程说明了我们可以放心地遗忘前面的数字,并继续求解剩下数字中的众数。最后,总有一个后缀满足计数器是大于 0 的,此时这个后缀的众数就是整个数组的众数。

代码如下:

public int majorityElement(int[] nums) {
    int count = 0;
    Integer candidate = null;

    for (int num : nums) {
        if (count == 0) {
            candidate = num;
        }
        count += (num == candidate) ? 1 : -1;
    }

    return candidate;
}

Missing Positive(求缺失的第一个正数)

题目:

给定一个未排序的整数数组,找出其中没有出现的最小的正整数。

示例 1:

输入: [1,2,0]
输出: 3

示例 2:

输入: [7,8,9,11,12]
输出: 1

说明:

你的算法的时间复杂度应为$O(n)$,并且只能使用常数级别的空间。

思路:看到说明后就知道不能用哈希表来解决了,所以要换个思路,想了半天想不明白,咱也不敢说,咱也不敢问,只好去偷瞄一眼官方题解,看了后才觉得还是大佬们🐂🏆。点击此处链接

代码如下:

public int firstMissingPositive(int[] nums) {
  int n = nums.length;

  // 基本情况
  int contains = 0;
  for (int i = 0; i < n; i++)
    if (nums[i] == 1) {
      contains++;
      break;
    }

  if (contains == 0)
    return 1;

  // nums = [1]
  if (n == 1)
    return 2;

  // 用 1 替换负数,0,
  // 和大于 n 的数
  // 在转换以后,nums 只会包含
  // 正数
  for (int i = 0; i < n; i++)
    if ((nums[i] <= 0) || (nums[i] > n))
      nums[i] = 1;

  // 使用索引和数字符号作为检查器
  // 例如,如果 nums[1] 是负数表示在数组中出现了数字 `1`
  // 如果 nums[2] 是正数 表示数字 2 没有出现
  for (int i = 0; i < n; i++) {
    int a = Math.abs(nums[i]);
    // 如果发现了一个数字 a - 改变第 a 个元素的符号
    // 注意重复元素只需操作一次
    if (a == n)
      nums[0] = - Math.abs(nums[0]);
    else
      nums[a] = - Math.abs(nums[a]);
  }

  // 现在第一个正数的下标
  // 就是第一个缺失的数
  for (int i = 1; i < n; i++) {
    if (nums[i] > 0)
      return i;
  }

  if (nums[0] > 0)
    return n;

  return n + 1;
}

链表题目

Linked List Cycle I(环形链表)

题目:

给定一个链表,判断链表中是否有环。

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。
image.png

思路:此题即是单向链表的常见操作中链表环的检测,可以直接点击点链接跳转去看看。

这里直接给出代码:

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
}

Merge k Sorted Lists(合并 k 个排序链表)

题目:

合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:

[
  1->4->5,
  1->3->4,
  2->6
]

输出: 1->1->2->3->4->4->5->6

思路:这里直接给出官方题解的链接,因为有很多种方法可以解决这个问题,详见官方题解

代码如下:这里给出利用优先队列实现的代码

public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(node -> node.val));
    ListNode dummy = new ListNode(0);
    ListNode p = dummy;
    queue.addAll(Stream.of(lists).filter(Objects::nonNull).collect(Collectors.toList()));
    while (!queue.isEmpty()) {
        ListNode node = queue.poll();
        p.next = node;
        p = p.next;
        if (node.next != null)
            queue.add(node.next);
    }
    return dummy.next;
}

做完题目之后,你可以点击左侧的分享,把测试题分享给你的朋友,说不定就帮他解决了一个难题。也可以给我留言,和我一起分享。


本博客所有文章除特别声明外,均采用 CC BY-SA 3.0协议 。转载请注明出处!

LeetCode刷题:栈、队列和递归 上一篇
53.算法实战(五) 下一篇

欢迎关注我的公众号😘