Weekly Contest 151

Posted on | In , | |
Words count in article: 2.4k | Reading time ≈ 14

Invalid Transactions

A transaction is possibly invalid if:

the amount exceeds $1000, or;

if it occurs within (and including) 60 minutes of another transaction with the same name in a different city.

Each transaction string transactions[i] consists of comma separated values representing the name, time (in minutes), amount, and city of the transaction.

Given a list of transactions, return a list of transactions that are possibly invalid. You may return the answer in any order.

1
2
3
Input: transactions = ["alice,20,800,mtv","alice,50,100,beijing"]
Output: ["alice,20,800,mtv","alice,50,100,beijing"]
Explanation: The first transaction is invalid because the second transaction occurs within a difference of 60 minutes, have the same name and is in a different city. Similarly the second one is invalid too.
1
2
Input: transactions = ["alice,20,800,mtv","alice,50,1200,mtv"]
Output: ["alice,50,1200,mtv"]
1
2
Input: transactions = ["alice,20,800,mtv","bob,50,1200,mtv"]
Output: ["bob,50,1200,mtv"]

暴力

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
class Solution {
public:
    vector<string> invalidTransactions(vector<string>& t) {
        unordered_map<string, vector<string>> mp;
        for(int i=0; i<t.size(); i++)
        {
            vector<string> v;
            string s = "";
            for(int j=0; j<t[i].size(); j++)
            {
                if(t[i][j] == ',')
                {
                    v.push_back(s);
                    s = "";
                }
                else
                    s += t[i][j];
            }
            v.push_back(s);
            bool f = false;
            for(auto it = mp.begin(); it != mp.end(); it++)
            {
                vector<string> c = it->second;
                if(c[0] == v[0] && c[3] != v[3] && abs(stoi(c[1])-stoi(v[1])) <= 60)
                {
                    if((it->second).back() != "-1")
                        (it->second).push_back("-1");
                    f = true;
                }
            }
            if(stoi(v[2]) > 1000 || f)
            {
                v.push_back("-1");
            }
            mp[t[i]] = v;
        }
        vector<string> ret;
        for(auto it = mp.begin(); it != mp.end(); it++)
        {
            if((it->second).back() == "-1")
                ret.push_back(it->first);
        }
        return ret;
    }
};

Compare Strings by Frequency of the Smallest Character

Let’s define a function f(s) over a non-empty string s, which calculates the frequency of the smallest character in s. For example, if s = “dcce” then f(s) = 2 because the smallest character is “c” and its frequency is 2.

Now, given string arrays queries and words, return an integer array answer, where each answer[i] is the number of words such that f(queries[i]) < f(W), where W is a word in words.

1
2
3
4
5
6
7
8
9
10
Example 1:

Input: queries = ["cbd"], words = ["zaaaz"]
Output: [1]
Explanation: On the first query we have f("cbd") = 1, f("zaaaz") = 3 so f("cbd") < f("zaaaz").
Example 2:

Input: queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
Output: [1,2]
Explanation: On the first query only f("bbb") < f("aaaa"). On the second query both f("aaa") and f("aaaa") are both > f("cc").
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
class Solution {
public:
    vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
        map<int, int> freq; // map会自动排序
        for(int i=0; i<words.size(); i++) freq[f(words[i])]++;
        int cur = 0;
        for(auto p = freq.end(); p != freq.begin(); p--)
        {
            p->second += cur;
            cur = p->second;
        }
        vector<int> res;
        for(int i=0; i<queries.size(); i++)
        {
            int q = f(queries[i]);
            auto p = freq.upper_bound(q);
            if(p == freq.end()) res.push_back(0);
            else  res.push_back(p->second);
        }
        //lower_bound(起始地址，结束地址，要查找的数值) 返回的是数值 第一个 出现的位置。

        //upper_bound(起始地址，结束地址，要查找的数值) 返回的是数值 最后一个 出现的位置。

        //binary_search(起始地址，结束地址，要查找的数值)  返回的是是否存在这么一个数，是一个bool值。
        return res;
    }
    
    int f(string s)
    {
        vector<int> freq(26, 0);
        for(int i=0; i<s.size(); i++) freq[s[i]-'a']++;
        for(int i=0; i<26; i++)
        {
            if(freq[i] != 0) return freq[i];
        }
        return 0;
    }
};

Remove Zero Sum Consecutive Nodes from Linked List

Given the head of a linked list, we repeatedly delete consecutive sequences of nodes that sum to 0 until there are no such sequences.

After doing so, return the head of the final linked list. You may return any such answer.

(Note that in the examples below, all sequences are serializations of ListNode objects.)

1
2
3
4
5
6
7
8
9
10
11
12
13
Example 1:

Input: head = [1,2,-3,3,1]
Output: [3,1]
Note: The answer [1,2,1] would also be accepted.
Example 2:

Input: head = [1,2,3,-3,4]
Output: [1,2,4]
Example 3:

Input: head = [1,2,3,-3,-2]
Output: [1]

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head) {
        auto d = new ListNode(-1);
        d->next = head;
        auto p = d;
        
        while(p)
        {
            int sum = 0;
            bool flag = false;
            auto q = p->next;
            
            while(q)
            {
                sum += q->val;
                if(sum == 0)
                {
                    p->next = q->next;
                    flag = true;
                    break;
                }
                q = q->next;
            }
            if(!flag)
                p = p->next;
        }
        return d->next;
    }
};

Dinner Plate Stacks

You have an infinite number of stacks arranged in a row and numbered (left to right) from 0, each of the stacks has the same maximum capacity.

Implement the DinnerPlates class:

  • DinnerPlates(int capacity) Initializes the object with the maximum capacity of the stacks.
  • void push(int val) pushes the given positive integer val into the leftmost stack with size less than capacity.
  • int pop() returns the value at the top of the rightmost non-empty stack and removes it from that stack, and returns -1 if all stacks are empty.
  • int popAtStack(int index) returns the value at the top of the stack with the given index and removes it from that stack, and returns -1 if the stack with that given index 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
Input: 
["DinnerPlates","push","push","push","push","push","popAtStack","push","push","popAtStack","popAtStack","pop","pop","pop","pop","pop"]
[[2],[1],[2],[3],[4],[5],[0],[20],[21],[0],[2],[],[],[],[],[]]
Output: 
[null,null,null,null,null,null,2,null,null,20,21,5,4,3,1,-1]

Explanation: 
DinnerPlates D = DinnerPlates(2);  // Initialize with capacity = 2
D.push(1);
D.push(2);
D.push(3);
D.push(4);
D.push(5);         // The stacks are now:  2  4
                                           1  3  5
                                           ﹈ ﹈ ﹈
D.popAtStack(0);   // Returns 2.  The stacks are now:     4
                                                       1  3  5
                                                       ﹈ ﹈ ﹈
D.push(20);        // The stacks are now: 20  4
                                           1  3  5
                                           ﹈ ﹈ ﹈
D.push(21);        // The stacks are now: 20  4 21
                                           1  3  5
                                           ﹈ ﹈ ﹈
D.popAtStack(0);   // Returns 20.  The stacks are now:     4 21
                                                        1  3  5
                                                        ﹈ ﹈ ﹈
D.popAtStack(2);   // Returns 21.  The stacks are now:     4
                                                        1  3  5
                                                        ﹈ ﹈ ﹈ 
D.pop()            // Returns 5.  The stacks are now:      4
                                                        1  3 
                                                        ﹈ ﹈  
D.pop()            // Returns 4.  The stacks are now:   1  3 
                                                        ﹈ ﹈   
D.pop()            // Returns 3.  The stacks are now:   1 
                                                        ﹈   
D.pop()            // Returns 1.  There are no stacks.
D.pop()            // Returns -1.  There are still no stacks.
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
class DinnerPlates 
{
public:
    set<int> s_aval;
    vector<stack<int>> vs;
    int cap = 0;
    
    DinnerPlates(int capacity) { cap = capacity; }
    
    void push(int val) {
      if (s_aval.empty()) {
        vs.push_back(stack<int>());
        s_aval.insert(vs.size() - 1);
      }
      auto idx = *s_aval.begin();
      vs[idx].push(val);
      if (vs[idx].size() == cap) s_aval.erase(s_aval.begin());
    }
    
    int pop() {
      if (vs.empty()) return -1;
      auto res = vs.back().top(); vs.back().pop();
      while (!vs.empty() && vs.back().empty()) {
        s_aval.erase(vs.size() - 1);
        vs.pop_back();
      }
      if (!vs.empty() && vs.back().size() < cap) s_aval.insert(vs.size() - 1);
      return res;
    }
    int popAtStack(int index) {
      if (vs.size() <= index || vs[index].empty()) return -1;
      if (vs.size() - 1 == index) return pop();
      auto res = vs[index].top(); vs[index].pop();
      s_aval.insert(index);
      return res;
    }
};

/**
 * Your DinnerPlates object will be instantiated and called as such:
 * DinnerPlates* obj = new DinnerPlates(capacity);
 * obj->push_back(val);
 * int param_2 = obj->pop_back();
 * int param_3 = obj->pop_backAtStack(index);
 */

Maximum Level Sum of a Binary Tree

Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on.

Return the smallest level X such that the sum of all the values of nodes at level X is maximal.

1
2
3
4
5
6
7
Input: [1,7,0,7,-8,null,null]
Output: 2
Explanation: 
Level 1 sum = 1.
Level 2 sum = 7 + 0 = 7.
Level 3 sum = 7 + -8 = -1.
So we return the level with the maximum sum which is level 2.
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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxLevelSum(TreeNode* root) {
        if(!root)
            return 0;
        int cur_level = 0;
        queue<TreeNode* > q;
        q.push(root);
        int mx_sum = INT_MIN;
        int level = -1;
        while(!q.empty())
        {
            cur_level++;
            int sz = q.size();
            int local_sum = 0;
            for(int i=0; i<sz; i++)
            {
                TreeNode *tmp = q.front();
                q.pop();
                local_sum += tmp->val;
                if(tmp->left){
                    q.push(tmp->left);
                }
                if(tmp->right)
                {
                    q.push(tmp->right);
                }
            }
            if(local_sum > mx_sum){
                mx_sum = local_sum;
                level = cur_level;
            }
        }
        return level;
    }
};

Find Words That Can Be Formed by Characters

You are given an array of strings words and a string chars.

A string is good if it can be formed by characters from chars (each character can only be used once).

Return the sum of lengths of all good strings in words.

1
2
3
4
5
6
7
8
9
10
11
12
Example 1:

Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: 
The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.
Example 2:

Input: words = ["hello","world","leetcode"], chars = "welldonehoneyr"
Output: 10
Explanation: 
The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10.
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
class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        if(words.size() == 0)
            return 0;
        
        map<char, int> ma;
        map<char, int> co;
        
        for(int i=0; i<chars.size(); i++)
            ma[chars[i]]++;
        
        int count = 0;
        for(int i=0; i<words.size(); i++)
        {
            co = ma;
            int flag = 0;
            for(int j=0; j<words[i].size(); j++)
            {
                if(co[words[i][j]]!=0)
                {
                    co[words[i][j]]--;
                }
                else
                {
                    flag = 1;
                    break;
                }
            }
            if(flag == 0)
                count += words[i].size();
        }
        return count;
    }
};

Last Substring in Lexicographical Order

Given a string s, return the last substring of s in lexicographical order.

1
2
Input: "leetcode"
Output: "tcode"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    string lastSubstring(string s) {
        int start = 0, N = s.size();
        for(int i=1; i<N; i++)
        {
            if(s[i] == s[start] && s[i-1] == s[start]) continue;
            for(int j=0; i+j < N; j++)
            {
                if(s[start+j] == s[i+j]) continue;
                start = s[start+j] > s[i+j] ? start : i;
                break;
            }
        }
        return s.substr(start);
    }
};

As Far from Land as Possible

Given an N x N grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized and return the distance.

The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.

If no land or water exists in the grid, return -1.

BFS

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
 class Solution {
public:
    int maxDistance(vector<vector<int>>& g) {
        int steps = 0;
        queue<pair<int, int>> q, q1;
        for(auto i=0; i< g.size(); i++)
        {
            for(auto j=0; j < g[i].size(); j++)
            {
                if(g[i][j] == 1)
                {
                    q.push({i-1, j});
                    q.push({i+1, j});
                    q.push({i, j-1});
                    q.push({i, j+1});
                }
            }
        }
        while(!q.empty())
        {
            ++steps;
            while(!q.empty())
            {
                int i=q.front().first, j = q.front().second;
                q.pop();
                if(i >= 0 && j >= 0 && i < g.size() && j < g[i].size() && g[i][j] == 0){
                    g[i][j] = steps;
                    q1.push({i-1, j});
                    q1.push({i+1, j});
                    q1.push({i, j-1});
                    q1.push({i, j+1});
                }
            }
            swap(q1, q);
        }
        return steps == 1 ? -1 : steps-1;
    }
};
Donate? comment?