讨论/题目交流/🏆 迎国庆,力扣第 156 场周赛 🇨🇳/
🏆 迎国庆,力扣第 156 场周赛 🇨🇳

祖国 image.png 周年盛世华诞,这是国庆前的一场激烈竞赛,欢迎小伙伴们在这里交流分享你的参赛心得以及体验,祝大家国庆假期快乐。

image.png前往竞赛本周周赛题目:

独一无二的出现次数
尽可能使字符串相等
删除字符串中的所有相邻重复项 II
穿过迷宫的最少移动次数 —— 小蛇移动

展开讨论
力扣 (LeetCode)发起于 2019-09-29
最近编辑于 2019-09-29
共 21 个讨论

先占坑,题解稍晚来:

  • 独一无二的出现次数
    数据范围很小,暴力每个数出现次数就可以了。

  • 尽可能使字符串相等
    计算 st 在每个位置的转换价值,然后问题转化为求一个最长的子数组,使得转换价值和小于给定限制,且长度最长。可以用两个指针来维护最长子数组,时间复杂度 O(n)O(n)

  • 删除字符串中的所有相邻重复项 II
    用一个栈模拟题目操作,碰到当前字母连续出现就出栈。

  • 穿过迷宫的最少移动次数
    记忆化搜索 or 动态规划,和之前经典的左上走到右下的动态规划题目没有本质区别。当前状态 dp[x][y][way]dp[x][y][way] 表示蛇走到 xxyy,且身体方向为 wayway 的最小步数。

8

哈哈哈哈,第二题一开始用的 Python 超时了,后来气急败坏改用 Java,还是超时,换成 Go,终于 AC 了,毕竟 O(n2)O(n^2) 的复杂度 hhh

在这里,我想说,Go 语言真的流弊。

6

image.png
第四题DP附解释

4

bool uniqueOccurrences(int* arr, int arrSize){
int count[1001] = {0};
int i=0;
int j,L=0;
for(i=0;i<arrSize;i++){
L++;
if(arr[i]<1002){
count[i] = 1;
for(j=i+1;j<arrSize;j++){
if(arr[j]<1002){
if(arr[i]==arr[j]){
arr[j]=1003;
count[i]++;
}
}
}
}
}
for(i=0;i<L;i++){
if(count[i])
for(j=i+1;j<L;j++){
if(count[i]==count[j])
return false;
}
}
return true;
}
看到各位大佬用各种稀奇古怪的语言,看得我这个CS小白瑟瑟发抖。
我用最基础的C语言写一下吧,写了我好久,可能有点混乱,见谅......
然后我要去攻克第二题了-

1

第四题花了40分钟写出来,但有些小错,改完已经结束20分钟了。

1

第三题题解,运用itertools中的groupby
题解

from itertools import groupby
class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        l = [list(k) for j,k in groupby(s)]
        m = [l[i] if len(l[i])<k else l[i][0]*(len(l[i])%k) for i in range(len(l))]
        if l == m:
            return ''.join([j[i] for j in l for i in range(len(j))])
        s = ''.join([j[i] for j in m for i in range(len(j))])
        return self.removeDuplicates(s,k)
1

第二题是不是先写个关于差的前缀和,然后遍历数组每次二分搜索 cha[i] - maxCost的下标

求助各位大佬帮忙看一下为什么第四题的case会有不通过?不通过的case在main函数中定义了。
超级感谢!!!

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.*;

class Solution {

    public static void main(String[] args) {
        int[][] grid = new int[][] {
                {0,0,0,0,0,0,0,0,0,0},
                {0,0,0,0,0,0,0,0,0,0},
                {0,0,1,1,0,0,1,0,0,0},
                {0,0,1,0,0,0,0,0,0,0},
                {1,0,0,0,0,0,0,0,0,0},
                {0,0,0,0,0,0,0,0,0,0},
                {0,0,0,1,0,0,0,0,1,0},
                {0,0,0,0,0,0,1,0,0,1},
                {0,1,0,0,1,0,0,0,0,0},
                {0,0,0,0,0,1,0,0,0,0}

        };
        System.out.println(new Solution().minimumMoves(grid));
    }

    public int minimumMoves(int[][] grid) {
        // 这个就是动态规划了,
        int rowNum = grid.length;
        int colNum = grid[0].length;
        if (grid[rowNum-1][colNum-2]==1 || grid[rowNum-1][colNum-1]==1)
            return -1;
        int[][][] pos = new int[rowNum][colNum][2]; // 第三维度0表示向右横着,1表示向下竖着
        // 用广度优先BFS,只要遍历到,就是最短
        Stack<State> stack = new Stack<>();
        stack.push(new State(0, 0, 0));
        pos[0][0][0] = 1; // 标记初始位置。因为0表示未被访问过。
        while(!stack.isEmpty()) {
            int len = stack.size();
            for (int i=0; i<len; i++) {
                State s = stack.pop();
                // 判断当前方向
                if (s.dir==0) { // 如果是横向向右
                    // 1. 变向
                    if (s.row<rowNum-1 && pos[s.row][s.col][1]==0 && grid[s.row+1][s.col]==0 && grid[s.row+1][s.col+1]==0) {
                        pos[s.row][s.col][1] = pos[s.row][s.col][0]+1;
                        stack.push(new State(s.row, s.col, 1));
                    }
                    // 2. 右行
                    if (s.col<colNum-2 && pos[s.row][s.col+1][0]==0 && grid[s.row][s.col+2]==0) {
                        pos[s.row][s.col+1][0] = pos[s.row][s.col][0]+1;
                        if (pos[rowNum-1][colNum-2][0]!=0) {
                            return pos[rowNum-1][colNum-2][0]-1;
                        }
                        stack.push(new State(s.row, s.col+1, 0));
                    }
                    // 3. 下行
                    if (s.row<rowNum-1 && pos[s.row+1][s.col][0]==0 && grid[s.row+1][s.col]==0 && grid[s.row+1][s.col+1]==0) {
                        pos[s.row+1][s.col][0] = pos[s.row][s.col][0]+1;
                        if (pos[rowNum-1][colNum-2][0]!=0) {
                            return pos[rowNum-1][colNum-2][0]-1;
                        }
                        stack.push(new State(s.row+1, s.col, 0));
                    }

                } else { // 如果是纵向向下
                    // 1. 变向
                    if (s.col<colNum-1 && pos[s.row][s.col][0]==0 && grid[s.row][s.col+1]==0 && grid[s.row+1][s.col+1]==0) {
                        pos[s.row][s.col][0] = pos[s.row][s.col][1]+1;
                        if (pos[rowNum-1][colNum-2][0]!=0) {
                            return pos[rowNum-1][colNum-2][0]-1;
                        }
                        stack.push(new State(s.row, s.col, 0));
                    }
                    // 2. 右行
                    if (s.col<colNum-1 && pos[s.row][s.col+1][1]==0 && grid[s.row][s.col+1]==0 && grid[s.row+1][s.col+1]==0) {
                        pos[s.row][s.col+1][1] = pos[s.row][s.col][1]+1;
                        stack.push(new State(s.row, s.col+1, 1));
                    }
                    // 3. 下行
                    if (s.row<rowNum-2 && pos[s.row+1][s.col][1]==0 && grid[s.row+2][s.col]==0) {
                        pos[s.row+1][s.col][1] = pos[s.row][s.col][1]+1;
                        stack.push(new State(s.row+1, s.col, 1));
                    }
                }
            }
        }


        if (pos[rowNum-1][colNum-2][0]==0)
            return -1;
        else
            return pos[rowNum-1][colNum-2][0]-1;
    }


}

  class State {
      int row;
      int col;
      int dir;
      public State(int r, int c, int d) {
          row = r;
          col = c;
          dir = d;
      }
  }

第四题隐藏规则有点多啊,要考虑蛇头蛇尾的问题,没玩过贪食蛇的朋友岂不被坑死。我玩过,也没联想到规则啊