https://leetcode.com/problems/count-number-of-teams/
树状数组，不会，看题解发现不需要DP直接n^2模拟就行，我真是sb
题目看了一半，下意识以为是把人刚好分成几个team然后不剩下，问有几种分法，下意识觉得难道不是二分吗？结果看完了才知道是穷举 
脑子里蹦出来的想法就是，可以按照比如说递增关系，把整个队伍做成partial ordered graph，每一个successor projection出来的链表都是单调的，接受O(n)空间复杂度的话构造这个graph时间复杂度应该也是O(n)，这样也形如DP了
如果是自己的项目我肯定会这么做的，因为虽然worst case还是n^2，但是日常数据应该会无限逼近n。不过leetcode 的不可能这么麻烦，可能真的穷举就好了
O(n^2)穷举，STL没有的数据结构除了并查集我是基本不会自己写的 
我从来都是自己写stl的（除了只能编译器开后门的那些，比如 type_traits 或者 atomic啥的）。只有有思路，实现都不是问题
我会写但是很懒，而且细节经常处理不好，很难受
你需要能帮你做unit test，code coverage和memory leak的工具，习惯了会对测试上瘾
这题如果不会
也是可以做的。就是我们前两天说过的
求
做两遍就行，第一遍求二元逆序对的数量，第二遍根据第一遍的结果求三元逆序对的数量。因为rating是unique的，方便了查询，带个log就完事了。复杂度O(n log^2 n)吧，用hash可以做到伪O(n log n)。
1 个赞
放弃治疗了，我爱暴力
下次见到大哥给你出四元逆序对
直接上dp，或者
直觉上就是往字符串砍一刀，要求左边的b和右边的a加起来最小。字符串得每一个字符都是有效信息，所以复杂度最低必然是O(n)，从左到右试一下也是O(n)
https://leetcode.com/problems/filling-bookcase-shelves/
一开始以为是3d dp，看了提示发现是1d dp
d_i=\min_{j: \sum_i^j{w_j} \leq W}{\max_{k\in \{i, \cdots, j-1\}}{h_k} + d_j}
差不多这么个意思，秒了
https://leetcode.com/problems/toss-strange-coins
简单的概率dp，边界条件需要复习一下
d_{i, h}=d_{i-1, h-1}\mathbb{P}_i(\text{H})+d_{i-1, h}\mathbb{P}_i(\text{T})
日常写一坨屎发泥潭：
def probabilityOfHeads(self, prob: List[float], target: int) -> float:
dp: Callable[[int, int], float] = (lru_cache(maxsize=len(prob)*target+64)(lambda i, heads: 1.0 if i==-1 and heads == 0 else 0.0 if i<0 or heads < 0 else (dp(i-1, heads-1)*prob[i] + dp(i-1, heads)*(1-prob[i]))))
return dp(len(prob)-1, target)
又是带锁题，再见 
You have some coins. The i-th coin has a probability prob[i] of facing heads when tossed.
Return the probability that the number of coins facing heads equals target if you toss every coin exactly once.
Example 1:
Input: prob = [0.4], target = 1 Output: 0.40000
Example 2:
Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0 Output: 0.03125
Constraints:
1 <= prob.length <= 10000 <= prob[i] <= 10 <= target<= prob.length- Answers will be accepted as correct if they are within
10^-5of the correct answer.
你小子整天就秒了
我还在这里复习怎么写sort
这他妈怎么面试啊
#include "algorithm"
#include "functional"
using namespace std;
template <class T>
vector<T> aws_sort(vector<T>& data, function<bool(T&, T&)> comp) {
vector<T> result(data.begin(), data.end());
sort(result.begin(), result.end(), comp);
return result;
}
秒了
主要好久不写sort了得复习下
之前一直偷懒用heapify
# break into halfs (recursive)
# only focus on merge function
# -> which is basically same as merging two sorted linked lists
def MergeSort(arr):
n = len(arr)
if n <= 1:
return arr
mid = n // 2
left = arr[:mid]
right = arr[mid:]
left = MergeSort(left)
right = MergeSort(right)
return _merge(left, right)
def _merge(left, right):
res = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
res.append(left[i])
i += 1
else:
res.append(right[j])
j += 1
res.extend(left[i:])
res.extend(right[j:])
return res
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = MergeSort(arr)
print("Sorted array:", sorted_arr)
NMD周二easy run秒了
这里没有异常检测，what if your arr is None?