class035 数据结构设计高频题【算法】

class035 数据结构设计高频题【算法】

算法讲解035【必备】数据结构设计高频题
在这里插入图片描述
在这里插入图片描述

code1 设计有setAll功能的哈希表

// setAll功能的哈希表
// 测试链接 : https://www.nowcoder.com/practice/7c4559f138e74ceb9ba57d76fd169967
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过

思路：带时间戳

package class035;

// setAll功能的哈希表
// 测试链接 : https://www.nowcoder.com/practice/7c4559f138e74ceb9ba57d76fd169967
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.HashMap;

public class Code01_SetAllHashMap {

	public static HashMap<Integer, int[]> map = new HashMap<>();
	public static int setAllValue;
	public static int setAllTime;
	public static int cnt;

	public static void put(int k, int v) {
		if (map.containsKey(k)) {
			int[] value = map.get(k);
			value[0] = v;
			value[1] = cnt++;
		} else {
			map.put(k, new int[] { v, cnt++ });
		}
	}

	public static void setAll(int v) {
		setAllValue = v;
		setAllTime = cnt++;
	}

	public static int get(int k) {
		if (!map.containsKey(k)) {
			return -1;
		}
		int[] value = map.get(k);
		if (value[1] > setAllTime) {
			return value[0];
		} else {
			return setAllValue;
		}
	}

	public static int n, op, a, b;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StreamTokenizer in = new StreamTokenizer(br);
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		while (in.nextToken() != StreamTokenizer.TT_EOF) {
			map.clear();
			setAllValue = 0;
			setAllTime = -1;
			cnt = 0;
			n = (int) in.nval;
			for (int i = 0; i < n; i++) {
				in.nextToken();
				op = (int) in.nval;
				if (op == 1) {
					in.nextToken();
					a = (int) in.nval;
					in.nextToken();
					b = (int) in.nval;
					put(a, b);
				} else if (op == 2) {
					in.nextToken();
					a = (int) in.nval;
					out.println(get(a));
				} else {
					in.nextToken();
					a = (int) in.nval;
					setAll(a);
				}
			}
		}
		out.flush();
		out.close();
		br.close();
	}

}

code2 146. LRU 缓存

// 实现LRU结构
// 测试链接 : https://leetcode.cn/problems/lru-cache/

思路：HashMap+双向链表（新增结点到尾部，删除头部的结点，将结点移到尾部）

package class035;

import java.util.HashMap;

// 实现LRU结构
public class Code02_LRU {

	// 测试链接 : https://leetcode.cn/problems/lru-cache/
	class LRUCache {

		class DoubleNode {
			public int key;
			public int val;
			public DoubleNode last;
			public DoubleNode next;

			public DoubleNode(int k, int v) {
				key = k;
				val = v;
			}
		}

		class DoubleList {
			private DoubleNode head;
			private DoubleNode tail;

			public DoubleList() {
				head = null;
				tail = null;
			}

			public void addNode(DoubleNode newNode) {
				if (newNode == null) {
					return;
				}
				if (head == null) {
					head = newNode;
					tail = newNode;
				} else {
					tail.next = newNode;
					newNode.last = tail;
					tail = newNode;
				}
			}

			public void moveNodeToTail(DoubleNode node) {
				if (tail == node) {
					return;
				}
				if (head == node) {
					head = node.next;
					head.last = null;
				} else {
					node.last.next = node.next;
					node.next.last = node.last;
				}
				node.last = tail;
				node.next = null;
				tail.next = node;
				tail = node;
			}

			public DoubleNode removeHead() {
				if (head == null) {
					return null;
				}
				DoubleNode ans = head;
				if (head == tail) {
					head = null;
					tail = null;
				} else {
					head = ans.next;
					ans.next = null;
					head.last = null;
				}
				return ans;
			}

		}

		private HashMap<Integer, DoubleNode> keyNodeMap;

		private DoubleList nodeList;

		private final int capacity;

		public LRUCache(int cap) {
			keyNodeMap = new HashMap<>();
			nodeList = new DoubleList();
			capacity = cap;
		}

		public int get(int key) {
			if (keyNodeMap.containsKey(key)) {
				DoubleNode ans = keyNodeMap.get(key);
				nodeList.moveNodeToTail(ans);
				return ans.val;
			}
			return -1;
		}

		public void put(int key, int value) {
			if (keyNodeMap.containsKey(key)) {
				DoubleNode node = keyNodeMap.get(key);
				node.val = value;
				nodeList.moveNodeToTail(node);
			} else {
				if (keyNodeMap.size() == capacity) {
					keyNodeMap.remove(nodeList.removeHead().key);
				}
				DoubleNode newNode = new DoubleNode(key, value);
				keyNodeMap.put(key, newNode);
				nodeList.addNode(newNode);
			}
		}

	}

}

code3 380. O(1) 时间插入、删除和获取随机元素

// 插入、删除和获取随机元素O(1)时间的结构
// 测试链接 : https://leetcode.cn/problems/insert-delete-getrandom-o1/

思路：HashMap+动态数组 remove()方法使用最后一个元素填补中间的空缺

package class035;

import java.util.ArrayList;
import java.util.HashMap;

// 插入、删除和获取随机元素O(1)时间的结构
public class Code03_InsertDeleteRandom {

	// 测试链接 : https://leetcode.cn/problems/insert-delete-getrandom-o1/
	class RandomizedSet {

		public HashMap<Integer, Integer> map;

		public ArrayList<Integer> arr;

		public RandomizedSet() {
			map = new HashMap<>();
			arr = new ArrayList<>();
		}

		public boolean insert(int val) {
			if (map.containsKey(val)) {
				return false;
			}
			map.put(val, arr.size());
			arr.add(val);
			return true;
		}

		public boolean remove(int val) {
			if (!map.containsKey(val)) {
				return false;
			}
			int valIndex = map.get(val);
			int endValue = arr.get(arr.size() - 1);
			map.put(endValue, valIndex);
			arr.set(valIndex, endValue);
			map.remove(val);
			arr.remove(arr.size() - 1);
			return true;
		}

		public int getRandom() {
			return arr.get((int) (Math.random() * arr.size()));
		}

	}

}

code4 381. O(1) 时间插入、删除和获取随机元素 - 允许重复

// 插入、删除和获取随机元素O(1)时间且允许有重复数字的结构
// 测试链接 :
// https://leetcode.cn/problems/insert-delete-getrandom-o1-duplicates-allowed/

思路：HashMap<Integer,HashSet< Integer>>+动态数组 remove()方法使用最后一个元素填补中间的空缺

package class035;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

// 插入、删除和获取随机元素O(1)时间且允许有重复数字的结构
public class Code04_InsertDeleteRandomDuplicatesAllowed {

	// 测试链接 :
	// https://leetcode.cn/problems/insert-delete-getrandom-o1-duplicates-allowed/
	class RandomizedCollection {

		public HashMap<Integer, HashSet<Integer>> map;

		public ArrayList<Integer> arr;

		public RandomizedCollection() {
			map = new HashMap<>();
			arr = new ArrayList<>();
		}

		public boolean insert(int val) {
			arr.add(val);
			HashSet<Integer> set = map.getOrDefault(val, new HashSet<Integer>());
			set.add(arr.size() - 1);
			map.put(val, set);
			return set.size() == 1;
		}

		public boolean remove(int val) {
			if (!map.containsKey(val)) {
				return false;
			}
			HashSet<Integer> valSet = map.get(val);
			int valAnyIndex = valSet.iterator().next();
			int endValue = arr.get(arr.size() - 1);
			if (val == endValue) {
				valSet.remove(arr.size() - 1);
			} else {
				HashSet<Integer> endValueSet = map.get(endValue);
				endValueSet.add(valAnyIndex);
				arr.set(valAnyIndex, endValue);
				endValueSet.remove(arr.size() - 1);
				valSet.remove(valAnyIndex);
			}
			arr.remove(arr.size() - 1);
			if (valSet.isEmpty()) {
				map.remove(val);
			}
			return true;
		}

		public int getRandom() {
			return arr.get((int) (Math.random() * arr.size()));
		}
	}

}

code5 295. 数据流的中位数

// 快速获得数据流的中位数的结构
// 测试链接 : https://leetcode.cn/problems/find-median-from-data-stream/

思路：大根堆+小根堆

package class035;

import java.util.PriorityQueue;

// 快速获得数据流的中位数的结构
public class Code05_MedianFinder {

	// 测试链接 : https://leetcode.cn/problems/find-median-from-data-stream/
	class MedianFinder {

		private PriorityQueue<Integer> maxHeap;

		private PriorityQueue<Integer> minHeap;

		public MedianFinder() {
			maxHeap = new PriorityQueue<>((a, b) -> b - a);
			minHeap = new PriorityQueue<>((a, b) -> a - b);
		}

		public void addNum(int num) {
			if (maxHeap.isEmpty() || maxHeap.peek() >= num) {
				maxHeap.add(num);
			} else {
				minHeap.add(num);
			}
			balance();
		}

		public double findMedian() {
			if (maxHeap.size() == minHeap.size()) {
				return (double) (maxHeap.peek() + minHeap.peek()) / 2;
			} else {
				return maxHeap.size() > minHeap.size() ? maxHeap.peek() : minHeap.peek();
			}
		}

		private void balance() {
			if (Math.abs(maxHeap.size() - minHeap.size()) == 2) {
				if (maxHeap.size() > minHeap.size()) {
					minHeap.add(maxHeap.poll());
				} else {
					maxHeap.add(minHeap.poll());
				}
			}
		}

	}

}

code6 895. 最大频率栈

// 最大频率栈
// 测试链接 : https://leetcode.cn/problems/maximum-frequency-stack/

思路：多级链表+HashMap

package class035;

import java.util.ArrayList;
import java.util.HashMap;

// 最大频率栈
public class Code06_MaximumFrequencyStack {

	// 测试链接 : https://leetcode.cn/problems/maximum-frequency-stack/
	class FreqStack {

		// 出现的最大次数
		private int topTimes;
		// 每层节点
		private HashMap<Integer, ArrayList<Integer>> cntValues = new HashMap<>();
		// 每一个数出现了几次
		private HashMap<Integer, Integer> valueTimes = new HashMap<>();

		public void push(int val) {
			valueTimes.put(val, valueTimes.getOrDefault(val, 0) + 1);
			int curTopTimes = valueTimes.get(val);
			if (!cntValues.containsKey(curTopTimes)) {
				cntValues.put(curTopTimes, new ArrayList<>());
			}
			ArrayList<Integer> curTimeValues = cntValues.get(curTopTimes);
			curTimeValues.add(val);
			topTimes = Math.max(topTimes, curTopTimes);
		}

		public int pop() {
			ArrayList<Integer> topTimeValues = cntValues.get(topTimes);
			int ans = topTimeValues.remove(topTimeValues.size() - 1);
			if (topTimeValues.size() == 0) {
				cntValues.remove(topTimes--);
			}
			int times = valueTimes.get(ans);
			if (times == 1) {
				valueTimes.remove(ans);
			} else {
				valueTimes.put(ans, times - 1);
			}
			return ans;
		}
	}

}

code7 432. 全 O(1) 的数据结构

// 全O(1)的数据结构
// 测试链接 : https://leetcode.cn/problems/all-oone-data-structure/

思路：HashMap+双向链表

package class035;

import java.util.HashMap;
import java.util.HashSet;

// 全O(1)的数据结构
public class Code07_AllO1 {

	// 测试链接 : https://leetcode.cn/problems/all-oone-data-structure/
	class AllOne {

		class Bucket {
			public HashSet<String> set;
			public int cnt;
			public Bucket last;
			public Bucket next;

			public Bucket(String s, int c) {
				set = new HashSet<>();
				set.add(s);
				cnt = c;
			}
		}

		private void insert(Bucket cur, Bucket pos) {
			cur.next.last = pos;
			pos.next = cur.next;
			cur.next = pos;
			pos.last = cur;
		}

		private void remove(Bucket cur) {
			cur.last.next = cur.next;
			cur.next.last = cur.last;
		}

		Bucket head;

		Bucket tail;

		HashMap<String, Bucket> map;

		public AllOne() {
			head = new Bucket("", 0);
			tail = new Bucket("", Integer.MAX_VALUE);
			head.next = tail;
			tail.last = head;
			map = new HashMap<>();
		}

		public void inc(String key) {
			if (!map.containsKey(key)) {
				if (head.next.cnt == 1) {
					map.put(key, head.next);
					head.next.set.add(key);
				} else {
					Bucket newBucket = new Bucket(key, 1);
					map.put(key, newBucket);
					insert(head, newBucket);
				}
			} else {
				Bucket bucket = map.get(key);
				if (bucket.next.cnt == bucket.cnt + 1) {
					map.put(key, bucket.next);
					bucket.next.set.add(key);
				} else {
					Bucket newBucket = new Bucket(key, bucket.cnt + 1);
					map.put(key, newBucket);
					insert(bucket, newBucket);
				}
				bucket.set.remove(key);
				if (bucket.set.isEmpty()) {
					remove(bucket);
				}
			}
		}

		public void dec(String key) {
			Bucket bucket = map.get(key);
			if (bucket.cnt == 1) {
				map.remove(key);
			} else {
				if (bucket.last.cnt == bucket.cnt - 1) {
					map.put(key, bucket.last);
					bucket.last.set.add(key);
				} else {
					Bucket newBucket = new Bucket(key, bucket.cnt - 1);
					map.put(key, newBucket);
					insert(bucket.last, newBucket);
				}
			}
			bucket.set.remove(key);
			if (bucket.set.isEmpty()) {
				remove(bucket);
			}
		}

		public String getMaxKey() {
			return tail.last.set.iterator().next();
		}

		public String getMinKey() {
			return head.next.set.iterator().next();
		}

	}

}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/222348.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

class050 双指针技巧与相关题目【算法】

class050 双指针技巧与相关题目【算法】

class050 双指针技巧与相关题目【算法】 算法讲解050【必备】双指针技巧与相关题目 code1 922. 按奇偶排序数组 II // 按奇偶排序数组II // 给定一个非负整数数组 nums。nums 中一半整数是奇数 &#xff0c;一半整数是偶数 // 对数组进行排序&#xff0c;以便当 nums[i] 为…
阅读更多...
Isaac Sim教程04 Isaac Sim的高级使用

Isaac Sim教程04 Isaac Sim的高级使用

Isaac Sim 高级使用 版权信息 Copyright 2023 Herman YeAuromix. All rights reserved.This course and all of its associated content, including but not limited to text, images, videos, and any other materials, are protected by copyright law. The author holds…
阅读更多...
EI论文复现：考虑源荷不确定性的含风电-电力系统低碳调度程序代码！

EI论文复现：考虑源荷不确定性的含风电-电力系统低碳调度程序代码！

本程序参考论文《考虑源荷不确定性的含风电-电力系统低碳调度》&#xff0c;程序中考虑了源荷的不确定性&#xff0c;引入模糊机会约束规划来求解不确定性模型&#xff0c;对做相关研究方向的小伙伴非常有帮助&#xff0c;程序算例丰富、注释清晰、干货满满&#xff0c;下面对文…
阅读更多...
JAVA刷题之数组的总结和思路分享

JAVA刷题之数组的总结和思路分享

꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好&#xff0c;我是xiaoxie.希望你看完之后,有不足之处请多多谅解&#xff0c;让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN …
阅读更多...
Amazon Code Whisperer 的正式使用，全新 AI 代码工具等你发现！（内附详细安装步骤图解）

Amazon Code Whisperer 的正式使用，全新 AI 代码工具等你发现！（内附详细安装步骤图解）

文章作者&#xff1a;稚始稚终 关于 Code Whisperer Code Whisperer&#xff0c;亚马逊推出的实时 AI 编程助手&#xff0c;是一项基于机器学习的服务&#xff0c;它可以分析开发者在集成开发环境&#xff08;IDE&#xff09;中的注释和代码&#xff0c;并根据其内容生成多种代…
阅读更多...
【LeetCode:2646. 最小化旅行的价格总和 | DFS + DP】

【LeetCode:2646. 最小化旅行的价格总和 | DFS + DP】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…
阅读更多...
【开发问题解决方法记录】04.dian 权限表单优化

【开发问题解决方法记录】04.dian 权限表单优化

权限表单优化方向&#xff1a; 父级权限从晶点权限表获取做成列表下拉选中 权限名称和编码一行两列 页面id从 select * from APEX_APPLICATION_PAGES where APPLICATION_ID304; 中获取 【遇到的问题1】 DG可以获取到页面信息&#xff0c;但是表和应用程序无法获取到 【问…
阅读更多...
机器学习-逻辑回归

机器学习-逻辑回归

一、引言 逻辑回归&#xff08;Logistic Regression&#xff09;是一种广泛应用于分类问题的监督学习算法。尽管名字中含有“回归”二字&#xff0c;但这并不意味着它用于解决回归问题。相反&#xff0c;逻辑回归专注于解决二元或多元分类问题&#xff0c;如邮件是垃圾邮件还是…
阅读更多...
TSMaster添加注释

TSMaster添加注释

当我们在回放报文的时候&#xff0c;会遇到一些需要添加注释&#xff0c;有以下几种办法进行注释 报文运行时手动注释 在图形窗口回放报文&#xff0c;正在抓取报文或者进行报文回放。工具栏选择添加实时注释&#xff0c;这种办法需要手速快&#xff0c;而且时间对的不是很准…
阅读更多...
App内存优化

App内存优化

一、内存优化介绍 1.背景介绍 内存是大问题但缺乏关注压实骆驼的最后一个稻草&#xff08;堆栈溢出&#xff09; 2.内存问题 内存抖动&#xff1a;锯齿状、GC导致卡顿内存泄露&#xff1a;可用内存减少、频繁GC内存溢出&#xff1a;OOM&#xff0c;程序异常 二、优化工具选…
阅读更多...
jvs智能bi新增：数据集添加sql自定义节点、添加websocket任务进度动态展示等等

jvs智能bi新增：数据集添加sql自定义节点、添加websocket任务进度动态展示等等

智能bi更新功能 新增: 1.数据集添加sql自定义输入节点&#xff0c;支持mysql Oracle数据源&#xff1b; 用户可以从这些数据源中获取数据&#xff0c;并通过SQL语句对数据进行自定义处理和分析。可以帮助用户更加灵活地处理和分析数据&#xff0c;满足各种个性化的需求。 2.…
阅读更多...
识别低效io引起的free buffer waits

识别低效io引起的free buffer waits

产生事发时间段的awr报告 Top 5 wait events 这里重点关注&#xff1a; 1.free buffer waits 2.enq_HW-contention 3.enq:tx-row lock contention enq:HW-contention属于水位线的争用&#xff0c;已经透过alter table allocate extent&#xff0c;提前分配空间,这里不做讨论 …
阅读更多...
spring boot+sharding jdbc实现读写分离

spring boot+sharding jdbc实现读写分离

shigen日更文章的博客写手&#xff0c;擅长Java、python、vue、shell等编程语言和各种应用程序、脚本的开发。记录成长&#xff0c;分享认知&#xff0c;留住感动。 在shigen之前的文章中&#xff0c;写到了Springboot mybatis plus实现读写分离&#xff0c;没有sharding-jdbc的…
阅读更多...
怎么修改按SHIFT键关闭Caps Lock功能？

怎么修改按SHIFT键关闭Caps Lock功能？

win11 Step 1> 设置-> 时间和语言Step 2> 输入Step 3> 高级键盘设置Step 4> 语言栏选项 -> 高级设置-> 按CAPS LOCK键 Step 1> 设置-> 时间和语言 Step 2> 输入 Step 3> 高级键盘设置 Step 4> 语言栏选项 -> 高级设置-> 按CAPS LOCK…
阅读更多...
同调群的维度 和 同调群的秩

同调群的维度 和 同调群的秩

同调群的维度是指同调群中非零元素的最小阶数。与线性代数中对向量空间的维度的理解类似。对同调群&#xff0c;k维同调群的维度是k。 同调群的秩是指同调群中的自由部分的维度。同调群通常包含自由部分和挠部分。同调群的秩是指同调群中自由部分的维度。对同调群&#xff0c;…
阅读更多...
python+django教师下乡支教岗位分配管理系统pycharm毕业设计项目推荐

python+django教师下乡支教岗位分配管理系统pycharm毕业设计项目推荐

本课题使用Python语言进行开发。代码层面的操作主要在PyCharm中进行&#xff0c;将系统所使用到的表以及数据存储到MySQL数据库中&#xff0c;方便对数据进行操作本课题基于WEB的开发平台 1.运行环境&#xff1a;python3.7/python3.8。 2.IDE环境&#xff1a;pycharmmysql5.7; …
阅读更多...
多线程（初阶八：计时器Timer）

多线程（初阶八：计时器Timer）

目录 一、标准库中的计时器 1、计时器的概念 2、计时器的简单介绍 二、模拟实现一个计时器 1、思路 &#xff08;1&#xff09;计数器中要存放任务的数据结构 &#xff08;2&#xff09;存放优先级队列中的类型&#xff1a;自定义任务类MyTimerTask &#xff08;3&…
阅读更多...
用python找到音乐数据的位置，并实现音乐下载

用python找到音乐数据的位置，并实现音乐下载

嗨喽~大家好呀&#xff0c;这里是魔王呐 ❤ ~! python更多源码/资料/解答/教程等 点击此处跳转文末名片免费获取 需求分析: 有什么需求要实现? 这些需求可以用什么技术实现? 找到音乐数据的位置, 分析 不同音乐的链接有何规律?https://lx-sycdn.kuwo.cn/b784688662c82db8…
阅读更多...
RocketMq环境搭建

RocketMq环境搭建

目录 MQ作用 RocketMQ背景 MQ对比 RocketMQ环境搭建 搭建dashboard可视化界面 MQ作用 异步解耦削峰 RocketMQ背景 ​ RocketMQ是阿里巴巴开源的一个消息中间件&#xff0c;在阿里内部历经了双十一等很多高并发场景的考验&#xff0c;能够处理亿万级别的消息。2016年开源…
阅读更多...
Win10无法删除文件需要管理员权限的解决方法

Win10无法删除文件需要管理员权限的解决方法

在Win10电脑中&#xff0c;用户想要删除不需要的文件&#xff0c;却收到了需要管理员权限才能删除&#xff0c;导致用户自己无法将文件删除掉。下面小编给大家带来Win10系统删除文件需要权限的解决方法&#xff0c;解决后用户在Win10电脑上就能删除任意文件了。 Win10无法删除文…
阅读更多...
最新文章

Copyright @ 2022~2023