IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 2021-12-14:根据身高重建队列。 假设有打乱顺序的一群人站成一个队列,数组 people 表示队列中一些人的属性(不一定按顺序)。每个 people[i] = [hi ki] 表示第 i 个 -> 正文阅读

[数据结构与算法]2021-12-14:根据身高重建队列。 假设有打乱顺序的一群人站成一个队列,数组 people 表示队列中一些人的属性(不一定按顺序)。每个 people[i] = [hi ki] 表示第 i 个

2021-12-14:根据身高重建队列。
假设有打乱顺序的一群人站成一个队列,数组 people 表示队列中一些人的属性(不一定按顺序)。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ,前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ,其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性(queue[0] 是排在队列前面的人)。
力扣406。

答案2021-12-14:

具体见代码。golang代码有点问题,具体可查看java代码。

代码用golang编写。代码如下:

package main

import (
    "fmt"
    "sort"
)

func main() {
    people := [][]int{{6, 0}, {5, 0}, {4, 0}, {3, 2}, {2, 2}, {1, 4}}
    ret := reconstructQueue2(people)
    fmt.Println(ret)
}

func reconstructQueue1(people [][]int) [][]int {
    N := len(people)
    units := make([]*Unit, N)
    for i := 0; i < N; i++ {
        units[i] = NewUnit(people[i][0], people[i][1])
    }
    sort.Slice(units, func(i, j int) bool {
        o1 := units[i]
        o2 := units[j]
        if o1.h != o2.h {
            return o2.h < o1.h
        } else {
            return o1.k > o2.k
        }
    })
    arrList := make([]*Unit, 0)
    for _, unit := range units {
        arrListCopy := arrList[0:unit.k]
        arrListCopy = append(arrListCopy, unit)
        arrListCopy = append(arrListCopy, arrList[unit.k:]...)
        arrList = arrListCopy
    }
    ans := make([][]int, N)
    for i := 0; i < N; i++ {
        ans[i] = make([]int, 2)
    }
    index := 0
    for _, unit := range arrList {
        ans[index][0] = unit.h
        ans[index][1] = unit.k
        index++
    }
    return ans
}

func reconstructQueue2(people [][]int) [][]int {
    N := len(people)
    units := make([]*Unit, N)
    for i := 0; i < N; i++ {
        units[i] = NewUnit(people[i][0], people[i][1])
    }
    sort.Slice(units, func(i, j int) bool {
        o1 := units[i]
        o2 := units[j]
        if o1.h != o2.h {
            return o2.h < o1.h
        } else {
            return o1.k > o2.k
        }
    })
    tree := &SBTree{}
    for i := 0; i < N; i++ {
        tree.insert(units[i].k, i)
    }
    allIndexes := tree.allIndexes()

    ans := make([][]int, N)
    for i := 0; i < N; i++ {
        ans[i] = make([]int, 2)
    }
    index := 0
    for _, arri := range *allIndexes {
        ans[index][0] = units[arri].h
        ans[index][1] = units[arri].k
        index++
    }
    return ans
}

type Unit struct {
    h int
    k int
}

func NewUnit(height, greater int) *Unit {
    ret := &Unit{}
    ret.h = height
    ret.k = greater
    return ret
}

type SBTNode struct {
    value int
    l     *SBTNode
    r     *SBTNode
    size  int
}

func NewSBTNode(arrIndex int) *SBTNode {
    ret := &SBTNode{}
    ret.value = arrIndex
    ret.size = 1
    return ret
}

func twoSelectOne(c bool, a, b int) int {
    if c {
        return a
    } else {
        return b
    }
}

type SBTree struct {
    root *SBTNode
}

func (this *SBTree) rightRotate(cur *SBTNode) *SBTNode {
    leftNode := cur.l
    cur.l = leftNode.r
    leftNode.r = cur
    leftNode.size = cur.size
    a := 0
    if cur.l != nil {
        a = cur.l.size
    }
    b := 0
    if cur.r != nil {
        b = cur.r.size
    }
    cur.size = a + b + 1
    return leftNode
}

func (this *SBTree) leftRotate(cur *SBTNode) *SBTNode {
    rightNode := cur.r
    cur.r = rightNode.l
    rightNode.l = cur
    rightNode.size = cur.size
    cur.size = (twoSelectOne(cur.l != nil, cur.l.size, 0)) + (twoSelectOne(cur.r != nil, cur.r.size, 0)) + 1
    return rightNode
}

func (this *SBTree) maintain(cur *SBTNode) *SBTNode {
    if cur == nil {
        return nil
    }
    leftSize := 0
    if cur.l != nil {
        leftSize = cur.l.size
    }
    leftLeftSize := 0
    if cur.l != nil && cur.l.l != nil {
        leftLeftSize = cur.l.l.size
    } else {
        leftLeftSize = 0
    }
    leftRightSize := 0
    if cur.l != nil && cur.l.r != nil {
        leftRightSize = cur.l.r.size
    }
    rightSize := 0
    if cur.r != nil {
        rightSize = cur.r.size
    }
    rightLeftSize := 0
    if cur.r != nil && cur.r.l != nil {
        rightLeftSize = cur.r.l.size
    }
    rightRightSize := 0
    if cur.r != nil && cur.r.r != nil {
        rightRightSize = cur.r.r.size
    }
    if leftLeftSize > rightSize {
        cur = this.rightRotate(cur)
        cur.r = this.maintain(cur.r)
        cur = this.maintain(cur)
    } else if leftRightSize > rightSize {
        cur.l = this.leftRotate(cur.l)
        cur = this.rightRotate(cur)
        cur.l = this.maintain(cur.l)
        cur.r = this.maintain(cur.r)
        cur = this.maintain(cur)
    } else if rightRightSize > leftSize {
        cur = this.leftRotate(cur)
        cur.l = this.maintain(cur.l)
        cur = this.maintain(cur)
    } else if rightLeftSize > leftSize {
        cur.r = this.rightRotate(cur.r)
        cur = this.leftRotate(cur)
        cur.l = this.maintain(cur.l)
        cur.r = this.maintain(cur.r)
        cur = this.maintain(cur)
    }
    return cur
}

func (this *SBTree) insert0(root *SBTNode, index int, cur *SBTNode) *SBTNode {
    if root == nil {
        return cur
    }
    root.size++
    leftAndHeadSize := 0
    if root.l != nil {
        leftAndHeadSize = root.l.size + 1
    } else {
        leftAndHeadSize = 1
    }
    if index < leftAndHeadSize {
        root.l = this.insert0(root.l, index, cur)
    } else {
        root.r = this.insert0(root.r, index-leftAndHeadSize, cur)
    }
    root = this.maintain(root)
    return root
}

func (this *SBTree) get0(root *SBTNode, index int) *SBTNode {
    leftSize := twoSelectOne(root.l != nil, root.l.size, 0)
    if index < leftSize {
        return this.get0(root.l, index)
    } else if index == leftSize {
        return root
    } else {
        return this.get0(root.r, index-leftSize-1)
    }
}

func (this *SBTree) process(head *SBTNode, indexes *[]int) {
    if head == nil {
        return
    }
    this.process(head.l, indexes)
    //indexes.addLast(head.value)
    *indexes = append(*indexes, head.value)
    this.process(head.r, indexes)
}

func (this *SBTree) insert(index, value int) {
    cur := NewSBTNode(value)
    if this.root == nil {
        this.root = cur
    } else {
        if index <= this.root.size {
            this.root = this.insert0(this.root, index, cur)
        }
    }
}

func (this *SBTree) get(index int) int {
    ans := this.get0(this.root, index)
    return ans.value
}

func (this *SBTree) allIndexes() *[]int {
    //LinkedList<Integer> indexes = new LinkedList<>();
    indexes := make([]int, 0)
    this.process(this.root, &indexes)
    return &indexes
}

执行结果如下:
图片


左神java代码

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-12-15 18:33:00  更:2021-12-15 18:34:28 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 16:26:57-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码