Tip-Review-Algorithm 第十一期

发表于 更新于 分类于
1. jq. 2. 写注释的最佳实践. 3. 双指针.

「Tip」./jq 轻量级命令行 JSON 处理器

jq is a lightweight and flexible command-line JSON processor.

有时候会在命令行确认一些 HTTP 请求，并分析以下其中的某些字段，但是如果 server 返回 JSON 没有格式化的话，会比较难以阅读，这里推荐一个命令行 JSON 处理工具 jq。

官网地址：https://stedolan.github.io/jq/

  1. 按系统下载执行文件 jq-osx-amd64
  2. 重命名为 jq，并移动至 usr/local/bin 目录下；或者其他目录，确保已经在 $PATH 中。
  3. 使用 curl xxxx | jq .

效果如图所示：
jq

「Review」写代码注释的最佳实践

原文：Best practices for writing code comments

程序代码有两类读者，编译器和人类。编译器会忽略注释，找到语法正确的代码进行执行；而人类则依赖注释来理解作者的代码。

遵守一些注释的规则可以节省自己和队友的时间。

代码告诉你怎么做，注释告诉你为什么。

  1. 注释不能只是代码的重复。

    • Bad Case

      1
      2
      3
      4
      5
      6
      7
      8
      // create a for loop // <-- comment
      for // start for loop
      (   // round bracket
          // newline
      int // type for declaration
      i    // name for declaration
      =   // assignment operator for declaration
      0   // start value for i

      代码重复注释

  2. 注释不能用来解释本不清晰的代码。应该在代码内体现的信息，就不要通过滥用注释来提供。

    • Bad Case

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      private static Node getBestChildNode(Node node) {
          Node n; // best child node candidate
          for (Node node: node.getChildren()) {
              // update n if the current state is better
              if (n == null || utility(node) > utility(n)) {
                  n = node;
              }
          }
          return n;
      }

    • Good Case

      1
      2
      3
      4
      5
      6
      7
      8
      9
      private static Node getBestChildNode(Node node) {
          Node bestNode;
          for (Node currentNode: node.getChildren()) {
              if (bestNode == null || utility(currentNode) > utility(bestNode)) {
                  bestNode = currentNode;
              }
          }
          return bestNode;
      }

  3. 如果你不能写出清晰的注释，可能是代码有问题。

    • Kernighan’s Law

      调试在一开始就比编写程序困难一倍。因此，按照定义，如果你的代码写得非常巧妙，那么你就没有足够的能力来调试它。

      Brian Kernighan

      即：简单的代码会比复杂的代码更可取，因为调试复杂代码的过程中出现的任何问题都会十分棘手，甚至无法解决。

    • Bad Case

      1
      // 你不需要理解这块逻辑

  4. 注释应该用于消除困惑，而不是造成困惑。

  5. 对一些不太地道的代码应该加以注释。

    即对一些别人可能认为不需要的或者多余的代码进行注释，如果没有注释，有人可能会“简化”代码。

    通过写下注释来解释，可以节省未来读者的时间和焦虑。

    • Good Case

      1
      2
      3
      4
      5
      6
      final Object value = (new JSONTokener(jsonString)).nextValue();
      // Note that JSONTokener.nextValue() may return
      // a value equals() to null.
      if (value == null || value.equals(null)) {
          return null;
      }

  6. 复制的代码需要提供原始的链接。

    你有时候会使用网上找到的代码，提供引用的来源，可以让读者了解完整的上下文，比如：

    1. 解决了什么问题
    2. 是谁提供的代码
    3. 为什么推荐这个方案
    4. 评论者的看法
    5. 到目前为止是否还有效
    6. 它能否被改进

    • Good Case

      1
      /** Converts a Drawable to Bitmap. via <https://stackoverflow.com/a/46018816/2219998>. */
      1
      2
      // Many thanks to Chris Veness at <http://www.movable-type.co.uk/scripts/latlong.html>
      // for a great reference and examples.

    • Bad Case

      1
      2
      3
      // Magical formula taken from a stackoverflow post, reputedly related to
      // human vision perception.
      return (int) (0.3 * red + 0.59 * green + 0.11 * blue);

    备注：不要拷贝你不理解的代码。

  7. 注释里放一些外部参考资料的链接，当这些资料十分有帮助的时候。

    一些标准或者其他文档的链接，可以帮助读者理解代码正在解决的问题。

    虽然这些信息可能位于设计文档的某个地方，但是一个放置得当的注释可以为读者在最需要它的时间和地点提供及时的帮助。

    • Good Case

      1
      2
      3
      // <http://tools.ietf.org/html/rfc4180> suggests that CSV lines
      // should be terminated by CRLF, hence the \\r\\n.
      csvStringBuilder.append("\\r\\n");

  8. 注释不仅应该在最初编写代码的时候添加，还应该在修改代码时添加，尤其是在修复 Bug 的时候。

    • Good Case

      1
      2
      3
      4
      5
      6
      // NOTE: At least in Firefox 2, if the user drags outside of the browser window,
      // mouse-move (and even mouse-down) events will not be received until
      // the user drags back inside the window. A workaround for this issue
      // exists in the implementation for onMouseLeave().
      @Override
      public void onMouseMove(Widget sender, int x, int y) { .. }
      1
      // Use the name as the title if the properties did not include one (issue #1425)

  9. 使用注释标记不完整的实现。

    有时候即使知道代码有局限性，但也只能先 merge。虽然说大家不愿意分享代码已知的缺陷，但最好明确地说出这些缺陷，比如用 TODO 进行注释。

    还有一点，对这一类注释使用标准的格式，有助于度量和处理技术债务。

    再优化一些，可以在自己的 Board 中添加一个 issue，并在注释中引用这个 issue。

    • Good Case

      1
      2
      3
      4
      5
      // TODO(hal): We are making the decimal separator be a period, 
      // regardless of the locale of the phone. We need to think about 
      // how to allow comma as decimal separator, which will require 
      // updating number parsing and other places that transform numbers 
      // to strings, such as FormatAsDecimal

「Algorithm」最接近的三数之和

题目：给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

思路： 双指针，左右指针。

解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/*
 * @lc app=leetcode.cn id=16 lang=cpp
 *
 * [16] 最接近的三数之和
 */

// @lc code=start
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int best = 1e7;

        auto update = [&](int cur) {
            if (abs(cur - target) < abs(best - target)) {
                best = cur;
            }
        };

        for (int a = 0; a < n; a++) {
            if (a > 0 && nums[a] == nums[a - 1]) {
                continue;
            }

            int b = a + 1, c =  n - 1;
            while (b < c) {
                int sum = nums[a] + nums[b] + nums[c];
                if (sum == target) {
                    return target;
                }
                update(sum);
                if (sum > target) {
                    int c0 = c - 1;
                    while (b < c0 && nums[c0] == nums[c]) {
                        c0--;
                    }
                    c = c0;
                } else {
                    int b0 = b + 1;
                    while (b0 < c && nums[b0] == nums[b]) {
                        b0++;
                    }
                    b = b0;
                }
            }
        }
        return best;
    }
};
// @lc code=end

双指针套路框架

快、慢指针的常用算法

  1. 判定链表中是否含有环。
  2. 已知链表中含有环，返回这个环的起始位置。
  3. 寻找无环单链表的中点。
  4. 寻找单链表的倒数第k个元素。

左、右指针的常用算法

  1. 二分搜索。
  2. 两数之和。
  3. 反转数组。
  4. 滑动窗口算法。