头像

emmm...


访客:1651

离线:1天前



emmm...
3个月前

题目描述

数字以0123456789101112131415…的格式序列化到一个字符序列中。

在这个序列中,第5位(从0开始计数)是5,第13位是1,第19位是4,等等。

请写一个函数求任意位对应的数字。

样例

输入:13

输出:1

golang 代码

func digitAtIndex(n int) int {
    // 1-9  9个1位数   10-99  90个2位数  100-999  900个3位数 1000-9999 9000个4位数
    var i,j,k = 9,1,1    //i表示9 ,j表示几位数 , k表示第几位开始
    for n > i * j {
        n -= i * j 
        i *= 10
        j++
        k *= 10
    }

    order := k + (n - 1) / j
    //对位数求余,余几就是第几位。余0表示最后一位    如190,表示100,余1,表示第一位1,余2,表示第二位0
    num := n % j 
    if num == 0 {
        num = j
    }
    for m := 0 ; m < j - num ; m++ {
        order /= 10
    }
    return order%10

}



emmm...
3个月前

题目描述

输入一个 非空 整型数组,数组里的数可能为正,也可能为负。

数组中一个或连续的多个整数组成一个子数组。

求所有子数组的和的最大值。

要求时间复杂度为O(n)。

样例

输入:[1, -2, 3, 10, -4, 7, 2, -5]

输出:18

golang 代码

func maxSubArray(nums []int) int {
    sum := 0
    big := nums[0]
    for _,num := range nums {
        if sum >= 0 {
            sum += num
        }else{
            sum = num
        }
        if sum > big {
            big = sum
        }
    }
    return big
}



emmm...
3个月前

题目描述

如何得到一个数据流中的中位数?

如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。

如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。

样例

输入:1, 2, 3, 4

输出:1,1.5,2,2.5

解释:每当数据流读入一个数据,就进行一次判断并输出当前的中位数。

golang 代码

var nums []int
func insert(num int) {
    var temp = make([]int,len(nums))
    _ = copy(temp,nums)
    for i := 0 ; i < len(nums) ; i++ {
        if num <= nums[i] {
            temp = append(temp[:i],num)
            nums = append(temp, nums[i:]...)
            return
        }
    }
    nums = append(nums,num)
}

func getMedian() float64{
    if len(nums) % 2 == 1 {
        return float64(nums[len(nums)/2])
    }else{
        return (float64(nums[len(nums)/2-1])+float64(nums[len(nums)/2]))/2
    }

}



emmm...
3个月前

题目描述

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。

假设数组非空,并且一定存在满足条件的数字。

思考题:

假设要求只能使用 O(n) 的时间和额外 O(1) 的空间,该怎么做呢?

样例

输入:[1,2,1,1,3]

输出:1

golang 代码

func moreThanHalfNum_Solution(nums []int) int {
    var ans,count int
    for _,num := range nums {
        if count == 0 {
            ans = num
            count++
        }else{
            if(ans == num){
                count++
            }else{
                count--
            }
        }
    }
    return ans
}



emmm...
3个月前

题目描述

输入一组数字(可能包含重复数字),输出其所有的排列方式。

样例

输入:[1,2,3]

输出:
      [
        [1,2,3],
        [1,3,2],
        [2,1,3],
        [2,3,1],
        [3,1,2],
        [3,2,1]
      ]

golang 代码

var ans [][]int
var path []int
func permutation(nums []int) [][]int {
    path = make([]int,len(nums))
    sort.Ints(nums)
    order(nums,0,0,0)
    return ans
}

//nums:输入数组 u:把数组里第u个元素插入  
//s:上一个元素插入位置(如果不同,0开始;相同则s之后)state:插入位置通过二进制保存
func order(nums []int, u int, s int, state int) {
    if u == len(nums){
        var temp = make([]int,len(path))
        _ = copy(temp,path)
        ans = append(ans,temp)
        return
    }
    if u == 0 || nums[u] != nums[u-1] {
        s = 0
    }
    for i := s ; i < len(nums) ; i++ {
        if (state >> uint(i)) & 1 == 0 {
            path[i] = nums[u]
            order(nums, u + 1, i + 1 , state + (1 << uint(i)))
        }
    }
}



emmm...
3个月前

题目描述

输入一组数字(可能包含重复数字),输出其所有的排列方式。

样例

输入:[1,2,3]

输出:
      [
        [1,2,3],
        [1,3,2],
        [2,1,3],
        [2,3,1],
        [3,1,2],
        [3,2,1]
      ]

golang 代码

/*
//数字全部不重复
//思想:n个数字,先对n-1个进行排序,再把第n个数字插入n-1排序的切片里
func permutation(nums []int) [][]int {
    return order(nums)
}

//求出所有n个元素排序
func order(nums []int) [][]int {
    if len(nums) == 0 {
        return nil
    }
    if len(nums) == 1 {
        temp := make([][]int, 1)
        temp[0] = nums
        return temp
    }
    //将第n个元素插入到前n-1个元素的队列里
    return insert(order(nums[:len(nums)-1]), nums[len(nums)-1]) 
}

//例如输入 [[1,2],[2,1]]   3        需要返回[[1,2,3], ... ]
func insert(nums [][]int, insertnum int) [][]int {
    var ans [][]int
    for _ , n := range nums {
        for i := 0 ; i < len(n) ; i++ {
            var temp = make([]int,len(n))
            _ = copy(temp, n)
            temp = append(temp[:i], insertnum)
            temp = append(temp,n[i:]...)
            ans = append(ans,temp)
        }
        temp := append(n, insertnum)
        ans = append(ans,temp)
    }
    return ans
}
*/

//数字重复,重复的数字只能放到另一个数字之后
func permutation(nums []int) [][]int {
    //排序
    mysort(nums)
    return order(nums)
}

//冒泡
func mysort(nums []int) {
    for i := 0 ; i < len(nums) - 1 ; i++ {
        for j := i + 1 ; j < len(nums) ; j++ {
            if nums[i] > nums[j] {
                nums[i],nums[j] = nums[j],nums[i]
            }
        }
    }
}

func order(nums []int) [][]int {
    if len(nums) == 0 {
        return nil
    }
    if len(nums) == 1 {
        temp := make([][]int, 1)
        temp[0] = nums
        return temp
    }
    return insert(order(nums[:len(nums)-1]), nums[len(nums)-1])
}

func insert(nums [][]int , insertnum int) [][]int {
    var ans [][]int
    for _, n := range nums {
        var pre = -1
        //存在相等数就添加后面,不存在则从头开始添加
        for k := len(n)-1 ; k >= 0 ; k-- {
            if n[k] == insertnum {
                pre = k
                break
            }
        }
        for i := pre + 1 ; i < len(n) ; i++ {
            var temp = make([]int , len(n))
            _ = copy(temp, n)
            temp = append(temp[:i],insertnum)
            temp = append(temp, n[i:]...)
            ans = append(ans,temp)
        }
        temp := append(n,insertnum)
        ans = append(ans,temp)
    }
    return ans
}



emmm...
3个月前

题目描述

请实现两个函数,分别用来序列化和反序列化二叉树。

您需要确保二叉树可以序列化为字符串,并且可以将此字符串反序列化为原始树结构。

样例

你可以序列化如下的二叉树
    8
   / \
  12  2
     / \
    6   4

为:"[8, 12, 2, null, null, 6, 4, null, null, null, null]"

golang 代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 /**
 * Encodes a tree to a single string.
 */

 func serialize(root *TreeNode) string {
    var ans = "["

    var queue []*TreeNode
    queue = append(queue,root)

    for len(queue) != 0 {
        myroot := queue[0]
        if myroot == nil {
            ans = ans + "null,"
        }else{
            ans = ans + strconv.Itoa(myroot.Val) + ","
            queue = append(queue,myroot.Left)
            queue = append(queue,myroot.Right)
        }
        queue = queue[1:]
    }
    ans = ans[:len(ans)-1] + "]"
    return ans
}





/**
 * Decodes your encoded data to tree.
 */
func deserialize(data string) *TreeNode {
    //对数据进行处理,分割成  []string
    data = data[1:len(data)-1]
    mydata := strings.Split(data,",")
    if mydata[0] == "null" {
        return nil
    }
    var root = new(TreeNode)
    root.Val,_ = strconv.Atoi(mydata[0])
    makeTree(mydata, root, 0)
    return root
}

//mydata为数据,root为根节点,num为root在mydata中的位置
func makeTree(mydata []string, root *TreeNode, num int) {
    //判断空节点数量
    var nilnum int
    for i := 0 ; i < num ; i++ {
        if mydata[i] == "null" {
            nilnum++
        }
    }
    //左子树存在
    if (num - nilnum) * 2 + 1 < len(mydata) {
        if mydata[(num - nilnum) * 2 + 1] != "null" {
            var left =  new(TreeNode)
            left.Val,_ = strconv.Atoi(mydata[(num - nilnum) * 2 + 1])
            root.Left = left
            makeTree(mydata, left , (num - nilnum) * 2 + 1)
        }
        //左子树为空   
    }
    //右子树存在
    if (num - nilnum + 1 ) * 2 < len(mydata) {
        if mydata[(num - nilnum + 1 ) * 2 ] != "null" {
            var right =  new(TreeNode)
            right.Val,_ = strconv.Atoi(mydata[(num - nilnum + 1 ) * 2 ])
            root.Right = right
            makeTree(mydata, right , (num - nilnum + 1 ) * 2 )
        }
        //右子树为空   
    }
}



emmm...
3个月前

题目描述

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。

要求不能创建任何新的结点,只能调整树中结点指针的指向。
注意:

需要返回双向链表最左侧的节点。


golang 代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var pre *TreeNode
func convert(root *TreeNode) *TreeNode {
    midorder(root)
    for root != nil && root.Left != nil {
        root = root.Left
    }
    return root
}

func midorder(root *TreeNode) {
    if root == nil {
        return
    }

    midorder(root.Left)

    //前一个节点是现在节点的左子树,现在节点是前一个节点的右子树
    root.Left = pre
    if pre != nil {
        pre.Right = root
    }
    pre = root

    midorder(root.Right)
}



emmm...
3个月前

题目描述

输入一棵二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。

从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

样例

给出二叉树如下所示,并给出num=22。
      5
     / \
    4   6
   /   / \
  12  13  6
 /  \    / \
9    1  5   1

输出:[[5,4,12,1],[5,6,6,5]]

golang 代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 //定义全局变量
var ans [][]int
func findPath(root *TreeNode, sum int) [][]int {
    if root == nil {
        return nil
    }
    var a []int
    //深度优先遍历
    dfs(root, sum, a)
    return ans
}

func dfs(root *TreeNode, sum int, a []int) {
    //添加节点到路径slice
    a = append(a, root.Val)
    //子节点不为空,向下遍历
    if root.Left != nil {
        dfs(root.Left, sum, a)
    }
    if root.Right != nil {
        dfs(root.Right, sum, a)
    }
    //找到子节点,判断
    if root.Left == nil && root.Right == nil{
        var t []int
        //此处添加t而不是直接append切片a,是因为append切片是添加切片指针,后续切片改变会影响ans结果
        var temp int
        for _,i := range a {
            temp += i
            t = append(t,i)
        }
        if temp == sum {
            ans = append(ans,t)
        }
    }
}






emmm...
3个月前

题目描述

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。

如果是则返回true,否则返回false。

假设输入的数组的任意两个数字都互不相同。

样例

输入:[4, 8, 6, 12, 16, 14, 10]

输出:true

golang 代码

func verifySequenceOfBST(seq []int) bool{
    return istree(seq, 0, len(seq)-1)
}

//输入序列
func istree(seq []int, left int, right int) bool {
    if left >= right {
        return true
    }
    var mid = -1
    for i := right - 1 ; i >= 0 ; i-- {
        //遇到左子树的根
        if seq[i] < seq[right] && mid == -1 {
            mid = i
        //左子树中有大于根的值
        }else if seq[i] > seq[right] && mid != -1 {
            return false
        }
    }
    //只有左子树或者只有右子树
    if mid == -1 || mid == right - 1 {
        return istree(seq, left, right-1)
    }else {
        return istree(seq, left, mid) && istree(seq, mid+1, right-1)
    }
}