每周完成一个ARTS: 1.Algorithm:每周至少做一个 leetcode 的算法题 2.Review:阅读并点评至少一篇英文技术文章 3.Tip:学习至少一个技术技巧 4.Share:分享一篇有观点和思考的技术文章 +++ banner = "” categories = [“DataStruct”] date = “2019-03-08T11:58:06+02:00” description = "” images = [] menu = "” tags = [“DataStruct”] title = “作恶的矿工们” draft = true +++

Algorithm

leetcode-42

42. Trapping Rain Water

Desc

1
2
3
4
5
6
7
8
9
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.


The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Analyze

第一遍遍历dp[i]中存入i位置左边的最大值,然后开始第二遍遍历数组,第二次遍历时找右边最大值,然后和左边最大值比较取其中的较小值,然后跟当前值height[i]相比,如果大于当前值,则将差值存入结果

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int trap(vector<int>& height) {
        int res = 0, mx = 0, n = height.size();
        vector<int> dp(n, 0);
        for (int i = 0; i < n; ++i) {
            dp[i] = mx;
            mx = max(mx, height[i]);
        }
        mx = 0;
        for (int i = n - 1; i >= 0; --i) {
            dp[i] = min(dp[i], mx);
            mx = max(mx, height[i]);
            if (dp[i] > height[i]) res += dp[i] - height[i];
        }
        return res;
    }
};

Deep

参考Relation部分

Relation

  1. 407. Trapping Rain Water II

Review

优点

  1. Minimal disruption
  2. Balance
  3. Consistency

要点

  1. U 表示key的集合
  2. S 表示资源的集合
  3. W 当前已经匹配key的buckets集合
  4. A 表示所有buckets的集合

内容来自AnchorHash: A Scalable Consistent Hash

Tip

  1. 使用partyTu实现在ios上实现后台播放youtube视频

Share

Lessons to learn in your first 5 years as a programmer:

  1. Don’t be afraid to do the same work multiple times. Your first try will often have a lot of bad design. You need repetitions before you get good. Don’t let laziness get in the way of learning and improving.

  2. Reliability is important. The new hot tech has those new features you’ve been dying to try! But it’s also a giant mess, constantly updating, has bad documentation, is hard to set up and difficult to debug. Older tech has google-able solutions. You’ll save time with older tech.

  3. Code for readability. It’s tempting to show off how clever you are by using some obscure language feature that does everything you want in one line. It’s clever, but makes maintenance hard. The new grad that’s reading your code will curse you. Don’t be that guy.

  4. Write unit tests. Seriously, your QA teammates will thank you. You’ll have less bugs. You’ll understand your own code a lot better. You’ll also make your code a lot more modular and testable. Yea, it takes more time, but you’ll probably spend the time you save debugging later.

  5. Don’t over-abstract. I blame this on OO. No, you don’t need some super abstract class that can handle all cases. Just make the program do what you need it to. Abstract later when it makes sense, not before any other instance is written.

  6. Don’t be afraid to learn. Too many devs are one trick ponies (cough Java cough). Learn new stuff or you’ll grow stale. The ability to learn quickly is one of the most in-demand skills as a developer, so you’d best get started earlier than later.

  7. Learn to present. Teach other coders what you’ve learned. Give management an overview. If you ever want to get ahead in your career, presenting is a skill you need. Putting a presentation together is not that different than coding, in any case.

  8. Learn your tools. For the love of God, please learn command line, git and a text editor like vim or emacs. You’re most likely going to have to self-learn on these, but they’re well worth your time. The time you can save pays back the investment manyfold.

All this is to say that your education as a programmer doesn’t end with your CS degree or bootcamp. In fact, it’s really just beginning. You can learn the rules pretty quickly, but to master the art takes a lifetime.

欢迎关注

欢迎关注微信公众帐号:沉风网事(savewind)

沉风网事