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;
}
}