骨骼 OV 挂经 求米安抚

这个可以用 dp 来做，定义 dp[i][k1][k2][k3][j][l] 代表考虑了数字1～i，i 还有k1个，i-1还有k2个，i-2还有k3个，以i结尾的顺子还有j个，有l个对子，是否是可行的。

每次转移可以选 2 个 i 组成对子，3个i组成碰子，给之前的顺子续命，以及三个连续数字组成新的顺子。
最后看 dp[n][0][0][0][0][1] 是否是合法的即可。

假设数字范围是 n，每个数字最多的数量是 k，状态数是 n*k^4*2

转移的时候选择给多少顺子续命是O(k)的，剩下都是O
(1)的，所以整体复杂度是O(n*k^5)

试了一下，确实想不到更好的解法了。。这时间复杂度似乎是exponential啊edit：因为有memo，应该是polynomial

1. def canHu(s: str) -> bool:
   
2.     n = len(s)
   
3.     card_count = [0 for i in range(10)]
   
4.     for i in range(n):
   
5.         card_count[int(s[i])] += 1
   
6. 
   
7.     def dfs(counts):
   
8.         print(counts)
   
9.         if sum(counts) == 0:
   
10.             return True
    
11.         str_form = ''
    
12.         for i in range(1, 10):
    
13.             str_form += str(counts[i])
    
14.         if str_form in memo:
    
15.             return False
    
16.         ans = False
    
17.         for i in range(1, 10):
    
18.             if counts[i] > 3:
    
19.                 counts[i] -= 3
    
20.                 ans = ans or dfs(counts)
    
21.                 counts[i] += 3
    
22.             if i >= 3 and counts[i] > 0 and counts[i - 1] > 0 and counts[i - 2] > 0:
    
23.                 counts[i] -= 1
    
24.                 counts[i - 1] -= 1
    
25.                 counts[i - 2] -= 1
    
26.                 ans = ans or dfs(counts)
    
27.                 counts[i] += 1
    
28.                 counts[i - 1] += 1
    
29.                 counts[i - 2] += 1
    
30.         if not ans:
    
31.             memo[str_form] = True
    
32.         return ans
    
33. 
    
34.     memo = {}
    
35.     for i in range(1, 10):
    
36.         if card_count[i] >= 2:
    
37.             card_count[i] -= 2
    
38.             if dfs(card_count):
    
39.                 return True
    
40.             card_count[i] += 2
    
41. 
    
42.     return False

复制代码

[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]

最近跳槽感觉国人如果不是大牛的话，在美国只有两种情况面试过的概率较高。

1. 大厂常规面试，面试官里国人多一些，或者遇到人比较nice的其他族裔面试官。
2. 不管什么厂，组里确实大量缺人的情况。

个人经验就是组里不缺人，再加上没有国人面试官基本就是面成啥样都挂。疫情期间第二条没了，基本纯拼运气了。

心态放平，move on吧。

zvzv1919 发表于 2020-7-31 13:38
诶，你那个greedy的话11111111算胡牌吗？

算..题目似乎没有要求说碰/顺子不能和pair重复数字 这应该是合法的吧

相位疯脸 发表于 2020-7-31 15:05
最近跳槽感觉国人如果不是大牛的话，在美国只有两种情况面试过的概率较高。

1. 大厂常规面试，面试官里 ...

很有道理。现在的bar真的比较高。

麻将似乎是贪婪题，先统计一下各个数字出现的次数，存放到int[] arr中
然后先找到> 2的数字，从arr中减去，对剩下的数字从小到大进行贪婪，总是优先满足顺子，没顺子了就看是否满足碰子。
这样的复杂度应该是O(NK)，因为已知道数字是1-9，所以就是O(N)复杂度
比如
11223344，先移除2个1，对剩余的数优先找顺子，就是234和234
再比如
12233333445，移除2个3，剩余的数就是123，234，345

[i][i][i][i][i][i][i][i][i][i][i][i][i]

1. private boolean nengHu(int[] arr){
   
2.         int[] majiang = new int[9];
   
3.         if((arr.length - 2) % 3!= 0) return false;
   
4.         for(int num : arr) majiang[num-1]++;
   
5.         for(int i=0;i<9;i++){
   
6.                 if(arr[i] >= 2){
   
7.                         int[] cp = Arrays.copyOfRange(majiang, 0, majiang.length);
   
8.                         cp[i] -=2;
   
9.                         if(helper(cp)) return true;
   
10.                 }
    
11.         }
    
12.         return false;
    
13. }
    
14. private boolean helper(int[] arr){
    
15.         for(int i=0;i<arr.length;i++){
    
16.                 while(arr[i] > 0){
    
17.                         if(i <= 7 && arr[i] > 0 && arr[i+1] > 0 && arr[i+2] > 0){
    
18.                                 arr[i]--;
    
19.                                 arr[i+1]--;
    
20.                                 arr[i+2]--;
    
21.                         } else if(arr[i] >= 3){
    
22.                                 arr[i]-=3;
    
23.                         } else return false;
    
24.                 }
    
25.         }
    
26.         return true;
    
27. }

复制代码

[/i][/i][/i][/i][/i][/i]
[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]

补充内容 (2020-8-3 02:00):
emmm，好像不对，不能从小到大选顺子
11222334455好像过不了，还是要穷举

ycj28c 发表于 2020-8-2 07:23
麻将似乎是贪婪题，先统计一下各个数字出现的次数，存放到int[] arr中
然后先找到> 2的数字，从arr中减去 ...

那如果input是个array of number 呢？也就是说，不是像麻将一样每次一定14张牌。

麻将的题目，试着写了一个。欢迎讨论。

1. def valid(count: dict):
   
2.     if not count:
   
3.         return True
   
4. 
   
5.     min_key = min(count.keys())  # should be quick enough since there are maximum 9 different digits. can use OrderedDict to save some time
   
6.     if count[min_key] >= 3:
   
7.         backup = s[min_key]
   
8.         count[min_key] -= 3
   
9.         if count[min_key] == 0:
   
10.             del count[min_key]
    
11.         if valid(count):
    
12.             return True
    
13.         count[min_key] = backup
    
14. 
    
15.     if min_key + 1 in count and min_key + 2 in count:
    
16.         for k in [min_key, min_key + 1, min_key + 2]:
    
17.             if count[k] == 1:
    
18.                 del count[k]
    
19.                 continue
    
20.             count[k] -= 1
    
21. 
    
22.         return valid(count)
    
23. 
    
24.     return False
    
25. 
    
26. 
    
27. def main(s: str):
    
28.     if (len(s) - 2) % 3 != 0:
    
29.         return False
    
30. 
    
31.     from collections import Counter
    
32. 
    
33.     s = [int(c) for c in s]
    
34. 
    
35.     counter = Counter(s)
    
36.     pairs = [k for k, v in counter.items() if v >= 2]
    
37. 
    
38.     for pair in pairs:
    
39.         backup = counter[pair]
    
40.         counter[pair] -= 2
    
41.         if counter[pair] == 0:
    
42.             del counter[pair]
    
43.         if valid(counter):
    
44.             return True
    
45.         counter[pair] = backup
    
46. 
    
47.     return False

复制代码

string 替换那个，嵌套的意思是这个吗？
例如%b -> bad
那么 %%%b ->%%bad -> %badad -> badadad ?

不好意思，楼主很久没有看帖子了。

其实是需要两个%%，所以是要替换两个%之间的值。
user -> user
1. 当你遇到%user%，就会替换成user。
2. 当你遇到%%user%%，第一步替换成%user%，第二步替换成user。