字节跳动 2022.02.27后端实习笔试

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;
    }
}
  • 打赏
请选择打赏方式
  • 微信
  • 支付宝
订阅评论
提醒
0 评论
内联反馈
查看所有评论
0
动动你可爱的小手留下个评论吧x