堆和前綴樹

1 堆

1.1 堆結構
  1. 堆是用數組實現的完全二叉樹結構
  2. 完全二叉樹中如果每棵樹的最大值都在頂部就是大根堆,最小值在頂部就是小根堆
  3. 堆結構的heapInsert就是插入操作,heapify是取出數組后進行堆結構調整的操作
  4. 優先級隊列結構就是堆結構
public class Heap {// 大根堆結構public static class MyMaxHeap {private int[] heap;private final int limit;private int heapSize;public MyMaxHeap(int limit) {heap = new int[limit];this.limit = limit;heapSize = 0;}public boolean isEmpty() {return heapSize == 0;}public boolean isFull() {return heapSize == limit;}public void push(int value) {if(heapSize == limit) {throw new RuntimeException("Heap is full!");}heap[heapSize] = value;heapInsert(heap, heapSize++);}public int pop() {if(heapSize == 0) {throw new RuntimeException("Heap is empty!");}int ans = heap[0];swap(heap, 0, --heapSize);heapify(heap, 0, heapSize);return ans;}private void heapify(int[] heap, int index, int heapSize) {int left = index * 2 + 1;while (left < heapSize) {int largest = left + 1 > heapSize ? left : (heap[left] > heap[left + 1] ? left : left + 1);largest = heap[largest] > heap[index] ? largest : index;if (largest == index) {return;}swap(heap, index, largest);index = largest;left = index * 2 - 1;}}private void heapInsert(int[] heap, int index) {while (heap[index] > heap[(index - 1) / 2]) {swap(heap, index, (index - 1) / 2);index = (index - 1) / 2;}}private void swap(int[] heap, int i, int j) {int temp = heap[i];heap[i] = heap[j];heap[j] = temp;}}// 參照組:暴力public static class RightMaxHeap {private int[] heap;private final int limit;private int heapSize;public RightMaxHeap(int limit) {heap = new int[limit];this.limit = limit;heapSize = 0;}public boolean isEmpty() {return heapSize == 0;}public boolean isFull() {return heapSize == limit;}public void push(int value) {if(heapSize == limit) {throw new RuntimeException("Heap is full!");}heap[heapSize++] = value;}public int pop() {if(heapSize == 0) {throw new RuntimeException("Heap is empty!");}int maxIndex = 0;for (int i = 1; i < heap.length; i++) {if(heap[maxIndex] < heap[i]) {maxIndex = i;}}int ans = heap[maxIndex];heap[maxIndex] = heap[--heapSize];return ans;}}public static void main(String[] args) {// 寫對數器驗證堆結構int value = 1000;int limit = 100;int testTimes = 1000000;for (int i = 0; i < testTimes; i++) {int curLimit = (int)(Math.random() * limit) + 1;RightMaxHeap test = new RightMaxHeap(curLimit);MyMaxHeap my = new MyMaxHeap(curLimit);int curOpTimes = (int)(Math.random() * limit);for (int j = 0; j < curOpTimes; j++) {if (my.isEmpty() != test.isEmpty()) {System.out.println("Oops!");}if (my.isFull() != test.isFull()) {System.out.println("Oops!");}if (my.isEmpty()) {int curValue = (int)(Math.random() * value);my.push(value);test.push(value);}else if (my.isFull()) {if(my.pop() != test.pop()) {System.out.println("Oops!");}}else {if(Math.random() < 0.5) {int curValue = (int)(Math.random() * value);my.push(value);test.push(value);}else {if(my.pop() != test.pop()) {System.out.println("Oops!");}}}}}System.out.println("Finish!");}
}
1.2 改進的堆結構

為什么要改進?

  • 原始堆,傳進去的東西比如Student類,我不修改這個類的任何值,用原始堆沒問題。
  • 但是要是想把傳進去的Student類修改一下,比如修改年齡或者id,那么就必須要使用改進的堆。
  • 改進的堆增加resign方法,可以在修改已經在堆里面的值之后還能形成堆結構。

改進的堆:

public class MyHeap<T> {private ArrayList<T> heap;private HashMap<T, Integer> indexMap;private int heapSize;private Comparator<? super T> comparator;public MyHeap(Comparator<? super T> comparator) {heap = new ArrayList<>();indexMap = new HashMap<>();heapSize = 0;this.comparator = comparator;}public boolean isEmpty() {return heapSize == 0;}public int getHeapSize() {return heapSize;}public void push(T value) {heap.add(value);indexMap.put(value, heapSize);heapInsert(heapSize++);}public T poll() {T ans = heap.get(0);int end = heapSize - 1;swap(0, end);heap.remove(end);indexMap.remove(ans);heapify(0, --heapSize);return ans;}public void resign(T value) {int valueIndex = indexMap.get(value);heapify(valueIndex, heapSize);heapInsert(valueIndex);}private void heapify(int index, int heapSize) {int left = index * 2 + 1;while (left < heapSize) {int largest = (left + 1 < heapSize) && (comparator.compare(heap.get(left + 1), heap.get(left)) < 0) ? left + 1 : left;largest = (comparator.compare(heap.get(largest), heap.get(index)) < 0) ? largest : index;if (largest == index) {return;}swap(largest, index);index = largest;left = index * 2 + 1;}}private void heapInsert(int index) {while (comparator.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {swap(index, (index - 1) / 2);index = (index - 1) / 2;}}private void swap(int i, int j) {T o1 = heap.get(i);T o2 = heap.get(j);heap.set(i, o2);heap.set(j, o1);indexMap.put(o1, j);indexMap.put(o2, i);}
}

學生類:

public class Student {private int id;private String name;private int age;private String address;public Student() {}public Student(int id, String name, int age, String address) {this.id = id;this.name = name;this.age = age;this.address = address;}/*** 獲取* @return id*/public int getId() {return id;}/*** 設置* @param id*/public void setId(int id) {this.id = id;}/*** 獲取* @return name*/public String getName() {return name;}/*** 設置* @param name*/public void setName(String name) {this.name = name;}/*** 獲取* @return age*/public int getAge() {return age;}/*** 設置* @param age*/public void setAge(int age) {this.age = age;}/*** 獲取* @return address*/public String getAddress() {return address;}/*** 設置* @param address*/public void setAddress(String address) {this.address = address;}public String toString() {return "Student{id = " + id + ", name = " + name + ", age = " + age + ", address = " + address + "}";}
}

測試:

public class test {public static void main(String[] args) {Student s1 = new Student(1, "張三", 18, "西安");Student s2 = new Student(2, "李四", 20, "重慶");Student s3 = new Student(3, "王五", 19, "成都");Student s4 = new Student(4, "趙六", 22, "深圳");Student s5 = new Student(5, "錢七", 21, "北京");MyHeap<Student> myHeap = new MyHeap<>(new Comparator<Student>() {@Overridepublic int compare(Student o1, Student o2) {return o2.getId() - o1.getId();}});myHeap.push(s1);myHeap.push(s2);myHeap.push(s3);myHeap.push(s4);myHeap.push(s5);System.out.println(myHeap.isEmpty());System.out.println(myHeap.getHeapSize());System.out.println("====================");s1.setId(15);myHeap.resign(s1);while (!myHeap.isEmpty()) {System.out.println(myHeap.poll().toString());}}
}

2 前綴樹

可以完成前綴相關的查詢

2.1 前綴樹的結構
  1. 單個字符串中的字符從前到后加到一顆多叉樹上
  2. 字符放在路上,節點上有專屬的數據項(常見的是pass和end)
  3. 所有樣本都這樣添加,如果沒有路就新建,如果有路就復用
  4. 沿途所有的經過的節點的pass值加1,每個字符串結束時來到的節點的end值加1
// Node和TrieTree結合使用,Node2和TrieTree2結合使用。
// TrieTree2只能加入小寫字符組成的字符串,有局限性
// TrieTree可以都加入
public class TrieTreeSearch {public static class Node {public int pass;public int end;public HashMap<Integer, Node> next;public Node() {pass = 0;end = 0;next = new HashMap<>();}}public static class TrieTree {private final Node root;public TrieTree() {root = new Node();}public void insert(String word) {if (word == null) {return;}Node node = root;node.pass++;char[] chars = word.toCharArray();int index = 0;for (char aChar : chars) {index = aChar;if (!node.next.containsKey(index)) {node.next.put(index, new Node());}node = node.next.get(index);node.pass++;}node.end++;}public void delete(String word) {if (search(word) != 0) {Node node = root;node.pass--;int index = 0;char[] chars = word.toCharArray();for (char aChar : chars) {index = aChar;if (node.next.containsKey(index)) {node = node.next.get(index);}node.pass--;}node.end--;}}public int search(String word) {return research(word).end;}public int prefixNum(String word) {return research(word).pass;}private Node research(String word) {if (word == null) {return new Node();}Node node = root;char[] chars = word.toCharArray();int index = 0;for (char aChar : chars) {index = aChar;if (!node.next.containsKey(index)) {return new Node();}node = node.next.get(index);}return node;}}public static class Node2 {public int pass;public int end;public Node2[] next;public Node2() {pass = 0;end = 0;next = new Node2[26];}}public static class TrieTree2 {private final Node2 root;// 無參構造public TrieTree2() {root = new Node2();}// 添加字符串public void insert(String word) {if (word == null) {return;}char[] chars = word.toCharArray();Node2 node = root;node.pass++;int index = 0;for (char aChar : chars) {index = aChar - 'a';if (node.next[index] == null) {node.next[index] = new Node2();}node = node.next[index];node.pass++;}node.end++;}// 查找字符串有多少個public int search(String word) {if (word == null) {return 0;}char[] chars = word.toCharArray();Node2 node = root;int index = 0;for (char aChar : chars) {index = aChar - 'a';if (node.next[index] == null) {return 0;}node = node.next[index];}return node.end;}// 刪除字符串public void delete(String word) {if (search(word) != 0) {Node2 node = root;node.pass--;int index = 0;char[] chars = word.toCharArray();for (char aChar : chars) {index = aChar - 'a';if (--node.next[index].pass == 0) {node.next[index] = null;return;}node = node.next[index];}node.end--;}}// 有幾個字符串前綴是wordpublic int prefixNum(String word) {if (word == null) {return 0;}char[] chars = word.toCharArray();Node2 node = root;int index = 0;for (char aChar : chars) {index = aChar - 'a';if (node.next[index] == null) {return 0;}node = node.next[index];}return node.pass;}}public static String generateRandomString(int strLen) {char[] ans = new char[(int) (Math.random() * strLen) + 1];for (int i = 0; i < ans.length; i++) {int value = (int) (Math.random() * 26);ans[i] = (char) (value + 97);}return String.valueOf(ans);}public static String[] generateRandomString(int arrLen, int strLen) {String[] ans = new String[(int) (Math.random() * arrLen) + 1];for (int i = 0; i < ans.length; i++) {ans[i] = generateRandomString(strLen);}return ans;}// 寫對數器進行測試public static void main(String[] args) {int strLen = 20;int arrLen = 100;int testTimes = 1000000;for (int i = 0; i < testTimes; i++) {String[] strings = generateRandomString(arrLen, strLen);TrieTree my = new TrieTree();TrieTree2 test = new TrieTree2();for (String word : strings) {double decide = Math.random();if (decide < 0.25) {my.insert(word);test.insert(word);} else if (decide < 0.5) {my.delete(word);test.delete(word);} else if (decide < 0.75) {int ans1 = my.search(word);int ans2 = test.search(word);if(ans1 != ans2) {System.out.println("Oops!");}}else {int ans1 = my.prefixNum(word);int ans2 = test.prefixNum(word);if (ans1 != ans2) {System.out.println("Oops!");}}}}System.out.println("Finish!");}
}

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/167116.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/167116.shtml
英文地址,請注明出處:http://en.pswp.cn/news/167116.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

通過ros系統中websocket中發送sensor_msgs::Image數據給web端顯示(三)

通過ros系統中websocket中發送sensor_msgs::Image數據給web端顯示(三) 不使用base64編碼方式傳遞 #include <ros/ros.h> #include <signal.h> #include <sensor_msgs/Image.h> #include <message_filters/subscriber.h> #include <message_filter…

【正點原子STM32連載】第五十九章 T9拼音輸入法實驗(Julia分形)實驗 摘自【正點原子】APM32F407最小系統板使用指南

1&#xff09;實驗平臺&#xff1a;正點原子APM32F407最小系統板 2&#xff09;平臺購買地址&#xff1a;https://detail.tmall.com/item.htm?id609294757420 3&#xff09;全套實驗源碼手冊視頻下載地址&#xff1a; http://www.openedv.com/thread-340252-1-1.html## 第五十…

關于 token 和證書

關于 token 和證書 在網絡檢測中&#xff0c;Token通常是指一種特殊的令牌&#xff0c;用于在分布式系統中進行資源控制和訪問管理。Token可以用于驗證客戶端的身份、限制客戶端的訪問權限以及控制客戶端對某些資源的使用。 在網絡檢測中&#xff0c;Token通常用于以下幾個方…

uniapp IOS從打包到上架流程(詳細簡單) 原創

? 1.登入蘋果開發者網站&#xff0c;打開App Store Connect ? 2.新App的創建 點擊我的App可以進入App管理界面&#xff0c;在右上角點擊?新建App 即可創建新的App&#xff0c;如下圖&#xff1a; ? 3.app基本信息填寫 新建完App后&#xff0c;需要填寫App的基本信息&…

SOLIDWORKS 2024新功能之CAM篇

SOLIDWORKS 2024 新功能 CAM篇目錄概述 ? 附加探測周期參數 ? 反轉切割的固定循環螺紋加工 ? 包含裝配體的零件的正確進給/速度數據 ? Heidenhain 探測類型 ? 2.5 軸特征向導中島嶼的終止條件 ? 鏈接輪廓銑削操作的切入引導和切出引導參數 ? 螺紋銑削操作的最小孔…

網絡工程師眼中的網站安全:應對攻擊的綜合措施

作為一名專業的網絡工程師&#xff0c;我們深知網站面臨各種攻擊威脅的現實。在構建網站安全的同時&#xff0c;綜合運用技術手段和管理策略是至關重要的。在這篇文章中&#xff0c;我們將從網絡工程師的視角出發&#xff0c;介紹如何解決網站被攻擊的問題&#xff0c;并在其中…

飛凌嵌入式受邀參加「2023年電子工程師大會」并做主旨演講

11月23日&#xff0c;華秋電子發燒友在深圳總部舉辦了「2023年電子工程師大會暨第三屆社區年度頒獎」活動&#xff0c;邀請到了高校教授、企業創始人及高管、行業技術專家、電子工程師等眾多嘉賓到場&#xff0c;呈現并傳播了電子產業動態、最新技術、應用案例及開源硬件項目。…

C#FlaUI.UIA實現發送微信消息原理

一 準備 .NetFramework 4.8 FlaUI.UIA3 4.0.0 FlaUInspect V1.3.0 1下載FlaUInspect https://github.com/FlaUI/FlaUInspect FlaUInspect V1.3.0 百度網盤下載 2 NuGet 引用 flaUI.UIA3 4.0.0 二代碼部分 1 引用FlaUI using FlaUI.Core; using FlaUI.Core.Automatio…

安防系統智能視頻監控中出現畫面異常該如何自檢?

大家都知道&#xff0c;在當今社會&#xff0c;攝像頭無處不在&#xff0c;除了常見的生活與工作場景中&#xff0c;在一些無法人員無法長期駐點場景&#xff0c;如野生動物監測、高空作業監控、高壓電纜監控等場景&#xff0c;在這些地方安裝攝像頭就是為方便日常監控。但是由…

Odoo:行業領先的免費開源生產制造管理系統

產品生命周期管理 用 Odoo 產品數據管理解決方案加速產品開發 研究、開發和設計新產品或者重新設計現有產品是所有制造企業的活力之源&#xff0c;但很多企業的設計部門和工程部門卻完全脫離 ERP 系統。這導致工程師需要耗費大量時間來回答企業中其他部門就產品狀態、修改級別…

遞歸和動態規劃的區別

時間復雜度方面&#xff1a; 遞歸會導致指數級別的時間復雜度&#xff0c;因為它會計算許多重復的子問題。 動態規劃會存儲子問題的結果&#xff0c;來降低復雜度&#xff0c;使其變成多項式級別。 自頂向下VS自底向上 遞歸采用自頂向下的方式&#xff0c;從原問題出發&#xf…

Course1-Week2-多輸入變量的回歸問題

Course1-Week2-多輸入變量的回歸問題 文章目錄 Course1-Week2-多輸入變量的回歸問題1. 向量化和多元線性回歸1.1 多維特征1.2 向量化1.3 用于多元線性回歸的梯度下降法 2. 使梯度下降法更快收斂的技巧2.1 特征縮放2.2 判斷梯度下降是否收斂2.3 如何設置學習率 3. 特征工程3.1 選…

看圖說話:對臟讀、不可重復度、幻讀進行總結

1、臟讀 「事務B」將 id 為 1 的用戶 name 修改為“小卡”&#xff0c;事務未提交。「事務A」查詢 id 為 1 的用戶數據&#xff0c;此時 name 已為“小卡”。 2、不可重復度 「事務A」第一次讀取 id 為 1 的用戶&#xff0c;name 是 “卡卡”。「事務B」將 id 為 1 的用戶 nam…

Sectigo

隨著互聯網的普及和技術的飛速發展&#xff0c;網絡安全問題引起重視。這時&#xff0c;有一家名為Sectigo(原Comodo CA)的公司應運而生&#xff0c;致力于為企業和個人提供最先進、最可靠的網絡安全解決方案。 Sectigo(原Comodo CA) 成立于2008年&#xff0c;總部位于美國加利…

數據分析策略

文章目錄 我想對比不同完整度40%&#xff0c;50%&#xff0c;60%抽樣計算來10min的TI序列&#xff0c;它們的差異與完整率的關系&#xff0c;告訴我怎么對比即可 了解您的分析目標后&#xff0c;我可以提供一個比較不同完整度&#xff08;40%&#xff0c;50%&#xff0c;60%&am…

啟發式算法

什么是啟發式算法&#xff1f;他們都有什么特點&#xff1f; 啟發式算法是一類用于在大規模問題上尋找近似解的搜索算法。這些算法不保證找到全局最優解&#xff0c;但通常能夠在合理的時間內找到一個較好的解決方案。啟發式算法常用于解決組合優化問題&#xff0c;其中目標是…

《使用Python將Excel數據批量寫入MongoDB數據庫》

在數據分析及處理過程中&#xff0c;我們經常需要將數據寫入數據庫。而MongoDB作為一種NoSQL數據庫&#xff0c;其具有強大的可擴展性、高性能以及支持復雜查詢等特性&#xff0c;廣泛用于大規模數據存儲和分析。在這篇文章中&#xff0c;我們將使用Python編寫一個將Excel數據批…

dos 命令移到文件夾

SET GenFolder C:\Users\administered\Desktop\t2\old_file set path1C:\Users\administered\Desktop\t1\crontab_master set path2C:\Users\administered\Desktop\t2\old_file if not exist %GenFolder% ( echo %GenFolder%目錄不存在&#xff0c;已創建該目錄&#x…

Linux python安裝 虛擬環境 virtualenv,以及 git clone的 文件數據, 以及 下資源配置

根目錄創建 venvs 文件夾 sudo mkdir /venvs 進入 /venvs 目錄 cd /venvsp 創建虛擬環境&#xff0c;前提要按照 python3 安裝 的 命令 sudo apt install python3 sudo python3 -m venv 虛擬環境名 激活虛擬環境 source /venvs/zen-venv/bin/activate 安裝flask pip install fl…

探究Kafka原理-2.Kafka基本命令實操

&#x1f44f;作者簡介&#xff1a;大家好&#xff0c;我是愛吃芝士的土豆倪&#xff0c;24屆校招生Java選手&#xff0c;很高興認識大家&#x1f4d5;系列專欄&#xff1a;Spring源碼、JUC源碼、Kafka原理&#x1f525;如果感覺博主的文章還不錯的話&#xff0c;請&#x1f44…