LeetCode 周赛-236（万得场）

曾经终败给现在 2022-11-18 04:45 30阅读 0赞

# 236周赛 #

## [数组元素积的符号][Link 1]（简单） ##

已知函数 signFunc(x) 将会根据 x 的正负返回特定值：

*  如果 x 是正数，返回 1 。
 *  如果 x 是负数，返回 -1 。
 *  如果 x 是等于 0 ，返回 0 。

给你一个整数数组 *nums* 。令 *product* 为数组 *nums* 中所有元素值的乘积。

返回 *signFunc(product)* 。

示例 1：

*输入：nums = \[-1,-2,-3,-4,3,2,1\]*  
*输出：1*  
*解释：数组中所有值的乘积是 144 ，且 signFunc(144) = 1*  
示例 2：

*输入：nums = \[1,5,0,2,-3\]*  
*输出：0*  
*解释：数组中所有值的乘积是 0 ，且 signFunc(0) = 0*

### 题解 ###

思想：简单题目最主要的就是快速解决和思考到所有情况

1.  有0的时候就要立马退出循环体，防止浪费更多的时间与空间。
2.  因为题目中是数字的相乘所以，对于负数的奇偶很是重要，

### 代码 ###

public int arraySign(int[] nums) { 
     int ans = 1;
            for (auto n : nums) { 
                if (n == 0) return 0;
                ans *= (n > 0) ? 1 : -1;
            }
            return ans;
        }

## [找出游戏的获胜者][Link 2]（中等） ##

共有 `n` 名小伙伴一起做游戏。小伙伴们围成一圈，按 **顺时针顺序** 从 `1` 到 `n` 编号。确切地说，从第 `i` 名小伙伴顺时针移动一位会到达第 `(i+1)` 名小伙伴的位置，其中 `1 <= i < n` ，从第 `n` 名小伙伴顺时针移动一位会回到第 `1` 名小伙伴的位置。

游戏遵循如下规则：

1.  从第 `1` 名小伙伴所在位置 **开始** 。
2.  沿着顺时针方向数 `k` 名小伙伴，计数时需要 **包含** 起始时的那位小伙伴。逐个绕圈进行计数，一些小伙伴可能会被数过不止一次。
3.  你数到的最后一名小伙伴需要离开圈子，并视作输掉游戏。
4.  如果圈子中仍然有不止一名小伙伴，从刚刚输掉的小伙伴的 **顺时针下一位** 小伙伴 **开始**，回到步骤 `2` 继续执行。
5.  否则，圈子中最后一名小伙伴赢得游戏。

给你参与游戏的小伙伴总数 `n` ，和一个整数 `k` ，返回游戏的获胜者。

### 题解 ###

注： 此题为剑指offer原题：[Jz46][]

1.  题目中要求是在完成一圈之后要再度回到节点一，所以思考如何设置一个循环出来。
2.  题目中给定的`n`值是一共多少个人，所以我们需要思考使用什么数据结构。
    
    1.  使用到数组，就意味着数组的大小是不可以变化的，那对于访问过的需要怎么处理,来表示已经访问成功？我们可以设置不同的值来表示已经成功访问。
    2.  使用到链表时候，怎么来表示是哪个成员
3.  所以比较起来使用到数组更为合适,使用值-1表示已经成功访问.一直循环进行访问,在访问到末尾的时候,设置访问值变成一即可

### 代码 ###

public int findTheWinner(int n, int m) { 
         int [] num = new int[n];
            int i = -1;
            int count = n;
            int index = -1;
            while(count>0)
            { 
                i++;
                if(i>=n)i =0;
                if(num[i] == -1)
                    continue;
                index++;
                if(index == m-1)
                { 
                    num[i] = -1;
                    index = -1;
                    count--;
                }
            }
            return i+1;
        }

## [最小侧跳次数][Link 3](中等) ##

给你一个长度为 `n` 的 `3` **跑道道路** ，它总共包含 `n + 1` 个 点 ，编号为`0`到 *n* 。一只青蛙从 0 号点第二条跑道 出发 ，它想要跳到点 n 处。然而道路上可能有一些障碍。

给你一个长度为 n + 1 的数组 obstacles ，其中 obstacles\[i\] （取值范围从 0 到 3）表示在点 i 处的 obstacles\[i\] 跑道上有一个障碍。如果 obstacles\[i\] == 0 ，那么点 i 处没有障碍。任何一个点的三条跑道中 最多有一个 障碍。

**比方说，如果 obstacles\[2\] == 1 ，那么说明在点 2 处跑道 1 有障碍。**  
这只青蛙从点 i 跳到点 i + 1 且跑道不变的前提是点 i + 1 的同一跑道上没有障碍。为了躲避障碍，这只青蛙也可以在 同一个 点处 侧跳 到 另外一条 跑道（这两条跑道可以不相邻），但前提是跳过去的跑道该点处没有障碍。

**比方说，这只青蛙可以从点 3 处的跑道 3 跳到点 3 处的跑道 1** 。  
这只青蛙从点 0 处跑道 2 出发，并想到达点 n 处的 任一跑道 ，请你返回 最少侧跳次数 。

注意：点 0 处和点 n 处的任一跑道都不会有障碍。

![img][]

### 题解 ###

面对这种找寻最小的次数,或者说想要我们给出一个最后的结果(个数)一般都是通过动态规划来求解,但是对于那种让我们给出全部的路径,从哪里到哪里的具体路径值是多少,一般使用到回溯算法,记录下来具体的值来求解

1.  以动态规划的思想来解决的第一步就是定义dp的状态

`dp[i][j]`: 表示说 跳到第`i`行第`j`列时候需要的步数

1.  对于初始值的定义,我们这样看上图是三行多列,不是很符合我们的一般操作习惯,于是我们定义 `dp[len]3]`: 表示说,现在我们有`len`列,但是只有三行
2.  初始值: 因为我们最开始位于`dp[0][1]`此时需要移动的次数是0,题目中说了对于第一行来说是不会设置石头的,所以此时我们对于`dp[0][0]`,与`dp[0][2]`的初始值就是从`dp[0][1]`侧跳一次移动过去所以我们有如下的初值定义:

dp[0][0] = 1;
    dp[0][2] = 1;
    dp[0][1] = 0;// 默认就是0

1.  状态方程的转移: 对于第一列来说若是石头,就表示不可达,我们设置为`最大值-1`(因为设置最大值时候,后期会出现+1,就会变成最小值)此时其他两列的转移就有两个方向
    
    1.  从上一行过来不进行侧跳,此时`dp[i][j] = dp[i-1][j]`.
    2.  但是同事也可以从另外一个没有石头的方位侧跳过来(注意此时我们还没有判断当前行的所有列值,只能够取上一行的值,我们也说过了,对于一列,没有出现四石头的时候值都是相同的)`dp[i][j] = dp[i-1][j+1]||dp[i-1][j+1]`\+1,最后取两者之间的较小值.

### 代码 ###

public int minSideJumps(int[] obstacles) { 
       int n = obstacles.length;
            int[][] dp=new int[n][3];
            dp[0][0]=1;
            dp[0][2]=1;
            
            for(int i=1;i<n;++i){ 
                if(obstacles[i]==1){     
                    dp[i][0]=Integer.MAX_VALUE-1;
                    dp[i][1]=Math.min(dp[i-1][1],dp[i-1][2]+1);
                    dp[i][2]=Math.min(dp[i-1][2],dp[i-1][1]+1);                
                }else if(obstacles[i]==2){ 
                    dp[i][1]=Integer.MAX_VALUE-1;
                    dp[i][0]=Math.min(dp[i-1][0],dp[i-1][2]+1);
                    dp[i][2]=Math.min(dp[i-1][2],dp[i-1][0]+1);                
                }else if(obstacles[i]==3){ 
                    dp[i][2]=Integer.MAX_VALUE-1;
                    dp[i][0]=Math.min(dp[i-1][0],dp[i-1][1]+1);
                    dp[i][1]=Math.min(dp[i-1][1],dp[i-1][0]+1);                
                }else{ 
                    dp[i][0]=Math.min(dp[i-1][0],Math.min(dp[i-1][1],dp[i-1][2])+1);
                    dp[i][1]=Math.min(dp[i-1][1],Math.min(dp[i-1][0],dp[i-1][2])+1);
                    dp[i][2]=Math.min(dp[i-1][2],Math.min(dp[i-1][0],dp[i-1][1])+1);
                }            
            }
            
            return Math.min(dp[n-1][0],Math.min(dp[n-1][1],dp[n-1][2]));
        }

[Link 1]: https://leetcode-cn.com/problems/sign-of-the-product-of-an-array/
[Link 2]: https://leetcode-cn.com/problems/find-the-winner-of-the-circular-game/
[Jz46]: https://www.nowcoder.com/ta/coding-interviews
[Link 3]: https://leetcode-cn.com/problems/minimum-sideway-jumps/
[img]: /images/20221022/c38a0506642742e0b56aff4e02240ad7.png