早起刷题（Day 18）

LeetCode426. 将二叉搜索树转化为排序的双向链表

#DFS #二叉树 #链表

题目描述

将一个 二叉搜索树 就地转化为一个 已排序的双向循环链表 。
对于双向循环列表，你可以将左右孩子指针作为双向循环链表的前驱和后继指针，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
特别地，我们希望可以 就地 完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中最小元素的指针。

示例 1:

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

解释：下图显示了转化后的二叉搜索树，实线表示后继关系，虚线表示前驱关系。

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

示例 3：
输入：root = []
输出：[]
解释：输入是空树，所以输出也是空链表。

示例 4：
输入：root = [1]
输出：[1]
 

提示：
-1000 <= Node.val <= 1000
Node.left.val < Node.val < Node.right.val
Node.val 的所有值都是独一无二的
0 <= Number of Nodes <= 2000

解题思路

(1). 题目要求要原地修改，那么就要注意在原地修改的时候，节点的左右节点会被破坏，所以要用变量来提前保存；
(2). 根据二叉搜索树的性质，其中序遍历的结果就是升序的排列，所以要通过中序遍历来遍历所有节点；
(3). 中序遍历过程中会首先访问到所有节点的左子树，所以修改节点的左右字节点不会影响左子树的遍历，所以只需要保存右节点即可；
(4). 在构造双端链表的过程中，还需要构造一个变量来实时保存当前节点的前序节点，并且在中序遍历过程中无法感知当前节点是否是最后一个节点，所以在构造双端链表的过程中，要把所有节点都假设成最后一个节点，使其后继节点指向头节点，把头节点的前序节点指向当前节点。

解题代码

/**

* Definition for a Node.
* type Node struct {
* 	Val int
* 	Left *Node
* 	Right *Node
* }
*/

func treeToDoublyList(root *Node) *Node {

	if root == nil {
		return root
	} else if root.Left == nil && root.Right == nil {
		root.Left = root
		root.Right = root
		return root
	}

	head := &Node{Val:1001}
	var pre, right *Node

	var backTracking func(*Node)
	backTracking = func (p *Node) {
		if p == nil {
			return
		}

		backTracking(p.Left)
		if head.Val == 1001 {
			head = p
			pre = p
			right = p.Right
		} else if head.Val == p.Val {
			return
		} else {
			pre.Right = p
			p.Left = pre
			right = p.Right
			p.Right = head
			head.Left = p
			pre = p
		}

		backTracking(right)

	}

	backTracking(root)

	return head
}

LeetCode443. 压缩字符串

#双指针

题目描述

给你一个字符数组 chars ，请使用下述算法压缩：
从一个空字符串 s 开始。对于 chars 中的每组 连续重复字符 ：
如果这一组长度为 1 ，则将字符追加到 s 中。
否则，需要向 s 追加字符，后跟这一组的长度。
压缩后得到的字符串 s 不应该直接返回 ，需要转储到字符数组 chars 中。需要注意的是，如果组长度为 10 或 10 以上，则在 chars 数组中会被拆分为多个字符。
请在 修改完输入数组后 ，返回该数组的新长度。
你必须设计并实现一个只使用常量额外空间的算法来解决此问题。

示例 1：
输入：chars = ["a","a","b","b","c","c","c"]
输出：返回 6 ，输入数组的前 6 个字符应该是：["a","2","b","2","c","3"]
解释："aa" 被 "a2" 替代。"bb" 被 "b2" 替代。"ccc" 被 "c3" 替代。

示例 2：
输入：chars = ["a"]
输出：返回 1 ，输入数组的前 1 个字符应该是：["a"]
解释：唯一的组是“a”，它保持未压缩，因为它是一个字符。

示例 3：
输入：chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
输出：返回 4 ，输入数组的前 4 个字符应该是：["a","b","1","2"]。
解释：由于字符 "a" 不重复，所以不会被压缩。"bbbbbbbbbbbb" 被 “b12” 替代。
 

提示：
1 <= chars.length <= 2000
chars[i] 可以是小写英文字母、大写英文字母、数字或符号

解题思路

(1). 为了实现原地压缩，我们可以使用双指针分别标志我们在字符串中读和写的位置。每次当读指针 end 移动到某一段连续相同子串的最右侧，我们就在写指针 start 处依次写入该子串对应的字符和子串长度即可；
(2). 当当前读的自符不同于之前的字符时，此时需要根据 start 记录的位置来对 start 到 end 之间的字符进行删补；
(3). 要注意读到字符串最后一个字符时的边界处理。

时间复杂度

O(N)

解题代码

func compress(chars []byte) int {

    if len(chars) == 1 {
        return 1
    }

    count := 1
    start := 0
    c := chars[0]

    ret := 0
    for i:=1; i<len(chars); i++ {
        if chars[i] == c && i != len(chars)-1 {
            count++
            continue
        } else {
            var end int
            if i == len(chars)-1 && chars[i] == c {
                count++
                end = i+1
            } else if i == len(chars)-1{
                ret++
                end = i
            } else {
                end = i
            }
			
            var b []byte
            if count <= 2 {
                ret += count
                if count == 2 {
                    if i == len(chars)-1 && chars[i] == c {
                        chars[i] = '2'
                    } else {
                        chars[i-1] = '2'
                    }   
                }
            } else {
                t := count
                chars = append(chars[:start+1], chars[end:]...)
                for t > 0 {
                    b = append([]byte{byte(t%10+'0')}, b...)
                    t /= 10
                    ret++
                }

                chars = append(chars[:start+1], append(b, chars[start+1:]...)...)
                ret++
                i = len(b)+start+1
            }

            if i < len(chars) {
                c = chars[i]
            }
            count = 1
            start = i
        }
    }

    return ret
}