Last Updated on 2022-03-20 by Clay
題目
In a row of dominoes, tops[i] and bottoms[i] represent the top and bottom halves of the ith domino. (A domino is a tile with two numbers from 1 to 6 - one on each half of the tile.)
We may rotate the ith domino, so that tops[i] and bottoms[i] swap values.
Return the minimum number of rotations so that all the values in tops are the same, or all the values in bottoms are the same.
If it cannot be done, return -1.
Example 1:
Input: tops = [2,1,2,4,2,2], bottoms = [5,2,6,2,3,2] Output: 2 Explanation: The first figure represents the dominoes as given by tops and bottoms: before we do any rotations. If we rotate the second and fourth dominoes, we can make every value in the top row equal to 2, as indicated by the second figure.
Example 2:
Input: tops = [3,5,1,2,3], bottoms = [3,6,3,3,4] Output: -1 Explanation: In this case, it is not possible to rotate the dominoes to make one row of values equal.
Constraints:
2 <= tops.length <= 2 * 104bottoms.length == tops.length1 <= tops[i], bottoms[i] <= 6
題目會給 tops 和 bottoms 兩個列表，列表中儲存的數字代表骰子的點數；我們要做的，就是看如何交換才能以最少的步驟讓其中一個列表的點數全部相同。
如果不存在可以讓列表點數相同的方法，則回傳 -1。
解題思路
這題我真的沒有想到特別好的解法，只有一個 brute force 的暴力解、以及優化一點這個暴力解的寫法。
如過有更好的解法，歡迎隨時提供給我！非常感謝！
Brute Force
首先，把所有點數都試試看能否排成同一列表全部相同，與此同時紀錄需要交換骰子點數的次數；除了 tops 需要計算外、也需要把 bottoms 計算一次。
我在程式碼中使用了 hash map 來記錄該點數是否已經被計算過，計算過的點數可以跳過；不過由於骰子只存在六種點數、十分固定，所以空間複雜度我直接算 O(1)。
當然，正是因為程式碼實在太長了，所以我還是想辦法優化了程式碼的行數與可讀性。
Brute Force 複雜度
| Time complexity | O(n) |
| Space complexity | O(1) |
Brute Force C++ 範例程式碼
class Solution {
public:
int minDominoRotations(vector<int>& tops, vector<int>& bottoms) {
// Init
int minTried = INT_MAX;
unordered_map<int, int> used;
// Find the mini-steps method
for (int prob: tops) {
int temp = 0;
bool isBreak = false;
if (used.count(prob)) continue;
else used[prob] = 1;
for (int i=0; i<tops.size(); ++i) {
if (tops[i] != prob) {
// If bottom can exchange, increase the `temp` variable
if (bottoms[i] == prob) {
++temp;
}
// If top and bottom is not equal to prob[i], break out the matching
else {
isBreak = true;
break;
}
}
}
if (!isBreak) {
// Maybe we rotate bottoms is faster than tops
temp = min(temp, int(tops.size()-temp));
// Minimum
minTried = min(minTried, temp);
}
}
// Use Bottom to calculation
used.clear();
// Find the mini-steps method
for (int prob: bottoms) {
int temp = 0;
bool isBreak = false;
if (used.count(prob)) continue;
else used[prob] = 1;
for (int i=0; i<bottoms.size(); ++i) {
if (bottoms[i] != prob) {
// If bottom can exchange, increase the `temp` variable
if (tops[i] == prob) {
++temp;
}
// If top and bottom is not equal to prob[i], break out the matching
else {
isBreak = true;
break;
}
}
}
if (!isBreak) {
// Maybe we rotate bottoms is faster than tops
temp = min(temp, int(tops.size()-temp));
// Minimum
minTried = min(minTried, temp);
}
}
// If the minTried is still `INT_MAX`, that means it cannot be done
if (minTried == INT_MAX) return -1;
else return minTried;
}
};Brute Force Python 範例程式碼
class Solution:
def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:
# Init
min_tried = 20001
used = dict()
# Find the mini-steps method
for prob in tops:
temp = 0
isBreak = False
if used.get(prob, 0) == 1: continue
else: used[prob] = 1
for i in range(len(tops)):
if tops[i] != prob:
# If bottom can exchange, increase the `temp` variable
if bottoms[i] == prob:
temp += 1
# If top and bottom is not equal to prob[i], break out the matching
else:
isBreak = True
break
if not isBreak:
min_tried = min(min_tried, temp)
# Use Bottom to calculation
used.clear()
# Find the mini-steps method
for prob in bottoms:
temp = 0
isBreak = False
if used.get(prob, 0) == 1: continue
else: used[prob] = 1
for i in range(len(bottoms)):
if bottoms[i] != prob:
# If tops can exchange, increase the `temp` variable
if tops[i] == prob:
temp += 1
# If top and bottom is not equal to prob[i], break out the matching
else:
isBreak = True
break
if not isBreak:
min_tried = min(min_tried, temp)
# If the minTried is still `INT_MAX`, that means it cannot be done
return -1 if min_tried == 20001 else min_tried
優化解法
直接記算兩列表中的不同點數出現次數、以及兩列表剛好出現同個點數的次數。因為這樣一來，我們可以透過相加兩列表中不同點數出現次數再減去剛好出現相同的次數是否等於列表長度，來判斷是否可以完成交換。
有點繞口，不過簡單來說，假設 AB 列表一共有 6 個點數，其中 2 的點數 A 出現了 4 次，B 出現了 3 次，而 AB 剛好都為 2 的次數有 1 次。
A[2] = 4 B[2] = 3 SAME[2] = 1 4 + 3 - 1 = 6 (是可以交換成列表中都是同樣點數的！)
接著就是跟第一種解法一樣，紀錄最短的交換次數即可。
其實跟第一種解法非常相似，只是多了紀錄出現相同點數的次數這個步驟，讓本來需要判斷兩次的程式碼簡化成了一次。
優化解法複雜度
同樣，只使用了固定長度為 6 的列表儲存，同樣視為空間複雜度 O(1)。
| Time complexity | O(n) |
| Space complexity | O(1) |
優化解法 C++ 範例程式碼
class Solution {
public:
int minDominoRotations(vector<int>& tops, vector<int>& bottoms) {
// Init
int minRotation = INT_MAX;
vector<int> topNums(6, 0);
vector<int> bottomNums(6, 0);
vector<int> sameNums(6, 0);
// Count the Domino numbers
for (int i=0; i<tops.size(); ++i) {
++topNums[tops[i]-1];
++bottomNums[bottoms[i]-1];
if (tops[i] == bottoms[i]) {
++sameNums[tops[i]-1];
}
}
// Find the minimum numbers of rotations
for (int i=0; i<6; ++i) {
if (topNums[i]+bottomNums[i]-sameNums[i] == tops.size()) {
int temp = min(topNums[i]-sameNums[i], bottomNums[i]-sameNums[i]);
minRotation = min(minRotation, temp);
}
}
// If minRotation is equal to `INT_MAX`, it means it cannot be done
return minRotation == INT_MAX ? -1 : minRotation;
}
};優化解法 Python 範例程式碼
class Solution:
def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:
# Init
minRotation = 20001
topNums = [0 for _ in range(6)]
bottomNums = [0 for _ in range(6)]
sameNums = [0 for _ in range(6)]
# Count the Domino numbers
for i in range(len(tops)):
topNums[tops[i]-1] += 1
bottomNums[bottoms[i]-1] += 1
if tops[i] == bottoms[i]:
sameNums[tops[i]-1] += 1
# Find the minimum numbers of rotations
for i in range(6):
if topNums[i]+bottomNums[i]-sameNums[i] == len(tops):
temp = min(topNums[i]-sameNums[i], bottomNums[i]-sameNums[i])
minRotation = min(minRotation, temp)
# If minRotation is equal to `INT_MAX`, it means it cannot be done
return -1 if minRotation == 20001 else minRotation;