31.栈的压入，弹出序列

剑指 Offer 31. 栈的压入、弹出序列 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

太难了，这题连思路都没有。。。只能看大佬的题解了呜呜呜

解法一： 模拟法

这题严格来说不算太难，其实就是模拟一下入栈和出栈的操作

func validateStackSequences(pushed []int, popped []int) bool {
   // 初始化一个栈，模拟
   stack:=list.New()
   // 声明节点表示位置
   i:=0
   // 遍历整个pushed节点
   for _,v:=range pushed{
      // 先把当前节点放入栈中
      stack.PushBack(v)
      // 判断栈顶元素是否和popped的元素相同，相同我们就出栈
      for stack.Len()!=0 && stack.Back().Value.(int) == popped[i] {
         stack.Remove(stack.Back())
         i++
      }
   }
   // 最后如果栈为空，就说明我们遍历完毕了
   return stack.Len() == 0
}

32.I 从上到下打印二叉树

剑指 Offer 32 - I. 从上到下打印二叉树 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

这题居然是中等难度？看不懂，不过我居然做出来了，哈哈哈哈哈哈

解法一 ：BFS

这题其实就是一个广度优先搜索解决的事情。。。。

func levelOrder(root *TreeNode) []int {
   if root == nil {
      return []int{}
   }
   // 我们使用队列来进行操作
   queue:=list.New()
   queue.PushBack(root)
   // 初始化结果数组
   var res []int
   // 当栈为空时，我们停止循环
   for queue.Len() != 0 {
      // 打印当前值并出栈
      node:=queue.Remove(queue.Front()).(*TreeNode)
      res = append(res, node.Val)
      // 判断左右子树是否为空,如果不为空，我们就进栈
      if node.Left != nil {
         queue.PushBack(node.Left)
      }
      if node.Right != nil {
         queue.PushBack(node.Right)
      }
   }
   return res
}

32.II 从上到下打印二叉树II

剑指 Offer 32 - II. 从上到下打印二叉树 II - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

这题其实就和上一题差不多。。。简单思考了一下还是做出来了哈哈，不过我的解法和大佬的比起来还是不够优雅啊。。。

解法一： BFS层次遍历

我的解法比较low，会浪费大量的空间。。。。

func levelOrder(root *TreeNode) [][]int {
   if root == nil {
      return [][]int{}
   }
   // 当前层
   queue:=list.New()
   // 最终结果
    var res [][]int
   queue.PushBack(root)
   for queue.Len()!=0 {
      var data []int
      // 初始化一个新的队列来暂存
      queue2:=list.New()
      // 这里我们把当前队列清空，把当前这一层的数据全部打印出来
      for queue.Len() != 0 {
         // 同时我们获取队列头部元素
         node:=queue.Remove(queue.Front()).(*TreeNode)
         data = append(data, node.Val)
         if node.Left != nil {
            queue2.PushBack(node.Left)
         }
         if node.Right != nil {
            queue2.PushBack(node.Right)
         }
      }
      res= append(res, data)
      // 切换队列
      queue = queue2
   }
   return res
}

这个是大佬的解法，不得不说，大佬的思路就是清奇，大佬没有使用两个队列而是只用一个队列就完成了操作

func levelOrder(root *TreeNode) [][]int {
   if root == nil {
      return [][]int{}
   }
   // 当前层
   queue:=list.New()
   // 最终结果
   var res [][]int
   queue.PushBack(root)
   for queue.Len()!=0 {
      fmt.Println(queue.Len())
      var data []int
      // 这里我们仅临时记录一下当前队列的长度，然后把元素全部放入数组中
      tmp:=queue.Len()
      for i:=0;i<tmp;i++{
         // 同时我们获取队列头部元素
         node:=queue.Remove(queue.Front()).(*TreeNode)
         data = append(data, node.Val)
         if node.Left != nil {
            queue.PushBack(node.Left)
         }
         if node.Right != nil {
            queue.PushBack(node.Right)
         }
      }
      res= append(res, data)
   }
   return res
}

32.III 从上到下打印二叉树III

剑指 Offer 32 - III. 从上到下打印二叉树 III - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

害，又是二叉树，我人都快做傻了，这题没做出来害，我果然还是太菜了。。。

解法一： DFS+双端队列

这里我们可以简单的通过res的长度来判断我们属于那层

// 解法一 层次遍历加双端列队
func levelOrder(root *TreeNode) [][]int {
   if root == nil {
      return [][]int{}
   }
   // 当前层
   queue:=list.New()
   // 最终结果
   var res [][]int
   queue.PushBack(root)
   // 用n来表示遍历的方向
   for queue.Len()!=0 {
      var data []int
      // 这里我们把当前队列清空，把当前这一层的数据全部打印出来
      for i:=queue.Len();i>0;i-- {
         // 同时我们获取队列头部元素
         node:=queue.Remove(queue.Front()).(*TreeNode)
         // 判断是奇数层还是偶数层
         if len(res)%2 == 0 {
            // 如res是偶数，说明当前层是奇数层，此时我们要按照从左到右的顺序进行打印
            data = append(data, node.Val)
         } else {
            // 否则我们就按照从右到左的顺序进行打印
            data = append([]int{node.Val},data...)
         }
         // 添加元素
         if node.Left != nil { queue.PushBack(node.Left) }
         if node.Right != nil { queue.PushBack(node.Right) }
      }
      res= append(res, data)
   }
   return res
}

解法二： DFS+双端队列（奇偶分离）

这个地方有个细节需要注意，就是在遍历奇数层的时候我们是从左到右，然后我们使用栈的方式。

然后在遍历偶数层的时候我们从右到左，同时使用队列的方式来进行遍历

func levelOrder(root *TreeNode) [][]int {
   if root == nil {
      return [][]int{}
   }
   // 当前层
   queue:=list.New()
   // 最终结果
   var res [][]int
   queue.PushBack(root)
   // 用n来表示遍历的方向
   for queue.Len()!=0 {
      // 遍历奇数层
      var data []int
      // 这里我们把当前队列清空，把当前这一层的数据全部打印出来
      for i:=queue.Len();i>0;i-- {
         // 同时我们获取队列头部元素
         node:=queue.Remove(queue.Front()).(*TreeNode)
         // 判断是奇数层还是偶数层
         data = append(data, node.Val)
         // 添加元素
         if node.Left != nil { queue.PushBack(node.Left) }
         if node.Right != nil { queue.PushBack(node.Right) }
      }
      res= append(res, data)
      // 遍历偶数层
      if queue.Len() == 0 {
         break
      }
      data = []int{}
      // 这里我们把当前队列清空，把当前这一层的数据全部打印出来
      for i:=queue.Len();i>0;i-- {
         // 同时我们获取队列头部元素
         node:=queue.Remove(queue.Back()).(*TreeNode)
         // 判断是奇数层还是偶数层
         data = append(data, node.Val)
         // 添加元素
         if node.Right != nil { queue.PushFront(node.Right) }
         if node.Left != nil { queue.PushFront(node.Left) }
      }
      res= append(res, data)
   }
   return res
}

解法三：DFS+倒序

这题我用go实现好像有点问题，因为go好像没有专门的反转数组的包，我这里也懒得重新写一个了，这里直接贴上原大佬的代码吧。

关键部分就在于最后放入数据的时候，会根据当前数据的层数进行反转

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            if(res.size() % 2 == 1) Collections.reverse(tmp);
            res.add(tmp);
        }
        return res;
    }
}

33.二叉搜索树的后序遍历序列

剑指 Offer 33. 二叉搜索树的后序遍历序列 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

这题完全没有思路。。。只能乖乖滚去看大佬的题解了

解法一： 递归分治

二叉搜索树的定义 ：左子树中所有节点的值 << 根节点的值；右子树中所有节点的值 >> 根节点的值；其左、右子树也分别为二叉搜索树。

后序遍历的定义 ：[ 左子树 | 右子树 | 根节点 ] ，即遍历顺序为 “左、右、根” 。

思路很好理解，就是左子树一定比根节点小，右子树一定比根节点大，此时我们分别比较就可以找出左右子树的范围，然后我们再继续检查左右子树。最后如果都符合条件我们即可得出结果

func verifyPostorder(postorder []int) bool {
   // 这里开始进行判断，我们需要传入数组，然后还有起始点和终止点
   return recur(postorder,0, len(postorder)-1)
}
// 辅助函数
func recur(postorder []int,i int,j int) bool {
   // 当i大于或者等于j时，我们就比较完毕了，可以返回true了
   if i >= j { return true }
   // 然后我们记录一下起始点的位置
   p:=i
   // j起始就是根节点，我们的左子树比根节点要小，所以我们这里找出符合条件的所有点
   for postorder[p] < postorder[j] { p++ }
   // m暂存一下，此时m恰好为右子树的第一个节点
   m:=p
   // 这里我们开始下一轮的比较，这里我们找出所有的右子树
   for postorder[p] > postorder[j] { p++ }
   // 当右子树遍历完时，此时p一定会是根节点（如果不是的话，那就不是搜索二叉树）
   // 此时我们还需要分别比较左子树和右子树是否符合条件
   return p==j && recur(postorder,i,m-1) && recur(postorder,m,j-1)
}

解法二：辅助单调栈

这个的话理解起来比较困难，我也解释不明白还是看大佬的解释吧

单调递增栈辅助，逆向遍历数组 - 二叉搜索树的后序遍历序列 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

func verifyPostorder(postorder []int) bool {
   stack:=list.New()
   root:=math.MaxInt32
   // 我们后序遍历的方向的节点是 根、右、左 的顺序
   // 所以一开始越往右越大的
   for i:=len(postorder)-1;i>=0;i--{
      if postorder[i] > root {
         return false
      }
      // 一旦发现我们的节点小于小于栈顶元素时，就说明我们要进入左子树了
      // 接下来，数组继续往前遍历，之后的左子树的每个节点，都要比子树的根要小，才能满足二叉搜索树
      for stack.Len() != 0 && stack.Back().Value.(int) > postorder[i] {
         root = stack.Remove(stack.Back()).(int)
      }
      // 先把值推入栈中
      stack.PushBack(postorder[i])
   }
   return true
}

35.复杂链表的复制

剑指 Offer 35. 复杂链表的复制 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

这题我是真的不会做。。。。然后看了一下题解，简直就是神仙打架。。各种解法都来了，我忍不住说一声，我是傻逼。。。

解法一 ：哈希表

这个解法很巧妙，我们利用hash表的特性，第一个存储节点的值，另外一个就存储新值

func copyRandomList(head *Node) *Node {
   // 当我们的节点为空时返回空
   if head==nil {
      return nil
   }
   // 初始化map来存储数据
   link:=map[*Node]*Node{}
   // 第一遍遍历我们先存储值
   cur:=head
   for cur!= nil{
      link[cur] = &Node{Val: cur.Val}
      cur = cur.Next
   }
   // 第二遍我们就可以开始进行复制了
   cur=head
   for cur!= nil {
      // 这里我们就可以把我们存储的新节点的next和random都进行赋值了
      link[cur].Next = link[cur.Next]
      link[cur].Random = link[cur.Random]
      cur = cur.Next
   }
   // 返回我们复制好的对象
   return link[head]
}

解法二： 拼接+拆分

这个解法主要思想是创建 原节点 1 -> 新节点 1 -> 原节点 2 -> 新节点 2 -> …… 的拼接链表，如此便可在访问原节点的 random 指向节点的同时找到新对应新节点的 random 指向节点。流程如下：

代码是下面这些，我就不多解释了

func copyRandomList(head *Node) *Node {
   if head == nil {
      return nil
   }
   cur := head
   for cur != nil {
      tmp := &Node{Val: cur.Val}
      tmp.Next = cur.Next
      cur.Next = tmp
      cur = tmp.Next
   }
   cur = head
   for cur != nil {
      if cur.Random != nil {
         cur.Next.Random = cur.Random.Next
      }
      cur = cur.Next.Next
   }
   cur = head.Next
   pre := head
   res := head.Next
   for cur.Next != nil {
      pre.Next = pre.Next.Next
      cur.Next = cur.Next.Next
      pre = pre.Next
      cur = cur.Next
   }
   pre.Next = nil
   return res
}

36.二叉搜索树与双向链表（做）

剑指 Offer 36. 二叉搜索树与双向链表 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

为了让您更好地理解问题，以下面的二叉搜索树为例：

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

这题居然不能用GO。。。我大GO莫得排面啊，，，，先贴个java的吧。。

解法一： 中序遍历

class Solution {
    Node pre, head;
    public Node treeToDoublyList(Node root) {
        if(root == null) return null;
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }
    void dfs(Node cur) {
        if(cur == null) return;
        dfs(cur.left);
        if(pre != null) pre.right = cur;
        else head = cur;
        cur.left = pre;
        pre = cur;
        dfs(cur.right);
    }go 
}

37.序列化二叉树（做）

剑指 Offer 37. 序列化二叉树 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

这题又没有go的，我。。。。语言歧视！！！

解法一： 层次遍历

public class Codec {
    public String serialize(TreeNode root) {
        if(root == null) return "[]";
        StringBuilder res = new StringBuilder("[");
        Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(node != null) {
                res.append(node.val + ",");
                queue.add(node.left);
                queue.add(node.right);
            }
            else res.append("null,");
        }
        res.deleteCharAt(res.length() - 1);
        res.append("]");
        return res.toString();
    }

    public TreeNode deserialize(String data) {
        if(data.equals("[]")) return null;
        String[] vals = data.substring(1, data.length() - 1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
        int i = 1;
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(!vals[i].equals("null")) {
                node.left = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(node.left);
            }
            i++;
            if(!vals[i].equals("null")) {
                node.right = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }
}

38.字符串排列

剑指 Offer 38. 字符串的排列 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

这题。。我有思路也符合了一些情况，但是就是有些例子过不去。。。（看了一下大佬的题解是我的思路优点问题）

解法一： DFS加剪枝

我一开始的思路如下

func permutation(s string) []string {
	var data []string
	//visited := make([]bool, len(s))
	dfs(&data, 0, []byte(s))
	return data
}

func dfs(data *[]string,k int,s []byte)  {
	if k == len(s)-1 {
		tmp:=make([]byte,len(s))
		copy(tmp,s)
		*data = append(*data, string(tmp))
		return
	}
	// 开始遍历
	for i := k; i < len(s); i++ {
		if s[i] != s[k] || i==k {
			s[k],s[i] = s[i],s[k]
			dfs(data,k+1,s)
			s[k],s[i] = s[i],s[k]
		}
	}
}

这样的思路虽然可以避免出现和当前字符串重复的情况，但是不能保证其他字符串重复的情况。。。所以最好的方法就是把我们要交换的放到一个map里去，然后在map里面是否存在。

func permutation(s string) []string {
	var data []string
	//visited := make([]bool, len(s))
	dfs(&data, 0, []byte(s))
	return data
}

func dfs(data *[]string,k int,s []byte)  {
	if k == len(s)-1 {
		tmp:=make([]byte,len(s))
		copy(tmp,s)
		*data = append(*data, string(tmp))
		return
	}
	set:=map[byte]bool{}
	// 开始遍历
	for i := k; i < len(s); i++ {
		// 字符串不存在我们才进行交换
		if _, ok := set[s[i]]; !ok {
			set[s[i]] = true
			s[k],s[i] = s[i],s[k]
			dfs(data,k+1,s)
			s[k],s[i] = s[i],s[k]
		}
	}
}

39.数组中出现次数超过一半的数字

剑指 Offer 39. 数组中出现次数超过一半的数字 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

解法一： 暴力法

我们直接使用map来存储每一位出现的次数，然后我们不断遍历找到出现次数最多的那个就是最终答案了

func majorityElement(nums []int) int {
   // 统计每位出现的次数
   count:=make(map[int]int)
   max:=0
   // 找出出现次数最多的
   for _,v:=range nums{
      count[v] ++
      if count[v] > count[max] {
         max = v
      }
   }
   return max
}

解法二： 排序

这个没想到哈哈，原理其实也很简单，我们对数组进行排序，出现了一半的数肯定会在中间

// 解法二 排序
func majorityElement(nums []int) int {
   // 先排序
   sort.Ints(nums)
   return nums[(0+len(nums))/2]
}

解法三： 位运算

这个用go没有调出来。。。所以先暂时跳过吧，这里就贴一下大佬的题解

public int majorityElement(int[] nums) {
    int major = 0;
    int length = nums.length;
    //在java中int类型是32位，我们遍历每一位
    for (int i = 0, mask = 1; i < 32; i++, mask <<= 1) {
        //bitCounts表示所有数字在当前位置1的个数。比如当i=0
        //的时候，我们可以认为他表示的是所有数字在二进制位
        //中最右边1的总数。
        int bitCounts = 0;
        for (int j = 0; j < length; j++) {
            //判断数字nums[j]的第i（i从0开始）个位置是否为1，
            //如果是1，bitCounts就加1
            if ((nums[j] & mask) == 1)
                bitCounts++;
            //如果bitCounts大于数组的一半，那么这个众数在
            //这个位置肯定是1，然后通过 major |= mask运算
            //把这个位置变为1，后面不需要再判断了，直接终止
            //内层循环
            if (bitCounts > length / 2) {
                major |= mask;
                break;
            }
        }
    }
    return major;
}

解法四： 摩尔投票法

不得不说，这个算法还是很巧妙的。

假设数组中每个不同的数字就代表一个国家，而数字的个数就代表这个国家的人数，他们在一起混战，就是每两个两个同归于尽。我们就可以知道那个人数大于数组长度一半的肯定会获胜。

就算退一万步来说，其他的所有人都来攻击这个人数最多的国家，他们每两个两个同归于尽，最终剩下的也是那个众数。

func majorityElement(nums []int) int {
   // 一开始我们让这个人表示第一个国家
   major:=nums[0]
   // 国家人数设置为1
   count:=1
   // 下面我们开始相互对抗
   for i := 1; i < len(nums); i++ {
      // 如果国家人数为0，那么我们就选一个新的国家
      if count == 0 {
         major = nums[i]
         count++
      } else if nums[i] == major {
         // 如果数字相同，那么国家人数+1
         count++
      } else {
         // 否则的话，我们国家人数就要派一个人同归于尽，人数少一
         count--
      }
   }
   // 最后还剩下的国家就是大于一半的情况了
   return major
}

40.最小K个数

剑指 Offer 40. 最小的k个数 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

解法一：使用自带的排序包

func getLeastNumbers(arr []int, k int) []int {
   sort.Ints(arr)
   var res []int
   for i := 0; i < k; i++ {
      res = append(res, arr[i])
   }
   return res
}

解法二：快排

这个就不说了，这题目本质上就是排序