Wednesday, June 5, 2019

LeetCode [451] Sort Characters By Frequency

Given a string, sort it in decreasing order based on the frequency of characters.
Example 1:
Input:
"tree"

Output:
"eert"

Explanation:
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.
Example 2:
Input:
"cccaaa"

Output:
"cccaaa"

Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.
Example 3:
Input:
"Aabb"

Output:
"bbAa"

Explanation:
"bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.
 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) {
        map<char, int> mp;
        for(auto c:s){
            mp[c]++;
        }
        priority_queue<pair<int, char>> pq;
        for(auto h:mp){
            pq.push(make_pair(h.second, h.first));
        }

        string r;
        while(!pq.empty()){
            r.append(pq.top().first, pq.top().second);
            pq.pop();
        }
        return r;
    }
};

 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
//Java, Bucket Sort
    class Solution {
        public String frequencySort(String s) {
            int n = s.length();
            char[] chars = s.toCharArray();
            Map<Character, Integer> freq = new HashMap<>();
            for(char c : chars){
                freq.put(c, freq.getOrDefault(c, 0)+1);
            }

            List<Character>[] buckets = new List[n+1];
            for(Map.Entry<Character, Integer> e : freq.entrySet()){
                char c = e.getKey();
                int cnt = e.getValue();
                if(buckets[cnt]==null){
                    buckets[cnt] = new ArrayList<>();
                }
                buckets[cnt].add(c);
            }

            StringBuilder sb = new StringBuilder();
            for(int i=n; i>0; --i){
                if(buckets[i]==null) continue;
                for(char c : buckets[i]){
                    for(int j=0; j<freq.get(c); ++j){
                        sb.append(c);
                    }
                }
            }

            return sb.toString();
        }
    }
Posted by at No comments:

LeetCode [658] Find K Closest Elements

Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.
Example 1:
Input: [1,2,3,4,5], k=4, x=3
Output: [1,2,3,4]
Example 2:
Input: [1,2,3,4,5], k=4, x=-1
Output: [1,2,3,4]
Note:
  1. The value k is positive and will always be smaller than the length of the sorted array.
  2. Length of the given array is positive and will not exceed 104
  3. Absolute value of elements in the array and x will not exceed 104
UPDATE (2017/9/19):
The arr parameter had been changed to an array of integers (instead of a list of integers). Please reload the code definition to get the latest changes.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
    int left = 0;
    int right = arr.size()-k;
    while(left<right){
        int mid = left+(right-left)/2;
        if(x-arr[mid]>arr[mid+k]-x){
            left = mid+1;
        }else{
            right = mid;
        }
    }
    auto S = arr.begin()+left;
    auto E = arr.begin()+left+k;
    
    return vector<int>(S,E);
}
};
Posted by at No comments:

Tuesday, June 4, 2019

LeetCode [895] Maximum Frequency Stack

Implement FreqStack, a class which simulates the operation of a stack-like data structure.
FreqStack has two functions:
  • push(int x), which pushes an integer x onto the stack.
  • pop(), which removes and returns the most frequent element in the stack.
    • If there is a tie for most frequent element, the element closest to the top of the stack is removed and returned.

Example 1:
Input: 
["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
Output: [null,null,null,null,null,null,null,5,7,5,4]
Explanation:
After making six .push operations, the stack is [5,7,5,7,4,5] from bottom to top.  Then:

pop() -> returns 5, as 5 is the most frequent.
The stack becomes [5,7,5,7,4].

pop() -> returns 7, as 5 and 7 is the most frequent, but 7 is closest to the top.
The stack becomes [5,7,5,4].

pop() -> returns 5.
The stack becomes [5,7,4].

pop() -> returns 4.
The stack becomes [5,7].

Note:


  • Calls to FreqStack.push(int x) will be such that 0 <= x <= 10^9.
  • It is guaranteed that FreqStack.pop() won't be called if the stack has zero elements.
  • The total number of FreqStack.push calls will not exceed 10000 in a single test case.
  • The total number of FreqStack.pop calls will not exceed 10000 in a single test case.
  • The total number of FreqStack.push and FreqStack.pop calls will not exceed 150000 across all test cases.
 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
struct Ele{
    int value;
    int index;
    int count;
    Ele(int v, int i, int c):value(v),index(i),count(c){}
};

struct Comp
{
    bool operator()(const Ele& lhs, const Ele& rhs)
    {
        if (lhs.count<rhs.count) return true;
        if (lhs.count==rhs.count) return lhs.index<rhs.index;
        return false;
    }
};

class FreqStack {
    priority_queue<Ele, vector<Ele>, Comp> pq;
    int index = 0;
    map<int, int> mp;//number, count
public:
    FreqStack() {
        
    }
    
    void push(int x) {
        Ele e(x, index++, ++mp[x]);
        pq.push(e);
    }
    
    int pop() {
        int v = pq.top().value;
        pq.pop();
        mp[v]--;
        return v;
    }
};

/**
 * Your FreqStack object will be instantiated and called as such:
 * FreqStack* obj = new FreqStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 */
Posted by at No comments:

Saturday, June 1, 2019

LeetCode [716] Max Stack

Design a max stack that supports push, pop, top, peekMax and popMax.
  1. push(x) -- Push element x onto stack.
  2. pop() -- Remove the element on top of the stack and return it.
  3. top() -- Get the element on the top.
  4. peekMax() -- Retrieve the maximum element in the stack.
  5. popMax() -- Retrieve the maximum element in the stack, and remove it. If you find more than one maximum elements, only remove the top-most one.
Example 1:
MaxStack stack = new MaxStack();
stack.push(5); 
stack.push(1);
stack.push(5);
stack.top(); -> 5
stack.popMax(); -> 5
stack.top(); -> 1
stack.peekMax(); -> 5
stack.pop(); -> 1
stack.top(); -> 5
Note:
  1. -1e7 <= x <= 1e7
  2. Number of operations won't exceed 10000.
  3. The last four operations won't be called when stack is empty.
 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
48
49
50
51
52
53
54
55
56
57
58
59
60
class MaxStack {
    stack<int> stk, stkM;
public:
    /** initialize your data structure here. */
    MaxStack() {
        
    }
    
    void push(int x) {
        stk.push(x);
        if(stkM.empty() || x>=stkM.top()) stkM.push(x);
    }
    
    int pop() {
        int v = stk.top();
        stk.pop();
        if(stkM.top()==v) stkM.pop();
        return v;
    }
    
    int top() {
        return stk.top();
    }
    
    int peekMax() {
        return stkM.top();
    }
    
    int popMax() {
        int v = stkM.top();
        stkM.pop();
        if(v==stk.top()){
            stk.pop();
        }else{
            stack<int> tmp;
            while(!stk.empty() && stk.top()!=v){
                tmp.push(stk.top());
                stk.pop();
            }
            stk.pop();
            while(!tmp.empty()){
                stk.push(tmp.top());
                if(stkM.empty() || tmp.top()>=stkM.top()) stkM.push(tmp.top());
                tmp.pop();
            }
        }
        
        return v;
    }
};

/**
 * Your MaxStack object will be instantiated and called as such:
 * MaxStack* obj = new MaxStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->peekMax();
 * int param_5 = obj->popMax();
 */
Posted by at No comments:

LeetCode [735] Asteroid Collision

735. Asteroid Collision
Medium

We are given an array asteroids of integers representing asteroids in a row.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

 

Example 1:

Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10.  The 5 and 10 never collide.

Example 2:

Input: asteroids = [8,-8]
Output: []
Explanation: The 8 and -8 collide exploding each other.

Example 3:

Input: asteroids = [10,2,-5]
Output: [10]
Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.

Example 4:

Input: asteroids = [-2,-1,1,2]
Output: [-2,-1,1,2]
Explanation: The -2 and -1 are moving left, while the 1 and 2 are moving right. Asteroids moving the same direction never meet, so no asteroids will meet each other.

 

Constraints:

  • 1 <= asteroids <= 104
  • -1000 <= asteroids[i] <= 1000
  • asteroids[i] != 0
 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
class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        stack<int> stk;//asteroids moving to right
        vector<int> ret;
        for(auto a:asteroids){
            if(a>0){//to right
                stk.push(a);
            }else{//to left
                if(stk.empty()){
                    ret.push_back(a);
                }else{
                    bool aWins = true;//the as to the left wins
                    while(!stk.empty())
                    {
                        int ar = stk.top();//the as to the right
                        stk.pop();
                        if(abs(ar) > abs(a)){//ar win
                            stk.push(ar);
                            aWins = false;
                            break;
                        }else if(abs(ar)<abs(a)){//a win
                            continue;
                        }else{
                            aWins = false;
                            break;
                        }
                    }
                    if(stk.empty() && aWins){
                        ret.push_back(a);
                    }
                }
            }
        }
        
        //insert stk to the end of ret, 
        int i = 0;
        while(!stk.empty()){
            ret.insert(ret.end()-(i++), stk.top());
            stk.pop();
        }
        return ret;
    }
};
Posted by at No comments:

LeetCode [529] Minesweeper

Let's play the minesweeper game (Wikipedia, online game)!
You are given a 2D char matrix representing the game board. 'M' represents an unrevealed mine, 'E' represents an unrevealed empty square, 'B' represents a revealed blank square that has no adjacent (above, below, left, right, and all 4 diagonals) mines, digit ('1' to '8') represents how many mines are adjacent to this revealed square, and finally 'X' represents a revealed mine.
Now given the next click position (row and column indices) among all the unrevealed squares ('M' or 'E'), return the board after revealing this position according to the following rules:
  1. If a mine ('M') is revealed, then the game is over - change it to 'X'.
  2. If an empty square ('E') with no adjacent mines is revealed, then change it to revealed blank ('B') and all of its adjacent unrevealed squares should be revealed recursively.
  3. If an empty square ('E') with at least one adjacent mine is revealed, then change it to a digit ('1' to '8') representing the number of adjacent mines.
  4. Return the board when no more squares will be revealed.

Example 1:
Input: 

[['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'M', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E']]

Click : [3,0]

Output: 

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Explanation:
Example 2:
Input: 

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Click : [1,2]

Output: 

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'X', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Explanation:

Note:
  1. The range of the input matrix's height and width is [1,50].
  2. The click position will only be an unrevealed square ('M' or 'E'), which also means the input board contains at least one clickable square.
  3. The input board won't be a stage when game is over (some mines have been revealed).
  4. For simplicity, not mentioned rules should be ignored in this problem. For example, you don't need to reveal all the unrevealed mines when the game is over, consider any cases that you will win the game or flag any squares.
 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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class Solution
{
    vector<vector<int>> dir;

public:
    vector<vector<char>> updateBoard(vector<vector<char>> &board, vector<int> &click)
    {
        if (board[click[0]][click[1]] == 'M')
        {
            board[click[0]][click[1]] = 'X';
            return board;
        }

        int m = board.size(), n = board[0].size();
        dir.push_back(vector<int>{-1, 0});
        dir.push_back(vector<int>{1, 0});
        dir.push_back(vector<int>{0, -1});
        dir.push_back(vector<int>{0, 1});
        dir.push_back(vector<int>{1, 1});
        dir.push_back(vector<int>{1, -1});
        dir.push_back(vector<int>{-1, 1});
        dir.push_back(vector<int>{-1, -1});

        queue<vector<int>> que;
        que.push(click);
        set<vector<int>> visited;
        visited.insert(click);
        while (!que.empty())
        {
            vector<int> c = que.front();
            que.pop();
            int count = 0;
            queue<vector<int>> tmp;
            for (auto d : dir)
            {
                int i = c[0] + d[0], j = c[1] + d[1];
                if (i >= 0 && i < m && j >= 0 && j < n && (board[i][j] == 'M' || board[i][j] == 'E'))
                {
                    if (board[i][j] == 'M')
                    {
                        count++;
                    }
                    else //E
                    {
                        tmp.push(vector<int>{i, j});
                    }
                }
            }

            if (count)
                board[c[0]][c[1]] = ('0' + count);
            else
            {
                board[c[0]][c[1]] = 'B';
                while (!tmp.empty())
                {
                    vector<int> s = tmp.front();
                    if (visited.count(s) == 0)
                    {
                        visited.insert(s);
                        que.push(s);
                    }
                    tmp.pop();
                }
            }
        }
        return board;
    }
};

 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
class Solution {
    int m, n;
    int[][] dir = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,-1},{-1,1},{1,-1}};
    public char[][] updateBoard(char[][] board, int[] click) {
        m = board.length;
        n = board[0].length;
        helper(click[0], click[1], board);
        return board;
    }

    void helper(int i, int j, char[][] board){
        if(board[i][j]=='M'){
            board[i][j] = 'X';
        }else if(board[i][j] == 'E'){
            int mines = 0;
            for(int[] d : dir){
                int ii = i+d[0];
                int jj = j+d[1];
                if(ii>=0 && ii<m && jj>=0 && jj<n && board[ii][jj]=='M'){
                    mines++;
                }
            }
            if(mines>0){
                board[i][j] = (char)('0'+mines);
            }else{
                board[i][j] = 'B';
                for(int[] d : dir){
                    int ii = i+d[0];
                    int jj = j+d[1];
                    if(ii>=0 && ii<m && jj>=0 && jj<n){
                        helper(ii, jj, board);
                    }
                }
            }
        }
    }
}
Posted by at No comments:

LeetCode [815] Bus Routes

815. Bus Routes
Hard

We have a list of bus routes. Each routes[i] is a bus route that the i-th bus repeats forever. For example if routes[0] = [1, 5, 7], this means that the first bus (0-th indexed) travels in the sequence 1->5->7->1->5->7->1->... forever.

We start at bus stop S (initially not on a bus), and we want to go to bus stop T. Travelling by buses only, what is the least number of buses we must take to reach our destination? Return -1 if it is not possible.

Example:
Input: 
routes = [[1, 2, 7], [3, 6, 7]]
S = 1
T = 6
Output: 2
Explanation: 
The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

 

Constraints:

  • 1 <= routes.length <= 500.
  • 1 <= routes[i].length <= 10^5.
  • 0 <= routes[i][j] < 10 ^ 6.
 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
class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int S, int T) {
        if(S==T) return 0;
        set<int> visitedBus, visitedStops;
        int ret = 0;
        map<int, vector<int>> mp;//stop, bus
        for(int i=0; i<routes.size(); ++i)
        {
            for(auto st:routes[i]){
                mp[st].push_back(i);
            }
        }

        queue<int> que;//stops
        que.push(S);
        queue<int> tmp;
        while(!que.empty())
        {
            int curStop = que.front();
            que.pop();
            for(auto b:mp[curStop]){
                if(visitedBus.count(b)) continue;
                visitedBus.insert(b);
                for(auto s:routes[b]){
                    if(visitedStops.count(s)) continue;
                    if(s==T) return ret+1;
                    visitedStops.insert(s);
                    tmp.push(s);
                }
            }
            if(que.empty()){
                ret++;
                que = tmp;
                queue<int> empty;
                swap(tmp, empty);
            }
        }

        return -1;
    }
};
Posted by at No comments:
Subscribe to: Posts (Atom)