299.猜數字遊戲，新發明了詞兒——正負選擇
- 2020 年 3 月 11 日
- 筆記
這個題是簡單題，但裡面的思路很有意思，用到了反證法。
題目描述
你正在和你的朋友玩 猜數字（Bulls and Cows）遊戲：你寫下一個數字讓你的朋友猜。每次他猜測後，你給他一個提示，告訴他有多少位數字和確切位置都猜對了（稱為「Bulls」, 公牛），有多少位數字猜對了但是位置不對（稱為「Cows」, 奶牛）。你的朋友將會根據提示繼續猜，直到猜出秘密數字。
請寫出一個根據秘密數字和朋友的猜測數返回提示的函數，用 A 表示公牛，用 B 表示奶牛。
請注意秘密數字和朋友的猜測數都可能含有重複數字。
示例 1:
輸入: secret = "1807", guess = "7810" 輸出: "1A3B" 解釋: 1 公牛和 3 奶牛。公牛是 8，奶牛是 0, 1 和 7。
示例 2:
輸入: secret = "1123", guess = "0111" 輸出: "1A1B" 解釋: 朋友猜測數中的第一個 1 是公牛，第二個或第三個 1 可被視為奶牛。
說明: 你可以假設秘密數字和朋友的猜測數都只包含數字，並且它們的長度永遠相等。
解題
當我做這道題的時候，有點過分關注公牛和奶牛數量的統計，忽略掉了既不是公牛也不是奶牛的數量統計。
當然不是說僅僅關注公牛和奶牛的數量統計而不能得到答案，是因為我後面想到的一個優化，需要使用到其它性質的數字。
既然題目標籤是哈希表，而且題目描述挺適合使用直接定址表，使用的輸入示例都是0~9組成的，可以直接創建10個空間的數組，分別放置0~9。
直接定址表也是哈希表，適合於不是很散的範圍使用。
我們假設輸入示例是「1123」和「0111」，公牛數字的統計很簡單，遍歷一次，判斷相同位置上的數字是否相等；而奶牛數字的統計需要藉助兩個直接定址表，分別統計兩個輸入字元串中不是公牛數字的數量。
兩個直接定址表
但我想要一個直接定址表應該怎麼辦呢？
可以藉助既不是公牛也不是奶牛的數量統計。
還是剛才的示例「1123」和「0111」，在「1123」中可以看到『2』和『3』不屬於公牛數字和奶牛數字，可以統計到兩者不屬於的數量。
如果得到了公牛數量，也得到了兩者不屬於的數量，就可以得到奶牛的數量。
這是因為公牛數量 + 奶牛數量 + 兩者不屬於的數量，剛好等於一個字元串「1123」的長度。
既然是使用一個直接定址表，怎麼才能得到『2』和『3』呢？
這時候我們就需要一個正負判斷了，可以將「1123」中所有的數字都是正數，而「0111」中所有的數字都是負數。公牛數字在同一個位置上相等，而奶牛數字有了正負可以互相抵消掉了，剩下的就是不屬於公牛和奶牛的數字了。
正負選擇
前幾天分享的文章 (天際線問題 和 完美矩形) 也有類似的小技巧，正負選擇，例如遇左邊界 (正) ，高度入堆；遇右邊界 (負) ，高度出堆。
以後看題的時候，遇到類似的情況，一定要能巧妙地想到這點。
Java程式碼
class Solution { public String getHint(String secret, String guess) { int len = secret.length(); int A = 0; // 公牛數量 int B = 0; // 奶牛數量 // 創建直接定址表 int[] address = new int[10]; // secret和guess奶牛數字的相互抵消 for (int i = 0; i < len; i++) { if (secret.charAt(i) == guess.charAt(i)) A++; else { address[secret.charAt(i) - '0']++; address[guess.charAt(i) - '0']--; } } for (int addr : address) if (addr > 0) B += addr; B = len - A - B; return A + "A" + B + "B"; } }
Go語言程式碼
import ( "fmt" ) func getHint(secret string, guess string) string { len := len(secret) A := 0 // 公牛統計 B := 0 // 奶牛統計 // 創建直接定址表 address := [10]int{0} for i := 0; i < len; i++ { if secret[i] == guess[i] { A++ continue } address[secret[i]-'0']++ address[guess[i]-'0']-- } for _, addr := range address { if addr > 0 { B += addr } } B = len - A - B // 字元串拼接 return fmt.Sprint(A, "A", B, "B") }
Go語言執行結果
執行用時 : 0 ms , 在所有 Go 提交中擊敗了 100.00% 的用戶 記憶體消耗 : 2.3 MB , 在所有 Go 提交中擊敗了 75.00% 的用戶
Java提交之後，執行結果有點慘不忍睹，一度懷疑這演算法不是題目標籤中更優秀的演算法，可能前面提交的人太多，相同的執行用時已經趕不上前面的了。
為了Java和Golang有明顯的對比，Java就貼上執行用時和記憶體消耗。
執行用時 : 6 ms 記憶體消耗 : 38.4 MB
通過執行結果，Golang的執行用時差別不是很大，而消耗記憶體切實很省空間。
