Leetcode-第156场周赛

发表于 分类于 阅读次数：

5205.独一无二的出现次数

给你一个整数数组 arr，请你帮忙统计数组中每个数的出现次数。

如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。

示例 1：

1
2
3
输入：arr = [1,2,2,1,1,3]
输出：true
解释：在该数组中，1 出现了 3 次，2 出现了 2 次，3 只出现了 1 次。没有两个数的出现次数相同。

示例 2：

1
2
输入：arr = [1,2]
输出：false

示例 3：

1
2
输入：arr = [-3,0,1,-3,1,1,1,-3,10,0]
输出：true

提示：

  • 1 <= arr.length <= 1000
  • -1000 <= arr[i] <= 1000
解法1：map+set

map存各数出现的次数，set看次数有没有重复的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool uniqueOccurrences(vector<int>& arr) {
        int n=arr.size();
        map<int,int> m;
        for(int i=0;i<n;i++)
        {
            m[arr[i]]++;
        }
        map<int,int> res;
        for(map<int,int>::iterator ite=m.begin();ite!=m.end();ite++)
        {
            if(res[ite->second]!=0)
                return false;
            res[ite->second]++;
        }
        return true;
    }
};

5207.尽可能使字符串相等

给你两个长度相同的字符串，s 和 t。

将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。

用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。

如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。

如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0。

示例 1：

1
2
3
输入：s = "abcd", t = "bcdf", cost = 3
输出：3
解释：s 中的 "abc" 可以变为 "bcd"。开销为 3，所以最大长度为 3。

示例 2：

1
2
3
输入：s = "abcd", t = "cdef", cost = 3
输出：1
解释：s 中的任一字符要想变成 t 中对应的字符，其开销都是 2。因此，最大长度为 1。

示例 3：

1
2
3
输入：s = "abcd", t = "acde", cost = 0
输出：1
解释：你无法作出任何改动，所以最大长度为 1。

提示：

  • 1 <= s.length, t.length <= 10^5
  • 0 <= maxCost <= 10^6
  • s 和 t 都只含小写英文字母。
解法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
40
41
42
class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int n=s.size();
        vector<int> nums(n,0);
        //先用nums数组存下每个位置所需的开销
        for(int i=0;i<n;i++)		
        {
            nums[i]=abs(s[i]-t[i]);
        }
        int res=0;
        int sum=0;
        int left=0;
        //滑动窗口
        for(int i=0;i<n;)
        {
            //当前总和+当前元素<=最大开销
            if(sum+nums[i]<=maxCost)
            {
                sum+=nums[i];
                res=max(res,i-left+1);
                i++;
            }
            else
            {
                //一直循环到当前总和+当前元素<=最大开销||或者当前窗口中没有元素！（一开始忘了这部分）
               while(sum+nums[i]>maxCost&&left<i)
               {
                   sum-=nums[left];
                   left++;
               }
            }
            //如果当前窗口没有元素且当前元素大于最大开销向前移动一个位置
            while(i<n&&nums[i]>maxCost&&left==i)
            {
                i++;
                left++;
            }
        }
        return res;
    }
};

5206.删除字符串中的所有相邻重复项 II

给你一个字符串 s，「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。

你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。

在执行完所有删除操作后，返回最终得到的字符串。

本题答案保证唯一。

示例 1：

1
2
3
输入：s = "abcd", k = 2
输出："abcd"
解释：没有要删除的内容。

示例 2：

1
2
3
4
5
6
输入：s = "deeedbbcccbdaa", k = 3
输出："aa"
解释： 
先删除 "eee" 和 "ccc"，得到 "ddbbbdaa"
再删除 "bbb"，得到 "dddaa"
最后删除 "ddd"，得到 "aa"

示例 3：

1
2
输入：s = "pbbcggttciiippooaais", k = 2
输出："ps"

提示：

  • 1 <= s.length <= 10^5
  • 2 <= k <= 10^4
  • s 中只含有小写英文字母。
解法1：栈

理解好题意，理解好题意。一开始以为只能把正好连续为k个元素删除，正确要求是若连续k个元素相同就把这k个删除。

用栈，记录每个的字符和位于当前连续的第几个。

遍历完后出栈放入res中，颠倒res便得到了结果

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
class Solution
{
	public:
		string removeDuplicates(string s,int k)
		{
			stack<pair<char,int>> st;
			int n=s.size();
			int temp=0;
			for(int i=0;i<n;i++)
			{
				if(st.empty()||s[i]==st.top().first)
				{
					if(st.empty())
						temp=1;
					else temp=st.top().second+1;
					st.push(make_pair(s[i],temp));
                    if(st.top().second==k)
                    {
                        int j=st.top().second;
						while(j--)
						{
							st.pop();
						}
                    }
				}
				else
				{
                    temp=1;
					st.push(make_pair(s[i],temp));
				}
			}
			string res="";
			while(!st.empty())
			{
				res+=st.top().first;
				st.pop();
			}
			reverse(res.begin(),res.end());
			return res;
		}
};

5208.穿过迷宫的最少移动次数

你还记得那条风靡全球的贪吃蛇吗？

我们在一个 n*n 的网格上构建了新的迷宫地图，蛇的长度为 2，也就是说它会占去两个单元格。蛇会从左上角（(0, 0) 和 (0, 1)）开始移动。我们用 0 表示空单元格，用 1 表示障碍物。蛇需要移动到迷宫的右下角（(n-1, n-2) 和 (n-1, n-1)）。

每次移动，蛇可以这样走：

  • 如果没有障碍，则向右移动一个单元格。并仍然保持身体的水平／竖直状态。
  • 如果没有障碍，则向下移动一个单元格。并仍然保持身体的水平／竖直状态。
  • 如果它处于水平状态并且其下面的两个单元都是空的，就顺时针旋转 90 度。蛇从（(r, c)、(r, c+1)）移动到 （(r, c)、(r+1, c)）。
    img
  • 如果它处于竖直状态并且其右面的两个单元都是空的，就逆时针旋转 90 度。蛇从（(r, c)、(r+1, c)）移动到（(r, c)、(r, c+1)）。
    img

返回蛇抵达目的地所需的最少移动次数。

如果无法到达目的地，请返回 -1。

示例 1：

img

1
2
3
4
5
6
7
8
9
输入：grid = [[0,0,0,0,0,1],
               [1,1,0,0,1,0],
               [0,0,0,0,1,1],
               [0,0,1,0,1,0],
               [0,1,1,0,0,0],
               [0,1,1,0,0,0]]
输出：11
解释：
一种可能的解决方案是 [右, 右, 顺时针旋转, 右, 下, 下, 下, 下, 逆时针旋转, 右, 下]。

示例 2：

1
2
3
4
5
6
7
输入：grid = [[0,0,1,1,1,1],
               [0,0,0,0,1,1],
               [1,1,0,0,0,1],
               [1,1,1,0,0,1],
               [1,1,1,0,0,1],
               [1,1,1,0,0,0]]
输出：9

提示：

  • 2 <= n <= 100
  • 0 <= grid[i][j] <= 1
  • 蛇保证从空单元格开始出发。
解法1：BFS

注意：这个蛇跟贪吃蛇的移动不太一样，仔细阅读题干。考虑各个情况采用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
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
class Solution {
public:
    int minimumMoves(vector<vector<int>>& grid) {
        int n=grid.size();
        int ans=-1;
        vector<vector<vector<int>>> ck(2,vector<vector<int>>(n,vector<int>(n,false)));
        ck[0][0][1]=true;
        queue<vector<vector<int>>> q;
        vector<vector<int>> qr(2,vector<int>(2,0));
        qr[1][1]=1;
        q.push(qr);
        while(!q.empty())
        {
            int size=q.size();
            ans++;
            for(int i=0;i<size;i++)
            {
                vector<vector<int>> temp(q.front());
                vector<vector<int>> qr(2,vector<int>(2,0));
                q.pop();
                int x1=temp[0][0],y1=temp[0][1],x2=temp[1][0],y2=temp[1][1];    //(x1,y1)蛇尾 (x2,y2)蛇头
                if(x1==n-1&&x2==n-1&&y1==n-2&&y2==n-1)
                    return ans;
                int dir= x1==x2?0:1;        //  竖1,横0
                if(!dir)            //  横向状态
                {
                    if(y2+1<n&&grid[x2][y2+1]==0&&!ck[dir][x2][y2+1])  //  右移
                    {
                        qr[0][0]=x1;qr[0][1]=y1+1;qr[1][0]=x2;qr[1][1]=y2+1;
                        q.push(qr);
                        ck[dir][x2][y2+1]=true;
                    }
                    if(x1+1<n&&grid[x1+1][y1]==0&&grid[x2+1][y2]==0&&!ck[dir][x2+1][y2])     //下移
                    {
                        qr[0][0]=x1+1;qr[0][1]=y1;qr[1][0]=x2+1;qr[1][1]=y2;
                        q.push(qr);
                        ck[dir][x2+1][y2]=true;
                    }
                    if(x1+1<n&&grid[x1+1][y1]==0&&grid[x2+1][y2]==0&&!ck[1-dir][x1+1][y1])   //顺时针90
                    {
                        qr[0][0]=x1;qr[0][1]=y1;qr[1][0]=x1+1;qr[1][1]=y1;
                        q.push(qr);
                        ck[1-dir][x1+1][y1]=true;
                    }
                }
                else                    // 竖向状态
                {
                    if(y1+1<n&&grid[x1][y1+1]==0&&grid[x2][y2+1]==0&&!ck[dir][x2][y2+1])      //右移
                    {
                        qr[0][0]=x1;qr[0][1]=y1+1;qr[1][0]=x2;qr[1][1]=y2+1;
                        q.push(qr);
                        ck[dir][x2][y2+1]=true;
                    }
                    if(x2+1<n&&grid[x2+1][y2]==0&&!ck[dir][x2+1][y2])        //下移
                    {
                        qr[0][0]=x1+1;qr[0][1]=y1;qr[1][0]=x2+1;qr[1][1]=y2;
                        q.push(qr);
                        ck[dir][x2+1][y2]=true;
                    }
                    if(y1+1<n&&grid[x1][y1+1]==0&&grid[x2][y2+1]==0&&!ck[1-dir][x1][y1+1])      //逆时针90
                    {
                        qr[0][0]=x1;qr[0][1]=y1;qr[1][0]=x1;qr[1][1]=y1+1;
                        q.push(qr);
                        ck[1-dir][x1][y1+1]=true;
                    }
                }
            }
        }
        return -1;
    }
};