前言

1、红蓝格子填字母
2、桌上弹球游戏
3、困于环中的机器人

一、红蓝格子填字母【蚂蚁4.11笔试第三题】

小红拿到了一排格子，每个格子的背景是红色或者蓝色。小红希望你将每个格子上填写一个小写字母，需要满足相同的字母背景颜色是相同的。
小红希望最终出现次数最多的字母的出现次数尽可能小。你能帮帮她嘛？

输入描述：
一个仅由字符’0’和’1’组成的字符串，长度不超过200000.
字符串用于表示小红拿到的格子的颜色。第 i 个字符为’0’代表第 i 个格子为蓝色背景，字符’1’ 代表第 i 个格子为红色背景。

输出描述：
一个仅由小写字母构成的字符串，第 i 个字符为第 i 个格子上填写的字母，请务必保证字符串是合法的。如果有多解，输出任意即可。

示例一：
输入 ： 010
输出 ： abc

示例二：
输入 ： 0000000000000000000000000001
输出 ： bbcdefghijklmnopqrstuvwxyza

解法一：二分解法

分析：

枚举了出现次数最大的字母，对于其他字母的话，最多也是这么多

public class heihei {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String s = sc.nextLine();int num0 = 0, num1 = 0;for(int i = 0; i < s.length(); i++){if(s.charAt(i) == '0')num0++;elsenum1++;}//二分次数int right = Math.max(num0, num1);int left = 1;int ans = 0;while(left <= right){int mid = (left + right) / 2;if(judge(num0, num1, mid)){ans = mid;right = mid - 1;}else{left = mid + 1;}}char c0 = 'a';char c1 = 'z';num0 = 0;num1 = 0;char[] res = new char[s.length()];for(int i = 0; i < s.length(); i++){if(s.charAt(i) == '0'){num0++;res[i] = c0;if(num0 == ans){c0++;num0 = 0;}}else{num1++;res[i] = c1;if(num1 == ans){c1--;num1 = 0;}}}for(char c : res){System.out.print(c);}}public static boolean judge(int num0, int num1, int mid){int sum = 0;if(num0 % mid != 0){sum = sum + num0 / mid + 1;}else{sum = sum + num0 / mid;}if(num1 % mid != 0){sum = sum + num1 / mid + 1;}else{sum = sum + num1 / mid;}if(sum <= 26){return true;}return false;}
}

解法二：模拟

分析：
根据0/1的数量分配应该给他们的字母的个数，然后从a-z 26个字母里面给他们分配,然后用两个指针赋值。

public static void main(String[] args) {Scanner sc = new Scanner(System.in);String input = sc.nextLine();int n = input.length();char[] array = input.toCharArray();double[] res1 = new double[]{0,0};char[] res3 = new char[n];//便利输入字符串，统计0/1出现的次数for (char c : array) {if(c == '0')res1[0]++;elseres1[1]++;}double[] res2 = new double[2];//计算0和1的比例，并算出应该在26个字母中分配的个数，存储在res2中if(res1[0]<res1[1]){res2[0] = Math.ceil(26*(res1[0]/(res1[0]+res1[1])));res2[1] = 26 - res2[0];}else{res2[1] = Math.ceil(26*(res1[1]/(res1[0]+res1[1])));res2[0] = 26 - res2[1];}
//000000000000000000000000001String a2z = "abcdefghijklmnopqrstuvwxyz";//s0是给0分配的字母String s0 = a2z.substring(0,(int)res2[0]);//s1是给1分配的字母String s1 = a2z.substring((int)res2[0],a2z.length());//双指针int zeroIndex = 0;int oneIndex = 0;//输入少于等于26时直接输出if(input.length()<=26){System.out.println(a2z.substring(0,input.length()));}else{for (int i = 0; i < n; i++) {if(array[i] == '0'){res3[i] = s0.charAt(zeroIndex);zeroIndex++;if(zeroIndex >= s0.length()){zeroIndex = 0;}}else{res3[i] = s1.charAt(oneIndex);oneIndex++;if(oneIndex >= s1.length()){oneIndex = 0;}}}String result = new String(res3);System.out.println(result);}HashMap<Character,Integer> map = new HashMap<>();for (char c : res3) {map.put(c,map.getOrDefault(c,0)+1);}for (Map.Entry<Character, Integer> characterIntegerEntry : map.entrySet()) {System.out.println(characterIntegerEntry.getKey()+"->"+characterIntegerEntry.getValue());}}

二、桌上弹球游戏【蚂蚁4.11笔试第二题】

小红在玩一个桌上弹球游戏。已知桌子可以视为一个n*m的矩阵，初始有一个小球的坐标为(i,j)(可以视为第i行第j列)。小球会以以下四个方向之一开始运动：

• 小球向右下运动，记为“DR”。每过一秒小球会从(i,j)坐标移动到(i+1,j+1)坐标。
• 小球向左下运动，记为“DL”。每过一秒小球会从(i,j)坐标移动到(i+1,j-1)坐标。
• 小球向右上运动，记为“UR”。每过一秒小球会从(i,j)坐标移动到(i-1,j+1)坐标。
• 小球向左上运动，记为“UL”。每过一秒小球会从(i,j)坐标移动到(i-1,j-1)坐标。

当小球撞到墙的时候会反弹，反向发生改变。
小球将不断行进，永不停止。现在给定了桌面大小。以及小球的初始坐标和初始方向。请问小球多少秒后将回到初始点？
输入描述：
第一行输入两个正整数n和m，代表桌面矩阵的行数和列数。
第二行输入两个正整数i和j以及一个长度为2的字符串d，代表小球的初始坐标和方向。
d∈{DR,DL,UR,UL}

输出描述：
一个整数，代表小球回到初始点需要经过的秒数

示例一：
输入 ：
5 7
1 7 DL

输出 ：
24

模拟：
需要考虑一些边界问题

    public static void main(String[] args) {//输入Scanner input = new Scanner(System.in);//n行m列int n = input.nextInt();int m = input.nextInt();//初始位置（x,y）int x = input.nextInt();int y = input.nextInt();//初始方向String d = input.next();int count = 0;//修正存储和输入的起点索引不一致x = x - 1;y = y - 1;int tx = x, ty = y;  //当前坐标String dir = d;  //当前方向while(true){     //一定要考虑全面边界条件，以及典型样例包括网格为1*1的//不同方向的走法if(dir.equals("DL")){tx = tx + 1;ty = ty - 1;}else if(dir.equals("DR")){tx = tx + 1;ty = ty + 1;}else if(dir.equals("UL")){tx = tx - 1;ty = ty - 1;}else if(dir.equals("UR")){tx = tx - 1;ty = ty + 1;}//判断所处当前坐标的方向是否需要改变改变String t = modifyDir(tx, ty, n, m, dir);if(!dir.equals(t)){//相当于已经走出边界了，需要返回到网格中来if(dir.equals("DL")){tx = tx - 1;ty = ty + 1;}else if(dir.equals("DR")){tx = tx - 1;ty = ty - 1;}else if(dir.equals("UL")){tx = tx + 1;ty = ty + 1;}else if(dir.equals("UR")){tx = tx + 1;ty = ty - 1;}count--; //走出网格这一步多走了，返回去减1}dir = t;count++;//计时if(tx == x && ty == y){System.out.println(count);break;}}}public static String modifyDir(int tx, int ty, int n, int m, String dir){//if((tx < 0 && dir.charAt(0) == 'U') || (tx == n && dir.charAt(0) == 'D')){//撞上下边，只改变上下方向，左右方向不变if(dir.charAt(0) == 'U'){dir = dir.replace('U', 'D');}else{dir = dir.replace('D', 'U');}}//这两个if之间不能加else，因为可能存在对角线反弹if((ty < 0 && dir.charAt(1) == 'L') || (ty == m && dir.charAt(1) == 'R')){//撞左右边，只改变左右方向，上下方向不变if(dir.charAt(1) == 'L'){dir = dir.replace('L', 'R');}else{dir = dir.replace('R', 'L');}}return dir;}

每日一题day82：困于环中的机器人（力扣1041）

大佬题解

class Solution {public boolean isRobotBounded(String instructions) {int k = 0;//表示位移int[] dist = new int[4];for(int i=0;i<instructions.length();i++){char c = instructions.charAt(i);if(c=='L'){k=(k+1)%4;}else if(c=='R'){k=(k+3)%4;}else{dist[k]++;}}return (dist[0] == dist[2] && dist[1] == dist[3]) || (k != 0);}
}