JavaInterview JavaInterview
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)

『Java面试+Java学习』
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)
  • 指南
  • 简历

  • Java

  • 面试

  • 算法

  • algorithm
  • leetcode
JavaInterview.cn
2022-10-13
目录

变为棋盘Java

文章发布较早,内容可能过时,阅读注意甄别。

# 题目

一个 n x n 的二维网络 board 仅由 0 和 1 组成 。每次移动,你能任意交换两列或是两行的位置。

返回 将这个矩阵变为  “棋盘”  所需的最小移动次数 。如果不存在可行的变换,输出 -1。

“棋盘” 是指任意一格的上下左右四个方向的值均与本身不同的矩阵。

示例 1:

输入: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]
输出: 2
解释:一种可行的变换方式如下,从左到右:
第一次移动交换了第一列和第二列。
第二次移动交换了第二行和第三行。

示例 2:

输入: board = [[0, 1], [1, 0]]
输出: 0
解释: 注意左上角的格值为0时也是合法的棋盘,也是合法的棋盘.

示例 3:

输入: board = [[1, 0], [1, 0]]
输出: -1
解释: 任意的变换都不能使这个输入变为合法的棋盘。

提示:

  • n == board.length
  • n == board[i].length
  • 2 <= n <= 30
  • board[i][j] 将只包含 0或 1

# 思路

// 状压后满足下列条件: 必须只有两个数且这两个数异或全为1 如果两个数数量不等,必须以数量大的开头,然后比较错误的顺序数即可

# 解法


class Solution {
    // 状压后满足下列条件: 必须只有两个数且这两个数异或全为1 如果两个数数量不等,必须以数量大的开头,然后比较错误的顺序数即可


    public int movesToChessboard(int[][] board) {

        int n = board.length,res = 0;
        int[] x = new int[n],y = new int[n];
        Map<Integer,Integer> m = new HashMap<>();
        Map<Integer,Integer> f = new HashMap<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(board[i][j]==1)
                    x[i]|=1<<j;
            }
            Integer integer = m.getOrDefault(x[i],0);
            m.put(x[i],integer+1);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(board[j][i]==1)
                    y[i]|=1<<j;
            }
        }
        for (int i = 0; i < n; i++) {
            Integer integer = f.getOrDefault(y[i],0);
            f.put(y[i],integer+1);
        }
        int exchangex = exchangex(m, x);
        int exchangey = exchangex(f, y);
        if(exchangey==-1||exchangex==-1)return -1;
        return exchangex+exchangey;
    }

    private int exchangex(Map<Integer, Integer> m, int[] x) {
        int size = m.size();
        if(size!=2)return -1;
        int max = 0,min = 10000,first = 0,res = 0,n = x.length;
        for (Map.Entry<Integer, Integer> entry : m.entrySet()) {
            Integer value = entry.getValue();
            if(max<value)
                first = entry.getKey();
            max = Math.max(value,max);
            min = Math.min(value,min);
        }
        if(max-min>1||m.get(first ^ ((1 << n) - 1))==null)return -1;
        first = max==min?x[0]:first;
        res = getLres(x, first, n);
        if(max==min)
            res = Math.min(getLres(x, first ^ ((1<<n)-1), n),res);
        return res>>1;
    }
    private  int getLres(int[] x, int first, int n) {
        int lres = 0;
        for (int i = 0; i < n; i++) {
            if((i&1)==0){
                if(first != x[i])
                    lres++;
            }else {
                if(first == x[i])
                    lres++;
            }
        }
        return lres;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

# 总结

  • 分析出几种情况,然后分别对各个情况实现
微信 支付宝
最近更新
01
1686. 石子游戏VI Java
09-07
02
1687. 从仓库到码头运输箱子 Java
09-07
03
1688. 比赛中的配对次数 Java
09-07
更多文章>
Theme by Vdoing | Copyright © 2019-2025 JavaInterview.cn
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式