fucking-algorithm
fucking-algorithm copied to clipboard
Published
20 hours ago •
labuladong
labuladong
谁能想到，斗地主也能玩出算法 :: labuladong的算法小抄
class Solution {
public boolean isPossible(int[] nums) {
HashMap<Integer,Integer> freq = new HashMap<>();
HashMap<Integer,Integer> need = new HashMap<>();
// 统计 nums 中元素的频率
for(int n:nums){
freq.put(n,freq.getOrDefault(n,0)+1);
}
for(int n:nums){
// 已经被用到其他子序列中(排除)
if(freq.get(n)==0) continue;
// 先判断 n 是否能接到其他子序列后面
if(need.containsKey(n) && need.get(n)>0){
// n 可以接到之前的某个序列后面
//对n的需求减一
need.put(n,need.get(n)-1);
freq.put(n,freq.get(n)-1);
//对n+1的需求加一
need.put(n+1,need.getOrDefault(n+1,0)+1);
}else if(freq.containsKey(n)&& freq.containsKey(n+1)&&freq.containsKey(n+2)
&& freq.get(n)>0 && freq.get(n+1)>0 && freq.get(n+2)>0){
// 将 n 作为开头，新建一个长度为 3 的子序列 [n,n+1,n+2]
freq.put(n,freq.get(n)-1);
freq.put(n+1,freq.get(n+1)-1);
freq.put(n+2,freq.get(n+2)-1);
// 对 n + 3 的需求加一
need.put(n+3,need.getOrDefault(n+3,0)+1);
} else{
// 两种情况都不符合，则无法分配
return false;
}
}
return true;
}
}
java版
补充一个使用贪心算法的方式，此方式优点难以理解，需要结合图和我写的注释理解
class Solution {
public boolean isPossible(int[] nums) {
HashMap<Integer,Integer> freq = new HashMap<>();//统计频率
for(int i: nums){
freq.put(i,freq.getOrDefault(i,0)+1);
}
for(int i : nums){
int subNumb = 0;//子数组中元素个数
//往子数组中后面加的数的频率最低为 1
int p = 1;
while(freq.getOrDefault(i,0)>= p){
// 频率为1的可以进这个循环 加到子数组后面
//如果频率大于1， 只能加到子数组里面一个，因为一开始p=1，后面p更新为了原来的频率 > 1
//将p（原来的频率） 和 选用后剩余的频率比较，确实无法进入循环向子数组后面添加了
//需要开辟一个新的子数组
p = freq.get(i);//获取当前元素的 频率
freq.put(i,p-1);//当前元素已经被选用了 频率减一
subNumb++;//子数组长度+1
i++;
}
if(subNumb>0 && subNumb<3){
return false;
}
}
return true;
}
}
js版
/**
* @param {number[]} nums
* @return {boolean}
*/
var isPossible = function (nums) {
// 这题比较特殊 使用2个哈希表来解决
// freq[v]表示每个数字出现的次数 need[v]表示v可以添加到上一个子串的末尾的次数
// 在分子序列遍历到某个数字的时候 可能有两种情况
// 1. 自成一派 自己开头 成为连续3个数字的第一个
// 2. 和前面的连接上
// 这两种情况应该优先选择第2种
const freq = new Map();
const need = new Map();
// 统计出现次数
nums.forEach(n => {
if (freq.has(n)) {
freq.set(n, freq.get(n)+1);
} else {
freq.set(n, 1);
}
})
// 注意是nums
for (let n of nums) {
// 这个数字已经被接入其他子序列 用过了
if (freq.get(n) === 0) {
continue;
}
// 看看是否可以接入之前的序列
if (need.has(n) && need.get(n) > 0) {
// 从freq和need中减少一次计数
freq.set(n, freq.get(n) - 1);
need.set(n, need.get(n) - 1);
// 对于下一个数字 是有需求接入这个子序列的
need.set(n + 1, (need.get(n + 1) || 0) + 1);
} else if (freq.get(n) && freq.get(n + 1) && freq.get(n + 2)) {
// 不能接入之前的 看看是否可以自成一派
// 连续三个数字
freq.set(n, freq.get(n) - 1);
freq.set(n + 1, freq.get(n + 1) - 1);
freq.set(n + 2, freq.get(n + 2) - 1);
// 三个之后的数字 可以有接入这个序列的需求
need.set(n + 3, (need.get(n + 3) || 0) + 1);
} else {
// 都不行 就真不行了 分不了了
return false
}
}
return true;
};
bool isPossible(vector<int>& nums) {
vector<unordered_set<int>> caches;
caches.push_back(unordered_set<int>{nums[0]});
for (int i = 1; i < nums.size(); i++) {
bool handled = false;
for (int j = caches.size() - 1; j >= 0; j--) {
// 序列中已经有该值了
if (caches[j].count(nums[i])) continue;
// 序列中没有该值，但是不连续了
if (!caches[j].count(nums[i] - 1)) break;
// 序列连续，插入值
caches[j].insert(nums[i]);
handled = true;
break;
}
//如果值没有被处理，另外新建一个序列
if (!handled) {
caches.push_back(unordered_set<int>{nums[i]});
}
}
for (auto cache: caches) {
if (cache.size() < 3) return false;
}
return true;
}
东哥，想请教一下为什么一个数要优先判断自己是否可以接在已有的序列之后呢？有没有一种情况是必须让某个数称为开头才可以满足条件呢？优先判断接在已有序列之后是一种贪心的思想么？
@Rasadell09 我的理解是如果一个数是接在已有序列之后，肯定能满足条件，因为已有序列中元素数量肯定>=3。而一个数自己开头的却不一定能满足条件。所以不会出现必须让某数开头才能满足条件的情况，因此优先判断是否能接在已有序列之后。
补充一个新思路吧。因为题目说了原始数组是已排序的，所以感觉可以按顺序扫描，然后根据不同情况来做不同的操作。代码是基于 Python 的，里面的解释比较长，因为是从比较朴素的实现方法开始一步步探讨到优化后的方法。
class Solution:
"""
659. Split Array into Consecutive Subsequences
因为题目说了原始数组是已排序的，所以感觉可以按顺序扫描。
遇到正常 +1 的情况时，加入当前序列。
遇到相同的数字时，可能需要新开一个序列，也可能可以加入之前已有的序列末尾。
例如 [1,1,2,2]，遇到重复的 1 就要新开一个序列，而遇到重复的 2 就可以加入序列 [1] 的末尾。
遇到跳跃的数字时，就肯定需要新开一个序列。
所以，根据以上推理，可能需要同时维护多个序列。
并且还要知道当前扫描到的元素需要加到哪个序列尾部，所以可能要用哈希表。
例如当前扫描到的元素是 k，那就需要找到所有以 k - 1 结尾的序列。
当一个元素有多个候选序列可以放入时，为了满足“所有序列的长度都大于等于三”的条件，
就应该优先选择短的候选序列放入，所以还需要知道每个候选序列的长度。
最简单的办法是每次都对所有候选序列调用 len() 函数求长度，然后找到最短的，但是这样很耗时。
想优化一下，可以用一个最小堆 min-heap 来存储，以数组长度作为排序的 key，这样就能减少每次寻找最短候选序列的时间。
综上所述，需要一个哈希表记录不同末尾元素的序列，
哈希表中的每一个键值对 (k, min_heap_k) 表示以 k 结尾的序列都存在了 min_heap_k 中。
min_heap_k 是一个最小堆，其中的每一个元素都是以 k 结尾的序列，此最小堆排序的 key 是序列的长度。
写到这里，发现其实我只关心每个序列的末尾元素，以及每个序列的长度，
所以其实不需要存储整个序列，只需要存末尾元素和长度即可，这样能节省不少空间;
然后又发现，其实末尾元素已经是由 k 指定了的，即必然是 k，所以只需要存储长度即可。
可以再进一步化简代码，前面讨论了按顺序扫描时会遇到的 3 种情况，分别是正常加一、重复、跳跃。
三种情况有不同的处理逻辑，可能是把元素添加到已有序列的末尾，也可能是用元素新开一个序列，
需要写很多 `if ... else ...` 判断。
但是可以发现，用某个元素新开一个序列，实际上可以看作是把这个元素添加到一个空序列的末尾。
所以可以在扫描到元素 k 时，从哈希表中获取以 k 结尾的候选序列集合 S。
若集合 S 不是空集，那就返回长度最小的那个候选序列；若集合 S 是空集，返回一个空序列作为长度最小的候选序列。
这样我就只需要写“把元素加到对应序列末尾”的代码逻辑。
写于 2022-08-19 10:52:41
"""
def isPossible(self, nums: List[int]) -> bool:
if len(nums) < 3:
return False
map_min_heap_k = {}
# 第一个元素的处理先单独写出来，后面直接写循环，就不用再判断是否是第一个
map_min_heap_k[nums[0]] = [1]
nums = nums[1:]
# 顺序扫描剩余元素
for k in nums:
if k not in map_min_heap_k:
map_min_heap_k[k] = []
if (k - 1) not in map_min_heap_k:
map_min_heap_k[k - 1] = []
min_heap_k_minus_1 = map_min_heap_k[k - 1] # 找到以 k - 1 结尾的所有序列
min_len_k_minus_1 = heapq.heappop(min_heap_k_minus_1) if len(min_heap_k_minus_1) > 0 else 0 # 选出长度最短的
min_heap_k = map_min_heap_k[k] # 找到存储以 k 结尾的所有序列的 min_heap_k
heapq.heappush(min_heap_k, min_len_k_minus_1 + 1) # 把之前以 k - 1 结尾的最短序列的长度加 1，插入 min_heap_k 中
# print(k, map_min_heap_k)
flag = True
for k in map_min_heap_k:
for l in (map_min_heap_k[k]):
if l < 3:
flag = False
break
if flag is False:
break
return flag
a = Solution()
b = a.isPossible([1,2,3])
print(True, b)
b = a.isPossible([1,2,3,3,4,5])
print(True, b)
b = a.isPossible([1,1,2,2,3,3])
print(True, b)
b = a.isPossible([1,2,3,3,4,4,5,5])
print(True, b)
b = a.isPossible([1,2,3,4,4,5])
print(False, b)
b = a.isPossible([1])
print(False, b)
b = a.isPossible([1,2])
print(False, b)
08/19/2022 10:53 提交，状态 Accepted。
想不明白如果是[1,2,3,4,5,6]这个case，不是应该优先让4成为start，组成[4,5,6]么，如果优先让4拼在[1,2,3]的后面不就错了么，因为剩下的array长度不够了呀
@sophiezxf 题目要求是可以分割数组可以组成一个或者多个subsequence， 所以你的例子它的subsequence就是它本身没毛病。每个frequency大于1的数才有可能是需要分割序列的地方。
首先，把不连续的部分拆开，比如[1,2,2,3,3,4, 11,12,13]拆成[1,2,2,3,3,4],[11,12,13]分别处理。 然后把数组处理成每个数字的重复次数，例如[1,2,2,3,3,4,4,4,5,5,5,6,6,6,7,7,8]，可以处理为[1,2,2,3,3,3,2,1]
就拿这个例子说明，[1,2,2,3,3,3,2,1] 最左边的3个数字肯定是要连在一起的，所以最左边3个数字-1，然后去掉最左边的0，变成[1,1, 3,3,3,2,1]。在这一步中，要先判断前三个数是否是非递减的，如果有递减例如[2,1,2,3,3,3,2,1]，直接失败。 那么要不要继续往后延伸呢？如果后面的数字频次递增或者不变的时候，往后延伸，否则不再延伸。 对于[1,2,2,3,3,3,2,1]这个例子，[1,2,2,3,3,3]都在递增，所以处理到3为止，这样一轮之后，变成[1,1,2,2,2,2,1]
然后重复上述过程，最后数组为空，说明成功。
class Solution {
public:
bool isPossible(vector<int>& nums) {
vector<vector<int>> arrs = split(nums);
for (vector<int> &arr : arrs) {
if (!subIsPossible(arr)) return false;
}
return true;
}
vector<vector<int>> split(const vector<int>& nums) {
vector<vector<int>> results;
vector<int> result{1};
for (int i = 1; i < nums.size(); i++) {
if (nums[i] == nums[i - 1]) {
result.back()++;
} else if (nums[i] == nums[i - 1] + 1) {
result.push_back(1);
} else {
results.push_back(std::move(result));
result.resize(0);
result.push_back(1);
}
}
results.push_back(std::move(result));
return results;
}
bool subIsPossible(vector<int>& nums) {
assert(nums[0] > 0);
const int N = 3;
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int minRight = left + N - 1;
if (minRight > right) return false;
for (int i = left + 1; i <= minRight; i++) {
if (nums[i] < nums[i - 1]) return false;
}
int curr = left;
while (curr <= minRight) {
nums[curr]--;
if (nums[curr] == 0) left++;
curr++;
}
while (curr <= right && nums[curr] >= nums[curr - 1] + 1) {
nums[curr]--;
if (nums[curr] == 0) left++;
curr++;
}
}
return true;
}
};
