Kotlin手动实现一个最简单的哈希表

参考的是《数据结构(C语言版)》上256页左右的哈希表的介绍,用了最简单的直接寻址法 + 链地址法。 用的是Kotlin。 package main.kotlin /** * 手动实现简单的hash表 * 简单的数组 +链表 (无红黑树) * 要求哈希函数可配置(被自我否决,太复杂了啦),这次就先做比较简单的 直接定址法 + 链地址法 * * @Date 2021-10-16. * @author Johnathan Lin */ data class Node( val key: Int, //key var value: Int, //value var next: Node? //如果hash值重复了,则用头插法放进去 ) fun main() { // hash表,这次可为空 val size = 100 val hashArr: Array<Node?> = Array(size) { null } //插入 假设插入key 8 value 24 println("插入key 8 value 24") set(hashArr, size, 8, 24) { k, s -> k % s } println("插入key 108 value 32") set(hashArr, size, 108, 32) { k, s -> k % s } var v = get(hashArr, size, 108) { k, s -> k % s } println("读取key为108: $v") println("删除key 108") remove(hashArr, size, 108) { k, s -> k % s } v = get(hashArr, size, 108) { k, s -> k % s } println("读取key为108: $v") v = get(hashArr, size, 8) { k, s -> k % s } println("读取key为8: $v") } /** * @param hashFunc 哈希函数 param1:key param2:size */ fun get(hashArr: Array<Node?...

October 16, 2021 · 3 min · JohnathanLin

Kotlin实现二叉堆、大顶堆、优先级队列

参考了 https://www.bilibili.com/video/BV11t4y1r79L https://blog.csdn.net/qq_19782019/article/details/78301832 他们已经写的足够好了。我最近都在用Kotlin编程开发,我尝试用Kotlin实现了大顶堆,并且作为手动实现的优先级队列,通过了Leetcode 347。 package main.kotlin /** * 二叉堆(大顶堆、优先级队列) * * @Date 2021-10-14. * @author Johnathan Lin */ data class MaxHeap<T : Comparable<T>>( val arr: Array<T>, var size: Int ) { //将无序的数组构建一个二叉堆 fun makeHeap() { for (i in (size - 1) downTo 0) { heapDown(i) } } //向二叉堆中加入元素 fun addItem(value: T) { //TODO 添加的边界还未考虑 val newIndex = size++ arr[newIndex] = value heapUp(newIndex) } //移除堆顶元素 fun removeItem(): T { //TODO 删除的边界还未考虑 val removeValue = arr[0] val lastValue = arr[size - 1] // println("lastValue:$lastValue") arr[0] = lastValue size-- heapDown(0) return removeValue } fun printHeap() { for (i in 0....

October 14, 2021 · 4 min · JohnathanLin

[算法]分布估计算法 - 一种求解多维背包问题的混合分布估计算法_王凌

作业要求实现《一种求解多维背包问题的混合分布估计算法_王凌》 百度学术路径 写这篇文章主要是因为,这论文的数据集实在是找不到,但最后我还是找到了。 CSDN下载地址 然后我还是实现了该论文的算法,虽然感觉还是有错,而且结果并不是很好看,但我就是要厚脸皮发出来给大家嘲笑。 我实现的是SENTO2.DAT,最佳值为8722。 package eda2; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.File; import java.io.FileInputStream; import java.io.FileWriter; import java.io.InputStreamReader; import java.io.IOException; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.HashMap; import java.util.HashSet; import java.util.List; import java.util.Map; import java.util.Random; import java.util.Set; import java.util.Map.Entry; public class eda { private int N;//最佳个体数 private int s;//搜索时的 private int Y;//初始步长 private int M;//种群规模 private double alpha;//学习因子 private int n;//物体个数 private double []p;//概率向量 private int[][] population; private int[][] popValue; private int bagNum;//维度(背包数) private int []bagCapacity; //核重 private int [][]r;//物体在不同维度上的价值 第一个 维度 第二个 维度值 private int []weigh; private int []popWeigh; private Map<Integer,Integer> collection; //10 2 50 40 0....

December 18, 2017 · 5 min · JohnathanLin