1.反转链表

206. 反转链表 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

这题考察的就是你对递归和迭代的综合运用

解法一：递归

这递归好久没做了，还有有点蒙，下面我简单说一下思路吧

func reverseList(head *ListNode) *ListNode {
   // 先判断节点是否为空(如果节点的后一位为空，说明我们已经到达节点末尾了)
   if head == nil || head.Next == nil {
      return head
   }
   // 这里是理解的关键，这个递归他的目的就是直接到达链表的末尾
   res:=reverseList(head.Next)
   // 这里我们可以理解为head已经是尾结点了，所以我们需要修改一下方向
   head.Next.Next = head
   head.Next = nil
   return res
}

Java代码实现如下

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

解法二：迭代

我好菜啊，迭代都没想出来。。。。其实不难，主要是自己之前一直在想如何使用一个指针来实现，然后发现自己需要两个指针。。。。

func reverseList(head *ListNode) *ListNode {
   // 设置前一个节点
   var prev *ListNode = nil
   // 然后设置当前节点
   var curr = head
   // 当当前的节点为空的时候我们跳出循环
   for curr != nil {
      // 我们先暂时保存下一个节点
      tmp:=curr.Next
      // 当前节点的下一个节点就是前一个节点
      curr.Next = prev
      // 修改后我们就把前一个接地那切换为当前节点
      prev = curr
      // 然后当前节点就是下一个基点
      curr = tmp
   }
   return prev
}

java的实现代码如下

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode current = head;
    while (current!=null){
        ListNode tmp = current.next;
        current.next = prev;
        prev = current;
        current = tmp;
    }
    return prev;
}

2.LRU缓存机制

146. LRU 缓存机制 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

这题目算是比较复杂的了，先简单解释一怎么实现。我们维护一个链表和一个map，map用于判断数据是否存在，然后list用于表示使用的情况，如果是使用过就会放在最前面，然后我们每次淘汰时，都会淘汰最末尾的元素。

解法一：链表

注意，这东西得多写几遍。。。我第一次写。错了8次。。。还是看了代码的情况下，这里有好多细节可以扣

type entry struct {
   key, value int
}

type LRUCache struct {
   cap   int
   cache map[int]*list.Element
   lst   *list.List
}

// 构造缓存
func Constructor(capacity int) LRUCache {
   return LRUCache{capacity, map[int]*list.Element{}, list.New()}
}

// 获取值
func (c *LRUCache) Get(key int) int {
   // 获取值，如果不为空，那么就返回-1
   e := c.cache[key]
   if e == nil {
      return -1
   }
   // 把当前值移动到头部
   c.lst.MoveToFront(e) // 刷新缓存使用时间
   return e.Value.(entry).value
}

// 设置值
func (c *LRUCache) Put(key, value int) {
   // 判断缓存中是否存在
   if e := c.cache[key]; e != nil {
      // 存在就更新
      e.Value = entry{key, value}
      c.lst.MoveToFront(e) // 刷新缓存使用时间
      return
   }
   // 不存在我们就放一个新的
   c.cache[key] = c.lst.PushFront(entry{key, value})
   // 哦按的是否超过大小，如果超过，那么就删除
   if len(c.cache) > c.cap {
      delete(c.cache, c.lst.Remove(c.lst.Back()).(entry).key)
   }
}

3.手撕快速排序

这个已经手撕很多遍了，所以这里就不说了

4.字符串相加

415. 字符串相加 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

我去，真的不容易啊。本来嫌麻烦不想做的，但是最后还是坚持了一下，还是做出来了。我使用的是模拟法。手动模拟整个计算的进位问题

解法一：模拟法

func addStrings(num1 string, num2 string) string {
   // 为了方便计算，我们直接把字符串转换为byte
   str1:=[]byte(num1)
   str2:=[]byte(num2)
   l1:=len(str1)-1
   l2:=len(str2)-1
   // 同理我们获取两个字符串的长度，然后获取最大的一个来新建一个byte数组
   // 这个byte数组用于存储结果
   high:=max(l2,l1)
   res:=make([]byte,high+1)
   // add表示进位
   add:=0
   // 当两个字符串指针都加完时我们跳出循环
   for l1>=0 || l2>=0 {
      sum:=0
      // 因为可能存在一个指针已经加完的情况，所以我们这里为了三种情况来计算
      // 注意这里我们需要考虑进位。我们使用add来表示
      if l1 >= 0 && l2>=0 {
         sum=int(str1[l1]-'0'+str2[l2]-'0')+add
      } else if l1 >= 0 && l2 < 0 {
         sum=int(str1[l1]-'0')+add
      } else {
         sum=int(str2[l2]-'0')+add
      }
      // 如果sum大于0，表示有进位，否则我们把add置为0
      if sum >= 10 {
         add = sum/10
      } else {
         add=0
      }
      // 这里我们就可以知道当前结果位结果是多少了
      res[high] = byte(sum % 10)+'0'
      high--;l1--;l2--
   }
   // 如果还存在进位的话，我们就需要把进位加进去
   if add != 0 {
      return  string(rune(add+'0'))+string(res)
   } else {
      return string(res)
   }
}

func max(a int,b int) int {
   if a > b {
      return a
   } else {
      return b
   }
}

看了一下官方题解，看来我还是太年轻了，我的代码实在太长了。。。我这里贴一下官方的java代码

public String addStrings(String num1, String num2) {
   int i=num1.length()-1,j=num2.length()-1,add=0;
   StringBuilder ans = new StringBuilder();
   // 只有当i，j，add都为0时，我们才跳出循环
   while (i>=0 || j>=0 || add!=0){
       // 计算X(我们要避免为0的情况)
       int x = i>=0?num1.charAt(i):0;
       // 计算Y()
       int y = j>=0?num2.charAt(j):0;
       // 计算和，需要考虑进位情况
       int result = x+y+add;
       // 把结果加到ans里面
       ans.append(result%10);
       add = result/10;
       i++;
       j++;
   }
   ans.reverse();
   return ans.toString();
}

6.实现二叉树的先序、中序、后序遍历

实现二叉树先序，中序和后序遍历_牛客题霸_牛客网 (nowcoder.com) (opens new window)

唉，这题我当时想着只用一个递归解决，没想到居然没用。。。。我果然是菜鸡

主要有下面这几个思路

解法一：三个递归

最简单的方法就是，前中后序全部遍历一遍

func threeOrders( root *TreeNode ) [][]int {
	var ans [][]int
	var tmp []int
	ans = append(ans, preNode(root,&tmp))
	tmp = nil
	ans = append(ans, midNode(root,&tmp))
	tmp = nil
	ans = append(ans, lastNode(root,&tmp))
	return ans
}

func preNode(root *TreeNode,data *[]int) []int{
	if root == nil {
		return *data
	}
	*data = append(*data, root.Val)
	preNode(root.Left,data)
	preNode(root.Right,data)
	return *data
}

func midNode(root *TreeNode,data *[]int) []int{
	if root == nil {
		return *data
	}
	midNode(root.Left,data)
	*data = append(*data, root.Val)
	midNode(root.Right,data)
	return *data
}

func lastNode(root *TreeNode,data *[]int) []int{
	if root == nil {
		return *data
	}
	lastNode(root.Left,data)
	lastNode(root.Right,data)
	*data = append(*data, root.Val)
	return *data
}

解法二：两个递归

这个我咋感觉我的思路就是这个，不知道为什么当时没做出来。。。emm

// 开始遍历
func threeOrders( root *TreeNode ) [][]int {
   ans:=[][]int{{},{},{}}
   PreMidLastRoot(root,&ans[0],&ans[1],&ans[2])
   return ans
}

// PreMidLastRoot 一次递归
func PreMidLastRoot(root *TreeNode,pre,mid,last *[]int){
   if root == nil {
      return
   }
   *pre = append(*pre, root.Val)
   PreMidLastRoot(root.Left, pre, mid, last)
   *mid = append(*mid, root.Val)
    PreMidLastRoot(root.Right, pre, mid, last)
   *last = append(*last, root.Val)
}

解法三： 使用栈

这个我暂时还没理解，先放这

func PreMidLastRootStack(root *TreeNode)(pre[]int,mid[]int,last[]int){
   var stk1 []*TreeNode
   var stk2 []int  //stk1[i]对应的stk2[i], stk2[i]为 1：表示放入，前序； 2表示取出判断左子树， 3表示取出判断右子树
   if root == nil {
      return nil, nil, nil
   }
   // 放入栈时，前序pre里加入Val
   // 第一次拿出看左子树时，pre加入左子树
   // 第二次拿出看右子树，mid加入。同时pre加入右子树
   // 最后一次拿出时， last加入
   stk1 = append(stk1, root)
   stk2 = append(stk2, 1)
   pre = append(pre, root.Val)
   for len(stk1) > 0 {
      top := len(stk1) - 1
      cur := stk1[top]
      if stk2[top] == 1 {
         stk2[top] = 2
         if cur.Left != nil {
            pre = append(pre, cur.Left.Val)
            stk1 = append(stk1, cur.Left)
            stk2 = append(stk2, 1)
         }
      } else if stk2[top] == 2 {
         stk2[top] = 3
         mid = append(mid, cur.Val)
         if cur.Right != nil {
            pre = append(pre, cur.Right.Val)
            stk1 = append(stk1, cur.Right)
            stk2 = append(stk2, 1)
         }
      } else {
         last = append(last, cur.Val)
         stk1 = stk1[:top]
         stk2 = stk2[:top]
      }
   }
   return
}