最近工作還算是清閑醉者，也不用加班什么的厚者，所以有了大把時間刷題。直接開始吧晃琳。
隨即翻轉(zhuǎn)矩形
題目：題中給出一個 n_rows 行 n_cols 列的二維矩陣，且所有值被初始化為 0。要求編寫一個 flip 函數(shù)蝎土，均勻隨機的將矩陣中的 0 變?yōu)?1视哑，并返回該值的位置下標(biāo) [row_id,col_id]；同樣編寫一個 reset 函數(shù)誊涯，將所有的值都重新置為 0挡毅。盡量最少調(diào)用隨機函數(shù) Math.random()，并且優(yōu)化時間和空間復(fù)雜度暴构。
注意:
1 <= n_rows, n_cols <= 10000
0 <= row.id < n_rows 并且 0 <= col.id < n_cols
當(dāng)矩陣中沒有值為 0 時跪呈，不可以調(diào)用 flip 函數(shù)
調(diào)用 flip 和 reset 函數(shù)的次數(shù)加起來不會超過 1000 次
示例 1：
輸入:
["Solution","flip","flip","flip","flip"]
[[2,3],[],[],[],[]]
輸出: [null,[0,1],[1,2],[1,0],[1,1]]
示例 2：
輸入:
["Solution","flip","flip","reset","flip"]
[[1,2],[],[],[],[]]
輸出: [null,[0,0],[0,1],null,[0,0]]
輸入語法解釋：
輸入包含兩個列表：被調(diào)用的子程序和他們的參數(shù)。Solution 的構(gòu)造函數(shù)有兩個參數(shù)取逾，分別為 n_rows 和 n_cols耗绿。flip 和 reset 沒有參數(shù)，參數(shù)總會以列表形式給出砾隅，哪怕該列表為空
思路：這個題怎么說呢误阻，我好想是沒太看懂。而且這里說最少用random晴埂。最少就一次唄究反。先用我的理解去寫寫代碼試試吧。這種題目本來就是開放的儒洛。
好了精耐，第一版本代碼出來了，我先貼代碼：
class Solution {
Set<String> set;
int r;
int c;
public Solution(int n_rows, int n_cols) {
set = new HashSet<String>();
r = n_rows;
c = n_cols;
}
public int[] flip() {
int rr = new Random().nextInt(r);
int cc = new Random().nextInt(c);
while(set.contains(rr+","+cc)){
rr = new Random().nextInt(r);
cc = new Random().nextInt(c);
}
set.add(rr+","+cc);
return new int[]{rr,cc};
}
public void reset() {
set.clear();
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(n_rows, n_cols);
* int[] param_1 = obj.flip();
* obj.reset();
*/
沒啥技術(shù)含量琅锻，畢竟這種開放的題目對付實現(xiàn)就完事了卦停。但是我估計肯定是有更合適的做法。我去看下題解吧恼蓬。
class Solution {
Map<Integer, Integer> V = new HashMap<>();
int nr, nc, rem;
Random rand = new Random();
public Solution(int n_rows, int n_cols) {
nr = n_rows;
nc = n_cols;
rem = nr * nc;
}
public int[] flip() {
int r = rand.nextInt(rem--);
int x = V.getOrDefault(r, r);
V.put(r, V.getOrDefault(rem, rem));
return new int[]{x / nc, x % nc};
}
public void reset() {
V.clear();
rem = nr * nc;
}
}
我還特意去百度代碼中的一個方法：
getOrDefault(key, defaultValue)
意味如果有這個key惊完，則返回key對應(yīng)的value。如果沒有這個key处硬，則返回給定的defaultValue.簡單來說上面題目的思路是做Map映射小槐，如果key不存在，則取并且從尾部取值對應(yīng)到Key上郁油，如果key存在本股，取對應(yīng)的Value攀痊，并且把隨機范圍減一桐腌。這樣做到用一維的map來維護了n*c個元素的二維數(shù)組。
這個題我寫的挺無腦的苟径，答案挺精巧的案站。總而言之是個挺有意思的題棘街。學(xué)到的是一種新的思維方式蟆盐。就是map映射做跳表的思路承边。。下一題石挂。
最長特殊序列2
題目：給定字符串列表博助，你需要從它們中找出最長的特殊序列。最長特殊序列定義如下：該序列為某字符串獨有的最長子序列（即不能是其他字符串的子序列）痹愚。子序列可以通過刪去字符串中的某些字符實現(xiàn)富岳，但不能改變剩余字符的相對順序≌空序列為所有字符串的子序列窖式，任何字符串為其自身的子序列。輸入將是一個字符串列表动壤，輸出是最長特殊序列的長度。如果最長特殊序列不存在，返回 -1 疑苫。
示例：
輸入: "aba", "cdc", "eae"
輸出: 3
提示：
所有給定的字符串長度不會超過 10 肮帐。
給定字符串列表的長度將在 [2, 50 ] 之間。
思路：這個題怎么說呢肩碟，本身序列的題就比較復(fù)雜强窖。畢竟不是字面量，可以跳元素削祈。你就看著限制條件翅溺。字符串長度不會超過十∷枰郑總數(shù)小于50就能看出計算有多復(fù)雜咙崎。反正這種題目第一反應(yīng)是dp沒啥問題。至于狀態(tài)轉(zhuǎn)移方程我的慢慢去琢磨吨拍。大概的思路是每一個和其余的比找出特殊的序列褪猛。然后這些特殊的繼續(xù)往下比，應(yīng)該是個二維數(shù)組羹饰。我去試試吧伊滋。
算了，dp個屁队秩，我還是先用自己的方式對付實現(xiàn)了再說吧笑旺。就暴力破解了。
直接貼代碼：
class Solution {
public int findLUSlength(String[] strs) {
Arrays.sort(strs, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o1.length()>o2.length()?-1:1;
}
});
if(strs[0].length()>strs[1].length()) return strs[0].length();
for(int i = 0;i<strs.length;i++){
String res = strs[i];
for(int j = 0;j<strs.length;j++){
if(i==j) continue;
res = getDiff(res, strs[j]);
//說明這個元素沒有自己的子序列
if("".equals(res)) break;
}
if(!"".equals(res)) return res.length();
}
return -1;
}
public String getDiff(String a,String b) {
char[] aa = a.toCharArray();
int idx = 0;
for(char c:b.toCharArray()) {
//這個元素有了繼續(xù)往下對比
if(c==aa[idx]) {
//如果最后一個元素都比對完了說明這個序列不是唯一的馍资。返回空
if(idx==aa.length-1) return "";
idx++;
}
}
//到這還沒返回說明這個子序列 b中沒有筒主，暫時算是特殊的
return a;
}
}
我簡直呵呵了，性能百分百過的。我為什么會覺得這道題要dp乌妙？怕不是腦子進了水了使兔。生生想了半個多小時到懷疑人生。
這個題簡單的很藤韵，思路主要是：一個串中有特殊序列虐沥，那么這整個串一定是特殊的。有點心累泽艘，不想多說話置蜀，下一題吧。
連續(xù)的子序組合
題目：給定一個包含 非負(fù)數(shù) 的數(shù)組和一個目標(biāo) 整數(shù) k悉盆，編寫一個函數(shù)來判斷該數(shù)組是否含有連續(xù)的子數(shù)組盯荤，其大小至少為 2，且總和為 k 的倍數(shù)焕盟，即總和為 n*k秋秤，其中 n 也是一個整數(shù)。
示例 1：
輸入：[23,2,4,6,7], k = 6
輸出：True
解釋：[2,4] 是一個大小為 2 的子數(shù)組脚翘，并且和為 6灼卢。
示例 2：
輸入：[23,2,6,4,7], k = 6
輸出：True
解釋：[23,2,6,4,7]是大小為 5 的子數(shù)組，并且和為 42来农。
說明：
數(shù)組的長度不會超過 10,000 鞋真。
你可以認(rèn)為所有數(shù)字總和在 32 位有符號整數(shù)范圍內(nèi)。
思路：這個題感覺最暴力的就是每一個數(shù)開始往后加沃于。但是感覺暴力法會有問題涩咖。但是我要去試試。
第一版本暴力法解出來了繁莹，我先貼代碼：
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
if(k==0) {
for(int i=0;i<nums.length-1;i++){
if(nums[i] == nums[i+1] && nums[i] == 0) return true;
}
return false;
}
for(int i = 0;i<nums.length;i++) {
int sum = nums[i];
for(int j = i+1;j<nums.length;j++) {
sum += nums[j];
if(sum%k == 0) return true;
}
}
return false;
}
}
怎么說呢檩互，現(xiàn)在越來越懶得寫題解了，感覺有的題目比較簡單咨演，沒啥好說的闸昨，太難的又說不明白。反正這道題面向測試案例編程薄风。給出的結(jié)果中0,0 k=0的話也是true饵较。所以有了第一個key=0的特殊處理。性能超過百分之五十遭赂。估計是有更好的做法循诉。但是我沒精力想了，直接去看性能排行第一的代碼：
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
int sum = 0, n = nums.length;
for (int i = 0; i < n; i++) {
sum += nums[i];
int v = k != 0 ? sum % k : sum == 0 ? 0 : sum;
Integer o = map.put(v, i);
if (o != null) {
if (i - o > 1) return true;
map.put(v, o);
}
}
return false;
}
}
這個題的題解我覺得超級贊的一個思路嵌牺。但是人家官方的說法太不好理解了打洼。我自己的想法就是：
sum%k = n. （sum+（x+y+z+...））%k =n。
我是不是可以理解x+y+z+...本身被k整除了逆粹？只要確定這個x.y,z..的數(shù)量大于2募疮，就說明出現(xiàn)了能大于2的k的倍數(shù)（這個題坑的一點是哪怕1，-1或者0,0這種也算正確答案僻弹。）反正數(shù)學(xué)我也就這樣了阿浓，什么取模對數(shù)啥的也心有余力不足了。用自己的方式能理解就挺好了蹋绽。下一題芭毙。
通過刪除字母匹配到字典里最長單詞
題目：給定一個字符串和一個字符串字典，找到字典里面最長的字符串卸耘，該字符串可以通過刪除給定字符串的某些字符來得到退敦。如果答案不止一個，返回長度最長且字典順序最小的字符串蚣抗。如果答案不存在侈百，則返回空字符串。
示例 1:
輸入:
s = "abpcplea", d = ["ale","apple","monkey","plea"]
輸出:
"apple"
示例 2:
輸入:
s = "abpcplea", d = ["a","b","c"]
輸出:
"a"
說明:
所有輸入的字符串只包含小寫字母翰铡。
字典的大小不會超過 1000钝域。
所有輸入的字符串長度不會超過 1000。
思路：第一反應(yīng)就是判斷這個單詞是不是給定字符串的子序列锭魔。其實也就是暴力遍歷法例证。找到最長的那個子序列。相同長度取排位靠前的迷捧。就是這樣织咧，我去試試能不能過。
翻車的地方莫名其妙漠秋。字典順序最小的字符串烦感。我本來以為是在數(shù)組中排名靠前的呢。我去把這一塊改了
貼代碼:
class Solution {
public String findLongestWord(String s, List<String> d) {
String res = "";
int max = 0;
for(String dd:d) {
if(isOk(s, dd)) {
//是子序列,直接取最大的
if(max<dd.length()) {
max = dd.length();
res = dd;
}else if(max == dd.length()) {//相同長度取字典順序最小的
res = dd.compareTo(res)<0?dd:res;
}
}
}
return res;
}
//判斷是不是子序列
public boolean isOk(String s,String d) {
char[] c = d.toCharArray();
int idx = 0;
for(char ss : s.toCharArray()) {
if(ss==c[idx]) {
idx++;
//d中所有元素s中都有膛堤，所以直接返回true
if(idx == c.length) return true;
}
}
return false;
}
}
這個沒什么好說的手趣。就是暴力破解。用到了兩個方法：一個是判斷一個字符串是不是另一個字符串的子序列肥荔。還有就是字符串字典順序比較绿渣。我這里直接調(diào)用的內(nèi)置函數(shù)compareTo。想自己寫就拆開比較就ok了燕耿，也沒啥難度就是比較墨跡中符、這個題就這樣了，下一題誉帅。
連續(xù)數(shù)組
題目：給定一個二進制數(shù)組, 找到含有相同數(shù)量的 0 和 1 的最長連續(xù)子數(shù)組（的長度）淀散。
示例 1:
輸入: [0,1]
輸出: 2
說明: [0, 1] 是具有相同數(shù)量0和1的最長連續(xù)子數(shù)組右莱。
示例 2:
輸入: [0,1,0]
輸出: 2
說明: [0, 1] (或 [1, 0]) 是具有相同數(shù)量0和1的最長連續(xù)子數(shù)組。
注意: 給定的二進制數(shù)組的長度不會超過50000档插。
思路：不知道為啥這個題沒有任何時間空間的約束慢蜓。反正暴力法就是數(shù)組最長才5w。我的想法就是建立一個list（因為不定長所以不用數(shù)組了）郭膛。然后0的出現(xiàn)個數(shù)統(tǒng)計晨抡，1的出現(xiàn)個數(shù)統(tǒng)計。就這樣往下統(tǒng)計下去则剃。最后遍歷list找到連續(xù)兩個數(shù)的較小的值中的最大值耘柱。說起來比較繞，但是我覺得實現(xiàn)起來還是很容易的棍现。我去試試了调煎。
好吧，是我沒理解題意己肮。這里0,1汛蝙，0，1我以為結(jié)果是2.但是沒想到這樣是4朴肺，所以上面的思路推翻重試窖剑。暴力法就不合適了。我想想怎么實現(xiàn)吧戈稿。
我覺得我思路賊精巧西土，還好這兩道題挨在一起了所以找到了思路。但是性能不咋地鞍盗。我先附上代碼：
class Solution {
public int findMaxLength(int[] nums) {
for(int i = 0;i<nums.length;i++){
if(nums[i]==0) nums[i]=-1;
}
//找到和為0的最長子序列(和上一道題類似)
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
map.put(0,-1);//默認(rèn)就是0了需了。
int sum = 0;
int max = 0;
for(int i = 0;i<nums.length;i++){
sum += nums[i];
//當(dāng)再次出現(xiàn)和是sum，說明中間累加這么多和為0.也就是1和-1數(shù)目相等
if(map.containsKey(sum)) {
max = Math.max(max, i-map.get(sum));
}else {
map.put(sum,i);//第一次出現(xiàn)和是sum的情況般甲。
}
}
return max;
}
上一道題也是這個思路肋乍，我覺得我注釋寫的比較清楚了。真的這兩道題安排在一起幫了我敷存。我再去看看性能排行第一的代碼：
class Solution {
public int findMaxLength(int[] nums) {
if (null == nums || nums.length < 2) {
return 0;
}
int length = nums.length;
int mappingLength = 2 * length + 1;
int[] mapping = new int[mappingLength];
for (int i = 0; i < mappingLength; i++) {
mapping[i] = -2;
}
mapping[length] = -1;
int maxLength = 0;
int count = 0;
for (int i = 0; i < length; i++) {
count += 2 * nums[i] - 1;
if (mapping[count + length] >= -1) {
maxLength = Math.max(maxLength, i - mapping[count + length]);
} else {
mapping[count + length] = i;
}
}
return maxLength;
}
}
本質(zhì)上和我的思路是一樣的墓造。不過我把0賦值為-1了。而這里用的是2 * nums[i] - 1锚烦、算出來還是1就+1.0就-1觅闽。
區(qū)別就是我用的map存儲。而這里用數(shù)組存儲了涮俄。其實我覺得就是用空間換時間嘛蛉拙。不是很驚喜。這道題就這樣了彻亲。
這篇筆記就記到這里孕锄，如果稍微幫到你了記得點個喜歡點個關(guān)注吮廉。也祝大家工作順順利利！生活愉快畸肆！
