《剑指 Offer I》刷题笔记 1 ~ 19 题

剑指 Offer I 刷题笔记 1

栈与队列（简单）

1. 用两个栈实现队列

_解法 1：暴力做法解法 2：优化解法 1 2. 包含 min 函数的栈

_解法 1：pop() 复杂度 O(n)解法 2：链表链表（简单）

3. 从尾到头打印链表

_解法 1：常规遍历解法 2：优化解法 1 的空间解法 3：递归解法 4：辅助栈 4. 反转链表（递归）

_解法 1：辅助栈 + 迭代解法 2：双指针解法 3：递归 * 5. 复杂链表的复制

_解法 1：暴力迭代解法 2：哈希解法 3：拼接 + 拆分字符串（简单）

6. 替换空格

_解法 1：迭代解法 2 ：数组解法 3：原地修改 7. 左旋转字符串

_解法 1：迭代_解法 2：缩小迭代范围解法 3：字符串切片查找算法（简单）

8. 数组中重复的数字

_解法 1：迭代 + map_解法 2：迭代 + 数组解法 3：迭代 + set解法 4：原地交换 9. 在排序数组中查找数字 I

_解法 1：迭代_解法 2：二分法 10. 0～n-1中缺失的数字（二分）

_解法 1：迭代解法 2：二分查找算法（中等）

11. 二维数组中的查找

_解法 1：暴力迭代解法 2：标志数解法 3：逐行二分 12. 旋转数组的最小数字

_解法 1：暴力迭代解法 2：二分 13. 第一个只出现一次的字符

_解法 1：暴力迭代_解法 2：哈希解法 3：有序哈希表搜索与回溯算法（简单）

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

解法 1：队列 15. 从上到下打印二叉树 II

解法 1：队列解法 2：递归 16. 从上到下打印二叉树 III

_解法 1：双栈解法 2：双端队列解法 3：层序遍历 + 倒序Go 语言切片 17. 树的子结构

解法 1：双重递归 DFS解法 2：双重 BFS（很慢） 18.二叉树的镜像

_解法 1：递归 DFS解法 2：辅助栈 19. 对称的二叉树

_解法 1：暴力解法 2：递归

代码：https://gitee.com/szluyu99/my-leet-code

小标题以 _ 开头的题目和解法代表独立想到思路及编码完成，其他是对题解的学习。

VsCode 搭建的 Java 环境中 sourcePath 配置比较麻烦，可以用 java main.java 运行（JDK 11 以后）

LeetCode 支持 https://godoc.org/github.com/emirpasic/gods 第三方库。
go get github.com/emirpasic/gods

栈与队列（简单） 1. 用两个栈实现队列

题目：剑指 Offer 09. 用两个栈实现队列

_解法 1：暴力做法

思路：

每次入栈就入 A 栈出栈就将 A 全部丢到 B 再出，结束后将数据放回 A 栈

Java：

class CQueue {
    Stack stack1;
    Stack stack2;

    public CQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    public void appendTail(int value) {
        stack1.push(value);
    }
    
    public int deleteHead() {
       while(!stack1.isEmpty()) {
           stack2.push(stack1.pop());
       }
       Integer result = -1;
       if (!stack2.isEmpty()) {
           result = stack2.pop();
       }
       while(!stack2.isEmpty()) {
           stack1.push(stack2.pop());
       }
       return result;
    }

}

解法 2：优化解法 1

参考：清晰图解

思路：

优化掉解法 1 中出栈思路，无需每次出完就将数据放回 A 栈

Java：

class CQueue {
    Stack inStack, outStack;

    public CQueue() {
        inStack = new Stack<>();
        outStack = new Stack<>();
    }
    
    public void appendTail(int value) {
        inStack.push(value);
    }
    
    public int deleteHead() {
        if (!outStack.isEmpty())
            return outStack.pop();
        if (inStack.isEmpty())
            return -1;
        while (!inStack.isEmpty())
            outStack.push(inStack.pop());
        return outStack.pop();
    }
}

Go：

Go 里面没有栈这个数据结构，做这种题目有点麻烦… 以后数据结构题目还是用 Java 吧

type CQueue struct {
	inStack, outStack *list.List
}

func Constructor() CQueue {
	return CQueue{
		inStack:  list.New(),
		outStack: list.New(),
	}
}

func (this *CQueue) AppendTail(value int) {
	this.inStack.PushBack(value)
}

func (this *CQueue) DeleteHead() int {
	if this.outStack.Len() != 0 {
		e := this.outStack.Back()
		this.outStack.Remove(e)
		return e.Value.(int)
	}
	if this.inStack.Len() == 0 {
		return -1
	}
	for this.inStack.Len() > 0 {
		this.outStack.PushBack(this.inStack.Remove(this.inStack.Back()))
	}
	e := this.outStack.Back()
	this.outStack.Remove(e)
	return e.Value.(int)
}

2. 包含 min 函数的栈

题目：剑指 Offer 30. 包含min函数的栈

_解法 1：pop() 复杂度 O(n)

Java：

class MinStack {
    int[] vals;
    int min = Integer.MAX_VALUE;
    int index = 0;

    public MinStack() {
        vals = new int[20000];
    }
    
    public void push(int x) {
        if (x < min) {
            min = x;
        }
        vals[index++] = x;
    }
    
    public void pop() {
        int val = vals[--index];
        if (val == min) {
            min = Integer.MAX_VALUE;
            for (int i = 0; i < index; i++) {
                if (vals[i] < min) {
                    min = vals[i];
                }
            }
        }
    }
    
    public int top() {
        return vals[index - 1];
    }
    
    public int min() {
        return min;
    }

}

解法 2：链表

class MinStack {
    private Node head;

    public MinStack() {}
    
    public void push(int x) {
        if (head == null) 
            head = new Node(x, x, null);
        else 
            head = new Node(x, Math.min(head.min, x), head);
    }
    
    public void pop() {
        head = head.next;
    }
    
    public int top() {
        return head.val;
    }
    
    public int min() {
        return head.min;
    }

    class Node {
        int val;
        int min;
        Node next;

        public Node(int val, int min, Node next) {
            this.val = val;
            this.min  = min;
            this.next = next;
        }
    }
}

链表（简单） 3. 从尾到头打印链表

题目：剑指 Offer 06. 从尾到头打印链表

_解法 1：常规遍历

思路：

创建一个容量足够大的数组，遍历链表将值存到数组中再将该数组中的值倒序存到另一个数组，即为结果

// java
public int[] reversePrint(ListNode head) {
  int[] vals = new int[10001];
  int len = 0;
  while (head != null) {
    vals[len++] = head.val;
    head = head.next;
  }
  int[] res = new int[len];
  int j = 0;
  for (int k = len - 1; k >= 0; k--) {
    res[j++] = vals[k];
  }
  return res;
}

// go
func reversePrint(head *ListNode) []int {
	vals := make([]int, 0)
	for head != nil {
		vals = append(vals, head.Val)
		head = head.Next
	}
	res := make([]int, 0)
	for i := len(vals) - 1; i >= 0; i-- {
		res = append(res, vals[i])
	}
	return res
}

解法 2：优化解法 1 的空间

思路：

解法 1 中创建了一个数组来存储第一次遍历链表的值，不需要这么做直接复制一份链表，则不用开辟很大的数组，尽量减少空间

// java
public int[] reversePrint(ListNode head) {
  ListNode node = head;
  int len = 0;
  while (node != null) {
    len++;
    node = node.next;
  }
  int[] nums = new int[len];
  node = head;
  for (int i = len - 1; i >=0; i--) {
    nums[i] = node.val;
    node = node.next;
  }
  return nums;
}

Go：类似的优化，第一次遍历不需要进行赋值操作，只需要获取到数组长度，即可在第二次循环倒序赋值。

// go
func reversePrint(head *ListNode) []int {
	cn := 0
	for p := head; p != nil; p = p.Next {
		cn++
	}
	node := make([]int, cn)
	for head != nil {
		node[cn-1] = head.Val
		head = head.Next
		cn--
	}
	return node
}

解法 3：递归

参考题解：面试题06. 从尾到头打印链表（递归法、辅助栈法，清晰图解）

Java：

class Solution {
    ArrayList tmp = new ArrayList<>();

    public int[] reversePrint(ListNode head) {
        recur(head);
        int[] res = new int[tmp.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = tmp.get(i);
        }
        return res;
    }

    void recur(ListNode head) {
        if (head == null) return;
        recur(head.next);
        tmp.add(head.val);
    }
}

Go：像 Go 这种可以往切片后面直接添加元素的语言，递归实现起来更简洁

func reversePrint3(head *ListNode) []int {
	if head == nil {
		return nil
	}
	return append(reversePrint(head.Next), head.Val)
}

解法 4：辅助栈

参考题解：面试题06. 从尾到头打印链表（递归法、辅助栈法，清晰图解）

链表是从前往后访问每个节点，而题目要求倒序输出，这种先入后出的需求可以借助栈

// java
public int[] reversePrint3(ListNode head) {
  Stack stack = new Stack<>();
  while (head != null) {
    stack.push(head.val);
    head = head.next;
  }
  int[] res = new int[stack.size()];
  for (int i = 0; i < res.length; i++) 
    res[i] = stack.pop();
  return res;
}

4. 反转链表（递归）

题目：剑指 Offer 24. 反转链表

_解法 1：辅助栈 + 迭代

思路：

遍历链表，将值添加到栈中再遍历该栈并出栈，将出栈的值组成新的链表

// java
public ListNode reverseList(ListNode head) {
  if (head == null) return null;

  Stack stack = new Stack<>();
  while(head != null) {
    stack.push(head.val);
    head = head.next;
  }

  ListNode node = new ListNode(stack.pop());
  ListNode res = node;
  while (!stack.isEmpty()) {
    node.next = new ListNode(stack.pop());
    node = node.next;
  }
  return res;
}

解法 2：双指针

参考题解：剑指 Offer 24. 反转链表（迭代 / 递归，清晰图解）

// java
public ListNode reverseList2(ListNode head) {
  ListNode cur = head, pre = null;
  while (cur != null) {
    ListNode tmp = cur.next;
    cur.next = pre;
    pre = cur;
    cur = tmp;
  }
  return pre;
}

解法 3：递归 *

递归 1：

// java
public ListNode reverseList(ListNode head) {
  if (head == null) return null; // 空节点返回后还是空节点
  if (head.next == null) return head; // 一个节点反转后还是这个节点
  ListNode newNode = reverseList(head.next); // 递归后继节点
  head.next.next = head;
  head.next = null;
  return newNode;
}

递归 2：剑指 Offer 24. 反转链表（迭代 / 递归，清晰图解）

// java
public ListNode reverseList(ListNode head) {
  return recur(head, null);
}
public ListNode recur(ListNode cur, ListNode pre) {
  if (cur == null) return pre;
  ListNode node = recur(cur.next, cur); // 递归后继节点
  cur.next = pre; // 修改节点引用指向
  return node;
}

5. 复杂链表的复制

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

本题链表节点定义：

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

_解法 1：暴力迭代

思路：

先复制出一个链表副本（处理好 next，random 有 null 指 null，不做其他处理）再次迭代，去处理 random 的指向

// java
public Node copyRandomList(Node head) {
  if (head == null) return null;
  Node newNode = new Node(head.val);
  // 保存两个链表的首指针
  Node pHead = head, pNew = newNode; 
  while (pHead != null) {
    pNew.next = pHead.next == null ? null : new Node(pHead.next.val);
    if (pHead.random == null)
      pNew.random = null;
    pNew = pNew.next;
    pHead = pHead.next; 
  }
  // 恢复指针状态
  pHead = head;
  pNew = newNode; 

  while (pHead != null) {
    // 寻找random节点
    Node tmpNode = head, ptmpNode = newNode;
    while (pHead.random != tmpNode) {
      tmpNode = tmpNode.next;
      ptmpNode = ptmpNode.next; 
    }
    pNew.random = ptmpNode;

    pNew = pNew.next;
    pHead = pHead.next;
  }
  return newNode;
}

解法 2：哈希

思路：

在解法 1 的基础上，优化寻找 random 节点的过程（使用 HashMap 存放）

题解：剑指 Offer 35. 复杂链表的复制（哈希表 / 拼接与拆分，清晰图解）

学习的人家更优雅的写法：

// java
public Node copyRandomList2(Node head) {
  if (head == null) return null;
  Map map = new HashMap<>();
  Node cur = head;
  // 复制各节点，并建立 "原节点 -> 新节点" 的映射
  while (cur != null) {
    map.put(cur, new Node(cur.val));
    cur = cur.next;
  }
  cur = head;
  // 构建新的next和random指向
  while (cur != null) {
    map.get(cur).next = map.get(cur.next);
    map.get(cur).random = map.get(cur.random);
    cur = cur.next;
  }
  return map.get(head);
}

解法 3：拼接 + 拆分

题解：剑指 Offer 35. 复杂链表的复制（哈希表 / 拼接与拆分，清晰图解）

注：如果能想到这个思路，实际上编写代码的难点在于 “拆分两链表”。

// java
public Node copyRandomList3(Node head) {
  if (head == null) return null;
  Node cur = head;
  // 1. 复制各节点，并构建拼接链表
  while (cur != null) {
    Node node = new Node(cur.val);
    node.next = cur.next;
    cur.next = node;
    cur = cur.next.next;
  }
  // 2. 构建各新节点的 random 指向
  cur = head;
  while (cur != null) {
    if (cur.random != null)
      cur.next.random = cur.random.next; 
    // cur.next.random = cur.random == null ? null : cur.random.next;
    cur = cur.next.next;
  }
  // 3，拆分两链表
  cur = head.next;
  Node pre = head, res = head.next;
  while (cur.next != null) {
    pre.next = pre.next.next;
    cur.next = cur.next.next;             
    pre = pre.next;
    cur = cur.next;
  }
  pre.next = null; // 单独处理原链表尾节点
  return res;
}

字符串（简单） 6. 替换空格

题目：剑指 Offer 05. 替换空格

该题第一反应：调库

func replaceSpace_(s string) string {	
  return strings.ReplaceAll(s, " ", "%20")
}

_解法 1：迭代

// java
public String replaceSpace(String s) {
  StringBuilder sb = new StringBuilder();
  for (char c : s.toCharArray()) {
    if (c == ' ') sb.append("%20");
    else sb.append(c);
  }
  return sb.toString();
}

循环中也可以这么写：

for (int i = 0; i < s.length(); i++) {  
  if (s.charAt(i) == ' ') sb.append("%20");  
  else sb.append(s.charAt(i));
}

解法 2 ：数组

参考：这道题目真的有这么简单吗？请看题解吧

代码 1：会浪费空间

class Solution {    
  public String replaceSpace(String s) {        
    int n = s.length();        
    char[] newArr = new char[3 * n]; // 最坏情况，全是空格        
    int j = 0;        
    for (int i = 0; i < n; i++) {            
      char c = s.charAt(i);            
      if (c == ' ') {                
        newArr[j++] = '%';                
        newArr[j++] = '2';                
        newArr[j++] = '0';            
      } else {                
        newArr[j++] = c;            
      }        
    }                      
    return new String(newArr, 0, j);    
  }
}

代码 2：不浪费空间，有些许性能损耗

就是提前计算一下需要初始化数组的大小

int n = s.length();
int cnt = 0;
for (char c: s.toCharArray()) {  
  if (c == ' ') cnt++;
}
char[] newArr = new char[n + 2 * cnt]; // 不浪费空间// 后面一样

解法 3：原地修改

参考：面试题05. 替换空格（字符串修改，清晰图解）

C++ 中字符串是可变的，因此可以实现空间复杂度为 O(1) 的解法。

7. 左旋转字符串

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

_解法 1：迭代

思路：遍历字符串，将 k 之前和之后的内容分别拼接出新字符串，遍历结束返回拼接的字符串

// go
func reverseLeftWords(s string, n int) string {
	var pre, suffix string
	for i, v := range s {
		if i < n {
			suffix += string(v) // 前缀
		} else {
			pre += string(v) // 后缀
		}
	}
	return pre + suffix
}

_解法 2：缩小迭代范围

思路：只迭代传入的 n 这个范围，将拿到的数据往字符串后面放即可

// go
func reverseLeftWords2(s string, n int) string {
	res := []byte(s)
	for i := 0; i < n; i++ {
		res = append(res, s[i])
	}
	return string(res[n:])
}

解法 3：字符串切片

题解：面试题58 - II. 左旋转字符串（切片 / 列表 / 字符串，清晰图解）

// go
func reverseLeftWords3(s string, n int) string {
	return s[n:] + s[:n]
}

// Java
public String reverseLeftWords(String s, int n) {  
  return s.substring(n) + s.substring(0, n);
}

查找算法（简单） 8. 数组中重复的数字

题目：数组中重复的数字

_解法 1：迭代 + map

// go
func findRepeatNumber(nums []int) int {
	m := make(map[int]int)
	for i := 0; i < len(nums); i++ {
		if val, ok := m[nums[i]]; ok {
			return val
		}
		m[nums[i]] = nums[i]
	}
	return 0
}

// java
public int findRepeatNumber(int[] nums) {
  Map map = new HashMap<>();
  for (int i = 0; i < nums.length; i++) {
    if (map.containsKey(nums[i])) {
      return nums[i];
    }
    map.put(nums[i], nums[i]);
  }
  return 0;
}

_解法 2：迭代 + 数组

// go
func findRepeatNumber2(nums []int) int {
	records := make([]int, len(nums))
	for i := 0; i < len(nums); i++ {
		records[nums[i]]++
		if records[nums[i]] > 1 {
			return nums[i]
		}
	}
	return 0
}

// java
public int findRepeatNumber2(int[] nums) {
  int[] records = new int[nums.length];
  for (int i = 0; i < nums.length; i++) {
    records[nums[i]]++;
    if (records[nums[i]] > 1) {
      return nums[i];
    }
  }
  return 0;
}

解法 3：迭代 + set

题解：剑指 Offer 03. 数组中重复的数字（哈希表 / 原地交换，清晰图解）

这个其实和我想的 “迭代 + map” 属于相同思路，但是这里用 set 这个数据结构更合适。

public int findRepeatNumber3(int[] nums) {
  Set dic = new HashSet<>();
  for (int num : nums) {
    if (dic.contains(num))
      return num;
    dic.add(num);
  }
  return 0;
}

Golang 中没有实现 set 这个数据结构，还是用 map。

解法 4：原地交换

题解：剑指 Offer 03. 数组中重复的数字（哈希表 / 原地交换，清晰图解）

原地交换的思路和 “解法 2 - 迭代 + 数组” 有点类似，都是借助于 nums 里的所有数字都在 0～n-1 的范围内这个条件，这个条件使得 nums 里的值一定都可以放到对应长度的数组中，这也就是解法 2 的思路。

这里更高级的点在于不需要开辟新的空间，只要想着将 nums 数组中的值放到这个值对应的索引位置，这个数组最后必然会变的有序，而某个地方如果值已经对上，下次再想放进来就能发现重复了。

// go
func findRepeatNumber3(nums []int) int {
	i := 0
	for i < len(nums) {
		if nums[i] == nums[nums[i]] {
			i++
			continue
		}
		tmp := nums[i]
		nums[i] = nums[nums[i+1]]
		nums[nums[i+1]] = tmp
	}
	return -1
}

// java
public int findRepeatNumber(int[] nums) {  
  int i = 0;  
  while(i < nums.length) {    
    if(nums[i] == i) {      
      i++;      
      continue;    
    }    
    if(nums[nums[i]] == nums[i]) return nums[i];    
    int tmp = nums[i];    
    nums[i] = nums[tmp];    
    nums[tmp] = tmp;  
  }  
  return -1;
}

9. 在排序数组中查找数字 I

题目：剑指 Offer 53 - I. 在排序数组中查找数字 I

_解法 1：迭代

思路：遍历一次数组即可

func search(nums []int, target int) int {
	var count int
	for _, v := range nums {
		if v > target {
			break
		}
		if target == v {
			count++
		}
	}
	return count
}

_解法 2：二分法

思路：二分查找，找到一个满足条件的数组，则往前往后继续寻找

func search2(nums []int, target int) int {
	var count int
	start, end := 0, len(nums)
	for start < end {
		mid := (start + end) / 2
		if target < nums[mid] {
			end = mid
		} else if target > nums[mid] {
			start = mid + 1
		} else {
			count++
			// behind
			idx := mid + 1
			for idx < len(nums) {
				if nums[idx] == target {
					count++
					idx++
				} else {
					break
				}
			}
			// front
			idx = mid - 1
			for idx >= 0 {
				if nums[idx] == target {
					count++
					idx--
				} else {
					break
				}
			}
			return count
		}
	}
	return 0
}

评论区的二分法，思路更简洁一些：

func search3(nums []int, target int) int {
	left, right := 0, len(nums)-1
	var count int
	for left < right {
		mid := (left + right) / 2
		if nums[mid] >= target {
			right = mid
		}
		if nums[mid] < target {
			left = mid + 1
		}
	}
	for left < len(nums) && nums[left] == target {
		count++
		left++
	}
	return count
}

10. 0～n-1中缺失的数字（二分）

对于有序数组，都应该考虑二分法搜索。

题目：剑指 Offer 53 - II. 0～n-1中缺失的数字

_解法 1：迭代

// go
func missingNumber(nums []int) int {
	length := len(nums)
	if nums[0] != 0 {
		return 0
	}
	if nums[length-1] == length-1 {
		return length
	}
	for i := 1; i < length; i++ {
		if nums[i]-nums[i-1] != 1 {
			return nums[i] - 1
		}
	}
	return -1
}

解法 2：二分

经验之谈：二分循环范围如何选定

while(i <= j) 搜索的是闭区间 [i, j]，闭区间内的每一个元素都会被搜索，循环退出时 i = j + 1

while(i < j) 搜索的是区间 [i, j)，区间内除了 j 指向的每一个元素都会被搜索，循环退出时 i = j

根据具体问题，先明确下希望搜索的范围再决定用哪种，有的用哪种都可以，有的只能用其中一种。
// 二分模板
public int binarySearch(int l, int r) {
	int mid;
	while (l < r) {
		mid = (l + r) >> 1;
 		if (check(mid)) {
    		r = mid;
  		} else {
      		l = mid + 1;
  		}
	}
	return l;
}

public int binarySearch(int l, int r) {
	int mid;
	while (l < r) {
		mid = (l + r + 1) >> 1;
  		if (check(mid)) {
      		l = mid;
  		} else {
      		r = mid - 1;
  		}
	}
	return l;
}

二分的经验：计算中点

正常写法：
mid = (left + right) / 2
上面的写法在 left 和 right 特别大的时候，会有整形溢出的风险，最好如下写：
mid = left + (right - left) >> 1

我的二分：

// 二分搜索
func missingNumber2(nums []int) int {
	length := len(nums)
	// 首尾边界
	if nums[0] != 0 {
		return 0
	}
	if nums[length-1] == length-1 {
		return length
	}

	left, right := 0, length-1
	for left <= right {
		mid := (left + right) / 2
		if nums[mid] <= mid {
			left = mid + 1
		} else if nums[mid] > mid {
			right = mid - 1
		}
		if nums[mid+1]-nums[mid] != 1 {
			return nums[mid] + 1
		}
	}

	return -1
}

题解中的二分：

// go
func missingNumber3(nums []int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		mid := (left + right) >> 1
		if nums[mid] == mid {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return left
}

查找算法（中等） 11. 二维数组中的查找

题目：剑指 Offer 04. 二维数组中的查找

_解法 1：暴力迭代

时间复杂度：O(n * m)

// go
func findNumberIn2DArray(matrix [][]int, target int) bool {
	for _, item := range matrix {
		for _, v := range item {
			if target == v {
				return true
			}
		}
	}
	return false
}

解法 2：标志数

题解：面试题04. 二维数组中的查找（标志数，清晰图解）

以后遇到二维数组，不一定要从 0, 0 开始循环，多点别的思路。。。

时间复杂度：O(n + m)

// go
func findNumberIn2DArray(matrix [][]int, target int) bool {
	row := len(matrix)
	// []
	if row == 0 {
		return false
	}
	col := len(matrix[0])
	// [[]]
	if col == 0 {
		return false
	}

	i, j := row-1, 0

	for i >= 0 && j < col {
		if matrix[i][j] > target {
			i--
		} else if matrix[i][j] < target {
			j++
		} else {
			return true
		}
	}

	return false
}

解法 3：逐行二分

还是没有领悟那句话的精髓 ---- 遇到有序数组就用二分！

思路：依旧是遍历每行，对行再遍历的时候使用二分查找

时间复杂度：O(n * log(m))

// java
class Solution {
	public boolean findNumberIn2DArray(int[][] matrix, int target) {
		if (matrix.length == 0) {
			return false;
		}
		for (int i = 0; i < matrix.length; i++) {
			int index = Arrays.binarySearch(matrix[i], target);
			if (index >= 0) {
				return true;
			}
		}
		return false;
	}
}

12. 旋转数组的最小数字

题目：剑指 Offer 11. 旋转数组的最小数字

_解法 1：暴力迭代

思路：遍历找到第一个比左边的数字大的数字，就是目标值

func minArray(numbers []int) int {
	if len(numbers) == 1 {
		return numbers[0]
	}
	for i := 1; i < len(numbers); i++ {
		if numbers[i] < numbers[i-1] {
			return numbers[i]
		}
	}
	return numbers[0]
}

题解中看到的思路：遍历找到比 numbers[0] 小的值就是目标值

func minArray(numbers []int) int {
	for i := 0; i < len(numbers); i++ {
		if numbers[i] < numbers[0] {
			return numbers[i]
		}
	}
	return numbers[0]
}

解法 2：二分

二分的模板已经很熟了，但是真正应用还需要多练！

核心在于在适当的时候控制边界条件！

func minArray(number []int) int {
	left, right := 0, len(number)-1
	for left < right {
		mid := left + (right-left)>>1
		if number[mid] < number[right] {
			right = mid
		} else if number[mid] > number[right] {
			left = mid + 1
		} else {
			right--
		}
	}
	return number[left]
}

func minArray(numbers []int) int {
	left, right := 0, len(numbers)-1
	for left < right {
		mid := left + (right-left)>>1
		if numbers[mid] < numbers[right] {
			right--
		} else if numbers[mid] > numbers[right] {
			left = mid + 1
		}
	}
	return numbers[left]
}

13. 第一个只出现一次的字符

题目：剑指 Offer 50. 第一个只出现一次的字符

_解法 1：暴力迭代

若从前往后找到某个元素的索引，和从后往前找到某个元素的索引相同，则说明只出现一次。

好像由于下面的方法每次要执行 s[i]，还是会比上面慢一点。

// go
// 转成 byte 数组后遍历
func firstUniqChar(s string) byte {
	b := []byte(s)
	for _, v := range b {
		if bytes.LastIndexByte(b, v) == bytes.IndexByte(b, v) {
			return v
		}
	}
	return ' '
}

// 直接遍历字符串
func firstUniqChar(s string) byte {
	for i := 0; i < len(s); i++ {
		if strings.IndexByte(s, s[i]) == strings.LastIndexByte(s, s[i]) {
			return s[i]
		}
	}
	return ' '
}

_解法 2：哈希

// go
func firstUniqChar2(s string) byte {
	m := make(map[byte]int, 0)

	b := []byte(s)
	for _, v := range b {
		m[v]++
	}
	for _, v := range b {
		if m[v] == 1 {
			return v
		}
	}
	return ' '
}

评论中的做法：是哈希的思路，但是用数组存储。

对于这种存储范围已经固定的，完全可以用数组。

// go
func firstUniqChar3(s string) byte {
	if s == "" {
		return ' '
	}
	dic := make([]int, 26)
	b := []byte(s)
	for _, v := range b {
		dic[v-'a']++
	}
	for _, v := range b {
		if dic[v-'a'] == 1 {
			return v
		}
	}
	return ' '
}

解法 3：有序哈希表

题解：面试题50. 第一个只出现一次的字符（哈希表 / 有序哈希表，清晰图解）

该思路我是想到了，不过 Go 中没有有序哈希表这个数据结构，Java 中有 linkedHashMap。

// java
public char firstUniqChar2(String s) {
  Map dic = new linkedHashMap<>();
  char[] sc = s.toCharArray();
  for (char c : sc)
    dic.put(c, !dic.containsKey(c));
  for (Map.Entry d : dic.entrySet()) {
    if (d.getValue())
      return d.getKey();
  }
  return ' ';
}

搜索与回溯算法（简单） 14. 从上到下打印二叉树 I

题目：面试题32 - I. 从上到下打印二叉树

二叉树的层序遍历，又称二叉树的广度优先搜索（BFS）。

广度优先搜索算法（Breadth-First-Search，缩写为 BFS），是一种利用队列实现的搜索算法。

简单来说，其搜索过程和 “湖面丢进一块石头激起层层涟漪” 类似。

深度优先搜索算法（Depth-First-Search，缩写为 DFS），是一种利用递归实现的搜索算法。

简单来说，其搜索过程和 “不撞南墙不回头” 类似。

解法 1：队列

// java
class Solution {
    public int[] levelOrder(TreeNode root) {
        if (root == null) return null;
        
        List resList = new ArrayList<>();
        Queue queue = new linkedList<>() {{ offer(root); }};
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            resList.add(node.val);

            if (node.left != null)
                queue.offer(node.left);
            if (node.right != null)
                queue.offer(node.right);
        }
        // list ---> int[]
	      return resList.stream().mapToInt(e -> e.intValue()).toArray();
        // int[] resArray = new int[resList.size()];
        // for (int i = 0; i < resList.size(); i++) 
            // resArray[i] = resList.get(i);
        // return resArray;
    }
}

// go
func levelOrder(root *TreeNode) []int {
	if root == nil {
		return []int{}
	}

	var res = make([]int, 0)

	queue := make([]*TreeNode, 0)
	queue = append(queue, root)
	for len(queue) != 0 {
		node := queue[0]
		queue = queue[1:] // 模拟队列出队

		res = append(res, node.Val)
		if node.Left != nil {
			queue = append(queue, node.Left)
		}
		if node.Right != nil {
			queue = append(queue, node.Right)
		}
	}
	return res
}

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

题目：剑指 Offer 32 - II. 从上到下打印二叉树 II

解法 1：队列

题解：面试题32 - II. 从上到下打印二叉树 II（层序遍历 BFS，清晰图解）

class Solution {
    public List> levelOrder1(TreeNode root) {
        if (root == null) return new ArrayList<>();

        List> resList = new linkedList<>();
        Queue queue = new linkedList<>() {{ offer(root); }};
        while (!queue.isEmpty()) {
            List tmpList = new ArrayList<>();
          	// 取出一行元素
            for (int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                tmpList.add(node.val);
                if (node.left != null)
                    queue.offer(node.left);
                if (node.right != null)
                    queue.offer(node.right);
            }
          	resList.add(tmpList);
        }
        return resList;
    }
}

解法 2：递归

这个解法是比较妙的，本质上是个先序遍历，

遍历到哪一层就将这一层的 list 创建好，填入第一个元素当后面再次遍历来到这一层时，利用二维 list 的下标将结果放到对应的层中

class Solution {
    List> resList = new ArrayList<>();
    public List> levelOrder(TreeNode root) {
        helper(root, 0);
        return resList;
    }

    // 本质上是先序遍历
    public void helper(TreeNode node, int level) {
        if (node == null) return;
        if (resList.size() <= level)
            resList.add(new ArrayList<>());
        resList.get(level).add(node.val);
        helper(node.left, level + 1);
        helper(node.right, level + 1);
    }
}

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

题目：剑指 Offer 32 - III. 从上到下打印二叉树 III

_解法 1：双栈

思路：二叉树层次遍历的大模板下，加一些额外操作而已。

// java
public List> levelOrder(TreeNode root) {
  if (root == null) return new ArrayList<>();

  List> resList = new ArrayList<>();
  Stack stack1 = new Stack<>();
  Stack stack2 = new Stack<>();
  stack1.add(root);

  boolean flag = true;
  while (!(stack1.isEmpty() && stack2.isEmpty())) {
    List tmpList = new ArrayList<>();
    if (flag) {
      for (int i = stack1.size(); i > 0; i--) {
        TreeNode node = stack1.pop();
        tmpList.add(node.val);
        if (node.left != null)
          stack2.add(node.left);
        if (node.right != null)
          stack2.add(node.right);
      }
    } else {
      for (int i = stack2.size(); i > 0; i--) {
        TreeNode node = stack2.pop();
        tmpList.add(node.val);
        if (node.right != null)
          stack1.add(node.right);
        if (node.left != null)
          stack1.add(node.left);
      }

    }
    resList.add(tmpList);
    flag = !flag;
  }
  return resList;
}

解法 2：双端队列

题解：面试题32 - III. 从上到下打印二叉树 III（层序遍历 BFS / 双端队列，清晰图解

// java
public List> levelOrder(TreeNode root) {
  if (root == null) return new ArrayList<>();

  List> resList = new ArrayList<>();
  Deque deque = new linkedList<>();
  deque.add(root);

  while (!deque.isEmpty()) {
    List tmpList = new ArrayList<>();
    // 打印奇数层
    for (int i = deque.size(); i > 0; i--) {
      // 左 -> 右
      TreeNode node = deque.removeFirst();
      tmpList.add(node.val);
      // 先左后右加入下层节点
      if (node.left != null)
        deque.addLast(node.left);
      if (node.right != null)
        deque.addLast(node.right);
    }
    resList.add(tmpList);

    if (deque.isEmpty()) break;

    // 打印偶数层
    tmpList = new ArrayList<>();
    for (int i = deque.size(); i > 0; i--) {
      // 右 -> 左
      TreeNode node = deque.removeLast();
      tmpList.add(node.val);
      // 先右后左加入下层节点
      if (node.right != null)
        deque.addFirst(node.right);
      if (node.left != null)
        deque.addFirst(node.left);
    }
    resList.add(tmpList);
  }

  return resList;
}

解法 3：层序遍历 + 倒序

思路：在层序遍历的基础上，添加时将奇数层倒序。

public List> levelOrder(TreeNode root) {
  if (root == null) return new ArrayList<>();

  List> resList = new ArrayList<>();
  Queue queue = new linkedList<>();
  queue.add(root);

  while (!queue.isEmpty()) {
    List tmpList = new ArrayList<>();
    for (int i = queue.size(); i > 0; i--) {
      TreeNode node = queue.poll();
      tmpList.add(node.val);
      if (node.left != null)
        queue.offer(node.left);
      if (node.right != null)
        queue.offer(node.right);
    }
    // 奇数层倒序
    if (resList.size() % 2== 1)
      Collections.reverse(tmpList);
    resList.add(tmpList);
  }
  return resList;
}

Go 语言切片

Go 语言模拟队列的先进先出，相当于取出头部一个值后，丢弃这个值 queue = queue[1:]

func levelOrder(root *TreeNode) [][]int {
	var res = make([][]int, 0)
	if root == nil {
		return res
	}

	queue := []*TreeNode{root}
  
	flag := false // 奇偶顺序控制
	for len(queue) > 0 {
		length := len(queue)
		tmp := make([]int, length)

		for i := 0; i < length; i++ {
			node := queue[0]
			queue = queue[1:]
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
			if flag {
				tmp[length-i-1] = node.Val
			} else {
				tmp[i] = node.Val
			}
		}
		res = append(res, tmp)
		flag = !flag
	}
	return res
}

17. 树的子结构

题目：剑指 Offer 26. 树的子结构

解法 1：双重递归 DFS

我的 helper 函数基本写对了，不过 isSubStructure 没考虑到用递归。。

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) return false;
        return helper(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
    boolean helper(TreeNode A, TreeNode B) {
        if (B == null) return true;
        if (A == null || A.val != B.val) return false;
        return helper(A.left, B.left) && helper(A.right, B.right);
    }
}

解法 2：双重 BFS（很慢）

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) return false;
        Queue queue = new linkedList<>() {{ offer(A); }};
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.val == B.val) 
                if (helper(node, B))
                    return true;
            if (node.left != null)
                queue.offer(node.left);
            if (node.right != null)
                queue.offer(node.right);
        }
        return false;
    }
    boolean helper(TreeNode A, TreeNode B) {
        Queue queueA = new linkedList<>() {{ offer(A); }};
        Queue queueB = new linkedList<>() {{ offer(B); }};

        while (!queueB.isEmpty()) {
            TreeNode nodeA = queueA.poll();
            TreeNode nodeB = queueB.poll();
            if (nodeA == null || nodeA.val != nodeB.val)
                return false;
            if (nodeB.left != null) {
                queueA.offer(nodeA.left);
                queueB.offer(nodeB.left);
            }
            if (nodeB.right != null) {
                queueA.offer(nodeA.right);
                queueB.offer(nodeB.right);
            }
        }
        return true;
    }
}

18.二叉树的镜像

题目：剑指 Offer 27. 二叉树的镜像

_解法 1：递归 DFS

这题很简单！很适合用来检验对递归的掌握程度。

// java
public TreeNode mirrorTree(TreeNode root) {
	 if (root == null) return null;
	 TreeNode leftNode = mirrorTree(root.left);
	 TreeNode rightNode = mirrorTree(root.right);
	 root.left = rightNode;
	 root.right = leftNode;
	 return root;
}

利用 Go 语言平行赋值的写法，可以省略暂存操作。

// go
func mirrorTree(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	leftNode, rightNode := mirrorTree(root.Left), mirrorTree(root.Right)
	root.Left, root.Right = rightNode, leftNode
	return root
}

解法 2：辅助栈

题解：剑指 Offer 27. 二叉树的镜像（递归 / 辅助栈，清晰图解）

// java
public TreeNode mirrorTree1(TreeNode root) {
  if (root == null) return null;
  Stack stack = new Stack<>() {{ add(root); }};
  while (!stack.empty()) {
    TreeNode node = stack.pop();
    if (node.left != null)
      stack.add(node.left);
    if (node.right != null)
      stack.add(node.right);
    TreeNode tmp = node.left;
    node.left = node.right;
    node.right = tmp;
  }
  return root;	
}

19. 对称的二叉树

题目：剑指 Offer 28. 对称的二叉树

_解法 1：暴力

注意，这里写的获取二叉树的镜像涉及到一些 Java 值传递的概念，不可以在 root 上直接修改，需要创建一个新的对象，或者 root = new TreeNode(root.val) 也是可以的。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        TreeNode newTree = mirrorTree(root);
        return isSameTree(root, newTree);
    }

    
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if ((p != null && q ==null) || (p == null && q != null))
            return false;
        if (p.val != q.val)
            return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
    
    TreeNode mirrorTree(TreeNode root) {
        if (root == null)  return null;
        TreeNode leftNode = mirrorTree(root.left);
        TreeNode rightNode = mirrorTree(root.right);
        TreeNode node = new TreeNode(root.val);
        node.left = rightNode;
        node.right  = leftNode;
        return node;
    }
}

解法 2：递归

题解：面试题28. 对称的二叉树（递归，清晰图解）

1、递归的函数要干什么?

函数的作用是判断传入的两个树是否镜像。输入：TreeNode left, TreeNode right输出：是：true，不是：false
2、递归停止的条件是什么？

左节点和右节点都为空 -> 倒底了都长得一样 ->true左节点为空的时候右节点不为空，或反之 -> 长得不一样-> false左右节点值不相等 -> 长得不一样 -> false
3、从某层到下一层的关系是什么？

要想两棵树镜像，那么一棵树左边的左边要和二棵树右边的右边镜像，一棵树左边的右边要和二棵树右边的左边镜像调用递归函数传入左左和右右调用递归函数传入左右和右左只有左左和右右镜像且左右和右左镜像的时候，我们才能说这两棵树是镜像的
4、调用递归函数

我们想知道它的左右孩子是否镜像，传入的值是 root 的左孩子和右孩子。这之前记得判个 root==null。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root ==null) return true;
        return isMirror(root.left, root.right);
    }
    
    boolean isMirror(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        if (left.val != right.val) return false;
        return isMirror(left.left, right.right) && isMirror(left.right, right.left);
    }
}

《剑指 Offer I》刷题笔记 1 ~ 19 题

Java相关栏目本月热门文章