java栈队列优先队列算法

java栈队列优先队列算法

栈

public class Solution {
	//将做方向的括号放入栈中
    Stack stack = new Stack();
    for( int i = 0 ; i < s.length() ; i ++ )
        if( s.charAt(i) == '(' || s.charAt(i) == '{' || s.charAt(i) == '[')
            stack.push(s.charAt(i));	
	//遇到右方向的括号，取出栈中的元素，判断是否匹配
        else{

            if( stack.size() == 0 )
                return false;

            Character c = stack.pop();

            Character match;
            if( s.charAt(i) == ')' )
                match = '(';
            else if( s.charAt(i) == ']' )
                match = '[';
            else{
                assert s.charAt(i) == '}';
                match = '{';
            }

            if(c != match)
                return false;
        }

    if( stack.size() != 0 )
        return false;

    return true;
}	
}

队列

队列

import java.util.LinkedList;

public class Solution {
    LinkedList queue = new LinkedList();
    queue.addLast(new Pair(n, 0));

    boolean[] visited = new boolean[n+1];
    visited[n] = true;

    while(!queue.isEmpty()){
        Pair front = queue.removeFirst();
        int num = front.getKey();
        int step = front.getValue();
    	//判断是否到达了0，根据到达0判断经过的路径
        if(num == 0)
            return step;
    	//查看到达某一路径是否还有剩余的步数
        for(int i = 1 ; num - i*i >= 0 ; i ++)
            if(!visited[num - i * i]){
                queue.addLast(new Pair(num - i * i, step + 1));
                visited[num - i * i] = true;
            }
    }
    
}

优先队列根据个位数排序

    public static void main(String[] args) {

        // 默认的PriorityQueue, 底层是最小堆
        PriorityQueue pq = new PriorityQueue();

        for(int i = 0 ; i < 10 ; i ++){
            int num = (int)(Math.random() * 100);
            pq.add(num);
            System.out.println("insert " + num + " in priority queue.");
        }

        while (!pq.isEmpty())
            System.out.print(pq.poll() + " ");

        System.out.println();
        System.out.println();


        // 使用lambda表达式，创建底层是最大堆的PriorityQueue
        PriorityQueue pq2 = new PriorityQueue(10, (a, b) -> b - a);

        for(int i = 0 ; i < 10 ; i ++){
            int num = (int)(Math.random() * 100);
            pq2.add(num);
            System.out.println("insert " + num + " in priority queue.");
        }

        while (!pq2.isEmpty())
            System.out.print(pq2.poll() + " ");

        System.out.println();
        System.out.println();


        // 使用自定义的Comparator，创建个性化的PriorityQueue
        // 注意：也可以使用lambda表达式。在这里只是为了演示PriorityQueue的不同用法
        // 同理，上一个例子也可以使用自定义的Comparator的方式完成
        class myCmp implements Comparator{
            @Override
            public int compare(Integer a, Integer b){
                if(a%10 != b%10)
                    return a%10 - b%10;
                return a - b;
            }
        }
        PriorityQueue pq3 = new PriorityQueue(10, new myCmp());

        for(int i = 0 ; i < 10 ; i ++){
            int num = (int)(Math.random() * 100);
            pq3.add(num);
            System.out.println("insert " + num + " in priority queue.");
        }

        while (!pq3.isEmpty())
            System.out.print(pq3.poll() + " ");

        System.out.println();
        System.out.println();
    }

import java.util.LinkedList;

public class Solution {
//存入数据的同时记录频率
    if(k  freq.size())
        throw new IllegalArgumentException("k should be less than the number of unique numbers in nums");

//对所有的数据记录频率之后，对频率进行排序，记录频率前N的数据
    private class PairComparator implements Comparator{

        @Override
        public int compare(Pair p1, Pair p2){
            if(p1.getKey() != p2.getKey())
                return p1.getKey() - p2.getKey();
            return p1.getValue() - p2.getValue();
        }
    }	
	
    // 扫描freq,维护当前出现频率最高的k个元素
    // 在优先队列中,按照频率排序,所以数据对是 (频率,元素) 的形式
    PriorityQueue pq = new PriorityQueue(new PairComparator());
    for(Integer num: freq.keySet()){
        int numFreq = freq.get(num);
        if(pq.size() == k){
            if(numFreq > pq.peek().getKey()){
                pq.poll();
                pq.add(new Pair(numFreq, num));
            }
        }
        else
            pq.add(new Pair(numFreq, num));
    }

    ArrayList res = new ArrayList();
    while(!pq.isEmpty())
        res.add(pq.poll().getValue());

    return res;
}

}