template
js
js
// 常用的模版；
// listNode
class ListNode {
constructor(val, next) {
this.val = val;
this.next = next || null;
}
}
// console.log(new ListNode(1))
// TreeNode
class TreeNode {
constructor(val, leftChild, rightChild) {
this.val = val;
this.left = leftChild || null;
this.right = rightChild || null;
}
}
// console.log(new TreeNode(1))
// heap: 默认是小根堆，只用使用add, peek, size, poll，即可；
/**
* example1:
var x = new FastPriorityQueue();
x.add(1);
x.add(0);
x.add(5);
x.add(4);
x.add(3);
x.peek(); // should return 0, leaves x unchanged
x.size; // should return 5, leaves x unchanged
while(!x.isEmpty()) {
console.log(x.poll());
} // will print 0 1 3 4 5
x.trim(); // (optional) optimizes memory usage
example2:
var x = new FastPriorityQueue(function(a, b) {
return a > b;
});
x.add(1);
x.add(0);
x.add(5);
x.add(4);
x.add(3);
while (!x.isEmpty()) {
console.log(x.poll());
} // will print 5 4 3 1 0
*/
// the provided comparator function should take a, b and return *true* when a < b
function FastPriorityQueue(comparator) {
const defaultcomparator = function (a, b) {
return a < b;
};
if (!(this instanceof FastPriorityQueue)) return new FastPriorityQueue(comparator);
this.array = [];
this.size = 0;
this.compare = comparator || defaultcomparator;
}
// copy the priority queue into another, and return it. Queue items are shallow-copied.
// Runs in `O(n)` time.
FastPriorityQueue.prototype.clone = function () {
var fpq = new FastPriorityQueue(this.compare);
fpq.size = this.size;
fpq.array = this.array.slice(0, this.size);
return fpq;
};
// Add an element into the queue
// runs in O(log n) time
FastPriorityQueue.prototype.add = function (myval) {
var i = this.size;
this.array[this.size] = myval;
this.size += 1;
var p;
var ap;
while (i > 0) {
p = (i - 1) >> 1;
ap = this.array[p];
if (!this.compare(myval, ap)) {
break;
}
this.array[i] = ap;
i = p;
}
this.array[i] = myval;
};
// replace the content of the heap by provided array and "heapify it"
FastPriorityQueue.prototype.heapify = function (arr) {
this.array = arr;
this.size = arr.length;
var i;
for (i = this.size >> 1; i >= 0; i--) {
this._percolateDown(i);
}
};
// for internal use
FastPriorityQueue.prototype._percolateUp = function (i, force) {
var myval = this.array[i];
var p;
var ap;
while (i > 0) {
p = (i - 1) >> 1;
ap = this.array[p];
// force will skip the compare
if (!force && !this.compare(myval, ap)) {
break;
}
this.array[i] = ap;
i = p;
}
this.array[i] = myval;
};
// for internal use
FastPriorityQueue.prototype._percolateDown = function (i) {
var size = this.size;
var hsize = this.size >>> 1;
var ai = this.array[i];
var l;
var r;
var bestc;
while (i < hsize) {
l = (i << 1) + 1;
r = l + 1;
bestc = this.array[l];
if (r < size) {
if (this.compare(this.array[r], bestc)) {
l = r;
bestc = this.array[r];
}
}
if (!this.compare(bestc, ai)) {
break;
}
this.array[i] = bestc;
i = l;
}
this.array[i] = ai;
};
// internal
// _removeAt(index) will remove the item at the given index from the queue,
// retaining balance. returns the removed item, or undefined if nothing is removed.
FastPriorityQueue.prototype._removeAt = function (index) {
if (index > this.size - 1 || index < 0) return undefined;
// impl1:
//this.array.splice(index, 1);
//this.heapify(this.array);
// impl2:
this._percolateUp(index, true);
return this.poll();
};
// remove(myval) will remove an item matching the provided value from the
// queue, checked for equality by using the queue's comparator.
// return true if removed, false otherwise.
FastPriorityQueue.prototype.remove = function (myval) {
for (var i = 0; i < this.size; i++) {
if (!this.compare(this.array[i], myval) && !this.compare(myval, this.array[i])) {
// items match, comparator returns false both ways, remove item
this._removeAt(i);
return true;
}
}
return false;
};
// removeOne(callback) will execute the callback function for each item of the queue
// and will remove the first item for which the callback will return true.
// return the removed item, or undefined if nothing is removed.
FastPriorityQueue.prototype.removeOne = function (callback) {
if (typeof callback !== "function") {
return undefined;
}
for (var i = 0; i < this.size; i++) {
if (callback(this.array[i])) {
return this._removeAt(i);
}
}
};
// remove(callback[, limit]) will execute the callback function for each item of
// the queue and will remove each item for which the callback returns true, up to
// a max limit of removed items if specified or no limit if unspecified.
// return an array containing the removed items.
// The callback function should be a pure function.
FastPriorityQueue.prototype.removeMany = function (callback, limit) {
// Skip unnecessary processing for edge cases
if (typeof callback !== "function" || this.size < 1) {
return [];
}
limit = limit ? Math.min(limit, this.size) : this.size;
// Prepare the results container to hold up to the results limit
var resultSize = 0;
var result = new Array(limit);
// Prepare a temporary array to hold items we'll traverse through and need to keep
var tmpSize = 0;
var tmp = new Array(this.size);
while (resultSize < limit && !this.isEmpty()) {
// Dequeue items into either the results or our temporary array
var item = this.poll();
if (callback(item)) {
result[resultSize++] = item;
} else {
tmp[tmpSize++] = item;
}
}
// Update the result array with the exact number of results
result.length = resultSize;
// Re-add all the items we can keep
var i = 0;
while (i < tmpSize) {
this.add(tmp[i++]);
}
return result;
};
// Look at the top of the queue (one of the smallest elements) without removing it
// executes in constant time
//
// Calling peek on an empty priority queue returns
// the "undefined" value.
// https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/undefined
//
FastPriorityQueue.prototype.peek = function () {
if (this.size == 0) return undefined;
return this.array[0];
};
// remove the element on top of the heap (one of the smallest elements)
// runs in logarithmic time
//
// If the priority queue is empty, the function returns the
// "undefined" value.
// https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/undefined
//
// For long-running and large priority queues, or priority queues
// storing large objects, you may want to call the trim function
// at strategic times to recover allocated memory.
FastPriorityQueue.prototype.poll = function () {
if (this.size == 0) return undefined;
var ans = this.array[0];
if (this.size > 1) {
this.array[0] = this.array[--this.size];
this._percolateDown(0);
} else {
this.size -= 1;
}
return ans;
};
// This function adds the provided value to the heap, while removing
// and returning one of the smallest elements (like poll). The size of the queue
// thus remains unchanged.
FastPriorityQueue.prototype.replaceTop = function (myval) {
if (this.size == 0) return undefined;
var ans = this.array[0];
this.array[0] = myval;
this._percolateDown(0);
return ans;
};
// recover unused memory (for long-running priority queues)
FastPriorityQueue.prototype.trim = function () {
this.array = this.array.slice(0, this.size);
};
// Check whether the heap is empty
FastPriorityQueue.prototype.isEmpty = function () {
return this.size === 0;
};
// iterate over the items in order, pass a callback that receives (item, index) as args.
// TODO once we transpile, uncomment
// if (Symbol && Symbol.iterator) {
// FastPriorityQueue.prototype[Symbol.iterator] = function*() {
// if (this.isEmpty()) return;
// var fpq = this.clone();
// while (!fpq.isEmpty()) {
// yield fpq.poll();
// }
// };
// }
FastPriorityQueue.prototype.forEach = function (callback) {
if (this.isEmpty() || typeof callback != 'function') return;
var i = 0;
var fpq = this.clone();
while (!fpq.isEmpty()) {
callback(fpq.poll(), i++);
}
};
// return the k 'smallest' elements of the queue as an array,
// runs in O(k log k) time, the elements are not removed
// from the priority queue.
FastPriorityQueue.prototype.kSmallest = function (k) {
if (this.size == 0) return [];
k = Math.min(this.size, k);
var fpq = new FastPriorityQueue(this.compare);
const newSize = Math.min((k > 0 ? Math.pow(2, k - 1) : 0) + 1, this.size);
fpq.size = newSize;
fpq.array = this.array.slice(0, newSize);
var smallest = new Array(k);
for (var i = 0; i < k; i++) {
smallest[i] = fpq.poll();
}
return smallest;
}
// test:
// let queue1= new FastPriorityQueue();
// queue1.add(1);
// queue1.add(2);
// queue1.add(-1);
// console.log(queue1.peek())
// console.log(queue1.poll());
// console.log(queue1.peek())
// console.log(queue1.poll());
// console.log(queue1.peek())
// test2:
// const compareCb= (a,b)=>{
// return a.number<b.number
// }
// let queue2= new FastPriorityQueue(compareCb);
// queue2.add({
// number:100,
// name:'a',
// })
// queue2.add({
// number:101,
// name:'b',
// })
// queue2.add({
// number:200,
// name:'c',
// })
// queue2.add({
// number:10,
// name:'d',
// })
// console.log(queue2.peek())
// console.log(queue2.poll());
// console.log(queue2.peek())
// console.log(queue2.poll());
// console.log(queue2.peek())
//----------------------------------------------------------------
//----------------------------------------------------------------go
go
package main
import (
"container/heap"
"fmt"
)
type ListNode struct {
Val int
Next *ListNode
}
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// slice，api:
//map只能为slice, map, channel分配内存;
// values := [][]int{}; a := [3][4]int{{0, 1, 2, 3}, /* 第一行索引为 0 */{4, 5, 6, 7}, /* 第二行索引为 1 */{8, 9, 10, 11}, /* 第三行索引为 2 */}
// append,copy,len,[1:2];
// set,map
// map1 := map[string]string{}; delete(map1, "a"); if val, ok := map1["a"]; ok {}
// int heap;
type IntHeap []int
func (h IntHeap) Len() int { return len(h) }
//默认小根堆,大根堆类似;
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) {
// Push and Pop use pointer receivers because they modify the slice's length,
// not just its contents.
*h = append(*h, x.(int))
heap.Fix(h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
//优先队列；
// An Item is something we manage in a priority queue.
type Item struct {
value string // The value of the item; arbitrary.
priority int // The priority of the item in the queue.
// The index is needed by update and is maintained by the heap.Interface methods.
index int // The index of the item in the heap.
}
// A PriorityQueue implements heap.Interface and holds Items.
type PriorityQueue []*Item
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
// We want Pop to give us the highest, not lowest, priority so we use greater than here.
return pq[i].priority > pq[j].priority
}
func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
pq[i].index = i
pq[j].index = j
}
func (pq *PriorityQueue) Push(x interface{}) {
n := len(*pq)
item := x.(*Item)
item.index = n
*pq = append(*pq, item)
}
func (pq *PriorityQueue) Pop() interface{} {
old := *pq
n := len(old)
item := old[n-1]
item.index = -1 // for safety
*pq = old[0 : n-1]
return item
}
// update modifies the priority and value of an Item in the queue.
func (pq *PriorityQueue) update(item *Item, value string, priority int) {
item.value = value
item.priority = priority
heap.Fix(pq, item.index)
}
//------------------------------------------------------------
//--------------------示例的main函数，可以删除-------------------
func main1() {
nums := []int{1, 2, 2, 3}
// nums := []int{6, 5, 4, 4}
// nums := []int{1, 3, 2}
fmt.Println(nums)
//堆
h := &IntHeap{2, 1, 5, 100, 3, 6, 4, 5}
fmt.Println("test", h, *h)
heap.Init(h)
heap.Push(h, 3)
// heap.Fix(h, 3)
fmt.Println(h)
fmt.Printf("minimum: %d\n", (*h)[0])
for h.Len() > 0 {
fmt.Printf("%d ", heap.Pop(h))
}
//优先队列；
// Some items and their priorities.
items := map[string]int{
"banana": 3, "apple": 2, "pear": 4,
}
// Create a priority queue, put the items in it, and
// establish the priority queue (heap) invariants.
pq := make(PriorityQueue, len(items))
i := 0
for value, priority := range items {
pq[i] = &Item{
value: value,
priority: priority,
index: i,
}
i++
}
heap.Init(&pq)
// Insert a new item and then modify its priority.
item := &Item{
value: "orange",
priority: 1,
}
heap.Push(&pq, item)
pq.update(item, item.value, 5)
// Take the items out; they arrive in decreasing priority order.
for pq.Len() > 0 {
item := heap.Pop(&pq).(*Item)
fmt.Printf("%.2d:%s \n", item.priority, item.value)
}
}
// ----------------------------------------------------------------
// ----------------------------------------------------------------
func findDuplicates(nums []int) []int {
var swap func(arr[]int , k int, j int)
swap = func (arr []int, k int, j int) {
temp := arr[j]
arr[j] = arr[k]
arr[k] = temp
}
for i:= 0; i< len(nums); i++ {
for ; nums[i] != nums[nums[i]-1]; {
swap(nums, i, nums[i]-1)
}
}
// fmt.Printf("%v",nums)
ans := []int{}
for i:= 0; i< len(nums); i++ {
if(nums[i] != i+1){
ans = append(ans, nums[i])
}
}
return ans
}
func main () {
nums :=[]int{4,3,2,7,8,2,3,1}
ans := findDuplicates(nums)
fmt.Printf("%v",ans)
}