牛客NC79 丑数【中等 堆、优先级队列 Java,Go,PHP Go和PHP中我自己实现了优先级队列】
题目
题目链接：
https://www.nowcoder.com/practice/6aa9e04fc3794f68acf8778237ba065b
思路
注意： 数据范围：0≤n≤2000， 2000肯定到不了，最多到1690，相同题目链接：https://www.lintcode.com/problem/4。
思路，从小到大依次把丑数列出来,存入优先级队列
参考答案Java
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param index int整型
* @return int整型
*/
public int GetUglyNumber_Solution (int index) {
//n最多到1690，题目给的到不了2000，
if(index ==0) return 0;
PriorityQueue<Long> pq = new PriorityQueue<>();
for (long i = 1; i <= 0x7fffffff ; i *= 2) {
for (long j = i; j <= 0x7fffffff ; j *= 3) {
for (long k = j; k <= 0x7fffffff; k *= 5) {
pq.add(k);
}
}
}
while (index > 1) {
pq.poll();
index--;
}
long s = pq.poll();
return (int)s;
}
}
参考答案Go
package main
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param index int整型
* @return int整型
*/
func GetUglyNumber_Solution(index int) int {
//Go的优先级队列，或者叫堆，需要自己实现
if index ==0 {
return 0
}
h := newHeap02(true)
for i := 1; i <= 0x7fffffff; i *= 2 {
for j := i; j <= 0x7fffffff; j *= 3 {
for k := j; k <= 0x7fffffff; k *= 5 {
h.add(k)
}
}
}
for index > 1 { //升序优先级队列中要保留一个
h.remove()
index--
}
return h.remove()
}
type Heap02 struct { //heap的定义
Array []int
Size int
DefaultSize int
Asc bool //true: 升序 false 降序
}
func newHeap02(asc bool) Heap02 {
return Heap02{Array: make([]int, 10), Size: 0, DefaultSize: 10, Asc: asc}
}
func (h *Heap02) ensureSize(length int) { //扩容代码
oldsize := len(h.Array)
if oldsize >= length {
return
}
//新增容量为旧容量的1.5倍
newSize := oldsize + oldsize>>1
newArr := make([]int, newSize)
for i := 0; i < h.Size; i++ {
newArr[i] = h.Array[i]
}
h.Array = newArr
}
func (h *Heap02) add(val int) { //新增
oldSize := h.Size
h.ensureSize(oldSize + 1)
h.Array[oldSize] = val
h.Size++
//fmt.Println(h.Array, " is idx ")
h.siftUp(oldSize)
}
func (h *Heap02) siftUp(idx int) { //上滤,大顶堆
cur := h.Array[idx]
for idx > 0 {
//fmt.Println(idx, " is idx ")
pindex := (idx - 1) / 2
parent := h.Array[pindex]
if !h.Asc {
if parent >= cur {
break
}
} else {
if parent <= cur {
break
}
}
h.Array[idx] = parent
idx = pindex
}
h.Array[idx] = cur
//fmt.Println(idx, " is idx ")
}
// 删除：二叉堆的删除是删除堆顶元素
// 思路：最后一个元素代替堆顶元素，删除最后一个元素，然后下窜
func (h *Heap02) remove() int {
last := h.Size - 1
root := h.Array[0]
h.Array[0] = h.Array[last]
//arr[last] 不用管了，因为长度要减1，减1后，最后一个元素也不存在了
h.siftDown(0)
h.Size--
return root
}
func (h Heap02) siftDown(idx int) {
half := h.Size >> 1
root := h.Array[0]
for idx < half {
// idx:只有左节点，或者左右子节点都有
pos := (idx << 1) + 1
child := h.Array[pos]
right := pos + 1
if !h.Asc {
if right < h.Size && h.Array[right] > h.Array[pos] {
pos = right
child = h.Array[right]
}
if root > child {
break
}
} else {
if right < h.Size && h.Array[right] < h.Array[pos] {
pos = right
child = h.Array[right]
}
if root < child {
break
}
}
h.Array[idx] = child
idx = pos
}
h.Array[idx] = root
}
func (h Heap02) get() int { //获取堆顶元素
if h.Size == 0 {
const INT_MAX = int(^uint(0) >> 1)
return ^INT_MAX
}
return h.Array[0]
}
// 删除堆顶的元素的同时，插入一个新元素
func (h Heap02) replace(ele int) int { //替换堆顶元素
const INT_MAX = int(^uint(0) >> 1)
root := ^INT_MAX
if h.Size == 0 {
h.Array[0] = ele
h.Size++
} else {
root = h.Array[0]
h.Array[0] = ele
h.siftDown(0)
}
return root
}
参考答案PHP
<?php
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param index int整型
* @return int整型
*/
function GetUglyNumber_Solution( $index )
{
if($index ==0) return 0;
//PHP中的优先级队列，或者叫堆，需要自己实现
$h = new Heap();
for($i=1;$i<=0x7fffffff;$i*=2){
for($j=$i;$j<=0x7fffffff;$j*=3){
for($k=$j;$k<0x7fffffff;$k*=5){
$h->add($k);
}
}
}
while ($index>1) { //保留一个
$h->remove();
$index--;
}
return $h->remove();
}
class Heap //堆
{
public $arr = array();
public $size = 0;
public $defaultSize = 10;
public $asc = true; //true: 小顶堆 false：大顶堆
public function __construct()
{
for ($i = 0; $i < $this->defaultSize; $i++) {
$this->arr[$i] = 0;
}
}
public function ensureSize($len) //扩容代码
{
$oldSize = count($this->arr);
if ($oldSize >= $len) return;
$newSize = $oldSize + $oldSize >> 1;
$arr1 = array();
for ($i = 0; $i < $newSize; $i++) {
$arr1[$i] = 0;
if ($i < $oldSize) {
$arr1[$i] = $this->arr[$i];
}
}
$this->arr = $arr1;
}
public function add($val)
{
$oldSize = $this->size;
$this->ensureSize($oldSize + 1);
$this->arr[$oldSize] = $val;
$this->size++;
$this->siftUp($oldSize);
}
public function siftUp($idx)
{ //上滤
$root = $this->arr[$idx];
while ($idx > 0) {
$pindex = ($idx - 1) / 2;
$parent = $this->arr[$pindex];
if (!$this->asc) {
if ($parent >= $root) break;
} else {
if ($parent <= $root) break;
}
$this->arr[$idx] = $parent;
$idx = $pindex;
}
$this->arr[$idx] = $root;
}
//删除：二叉堆的删除是删除堆顶元素
//思路：最后一个元素代替堆顶元素，删除最后一个元素，然后下窜
public function remove()
{
$root = $this->arr[0];
$this->arr[0] = $this->arr[$this->size - 1];
//arr[last] 不用管了，因为长度要减1，减1后，最后一个元素也不存在了
$this->siftDown(0);
$this->size--;
return $root;
}
public function siftDown($idx)
{
$half = $this->size >> 1;
$root = $this->arr[0];
while ($idx < $half) {
//index:只有左子节点，或者左右子节点都有
$childIndex = ($idx << 1) + 1;
$right = $childIndex + 1;
$child = $this->arr[$childIndex];
if (!$this->asc) {
if ($right < $this->size && $this->arr[$right] > $this->arr[$childIndex]) {
$childIndex = $right;
$child = $this->arr[$right];
}
if ($child < $root) break;
} else {
if ($right < $this->size && $this->arr[$right] < $this->arr[$childIndex]) {
$childIndex = $right;
$child = $this->arr[$right];
}
if ($child > $root) break;
}
$this->arr[$idx] = $child;
$idx = $childIndex;
}
$this->arr[$idx] = $root;
}
//获取堆顶元素
public function get()
{
if ($this->size == 0) return 2147483647;
return $this->arr[0];
}
//替换堆顶元素
//删除堆顶的元素的同时，插入一个新元素
public function replace($ele)
{
$root = 2147483647;
if ($this->size == 0) {
$this->arr[0] = $ele;
$this->size++;
} else {
$root = $this->arr[0];
$this->arr[0] = $ele;
$this->siftDown(0);
}
return $root;
}
}
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
THE END
二维码