阿里笔试 8.28 代码分享

1. 黑白切换 (ac)
   抱歉抱歉，贴的是交卷后自己又精简了的代码，当时有点迷糊，代码写错了。现在已修复，谢谢各位指正。
   思路是这样的：
   总共三个操作：交换，变值，翻转。
   交换一次可以变两个数字，而变值一次只可以变一个数字，所以优先交换。
   翻转也就多一次操作，所以比较一下考虑翻转和不考虑翻转的情况就行了。
   若不考虑翻转的话：
   在 A 串中有 n 个 '0' 需要变成 '1'， m 个 ‘1’ 需要变成 '0'. 那么交换 min(n, m) 次，之后还剩 max(n, m) - min(n, m) 个值需要变值。所以一共 max(n, m) 次。
   考虑翻转的话，就先翻转，再进行上述的操作。

   import java.util.*;
   public class Main{
     public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         int n = Integer.parseInt(sc.nextLine());
         String A = sc.nextLine();
         String B = sc.nextLine();
         System.out.print(new Solution().solve(n, A, B));
     }
   }
   class Solution{
     public int solve(int n, String A, String B) {
         int[] n1 = new int[2], n2 = new int[2];
         for(int i = 0; i < n; i++) {
             char c = A.charAt(i);
             if(c != B.charAt(i)) n1[c - '0']++;
             if(c != B.charAt(n - 1- i)) n2[c - '0']++;
         }
         return Math.min(Math.max(n1[0], n1[1]), Math.max(n2[0], n2[1]) + 1);
     }
   }

2. n 排列后能整除 m 的个数 (原代码 a 了0.4，这个刚要粘贴时间到了……不知道能不能a)
   ps1: 经评论区大佬指正，此代码实测超时，自闭……
   ps2: 评论区大佬指出 C++ 可以调用库函数 next_permutation 来做
   ps3: 等我想到方法再来更新，如果有大佬 a 了的请不吝赐教，感谢

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        int m = sc.nextInt();
        System.out.print(new Solution().solve(n, m));
    }
}

class Solution{
    int ans = 0;
    int m;
    public int solve(long n, int m) {
        this.m = m;
        int len = (n + "").length();
        int[] hash = new int[10];
        while(n != 0) {
            hash[(int)(n % 10)]++;
            n /= 10;
        }
        dfs(hash, len, 0, 0);
        return ans;
    }

    void dfs(int[] hash, int len, int index, int temp){
        if(index == len - 1) {
            if(temp % m == 0) ans++;
            return;
        }
        for(int i = 0; i < 10; i++) {
            if(index == 0 && i == 0) continue;
            if(hash[i] > 0) {
                hash[i]--;
                dfs(hash, len, index + 1, temp * 10 + i);
                hash[i]++;
            }
        }
    }    
}