225. Implement Stack using Queues
Posted Updated LeetCode / Easy2 minutes read (About 366 words)

225. Implement Stack using Queues

Question

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

  • void push(int x) Pushes element x to the top of the stack.

  • int pop() Removes the element on the top of the stack and returns it.

  • int top() Returns the element on the top of the stack.

  • boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

  • You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
  • Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue’s standard operations.

Solution

用两个队列实现栈。一个队列存放压入的元素。

push()

将当前元素加入到第一个队列。

top() & pop()

当需要挤出或者查看栈顶时，第一个队列只保留一个元素，其余元素加入第二个队列。最后一个元素就是栈顶。当第一个队列为空时，交换第一个队列与第二个队列。

empty()

返回两个队列是否均为空。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class MyStack {
    Queue<Integer> q1;
    Queue<Integer> q2;
    public MyStack() {
        q1 = new LinkedList<Integer>();
        q2 = new LinkedList<Integer>();
        
    }
    
    public void push(int x) {
        q1.add(x);
    }
    
    public int pop() {
        move();
        return q1.poll();
    }
    
    public int top() {
        move();
        return q1.peek();
    }
    
    public boolean empty() {
        return q1.isEmpty() && q2.isEmpty();
    }
    
    private void move(){
        if(q1.isEmpty()){
            Queue<Integer> temp = q1;
            q1 = q2;
            q2 = temp;
        }
        while(q1.size() != 1){
            q2.add(q1.poll());
        }
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */
Posted Updated a few seconds read (About 39 words)

Distance - 几种距离

欧几里得距离

曼哈顿距离（方格距离）

切比雪夫距离（棋盘距离）

汉明距离（信号距离）

973. K Closest Points to Origin
Posted Updated LeetCode / Medium / 复习2 minutes read (About 260 words)

973. K Closest Points to Origin

Question

Given an array of points where points[i] = [x<sub>i</sub>, y<sub>i</sub>] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x<sub>1</sub><span> </span>- x<sub>2</sub>)<sup>2</sup><span> </span>+ (y<sub>1</sub><span> </span>- y<sub>2</sub>)<sup>2</sup>).

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

Solution

此题可以采用快速排序的思想。可以在O(n)时间复杂度里完成排序。

Solution 2

优先级队列，根据每个点距离的平方排序。时间复杂度O(nlogk)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[][] kClosest(int[][] points, int k) {
        int[][] ret = new int[k][2];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> squaredDistance(a) - squaredDistance(b));
        for(int[] point : points){
            pq.add(point);
        }
        for(int i = 0; i < k; i++){
            ret[i] = pq.poll();
        }
        return ret;
    }
    
    private int squaredDistance(int[] point){
        int x = point[0], y = point[1];
        return x * x + y * y;
    }
}

Solution 3

直接排序。时间复杂度为O(nlogn)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int[][] kClosest(int[][] points, int k) {
        int[][] ret = new int[k][2];
        Arrays.sort(points, (a, b) -> squaredDistance(a) - squaredDistance(b));
        for(int i = 0; i < k; i++){
            ret[i] = points[i];
        }
        return ret;
    }
    
    private int squaredDistance(int[] point){
        int x = point[0], y = point[1];
        return x * x + y * y;
    }
}
451. Sort Characters By Frequency
Posted Updated LeetCode / Mediuma minute read (About 203 words)

451. Sort Characters By Frequency

Question

Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.

Return the sorted string. If there are multiple answers, return any of them.

Solution

哈希表记录字符出现的频率。然后将其添加到优先队列中。
最后根据优先级队列的顺序，加入每个字符对应的哈希表中记录的字符数。
理论上也可以用数组记录频率，但是问题中字符较复杂故未采用。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public String frequencySort(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        PriorityQueue<Character> pq = new PriorityQueue<>((a,b) -> map.get(b) - map.get(a));
        StringBuffer sb = new StringBuffer();
        for(char c : s.toCharArray()){
            map.put(c, map.getOrDefault(c, 0)+1);
        }
        for(char c : map.keySet()){
            pq.add(c);
        }
        while(!pq.isEmpty()){
            char c = pq.poll();
            for(int i = 0; i < map.get(c); i++){
                sb.append(c);
            }
        }
        return sb.toString();
    }
}
215. Kth Largest Element in an Array
Posted Updated LeetCode / Mediuma minute read (About 149 words)

215. Kth Largest Element in an Array

Problem

Given an integer array nums and an integer k, return the k<sup>th</sup> largest element in the array.

Note that it is the k<sup>th</sup> largest element in the sorted order, not the k<sup>th</sup> distinct element.

Solution

直接排序数组，返回倒数第k个值。

Code

1
2
3
4
5
6
class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

Solution 2

采用优先级队列，将所有元素加入队列，采用倒序比较器。
挤出前k-1个值，然后返回第k个值。

Code

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for(int num : nums){
            pq.add(num);
        }
        for(int i = 0; i < k-1; i++){
            pq.poll();
        }
        return pq.peek();
    }
}
Follow

Recents

Archives

Links

×