[数据结构与算法]【乱序版 ● 剑指offer】每日算法题打卡题解—— 字符串和链表（题号5243558）

打卡day3

第一题：剑指 Offer 05. 替换空格

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

示例 1：

输入：s = “We are happy.”
输出：“We%20are%20happy.”

限制：

0 <= s 的长度 <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof

解题思路：
在java中字符串是不可变的类型，所以需要创建一个可变字符串对象StringBuilder。

java代码：

    public String replaceSpace(String s) {
        StringBuilder res = new StringBuilder();//定义一个StringBuilder
        for(Character c : s.toCharArray())//遍历列表中的每个字符c
        {
            if(c == ' ') {//当c为空格时，向res中添加%20
            	res.append("%20");
            }
            else res.append(c);//当c不为空格时，向res中添加c
        }
        return res.toString();//将res转化为字符串后返回
    }

第二题：剑指 Offer 58 - II. 左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

示例 1：

输入: s = “abcdefg”, k = 2 输出: “cdefgab” 示例 2：

输入: s = “lrloseumgh”, k = 6 输出: “umghlrlose”

限制：

1 <= k < s.length <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof

解题思路：
还是基于字符串不可变
直接切片或者新建StringBuilder/String

java代码：

	//方法一：字符串切片
    public String reverseLeftWords(String s, int n) {
    	//分别得到s[n:]的切片和s[:n]的切片，然后使用+进行拼接。
        return s.substring(n, s.length()) + s.substring(0, n);
    }
    
    //方法二：列表遍历拼接（在不允许使用字符串切片时）
    public String reverseLeftWords2(String s, int n) {
        StringBuilder res = new StringBuilder();//新建一个StringBuilder
        //向res添加n+1到最后一位的字符
        for(int i = n; i < s.length(); i++)
            res.append(s.charAt(i));
        //再添加首位到n的字符
        for(int i = 0; i < n; i++)
            res.append(s.charAt(i));
        return res.toString();//转换成字符串输出
    }
    
    //方法三：字符串遍历拼接（规定java只能用String）
    public String reverseLeftWords3(String s, int n) {
    	//思路和方法二相同
        String res = "";
        for(int i = n; i < s.length(); i++)
            res += s.charAt(i);
        for(int i = 0; i < n; i++)
            res += s.charAt(i);
        return res;
    }

第三题：剑指 Offer 24. 反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

限制：

0 <= 节点个数 <= 5000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof

解题思路：
在遍历链表时，将当前节点的 next 指针改为指向前一个节点。因为节点没有引用其前一个节点，所以需要存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

java代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

public class 反转链表 {
	//迭代（双指针）
    public ListNode reverseList(ListNode head) {
    	//初始化pre,cur分别指向null和头节点
        ListNode cur = head, pre = null;
        while(cur != null) {
            ListNode tmp = cur.next; // 暂存后继节点 cur.next
            cur.next = pre;          // 修改 next 引用指向
            pre = cur;               // pre 暂存 cur
            cur = tmp;               // cur 访问下一节点
        }
        return pre;
    }

}

第四题：剑指 Offer 35. 复杂链表的复制

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
（具体图片通过下方连接查看）

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

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

示例 3：
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

示例 4：
输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。

提示：
-10000 <= Node.val <= 10000 Node.random 为空（null）或指向链表中的节点。 节点数目不超过 1000 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof

题目理解：
还以为遍历返回就行，(Ｔ▽Ｔ)
还有一个 random 指针指向链表中的任意节点或者 null

解题思路：
普通链表的节点定义中没有random指针。所以复制普通链表很简单，只需遍历链表，每轮建立新节点 + 构建前驱节点 pre 和当前节点 node 的引用指向即可。

本题链表的节点新增了 random 指针，指向链表中的 任意节点 或者 null 。这个 random 指针意味着在复制过程中，除了构建前驱节点和当前节点的引用指向 pre.next ，还要构建前驱节点和其随机节点的引用指向 pre.random 。

这道题难在，在复制链表的过程中构建新链表各节点的 random 引用指向。

大佬的题解

java代码：

/*
//Definition for a Node.
class Node {
 int val;
 Node next;
 Node random;

 public Node(int val) {
     this.val = val;
     this.next = null;
     this.random = null;
 }
}
*/
public class ReplicationOfComplexLinkedList35 {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Node cur = head;
        Map<Node, Node> map = new HashMap<>();
        // 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
        while(cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        // 4. 构建新链表的 next 和 random 指向
        while(cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        // 5. 返回新链表的头节点
        return map.get(head);
    }


}