每日一题

题目

1694. 重新格式化电话号码 难度：easy

给你一个字符串形式的电话号码 number。number 由数字、空格 ' '、和破折号 '-' 组成。

请你按下述方式重新格式化电话号码。

• 首先，删除 所有的空格和破折号。

• 其次，将数组从左到右 每 3 个一组 分块，直到 剩下 4 个或更少数字。剩下的数字将按下述规定再分块：

  • 2 个数字：单个含 2 个数字的块。
  • 3 个数字：单个含 3 个数字的块。
  • 4 个数字：两个分别含 2 个数字的块。

最后用破折号将这些块连接起来。注意，重新格式化过程中 不应该 生成仅含 1 个数字的块，并且 最多 生成两个含 2 个数字的块。

返回格式化后的电话号码。

示例 1：

输入：number = "1-23-45 6"
输出："123-456"
解释：数字是 "123456"
步骤 1：共有超过 4 个数字，所以先取 3 个数字分为一组。第 1 个块是 "123" 。
步骤 2：剩下 3 个数字，将它们放入单个含 3 个数字的块。第 2 个块是 "456" 。
连接这些块后得到 "123-456" 。

示例 2：

输入：number = "123 4-567"
输出："123-45-67"
解释：数字是 "1234567".
步骤 1：共有超过 4 个数字，所以先取 3 个数字分为一组。第 1 个块是 "123" 。
步骤 2：剩下 4 个数字，所以将它们分成两个含 2 个数字的块。这 2 块分别是 "45" 和 "67" 。
连接这些块后得到 "123-45-67" 。

示例 3：

输入：number = "123 4-5678"
输出："123-456-78"
解释：数字是 "12345678" 。
步骤 1：第 1 个块 "123" 。
步骤 2：第 2 个块 "456" 。
步骤 3：剩下 2 个数字，将它们放入单个含 2 个数字的块。第 3 个块是 "78" 。
连接这些块后得到 "123-456-78" 。

示例 4：

输入：number = "12"
输出："12"

示例 5：

输入：number = "--17-5 229 35-39475 "
输出："175-229-353-94-75"

提示：

• 2 <= number.length <= 100
• number 由数字和字符 '-' 及 ' ' 组成。
• number 中至少含 2 个数字。

方法一：模拟

思路

根据题意，我们需要把给定字符串中的数字全部提取出来，然后再重新进行分块；

因此在遍历的过程中，我们可以存储剩余的数字数量 n 以及当前遍历到的字符位置 pt；

并且对于最后剩余的数字，也要按照一定的要求格式化：

• 当 n > 4 时，我们取出三个连续的字符，作为一个块；
• 当 n $\leq$ 4 时，我们根据题目的要求，将剩余的 n 个字符进行分块，并结束遍历。

所以通过模拟这个过程即可；
 

解题

Python：

class Solution:
    def reformatNumber(self, number: str) -> str:
        digits = list()
        for ch in number:
            if ch.isdigit():
                digits.append(ch)
        
        n, pt = len(digits), 0
        ans = list()

        while n > 0:
            if n > 4:
                ans.append("".join(digits[pt:pt+3]))
                pt += 3
                n -= 3
            else:
                if n == 4:
                    ans.append("".join(digits[pt:pt+2]))
                    ans.append("".join(digits[pt+2:pt+4]))
                else:
                    ans.append("".join(digits[pt:pt+n]))
                break
        
        return "-".join(ans)

Java：

class Solution {
    public String reformatNumber(String number) {
        StringBuilder digits = new StringBuilder();
        for (char ch : number.toCharArray()) {
            if (Character.isDigit(ch)) {
                digits.append(ch);
            }
        }
        
        int n = digits.length();
        int pt = 0;
        StringBuilder ans = new StringBuilder();
        while (n > 0) {
            if (n > 4) {
                ans.append(digits.substring(pt, pt + 3) + "-");
                pt += 3;
                n -= 3;
            } else {
                if (n == 4) {
                    ans.append(digits.substring(pt, pt + 2) + "-" + digits.substring(pt + 2, pt + 4));
                } else {
                    ans.append(digits.substring(pt, pt + n));
                }
                break;
            }
        }
        return ans.toString();
    }
}

21. 合并两个有序链表

题目

21. 合并两个有序链表 难度：easy

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

• 两个链表的节点数目范围是 [0, 50]
• -100 <= Node.val <= 100
• l1 和 l2 均按 非递减顺序 排列

方法一：递归

思路

根据题意，给出了两个链表，需要将这俩链表合成一个按升序排列的链表，那么可以递归地定义两个链表里的 merge 操作：

也就是说，两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并。

如果 l1 或者 l2 一开始就是空链表 ，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空，递归结束。

解题

Python：

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 is None:
            return l2
        elif l2 is None:
            return l1
        elif l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

Java：

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

方法二：迭代

思路

我们也可以用迭代的方法来实现上述算法。当 l1 和 l2 都不是空链表时，判断 l1 和 l2 哪一个链表的头节点的值更小，将较小值的节点添加到结果里，当一个节点被添加到结果里之后，将对应链表中的节点向后移一位。

解题

Python：

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        prehead = ListNode(-1)

        prev = prehead
        while l1 and l2:
            if l1.val <= l2.val:
                prev.next = l1
                l1 = l1.next
            else:
                prev.next = l2
                l2 = l2.next            
            prev = prev.next

        # 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 if l1 is not None else l2

        return prehead.next

Java：

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }
}

206. 反转链表

题目

206. 反转链表 难度：easy

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入： head = [1,2,3,4,5]
输出： [5,4,3,2,1]

示例 2：

输入： head = [1,2]
输出： [2,1]

示例 3：

输入： head = []
输出： []

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

方法一：栈

思路

看到反转的问题，最简单的就是通过开辟额外的空间来降低难度，这里我们可以使用栈，先顺序遍历将链表的节点都压入栈，然后再将他们一一弹出，形成链表，这样就成功反转链表了，伪代码如下：

for ..:
    stack.push(node)
    
for ..:
    reverse.next = stack.pop()

解题

Python：

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        stack = list()
        orign = head
        while orign:
            stack.append(orign)
            orign = orign.next
        reverse = ListNode()
        dummy = reverse
        while stack:
            node= stack.pop()
            node.next = None
            dummy.next = node
            dummy = dummy.next
        return reverse.next

Java：

public ListNode reverseList(ListNode head) {
    Stack<ListNode> stack = new Stack<>();
    // 把链表节点全部摘掉放到栈中
    while (head != null) {
        stack.push(head);
        head = head.next;
    }
    if (stack.isEmpty())
        return null;
    ListNode node = stack.pop();
    ListNode dummy = node;
    // 栈中的结点全部出栈，然后重新连成一个新的链表
    while (!stack.isEmpty()) {
        ListNode tempNode = stack.pop();
        node.next = tempNode;
        node = node.next;
    }
    // 最后一个结点就是反转前的头结点，一定要让他的 next
    // 等于空，否则会构成环
    node.next = null;
    return dummy;
}

方法二：迭代

思路

上述栈的思路是需要开辟额外空间的，那我们能够不开辟额外的空间实现吗，即原地反转；

在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

解题

Python：

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        cur = head   
        pre = None
        while(cur!=None):
            temp = cur
            cur.next = pre
            pre = cur
            cur = temp
        

Java：

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

方法三：递归

思路

递归法相对抽象一些，但是其实和迭代法是一样的逻辑，同样是当 cur 为空的时候循环结束，不断将 cur 指向 pre 的过程。

关键是初始化的地方，可能有的同学会不理解， 可以看到双指针法中初始化 cur = head，pre = null，在递归法中初始化的逻辑是一样的，只不过写法变了。

解题

Python：

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        def reverse(pre,cur):
            if not cur:
                return pre       
            tmp = cur.next
            cur.next = pre
            return reverse(cur,tmp)
        return reverse(None,head)

Java：

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

后记

📝 上篇精讲： 【算法题解】 Day2 字符串
💖 我是  𝓼𝓲𝓭𝓲𝓸𝓽，期待你的关注；
👍 创作不易，请多多支持；
🔥 系列专栏： 算法题解