字节跳动 2022.02.27后端实习笔试

2022-03-05

1.走迷宫
题目描述
小红站在一个n行m列的迷宫里。迷宫中1代表墙壁，0代表走道，迷宫的四周也被墙壁包围，题目中的输入没有画出来。
小红有WASD四种操作，其中‘W’代表向上走，‘S’代表向下走，‘A’代表向左走，‘D’代表向右走。
但当小红某一次操作会撞墙的时候，小红会站在原地不动。
已知小红的初始位置在左上角，小红想知道自己的最终位置是多少。

分析设计
这是一道简单的模拟题，只需要根据输入的操作字符串对目前位置信息进行判断即可。

代码实现

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int q = sc.nextInt();
        sc.nextLine();
        int[][] graph = new int[n][m];
        for(int i = 0; i < n; ++i){
            String line = sc.nextLine();
            for(int j = 0; j < m; ++j){
                graph[i][j] = line.charAt(j) - '0';
            }
        }
        String operate = sc.nextLine();
        char[] op = operate.toCharArray();
        int[] ans = help(graph, op);
        System.out.println(ans[0] + " " + ans[1]);
    }
    public int[] help(int[][] graph, char[] op){
        int curX = 0, curY = 0;
        int n = graph.length, m = graph[0].length;
        int index = 0;
        while(index < op.length){
            if(op[index] == 'W'){
                curX--;
                if(curX < 0 || curX >= n || graph[curX][curY] == 1){
                    curX++;
                }
            }
            else if(op[index] == 'S'){
                curX++;
                if(curX < 0 || curX >= n || graph[curX][curY] == 1){
                    curX--;
                }
            }
            if(op[index] == 'A'){
                curY--;
                if(curY < 0 || curY >= m || graph[curX][curY] == 1){
                    curY++;
                }
            }
            if(op[index] == 'D'){
                curY++;
                if(curY < 0 || curY >= m || graph[curX][curY] == 1){
                    curY--;
                }
            }
            index++;
        }
        return new int[]{curX, curY};
    }
}

package 数据结构与算法.考试;

import java.util.Scanner;

/**
 * Created by Huang on 2022/2/27 19:28
 */

public class test1 {
    public static void main(String args[]) {
            Scanner cin = new Scanner(System.in);
            String[] data = cin.nextLine().trim().split(" ");
            int n = Integer.parseInt(data[0]);
            int m = Integer.parseInt(data[1]);
            int[][] ground = new int[n+1][m+1];
            for (int i = 0 ; i < n ; i++){
                String[] conditions = cin.nextLine().trim().split(" ");
                for (int j = 0 ; j < m ; j++){
                    ground[i][j] = Integer.parseInt(conditions[j]);
                }
            }
            String operations = cin.nextLine().trim();
            //solution
            int x = 1;
            int y = 1;
            for(int k = 0 ; k < operations.length() ; k++){
                char op = operations.charAt(k);
                if ("W".equals(String.valueOf(op))){
                    if (((x-1)>=0)&&(ground[x-1][y]!=1)){
                        x-=1;
                    }
                }
                if ("S".equals(String.valueOf(op))){
                    if (((x+1)<=n)&&(ground[x+1][y]!=1)){
                        x+=1;
                    }
                }
                if ("A".equals(String.valueOf(op))){
                    if (((y-1)>=0)&&(ground[x][y-1]!=1)){
                        y-=1;
                    }
                }
                if ("D".equals(String.valueOf(op))){
                    if (((y+1)<=m)&&(ground[x][y+1]!=1)){
                        y+=1;
                    }
                }
            }
            System.out.println(x+" "+y);
        }
}
        /*
        3 3 7
        0 0 0
        1 1 0
        0 0 0
        SDWDSSA
        3 2
        */

2.分配数组
题目描述
小红想构造一个长度为n的数组，其中每个数的范围都是[1,n]，且每个数都不相同，并且其中正好有k对相邻数的和为奇数。
你能帮帮她吗？

分析设计
第一感觉这是一道数字排序题，将[1,n]的数字排列后找出其中满足恰好有k对相邻数字的和为奇数的那个排列。但是这样复杂度太高，所以不能用穷举法。仔细观察题目，不难看出，每次有个奇数放入排列中，为保证其与其相邻的数之和为奇数，就要为其相邻的位置放上偶数，这样一来，这道题目可以看是一个数学问题。

数组{1,2,3,…,n}本就是一个有n-1对相邻和为奇数的序列，不妨前k个数取{1,2,3,…,k}，此时相邻和为奇数的共k-1对
对后续的数字，用和k的奇偶性相同的k+2,k+4,…填充，再用k+1,k+3,…填充
后面的数字正好有一对相邻和为奇数的数，这样就有k对

代码实现

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int evenNum = n / 2;
        int oddNum = n - evenNum;
        int cnt = (k + 1) / 2;
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < oddNum; ++i){
            list.add(i * 2 + 1);
        }
        if(k % 2 == 0){
            for(int i = 1; i <= cnt - 1; ++i){
                list.add(oddNum - i, i * 2);
            }
            for(int i = cnt; i < evenNum; ++i){
                list.add(oddNum - cnt, i * 2);
            }
        }
        else{
            for(int i = 1; i <= cnt - 1; ++i){
                list.add(oddNum - i + 1, i * 2);
            }
            for(int i = cnt; i < evenNum; ++i){
                list.add(oddNum - cnt + 1, i * 2);
            }
        }
        for(int i = 0; i < list.size(); ++i){
            System.out.print(list.get(i) + " ");
        }
    }
}

3.染红数字
题目描述
小红拿到了一个长度为n的数组，其中一些数字已经被染红了。
小红想再给一些数字染红，已知染红一个数字的权值为该数字的值。
小红希望存在一个长度至少为k的被染红的连续区间。她想知道花费权值的最小值是多少。

分析设计
一般遇到连续长度的最值问题优先考虑滑动窗口，这题也不例外。通过固定右边界，然后不断右移左边界且要保证左右边界之间的长度大于等于k。左边界的右移可以用临时变量实现。这样实现下来，超时。所以这道题采用滑动窗口实现不是最优解。
仔细审题后，不难发现，我们每次保证长度大于等于k，如果超出k的地方是已经染色的数字，那就不会花费权值；如果超出k的地方是未染色的数字，就需要花费权值，这种情况下，一定会比长度仅为k时的花费多。所以，我们只需要计算长度仅为k时花费的权值即可。那么这样，这道题可以转换为前缀和问题。

代码实现

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < n; ++i){
            nums[i] = sc.nextInt();
        }
        sc.nextLine();
        String operate = sc.nextLine();
        long[] sum = new long[n + 1];
        for(int i = 1; i <= n; ++i){
            if(operate.charAt(i - 1) == 'W'){
                sum[i] = sum[i - 1] + nums[i - 1];
            }
            else{
                sum[i] = sum[i - 1];
            }
        }
        long minCost = Long.MAX_VALUE;
        for(int i = k; i <= n; ++i){
            minCost = Math.min(minCost, sum[i] - sum[i - k]);
        }
        System.out.println(minCost);
    }
}

4.走象棋
题目描述
众所周知，象棋中象走“田”字。假设象初始在(3,4)坐标，它一步可以走到(1,2)或(5,6)或(1,6)或(5,2)坐标。
但是如果象的象眼被堵了，那么就不能走过去。例如刚刚的例子，若(4,5)坐标有一个障碍，那么象则不能从(3,4)走到(5,6)。
若象踩的位置上有个兵，那么象可以把兵吃掉。但如果象眼被堵，那么就无法走到该处。
现在小红有一个n×m的棋盘，其中上面放置了k个兵。小红在(x0,y0)位置放置了一个象。小红想知道从(x0,y0)走到(xt,yt)至少要走多少步。

分析设计
对于多种走法的最值问题大多数情况下优先考虑BFS，如果用BFS解决不了再考虑DFS。
对于多种走法的概率或种数问题则考虑用动态规划。
这道题最开始我是尝试用BFS来解决的，通过使用队列存放下一步会到达的位置来判断是否到达目标点。对于下一步位置如果是兵，就利用HashSet来存储该点是否还是兵。但是这种方法有一个问题是我没有考虑到的：对于一个兵，它既可能是一种走法的象眼，也可能是另一种走法要被吃掉的棋，而这两种走法的先后顺序难以判定。所以，BFS不适用这道题目。
于是采用DFS来解决这个问题。那就转换为一般的路径问题。设置boolean[][] vis来判断该位置是否已经访问，也可以判断是否吃掉了该位置的兵。将所有结果排列出来，取最小即可。

代码实现

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        int[][] soldier = new int[k][2];
        for(int i = 0; i < k; ++i){
            soldier[i][0] = sc.nextInt();
            soldier[i][1] = sc.nextInt();
        }
        int startX = sc.nextInt();
        int startY = sc.nextInt();
        int endX = sc.nextInt();
        int endY = sc.nextInt();
        HashSet<Integer> change = new HashSet<>();
        for(int i = 0; i < k; ++i){
            change.add(i);
        }
        int minStep = Integer.MAX_VALUE;
        dfs(n, m, soldier, new boolean[n][m], minStep, startX, startY, endX, endY, 0, seen);
        if(minStep == Integer.MAX_VALUE){
            minStep = -1;
        } 
        System.out.println(minStep);
    }
    public void dfs(int n, int m, int[][] soldier, boolean[][] vis, int minStep, int startX, int startY, int endX, int endY, int step, HashSet<Integer> change){
        if(step >= minStep){
            return;
        }
        if(startX == endX && startY == endY){
            minStep = Math.min(minStep, step);
            return;
        }
        if(startX < 0 || startX >= n || startY < 0 || startY >= m || vis[startX][startY]){
            return;
        }
        vis[startX][startY] = true;
        if(check(soldier, startX - 1, startY - 1)){
            for(int i = 0; i < soldier.length; ++i){
                if(soldier[i][0] == startX && soldier[i][1] == startY){
                    change.remove(i);
                }
            }
            dfs(n, m, soldier, vis, minStep, startX - 2, startY - 2, endX, endY, step + 1, change);
        }
        if(check(soldier, startX - 1, startY + 1)){
            for(int i = 0; i < soldier.length; ++i){
                if(soldier[i][0] == startX && soldier[i][1] == startY){
                    change.remove(i);
                }
            }
            dfs(n, m, soldier, vis, minStep, startX - 2, startY + 2, endX, endY, step + 1, change);
        }
        if(check(soldier, startX + 1, startY - 1)){
            for(int i = 0; i < soldier.length; ++i){
                if(soldier[i][0] == startX && soldier[i][1] == startY){
                    change.remove(i);
                }
            }
            dfs(n, m, soldier, vis, minStep, startX + 2, startY - 2, endX, endY, step + 1, change);
        }
        if(check(soldier, startX + 1, startY + 1)){
            for(int i = 0; i < soldier.length; ++i){
                if(soldier[i][0] == startX && soldier[i][1] == startY){
                    change.remove(i);
                }
            }
            dfs(n, m, soldier, vis, minStep, startX + 2, startY + 2, endX, endY, step + 1, change);
        }
        vis[startX][startY] = false;
    }
    public boolean check(int[][] soldier, int x, int y){
        for(int i = 0; i < soldier.length; ++i){
            if(soldier[i][0] == x && soldier[i][1] == y){
                return false;
            }
        }
        return true;
    }
}
阅读人次 : 658
  • 打赏
请选择打赏方式
  • 微信
  • 支付宝
订阅评论
提醒
0 评论
内联反馈
查看所有评论
0
动动你可爱的小手留下个评论吧x