No.3 腾讯，阿里，字节，优科面经（上-算法篇）

https://blog.csdn.net/qq_41385137/article/details/12749270

/*
题目：给定两个整数数组 preorder 和 inorder ，
其中 preorder 是二叉树的先序遍历， 
inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
*/


/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder)==0{
        return nil
    }
    root := &TreeNode{preorder[0],nil,nil}
    i:=0
    for ;i<len(inorder);i++{
        if preorder[0]==inorder[i]{
            break
        }
    }
    root.Left=buildTree(preorder[1:len(inorder[:i])+1],inorder[:i])
    root.Right=buildTree(preorder[len(inorder[:i])+1:],inorder[i+1:])
    return root
}

/*
题目：请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：LRUCache(int capacity) 以 正整数 
作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 
存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，
则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。
如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
*/


type entry struct{
    key,value int
}
 
type LRUCache struct{
    cap int
    cache map[int]*list.Element
    lst *list.List
}
 
 
func Constructor(capacity int)LRUCache{  //LRU算法
        return LRUCache{capacity,map[int]*list.Element{},list.New()}
}
 
func (c *LRUCache)Get(key int)int{
    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)
    }
 
 
}

/*
题目一：(考察二叉树)
  给定一个有序数组，但是数组以某个元素作为支点进行了旋转(比如，0 1 2 4 5 6 7 可能成为4 5 6 7 0 1 2)。
  给定一个目标值target进行搜索，如果在数组中找到目标值返回数组中的索引位置，否则返回-1。
  你可以假设数组中不存在重复的元素。
*/
func search(nums []int, target int) int {
  if len(nums) == 0 {
    return -1
  }
  left := 0
  right := len(nums) - 1
 
 
  for left <= right {
    mid := (left + right)  2
    if target == nums[mid] {
      return mid
    }
    if nums[left] < nums[mid] && target <= nums[mid] && target >= nums[left] {
      right = mid - 1
    } else if nums[left] > nums[mid] && target <= nums[mid] {
      right = mid - 1
    } else if nums[left] > nums[mid] && target >= nums[left] {
      right = mid - 1
    } else {
      left = mid + 1
    }
  }
 
  return -1
}


/*
题目二：给你一个 m 行 n 列的矩阵 matrix ，
请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
*/
func spiralOrder(matrix [][]int) []int {
    ans :=make([]int,0)
    x,x1 := len(matrix),0
    y,y1 := len(matrix[0]),0
    zong := x * y
    for {
        for i1:=y1;i1<y;i1++{   //行固定的，列在动
            ans =append(ans,matrix[x1][i1])
        }
        x1++
 
        for i2:=x1;i2<x;i2++{ 
            ans=append(ans,matrix[i2][y-1])
        }
        y--
 
        for i3:=y-1; i3>=y1; i3--   {
            ans =append(ans,matrix[x-1][i3])
 
        }
        x--
        for i4:=x-1 ;i4>=x1;i4--{
             ans =append(ans,matrix[i4][y1])
        }
        y1++
 
        if len(ans)>=zong{
            break
 
        }
    } 
 
    return ans
}




/*
题目三：循环检测。如[['A','B'],['B','C']['C','D'],['B','D']]==>false
[['A','B'],['B','C'],['C','A']]==>true 
参考题解：https://mp.weixin.qq.com/s/pCRscwKqQdYYN7M1Sia7xA
*/


/*
题目四：这道题考了mysql的一些知识，当时给了一个学生表，
求SQL查每个学生成绩最好的科目，大家面字节的业务代码开发，
就多学一些mysql的东西吧，多刷一下常见sql语句。
*/

// 题目一：二分查找有序数组中第一次出现数的位置。（c++解题）
public int search (int[] nums, int target) {
       if(nums.length == 0) {
           return -1;
       }
        int begin = 0;
        int end = nums.length - 1;
        while(begin < end) {
            int mid = (begin + end)  2;
            if(nums[mid] < target) {
                begin = mid + 1;
            } else {
                end = mid; 
            }
        }
        return nums[begin] == target ? begin : -1;
    }
    


// 题目二：操作给定的二叉树，将其变换为源二叉树的镜像。(c++解题)
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */
 
/*
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * @param pRoot TreeNode类
 * @return TreeNode类
*/


func Mirror( pRoot *TreeNode ) *TreeNode {
    // write code here
    if pRoot==nil{
        return nil
    }
     
    pRoot.Left,pRoot.Right =pRoot.Right,pRoot.Left
    Mirror(pRoot.Left)
    Mirror(pRoot.Right)
    return pRoot
}
// 牛客101道题地址：https://www.nowcoder.com/exam/oj