A 门牌制作
【问题描述】
小蓝要为一条街的住户制作门牌号。
这条街一共有 2020 位住户，门牌号从 1 到 2020 编号。
小蓝制作门牌的方法是先制作 0 到 9 这几个数字字符，最后根据需要将字
符粘贴到门牌上，例如门牌 1017 需要依次粘贴字符 1、 0、 1、 7，即需要 1 个
字符 0， 2 个字符 1， 1 个字符 7。
请问要制作所有的 1 到 2020 号门牌，总共需要多少个字符 2？
方法一
用数学方法思考，一直做模10运算，看每一位上是否有2。
public class Main {
public static void main(String[] args) {
int count = 0;
for(int i=1;i<=2020;i++){
int x =i;//定义一个变量x 替换i ，防止发生死循环
while(x>0){
if(x%10==2){//模10检查每一位是否为2，为2的话，计数器count+1
count++;
}
x=x/10;//x的位数减1，带入到下一次while循环中
}
}
System.out.println(count);//运行结果为624
}
}
但是我们要注意这里的一个坑，
for(int i = 1; i <= 2020; i++) {
while(i>0){
if(i%10==2)count++;
i/=10;
}
}
如果我们for循环里面这样写，那么本身i的值就会改变，比如i=10，当我们走完一遍循环后，i就成为了1，显然我们没有在for循环里找一个替代值，肯定是不对的
方法二
用String字符串的方法，先用String.valueof（）方法把int转为string型，然后用charAt方法看每一位是否有2
public static void main(String[] args) {
int num=0;
for (int i = 1; i <2021 ; i++) {
String s=String.valueOf(i);
for (int j = 0; j <s.length() ; j++) {
if (s.charAt(j)=='2'){
num++;
}
}
}
System.out.println(num);
}
答案：624
B寻找2020
【问题描述】
小蓝有一个数字矩阵，里面只包含数字 0 和 2。小蓝很喜欢 2020，他想找
到这个数字矩阵中有多少个 2020 。
小蓝只关注三种构成 2020 的方式：
• 同一行里面连续四个字符从左到右构成 2020。
• 同一列里面连续四个字符从上到下构成 2020。
• 在一条从左上到右下的斜线上连续四个字符，从左上到右下构成 2020。
例如，对于下面的矩阵：
220000
000000
002202
000000
000022
002020
一共有 5 个 2020。其中 1 个是在同一行里的， 1 个是在同一列里的， 3 个
是斜线上的。
小蓝的矩阵比上面的矩阵要大，由于太大了，他只好将这个矩阵放在了一
个文件里面，在试题目录下有一个文件 2020.txt，里面给出了小蓝的矩阵。
请帮助小蓝确定在他的矩阵中有多少个 2020。
思路
首先我们先把2020.txt文件里的数都复制过来（也可以用控制台输入，但是要先确认2020.txt文件有多少行），封装成String数组，然后我们再从头到尾遍历，先找到2，然后再横向竖向斜向下找，最后要记得要先找到边界
- 注意
单引号的数据是char类型，如char[] arr={‘a’,‘b’}; 为char类型。
双引号的数据是String类型，如String[] arr = {“a”,“b”,“c”}; 为string类型。
代码
public class 寻找2020 {
public static void main(String[] args) {
String str[]=new String[]{
"220000",
"000000",
"002202",
"000000",
"000022",
"002020",
};
System.out.println(Arrays.toString(str));
int count=0;
for (int i = 0; i <str.length ; i++) {
for (int j = 0; j <str[i].length() ; j++) {
if (str[i].charAt(j)=='2'){//横着
if(j+3<str[i].length()&&str[i].charAt(j+1)=='0'&&str[i].charAt(j+2)=='2'&&str[i].charAt(j+3)=='0'){
count++;
}
if (i<str.length-3&&str[i+1].charAt(j)=='0'&&str[i+2].charAt(j)=='2'&&str[i+3].charAt(j)=='0'){
count++;
}
if(j+3<str[i].length()&&i<str.length-3&&str[i+1].charAt(j+1)=='0'&&str[i+2].charAt(j+2)=='2'&&str[i+3].charAt(j+3)=='0'){
count++;
}
}
}
}
System.out.println(count);
}
}
答案：16520
C蛇形填数
【问题描述】
如下图所示，小明用从 1 开始的正整数“蛇形”填充无限大的矩阵。
1 2 6 7 15 …
3 5 8 14 …
4 9 13 …
10 12 …
11 …
…
容易看出矩阵第二行第二列中的数是 5。请你计算矩阵中第 20 行第 20 列的数是多少？
思路
由于是道填空题，所以我们可以先找到第k行第k列的规律，从1，5，13，25…我们可以看出第k个数都比前一个数大（k-1）*4，我们可以用递归来求出来第20个数的值
代码
注意一定要设置边界
public class 蛇形填数 {
public static void main(String[] args) {
System.out.println(f(20));
}
public static int f(int a){
if (a-1<=0){return 0;}
if (a==1){return 1;}
if (a==2){return 5;}
return f(a-1)+4*(a-1);
}
}
答案：761
D七段码
【问题描述】
小蓝要用七段码数码管来表示一种特殊的文字。
上图给出了七段码数码管的一个图示，数码管中一共有 7 段可以发光的二极管，分别标记为 a, b, c, d, e, f, g。
小蓝要选择一部分二极管（至少要有一个）发光来表达字符。在设计字符的表达时，要求所有发光的二极管是连成一片的。
例如：b 发光，其他二极管不发光可以用来表达一种字符。
例如：c 发光，其他二极管不发光可以用来表达一种字符。这种方案与上一行的方案可以用来表示不同的字符，尽管看上去比较相似。
例如：a, b, c, d, e 发光，f, g 不发光可以用来表达一种字符。
例如：b, f 发光，其他二极管不发光则不能用来表达一种字符，因为发光的二极管没有连成一片。
请问，小蓝可以用七段码数码管表达多少种不同的字符？
思路
每个数码管都有两种选择，亮或者不亮。其实就是{a, b, c, d, e, f, g}的所有子集，然后从所有子集中选出子集元素相通的，就是合法的。
先枚举所有子集，然后通过dfs看该子集元素是否相通。
代码
真的自己写不出来，网上参考了一下，这题放了
public class D七段码 {
static int n = 7;
static int ans = 0;
static int[][] map = new int[n][n];
public static void main(String[] args) {
//建立关系图
map[0][1] = 1;
map[0][5] = 1;
map[1][0] = 1;
map[1][2] = 1;
map[1][6] = 1;
map[2][1] = 1;
map[2][3] = 1;
map[2][6] = 1;
map[3][2] = 1;
map[3][4] = 1;
map[4][3] = 1;
map[4][5] = 1;
map[4][6] = 1;
map[5][0] = 1;
map[5][4] = 1;
map[5][6] = 1;
map[6][1] = 1;
map[6][2] = 1;
map[6][4] = 1;
map[6][5] = 1;
List<Integer> path = new ArrayList<Integer>();
dfs(path, 0);
System.out.println(ans);
}
private static void dfs(List<Integer> path, int k) {
if(k == n) {
// System.out.println(path);
if(check(path)) {
ans++;
}
return;
}
dfs(path, k + 1);
path.add(k);
dfs(path, k + 1);
path.remove(path.size() - 1);
}
private static boolean check(List<Integer> path) {
if(path.size() == 1) {
return true;
}
List<Integer> temp = new ArrayList<>(path);
if(!temp.isEmpty()) {
f(temp, temp.get(0));
}
return temp.isEmpty();
}
private static void f(List<Integer> temp, int cur) {
//一个元素的时候， map[i][i] == 0， 自己跟自己没关系。
for(int i = 0; i < n; i++) {
if(temp.contains(i) && map[cur][i] == 1) {
temp.remove((Integer)i);
f(temp, i);
}
}
}
}
E排序
【问题描述】
小蓝最近学习了一些排序算法，其中冒泡排序让他印象深刻。 在冒泡排序中，每次只能交换相邻的两个元素。小蓝发现，如果对一个字符串中的字符排序，只允许交换相邻的两个字符， 则在所有可能的排序方案中，冒泡排序的总交换次数是最少的。
例如，对于字符串 lan 排序，只需要 1 次交换。对于字符串 qiao 排序， 总共需要 4 次交换。
小蓝找到了很多字符串试图排序，他恰巧碰到一个字符串，需要 100 次交 换，可是他忘了吧这个字符串记下来，现在找不到了。
请帮助小蓝找一个只包含小写英文字母且没有字母重复出现的字符串，对 该串的字符排序，正好需要 100 次交换。如果可能找到多个，请告诉小蓝最短的那个。如果最短的仍然有多个，请告诉小蓝字典序最小的那个。请注意字符串中不可以包含相同的字符。
思路
因为是找最短的，所以我们可以假设都是按照逆顺序排列的，然后写一个简单的快排，加一个count计数器，我们可以看到：
- ‘n’,‘m’,‘l’,‘k’,‘j’,‘i’,‘h’,‘g’,‘f’,‘e’,‘d’,‘c’,‘b’,'a’时需要交换91次
- ‘o’,‘n’,‘m’,‘l’,‘k’,‘j’,‘i’,‘h’,‘g’,‘f’,‘e’,‘d’,‘c’,‘b’,'a’时需要交换105次
题目说的要找正好100次，还得是最短的，字典顺序最小的，所以我们可以根据第2组数据，找到第六个元素（因为前五个元素都要和他交换，还要保证字典序数最小）放到最左边就好了，也就是把j放到o左边。
代码
public class 排序 {
public static void main(String[] args) {
// Scanner sc=new Scanner(System.in);
//
// s=sc.next();
//char s[]=new char[]{'o','n','m','l','k','j','i','h','g','f','e','d','c','b','a'}; 105
//char s[]=new char[]{'n','m','l','k','j','i','h','g','f','e','d','c','b','a'};91
char s[]=new char[]{'j','o','n','m','l','k','i','h','g','f','e','d','c','b','a',};
int count=0;
for (int i = 0; i <s.length ; i++) {
for (int j = 0; j <s.length-i-1 ; j++) {
if (s[j] > s[j +1]) {
char temp = s[j];
s[j] = s[j + 1];
s[j + 1] = temp;
count++;
}
}
}
System.out.println(count);}
}
答案：jonmlkihgfedcba