首页 > 9.13滴滴&度小满编程题Java
头像
xust_Hangc
编辑于 2020-09-13 22:25
+ 关注

9.13滴滴&度小满编程题Java

滴滴第一题:

题意 给你一个字符串  str 和 一个数字 k, 将这个字符串每隔k个倒置一下最后不足k个则有多少翻多少个;

思路: 直接做
参考代码:
import java.util.*;

public class Main  {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String tmpK = sc.nextLine();
        int k = Integer.valueOf(tmpK);
        String str = sc.nextLine();
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < str.length(); i += k){
            if(i + k > str.length()){
                sb.append(new StringBuilder(str.substring(i)).reverse());
            } else {
                sb.append(new StringBuilder(str.substring(i, i + k)).reverse());
            }
        }
        System.out.println(sb.toString());
    }
}

滴滴第二题:

题意:   给你n个点 m条边 最高花费k,  然后每两个点连起来需要给定的一个代价。  判断能否最后是这个图连通

思路:并查集裸题  union的判断依据就是判断给定的最高花费k和当前所需要的代价比大小即可

参考代码:
import java.util.*;

public class Main  {
    static int[] pre = new int[1010];
    static int[] size = new int[1010];

    public static void init(){
        for(int i = 1; i < 1010; i++){
            pre[i] = i;
            size[i] = 1;
        }
    }

    public static int find(int x){
        return x == pre[x] ? x : (pre[x] = find(pre[x]));
    }

    public static void union(int x, int y){
        x = find(x);
        y = find(y);
        if(x != y){
            pre[x] = y;
            size[y] += size[x];
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while((t--) != 0){
            init();
            int n = sc.nextInt();
            int m = sc.nextInt();
            int k = sc.nextInt();
            for(int i = 0; i < m; i++){
                int x = sc.nextInt();
                int y = sc.nextInt();
                int val = sc.nextInt();
                if(val <= k){
                    union(x, y);
                }
            }
            if(size[find(1)] != n){
                System.out.println("No");
            } else {
                System.out.println("Yes");
            }
        }
    }
}



度小满第一题:

题意 阅读理解题  直接做
参考代码:
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();
        long sum = 0;
        long pre = 0;
        for(int i = 1; i <= 3; i++){
            for(int j = 0; j < n; j++){
                pre += m;
                sum += pre;
            }
        }
        System.out.println(sum);
    }
}

度小满第二题:

题意:  给定一个地图 长宽都是n, 还有一个陷入陷阱所需的等待时间k。
有三种标志 分别代表 空地、 墙、 陷阱、 每次可以选择上下左右方向进行走, 走空地没处罚, 走陷阱需要等待k秒可以继续走, 墙不能走;

从左上点出发,到达右下点,询问最短时间. 不能到达右下点 输出"No solution"。

思路: bfs即可,因为可能存在陷入陷阱 所以我用了优先队列来搞;
参考代码:
import java.util.*;

public class Main  {
    static char[][] mat = new char[110][110];
    static int n;
    static int k;
    static int Go[][] =  new int[][]{{0, 1},{0, -1}, {1, 0}, {-1, 0}};
    static boolean[][] vis = new boolean[110][110];
    static class Node implements Comparable{
        int x;
        int y;
        int time;

        public Node(int x, int y, int time) {
            this.x = x;
            this.y = y;
            this.time = time;
        }

        @Override
        public int compareTo(Object o) {
            return this.time - ((Node) o).time;
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();
        for(int i = 1; i <= n; i++){
            String str = sc.next();
            for(int j = 1; j <= n; j++){
                mat[i][j] = str.charAt(j - 1);
            }
        }
        int val = bfs();
        if(val == -1){
            System.out.println("No solution");
        } else {
            System.out.println(val);
        }
    }

    public static int bfs(){
        PriorityQueue<Node> queue = new PriorityQueue<>();
        queue.add(new Node(1, 1, 0));
        vis[1][1] = true;
        while(!queue.isEmpty()){
            Node now = queue.poll();
            if(now.x == n && now.y == n){
                return now.time;
            }
            for(int i = 0; i < 4; i++){
                int tmpX = now.x + Go[i][0];
                int tmpY = now.y + Go[i][1];
                if(tmpX >= 1 && tmpX <= n && tmpY >= 1 && tmpY <= n && mat[tmpX][tmpY] != '1' && !vis[tmpX][tmpY]){
                    if(mat[tmpX][tmpY] == '0'){
                        queue.add(new Node(tmpX, tmpY, now.time + 1));
                        vis[tmpX][tmpY] = true;
                    } else if(mat[tmpX][tmpY] == '#'){
                        queue.add(new Node(tmpX, tmpY, now.time + k + 1));
                        vis[tmpX][tmpY] = true;
                    }
                }
            }
        }
        return -1;
    }
}



全部评论

(2) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐