Leetcode第236场周赛

Leetcode第236场周赛

Louis 1311 2021-04-11

参与的第三场周赛，之前的周赛都能解前面3个题。6分钟解第一个简单题，第二题调试了一个多钟居然超时，心态爆炸。然后看第三个题，还没复习到这种算法，直接放弃……表现最差的一次。

文章中会出现该周赛的题目&我的解法&大佬的解法。

周赛连接： 第 236 场周赛

数组元素积的符号

题目链接：数组元素积的符号

我的解法：

这是个阅读理解题，虽然说是所有数字的乘积，但是乘积数这么大，怎么可能可以保存，自己阅读发现，只是个判断结果正负号的题目。那就直接判断符号就行了。

class Solution {
public:
    int arraySign(vector<int> &nums) {
        int ret = 1;
        for (int i : nums) {
            if(i == 0){
                return 0;
            }else if (i < 0){
                ret = -ret;
            }
        }
        return ret;
    }
};

这种垃圾题目我都懒得跟说思路和改进方案了，6分钟的题，开心就好。

找出游戏的获胜者

题目连接：找出游戏的获胜者

我的解法：

按照题目的说法来，先做出一个队列，然后按照要求出列，返回最后剩下的那个编号。

class Solution {
public:
    int findTheWinner(int n, int k) {
        vector<int> queue(n);
        for (int i = 0; i < queue.size(); i++) {
            queue[i] = i + 1;
        }
        int last = 0;
        while (queue.size() != 0) {
            last += k ;
            last %= queue.size();
            last--;
            if (last == queue.size()) {
                last = 0;
            } else if (last < 0) {
                last += queue.size();
            }
            queue.erase(queue.begin() + last);
        }
        return queue[0];
    }
};

提交的时候，忘记把调试使用的cout删掉，导致提交超时，服了…… 后来我用题目来测试原来的答案，直接AC了

别人的答案：

class Solution {
public:
    int findTheWinner(int n, int k) {
        return n == 1 ? n : (findTheWinner(n - 1, k) + k - 1) % n + 1;
    }
};

一行代码……啊这

你……

他……

算了，看点阳间的操作

class Solution:
    def findTheWinner(self, n, k):
        if n == 1:
            return 1
        val = 0
        for i in range(2, n + 1):
            cur = (val + k) % i
            val = cur
        return val + 1

作者：qingfengpython
链接：https://leetcode-cn.com/problems/find-the-winner-of-the-circular-game/solution/5727zhao-chu-you-xi-de-huo-sheng-zhe-don-t80b/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

据说跟剑指offer的小朋友们的游戏如出一辙，书我没看完，可以翻阅一下。

最少侧跳次数

最少侧跳次数

不要说我的解法了，这题我结束比赛都没什么思路……感觉是一些我还没复习到的算法。

我的解法：

class Solution {
public:
    int minSideJumps(vector<int>& obstacles) {
			//贪心？ 动规？
    }
};

害，菜是原罪。

直接看题解吧：

dp[pos][赛道编号]表示到达第i处第j跑道的最少跳跃次数。

class Solution {
public:
    int minSideJumps(vector<int>& ob) {
        int n = ob.size();
        vector<vector<int>> dp(n, vector<int>(3, 0x3f3f3f3f) );
        dp[0][1] = 0;
        dp[0][0] = 1;
        dp[0][2] = 1;

        for(int i=1; i<n; ++i)
        {
            if(ob[i] != 1) dp[i][0] = dp[i-1][0];
            if(ob[i] != 2) dp[i][1] = dp[i-1][1];
            if(ob[i] != 3) dp[i][2] = dp[i-1][2];
            if(ob[i] != 1) dp[i][0] = min(dp[i][0], min(dp[i][1], dp[i][2]) + 1);
            if(ob[i] != 2) dp[i][1] = min(dp[i][1], min(dp[i][0], dp[i][2]) + 1);
            if(ob[i] != 3) dp[i][2] = min(dp[i][2], min(dp[i][0], dp[i][1]) + 1);
            
        }
        return min(dp[n-1][0], min(dp[n-1][1], dp[n-1][2]));
    }
};

作者：zhouzzz
链接：https://leetcode-cn.com/problems/minimum-sideway-jumps/solution/dp-by-zhouzzz-8tj2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

贪心解法的思路：

  1. 青蛙初始入赛道数记为num，然后for循环一直前行
  2. 当判断i + 1 等于num时，我们需要考虑两点
  3. 如果位置是否有障碍(因为走到了当前所有障碍肯定不是num)，然后只有三条赛道，所以此时求差集后直接次数加一继续即可
  4. 如果当前位置无障碍，这需要贪心思维，获取除num以外的两个赛道，谁能下一次走的更远，选择最远的跳过去
  5. 重复2,3,4，完成解题...
class Solution:
    def minSideJumps(self, obstacles):
        length = len(obstacles)
        ret = 0
        num = 2
        choices = {1, 2, 3}
        for i in range(length - 1):
            if obstacles[i + 1] == num:
                _choice = choices - {num, obstacles[i]}
                if len(_choice) == 1:
                    num = _choice.pop()
                    ret += 1
                else:
                    tmp = {}
                    for j in _choice:
                        n = i
                        while n < length and obstacles[n] != j:
                            n += 1
                        tmp[n] = j
                    num = tmp[max(tmp)]
                    ret += 1
        return ret

作者：qingfengpython
链接：https://leetcode-cn.com/problems/minimum-sideway-jumps/solution/5728zui-shao-ce-tiao-ci-shu-xiang-xi-jie-sdcw/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时隔两天，学习了一下贪心算法。写出如下能AC的代码

class Solution {
public:
    int minSideJumps(vector<int> &ob) {
        //贪心算法，尽量往前走
        //开始时处于赛道2
        int cur = 2;
        //侧跳次数
        int ret = 0;
        for (int i = 0; i < ob.size() - 1; i++) {
            //std::cout << "cur " << cur << endl;
            if (ob[i + 1] != cur) {
                continue;
            } else {
                //找一个位置跳
                int max_step = 0;
                for (int j = 1; j <= 3; j++) {
                    int step = i;
                    while (step < ob.size() && ob[step] != j) {
                        step++;
                    }
                    if (step > max_step) {
                        max_step = step;
                        cur = j;
                    }
                }
                ret++;
            }
        }
        return ret;
    }
};

尾声

心态没有保持到最后，提交的时候忘了删除cout，导致第二题的答案没有成功AC，第三题确实是算法基础一般，需要学习一下贪心和动规了。

做周赛的本质还是要学习算法，遇到不懂的题反复看题解，反复做。总算把第三题做出来了。

Leetcode