算法刷题

字数统计: 2.8k   |   阅读时长≈ 11 分钟

链表

使用哈希表可以降低很多问题的思维难度，也比较容易想到，这里就不记录了。

链表反转

牛客面试必刷TOP101, BM1-BM3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public ListNode ReverseList(ListNode head) {
        //step 1：优先处理空链表，空链表不需要反转。
        if(head == null) 
            return null;
        //step 2：我们可以设置两个指针，一个当前节点的指针，一个上一个节点的指针（初始为空）
        ListNode cur = head;
        ListNode pre = null;
        //step 3：遍历整个链表，每到一个节点，断开当前节点与后面节点的指针，并用临时变量记录后一个节点，然后当前节点指向上一个节点，即可以将指针逆向。
        //step 4：再轮换当前指针与上一个指针，让它们进入下一个节点及下一个节点的前序节点。
        while(cur != null){
            //断开链表，要记录后续一个
            ListNode temp = cur.next; 
            //当前的next指向前一个
            cur.next = pre; 
            //前一个更新为当前
            pre = cur; 
            //当前更新为刚刚记录的后一个
            cur = temp; 
        }
        return pre;
    }
}

链表判环

环形链表的环一定在末尾，末尾没有NULL了。基于这一结论：
设定双指针同时遍历，一个走的快，一个走的慢。如果遇到null，无环。快慢指针相遇有环。
同向访问的双指针，速度是快慢的，只要有环，二者就会在环内不断循环，且因为有速度差异，二者一定会相遇。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//判断有没有环，返回相遇的地方
public ListNode hasCycle(ListNode head) {
    //先判断链表为空的情况
    if(head == null)
        return null;
    //快慢双指针
    ListNode fast = head;
    ListNode slow = head;
    //如果没环快指针会先到链表尾
    while(fast != null && fast.next != null){
        //快指针移动两步
        fast = fast.next.next;
        //慢指针移动一步
        slow = slow.next;
        //相遇则有环，返回相遇的位置
        if(fast == slow)
            return slow;
    }
    //到末尾说明没有环，返回null
    return null;
}

那么如何获取到这个环的起始节点呢？
不妨假设快指针在环中走了n圈，慢指针在环中走了m圈，它们才相遇，而进入环之前的距离为x，环入口到相遇点的距离为y，相遇点到环入口的距离为z。相遇时，快指针走了慢指针两倍的路程。可计算得到$x+y=(n-2m)(y+z)$. 从链表头经过环入口到达相遇地方经过的距离等于整数倍环的大小。 那么如果这时候再来一个指针p从头开始以与慢指针相同的速度遍历（即，每一步长为1）。那么p走了x到环起点时，慢指针离再走完一圈少了一个y，即此时慢指针也到了环起点。此时的相遇点即为环起点。

1
2
3
4
5
6
7
8
9
10
public ListNode EntryNodeOfLoop(ListNode pHead) {
    ListNode slow = hasCycle(head);
    if(slow == null) return null;
    ListNode p = head;
    while(fast != slow){
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

K个有序链表合并

两个链表合并的方式很简单。双指针同时遍历即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//两个链表合并函数
public ListNode Merge(ListNode list1, ListNode list2) {
    //一个已经为空了，直接返回另一个
    if(list1 == null)
        return list2;
    if(list2 == null)
        return list1;
    //加一个表头
    ListNode head = new ListNode(0);
    ListNode cur = head;
    //两个链表都要不为空
    while(list1 != null && list2 != null){
        //取较小值的节点
        if(list1.val <= list2.val){
            cur.next = list1;
            //只移动取值的指针
            list1 = list1.next;
        }else{
            cur.next = list2;
            //只移动取值的指针
            list2 = list2.next;
        }
        //指针后移
        cur = cur.next;
    }
    //哪个链表还有剩，直接连在后面
    if(list1 != null)
        cur.next = list1;
    else
        cur.next = list2;
    //返回值去掉表头
    return head.next;
}

但是涉及到多个链表同时合并时，每次选取一条链表加入已合并的部分是比较低效的。提升效率最容易想到的方法是分治法。故：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//划分合并区间函数
ListNode divideMerge(ArrayList<ListNode> lists, int left, int right){
    if(left > right)
        return null;
    //中间一个的情况
    else if(left == right)
        return lists.get(left);
    //从中间分成两段，再将合并好的两段合并
    int mid = (left + right) / 2;
    return Merge(divideMerge(lists, left, mid), divideMerge(lists, mid + 1, right));
}

public ListNode mergeKLists(ArrayList<ListNode> lists) {
    //k个链表归并排序
    return divideMerge(lists, 0, lists.size() - 1);
}

归并的递归过程要注意以下三点：
终止条件： 划分的时候直到左右区间相等或左边大于右边。
返回值： 每级返回已经合并好的子问题链表。
本级任务： 对半划分，将划分后的子问题合并成新的链表。

链表去重

  • step 1：判断链表是否为空链表，空链表不处理直接返回。
  • step 2：使用一个指针遍历链表，如果指针当前节点与下一个节点的值相同，我们就跳过下一个节点，当前节点直接连接下个节点的后一位。
  • step 3：如果当前节点与下一个节点值不同，继续往后遍历。
  • step 4：循环过程中每次用到了两个节点值，要检查连续两个节点是否为空。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    public ListNode deleteDuplicates (ListNode head) {
        // write code here
        if(head == null|| head.next == null) return head;
        ListNode h = new ListNode(-101);
        h.next = head;
        ListNode p = h.next;
        ListNode q = h;
        while(p!=null){
            if(p.val == q.val){
                q.next = p.next;
                p = q.next;
            } else {
                q = p;
                p = p.next;
            }
        } 
        return h.next;
    }

进阶，删除所有有重复的元素

  • step 1：给链表前加上表头，方便可能的话删除第一个节点。
  • step 2：遍历链表，每次比较相邻两个节点，如果遇到了两个相邻节点相同，则新开内循环将这一段所有的相同都遍历过去。
  • step 3：在step 2中这一连串相同的节点前的节点直接连上后续第一个不相同值的节点。
  • step 4：返回时去掉添加的表头。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    public ListNode deleteDuplicates (ListNode head) {
        //空链表
        if(head == null)
            return null;
        ListNode res = new ListNode(0);
        //在链表前加一个表头
        res.next = head;
        ListNode cur = res;
        while(cur.next != null && cur.next.next != null){
            //遇到相邻两个节点值相同
            if(cur.next.val == cur.next.next.val){
                int temp = cur.next.val;
                //将所有相同的都跳过
                while (cur.next != null && cur.next.val == temp)
                    cur.next = cur.next.next;
            }
            else
                cur = cur.next;
        }
        //返回时去掉表头
        return res.next;
    }

二分查找

二分查找的本质是二段性，二分查找的过程本质是对可行区间的压缩。只要满足二段性的问题都可以用二分查找解决。
https://www.cnblogs.com/MAKISE004/p/17093253.html

一维数组二分查找：

闭区间
适用情况： 元素单调的数组（示例代码为升序），左右端点都有可能是所需的点。（单纯的查找）

  • 循环条件
    left<=right; left和right重合时都没找到结束
  • 查找时可能的情况
    • 查找位置指定的元素是目标元素 -> 返回这个位置的索引，结束搜索
    • 查找位置指定的元素不是目标元素
      1.元素值小于目标值：
        往元素值更大的区域收缩（`left=mid+1`）
      2.元素值大于目标值：
        往元素值更小的区域收缩 (`right=mid-1`)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int search (int[] nums, int target) {
    int l = 0;
    int r = nums.length - 1;
    //从数组首尾开始，直到二者相遇
    while(l <= r){
        //每次检查中点的值
        int m = (l + r) / 2;
        if(nums[m] == target)
            return m;
        //进入左的区间
        if(nums[m] > target)
            r = m - 1;
        //进入右区间
        else
            l = m + 1;
    }
    //未找到
    return -1;
}

单开区间
适用情况： 元素单调的数组、数组内单调性分段的（部分增、部分减）
情况一：元素单调，但可能有多个元素符合条件（升序为例）。

  1. 查找等于目标值的第一个位置：左开右闭。
    查找到位置的左边所有元素都满足小于 target，右边所有元素都满足大于等于 target.
    当出现 a[mid] < target 时，说明我们要查找的位置一定在 [mid + 1, right] 范围内，当然也可以写成 (mid, right] ；当出现 a[mid] >= target 时，说明要查找的位置有可能是当前的 mid，也有可能是当前 mid 左边的某个位置，所以此时要查找的位置一定在 [left, mid] 范围内。
    1
    2
    3
    4
    5
    6
    7
    8
    while(left < right){
         int mid = (left + right) /2;
         if(v[mid] < target)
             left = mid + 1;
         else
             right = mid;
     }
     return v[left] == target ? left : -1;
  2. 查找等于目标值的最后位置：左闭右开。
    查找到位置的左边所有元素都满足小于等于 target，右边所有元素都满足大于 target.
    当出现 a[mid] > target 时，说明我们要查找的位置一定在 [left, mid - 1] 范围内，当然也可以写成 [left, mid) ；当出现 a[mid] <= target 时，说明要查找的位置有可能是当前的 mid，也有可能是当前 mid 右边的某个位置，所以此时要查找的位置一定在 [mid, right] 范围内。
    1
    2
    3
    4
    5
    6
    7
    8
    while(left < right){
         int mid = (left + right + 1) /2;
         if(v[mid] > target)
             right = mid - 1;
         else
             left = mid;
     }
     return v[left] == target ? left : -1;

情况二：分段单调，找峰值。（找局部最大值为例）

  1. 找最先出现的峰值：左开右闭
    1
    2
    3
    4
    5
    6
    7
    8
    9
    int left = 0,  right = nums.length - 1;
     while(left < right){
         int mid = (left + right) / 2;
         if(nums[mid] > nums[mid + 1])
             right = mid;
         else
             left = mid + 1;
     }
     return right;
  2. 找最后出现的峰值：左闭右开
    1
    2
    3
    4
    5
    6
    7
    8
    9
    int left = 0,  right = nums.length - 1;
     while(left < right){
         int mid = (left + right + 1) / 2;
         if(nums[mid-1] > nums[mid])
             right = mid-1;
         else
             left = mid;
     }
     return right;

讨论 左闭右开的情况 点下标取值情况
因为整形数据除 2 会自动进行向下取整的问题。
当出现left + 1 == right的情况，那么我们取 mid 时:mid = (left + right) >> 1 = (2 * left + 1) >> 1 = left，很明显left 会一直等于 mid。

二维数组二分查找

适用情况：一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
这样的二维数组的性质：左上与右下必定为最小值与最大值; 左下元素大于它上方的元素，小于它右方的元素，右上元素与之相反。

  • step 1：首先获取矩阵的两个边长，判断特殊情况。
  • step 2：首先以左下角为起点，若是它小于目标元素，则往右移动去找大的，若是他大于目标元素，则往上移动去找小的。
  • step 3：若是移动到了矩阵边界也没找到，说明矩阵中不存在目标值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean Find(int target, int [][] array) {
    //优先判断特殊
    if(array.length == 0) 
        return false;
    int n = array.length;
    if(array[0].length == 0) 
        return false;
    int m = array[0].length;
    //从最左下角的元素开始往左或往上
    for(int i = n - 1, j = 0; i >= 0 && j < m; ){
        //元素较大，往上走
        if(array[i][j] > target)  
            i--;
        //元素较小，往右走
        else if(array[i][j] < target)
            j++;
        else
            return true;
    }
    return false;
}
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2022-2024 Konsin
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信