ARTS-12

Algorithm

1295. 统计位数为偶数的数字

题解：

class Solution {
    public int findNumbers(int[] nums) {
        int count = 0;
        for (int num : nums) {
            int bits = 0;
            do {
                num = num / 10;
                bits++;
            } while (num != 0);

            if (bits % 2 == 0) {
                count++;
            }
        }

        return count;
    }
}

执行用时：1ms，内存消耗：38.7MB。

Review

Fashionable Problems

作者在许多不同的领域见到了相同的模式：尽管很多人在对应的领域内努力工作，但是仅仅只能探索了很小的一部分可能性，因为他们大都工作在相似的事情上。

即使是最聪明、最优想象力的人们，在决定要做什么时，他们也会出奇地保守。那些从未想象过以任何方式成为主流的人会陷入对主流问题的研究中。

如果你想尝试研究非主流问题，最好的方向之一是去看看哪些人们认为自己已经完全摸透了的领域：文章、演讲、风险投资等。你会在这儿发现一种模式：如果你可以在一个庞大但显然已经淘汰的领域中找到新方法，你发现的事物的价值都会乘以该领域已经覆盖的面积。

避免陷入和其他人做一样的事情的最好的方法是真诚地热爱你所做的事情。这样，即便犯了和其他人相同的错误，你也会认为这很重要并且能够坚持下去。

Tip

数据库索引

作用

索引的出现其实就是为了提高数据查询的效率, 就像书的目录一样.

常见的索引模型

哈希表

• 特点: 插入快, 等值查询快, 区间查询慢.
• 适用场景: 只有等值查询的场景.

有序数组

• 特点: 有序数组在等值查询和范围查询场景中的性能都非常优秀, 但是插入慢.
• 适用场景: 静态存储引擎.

搜索树

• 特点: 均衡了读写速度, 相对来说都比较快.
• 适用场景: 已被广泛应用.

索引类型

• 主键索: 主键索引的叶子节点存的是整行数据. 在 InnoDB 里, 主键索引也被称为聚簇索引 (clustered index);
• 非主键索引: 非主键索引的叶子节点存的是主键的值. 在 InnoDB 里, 非主键索引也被称为二级索引 (secondary index);

非主键索引查询到的是索引值, 主键索引查询到的是整行数据, 所以非主键索引的查询需要多扫描一颗索引树. 因此, 我们在应用中应该尽量使用主键查询.

建议

一般情况下, 建议使用自增主键. 原因有二:

• 自增主键的每次插入都是一条新纪录, 执行追加操作, 不涉及挪动其他记录;
• 主键长度越小, 普通索引的叶子节点就越小, 普通索引占据的空间也就越小.
  KV 场景下, 可以使用业务字段直接做主键, 需要满足两个条件:
  • 只有一个索引;
  • 该索引必须是唯一索引.

优化

根据非主键索引查询到的主键回到主键索引搜索的过程称为 回表, 回表会增加搜索次数, 导致查询效率降低.

覆盖索引

索引上的字段已经满足了查询需求, 这种索引称之为 覆盖索引. 由于覆盖索引可以减少树的搜索次数, 显著提升查询性能, 所以使用覆盖索引是一个常用的优化手段.

最左前缀原则

B+ 树这种索引结构, 可以利用索引的 “最左前缀” 来定位记录. 这个最左前缀可以是联合索引的最左 N 个字段, 也可以是字符串索引的最左 M 个字符. 所以, 如果通过调整顺序可以少维护一个索引, 那么这个顺序往往就是优先考虑采用的.

索引下推

MySQL 5.6 引入的索引下推优化 (index condition pushdown), 可以在索引遍历过程中, 对索引中包含的字段先做判断, 直接过滤掉不满足条件的记录, 减少回表次数.

Share

之前听了极客时间谭超老师的直播，老师提到一个刷算法题的思路，感觉很是有道理。

做算法题最大的误区：只做一遍。

• 第一遍

  5 分钟读题 + 思考，不会做不要紧，直接看解法，比较各种解法的优劣。然后背诵、默写好的解法。

• 第二遍

  自己解题、优化、比较各种解法利弊、比较时间复杂度和空间复杂度。

• 第三遍

  一天之后 重复做题、专项练习。

• 第四遍

  一周之后 反复练习相同的题目。

• 第五遍

  面试前一周恢复性训练。

我自己做题会陷入一种“自己做出来才算是会了”的误区。但谭超老师有句话很有道理：“我们是在学算法，不是在发明算法。”如此说来，自己一直死磕就有点浪费时间了。