📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: moluren
跳转到指定楼层
上一主题 下一主题
收起左侧

[其他] 请大家分享一下大家觉得高大上且鬼父神工的算法实现

 
🔗
wihoho 2019-1-24 13:51:37 | 只看该作者
全局:
谁能告诉我为什么399 简单的DFS,BFS,union-find就可以?

假如有多个path,然后需要找最大值呢?
回复

使用道具 举报

🔗
syla 2019-1-25 02:19:55 | 只看该作者
全局:
https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/discuss/162767/Python-Sliding-Window-Solution
一道高频题,不清楚是不是惯用的技巧,但感觉一般滑窗的解法都习惯用个tmpMax来随时记录一下更新,看到这个解法才发现完全不需要tmpMax来每次都比较一下对象再更新到结果,而是当窗口本身的长度被扩大后就不会再缩小,所以最后直接返回right-left,感觉很巧妙。
回复

使用道具 举报

全局:
好棒 感谢呢
回复

使用道具 举报

🔗
rannn 2019-1-28 18:19:47 | 只看该作者
全局:
这不是基本操作吗
回复

使用道具 举报

🔗
max940623 2019-2-4 05:03:19 | 只看该作者
全局:
最近比较有印象的是一道union find的实现,不算鬼斧神工但是基本功很扎实,面试官肯定会喜欢。他实现了princeton算法第一课讲的path compression和rank weighting来优化表现,多数人不会在意这种细节。

class UF {
private:
    vector<int> fathers;
    vector<int> ranks;

public:
    UF(int m, int n): fathers(vector<int>(m*n, -1)), ranks(vector<int>(m*n, 0)){}

    // init a new union
    void Init(int i){
        fathers[i] = i;
        ranks[i] = 1;
    }

    // find with path compression
    int Find(int i){
        while(i!=fathers[i]){
            i = fathers[fathers[i]];
        }
        return i;
    }

    // union with rank weighting
    void Union(int i, int j){
        int root_i = Find(i);
        int root_j = Find(j);

        if (root_i==root_j) return;

        if (ranks[root_i]>ranks[root_j]){
            fathers[root_j] = root_i;
            ranks[root_i] += ranks[root_j];
        } else {
            fathers[root_i] = root_j;
            ranks[root_j] += ranks[root_i];
        }
    }

    // size of the union
    int Size(int i){
        return ranks[Find(i)];
    }
};


class Solution {
public:
    int largestIsland(vector<vector<int>> &grid) {
        int m = grid.size(), n = grid[0].size();
        UF uf(m,n);

        // preprocess to build uf and record zeros
        vector<int> zeros;
        for (int i = 0; i<m; i++){
            for (int j = 0; j<n; j++){
                int index = i*n+j;

                if (grid[i][j]==0) {
                    zeros.push_back(index);
                } else {
                    uf.Init(index);
                    // only union with previous, later not init yet
                    if (i>0 && grid[i-1][j]) uf.Union((i-1)*n+j, index);
                    if (j>0 && grid[i][j-1]) uf.Union(i*n+(j-1), index);
                }
            }
        }

        // solve
        if (zeros.empty()) return m*n;

        int ans = 0;
        for (auto &zero:zeros){
            int i = zero/n, j = zero%n;
            unordered_set<int> roots; // neighbors' root, use set to remove duplicate

            if (i>0 && grid[i-1][j]) roots.insert(uf.Find((i-1)*n+j));
            if (i<m-1 && grid[i+1][j]) roots.insert(uf.Find((i+1)*n+j));

            if (j>0 && grid[i][j-1]) roots.insert(uf.Find(i*n+j-1));
            if (j<n-1 && grid[i][j+1]) roots.insert(uf.Find(i*n+j+1));

            int area = 1;
            for (auto &root:roots){
                area += uf.Size(root);
            }
            ans = max(ans, area);
        }
        return ans;
    }
};


回复

使用道具 举报

🔗
max940623 2019-2-4 05:19:15 | 只看该作者
全局:
格式有问题,重发一次

  1. class UF {
  2. private:
  3.     vector<int> fathers;
  4.     vector<int> ranks;
  5.    
  6. public:
  7.     UF(int m, int n): fathers(vector<int>(m*n, -1)), ranks(vector<int>(m*n, 0)){}
  8.    
  9.     // init a new union
  10.     void Init(int i){
  11.         fathers[i] = i;
  12.         ranks[i] = 1;
  13.     }
  14.    
  15.     // find with path compression
  16.     int Find(int i){
  17.         while(i!=fathers[i]){
  18.             i = fathers[fathers[i]];
  19.         }
  20.         return i;
  21.     }
  22.    
  23.     // union with rank weighting
  24.     void Union(int i, int j){
  25.         int root_i = Find(i);
  26.         int root_j = Find(j);
  27.         
  28.         if (root_i==root_j) return;
  29.         
  30.         if (ranks[root_i]>ranks[root_j]){
  31.             fathers[root_j] = root_i;
  32.             ranks[root_i] += ranks[root_j];
  33.         } else {
  34.             fathers[root_i] = root_j;
  35.             ranks[root_j] += ranks[root_i];
  36.         }
  37.     }
  38.    
  39.     // size of the union
  40.     int Size(int i){
  41.         return ranks[Find(i)];
  42.     }
  43. };

  44. class Solution {
  45. public:
  46.     /**
  47.      * @param grid:
  48.      * @return: nothing
  49.      */
  50.     int largestIsland(vector<vector<int>> &grid) {
  51.         int m = grid.size(), n = grid[0].size();
  52.         UF uf(m,n);
  53.         
  54.         // preprocess to build uf and record zeros
  55.         vector<int> zeros;
  56.         for (int i = 0; i<m; i++){
  57.             for (int j = 0; j<n; j++){
  58.                 int index = i*n+j;
  59.                
  60.                 if (grid[i][j]==0) {
  61.                     zeros.push_back(index);
  62.                 } else {
  63.                     uf.Init(index);
  64.                     // only union with previous, later not init yet
  65.                     if (i>0 && grid[i-1][j]) uf.Union((i-1)*n+j, index);
  66.                     if (j>0 && grid[i][j-1]) uf.Union(i*n+(j-1), index);
  67.                 }
  68.             }
  69.         }
  70.         
  71.         // solve
  72.         if (zeros.empty()) return m*n;
  73.         
  74.         int ans = 0;
  75.         for (auto &zero:zeros){
  76.             int i = zero/n, j = zero%n;
  77.             unordered_set<int> roots; // neighbors' root, use set to remove duplicate
  78.             
  79.             if (i>0 && grid[i-1][j]) roots.insert(uf.Find((i-1)*n+j));
  80.             if (i<m-1 && grid[i+1][j]) roots.insert(uf.Find((i+1)*n+j));
  81.                         
  82.             if (j>0 && grid[i][j-1]) roots.insert(uf.Find(i*n+j-1));
  83.             if (j<n-1 && grid[i][j+1]) roots.insert(uf.Find(i*n+j+1));
  84.             
  85.             int area = 1;
  86.             for (auto &root:roots){
  87.                 area += uf.Size(root);
  88.             }
  89.             ans = max(ans, area);
  90.         }
  91.         return ans;
  92.     }
  93. };
复制代码
回复

使用道具 举报

🔗
小丸几 2019-4-14 11:55:53 | 只看该作者
全局:
太多了... 抱着学习的心态就好。
随便举两个例子:
480. Sliding Window Median, Po神的解法。下面加粗的部分,不换行的话也就4行,把弹入弹出的9种组合情况都cover到了,而且还完美避免了中间结点被弹出。简直太妙了。
  1. vector<double> medianSlidingWindow(vector<int>& nums, int k) {
  2.     multiset<int> window(nums.begin(), nums.begin() + k);
  3.     auto mid = next(window.begin(), k / 2);
  4.     vector<double> medians;
  5.     for (int i=k; ; i++) {

  6.         // Push the current median.
  7.         medians.push_back((double(*mid) + *prev(mid, 1 - k%2)) / 2);

  8.         // If all done, return.
  9.         if (i == nums.size())
  10.             return medians;
  11.             
  12.         // Insert nums[i].
  13.         [b]window.insert(nums[i]);
  14.         if (nums[i] < *mid)
  15.             mid--;

  16.         // Erase nums[i-k].
  17.         if (nums[i-k] <= *mid)
  18.             mid++;
  19.         window.erase(window.lower_bound(nums[i-k]));[/b]
  20.     }
  21. }
复制代码


再贴一个CF上的线段树实现,最好结合原文的例子理解。这个是我见过的最简洁的实现了,简直神奇。

  1. const int N = 1e5; // limit for array size
  2. int n; // array size
  3. int t[2 * N];

  4. void build() { // build the tree
  5. for (int i = n - 1; i > 0; --i) t[i] = t[i<<1] + t[i<<1|1];
  6. }

  7. void modify(int p, int value) { // set value at position p
  8. for (t[p += n] = value; p > 1; p >>= 1) t[p>>1] = t[p] + t[p^1];
  9. }

  10. int query(int l, int r) { // sum on interval [l, r)
  11. int res = 0;
  12. for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
  13. if (l&1) res += t[l++];
  14. if (r&1) res += t[--r];
  15. }
  16. return res;
  17. }
复制代码


回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表