Algorithm
LeetCode算法题
Java 程序实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public int trap(int[] height) {
int total = 0;
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < height.length; i++) {
if (stack.empty() || height[i] <= height[stack.peek()]) {
stack.push(i);
continue;
}
while (!stack.empty() && height[i] > height[stack.peek()]) {
int bottom = height[stack.peek()];
stack.pop();
if (stack.size() > 0) {
int distance = i - stack.peek() - 1;
int min = Math.min(height[stack.peek()], height[i]);
total = total + distance * (min - bottom);
}
}
stack.push(i);
}
return total;
}
}
Review
《算法》作者Sedgewick在ANALCO’11上的演讲Algorithms for the Masses：主要谈了一些为大众讲授算法的理念
- Philippe Flajolet : HyperLogLog
- algorithms that everyone should know
- everyone means scientists engineers mathematicians software/hardware designers cryptananalysts cobol programmers
- Scientific Method : 1\create a model describing natural world 2\use model to develop hypotheses 3\run experiments to validate hypotheses 4\refine model and repeat
- O-notation VS tilde-notation O(N^c) VS ~aN^c
- Analytic Combinatorics
- Introduction to CS
- computer science & science/engineering, both are essential
- anyone can learn the importance of the scientific method in understanding program behavior
- Future of publishing
- Algorithms for the masses
- 作者为了算法的教学工作，真是操碎了心啊，希望有越来越多的RS这样的教育工作者，特别是国内
Tip
- 日拱一卒长期坚持，拒绝战术编程，提升战略思维。
