首页 > 阿里笔试 8.28 代码分享
头像
泼墨一纸江南
编辑于 2020-08-28 22:32
+ 关注

阿里笔试 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]++;
            }
        }
    }    
}

全部评论

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

相关热帖

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

近期精华帖

热门推荐