从0学习算法-第4天

做人如果没有梦想,那和咸鱼有什么区别。

用栈实现队列

使用栈实现队列的下列操作:

push(x)--将一个元素放入队列的尾部

pop()--从队列首部移除元素

peek()--返回队列首部的元素

empty()--返回队列是否为空

//思路:队列先进先出,栈后进先出,所以一个栈肯定不行,我们需要一个输入栈和一个输出栈
class MyQueue{
	Stack<Integer> stackIn;//负责进栈
	Stack<Integer> stackOut;//负责出栈

	public MyQueue(){
		stackIn = new Stack()<>;//
		stackOut = new Stack()<>;
	}
  	public void push(int x){
	  stackIn.push(x);
	}
  	public int pop(){
	  dumpstackIn();
	  return stackOut.pop();
	}
  public int peek(){
	dumpstackIn();
	return stackOut.peek();
  }
  public boolean empty(){
	return stackIn.isEmpty()&&stackOut.isEmpty();
  }
  //如果stackIn不为空,那么将stackIn中的元素放入stackOut中
  private void dumpstackIn(){
	if(!stackOut.isEmpty()) return;
	while(!stackIn.isEmpty()){
	  stackOut.push(stackIn.pop());
	}
  }
}

用队列实现栈

使用队列实现栈的下列操作

push(x)--元素x入栈

pop()--移除栈顶元素

top()--获取栈顶元素

empty()--返回栈是否为空

//使用一个队列来模拟栈
class Mystack{
	Queue<Integer> queue;//使用队列来实现栈
  public Mystack{
	queue = new LinkedList<>();
  }
  public void rePosition(){
	int size=queue.size();//获取队列的大小
	size--;//
	while(size-->0){
	  queue.add(queue.poll());//循环将队首元素移动到队尾，直到队首元素变为栈顶元素
	}
	
  public void push(int x){
	queue.add(x);//入栈操作,将元素添加到队尾
  }
  public int pop(){
	rePosition();//调整队列顺序,使得队首元素为栈顶元素
	int result=queue.poll();//获取队首元素
	queue.add(result);//将队首元素再次添加
	return result;//返回队首元素
  }
  public boolean empty(){
  return queue.isEmpty();//判断栈是否为空
  }
  
}

20. 有效的括号

力扣题目链接(opens new window)

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

class Solution {
    public boolean isValid(String s) {
        Deque<Character> deque = new LinkedList<>();
        char ch;
        for (int i = 0; i < s.length(); i++) {
            ch = s.charAt(i);
            //碰到左括号，就把相应的右括号入栈
            if (ch == '(') {
                deque.push(')');
            }else if (ch == '{') {
                deque.push('}');
            }else if (ch == '[') {
                deque.push(']');
			//当遇到右括号时，会判断栈顶元素是否与当前右括号匹配。如果匹配，则将栈顶元素出栈；如果不匹配，则			返回false
            } else if (deque.isEmpty() || deque.peek() != ch) {
                return false;
            }else {//如果是右括号判断和栈顶元素匹配
                deque.pop(); //出栈
            }
        }
        //最后判断栈是否为空
        return deque.isEmpty();
    }
}

1047. 删除字符串中的所有相邻重复项

力扣题目链接(opens new window)

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入："abbaca"
输出："ca"
解释：例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

class Solution {
    public String removeDuplicates(String s) {
        Deque<Character> stack =new LinkedList<>();
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            if(stack.isEmpty()||stack.peek()!=ch){
                stack.push(ch);
            }else{
                stack.pop();
            }
        }
        String str="";
        //剩余元素即为不重复元素
        while(!stack.isEmpty()){
            str=stack.pop()+str;
        }
        return str;
    }
}

239. 滑动窗口最大值

力扣题目链接(opens new window)

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //利用单调队列
        ArrayDeque<Integer> deque=new ArrayDeque<>();
        int n=nums.length;
        int[] res=new int[n-k+1];
        int idx=0;
        for(int i=0;i<n;i++){
            //i为nums下标,是要在[i-k+1,i]中选到最大值,只要保证两点
            //1.队列头节点需要在[i-k+1,i]范围内,不符合则要弹出
            while(!deque.isEmpty()&&deque.peek()<i-k+1){
                deque.poll();//头部移除元素
            }
            //2.既然是单调,就要保证每次放进去的数字要比末尾的都大,否则也弹出
            while(!deque.isEmpty()&&nums[deque.peekLast()]<nums[i]){//队列尾部元素小于nums[i]时,从队列尾部移除元素
                deque.pollLast();//从尾部移除
            }
            deque.offer(i);
            //因为单调,当i增长到符合第一个k范围的时候,每滑动一步将队列的头节点放入结果就行
            if(i>=k-1){
                res[idx++]=nums[deque.peek()];
            }
        }
        return res;
    }
}

347.前 K 个高频元素

力扣题目链接(opens new window)

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

//思路:1.统计出现频率高的元素
	 //2.对1步骤排序
	 	//3.按顺序返回k个
//想到优先级队列
class Solution {
    //解法1：基于大顶堆实现
    public int[] topKFrequent1(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>(); //key为数组元素值，val为对应出现次数
        for(int num:nums){
            map.put(num,map.getOrDefault(num,0)+1); //将当前元素num的出现次数加1，并将其存储在map中
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2)->pair2[1]-pair1[1]); //创建一个优先队列pq，用于存储二元组(num,cnt)，其中num表示元素值，cnt表示元素值在数组中的出现次数。优先队列按照二元组的第二个元素（即出现次数）从大到小进行排序，这样队头的元素就是出现次数最多的元素。
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){ //遍历map中的每个条目
            pq.add(new int[]{entry.getKey(),entry.getValue()}); //将当前条目的键和值封装成一个二元组，并将其添加到优先队列pq中
        }
        int[] ans = new int[k]; //创建一个长度为k的整数数组ans，用于存储结果
        for(int i=0;i<k;i++){ //循环k次，从优先队列pq中依次弹出k个元素
            ans[i] = pq.poll()[0]; //弹出优先队列pq的队头元素，并将其第一个元素（即元素值）存储在ans数组的第i个位置
        }
        return ans; //返回结果数组ans，其中包含了出现频率最高的k个元素
    }
}