range模块
range模块
维护区间的添加合并,与区间的删除拆分成多个区间
通过treeMap[HTML_REMOVED]维护一个区间,
通过floorKey()获得小于指定key最大的一个区间
class RangeModule {
//通过TreeMap维护区间
TreeMap<Integer,Integer> treeMap;
public RangeModule() {
treeMap=new TreeMap<Integer,Integer>();
}
public void addRange(int left, int right) {
//获得小于left最大区间 小于right最大区间
Integer l1=treeMap.floorKey(left);
Integer l2=treeMap.floorKey(right);
//添加可能合并区间
int new_left=(l1==null||treeMap.get(l1)<left)? left:l1;
int new_right=(l2==null||treeMap.get(l2)<right)? right:treeMap.get(l2);
//将新区间元素删除
treeMap.subMap(new_left,true,new_right,false).clear();
treeMap.put(new_left,new_right);
}
public boolean queryRange(int left, int right) {
Integer l1=treeMap.floorKey(left);//能够包含左端点最大元素
if (l1 == null) {
return false;
}
return treeMap.get(l1)>=right;
}
public void removeRange(int left, int right) {
//删除某一个区间,可能会增加新的区间
Integer l1=treeMap.floorKey(left);Integer l2=treeMap.floorKey(right);
//从右往左 因为l2可能等于l1,对应的一个区间
if(l2!=null&&treeMap.get(l2)>right){
treeMap.put(right,treeMap.get(l2));
}
if (l1 != null && treeMap.get(l1) > left) {
treeMap.put(l1,left);
}
//将中间区间删除
treeMap.subMap(left,true,right,false).clear();
}
}
设计餐盘栈
餐盘栈
通过优先队列维护第一个不满的栈下标,对应的小根堆
通过优先队列维护第一个不空的栈下标,对应的大根堆
class DinnerPlates {
//定义优先队列
int maxv=200000;
int[][] stack;
int[] stack_p;
PriorityQueue<Integer> notEmpty;
PriorityQueue<Integer> notFull;
int capacity;
int index1;
public DinnerPlates(int capacity) {
this.capacity=capacity;
notEmpty=new PriorityQueue<Integer>((a,b)->b-a);
notFull=new PriorityQueue<Integer>((a,b)->a-b);//添加时,获得第一个不满的栈,从左往右
stack=new int[maxv+1][capacity+1];
stack_p=new int[maxv+1];
//初始化
notFull.offer(0);
index1=1;
}
public void push(int val) {
//notFull可能为null
if(notFull.isEmpty()){
//创建一个新的位置
notFull.add(index1++);
}
//添加位置
int index=notFull.peek();
int size=stack_p[index];//当前index栈元素个数
if(size==0){
notEmpty.add(index);
}
stack[index][size]=val;
stack_p[index]++;
//添加之后,如果满了
if(stack_p[index]==capacity){
notFull.poll();
}
}
public int pop() {
int index=-1;
int size=0;
while (!notEmpty.isEmpty()) {
index=notEmpty.peek();
if((size=stack_p[index])==0){
notEmpty.poll();
}else{
break;
}
}
//第一个notEmpty元素
if(notEmpty.isEmpty()){
return -1;
}else{
if(size==capacity){
notFull.add(index);
}
stack_p[index]--;
if(stack_p[index]==0){
notEmpty.poll();
}
return stack[index][size-1];
}
}
public int popAtStack(int index) {
int size=stack_p[index];
if(size==0){
return -1;
}else{
stack_p[index]--;
if(size==capacity){
notFull.add(index);
}
return stack[index][size-1];
}
}
}
最后k个数的乘积
最后k个数的乘积
通过前缀积的方式进行维护最后的k个元素的积;对于0的情况,直接通过将对应的之前的元素之间删除即可
class ProductOfNumbers {
int N=40010;
//定义数组
int[] nums;
int len=0;
int[] prefix;
public ProductOfNumbers() {
nums=new int[N];
nums[0]=1;
}
public void add(int num) {
if(num==0){
len=0;
}else{
nums[++len]=num;
nums[len]*=nums[len-1];
}
}
public int getProduct(int k) {
if(k>len){
return 0;
}else{
return nums[len]/nums[len-k];
}
}
}
通过数组模拟浏览器的back forword操作
class BrowserHistory {
List<String> nums=new ArrayList<String>();
int idx=1;
int length=1;
public BrowserHistory(String homepage) {
nums.add("");
nums.add(homepage);
}
public void visit(String url) {
nums.add(++idx,url);//将后面的进行覆盖
length=idx;
}
public String back(int steps) {
if(steps>=idx){
idx=1;
return nums.get(idx);
}
idx-=steps;
return nums.get(idx);
}
public String forward(int steps) {
if(steps>length-idx){
idx=length;
return nums.get(idx);
}
idx+=steps;
return nums.get(idx);
}
}
设计可以在前中后进行pop push操作的队列
class FrontMiddleBackQueue {
//如果只是对头尾元素进行修改,直接通过数组模拟即可,
//对中间元素进行修改,通过链表
class ListNode{
int val;
ListNode next;
public ListNode(int val){
this.val=val;
}
public ListNode(int val,ListNode next){
this.val=val;
this.next=next;
}
}
int size=0;//当前队列元素个数
ListNode dummy;
public FrontMiddleBackQueue() {
dummy=new ListNode(0);
}
//获取中间元素
public ListNode getMid(ListNode head){
ListNode slow=head;
ListNode fast=head;
while(fast.next!=null&&fast.next.next!=null){
slow=slow.next;
fast=fast.next.next;
}
return slow;
}
//获取队尾元素节点
public ListNode getTail(ListNode head){
ListNode cur=head;
while(cur.next!=null){
cur=cur.next;
}
return cur;
}
public void pushFront(int val) {
ListNode newNode=new ListNode(val);
newNode.next=dummy.next;
dummy.next=newNode;
}
public void pushMiddle(int val) {
ListNode mid=getMid(dummy);
ListNode newNode=new ListNode(val);
newNode.next=mid.next;
mid.next=newNode;
}
public void pushBack(int val) {
ListNode cur=getTail(dummy);
ListNode newNode=new ListNode(val);
cur.next=newNode;
}
public int popFront() {
if(dummy.next==null){
return -1;
}
int res=dummy.next.val;
dummy.next=dummy.next.next;
return res;
}
//获取中间结点的前一个结点
public ListNode getMidPre(ListNode head){
ListNode dummy=new ListNode(0,head);
ListNode slow=dummy;
ListNode fast=dummy;
while(fast.next!=null&&fast.next.next!=null){
slow=slow.next;
fast=fast.next.next;
}
return slow;
}
public int popMiddle() {
if(dummy.next==null){
return -1;
}
ListNode midPre=getMidPre(dummy);
if(midPre==null||midPre.next==null){
return -1;
}
int res=midPre.next.val;
midPre.next=midPre.next.next;
return res;
}
//获取倒数第二个节点
public ListNode getTail01(ListNode head){
ListNode cur=head;
while(cur.next!=null&&cur.next.next!=null){
cur=cur.next;
}
return cur;
}
public int popBack() {
ListNode cur=getTail01(dummy);
if(cur==null||cur.next==null){
return -1;
}
int res=cur.next.val;
cur.next=null;
return res;
}
}
设计双端队列 通过数组模拟双端队列
class MyCircularDeque {
//通过数组模拟双端队列
int[] queue;
int headIndex;
int count;int capacity;
public MyCircularDeque(int k) {
this.queue=new int[k];
this.count=0;
this.headIndex=0;
this.capacity=k;
}
public boolean insertFront(int value) {
if(count==capacity){
return false;
}
headIndex=(headIndex-1+capacity)%capacity;
queue[headIndex]=value;
count++;
return true;
}
public boolean insertLast(int value) {
if(count==capacity){
return false;
}
queue[(headIndex+count)%capacity]=value;
count++;
return true;
}
public boolean deleteFront() {
if(count==0){
return false;
}
headIndex=(headIndex+1)%capacity;
count--;
return true;
}
public boolean deleteLast() {
if(count==0){
return false;
}
count--;
return true;
}
public int getFront() {
if(count==0){
return -1;
}
return queue[headIndex];
}
public int getRear() {
if(count==0){
return -1;
}
return queue[(headIndex+count-1)%capacity];
}
public boolean isEmpty() {
return count==0;
}
public boolean isFull() {
return count==capacity;
}
}
设计循环队列 通过数组模拟循环队列
class MyCircularQueue {
//通过数组模拟循环队列
int[] queue;
int headIndex;
int count;
int capacity;
public MyCircularQueue(int k) {
this.queue=new int[k];
this.headIndex=0;
this.count=0;
this.capacity=k;
}
public boolean enQueue(int value) {
//判断是否已经超过capacity
if(count>=capacity){
return false;
}
//插入位置
int tail=(headIndex+count)%capacity;
queue[tail]=value
count++;
return true;
}
public boolean deQueue() {
//找到新队首位置
if(count==0){
return false;
}
headIndex=(headIndex+1)%capacity;
count--;
return true;
}
public int Front() {
if(count==0){
return -1;
}
return queue[headIndex];
}
public int Rear() {
if(count==0){
return -1;
}
return queue[(headIndex+count-1)%capacity];
}
public boolean isEmpty() {
return count==0;
}
public boolean isFull() {
return count==capacity;
}
}
设计推特
class Twitter {
Map<Integer,Integer> time;
int timeCnt;
//每一个用户只需要维护10条记录
int recentMax;
//每一个用户有对应的字自己的消息集合,通过链表进行维护LinkedList
//每一个用户都有关注的用户,关注的用户只需要维护对应的用户id 通过set维护
//userid:{Linkedlist:set}
class Node{
LinkedList<Integer> message;
Set<Integer> followId;
public Node(LinkedList<Integer> message,Set<Integer> followId){
this.message=message;
this.followId=followId;
}
}
Map<Integer,Node> user;
public Twitter() {
time=new HashMap<Integer, Integer>();
user=new HashMap<Integer,Node>();
timeCnt=0;
recentMax=10;
}
public void postTweet(int userId, int tweetId) {
//将对应的消息添加进userId,同时维护时间
if(!user.containsKey(userId)){
init(userId);
}
if(user.get(userId).message.size()==recentMax){
user.get(userId).message.remove(recentMax-1);
}
user.get(userId).message.addFirst(tweetId);
time.put(tweetId,timeCnt++);
}
public List<Integer> getNewsFeed(int userId) {
//将所有的用户的消息进行排序归并 归并的依据是发布的时间,所以通过hash维护每一条消息的发布时间即可
//将当前用户的所有消息取出
if(!user.containsKey(userId)){
init(userId);
}
LinkedList<Integer> ans = user.get(userId).message;
//对于当前用户的所有的关注用户
for (Integer id : user.get(userId).followId) {
if(id==userId){
continue;
}
LinkedList<Integer> followMessage = user.get(id).message;
LinkedList<Integer> res=new LinkedList<>();
int i=0,j=0;
while(i<ans.size()&&j<followMessage.size()){
if(time.get(ans.get(i))< time.get(followMessage.get(j))){
res.addLast(followMessage.get(j++));
}else{
res.addLast(ans.get(i++));
}
//如果已经达到recentMax
if(res.size()==recentMax){
break;//不需要进行当前后续归并
}
}
//将剩下的归并
while(i<ans.size()&&res.size()<recentMax){
res.addLast(ans.get(i++));
}
while(j<followMessage.size()&&res.size()<recentMax){
res.addLast(followMessage.get(j++));
}
ans=new LinkedList<>(res);
}
return ans;
}
public void init(int userId){
user.put(userId,new Node(new LinkedList<Integer>(),new HashSet<>()));
}
public void follow(int followerId, int followeeId) {
//需要在对应的用户hash中创建维护两个用户
if(!user.containsKey(followerId)){
init(followerId);
}
if(!user.containsKey(followeeId)){
init(followeeId);
}
//对应的followerId用户的 followid添加关注的用户
user.get(followerId).followId.add(followeeId);
}
public void unfollow(int followerId, int followeeId) {
//将对应的
user.get(followerId).followId.remove(followeeId);
}
}
/**
* Your Twitter object will be instantiated and called as such:
* Twitter obj = new Twitter();
* obj.postTweet(userId,tweetId);
* List<Integer> param_2 = obj.getNewsFeed(userId);
* obj.follow(followerId,followeeId);
* obj.unfollow(followerId,followeeId);
*/
最大频率栈
最大频率栈
Map[HTML_REMOVED] 维护每一个元素出现的次数
Map[HTML_REMOVED]>每一个频率对应的元素
class FreqStack {
Map<Integer,Integer> freq=new HashMap<Integer,Integer>();
Map<Integer,Stack<Integer>> group=new HashMap<Integer,Stack<Integer>>();
public FreqStack() {
}
int maxfreq=0;
public void push(int val) {
//最大频率是一个连续数
freq.put(val,freq.getOrDefault(val,0)+1);
int f=freq.get(val);
if(freq.get(val)>maxfreq){
maxfreq=freq.get(val);
}
if(group.containsKey(f)){
Stack<Integer> stack=group.get(f);
stack.push(val);
group.put(f,stack);
}else{
Stack<Integer> stack=new Stack<Integer>();
stack.push(val);
group.put(f,stack);
}
}
public int pop() {
Stack<Integer> stack=group.get(maxfreq);
int res=stack.pop();
freq.put(res,freq.get(res)-1);
if(stack.isEmpty()){
maxfreq--;
}
return res;
}
}
/**
* Your FreqStack object will be instantiated and called as such:
* FreqStack obj = new FreqStack();
* obj.push(val);
* int param_2 = obj.pop();
*/