仅记录,使用顺序合并,不包括分治和小顶堆(优先队列)

时间224ms,空间 28.8 MB(看脸)

思路简述

  1. 新建链表节点 res 作为答案链表的根节点
  2. 顺序遍历数组,使用 p 指针遍历数组中的每个链表
    • p 指针遍历链表时,向 res 中添加链表元素
  3. 使用前后指针 q1 和 q2 确定添加位置
    • q1 在前 q2 在后,当 q1.val 大于或等于 p.val 时,说明找到了 p 的位置(q1 和 q2 之间),此时将 q2 的下一个节点的 val 设置为 p.val、next 指向 q1 即可入链
    • 入链时需要 new 新的链表元素,直接使用 p 指针会导致重复链/断链

C# 题解

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode MergeKLists(ListNode[] lists) {
        int n = lists.Length;
        if(n == 0) return null;
        ListNode resRoot = new ListNode(val: -10001); //链的根
        for(int i = 0; i < n; i++) { //遍历链数组
            ListNode p = lists[i], q1, q2;
            while(p != null) { //遍历每个链
                q1 = resRoot.next; //前指针
                q2 = resRoot; //后指针
                while(q1 != null) { //寻找位置
                    if(q1.val == p.val || q1.val > p.val) break;
                    q1 = q1.next;
                    q2 = q2.next;
                }
                q2.next = new ListNode(val: p.val, next: q1); // ... -> q2 -> new ListNode(this.val = p.val) -> q1 -> ...
                p = p.next;
            }
        }
        return resRoot.next; //返回根的下一个元素
    }
}

 

实际上是一个找规律的题(以下题解表达得很差,仅适合本人阅读)

解法思想对应官方题解中的行扫描——N 型排列后一行一行地将字符加入数组——但是比官方解法多了一个变量:官方解法中一个一个添加字符,这里是两个两个添加

以 Leetcode 示例为例,设字符串 s 为 PAYPALISHIRING,行数为 numRows(后文简称 n),见下图

首先把 N 型排列写出来,可以发现:排列看似是 N 型,实际上是斜 V 字型的循环(图中的蓝色字符),于是找到循环数,得出循环数公式: nextIndex = (n – 1) * 2

得到循环数,也就得到了图中绿色背景字符的规律:设每行首个字符的下标为 i,绿色背景字符的下标偏移量为 k,则 k = i + nextIndex

对于黄色背景的字符,可以发现:设每行首个字符的下标为 i,黄色背景字符的下标偏移量为 j,则 j = nextIndexi * 2

最终将每行的字符按规律加入数组即可:每行的前两个字符下标分别为 i + ji + k,之后分别累加循环数 nextIndex

C# 题解

public class Solution {
    public string Convert(string s, int numRows) {
        int n = s.Length, nextIndex = 2 * (numRows - 1); //长度和循环数
    if (n == 1 || numRows == 1 || n <= numRows) return s; // 字符串长度小于等于行数时直接返回原串

    StringBuilder sb = new StringBuilder(); // 使用 StringBuilder 防坑

    for (int i = 0, cnt = 0; i < numRows; i++, cnt += 2) { // cnt 累加2,即 i * 2
        sb.Append(s[i]); // 每行第一个字符
        int step = nextIndex - cnt; // 黄色背景字符的下标偏移量
        for (int j = i + step, k = i + nextIndex; j <= n - 1; j += nextIndex, k += nextIndex) {
            if (step != 0 && step != nextIndex) //第一行和最后一行不添加黄色背景字符
                sb.Append(s[j]);
            if(k <= n - 1) // 循环退出条件是黄色背景字符,防止绿色背景字符下标溢出
                sb.Append(s[k]);
        }
    }

    return sb.ToString();
    }
}

Continue reading “Leetcode 6 – Z 字形变换”