Leetcode-第151场周赛

发表于 分类于 阅读次数：

1169.查询无效交易

题目描述

如果出现下述两种情况，交易 可能无效：

  • 交易金额超过 ¥1000
  • 或者，它和另一个城市中同名的另一笔交易相隔不超过 60 分钟（包含 60 分钟整）

每个交易字符串 transactions[i] 由一些用逗号分隔的值组成，这些值分别表示交易的名称，时间（以分钟计），金额以及城市。

给你一份交易清单 transactions，返回可能无效的交易列表。你可以按任何顺序返回答案。

示例 1：

1
2
3
输入：transactions = ["alice,20,800,mtv","alice,50,100,beijing"]
输出：["alice,20,800,mtv","alice,50,100,beijing"]
解释：第一笔交易是无效的，因为第二笔交易和它间隔不超过 60 分钟、名称相同且发生在不同的城市。同样，第二笔交易也是无效的。

示例 2：

1
2
输入：transactions = ["alice,20,800,mtv","alice,50,1200,mtv"]
输出：["alice,50,1200,mtv"]

示例 3：

1
2
输入：transactions = ["alice,20,800,mtv","bob,50,1200,mtv"]
输出：["bob,50,1200,mtv"]

提示：

  • transactions.length <= 1000
  • 每笔交易 transactions[i] 按 "{name},{time},{amount},{city}" 的格式进行记录
  • 每个交易名称 {name} 和城市 {city} 都由小写英文字母组成，长度在 1 到 10 之间
  • 每个交易时间 {time} 由一些数字组成，表示一个 0 到 1000 之间的整数
  • 每笔交易金额 {amount} 由一些数字组成，表示一个 0 到 2000 之间的整数
解法

1.将每个字符串切割存入到结构体中，同时记录在原字符串数组中的位置index

2.对结构体数组进行排序，先按名排序，名相同的按时间从小到大排序

3.

  • 遍历结构体数组先判断下一位是否越界，没有越界找到后面第一个不在相同城市的交易，因为已经排好了序，我们可知，若这一位与当前位时间相差超过60min，则名称相同的必然后面都超过60min,若找到无效交易将当前位放入res结果数组，直接continue下一循环
  • 若下一位超过60min，判断上一位是否越界,若没有越界找到前面第一个不在相同城市的交易，其他与找下一位类似

4.遍历完毕，返回结果数组

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
class Solution {
public:
    
    vector<string> invalidTransactions(vector<string>& transactions) {
        struct trans 
        {
            string na;
            int ta;
            int aa;
            string ca;
            int index;
        };
        vector<string> res;
        int n=transactions.size();
        vector<trans> tr(n);
        int i,j;
        for(i=0;i<n;i++)
        {
            int li=0,ln=transactions[i].size();
            tr[i].na=getStr(transactions[i],li,ln);
            tr[i].ta=getInt(transactions[i],li,ln);
            tr[i].aa=getInt(transactions[i],li,ln);
            tr[i].ca=getStr(transactions[i],li,ln);
            tr[i].index=i;
        }
        sort(tr.begin(),tr.end(),[](auto &l,auto &r){if(l.na!=r.na)return l.na<r.na;return l.ta<r.ta;});
        for(i=0;i<n;i++)
        {
            if(i+1<n)
            {
                int j=i+1;
                while(j<n&&tr[i].ca==tr[j].ca)			//这里极其重要，有可能两个相邻结构体的城市也是一样，要通过循环找到城市不一样的，这样才能找到所有的可能
                    j++;
                if(j<n&&tr[i].na==tr[j].na&&(tr[i].ca!=tr[j].ca)&&abs(tr[i].ta-tr[j].ta)<=60)
                {
                    res.push_back(transactions[tr[i].index]);
                    continue;
                }               
                if(tr[i].aa>1000)
                {
                    res.push_back(transactions[tr[i].index]);
                    continue;
                }
            }
            if(i-1>=0)
            {
                int j=i-1;
                while(j>=0&&tr[i].ca==tr[j].ca)
                    j--;
                if(j>=0&&tr[i].na==tr[j].na&&tr[i].ca!=tr[j].ca&&abs(tr[i].ta-tr[j].ta)<=60)
                {
                    res.push_back(transactions[tr[i].index]);
                    continue;
                }
                if(tr[i].aa>1000)
                {
                    res.push_back(transactions[tr[i].index]);
                    continue;
                }
            }
        }
        return res;
    }
    string getStr(string s,int &i,int n)
    {
        string temp="";
        while(i<n&&!('a'<=s[i]&&s[i]<='z'))
            i++;
        while(i<n&&('a'<=s[i]&&s[i]<='z'))
        {
            temp+=s[i];
            i++;
        }
        return temp;
    }
    int getInt(string s,int &i,int n)
    {
        int temp=0;
        while(i<n&&!('0'<=s[i]&&s[i]<='9'))
            i++;
        while(i<n&&('0'<=s[i]&&s[i]<='9'))
        {
            temp=temp*10+s[i]-'0';
            i++;
        }
        return temp;
    }
};

1170.比较字符串最小字母出现频次

我们来定义一个函数 f(s)，其中传入参数 s 是一个非空字符串；该函数的功能是统计 s 中（按字典序比较）最小字母的出现频次。

例如，若 s = "dcce"，那么 f(s) = 2，因为最小的字母是 "c"，它出现了 2 次。

现在，给你两个字符串数组待查表 queries 和词汇表 words，请你返回一个整数数组 answer 作为答案，其中每个 answer[i] 是满足 f(queries[i]) < f(W) 的词的数目，W 是词汇表 words 中的词。

示例 1：

1
2
3
输入：queries = ["cbd"], words = ["zaaaz"]
输出：[1]
解释：查询 f("cbd") = 1，而 f("zaaaz") = 3 所以 f("cbd") < f("zaaaz")。

示例 2：

1
2
3
输入：queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
输出：[1,2]
解释：第一个查询 f("bbb") < f("aaaa")，第二个查询 f("aaa") 和 f("aaaa") 都 > f("cc")。

提示：

  • 1 <= queries.length <= 2000
  • 1 <= words.length <= 2000
  • 1 <= queries[i].length, words[i].length <= 10
  • queries[i][j], words[i][j] 都是小写英文字母
解法

思路很简单

1.定义两个数组q,w分别存放queries和words各个字符串对应的f函数的值

2.将w从小到大排序，遍历q，当q[i]<w[i]时，则w[i]后面的也大于q[i]，也就得到了q[i]对应的结果数组的值

3.将q[i]的每项存起来，便得到了结果数组，返回

f函数的实现：

利用map，存字符串每个字母的出现次数

找到最小字母的出现次数，返回该值

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 Solution {
public:
    vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
        vector<int> q;
        vector<int> w;
        int map[26];
        memset(map,0,sizeof(map));
        int n=queries.size(),m=words.size();
        int i,j;
        for(i=0;i<n;i++)
        {
            for(j=0;j<queries[i].size();j++)
            {
                map[queries[i][j]-'a']++;
            }
            for(j=0;j<26;j++)
            {
                if(map[j]!=0)
                { 
                    q.push_back(map[j]);
                    break;
                }
            }
            memset(map,0,sizeof(map));
        }
        memset(map,0,sizeof(map));
        for(i=0;i<m;i++)
        {
            for(j=0;j<words[i].size();j++)
            {
                map[words[i][j]-'a']++;
            }
            for(j=0;j<26;j++)
            {
                if(map[j]!=0)
                { 
                    w.push_back(map[j]);
                    break;
                }
            }
            memset(map,0,sizeof(map));
        }
        sort(w.begin(),w.end());
        j=0;
        for(j=0;j<n;j++)
        {
            for(i=0;i<m;i++)
            {
                if(q[j]<w[i])
                {
                    q[j]=m-i;
                    break;
                }
            }
            if(i==m)
                q[j]=0;
        }
        return q;
    }
};

1171.从链表中删去总和为0的连续节点

给你一个链表的头节点 head，请你编写代码，反复删去链表中由 总和 值为 0 的连续节点组成的序列，直到不存在这样的序列为止。

删除完毕后，请你返回最终结果链表的头节点。

你可以返回任何满足题目要求的答案。

（注意，下面示例中的所有序列，都是对 ListNode 对象序列化的表示。）

示例 1：

1
2
3
输入：head = [1,2,-3,3,1]
输出：[3,1]
提示：答案 [1,2,1] 也是正确的。

示例 2：

1
2
输入：head = [1,2,3,-3,4]
输出：[1,2,4]

示例 3：

1
2
输入：head = [1,2,3,-3,-2]
输出：[1]

提示：

  • 给你的链表中可能有 1 到 1000 个节点。
  • 对于链表中的每个节点，节点的值：-1000 <= node.val <= 1000.
解法

因为只有1000个节点，所以直接考虑暴力

思路：

1.将链表转换为数组，便于进行操作

2.两层循环，i遍历每一个点，能否和后面形成总和为0的连续节点，若能，跳出循环，记录j位置，从开始位置i到结束位置j每个点赋值为INT_MAX,i跳转到j，进行下一次循环

3.循环完毕，遍历数组，将不为INT_MAX的值依次放入新的链表中，返回新链表

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
/**
 * 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) {
        vector<int> s;
        ListNode *p=head;
        int sum=0;
        while(p!=NULL)
        {
            s.push_back(p->val);
            p=p->next;
        }
        int n=s.size();
        int i,j;
        for(i=0;i<n;i++)
        {
            sum=0;
            for(j=i;j<n;j++)
            {
                sum+=s[j];
                if(sum==0)
                {
                    break;
                }
            }
            if(sum==0)
            {
                for(int k=i;k<=j;k++)
                {
                    s[k]=INT_MAX;
                }
                i=j;
            }
        }
        ListNode *newhead=new ListNode(-1);
        p=newhead;
        for(i=0;i<n;i++)
        {
            if(s[i]==INT_MAX)
                continue;
            ListNode *pn=new ListNode(s[i]);
            p->next=pn;
            p=p->next;
        }
        return newhead->next;
    }
};

1172.餐盘栈

我们把无限数量 ∞ 的栈排成一行，按从左到右的次序从 0 开始编号。每个栈的的最大容量 capacity 都相同。

实现一个叫「餐盘」的类 DinnerPlates：

  • DinnerPlates(int capacity) - 给出栈的最大容量 capacity。
  • void push(int val) - 将给出的正整数 val 推入 从左往右第一个 没有满的栈。
  • int pop() - 返回 从右往左第一个 非空栈顶部的值，并将其从栈中删除；如果所有的栈都是空的，请返回 -1。
  • int popAtStack(int index) - 返回编号 index 的栈顶部的值，并将其从栈中删除；如果编号 index 的栈是空的，请返回 -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
39
输入： 
["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],[],[],[],[],[]]
输出：
[null,null,null,null,null,null,2,null,null,20,21,5,4,3,1,-1]

解释：
DinnerPlates D = DinnerPlates(2);  // 初始化，栈最大容量 capacity = 2
D.push(1);
D.push(2);
D.push(3);
D.push(4);
D.push(5);         // 栈的现状为：    2  4
                                    1  3  5
                                    ﹈ ﹈ ﹈
D.popAtStack(0);   // 返回 2。栈的现状为：      4
                                          1  3  5
                                          ﹈ ﹈ ﹈
D.push(20);        // 栈的现状为：  20  4
                                   1  3  5
                                   ﹈ ﹈ ﹈
D.push(21);        // 栈的现状为：  20  4 21
                                   1  3  5
                                   ﹈ ﹈ ﹈
D.popAtStack(0);   // 返回 20。栈的现状为：       4 21
                                            1  3  5
                                            ﹈ ﹈ ﹈
D.popAtStack(2);   // 返回 21。栈的现状为：       4
                                            1  3  5
                                            ﹈ ﹈ ﹈ 
D.pop()            // 返回 5。栈的现状为：        4
                                            1  3 
                                            ﹈ ﹈  
D.pop()            // 返回 4。栈的现状为：    1  3 
                                           ﹈ ﹈   
D.pop()            // 返回 3。栈的现状为：    1 
                                           ﹈   
D.pop()            // 返回 1。现在没有栈。
D.pop()            // 返回 -1。仍然没有栈。

提示：

  • 1 <= capacity <= 20000
  • 1 <= val <= 20000
  • 0 <= index <= 100000
  • 最多会对 push，pop，和 popAtStack 进行 200000 次调用。
解法

模拟栈操作，注意数据量10W+

要记录下那些位置可放入数，不然会超时

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
class DinnerPlates {
private:
    int n;
    vector<stack<int>> res;
    stack<int> temp;
    int l,r;
public:
    DinnerPlates(int capacity) {
        n=capacity;
        l=r=0;
    }
    
    void push(int val) {
        int i;
        for(i=l;i<res.size();i++)
        {
            if(res[i].size()<n)
            {
                res[i].push(val);
                l=i;
                r=max(r,i);
                return ;
            }
        }
        res.push_back(temp);
        res[i].push(val);
        l=r=i;
    }
    
    int pop() {
        for(int i=r;i>=0;i--)
        {
            if(res[i].size())
            {
                int x=res[i].top();
                res[i].pop();
                r=i;
                l=min(l,i);
                return x;
            }
        }
        r=0;
        return -1;
    }
    
    int popAtStack(int index) {
        if(index>=res.size()||res[index].size()==0)
            return -1;
        else
        {
            int x=res[index].top();
            res[index].pop();
            l=min(l,index);
            return x;
        }
    }
};

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