Algorithm(leetcode 算法题)

Cut Off Trees for Golf Event

这道题真的……意外的花费了我非常多的时间,思路其实很快就理清了,但在最后的实现上卡得非常久,基本以下几个原因

  • 题意理解
  • 算法细节
  • 思路

这道题化简后重点就是二维矩阵上的两个点之间的最短距离,或者说迷宫问题?第一反应是 A* 寻路算法

  • 公式:F = G + H
  • G:起点该点的最短距离(考虑障碍)
  • H:该点到终点的最短距离(不考虑障碍,因此对矩阵来说任一点该值固定)

每轮迭代以 F 值最小点为候选点更新可到达点的 F、G、H 值,直到终点

刚开始编码实现时我遗漏了一个很重要的算法细节:因为取点是根据 F 值来取的,因此已经到达过的点计算出的 G 值可能不是它本身最小的 G 值,因此到过的点的 G 值需要在迭代过程中更新

题目中有这么一句描述:

cut off all the trees in this forest in the order of tree's height - always cut off the tree with lowest height first

最初我误以为是到达树的位置后必须砍掉这颗树,因此矩阵中能经过的格只有 1 和 0,若到达当前最小高度树必须经过其他高度的树则说明无法到达。后来 WA 后在评论区一翻发现有跟我一样对题意误解的朋友哈哈

enter image description here

实际上可以经过树而不砍,因此无法通过的道路就只有值为 0 的位置,以下是我的 A* 算法解法

class Solution(object):
  def currentFind(self, fMtrix, openList, hMtrix):
    current, length = openList[0], len(openList)
    for i in range(1, length):
      if fMtrix[openList[i][0]][openList[i][1]] < fMtrix[current[0]][current[1]]:
        current = openList[i]
      elif fMtrix[openList[i][0]][openList[i][1]] == fMtrix[current[0]][current[1]]:
        if hMtrix[openList[i][0]][openList[i][1]] < hMtrix[current[0]][current[1]]:
          current = openList[i]
    return current
  
  def minDistBetweenPoints(self, start, end, forest):
    width, height, openList, closeList = len(forest[0]), len(forest), [], []
    fMtrix = [[-1] * len(forest[0]) for i in range(0, len(forest))]
    hMtrix = [[0] * width for i in range(0, height)]
    for i in range(0, height):
      for j in range(0, width):
        hMtrix[i][j] = abs(i - end[0]) + abs(j - end[1])
    fMtrix[start[0]][start[1]] = hMtrix[start[0]][start[1]] + 0
    openList.append(start)
    while True:
      if end in openList:
        return fMtrix[end[0]][end[1]]
      current = self.currentFind(fMtrix, openList, hMtrix)
      curHDist = abs(current[0] - end[0]) + abs(current[1] - end[1])
      openList.remove(current)
      closeList.append(current)
      if current[0] - 1 >= 0 and forest[current[0] - 1][current[1]] != 0:
        newPoint = (current[0] - 1, current[1])
        if newPoint not in openList and newPoint not in closeList :
          fMtrix[newPoint[0]][newPoint[1]] = fMtrix[current[0]][current[1]] - curHDist + hMtrix[newPoint[0]][newPoint[1]] + 1
          openList.append(newPoint)
        elif fMtrix[current[0]][current[1]] - curHDist + hMtrix[newPoint[0]][newPoint[1]] + 1 < fMtrix[newPoint[0]][newPoint[1]]:
          fMtrix[newPoint[0]][newPoint[1]] = fMtrix[current[0]][current[1]] - curHDist + hMtrix[newPoint[0]][newPoint[1]] + 1
      if current[0] + 1 < height and forest[current[0] + 1][current[1]] != 0:
        newPoint = (current[0] + 1, current[1])
        if newPoint not in openList and newPoint not in closeList :
          fMtrix[newPoint[0]][newPoint[1]] = fMtrix[current[0]][current[1]] - curHDist + hMtrix[newPoint[0]][newPoint[1]] + 1
          openList.append(newPoint)
        elif fMtrix[current[0]][current[1]] - curHDist + hMtrix[newPoint[0]][newPoint[1]] + 1 < fMtrix[newPoint[0]][newPoint[1]]:
          fMtrix[newPoint[0]][newPoint[1]] = fMtrix[current[0]][current[1]] - curHDist + hMtrix[newPoint[0]][newPoint[1]] + 1
      if current[1] - 1 >= 0 and forest[current[0]][current[1] - 1] != 0:
        newPoint = (current[0], current[1] - 1)
        if newPoint not in openList and newPoint not in closeList :
          fMtrix[newPoint[0]][newPoint[1]] = fMtrix[current[0]][current[1]] - curHDist + hMtrix[newPoint[0]][newPoint[1]] + 1
          openList.append(newPoint)
        elif fMtrix[current[0]][current[1]] - curHDist + hMtrix[newPoint[0]][newPoint[1]] + 1 < fMtrix[newPoint[0]][newPoint[1]]:
          fMtrix[newPoint[0]][newPoint[1]] = fMtrix[current[0]][current[1]] - curHDist + hMtrix[newPoint[0]][newPoint[1]] + 1
      if current[1] + 1 < width and forest[current[0]][current[1] + 1] != 0:
        newPoint = (current[0], current[1] + 1)
        if newPoint not in openList and newPoint not in closeList :
          fMtrix[newPoint[0]][newPoint[1]] = fMtrix[current[0]][current[1]] - curHDist + hMtrix[newPoint[0]][newPoint[1]] + 1
          openList.append(newPoint)
        elif fMtrix[current[0]][current[1]] - curHDist + hMtrix[newPoint[0]][newPoint[1]] + 1 < fMtrix[newPoint[0]][newPoint[1]]:
          fMtrix[newPoint[0]][newPoint[1]] = fMtrix[current[0]][current[1]] - curHDist + hMtrix[newPoint[0]][newPoint[1]] + 1
      if len(openList) == 0:
        return -1
  
  def cutOffTree(self, forest):
    width, height = len(forest[0]), len(forest)
    positions = [(i, j) for i in range(0, height) for j in range(0, width) if forest[i][j] != 0]
    positions = sorted(positions, key=lambda x: forest[x[0]][x[1]])
    counts, steps = len(positions), self.minDistBetweenPoints((0, 0), positions[0], forest)
    steps = 0
    for a, b in zip([(0,0)] + positions, positions):
      single = self.minDistBetweenPoints(a, b, forest)
      if single == -1:
        return -1
      steps = steps + single
    return steps

然而尴尬的是这个解法并没有 AC 反而是 TLE 了……(此处应有嚎啕大哭)再次去评论区逛了逛,发现更多的解法是 BFS。从我直观上的理解来看,BFS 选点在图上的扩展大致是以起点为中心的一个菱形,A* 评估条件加入了一个距离终点的值,那么 A* 的迭代次数应该不会比 BFS 要高很多?

无论如何还是参考了下评论区用 BFS 同学的算法(一个 beats 了 92% 的 java 版),用 python 实现了一遍

然而竟然还是 TLE 了!!!!!!!

怎么 java 分分钟 beats 92% 然而 python连 AC 都不行……没天理啊……

此处放下两个版本对比,如果有同学明白请务必告诉我两者算法区别在哪里……

  • java
class Solution {
   private class Tree {
        int row;
        int col;
        int height;
        int distance;
        public Tree(int row, int col, int height, int distance){
            this.row = row;
            this.col = col;
            this.height = height;
            this.distance = distance;
        }
    }
    public int cutOffTree(List<List<Integer>> forest) {
        if (forest == null || forest.size() == 0){
            return 0;
        }
        List<Tree> trees = new ArrayList<>();
        int maxWidth = 0;
        for (int r = 0; r < forest.size(); r++){
            maxWidth = Math.max(maxWidth, forest.get(r).size());
            for (int c = 0; c < forest.get(r).size(); c++){
                if (forest.get(r).get(c) > 1){
                    trees.add(new Tree(r, c, forest.get(r).get(c), 0));
                }
            }
        }
        Collections.sort(trees, new Comparator<Tree>(){
            @Override
            public int compare(Tree t1, Tree t2){
                if (t1.height == t2.height){
                    return 0;
                }
                return t1.height < t2.height ? -1 : 1;
            }
        });
        Tree preTree = new Tree(0, 0, 0, 0);
        int steps = 0;
        for (Tree currTree : trees){
            int step = getDistance(preTree, currTree, forest, maxWidth);
            if (step == -1){
                return -1;
            }
            steps += step;
            preTree = currTree;
        }
        return steps;
    }
    private int getDistance(Tree t1, Tree t2, List<List<Integer>> forest, int maxWidth){
        boolean[][] visited = new boolean[forest.size()][maxWidth];
        Queue<Tree> queue = new ArrayDeque<>();
        int[][] directions = new int[][]{{-1,0}, {1, 0}, {0, -1}, {0, 1}};
        queue.offer(t1);
        visited[t1.row][t1.col] = true;
        while(!queue.isEmpty()){
            Tree curr = queue.poll();
            if (curr.row == t2.row && curr.col == t2.col){
                return curr.distance;
            }
            for (int i = 0; i < directions.length; i++){
                int row = curr.row + directions[i][0];
                int col = curr.col + directions[i][1];
                if (row < 0 || row >= forest.size() || col < 0 || col >= forest.get(row).size() 
                    || visited[row][col] || forest.get(row).get(col) == 0){
                    continue;
                }
                queue.offer(new Tree(row, col, 0, curr.distance + 1));
                visited[row][col] = true;
            }
        }
        return -1;
    }
}
  • python
class Solution(object):
  def minDistBetweenPoints(self, start, end, forest):
    width, height, queue, directions = len(forest[0]), len(forest), [], [(-1, 0), (1, 0), (0, -1), (0, 1)]
    visted = [[False] * width for i in range(height)]
    visted[start[0]][start[1]] = True
    queue.append((start[0], start[1], 0))
    while len(queue) != 0:
      x, y, dis = queue[0]
      if x == end[0] and y == end[1]:
        return dis
      queue.remove(queue[0])
      for i in range(0, 4):
        newX, newY = x + directions[i][0], y + directions[i][1]
        if (newX < 0 or newY < 0 or newX >= height or newY >= width or forest[newX][newY] == 0 or visted[newX][newY]):
          continue
        queue.append((newX, newY, dis + 1))
        visted[newX][newY] = True
    return -1
  
  def cutOffTree(self, forest):
    width, height = len(forest[0]), len(forest)
    positions = [(i, j) for i in range(0, height) for j in range(0, width) if forest[i][j] != 0]
    positions = sorted(positions, key=lambda x: forest[x[0]][x[1]])
    counts, steps = len(positions), self.minDistBetweenPoints((0, 0), positions[0], forest)
    steps = 0
    for a, b in zip([(0,0)] + positions, positions):
      single = self.minDistBetweenPoints(a, b, forest)
      if single == -1:
        return -1
      steps = steps + single
    return steps


Review(阅读并点评至少一篇技术文章)

1. Kubernetes for Beginners

Kubernetes 入门教室,右边是一个命令行界面,跟着教程走部署完一个 app 能初步掌握 Kubernetes 的基本概念(我跟着教程第一步操作就有问题,不知为何)

严格来说这不是一篇技术文章,应该算教程,前半部分是操作说明+简单解释,后半部分是对 Kubernetes 的概念解析,很简练,基本提取出了重点

个人认为着是最好的 Kubernetes 入门教程之一,对某些易混淆、难理解的概念给了清晰不乏有趣的解释,比如 Declarative vs imperative 这里:

Our container orchestrator puts a very strong emphasis on being declarative

Declarative:
I would like a cup of tea.

Imperative:
Boil some water. Pour it in a teapot. Add tea leaves. Steep for a while. Serve in cup.

Declarative seems simpler at first …
… As long as you know how to brew tea

What declarative would really be:

I want a cup of tea, obtained by pouring an infusion of tea leaves in a cup.
An infusion is obtained by letting the object steep a few minutes in hot water.
Hot liquid is obtained by pouring it in an appropriate container and setting it on a stove.
Ah, finally, containers! Something we know about. Let’s get to work, shall we?

hhhhhh比喻还是挺萌的。总之基本内容都涵盖了,集群联邦等扩展知识也以点带面简单的提了下要点,非常适合入门朋友(比如我)学习

2. Progressive Locks : fast, upgradable read/write locks

一个渐进式锁方案的设计、原理、思路、编码以及性能测量。第一遍读下来感觉是篇非常好的文章,锁方案的场景非常有针对性,分析的很清晰。问题的起源在于我们通常认为写请求会耗时长,那其主要耗时究竟是耗费在了什么地方呢?我个人认为至少有两种典型场景:

  • 要写入的内容多
  • 写入的位置搜索耗时长

第二种就是该锁方案针对的场景,既然是对写入位置的搜索,那本质上还是一个查找请求,即读请求,意味着这一状态下并不需要达到常规写锁的严格级别,基于这一基本思路作者从中抽出了不同于 R(Read)和 W(Write)的第三种状态:S(Seek),并为该状态设置了合理科学的互斥条件,而这一状态也是此方案的核心

进一步的方案设计中还独立出了一种 A 状态代表其他所有与锁无关的原子操作,可以说考虑非常充分了。文中还有相关的代码实现,但我并没有细看

嫌弃英文长不清晰的可以在我的博客里面找到中文翻译版,欢迎一切意见


Technique(技术技巧)

xsel

linux 的一个剪贴板操作的命令行小工具,非常方便,一般有两种基本的用法:

cat test.cpp | xsel -b
  • test.cpp 文件的内容直接输入到剪贴板。在管道 | 的帮助下我们可以轻松的将终端上输出的任意内容一键输入剪贴板,对于较大的文件也不需要打开再复制了
xsel -b > output.txt
  • 将剪贴板内容输入 output.txt ,非常适合我这种主要在 win 下写代码最后还是得把代码搬到虚拟机里跑的用户

更多用法有待挖掘哈哈


Share(分享有观点和思考的技术文章)

Corporate interests in open source and dev culture

这其实是篇访谈,而不是传统意义上的技术文章,访谈内容主要与开源项目社区、个人开发者有关,后半部分提及一些区块链相关。文章非常非常非常的长,我抽了将近一个周的空余时间来看才勉强看完……

受访人 Zed 早年是开源项目的重要贡献者,曾深度参与过重要的开源项目(相关 title 很多,详情见文内),对开源发展与现状有丰富的了解和独特的看法,这里简单提炼下部分核心内容:

  • 开源如今已经是大公司的游戏
  • 大企业是开源最大的受益人与依赖者,其设施服务基础基本建立在广大开源项目上
  • 如今开源环境导致个人开源作者难以维持生计
  • 项目、社区本质上还是把握在巨头(giants)手里
  • 巨头们(giants)利用开源的基础设施垄断了市场

和我们直观上感受到的“社区是顶级个人开发者们的聚集地”、“开源项目为你带来名声、工作”、“开源给你机会决定重磅项目的发展方向”这些印象不同,zed 认为如今开源界并不利于个人开发者的生存,巨头们在其中似乎扮演了“阻止”个人开源作者从中受益的角色。纵观 github,各大社区,对项目具有真正决策权的成员们来自各大资本。也就是说你觉得自己的编码设计/PR 会被接受或拒绝是基于社区的意见,然而这是错觉,实际上还是资本做出了这个决定,社区不过是混淆视线的烟雾弹

如今的科技巨头们早期建立起的基础设施服务使用的都是开源组件、公共资源(比如因为没为 java 付费被起诉了……),他们依赖着这些服务走到了上千亿美元的市值,而开源了这些组件代码的个人开发者们如今却走到了要到 GoFundMe 上请求人们资助的地步,zed 对这一现状感慨颇深

此外 zed 还提到一点:Google 的主要收入来源是广告,Amazon 的主要收入来源是电商,Microsoft 的主要收入是卖 office,主要收入来源都不是云计算平台,通过这些收入几大巨头们建立起了相对而言非常廉价的云计算平台,面向普通开发者们开放,而由于巨大的资本差异,小规模组织或个体开发者们即便拥有不错的技术力量也难以提供比他们更加优惠的基础设施资源,于是云计算的市场资源又进一步被巨头们占领,看起来像个恶性循环

因为是访谈的关系文章非常非常非常的长,而且有部分非常口语化的表达也许不易于理解,但内容非常不错,其见解有了解的价值,推荐有耐心的朋友们细读一下


Comment(via:Hao Chen)

  1. 算法题做的很用心,不过最后的Python版的Java算法没有通过,建议你看一下Python相关的操作的性能问题
  2. Review的英文文章选的很不错,但是第二篇没有看完,这周看吧
  3. 命令行的剪贴版还有一个是xclip命令
  4. 关于share,想知道一下你自己的观点是什么?

关于我的观点:

  • 对开源项目参与不足,没有深入了解过社区,对开源界整体现状难以做出有价值的评价

  • 能感受到的是在开源上大规模组织占据的份额确实越来越多(据说 Github 上贡献最活跃的其实是微软)

  • 赞同当前趋势下个人开源作者难以盈利的事实,在不开源的情况下都难以盈利更不用说获得源代码可以自行编译

  • iOS 用户由于平台原因付费习惯稍微好一些,但愿意为软件付费的人还是相对较少,Android 用户大多基本处于能白拿就白拿的阶段,有了源代码自己打包安装毫无阻碍愿意付费的更少

补充

另外,我隐约觉得你在读一些文章或是做一些事的时候,一旦出现困难或是一旦累了,你可能会就放下了。这就好像你跑步一下,每次都到生理极限时就停下了,你就永远不可能提高了。所以,你还是在你达到极限时要多坚持一下。(也许说的不对,供你参考了)


Written with StackEdit.