生活随笔
收集整理的這篇文章主要介紹了
LeetCode 2151. 基于陈述统计最多好人数（状态压缩）
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
文章目錄
1. 題目
游戲中存在兩種角色：
- 好人：該角色只說真話。
- 壞人：該角色可能說真話，也可能說假話。
給你一個下標從 0 開始的二維整數數組 statements ，大小為 n x n ，表示 n 個玩家對彼此角色的陳述。
具體來說，statements[i][j] 可以是下述值之一：
- 0 表示 i 的陳述認為 j 是 壞人 。
- 1 表示 i 的陳述認為 j 是 好人 。
- 2 表示 i 沒有對 j 作出陳述。
另外，玩家不會對自己進行陳述。形式上，對所有 0 <= i < n ，都有 statements[i][i] = 2 。
根據這 n 個玩家的陳述，返回可以認為是 好人 的 最大 數目。
示例 1：
輸入：statements
= [[2,1,2],[1,2,2],[2,0,2]]
輸出：
2
解釋：每個人都做一條陳述。
- 0 認為
1 是好人。
- 1 認為
0 是好人。
- 2 認為
1 是壞人。
以
2 為突破點。
- 假設
2 是一個好人：
- 基于
2 的陳述，
1 是壞人。
- 那么可以確認
1 是壞人，
2 是好人。
- 基于
1 的陳述，由于
1 是壞人，那么他在陳述時可能：
- 說真話。在這種情況下會出現矛盾，所以假設無效。
- 說假話。在這種情況下，
0 也是壞人并且在陳述時說假話。
- 在認為
2 是好人的情況下，這組玩家中只有一個好人。
- 假設
2 是一個壞人：
- 基于
2 的陳述，由于
2 是壞人，那么他在陳述時可能：
- 說真話。在這種情況下，
0 和
1 都是壞人。
- 在認為
2 是壞人但說真話的情況下，這組玩家中沒有一個好人。
- 說假話。在這種情況下，
1 是好人。
- 由于
1 是好人，
0 也是好人。
- 在認為
2 是壞人且說假話的情況下，這組玩家中有兩個好人。
在最佳情況下，至多有兩個好人，所以返回
2 。
注意，能得到此結論的方法不止一種。
示例 2：
輸入：statements
= [[2,0],[0,2]]
輸出：
1
解釋：每個人都做一條陳述。
- 0 認為
1 是壞人。
- 1 認為
0 是壞人。
以
0 為突破點。
- 假設
0 是一個好人：
- 基于與
0 的陳述，
1 是壞人并說假話。
- 在認為
0 是好人的情況下，這組玩家中只有一個好人。
- 假設
0 是一個壞人：
- 基于
0 的陳述，由于
0 是壞人，那么他在陳述時可能：
- 說真話。在這種情況下，
0 和
1 都是壞人。
- 在認為
0 是壞人但說真話的情況下，這組玩家中沒有一個好人。
- 說假話。在這種情況下，
1 是好人。
- 在認為
0 是壞人且說假話的情況下，這組玩家中只有一個好人。
在最佳情況下，至多有一個好人，所以返回
1 。
注意，能得到此結論的方法不止一種。提示：
n
== statements
.length
== statements
[i
].length
2 <= n
<= 15
statements
[i
][j
] 的值為
0、
1 或
2
statements
[i
][i
] == 2
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximum-good-people-based-on-statements
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
2. 解題
- n比較小，把每個人是好人還是壞人的實際情況看成 int 的 n 位 01 二進制位
- 枚舉每種狀態，遍歷該狀態下的好人說的話有沒有矛盾的
class Solution {
public:int maximumGood(vector
<vector
<int>>& statements
) {int n
= statements
.size(), ans
= 0;for(int state
= 1; state
< (1<<n
); ++state
){bool stop
= false;int count
= 0;for(int j
= 0; j
< n
; ++j
){ if((state
>>j
)&1) {count
++;for(int k
= 0; k
< n
; ++k
){ if(statements
[j
][k
]<2){ if(statements
[j
][k
] == ((state
>>k
)&1) ) continue;else{stop
= true;break;}}}if(stop
)break;}}if(!stop
)ans
= max(ans
, count
);}return ans
;}
};
112 ms 8.2 MB C++
我的CSDN博客地址 https://michael.blog.csdn.net/
長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！
總結
以上是生活随笔為你收集整理的LeetCode 2151. 基于陈述统计最多好人数（状态压缩）的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
