Coder Social home page Coder Social logo

blog's People

Contributors

ysmull avatar

Watchers

 avatar  avatar

blog's Issues

Prototype Pattern


Quote

  • Prototype design pattern is used in scenarios where application needs to create a number of instances of a class, which has almost same state or differs very little.[2]

  • Specify the kinds of objects to create using a prototypical instance, and create new objects by copying this prototype.[1]

  • 当创建给定类的实例很昂贵或很复杂时使用原型模式。—《Head First设计模式》

Participants

  • Prototype : the prototype of actual object.
  • Prototype registry : This is used as registry service to have all prototypes accessible using simple string parameters.
  • Client : Client will be responsible for using registry service to access prototype instances.

Practice

定义一个细胞Prototype,split()方法表示出分裂(clone)出一个新细胞。

interface Cell extends Cloneable {
Cell split() throws CloneNotSupportedException;

}

分别定义动物细胞和植物细胞

public class AnimalCell implements Cell {
@Override
public AnimalCell split() throws CloneNotSupportedException {
    return (AnimalCell) super.clone();
}

}

public class PlantCell implements Cell {

@Override
public PlantCell split() throws CloneNotSupportedException {
    return (PlantCell) super.clone();
}

}

写一个CellRegestry,可以根据不同的细胞类型返回对应的新细胞实例。(有种简单工厂的味道吧?)

public class CellRegestry {
public enum CellType {
    ANIMAL, PLANT
}
private static Map<CellType, Cell> prototypes = new HashMap<>();

static {
    prototypes.put(CellType.ANIMAL, new AnimalCell());
    prototypes.put(CellType.PLANT, new PlantCell());
}

public static Cell getCell(CellType type) throws CloneNotSupportedException {
    // 先根据type获取对应实例,然后clone之
    return prototypes.get(type).split();
}

}

Client使用:

public class Client {
    public static void main(String[] args) {
        try {
            AnimalCell cell1 = (AnimalCell) CellRegestry.getNewCell(CellType.ANIMAL);
            PlantCell cell2 = (PlantCell) CellRegestry.getNewCell(CellType.PLANT);
        } catch (CloneNotSupportedException e) {
            e.printStackTrace();
        }
    }
}

Attention

  1. Cloneable接口是个标记接口(tagging/marker interface),它没有方法。标记接口的唯一目的是可以用instanceof进行类型检查。
  2. 使用 Prototype Pattern 的其中一个原因是因为 clone 比 new 要快,但其实这已经过时了,参考[3]
  3. 可以使用工厂方法模式或者复制构造函数来替代该模式[4]
  4. 需要注意深拷贝浅拷贝的问题。

Reference

InnoDB存储引擎之 —— 锁(二)


锁的算法

  1. Record Lock
    只锁住行。总是去锁定索引,如果没有建索引,就锁主键。

  2. Gap Lock
    锁住一个范围,不包含记录本身

  3. Next-Key Lock (Previous-Key Lock)
    锁住一个范围,包含记录本身。

假设一个索引有10,11,13,20这四个值。那么有如下五个区间:

(-∞, 10)
(10, 11)
(11, 13)
(13, 20)
(20, +∞)
  • Gap Lock 锁的就是上述区间。
  • Next-Key Locking 锁的是上述区间的左开右闭区间。
  • Previous-Key Locking 锁的是上述区间的左闭右开区间。

InnoDB 加锁有如下三条特殊规则:

  1. 当查询的索引仅含有唯一索引的时候,Next-Key Lock 会降级为 Record Lock(联合唯一索引,每一个索引列都要查)
  2. InnoDB 还会对锁住的辅助索引加 Next-Key Lock,并且会给下一个键值加 Gap Lock
  3. 插入某记录时候,会检查插入记录的下一条记录是否被锁住了,如果锁住了,则不允许插入(阻塞)。

InnoDB 在默认的 REPETABLE READ 隔离级别下,使用 Next-Key Lock,在 READ COMMITED 隔离级别下,仅使用 Record Lock

锁的例子

下面举几个例子来讲解:

CREATE TABLE z (a INT, b, INT, PRIMARY KEY(a), KEY(b))

INSERT INTO z SELECT 1, 1;
INSERT INTO z SELECT 3, 1;
INSERT INTO z SELECT 5, 3;
INSERT INTO z SELECT 7, 6;
INSERT INTO z SELECT 10, 8

会话A:执行

SELECT * FROM z WHERE b=3 FOR UPDATE;

我们来分析会锁住哪些记录:
a 是聚集索引,加 Record Lock
b 是辅助索引,加 Next-Key Lock,下一个键值加 Gap Lock

索引 a 被锁住的记录为:

  • 5 — Record Lock

索引 b 被锁住的记录为:

  • (1, 3] — Next-Key Lock
  • (3, 6) — Gap Lock

会话B:如果执行下面这些 SQL ,则都会被阻塞:

  • SELECT FROM z WHERE a = 5 LOCK IN SHARE MODE;
    

    原因:a = 5 的索引已经被加了 Record Lock 的排它锁,所以无法再加一个共享锁了。

  • INSERT INTO z SELECT 4, 2;
    

    原因: 2 落在区间 (1, 3] Next-Key Lock 中

  • INSERT INTO z SELECT 6, 5;
    

    原因: 5 落在区间 (3, 6) Gap Lock 中

  • INSERT INTO z SELECT 2, 2;
    

    原因: 欲插入 b = 2 的记录,而 b = 3 的记录已经被锁住了。因此插入被阻塞。插入 b = 0 的记录没有问题,因为 b = 1 没有被锁。(实践发现这里 b 等于 1 的记录也可以插入,但是 b = 2 的记录被 next-key lock 锁住了呀,为什么呢?

实践了一些其它例子:

  • select * from z where b > 3;
    

    不会锁住 a = 5 的记录。同时 b 的 next-key lock 区间为 (3, +∞)
    可以给 b = 3 的记录加 S 锁 : select * from z where b = 3 lock in share mode;
    不可以 insert b = 3 的记录: INSERT INTO z SELECT 2, 3;

  • select * from z where b >= 3;
    

    会锁住 a = 5 的记录。同时 b 的 next-key lock 区间为 [3, +∞)
    不可以给 b = 3 的记录加 S 锁 : select * from z where b = 3 lock in share mode;
    不可以 insert b = 3 的记录: INSERT INTO z SELECT 2, 3;

阻塞&超时

错误代码: 1205

  • innodb_lock_wait_timeout: 用来控制等待的时间(默认是 50 秒),可以在 MYSQL 数据库运行时进行调整
  • innodb_rollback_on_timeout: 用来设定是否在等待超时时对进行中的事务进行回滚操作(默认是 OFF,代表不回滚)。不可在启动后进行修改。

当发生超时,MYSQL 数据库会抛出一个 1205 的错误,事务出现异常,在大多数情况下不会自动回滚,需要应用层自己去控制是commit还是rollback。

死锁

多个事务因争夺锁资源,造成相互等待,若无外力作用,无法推进下去。
错误代码: 1213
两种方案:

  1. 超时机制
    FIFO。谁先等待,谁先回滚。
  2. wait-for graph
    主动监测死锁,回滚 undo 代价最小的事务
    具体实现细节需要看源码,可能是通过如下两个数据结构去构造有向图:
    • Transaction Wait Lists
    • Lock Lists

      死锁检测通常采用深度优先的算法实现,在 INNODB1.2 版本之前,都是采用递归方式实现。而从 1.2 版本开始,对 wait- for graph 的死锁检测进行了优化,用非递归的方式实现。

死锁例子

  • 例子一
  • 例子二

锁升级

锁升级(Lock Escalation)是指将当前锁的粒度降低。举例来说,数据库可以把个表的 1000 个行锁升级为一个页锁,或者将页锁升级为表锁。如果在数据库的设计中认为锁是一种稀有资源,而且想避免锁的开销,那数据库中会频繁出现锁升级现象。
Microsoft SQL Server 数据库的设计认为锁是一种稀有的资源,在适合的时候会自动地将行、键或分页锁升级为更粗粒度的表级锁。这种升级保护了系统资源,防止系统使用太多的内存来维护锁,在一定程度上提高了效率。
即使在 Microsoft SQL Server20 版本之后,SQL Server 数据库支持了行锁,但是其设计和 INNODB 存储引擎完全不同,在以下情况下依然可能发生锁升级:

  1. 由一句单独的 SQL 语句在一个对象上持有的锁的数量超过了阈值,默认这个阈值为 5000。值得注意的是,如果是不同对象,则不会发生锁升级口
  2. 锁资源占用的内存超过了激活内存的 40%时就会发生锁升级

在 Microsoft SQL Server 数据库中,由于锁是一种稀有的资源,因此锁升级会带来一定的效率提高。但是锁升级带来的一个问题却是因为锁粒度的降低而导致并发性能的降低。

INNODB 存储引擎不存在锁升级的问题。因为其不是根据每个记录来产生行锁的,相反,其根据每个事务访问的每个页对锁进行管理的,采用的是位图的方式。因此不管个事务锁住页中一个记录还是多个记录,其开销通常都是一致的。

SICP - chapter 2


2.1

(define (make-rat n d)
  (let ((t1 (if (< n 0) -1 1)) ;获取n和d的符号位
        (t2 (if (< d 0) -1 1)))
       (cond ((= (* t1 t2) 1) (cons (* t1 n) (* t2 d)))
             ((= t1 -1) (cons n d))
             ((= t2 -1) (cons (* t2 n) (* t2 d))))))
(displayln (make-rat 1 22))
(displayln (make-rat 1 -22))
(displayln (make-rat -1 22))
(displayln (make-rat -1 -22))

2.2

(define (make-point x y)
  (cons x y))

(define (x-point p)
  (car p))

(define (y-point p)
  (cdr p))

(define (make-segment x y)
  (cons x y))

(define (start-segment s)
  (car s))

(define (end-segment s)
  (cdr s))

(define (mid-segment s)
  (let ((startP (start-segment s))
        (endP (end-segment s)))
       (let ((x1 (x-point startP))
             (x2 (x-point endP))
             (y1 (y-point startP))
             (y2 (y-point endP)))
            (make-point (/ (+ x1 x2) 2) (/ (+ y1 y2) 2)))))

(define (print-point p)
  (display "(")
  (display (x-point p))
  (display ",")
  (display (y-point p))
  (display ")"))

(define seg1 (make-segment (make-point 1 1) (make-point 3 3)))
(print-point (mid-segment seg1))

2.3

; 需要运行2.2
(define (make-rec p1 p2)
  (cons p1 p2))

(define (rec-length p)
  (let ((p1 (car p))
        (p2 (cdr p)))
       (let ((x1 (x-point p1))
             (x2 (x-point p2)))
            (abs (- x1 x2)))))

(define (rec-width p)
  (let ((p1 (car p))
        (p2 (cdr p)))
       (let ((y1 (y-point p1))
             (y2 (y-point p2)))
            (abs (- y1 y2)))))

(define (rec-area p)
  (* (rec-length p) (rec-width p)))

(define (rec-perimeter p)
  (* 2 (+ (rec-length p) (rec-width p))))

(define rec1 (make-rec (make-point 0 0) (make-point 3 2)))

(displayln (rec-area rec1))
(displayln (rec-perimeter rec1))

; 为了使rec-area和rec-perimeter过程不改变,另一种定义方式只要提供rec-length和rec-width接口即可。

2.4

(define (cons1 x y)
  (lambda (m) (m x y)))

(define (car1 z)
  (z (lambda (p q) p)))

(define (cdr1 z)
  (z (lambda (p q) q)))

(car1 (cons1 1 2))
(cdr1 (cons1 1 2))

(cdr1 (cons1 1 2))
; =>
(cdr1 (lambda (m) (m 1 2)))
; =>
((lambda (m) (m 1 2)) (lambda (p q) q))
;=>
((lambda (p q) q) 1 2)

2.5


2.17

(displayln "----2.17")
(define (last-pair l)
  (if (null? l)
      null
      (if (null? (cdr l))
          (car l)
          (last-pair (cdr l)))))

(last-pair (list 1 2 3))
(last-pair (list))

2.18

(define (reverse l)
  (if (null? l)
      null
      (append (reverse (cdr l)) (list (car l)))))

(reverse (list))
(reverse (list 1))
(reverse (list 1 2 3))

2.20

(define (same-parity x . xs)
  (define (same-p n)
        (= (remainder x 2) (remainder n 2)))
  (if (null? xs)
      null
      (if (= (remainder x 2) (remainder (car xs) 2))
          (cons (car xs) (apply same-parity (cons x (cdr xs))))
          (apply same-parity (cons x (cdr xs))))))

(same-parity 111 2 3 4 5 6 7 8 9)
(same-parity 100 2 3 4 5 6 7 8 9)

2.23

(define (for-each f xs)
  (if (null? xs)
      #t
      (begin
        (f (car xs))
        (for-each f (cdr xs)))))

(for-each (lambda (x) (displayln x)) (list 1 2 3))

2.25

(define x25-1 (list 1 3 (list 5 7) 9))
(car (cdr (car (cdr (cdr x25-1)))))

(define x25-2 (list (list 7)))
(car (car x25-2))

(define x25-3 (list 1 (list 2 (list 3 (list 4 (list 5 (list 6 7)))))))
(car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr x25-3))))))))))))

2.26

(define x26 (list 1 2 3))
(define y26 (list 4 5 6))
(append x26 y26)
(cons x26 y26)
(list x26 y26)

2.27

(define (deep-reverse l)
  (if (null? l)
      null
      (if (list? (car l))
          (append (deep-reverse (cdr l)) (list (deep-reverse (car l))))
          (append (deep-reverse (cdr l)) (list (car l))))))
(deep-reverse '())
(deep-reverse '(1))
(deep-reverse '(1 2))
(deep-reverse (list (list 1 2) (list 3 4)))
(deep-reverse '((1 2) (3 4) 5 6 (7 8)))

2.28

(displayln "二叉树版抽象")
(define (left-tree tree)
  (car tree))
(define (right-tree tree)
  (car (cdr tree)))
(define (fringe-bin tree)
  (cond ((null? tree) null)
        ((pair? tree) (append
                         (fringe-bin (left-tree tree))
                         (fringe-bin (right-tree tree))))
        (else (list tree))))

; 多叉树无法work
;(fringe-bin (list (list 1 2 3) (list 4 5 6) (list 7 8) 9))
(define x28 (list (list 1 2) (list 3 4)))
(fringe-bin x28)
(fringe-bin (list x28 x28))

; 多叉树work版
(define (fringe tree)
  (cond ((null? tree) null)
        ((pair? tree) (append
                         (fringe (car tree))
                         (fringe (cdr tree))))
        (else (list tree))))
(fringe (list (list 1 2 3) (list 4 5 6) (list 7 8) 9))

Maximum Subarray


原题目链接

题目描述

寻找数列的最大子列和。

分析

动态规划问题,见leetcode-3的讲解。

定义s[i]是以第i个元素结尾的最大子列和。

        nums[i] + s[i-1]  ,if s[i-1] >= 0
s[i] ={
        nums[i]           ,if s[i-1] < 0

代码

int maxSubArray(vector<int>& nums) {
    int curSum = nums[0];
    int maxSum = curSum;
    for (int i = 1; i < nums.size(); i++) {
        curSum = nums[i] + (curSum > 0 ? curSum : 0);
        if (curSum > maxSum) maxSum = curSum;
    }
    return maxSum;
}

下一个排列


原题链接

算法介绍

算法介绍

rust 实现(初学)

impl Solution {
    pub fn reverse(nums: &mut Vec<i32>, mut i: usize, mut j: usize) {
        while i < j {
            nums.swap(i, j);
            i += 1;
            j -= 1;
        }
    }
<span class="k">pub</span> <span class="k">fn</span> <span class="nf">next_permutation</span><span class="p">(</span><span class="n">nums</span><span class="p">:</span> <span class="o">&amp;</span><span class="k">mut</span> <span class="nb">Vec</span><span class="o">&lt;</span><span class="nb">i32</span><span class="o">&gt;</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">if</span> <span class="n">nums</span><span class="nf">.len</span><span class="p">()</span> <span class="o">&lt;</span> <span class="mi">2</span> <span class="p">{</span>
        <span class="k">return</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">let</span> <span class="k">mut</span> <span class="n">i</span> <span class="o">=</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span>
    <span class="c">// 从右向左找第一个升序对[i,i+1]</span>
    <span class="k">for</span> <span class="n">j</span> <span class="nf">in</span> <span class="p">(</span><span class="mi">0</span><span class="o">..=</span><span class="p">(</span><span class="n">nums</span><span class="nf">.len</span><span class="p">()</span> <span class="o">-</span> <span class="mi">2</span><span class="p">))</span><span class="nf">.rev</span><span class="p">()</span> <span class="p">{</span>
        <span class="k">if</span> <span class="n">nums</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">nums</span><span class="p">[</span><span class="n">j</span> <span class="o">+</span> <span class="mi">1</span><span class="p">]</span> <span class="p">{</span>
            <span class="n">i</span> <span class="o">=</span> <span class="n">j</span> <span class="k">as</span> <span class="nb">i32</span><span class="p">;</span>
            <span class="k">break</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">}</span>

    <span class="k">if</span> <span class="n">i</span> <span class="o">&gt;=</span> <span class="mi">0</span> <span class="p">{</span>
        <span class="c">// 从右向左找第一个比 nums[i] 大的数 nums[s]</span>
        <span class="k">for</span> <span class="n">j</span> <span class="nf">in</span> <span class="p">(</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="o">..</span><span class="p">(</span><span class="n">nums</span><span class="nf">.len</span><span class="p">()</span> <span class="k">as</span> <span class="nb">i32</span><span class="p">))</span><span class="nf">.rev</span><span class="p">()</span> <span class="p">{</span>
            <span class="k">if</span> <span class="n">nums</span><span class="p">[</span><span class="n">j</span> <span class="k">as</span> <span class="nb">usize</span><span class="p">]</span> <span class="o">&gt;</span> <span class="n">nums</span><span class="p">[</span><span class="n">i</span> <span class="k">as</span> <span class="nb">usize</span><span class="p">]</span> <span class="p">{</span>
                <span class="n">nums</span><span class="nf">.swap</span><span class="p">(</span><span class="n">i</span> <span class="k">as</span> <span class="nb">usize</span><span class="p">,</span> <span class="n">j</span> <span class="k">as</span> <span class="nb">usize</span><span class="p">);</span>
                <span class="k">break</span><span class="p">;</span>
            <span class="p">}</span>
        <span class="p">}</span>
    <span class="p">}</span>
    <span class="nn">Solution</span><span class="p">::</span><span class="nf">reverse</span><span class="p">(</span><span class="n">nums</span><span class="p">,</span> <span class="p">(</span><span class="n">i</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span> <span class="k">as</span> <span class="nb">usize</span><span class="p">,</span> <span class="n">nums</span><span class="nf">.len</span><span class="p">()</span> <span class="o">-</span> <span class="mi">1</span><span class="p">);</span>
<span class="p">}</span>

}

rust 学习迭代器之后

impl Solution {
    pub fn next_permutation(nums: &mut Vec<i32>) {
        // 从右向左找第一个升序对[i,i+1]
        if let Some(i) = nums[..nums.len() - 1].iter().enumerate().rposition(|(pos, _)| nums[pos] < nums[pos + 1]) {
            // 从右向左找第一个比 nums[i] 大的数 nums[x]
            if let Some(x) = nums[(i + 1)..].iter().rposition(|item| item > &nums[i]) {
                nums.swap(i, i + 1 + x);
            }
            &nums[i + 1..].reverse();
        } else {
            nums.reverse();
        }
    }
}

两年前写的 Java 代码

class Solution {
    public static void reverse(int[] nums, int start, int end) {
        int i = start;
        int j = end;
        while (i <= j) {
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
            i++;
            j--;
        }
    }
<span class="kd">public</span> <span class="kt">void</span> <span class="nf">nextPermutation</span><span class="o">(</span><span class="kt">int</span><span class="o">[]</span> <span class="n">nums</span><span class="o">)</span> <span class="o">{</span>
    <span class="kt">int</span> <span class="n">flag</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>
    <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">nums</span><span class="o">.</span><span class="na">length</span> <span class="o">-</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="o">;</span> <span class="n">i</span><span class="o">--)</span> <span class="o">{</span>
        <span class="k">if</span> <span class="o">(</span><span class="n">nums</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">&gt;</span> <span class="n">nums</span><span class="o">[</span><span class="n">i</span> <span class="o">-</span> <span class="mi">1</span><span class="o">])</span> <span class="o">{</span>
            <span class="n">flag</span> <span class="o">=</span> <span class="n">i</span><span class="o">;</span>
            <span class="k">break</span><span class="o">;</span>
        <span class="o">}</span>
    <span class="o">}</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">flag</span> <span class="o">==</span> <span class="mi">0</span><span class="o">)</span> <span class="o">{</span> <span class="c1">// 如果已经是逆序的了,下一个全排列是全增序的</span>
        <span class="n">reverse</span><span class="o">(</span><span class="n">nums</span><span class="o">,</span> <span class="mi">0</span><span class="o">,</span> <span class="n">nums</span><span class="o">.</span><span class="na">length</span> <span class="o">-</span> <span class="mi">1</span><span class="o">);</span>
    <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
        <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">nums</span><span class="o">.</span><span class="na">length</span> <span class="o">-</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o">&gt;=</span> <span class="n">flag</span><span class="o">;</span> <span class="n">i</span><span class="o">--)</span> <span class="o">{</span>
            <span class="k">if</span> <span class="o">(</span><span class="n">nums</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">&gt;</span> <span class="n">nums</span><span class="o">[</span><span class="n">flag</span><span class="o">-</span><span class="mi">1</span><span class="o">])</span> <span class="o">{</span>
                <span class="kt">int</span> <span class="n">tmp</span> <span class="o">=</span> <span class="n">nums</span><span class="o">[</span><span class="n">i</span><span class="o">];</span>
                <span class="n">nums</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">=</span> <span class="n">nums</span><span class="o">[</span><span class="n">flag</span><span class="o">-</span><span class="mi">1</span><span class="o">];</span>
                <span class="n">nums</span><span class="o">[</span><span class="n">flag</span><span class="o">-</span><span class="mi">1</span><span class="o">]</span> <span class="o">=</span> <span class="n">tmp</span><span class="o">;</span>
                <span class="k">break</span><span class="o">;</span>
            <span class="o">}</span>
        <span class="o">}</span>
        <span class="n">reverse</span><span class="o">(</span><span class="n">nums</span><span class="o">,</span> <span class="n">flag</span><span class="o">,</span> <span class="n">nums</span><span class="o">.</span><span class="na">length</span> <span class="o">-</span> <span class="mi">1</span><span class="o">);</span>
    <span class="o">}</span>
<span class="o">}</span>

}

Hamming Distance


原题目链接

题目描述

计算两个32位整数的Hamming distance

1 : (0 0 0 1)
4 : (0 1 0 0)
       ↑   ↑

分析

问题的关键是统计一个数的二进制表示中有多少个1

  1. 遍历异或所得数的每一位,统计1的个数,判断最低位为是否是1可以用 n % 2 或者用 n & 1
    int hammingDistance(int a, int b) {
     int sum = 0;
     for (int i = 0; i < 32; i++) {
         sum += (a & 1) ^ (b & 1);
         a >>= 1;
         b >>= 1;
     }
     return sum;
    }
    
  2. 使用n & (n-1)可以消去最后一位1,判断消到0一共消了多少次。
    int hammingDistance(int a, int b) {
     int count = 0;
     int n = a ^ b;
     while(n) {
         n = n & (n-1);
         count++;
     }
     return count;
    }
    
  3. 参考 Java 里的 Integer.bitCount 方法
    public static int bitCount(int i) {
     i = i - ((i >>> 1) & 0x55555555);
     i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
     i = (i + (i >>> 4)) & 0x0f0f0f0f;
     i = i + (i >>> 8);
     i = i + (i >>> 16);
     return i & 0x3f;
    }
    

搜索插入位置


原题链接

题目描述

分析

实现

class Solution {
    public int searchInsert(int[] nums, int target) {
        int l = 0, r = nums.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

Add Two Numbers


原题目地址

题目描述

每一个链表代表一个数,比如 2->3->4->null 代表的就是 432。现在输入是两个链表,代表两个数,输出是这两个数的和对应的链表。

分析

这是我的第一篇算法记录,不能为了做题而做题,而应该多思考我们能够从一道题中获得什么东西。
这道题思路上比较简单,就是从链表的第一个结点开始,计算相加和进位。但是有一个编程技巧可以简化我们代码的表达。

int val1 = (p1 == NULL) ? 0 : p1->val;
int val2 = (p2 == NULL) ? 0 : p2->val;

当其中一个链走到头但另一个链没有走到头的时候,另一个链表的节点在下一次循环中,值为0。如果不采用这种方式,那么我们可能要分别判断如果p1到头了该怎么做,p2到头了改怎么做等等。

总结一下:

  1. 当有多个数据结构需要并行操作互运算时,为了防止体量的不同而导致逻辑处理变复杂,可考虑采用这种方式来清洁代码逻辑。
  2. 不带头结点的单链表建表套路。

代码

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode *p1 = l1;
    struct ListNode *p2 = l2;
    struct ListNode *head = NULL;
    struct ListNode *ptr = NULL;
    int carry = 0;
    while (p1 != NULL || p2 != NULL || carry) {
        int val1 = (p1 == NULL) ? 0 : p1->val;
        int val2 = (p2 == NULL) ? 0 : p2->val;
        int newVal = val1 + val2 + carry;
    <span class="n">carry</span> <span class="o">=</span> <span class="n">newVal</span> <span class="o">/</span> <span class="mi">10</span><span class="p">;</span>
    <span class="n">newVal</span> <span class="o">%=</span> <span class="mi">10</span><span class="p">;</span>

    <span class="k">if</span> <span class="p">(</span><span class="n">head</span> <span class="o">==</span> <span class="nb">NULL</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">head</span> <span class="o">=</span> <span class="p">(</span><span class="k">struct</span> <span class="nc">ListNode</span> <span class="o">*</span><span class="p">)</span><span class="n">malloc</span><span class="p">(</span><span class="k">sizeof</span><span class="p">(</span><span class="k">struct</span> <span class="nc">ListNode</span><span class="p">));</span>
        <span class="n">head</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">=</span> <span class="n">newVal</span><span class="p">;</span>
        <span class="n">head</span><span class="o">-&gt;</span><span class="n">next</span> <span class="o">=</span> <span class="nb">NULL</span><span class="p">;</span>
        <span class="n">ptr</span> <span class="o">=</span> <span class="n">head</span><span class="p">;</span>
    <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
        <span class="k">struct</span> <span class="nc">ListNode</span> <span class="o">*</span><span class="n">newNode</span> <span class="o">=</span> <span class="p">(</span><span class="k">struct</span> <span class="nc">ListNode</span> <span class="o">*</span><span class="p">)</span><span class="n">malloc</span><span class="p">(</span><span class="k">sizeof</span><span class="p">(</span><span class="k">struct</span> <span class="nc">ListNode</span><span class="p">));</span>
        <span class="n">newNode</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">=</span> <span class="n">newVal</span><span class="p">;</span>
        <span class="n">newNode</span><span class="o">-&gt;</span><span class="n">next</span> <span class="o">=</span> <span class="nb">NULL</span><span class="p">;</span>
        <span class="n">ptr</span><span class="o">-&gt;</span><span class="n">next</span> <span class="o">=</span> <span class="n">newNode</span><span class="p">;</span>
        <span class="n">ptr</span> <span class="o">=</span> <span class="n">newNode</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">p1</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">p1</span> <span class="o">=</span> <span class="n">p1</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">p2</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">p2</span> <span class="o">=</span> <span class="n">p2</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">}</span>
<span class="k">return</span> <span class="n">head</span><span class="p">;</span>

}

理解 JavaScript 异步编程(一)


先从同步操作说起。

首先我们有一个函数,可以返回把传入参数加一的结果。

var syncPlusOne = function(a) {
  return a+1
}

如果我们需要把每一次调用的结果作为下一次调用的参数,就这样调用:

var continuousSyncPlusOne = function (s) {
  var a = syncPlusOne(s)
  var b = syncPlusOne(a)
  var c = syncPlusOne(b)
}

如果我们现在有一个异步Plus函数呢?

var wrongAsyncPlusOne = function(a) {
  setTimeout(function() {
    return a+1
  }, Math.random()*1000)
}

调用这个函数,会直接返回undefined,因为异步过程会直接返回,而不会阻塞。对于一个异步过程,我们有两种方法可以得知它的计算过程是否结束。

一种办法是轮训,比如如下代码:

var tv
setTimeout(function (){
  tv = 1
}, 1000);
while (true) {
  if (tv != undefined) {
    console.log("tv is set to :" + tv);
    break;
  }
}

我们在while循环中不断的轮询tv的值,直到tv被赋值。但很不幸,这个代码并不会按照我们的想法执行,这与javascript的运行机制有关,这里不展开讲,正确的写法如下:

var tv
setTimeout(function (){
  tv = 1
}, 1000);

var intervalId = setInterval(function() {
  if (tv != undefined) {
    console.log("tv is set to :" + tv);
    clearInterval(intervalId);
  }
}, 0)

另一种方法,是这个函数执行结束后自己告诉我们:

var tv
setTimeout(function (){
  tv = 1
  console.log("tv is set to :" + tv)
}, 1000);

我们在函数体内调用 console.log() 来表示 tv 的值已经被计算好了,本质上是将 tv 计算好之后的值,主动传递给了后续过程。如果把需要这个异步计算结果的函数作为参数传递进来,并在计算结束后将结果传递给它,那么这个函数就被称为回调函数
setTimeout的第一个参数传入的也是一个回调函数,当计时结束后,会调用回调函数。其实 setTimeoutsetInterval 的第三个可选参数可以给回调函数传参。)

那么重新改写我们之前的异步Plus如下:

var asyncPlusOne = function(a, callback) {
  setTimeout(function() {
    callback(a+1)
  }, Math.random()*1000)
}

如果我们需要得到某个数字连续调用asyncPlusOne之后的结果,则要写为:

var continuousAsyncPlusOne = function(s) {
  asyncPlusOne(s, function(a) {
    asyncPlusOne(a, function(b) {
      asyncPlusOne(b, function(c) {
        console.log(c); // 3
      })
    })
  })
}
continuousAsyncPlusOne(0);

es6语法可以这样写:

var continuousAsyncPlusOne = function(s) {
  asyncPlusOne(s, (a) => {
    asyncPlusOne(a, (b) => {
      asyncPlusOne(b, (c) => {
        console.log(c); // 3
      })
    })
  })
}

第一次写这种代码,感觉还挺酷的样子。但是久而久之,代码中到处都是这种callback结构,太不简洁了,这被称为 callback hell

那么我们如何把异步调用变成同步的书写方式呢?比如像这样子:

var a = asyncPlusIWant(s)
var b = asyncPlusIWant(a)
var c = asyncPlusIWant(b)
console.log(c);

我们希望:

  1. asyncPlusIWant() 是异步的
  2. 它能立即返回计算之后的结果(而不是undifined)

这两条不是自相矛盾吗。唉,如果我们的语句走到 asyncPlusIWant() 时,能够停下来,等待这个异步过程执行完成之后,再继续执行下面的语句,就好了。

Wait! 停下来再继续,好熟悉的东西,ES6 引入的 Generator 不是可以做到这件事吗!
把我们的语句放到 Generator 中看看!

var genAsync = function* (s) {
  var a = yield asyncPlusOne(s)
  console.log(a) // undefined
  var b = yield asyncPlusOne(a)
  var c = yield asyncPlusOne(b)
}
console.log(g.next().value); // undefined

并没有得到正确的输出,不是说好的会停下来的吗?
其实这里确实停了,只不过不是我们想象的那种停,这里两个地方输出都是undefined原因如下:

  • console.log(a) 输出 undefined 是因为 yield <expression> 的值取决于外部调用next时传入的值,外部调用g.next()时候并没有传值进去。
  • console.log(g.next().value) 输出 undefined 是因为 g.next().value 应该拿到的是表达式 asyncPlusOne(s) 的值,而 asyncPlusOne 是异步的,它直接返回了 undefined

那么如何才可以结合 Generator 函数实现异步过程的同步调用呢?

为了实现我们的目标,考虑如下辅助函数:

var g = function(f){
  return function (args){
    return function (callback){
      return f(args, callback)
    }
  }
}

那么

[mathrm{f(s, callback) = g(f)(s)(callback)}]

好吧,你看出来了,这里就是做了一个柯里化。

那我们令

[mathrm{asyncPlusIWant = g(asyncPlusOne)}]

var asyncPlus = function (a, callback) {
  setTimeout(function () {
    callback(a + 1);
  }, Math.random() * 1000);
}

var asyncPlusIWant = g(asyncPlus)

var genAsync =  function* (s) {
  var a = yield asyncPlusIWant(s);
  console.log('async a: ' + a)
  var b = yield asyncPlusIWant(a);
  console.log('async b: ' + b)
  var c = yield asyncPlusIWant(b);
  console.log('async c: ' + c)
  return c+1
};

var run = function run(gen) {
  function go(lastRes) {
    // 1.[唤醒],把上一次计算出的值放到LHS(left-hand side),然后移动到下一个异步调用的位置停下来
    var res = gen.next(lastRes);
    if (res.done) return;
    // 2.[执行],调用res.value(go)将开始执行异步计算,计算完成后调用会调用go继续唤醒generator
    res.value(go);
  }
  go()
}
run(genAsync(0));

这里的辅助函数 g 被称作 Thunk 函数

var Thunk = function(fn){
  return function (){
    var args = Array.prototype.slice.call(arguments);
    return function (callback){
      args.push(callback);
      return fn.apply(this, args);
    }
  };
};

var thunkFunc = Thunk(func); 可以把fn包裹成另一个函数 thunkFunc
他改变了原来 func 的调用方式:

func(arg_1, arg_2, ... , arg_k, callback)
func(arg_1, arg_2, ... , arg_k)(callback)

通过上面的 run() 方法,执行 run(genAsync) 就可以依次执行三个异步函数了。

这件很酷的事情本质是什么?

使用 Thunk 和 Generator 使异步函数以同步的方式书写,本质是:

Thunk 把异步函数的「执行」从 Generator 内,分离到了 Generator 外部,把 Generator 的「唤醒」放到了「在外部执行的异步操作的回调函数内」,所以整个执行流程变成了,在外部执行的异步函数,通过回调,不断的去唤醒 Generator 继续执行后续操作。

Matlab C++ 混合编程笔记


1. 直接调用C/C++生成的DLL

1.1 用VS生成dll

新建一个win32 dll工程,工程名为test,如果你的MATLAB和系统都是64位的,这里要修改平台参数到64位。
例如要导出add()函数,那么头文件里就要写:

//main.h
extern "C" double __declspec(dllexport)add(double x, double y);

注意extern "C"不能掉,表明它按照C的编译和连接规约来编译和连接,你可以认为这里的C++函数将要给C调用,因为下面讲到的MATLAB的loadlibrary()函数只能识别C格式的DLL。
源文件内容为:

//main.cpp
#include "main.h"
double add(double a, double b)
{
  return a + b;
}

这里的函数返回类型必须是数值类型
例如编写返回字符的函数 rep_str

char rep_str(char s)
{
  return s;
}

在Matlab中调用返回错误:

>> calllib('test','rep_str','a')
Error using calllib
Array must be numeric or logical.

1.2 在matlab中调用dll中的函数

将生成的test.dll与这里的main.h头文件放在同一个目录下,并把头文件中的extern "C"删除,因为C语言中没有这种写法,而MATLAB以为自己在调用C的DLL。
在matlab中使用loadlibrary()函数载入dll,使用libfunctions()函数查看该dll中包含的函数。
运行结果:

>>loadlibrary('test.dll', 'main.h')
>>libfunctions('test')

Functions in library test:

add      rep_str  

使用calllib()函数调用dll中的函数:

>> calllib('test', 'add', 8, 13)

ans =

    21

1.3 常见错误与注意事项

  1. 参数个数必须匹配
    >> calllib('test', 'add', 8)
    Error using calllib
    No method with matching signature.
    
  2. 参数必须是数值类型逻辑类型
    >> calllib('test', 'add', 'a', 'b')
    Error using calllib
    Array must be numeric or logical.
    
  3. 且必须是标量
    >> calllib('test', 'add', [1,2], [3,4])
    Error using calllib
    Parameter must be scalar.
    
  4. dll文件不能在某个磁盘的根目录,如"F:"

  5. 头文件的编写最好统采用如下形式:
    #ifdef __cplusplus
    extern "C" {
    #endif
    //exported functions...
    extern Type1 func1(...);
    extern Type2 func2(...);
    ...
    #ifdef __cplusplus
    }
    #endif
    

    这样就不需要二次修改头文件了。

2. 使用mex编译C++代码

不细讲了,见参考文献3,讲解了如何编写 mexFunction

3. 参考文献

  1. c++中的 extern “C”
  2. C++项目中的extern “C” {}
  3. Matlab与C/C++混合编程接口及应用

Factory Method


定义

定义一个创建对象的接口,让其子类自己决定实例化哪一个工厂类,工厂模式使其创建过程延迟到子类进行.

实践

工厂方法模式需要使用继承。在《大话数据结构》里使用的是继承一个只含有工厂方法的接口。《Head First 设计模式》里是继承一个抽象类,这个类不仅包括未实现的抽象工厂方法,而且实现了操纵产品的方法。这个抽象类就是产品的使用者。我们使用后者来讲述这个设计模式。

首先,Product同simple factory pattern
然后定义一个抽象的基类,其中protected abstract Product getProduct(String type)就是工厂方法,它将在子类被实现。

public abstract class AbstractCreator {
    public void operation() {
        //这里可以算是 client 的代码了
        Product product = getProduct();
        product.process();
    }
    // factory method
    protected abstract Product getProduct();
}

有几种产品就创建几个ConcreteCreator类

public class ConcreteCreator1 extends AbstractCreator {
    @Override
    protected Product getProduct() {
        return new ConcreteProduct1();
    }
}
public class ConcreteCreator2 extends AbstractCreator {
    @Override
    protected Product getProduct() {
        return new ConcreteProduct2();
    }
}
...

使用方法:

AbstractCreator creator1 = new ConcreteCreator1();
creator1.operation();
AbstractCreator creator2 = new ConcreteCreator2();
creator2.operation();

当需要增加一种产品的时候,新建一个类继承AbstractCreator,实现工厂方法getProduct即可。工厂方法模式客服了简单工厂模式违背「开放-封闭」原则的缺点。
我们来看一下,当增加一个产品的时候,我们需要做哪些事情:

  1. 添加一个产品类——>这个是无法避免的,我们对扩展开放。
  2. 如果工厂方法是在某个抽象类中,新建一个类继承该抽象类,覆盖工厂方法,返回新产品。
  3. 如果工厂方法在接口IFactory中,那么就要新建一个工厂实现IFactory来返回该产品。
  4. 在client使用时,得new一个新的类来产生新产品。

工厂方法也可以参数化,变得像一个简单工厂

public abstract class AbstractCreator {
    public void operation(String type) {
        Product product = getProduct(type);
        product.process();
    }
    // factory method
    protected abstract Product getProduct(String type);
}

public class ConcreteCreator extends AbstractCreator {
@Override
protected Product getProduct(String type) {
if (type.equals("1")) {
return new ConcreteProduct1();
} else if (type.equals("2")) {
return new ConcreteProduct2();
} else {
return null;
}
}
}

使用方法:

AbstractCreator creator = new ConcreteCreator();
creator.operation("1");
creator.operation("2");

如何进行二分查找


模板

记住这个模板,它返回的是: 第一个满足 f(m) == true 的位置

想要知道数学推导,请参考[1]
想要知道模板的应用,请参考[2]

class Solution {
    public int binarySearch(int[] nums) {
        int l = 0, r = nums.length;
        if (l < r) {
            int m = l + (r - l) / 2;
            if (f(m)) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
}

参考资料

SICP - chapter 1


1.3

(define (max_tow_sum a b c)
        (cond ((and (>= a b) (>= b c)) (+ a b))
              ((and (>= a c) (>= c b)) (+ a c))
              ((and (>= b a) (>= a c)) (+ b a))
              ((and (>= b c) (>= c a)) (+ b c))
              ((and (>= c a) (>= a b)) (+ c a))
              ((and (>= c b) (>= b a)) (+ c b))))

(define (max_tow_sum2 a b c)
        (- (+ a b c) (min a b c)))

(displayln (max_tow_sum2 1 2 3))

1.4

(define (a-plus-abs-b a b)
  ((if (> b 0) + -) a b))

1.5

(define (p) (p))
(define (test x y)
  (if (= x 0)
      0
      y))

1.6

(define (decrease a)
  (new-if (> a 0)
      (decrease (- a 1))
      a))

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

1.7

;很大的数,good_enough会爆掉;很小的数,即使0.001作为衡量标准也很大了。

(define (improve guess n)
  (/ (+ guess (/ n guess)) 2))

(define (good-enough? x y)
  (< (abs (- x y)) 0.000001))

(define (sqrt-iter1 last-guess cur-guess n)
  (if (good-enough? last-guess cur-guess)
      cur-guess
      (sqrt-iter1 cur-guess (improve cur-guess n) n)))
(define (my-sqrt1 n)
  (sqrt-iter1 (/ n 2) (+ (/ n 2) 1.0) n))

(define (sqrt-iter2 guess n)
  (let ((next-guess (improve guess n)))
  (if (good-enough? guess next-guess)
      next-guess
      (sqrt-iter2 next-guess n))))
(define (my-sqrt2 n)
  (sqrt-iter2 1.0 n))

(displayln (my-sqrt2 4))

1.8

; 需要先执行1.7
(define (improve3 guess n)
  (/ (+ (/ n (* guess guess)) (* 2 guess)) 3))
(define (sqrt3-iter guess n)
  (let ((next-guess (improve3 guess n)))
  (if (good-enough? guess next-guess)
      next-guess
      (sqrt3-iter next-guess n))))
(define (my-sqrt3 n)
  (sqrt3-iter 1.0 n))

(displayln (my-sqrt3 27.0))

1.12

;1.12
(define (pascal row col)
  (cond ((= row 1) 1)
        ((= col row) 1)
        (else (+ (pascal (- row 1) col) (pascal (- row 1) (+ col 1))))))

(displayln (pascal 5 3))

1.21

; 1.21

(define (square n)
  (* n n))

(define (smallest-divisor n)
  (find-divisor n 2))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

(define (divides? a b)
  (= (remainder b a) 0))

(define (prime? n)
  (= n (smallest-divisor n)))

(displayln (smallest-divisor 199))
(displayln (smallest-divisor 1999))
(displayln (smallest-divisor 19999))

1.22

; 先运行1.21,,会比较卡
; 1.22
(define (timed-prime-test n)
  (display "start-with: ")
  (displayln n)
  (start-prime-test n (current-milliseconds) 0))

(define (start-prime-test n start-time found-num)
  (if (= found-num 3)
      (report-prime (- (current-milliseconds) start-time))
      (if (prime? n)
          (begin
            (display "found: ")
            (displayln n)
            (start-prime-test (+ 2 n) start-time (+ found-num 1)))
          (start-prime-test (+ 2 n) start-time found-num))))

(define (report-prime elapsed-time)
  (display "time elapsed: ")
  (displayln elapsed-time)
  (displayln "-----------"))

(displayln (timed-prime-test 10000000001))
(displayln (timed-prime-test 100000000001))
;(displayln (timed-prime-test 1000000000001))
;(displayln (timed-prime-test 10000000000001))
;(displayln (timed-prime-test 100000000000001))
;(displayln (timed-prime-test 1000000000000001))

1.23

; 需要先运行1.22
; 1.23
(define (smallest-divisor2 n)
  (find-divisor2 n 2))

(define (find-divisor2 n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor2 n (next test-divisor)))))

(define (next n)
  (if (= n 2)
      3
      (+ n 2)))

(define (prime?2 n)
  (= n (smallest-divisor2 n)))

(define (start-prime-test2 n start-time found-num)
  (if (= found-num 3)
      (report-prime (- (current-milliseconds) start-time))
      (if (prime?2 n)
          (begin
            (display "found: ")
            (displayln n)
            (start-prime-test2 (+ 2 n) start-time (+ found-num 1)))
          (start-prime-test2 (+ 2 n) start-time found-num))))

(define (timed-prime-test2 n)
  (display "start-with: ")
  (displayln n)
  (start-prime-test2 n (current-milliseconds) 0))

; 差距确实是两倍
(displayln (timed-prime-test 100000000001))
(displayln (timed-prime-test2 100000000001))
; (displayln (timed-prime-test 1000000000001))
; (displayln (timed-prime-test2 1000000000001))
; (timed-prime-test 10000000000001)
; (timed-prime-test2 10000000000001)
; (timed-prime-test 100000000000001)
; (timed-prime-test2 100000000000001)
; (timed-prime-test 1000000000000001)
; (timed-prime-test2 1000000000000001)

1.24

; 需要先运行1.23
; 1.24

(define (expmod base exp m)
  (cond ((= exp 0)   1)
        ((even? exp) (remainder (square (expmod base (/ exp 2) m)) m))
        (else        (remainder (* base (expmod base (- exp 1) m))
                                   m))))

(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1))))) ; should be (random (- n 1))

(define (fast-prime? n times)
  (cond ((= times 0) #t)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else #f)))

(define (start-prime-test3 n start-time found-num)
  (if (= found-num 3)
      (report-prime (- (current-milliseconds) start-time))
      (if (fast-prime? n 100)
          (begin
            (display "found: ")
            (displayln n)
            (start-prime-test3 (+ 2 n) start-time (+ found-num 1)))
          (start-prime-test3 (+ 2 n) start-time found-num))))

(define (timed-prime-test3 n)
  (display "start-with: ")
  (displayln n)
  (start-prime-test3 n (current-milliseconds) 0))

(displayln (timed-prime-test 100000000001))
(displayln (timed-prime-test2 100000000001))
;不知道为什么浏览器跑test3会死循环
;(displayln (timed-prime-test3 100000000001))

1.27

; 需要先运行1.24
; 1.27
(prime? 561)
(fermat-test 561)
(fermat-test 1105)
(fermat-test 1729)
(fermat-test 2465)

1.28


(define (square n)
  (* n n))

(define (expmod base exp m)
  (cond ((= exp 0)   1)
        ((even? exp) (remainder (square (expmod base (/ exp 2) m)) m))
        (else        (remainder (* base (expmod base (- exp 1) m))
                                   m))))

(define (miller-rabin-test n)
  (define (test-p p k)
    (cond ((= k (- p 1)) true)
          ((= (remainder (* k k) p) 1) false)
          (else (test-p p (+ k 1)))))
  (define (try-it a)
    (= (expmod a (- n 1) n) 1))
  (cond ((not (test-p n 2)) false)
        ((try-it (+ 1 (random (- n 1)))) true)
        (else false)))

(define (fast-prime2? n times)
  (cond ((= n 2) true)
        ((= times 0) true)
        ((miller-rabin-test n) (fast-prime2? n (- times 1)))
        (else false)))

; 测试一下
(define (list-prime-less-than n)
  (cond ((= n 1) (displayln ""))
        ((fast-prime2? n 100)
            (displayln n)
            (list-prime-less-than (- n 1)))
        (else (list-prime-less-than (- n 1)))))

(list-prime-less-than 100)

Thread Local 之我见


引子

我们有了一个线程

Thread t = new Thread();

我们希望放置一些数据,使得在该线程的任何地方都可以访问和修改这些数据,这就是 ThreadLocal 对象。理所应当的,我们应该把这个些数据存放在当前 Thread 的对象上,这也就是为什么 Thread 类上有一个 threadLocals 字段,它的类型是 ThreadLocalMap,ThreadLocalMap 顾名思义是一个 Map,key 为 ThreadLocal 对象,value 是我们要存储的对象。

/* ThreadLocal values pertaining to this thread. This map is maintained
 * by the ThreadLocal class. */
ThreadLocal.ThreadLocalMap threadLocals = null;

每一个 threadLocal 对象只能存放「一个东西」。如果你想存放苹果,再存放书,得分别为要存放的东西创建 ThreadLocal 对象:

ThreadLocal<Apple> appleThreadLocal = new ThreadLocal<>();
ThreadLocal<Book> bookThreadLocal = new ThreadLocal<>();

不过,到目前为止,仍然是什么特殊的事情都没有发生,因为 ThreadLocal 的构造函数是空的

/**
    * Creates a thread local variable.
    * @see #withInitial(java.util.function.Supplier)
    */
public ThreadLocal() {
}

多个线程可以使用同一个 ThreadLocal 对象:

public static ThreadLocal<Apple> appThreadLocal = new ThreadLocal<>();

// thread1 // thread2
... ...
Apple apple1 = new Apple(); Apple apple2 = new Apple();
appThreadLocal.set(apple1); appThreadLocal.set(apple2);
... ...
appThreadLocal.get(); // apple1 appThreadLocal.get(); // apple2

在整个 Thread.java 的源码中,只有 exit() 方法使用到了 threadLocals

private void exit() {
    ...
    /* Speed the release of some of these resources */
    threadLocals = null;
    ...
}

而 threadLocalMap 的初始化,是在第一个 ThreadLocal 对象调用 set 或 get 的时候发生的

/**
 * Create the map associated with a ThreadLocal. Overridden in
 * InheritableThreadLocal.
 *
 * @param t the current thread
 * @param firstValue value for the initial entry of the map
 */
void createMap(Thread t, T firstValue) {
    t.threadLocals = new ThreadLocalMap(this, firstValue);
}

我们来看一下set方法是如何执行的

/**
 * Sets the current thread's copy of this thread-local variable
 * to the specified value.  Most subclasses will have no need to
 * override this method, relying solely on the {@link #initialValue}
 * method to set the values of thread-locals.
 *
 * @param value the value to be stored in the current thread's copy of
 *        this thread-local.
 */
public void set(T value) {
    Thread t = Thread.currentThread();
    ThreadLocalMap map = getMap(t);
    if (map != null)
        map.set(this, value);
    else
        createMap(t, value);
}

map.set(this, value); 可以看到,我们把要存储的值放到了 key 为当前 ThreadLocal 对象的 ThreadLocalMap 中去了。取值的时候也是从这个 map 中取,所以问题的关键就在于 ThreadLocalMap 的实现了。

ThreadLocalMap 的实现

跟 HashMap 类似,也是用数组来实现的

private Entry[] table; 

然而这里的Entry 是 WeakReference 的子类

/**
 * The entries in this hash map extend WeakReference, using
 * its main ref field as the key (which is always a
 * ThreadLocal object).  Note that null keys (i.e. entry.get()
 * == null) mean that the key is no longer referenced, so the
 * entry can be expunged from table.  Such entries are referred to
 * as "stale entries" in the code that follows.
 */
static class Entry extends WeakReference<ThreadLocal<?>> {
    /** The value associated with this ThreadLocal. */
    Object value;
Entry(ThreadLocal&lt;?&gt; k, Object v) {
    super(k);
    value = v;
}

}

由于弱引用的特性,当 ThreadLocal 对象不可达的时候,ThreadLocalMap 的 key 就会被 GC 回收掉。试想,如果这里不是弱引用,而是强引用,那么 ThreadLocal 对象将永远不会被回收,除非线程终止。因为 Thread 持有 threadLocals,threadLocals 的 Entry 因为不是弱引用,就会持有 threadLocal 对象的强引用,如果不显式调用 ThreadLocal 的 remove 去掉这里的强引用,线程生命周期内,threadLocal 就不会被回收。当线程结束后,Thread 的 exit() 方法会执行 threadLocals = null 使得线程内所有的 ThreadLocal 对象以及其上面带有的 value 不可达,导致被回收。不过 exit 方法的注释上说,这里只是为了加速 资源的释放,即便线程执行 exit 的时候不释放,线程本身最终也会不可达,所有线程相关的资源最终还是会被回收。

我再画一幅图解释一下:(人类的本质是复读机!)

Thread t // 某一个线程
   ↓
ThreadLocal.ThreadLocalMap t.threadLocals // 线程持有的 Map 对象
   ↓
Entry table[i] // Map 持有的某一个 Entry 对象
  1. 假设 Entry 持有 key 和 value 的强引用,那么如果 ThreadLocalMap 不自己清理,key 和 value 就会伴随整个 Thread 的生命周期。

  2. 假设 Entry 是 key 的弱引用,那么 key 不可达时(也就是 threadLocal 不可达时),key 会被 gc,value 仍然伴随 Thread 的生命周期。

那么 ThreadLocal 对象在什么时候才会不可达呢?最简单的情况是,离开了函数调用栈空间了,我们来看下面这个例子

public static void test() {
    ThreadLocal<String> t = new ThreadLocal<>();
    t.set("abc");
}
public static void main(String[] args) {
    new Thread(() -> {
        test();
        // 1
        System.gc();
        // 2
    }).start();
}

在线程执行完 test() 方法后,执行 System.gc() 之前,也就是上述代码注释 1 的位置,当前线程的 threadLocals 对象如下:

可以看见 ThreadLocalMap 的 Entry 的 referent 和 value 都还在,当执行 System.gc() 后,我们看一下有什么变化:

此时由于 threadLocal 对象已经不可达,所以会被 gc 回收。然而,value 对象还没回收呢

怎样才能让 value 对象也可以回收呢?上面已经说过很多次了,value 对象被回收当且仅当:

  1. ThreadLocaMap 自己清理
  2. Thread 对象被回收

下面我们来讲解 ThreadLocalMap 什么情况下才会自己清理 key 为 null 的 Entry

在 ThreadLocalMap 类中 ,真正可以回收 value (以及 key) 的方法是 expungeStaleEntry(int staleSlot) 方法:

private int expungeStaleEntry(int staleSlot) {
    Entry[] tab = table;
    int len = tab.length;
// expunge entry at staleSlot
tab[staleSlot].value = null;
tab[staleSlot] = null;
size--;

// Rehash until we encounter null
...

}

这个方法的实现是比较复杂的,不仅直接删除指定 index 的元素,并且在 rehash 的过程中也会清理一些其它的元素。

我们通过 IDE 分析调用链可以知道,只有在 ThreadLocal 的 get 、set、remove 方法被调用时,才有可能会进行清理。

注意事项

我们使用 ThreadLocal 最常见的场景是把 ThreadLocal 作为一个类的静态字段(即便不是静态字段,在 IOC 环境下,也可能是个全局的单例对象)多个线程共用同一个 ThreadLocal 对象。(也就是使用同一个 ThreadLocal 对象作为 key 放到各自线程 ThreadLocalMap 里)。

在这种场景下,ThreadLocal 对象的生命周期与承载它的对象的生命周期相同,在大多数 Web 场景下,这个 ThreadLocal 对象几乎在整个应用的生命周期中都是可达的。所以每个线程各自的 ThreadLocalMap 的 key 并不会因为使用了弱引用而被 GC 回收掉。我们只能够在每个线程中手动调用 ThreadLocal 的 remove 方法对 key 和 value 进行置 null,使得 GC 可以清理掉线程持有的 value(GC 清理不了 key,因为 key 总是可达)。如果不手动调用 remove,那么只有在线程被清理的时候,value 才会被清理(这里说了很多遍了,看不懂请重读上文)。

同时,在 web 场景下,大多数 http server 会使用到线程池,如果在上一次请求中没有主动调用 remove 进行清理,线程池为下一次请求分配的可能是同一个线程,那么调用 ThreadLocal 的 get 方法拿到的就是上一次线程存储的值,这可能会导致错误的业务逻辑。

因此,我们在使用 ThreadLocal 时,应该总是在当前线程结束前手动调用 remove 方法来清理这个线程的 ThreadLocalMap,否则,是有可能内存泄漏的(线程池中的每个线程的 threadLocals 都持有一个相同的 key 的 Entry,以及一个无用的 value)。

InnoDB存储引擎之 —— 锁(一)


SQL Server

2005 之前是页锁,页锁容易实现,并发写入性能比 MyISAM 要好。但是对于热点数据更新还是无能为力。

2005 之后是乐观并发悲观并发,乐观并发下支持行级锁,但与 InnoDB 的实现方式完全不同。在 SQL Server 下,锁是一种稀缺资源,锁越多开销越大,因此会导致锁升级,行锁会升级到表锁。

MyISAM

MyISAM 引擎是表锁设计,并发读性能没问题,并发写性能有问题,若插入在“底部”,还能有一定的并发写入性能。

InnoDB

InnoDB 锁的实现与 Oracle 比较像,提供一致性非锁定读行级锁,行级锁没有额外开销,支持并发性和一致性。

InnoDB 锁的类型

  1. 共享锁(S Lock)
    允许事务读一行数据
  2. 排它锁(X Lock)
    允许事务删除或更改一条数据
  3. 意向共享锁(IS Lock)
    事务想要获取一张表中某几行的共享锁
  4. 意向排它锁(IX Lock)
    事务想要获取一张表中某几行的排它锁
  5. 自增锁


例如,如果一个表上已经有了S表锁,那么尝试修改该表的几行记录,是不可以的,因为IX锁与S锁是不兼容的。

几张查看锁和事务的表

  1. INNODB_TRX
    可以查看事务的状态
  2. INNODB_LOCKS
    可以查看哪些表哪些记录被加了哪些锁。
  3. INNODB_LOCK_WAITS
    已经有了前面两张表,判断事务的等待情况,可以很清楚的看到一个事务被哪个事务和锁阻塞

一致性非锁定读

InnoDB 存储引擎通过多版本控制(multi versioning)的方式来读取当前执行时间数据库中行的数据。如果读取的行正在执行 DELETE 或 UPDATE 操作,这时读取操作不会因此去等待行上锁的释放。而是去读取行的一个快照数据,如图所示:

快照数据是指该行的之前版本的数据,该实现是通过 undo 段来完成。而 undo 用来在事务中回滚数据,因此快照数据本身是没有额外的开销。此外,读取快照数据是不需要上锁的,因为没有事务需要对历史的数据进行修改操作。

快照数据其实就是当前行数据之前的历史版本,每行记录可能有多个版本。一个行记录可能有不止一个快照数据,一般称这种技术为行多版本技术。由此带来的并发控制,称之为多版本并发控制(Multi Version Concurrency Control, MVCC)

非锁定读机制极大地提高了数据库的并发性。在事务隔离级别 READ COMMITTED 和 REPEATABLE READ (INNODB 存储引擎的默认事务隔离级别)下,INNODB 存储引擎使用非锁定的一致性读。然而,对于快照数据的定义却不相同。对于 READ COMMITTED 的事务隔离级别,它总是读取行的最新版本,如果行被锁定了,则读取该行版本的最新一个快照(也就是当前事务自己建立的那个快照)。而对于 REPEATABLE READ 的事务隔离级别,总是读取事务开始时的行数据(这里应该也包含自己建立的快照数据)。

一致性锁定读

如下两种语句必须在事务中使用,当事务提交了,锁也就释放了。

  • SELECT … FOR UPDATE
    对读取的行记录加一个 X 锁,其他事务不能对已锁定的行加上任何锁。
    即使读取的行已被执行了 SELECT… FOR UPDATE,还是可以进行一致性非锁定读的。
  • SELECT … LOCK IN SHARE MODE
    对读取的行记录加一个 S 锁,其他事务可以向被锁定的行加 S 锁,但是如果加 X 锁,则会被阻塞。

自增锁(2种实现方式)

AUTO- INC Locking(特殊的表锁)

在 INNODB 存储引擎的内存结构中,对每个含有自增长值的表都有一个自增长计数器(auto-increment counter)。当对含有自增长的计数器的表进行插入操作时,这个计数器会被初始化,执行如下的语句来得到计数器的值

SELECT MAX (auto inc col) FROM t FOR UPDATE:

每张表的自増长值并不保存在磁盘上进行持久化,而是在每次 INNODB 存储引檠启动时初始化。
—— 来自另一本硬核源码书

插人操作会依据这个自增长的计数器值加 1 赋予自增长列。这种锁其实是采用一种特殊的表锁机制,为了提高插入的性能,锁不是在一个事务完成后オ释放,而是在完成对自增长值插入的 SQL 语句后立即释放。但对于有自增长值的列的并发插人性能较差,事务必须等待前一个插入的完成(虽然不用等待事务的完成)。

互斥量

从 MYSQL5.1.22 版本开始,INNODB 存储引擎中提供了一种轻量级互斥量的自增长实现机制,这种机制大大提高了自增长值插入的性能。并且从该版本开始,INNODB 存储引擎提供了一个参数 innodb_autoinc_lock_mode 来控制自增长的模式,该参数的默认值为 1

三种插入类型

innodb_autoinc_lock_mode 说明

需要注意 InnoDB 存储引擎中自增长的实现和 MYISAM 不同。MYISAM 存储引擎是表锁设计,自增长不用考虑并发插人的问题。另外,在 INNODB 存储引擎中,自增长值的列必须是索引,同时必须是索引的第一个列。如果不是第一个列,则 MYSQL 数据库会抛出异常,而 MYISAM 存储引擎没有这问题。

外键与锁

外键主要用于引用完整性的约束检査。在 INNODB 存储引擎中,对于一个外键列,如果没有显式地对这个列加索引,INNODB 存储引擎自动对其加一个索引,因为这样可以避免表锁,Oracle 数据库不会自动添加索引,用户必须自己手动添加,这也导致了 Oracle 数据库中可能产生死锁。

对于外键值的插入或更新,首先需要査询父表中的记录,即 SELECT 父表。但是对于父表的 SELECT 操作,不是使用一致性非锁定读的方式,因为这样会发生数据不一致的问题,因此这时使用的是 SELECT… LOCK IN SHARE MODE 方式,即主动对父表加个 S 锁。如果这时父表上已经加了 X 锁,子表上的操作会被阻塞。

寻找旋转排序数组中的最小值


原题链接

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如,数组[0,1,2,4,5,6,7] 可能变为[4,5,6,7,0,1,2] 。

请找出其中最小的元素。

分析

这里只给出可以无脑使用二分模板的方法:
把这个旋转数组去掉最后一个元素(target)后,剩余的部分仍然是一个旋转数组(arr’)
原命题等价为:寻找 arr’ 中第一个小于 target 的元素

实现

这里直接使用二分模板

class Solution {
    static int search(int l, int r, Predicate<Integer> f) {
        while (l < r) {
            int m = l + (r - l) / 2;
            if (f.test(m)) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l; // 此时 l 等于 r,并且 f(l) 是第一个等于 true 的点
    }
<span class="kd">static</span> <span class="kt">int</span> <span class="nf">findMin</span><span class="o">(</span><span class="kt">int</span><span class="o">[]</span> <span class="n">array</span><span class="o">)</span> <span class="o">{</span>
    <span class="kt">int</span> <span class="n">l</span> <span class="o">=</span> <span class="mi">0</span><span class="o">,</span> <span class="n">r</span> <span class="o">=</span> <span class="n">array</span><span class="o">.</span><span class="na">length</span> <span class="o">-</span> <span class="mi">1</span><span class="o">;</span>
    <span class="c1">// 第一个小于等于最右端的点的元素位置,即最小值</span>
    <span class="kt">int</span> <span class="n">index</span> <span class="o">=</span> <span class="n">search</span><span class="o">(</span><span class="n">l</span><span class="o">,</span> <span class="n">r</span><span class="o">,</span> <span class="n">m</span> <span class="o">-&gt;</span> <span class="n">array</span><span class="o">[</span><span class="n">m</span><span class="o">]</span> <span class="o">&lt;=</span> <span class="n">array</span><span class="o">[</span><span class="n">r</span><span class="o">]);</span>
    <span class="k">return</span> <span class="n">array</span><span class="o">[</span><span class="n">index</span><span class="o">];</span>
<span class="o">}</span>

}

我自己的一开始写的分类讨论的版本,看起来还是比较乱的

class Solution {
    public int findMin(int[] nums) {
        int i = 0;
        int j = nums.length - 1;
        // 如果是升序的
        if (nums[i] <= nums[j]) return nums[i];
        while (true) {
            if (i == j || i == j - 1) return nums[j];
            int mid = (i + j) / 2;
            int n = nums[mid], l = nums[i], r = nums[j];
            if (n > l) { // n 在上方
                if (nums[mid+1] > nums[mid]) {
                    i = mid + 1;
                } else {
                    return nums[mid + 1];
                }
            } else { // n 在下方
                if (nums[mid] > nums[mid - 1]) {
                    j = mid - 1;
                } else {
                    return nums[mid];
                }
            }
        }
    }
}

「细谈」Java 中的弱引用(WeakReference)


本文只讲弱引用,文章中的内容均来自本人的实践的总结,某些观点不常见于其它文章。
该文是理解 ThreadLocal 的基础。

弱引用(Weak Reference)

WeakReference<T> weakRef = new WeakReference<>(referent);

当发生 gc 时, 如果 referent 对象满足下述条件则一定会被回收:

  1. referent 没有强引用
  2. referent 没有软引用

几种典型场景

  • 最简单的例子
    WeakReference<List> arrRef = new WeakReference<>(Arrays.asList(1,2,3));
    System.out.println(arrRef.get()); // [1, 2, 3]
    System.gc();
    System.out.println(arrRef.get()); // null
    
  • 有强引用无法回收
    List<Integer> arr = Arrays.asList(1,2,3);
    WeakReference<List> arrRef = new WeakReference<>(arr);
    System.out.println(arrRef.get()); // [1, 2, 3]
    System.gc();
    System.out.println(arrRef.get()); // [1, 2, 3] 还有 arr 强引用,无法回收
    arr = null;
    System.gc();
    System.out.println(arrRef.get()); // null
    
  • final 的东西无法回收
    WeakReference<String> strRef1 = new WeakReference<>(new String("abc"));
    System.gc();
    System.out.println(strRef1.get()); // null
    WeakReference<String> strRef2 = new WeakReference<>("abc");
    System.gc();
    System.out.println(strRef2.get()); // abc
    
  • WeakReference 数组内的元素会被回收(弱引用数组的每个 item 都是弱引用)
    WeakReference<String> a = new WeakReference<>(new String("aaa"));
    WeakReference<String> b = new WeakReference<>(new String("bbb"));
    WeakReference[] tab = new WeakReference[] {a, b};
    System.out.println(a.get()); // aaa
    System.out.println(b.get()); // bbb
    System.gc();
    System.out.println(a.get()); // null
    System.out.println(b.get()); // null
    

ReferenceQueue

用来监视被引用的对象是否已经被回收了。下面我们用 referenceQueue 来探究一下 WeakReference 的回收。

(为求代码清晰,下面的代码一律不捕获 InterruptedException

首先创建一个 referenceQueue, 在另一个线程中调用 remove,该调用是阻塞调用,如果有引用被回收,那么会调用成功,返回该该引用的 this。
最简单的例子:

ReferenceQueue<String> referenceQueue = new ReferenceQueue<>();
// 监视线程
new Thread(() -> {
    Reference remove = referenceQueue.remove();
    System.out.println("remove:" + remove);
}).start();
WeakReference<String> ref = new WeakReference<>(new String("111"), referenceQueue);
System.gc(); // remove:java.lang.ref.WeakReference@322b4b46

特殊情况

  1. 下例说明,不把 new 出来的 WeakReference 赋值给任何变量,那么可能虚拟机可能当场就回收了,因为 referenceQueue 并没有捕获到回收消息。
    1
    ReferenceQueue<String> referenceQueue = new ReferenceQueue<>();
    // 监视线程
    new Thread(() -> {
        Reference remove = referenceQueue.remove();
        System.out.println("remove:" + remove);
    }).start();
    new WeakReference<>(new String("111"), referenceQueue);
    System.gc(); // 什么都不打印
    
  2. 下例说明,显式调用 System.gc() 的线程,如果没有在该线程的任何地方使用到这个 ref,那么并不会触发 ref 的回收。想要 ref 能够被回收,那么需要在 gc 线程的任意一个位置出现 ref。
    ReferenceQueue<String> referenceQueue = new ReferenceQueue<>();
    // 监视线程
    new Thread(() -> {
        Reference remove = referenceQueue.remove(); // 不会捕获到引用的回收
        System.out.println("remove:" + remove);
    }).start();
    WeakReference<String> ref = new WeakReference<>(new String("111"), referenceQueue);
    // gc 线程
    new Thread(() -> {
        // Object a = ref; // 取消注释,则可以捕获到回收
        Thread.sleep(1000);
        System.out.println("gc");
        System.gc(); // 在另一个线程 System.gc()
    }).start();
    

搜索旋转排序数组 II


原题链接

题目描述

上一题的基础上,允许重复元素的出现,只需要判断是否存在某个元素。

分析

先把这道题转化成 30 题,这样当我们求出 mid 之后,是可以判断 mid 所处的位置的。

实现

class Solution {
    public boolean search(int[] nums, int target) {
        return search(nums, target, 0, nums.length - 1);
    }
<span class="kd">public</span> <span class="kt">boolean</span> <span class="nf">search</span><span class="o">(</span><span class="kt">int</span><span class="o">[]</span> <span class="n">nums</span><span class="o">,</span> <span class="kt">int</span> <span class="n">target</span><span class="o">,</span> <span class="kt">int</span> <span class="n">i</span><span class="o">,</span> <span class="kt">int</span> <span class="n">j</span><span class="o">)</span> <span class="o">{</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">i</span> <span class="o">&gt;</span> <span class="n">j</span><span class="o">)</span> <span class="k">return</span> <span class="kc">false</span><span class="o">;</span>
    <span class="kt">int</span> <span class="n">l</span> <span class="o">=</span> <span class="n">nums</span><span class="o">[</span><span class="n">i</span><span class="o">],</span> <span class="n">r</span> <span class="o">=</span> <span class="n">nums</span><span class="o">[</span><span class="n">j</span><span class="o">];</span>
    <span class="k">while</span> <span class="o">(</span><span class="n">l</span> <span class="o">==</span> <span class="n">r</span> <span class="o">&amp;&amp;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">j</span><span class="o">)</span> <span class="o">{</span>
        <span class="n">i</span> <span class="o">+=</span> <span class="mi">1</span><span class="o">;</span>
        <span class="n">l</span> <span class="o">=</span> <span class="n">nums</span><span class="o">[</span><span class="n">i</span><span class="o">];</span>
    <span class="o">}</span>
    <span class="c1">// 此时要么 l != r 了,要么 i == j 了</span>
    <span class="c1">// 这个时候就是 33 题了</span>
    <span class="kt">int</span> <span class="n">idx</span> <span class="o">=</span> <span class="o">(</span><span class="n">i</span> <span class="o">+</span> <span class="n">j</span><span class="o">)</span> <span class="o">/</span> <span class="mi">2</span><span class="o">;</span>
    <span class="kt">int</span> <span class="n">n</span> <span class="o">=</span> <span class="n">nums</span><span class="o">[</span><span class="n">idx</span><span class="o">];</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">target</span> <span class="o">==</span> <span class="n">n</span><span class="o">)</span> <span class="k">return</span> <span class="kc">true</span><span class="o">;</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">target</span> <span class="o">==</span> <span class="n">l</span><span class="o">)</span> <span class="k">return</span> <span class="kc">true</span><span class="o">;</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">target</span> <span class="o">==</span> <span class="n">r</span><span class="o">)</span> <span class="k">return</span> <span class="kc">true</span><span class="o">;</span>
    <span class="c1">// 因为此时 n 的位置已经可以确定了,所以先讨论 n 的位置</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">n</span> <span class="o">&gt;</span> <span class="n">r</span><span class="o">)</span> <span class="o">{</span> <span class="c1">// 如果 n 在上</span>
        <span class="k">if</span> <span class="o">(</span><span class="n">l</span> <span class="o">&lt;</span> <span class="n">target</span> <span class="o">&amp;&amp;</span> <span class="n">target</span> <span class="o">&lt;</span> <span class="n">n</span><span class="o">)</span> <span class="o">{</span>
            <span class="k">return</span> <span class="nf">search</span><span class="o">(</span><span class="n">nums</span><span class="o">,</span> <span class="n">target</span><span class="o">,</span> <span class="n">i</span> <span class="o">+</span> <span class="mi">1</span><span class="o">,</span> <span class="n">idx</span> <span class="o">-</span> <span class="mi">1</span><span class="o">);</span>
        <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
            <span class="k">return</span> <span class="nf">search</span><span class="o">(</span><span class="n">nums</span><span class="o">,</span> <span class="n">target</span><span class="o">,</span> <span class="n">idx</span> <span class="o">+</span> <span class="mi">1</span><span class="o">,</span> <span class="n">j</span> <span class="o">-</span> <span class="mi">1</span><span class="o">);</span>
        <span class="o">}</span>
    <span class="o">}</span> <span class="k">else</span> <span class="o">{</span> <span class="c1">// 如果 n 在下</span>
        <span class="k">if</span> <span class="o">(</span><span class="n">n</span> <span class="o">&lt;</span> <span class="n">target</span> <span class="o">&amp;&amp;</span> <span class="n">target</span> <span class="o">&lt;</span> <span class="n">r</span><span class="o">)</span> <span class="o">{</span> <span class="c1">// t 在下</span>
            <span class="k">return</span> <span class="nf">search</span><span class="o">(</span><span class="n">nums</span><span class="o">,</span> <span class="n">target</span><span class="o">,</span> <span class="n">idx</span> <span class="o">+</span> <span class="mi">1</span><span class="o">,</span> <span class="n">j</span> <span class="o">-</span> <span class="mi">1</span><span class="o">);</span>
        <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
            <span class="k">return</span> <span class="nf">search</span><span class="o">(</span><span class="n">nums</span><span class="o">,</span> <span class="n">target</span><span class="o">,</span> <span class="n">i</span> <span class="o">+</span> <span class="mi">1</span><span class="o">,</span> <span class="n">idx</span> <span class="o">-</span> <span class="mi">1</span><span class="o">);</span>
        <span class="o">}</span>
    <span class="o">}</span>
<span class="o">}</span>

}

Abstract Factory


定义

提供一个接口,用来创建相关或依赖对象的家族,而无需指定它们具体的类。

实践

抽象工厂模式其实就是对工厂方法模式的升级版。工厂方法模式的那个工厂接口或者抽象类里面只包含一个工厂方法。而抽象工厂方法的工厂接口或者抽象类里,包含有多个工厂方法,可以返回不同类型的产品。这里我们来举一个例子,首先定义一个水果抽象工厂:

public interface FruitFactory {
Apple getApple();

Pear getPear();

}

可以看到,这个抽象工厂里面有两个工厂方法,返回的是不同种类的产品,但是这两种产品具有相关性(都是水果)。然后我们实现这个接口,跟工厂方法模式的想法一样,为的是在子类中实例化产品

public class Factory1 implements FruitFactory {
    @Override
    public Apple getApple() {
        return new Apple1();
    }
@Override
public Pear getPear() {
    return new Pear1();
}

}
public class Factory2 implements FruitFactory {
@Override
public Apple getApple() {
return new Apple2();
}

@Override
public Pear getPear() {
    return new Pear2();
}

}

Factory1和Factory2分别返回的是不同的Apple和Pear。这基本上就是抽象工厂模式了。

当需要增加一类产品比如Banana时:

  1. 新增加Banana接口和产品类,这是正常的也是必须的。
  2. 在FruitFactory接口里增加一个getBanana的方法。
  3. 在Factory1和Factory2中实现getBanana方法。

可以看到,当我们增加一类产品,需要修改三个文件,这不符合对修改封闭的原则。那抽象工厂方法的优点是什么呢?就是我们只要一开始指定具体使用哪一个工厂,后面的代码将与具体产品解耦,都是面向接口的。

改进

我们可以使用带反射的简单工厂模式来改进抽象工厂模式。

public class FruitFactory {
private static final String prefix = "me.ysmull.factory.abstractFactory3.product.";

public Apple getApple(String className) {
    try {
        Class clazz = Class.forName(prefix + className);
        return (Apple) clazz.newInstance();
    } catch (ClassNotFoundException | InstantiationException | IllegalAccessException e) {
        e.printStackTrace();
        return null;
    }
}

public Pear getPear(String className) {
    try {
        Class clazz = Class.forName(prefix + className);
        return (Pear) clazz.newInstance();
    } catch (ClassNotFoundException | InstantiationException | IllegalAccessException e) {
        e.printStackTrace();
        return null;
    }
}

}

可以看到,每一个工厂方法都是一个使用反射的简单工厂。这样当我们需要新增加一类产品的时候,除去新建的类与接口外,我们只需要在FruitFactory里增加一个加单工厂即可。如果只是增加某一类产品的新品种,那么不需要有代码上的修改。

Minimum Window Substring


原题链接

题目

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
S = “ADOBECODEBANC”
T = “ABC”

解法

这道题目,我一开始用动态规划做,感觉有点难哦,只能看答案。
讨论区有个人给了一个解决一类字符串问题的模板:

For most substring problem, we are given a string and need to find a substring of it which satisfy some restrictions. A general way is to use a hashmap assisted with two pointers. The template is given below.

int findSubstring(string s) {
    vector<int> map(128,0);
    int counter; // check whether the substring is valid
    int begin=0, end=0; //two pointers, one point to tail and one  head
    int d; //the length of substring

    for() { /* initialize the hash map here */ }

    while(end<s.size()){

        if(map[s[end++]]-- ?){  /* modify counter here */ }

        while(/* counter condition */){

             /* update d here if finding minimum*/

            //increase begin to make it invalid/valid again

            if(map[s[begin++]]++ ?){ /*modify counter here*/ }
        }  

        /* update d here if finding maximum*/
    }
    return d;
}

这个模板暗示的算法是,维护两个指针start和end分别指向子串的起始位置和结束位置,end向后遍历,当满足子串的性质之后,
向后移动start破坏该性质并寻找下一个满足性质的位置。

用这个**可以解决Longest Substring Without Repeating Characters

代码

string minWindow(string s, string t) {
  int ascii[256];
  memset(ascii, 0, 256 * sizeof(int));
  int count = 0;
  for (int i = 0; i < t.length(); i++) {
      ascii[t[i]]++;
      count++;
  }

int start = 0, end = 0;
int minLen = 999999, minStart = 0;
while (end < s.length()) {
if (ascii[s[end]]-- > 0) {
count--;
}
while (count == 0) {
if (end - start + 1 < minLen) {
minStart = start;
minLen = end - start + 1;
}
if (++ascii[s[start++]] > 0) {
count++;
}
// if (start > end) break;
}
end++;
}
if (minLen == 999999 ) return "";
return s.substr(minStart, minLen);
}

搜索二维矩阵


原题链接

题目描述

编写一个高效的算法来判断m x n矩阵中,是否存在一个目标值。该矩阵具有如下特性:

  1. 每行中的整数从左到右按升序排列。
  2. 每行的第一个整数大于前一行的最后一个整数。

分析

先对第一列进行二分搜索,确定 target 在哪一行,再对那一行进行二分搜索。

对列搜索的时候,注意 f(m) 应该取 arr[m] > target。
如果 f(m) = arr[m] >= target,需要对 l 进行大量讨论,导致代码变得非常复杂。

实现

class Solution {
<span class="kd">public</span> <span class="kd">static</span> <span class="kt">boolean</span> <span class="nf">searchMatrix</span><span class="o">(</span><span class="kt">int</span><span class="o">[][]</span> <span class="n">matrix</span><span class="o">,</span> <span class="kt">int</span> <span class="n">target</span><span class="o">)</span> <span class="o">{</span>
    <span class="kt">int</span> <span class="n">m</span> <span class="o">=</span> <span class="n">matrix</span><span class="o">.</span><span class="na">length</span><span class="o">,</span> <span class="n">n</span> <span class="o">=</span> <span class="n">matrix</span><span class="o">[</span><span class="mi">0</span><span class="o">].</span><span class="na">length</span><span class="o">;</span>
    <span class="c1">// 先搜索是哪一行</span>
    <span class="kt">int</span> <span class="n">l</span> <span class="o">=</span> <span class="mi">0</span><span class="o">,</span> <span class="n">r</span> <span class="o">=</span> <span class="n">m</span><span class="o">;</span>
    <span class="k">while</span> <span class="o">(</span><span class="n">l</span> <span class="o">&lt;</span> <span class="n">r</span><span class="o">)</span> <span class="o">{</span>
        <span class="kt">int</span> <span class="n">mid</span> <span class="o">=</span> <span class="n">l</span> <span class="o">+</span> <span class="o">(</span><span class="n">r</span> <span class="o">-</span> <span class="n">l</span><span class="o">)</span> <span class="o">/</span> <span class="mi">2</span><span class="o">;</span>
        <span class="k">if</span> <span class="o">(</span><span class="n">matrix</span><span class="o">[</span><span class="n">mid</span><span class="o">][</span><span class="mi">0</span><span class="o">]</span> <span class="o">&gt;</span> <span class="n">target</span><span class="o">)</span> <span class="o">{</span>
            <span class="n">r</span> <span class="o">=</span> <span class="n">mid</span><span class="o">;</span>
        <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
            <span class="n">l</span> <span class="o">=</span> <span class="n">mid</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span>
        <span class="o">}</span>
    <span class="o">}</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">l</span> <span class="o">==</span> <span class="mi">0</span><span class="o">)</span> <span class="k">return</span> <span class="kc">false</span><span class="o">;</span>

    <span class="c1">// 否则可以确定行数,答案只可能在 l-1 行</span>
    <span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">,</span> <span class="n">j</span> <span class="o">=</span> <span class="n">n</span><span class="o">;</span>
    <span class="k">while</span> <span class="o">(</span><span class="n">i</span> <span class="o">&lt;</span> <span class="n">j</span><span class="o">)</span> <span class="o">{</span>
        <span class="kt">int</span> <span class="n">mid</span> <span class="o">=</span> <span class="n">i</span> <span class="o">+</span> <span class="o">(</span><span class="n">j</span> <span class="o">-</span> <span class="n">i</span><span class="o">)</span> <span class="o">/</span> <span class="mi">2</span><span class="o">;</span>
        <span class="k">if</span> <span class="o">(</span><span class="n">matrix</span><span class="o">[</span><span class="n">l</span> <span class="o">-</span> <span class="mi">1</span><span class="o">][</span><span class="n">mid</span><span class="o">]</span> <span class="o">&gt;=</span> <span class="n">target</span><span class="o">)</span> <span class="o">{</span>
            <span class="n">j</span> <span class="o">=</span> <span class="n">mid</span><span class="o">;</span>
        <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
            <span class="n">i</span> <span class="o">=</span> <span class="n">mid</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span>
        <span class="o">}</span>
    <span class="o">}</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">i</span> <span class="o">==</span> <span class="n">n</span> <span class="o">||</span> <span class="n">matrix</span><span class="o">[</span><span class="n">l</span> <span class="o">-</span> <span class="mi">1</span><span class="o">][</span><span class="n">i</span><span class="o">]</span> <span class="o">!=</span> <span class="n">target</span><span class="o">)</span> <span class="k">return</span> <span class="kc">false</span><span class="o">;</span>
    <span class="k">return</span> <span class="kc">true</span><span class="o">;</span>
<span class="o">}</span>

}

排序序列


原题链接

题目描述

给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列,返回第 k 大的排列。

方法

用第 31 的解法就行了。

impl Solution {
    pub fn get_permutation(n: i32, k: i32) -> String {
        let mut str_vec: Vec<i32> = (1..=n).collect();
        for i in 0..k-1 {
            Solution::next_permutation(&mut str_vec);
        }
        let a: Vec<String> = str_vec.iter().map(|item| item.to_string()).collect();
        return a.join("");
    }
<span class="k">pub</span> <span class="k">fn</span> <span class="nf">next_permutation</span><span class="p">(</span><span class="n">nums</span><span class="p">:</span> <span class="o">&amp;</span><span class="k">mut</span> <span class="nb">Vec</span><span class="o">&lt;</span><span class="nb">i32</span><span class="o">&gt;</span><span class="p">)</span> <span class="p">{</span>
    <span class="c">// 从右向左找第一个升序对[i,i+1]</span>
    <span class="k">if</span> <span class="k">let</span> <span class="nf">Some</span><span class="p">(</span><span class="n">i</span><span class="p">)</span> <span class="o">=</span> <span class="n">nums</span><span class="p">[</span><span class="o">..</span><span class="n">nums</span><span class="nf">.len</span><span class="p">()</span> <span class="o">-</span> <span class="mi">1</span><span class="p">]</span><span class="nf">.iter</span><span class="p">()</span><span class="nf">.enumerate</span><span class="p">()</span>
        <span class="nf">.rposition</span><span class="p">(|(</span><span class="n">pos</span><span class="p">,</span> <span class="mi">_</span><span class="p">)|</span> <span class="n">nums</span><span class="p">[</span><span class="n">pos</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">nums</span><span class="p">[</span><span class="n">pos</span> <span class="o">+</span> <span class="mi">1</span><span class="p">])</span> <span class="p">{</span>
        <span class="c">// 从右向左找第一个比 nums[i] 大的数 nums[x]</span>
        <span class="k">if</span> <span class="k">let</span> <span class="nf">Some</span><span class="p">(</span><span class="n">x</span><span class="p">)</span> <span class="o">=</span> <span class="n">nums</span><span class="p">[(</span><span class="n">i</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span><span class="o">..</span><span class="p">]</span><span class="nf">.iter</span><span class="p">()</span><span class="nf">.rposition</span><span class="p">(|</span><span class="n">item</span><span class="p">|</span> <span class="n">item</span> <span class="o">&gt;</span> <span class="o">&amp;</span><span class="n">nums</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="p">{</span>
            <span class="n">nums</span><span class="nf">.swap</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">i</span> <span class="o">+</span> <span class="mi">1</span> <span class="o">+</span> <span class="n">x</span><span class="p">);</span>
        <span class="p">}</span>
        <span class="o">&amp;</span><span class="n">nums</span><span class="p">[</span><span class="n">i</span> <span class="o">+</span> <span class="mi">1</span><span class="o">..</span><span class="p">]</span><span class="nf">.reverse</span><span class="p">();</span>
    <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
        <span class="n">nums</span><span class="nf">.reverse</span><span class="p">();</span>
    <span class="p">}</span>
<span class="p">}</span>

}

如何加速你的 count 查询


背景

项目中,经常会有一些统计类的查询,大概模式是:

select count(*) from table_name where ...

如何加速此类查询,大部分人首先想到的办法可能就是,「根据 where 条件」给表加索引。
那么如果是整表 count 呢,还有提高速度的办法吗?答案是,有的。

问题

线上有一张 news 表,会有爬虫不断的向该表插入爬取的新闻数据(所以下文中每次count的结果总不相同是因为数据确实增加了)

create table news
(
    id          int auto_increment primary key,
    type        varchar(20) default ''                not null comment '新闻分类',
    title       text                                  null,
    description text                                  null,
    content     mediumtext                            null,
    pics        json                                  null,
    source      varchar(255)                          null,
    create_time timestamp   default CURRENT_TIMESTAMP null
) collate = utf8mb4_unicode_ci;

直接执行

mysql> select count(*) from news;
+----------+
| count(*) |
+----------+
|   678532 |
+----------+
1 row in set (1 min 3.57 sec)

mysql> select count() from news;
+----------+
| count(
) |
+----------+
| 678538 |
+----------+
1 row in set (50.18 sec)

可以看到,执行该 SQL 非常的耗时,我们查看一下执行计划:

mysql> explain select count(*) from news G;
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: news
   partitions: NULL
         type: index
possible_keys: NULL
          key: PRIMARY
      key_len: 4
          ref: NULL
         rows: 440632
     filtered: 100.00
        Extra: Using index
1 row in set, 1 warning (0.00 sec)

执行计划说,该查询使用了主键索引,由于是主键索引,该查询自然而然的也是覆盖索引,并且 filtered 也是 100.00。那么如何对这句SQL进行加速呢?

解决

由于 count(*) 类型的查询不需要去任何一列的数据,主键索引(clustered index)的叶子节点存储了完整的行数据(上例中甚至还有很多的 blob 类字段,数据页都存储不下了),遍历主键索引会带来较大的磁盘 IO,所以解决办法就呼之欲出了———随便找个列,建一个小巧的辅助索引。

我们选择 source 列来建索引。

create index news_source_index on news (source);

索引建好后,我们查看执行计划:

mysql> explain select count(*) from news G;
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: news
   partitions: NULL
         type: index
possible_keys: NULL
          key: news_source_index
      key_len: 1023
          ref: NULL
         rows: 440697
     filtered: 100.00
        Extra: Using index
1 row in set, 1 warning (0.02 sec)

根据 Extra 字段,你会发现,该查询仍然是覆盖索引,但是 InnoDB 选择了使用我们刚刚创建的辅助索引,这是因为,辅助索引远小于主键索引,遍历辅助索引的代价较小一些。再一次执行查询:

mysql> select count(*) from news;
+----------+
| count(*) |
+----------+
|   678129 |
+----------+
1 row in set (1.32 sec)

mysql> select count(*) from news;
+----------+
| count(*) |
+----------+
|   678129 |
+----------+
1 row in set (0.09 sec)

连续两次执行该SQL的时间分别从 1 min 3.57 sec50.18 sec 变成了 1.32 sec0.09 sec

延伸

上文讲解的例子是一个没有 where 条件的 SQL,提高 count(*) 速度的方法是随便建一个代价较小的辅助索引。如果是带有查询条件的查询呢?我们是不是一定要建立精准命中查询条件的索引呢?答案是否定的。

对于 count 型查询,我们不一定需要一个完美切合查询条件的索引。

下面用一个例子来说明,首先还是举一个创建精确索引的例子。

还是上面的 news 表,我们想执行一个范围查询:

mysql> select count(*) from news where create_time > curdate();
+----------+
| count(*) |
+----------+
|      996 |
+----------+
1 row in set (1 min 44.76 sec)

该查询用不到任何索引,所以速度非常慢,因此,我们首先想到的是,给 create_time 字段建立索引。

mysql> create index news_create_time_index on news (create_time);
Query OK, 0 rows affected (1 min 16.94 sec)
Records: 0  Duplicates: 0  Warnings: 0

索引建好后,我们查看执行计划,可以用上这个索引,并且查询时间已经可以忽略不计了:

mysql> explain select count(*) from news where create_time > curdate() G;
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: news
   partitions: NULL
         type: range
possible_keys: news_create_time_index
          key: news_create_time_index
      key_len: 5
          ref: NULL
         rows: 1104
     filtered: 100.00
        Extra: Using where; Using index
1 row in set, 1 warning (0.00 sec)

mysql> select count() from news where create_time > curdate();
+----------+
| count(
) |
+----------+
| 1104 |
+----------+
1 row in set (0.01 sec)

(注意下面的转折)

然而,假设如果这张表已经有了包含 create_time 的联合索引,并且 create_time 不是联合索引的第一列,那么 InnoDB 可否使用那个联合索引来优化这个查询呢?

比如假设我们已经有了(source, create_time) 的联合索引,仅仅看 where 条件,是对 create_time 进行范围查找,显然是用不上这个联合索引的,因为联合索引只有第一列是有序的,其它列只相对于前一列保持有序。下面我们来实验一下,看看实际情况如何。

首先我们删除已经存在的 create_time 的索引,然后建立一个 (source, create_time) 的联合索引:

mysql> create index news_source_create_time_index on news (source, create_time);
Query OK, 0 rows affected (40.95 sec)
Records: 0  Duplicates: 0  Warnings: 0

mysql> drop index news_create_time_index on news;
Query OK, 0 rows affected (0.02 sec)
Records: 0  Duplicates: 0  Warnings: 0

(吃了个中饭回来)
然后我们看一看这条查询的执行计划:

mysql> explain select count(*) from news where create_time > curdate() G;
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: news
   partitions: NULL
         type: index
possible_keys: news_source_create_time_index
          key: news_source_create_time_index
      key_len: 1028
          ref: NULL
         rows: 441733
     filtered: 33.33
        Extra: Using where; Using index
1 row in set, 1 warning (0.03 sec)

根据执行计划我们发现,对 create_time 的范围查询,竟然可以用到 (source, create_time) 的联合索引,实际执行该查询:

mysql> select count(*) from news where create_time > curdate();
+----------+
| count(*) |
+----------+
|     1173 |
+----------+
1 row in set (0.27 sec)

查询仍然非常的高效,这是为什么呢?

原因在于,尽管 create_time 是无序的,但是对于 count(*) 类型的查询,我们需要使用到的字段其实只有 create_time 而已,而辅助索引 (source, create_time) 的 B+ 树中,已经包含了所有的 create_time 信息,可以「覆盖」我们的查询条件,足够我们对「记录数」进行统计,因此,不需要去遍历巨大的主键索引的 B+ 树。然而,由于 create_time 是无序的,我们仍然需要对所有的索引进行排序之后再筛选出满足条件的记录,所以 Extra 中包含了 Using where,但这比直接在主键索引中进行筛选,已经减少了很多的磁盘IO,所以仍然保持了查询性能。

Builder Pattern


Definition

The intent of the Builder design pattern is to separate the construction of a complex object from its representation. By doing so the same construction process can create different representations.

Participants

  • Product 表示被构造的复杂对象
  • Builder 指定 Product 各个部件的创建过程的接口(或抽象类)
  • ConcreteBuilder 实现Builder
  • Director 使用Builder的实例实际创建一个Product

Description

  1. Builder处理Director的请求。
  2. ClientDirector获取Product
  3. BuilderConcreteBuilder 都不应该有部件的具体业务数据,它们只负责抽象的创建过程。具体的数据只出现在Director
  4. Builder 的组件方法的返回类型设定为Builder类本身可以实现 fluent interface

Practice

Ordinary Version

// Product
@Data // using Lombok
class Car {
    private int wheels;
    private String color;
}
// Builder
interface CarBuilder {
    CarBuilder setWheels(final int wheels);
CarBuilder setColor(final String color);

Car build();

}
class CarBuilderImpl implements CarBuilder {
private Car car;

public CarBuilderImpl() {
    car = new Car();
}

@Override
public CarBuilder setWheels(final int wheels) {
    car.setWheels(wheels);
    return this;
}

@Override
public CarBuilder setColor(final String color) {
    car.setColor(color);
    return this;
}

@Override
public Car build() {
    return car;
}

}

// Director
public class CarBuildDirector {
    private CarBuilder builder;

    public CarBuildDirector(final CarBuilder builder) {
        this.builder = builder;
    }

    public Car construct() {
        return builder.setWheels(4)
                      .setColor("Red")
                      .build();
    }

    public static void main(final String[] arguments) {
        CarBuilder builder = new CarBuilderImpl();
        CarBuildDirector carBuildDirector = new CarBuildDirector(builder);
        System.out.println(carBuildDirector.construct());
    }
}

Generic Version

我们可以使用Java8实现一个泛型的Builder,很强大!

public class GenericBuilder<T> {
private final Supplier&lt;T&gt; instantiator;

private List&lt;Consumer&lt;T&gt;&gt; instanceModifiers = new ArrayList&lt;&gt;();

public GenericBuilder(Supplier&lt;T&gt; instantiator) {
    this.instantiator = instantiator;
}

public static &lt;T&gt; GenericBuilder&lt;T&gt; of(Supplier&lt;T&gt; instantiator) {
    return new GenericBuilder&lt;T&gt;(instantiator);
}

public &lt;U&gt; GenericBuilder&lt;T&gt; with(BiConsumer&lt;T, U&gt; consumer, U value) {
    Consumer&lt;T&gt; c = instance -&gt; consumer.accept(instance, value);
    instanceModifiers.add(c);
    return this;
}

public T build() {
    T value = instantiator.get();
    instanceModifiers.forEach(modifier -&gt; modifier.accept(value));
    instanceModifiers.clear();
    return value;
}

public static void main(String[] args) {
    Car car = GenericBuilder.of(Car::new)
            .with(Car::setColors, "red")
            .with(Car::setWheels, 5)
            .build();
}

}

Reference

  1. wikipedia builder pattern
  2. how-to-implement-the-builder-pattern-in-java-8

组合总和 III


原题链接

题目描述

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。

实现

impl Solution {
    pub fn combination_sum3(k: i32, n: i32) -> Vec<Vec<i32>> {
        let arr = vec![1, 2, 3, 4, 5, 6, 7, 8, 9];
        let mut vis: Vec<_> = arr.iter().map(|i| false).collect();
        let mut result = vec![];
        Solution::combination_sum0(k as usize, n, &arr, &mut vis, &mut vec![], &mut result);
        return result;
    }
<span class="k">fn</span> <span class="nf">combination_sum0</span><span class="p">(</span><span class="n">k</span><span class="p">:</span> <span class="nb">usize</span><span class="p">,</span> <span class="n">target</span><span class="p">:</span> <span class="nb">i32</span><span class="p">,</span> <span class="n">arr</span><span class="p">:</span> <span class="o">&amp;</span><span class="nb">Vec</span><span class="o">&lt;</span><span class="nb">i32</span><span class="o">&gt;</span><span class="p">,</span> <span class="n">vis</span><span class="p">:</span> <span class="o">&amp;</span><span class="k">mut</span> <span class="nb">Vec</span><span class="o">&lt;</span><span class="nb">bool</span><span class="o">&gt;</span><span class="p">,</span> <span class="n">collector</span><span class="p">:</span> <span class="o">&amp;</span><span class="k">mut</span> <span class="nb">Vec</span><span class="o">&lt;</span><span class="nb">i32</span><span class="o">&gt;</span><span class="p">,</span> <span class="n">result</span><span class="p">:</span> <span class="o">&amp;</span><span class="k">mut</span> <span class="nb">Vec</span><span class="o">&lt;</span><span class="nb">Vec</span><span class="o">&lt;</span><span class="nb">i32</span><span class="o">&gt;&gt;</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">if</span> <span class="n">collector</span><span class="nf">.len</span><span class="p">()</span> <span class="o">==</span> <span class="n">k</span> <span class="p">{</span>
        <span class="k">if</span> <span class="n">target</span> <span class="o">==</span> <span class="mi">0</span> <span class="p">{</span>
            <span class="n">result</span><span class="nf">.push</span><span class="p">(</span><span class="n">collector</span><span class="nf">.clone</span><span class="p">());</span>
        <span class="p">}</span>
        <span class="k">return</span><span class="p">;</span>
    <span class="p">}</span>

    <span class="k">for</span> <span class="p">(</span><span class="n">idx</span><span class="p">,</span> <span class="n">item</span><span class="p">)</span> <span class="n">in</span> <span class="n">arr</span><span class="nf">.iter</span><span class="p">()</span><span class="nf">.enumerate</span><span class="p">()</span> <span class="p">{</span>
        <span class="c">// 已经使用过 || 会溢出</span>
        <span class="k">if</span> <span class="n">vis</span><span class="p">[</span><span class="n">idx</span><span class="p">]</span> <span class="p">||</span> <span class="n">target</span> <span class="o">-</span> <span class="n">item</span> <span class="o">&lt;</span> <span class="mi">0</span> <span class="p">{</span>
            <span class="k">continue</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="c">// 保证结果升序</span>
        <span class="k">if</span> <span class="k">let</span> <span class="nf">Some</span><span class="p">(</span><span class="n">last</span><span class="p">)</span> <span class="o">=</span> <span class="n">collector</span><span class="nf">.last</span><span class="p">()</span> <span class="p">{</span>
            <span class="k">if</span> <span class="n">last</span> <span class="o">&gt;</span> <span class="n">item</span> <span class="p">{</span>
                <span class="k">continue</span><span class="p">;</span>
            <span class="p">}</span>
        <span class="p">}</span>
        <span class="n">vis</span><span class="p">[</span><span class="n">idx</span><span class="p">]</span> <span class="o">=</span> <span class="k">true</span><span class="p">;</span>
        <span class="n">collector</span><span class="nf">.push</span><span class="p">(</span><span class="o">*</span><span class="n">item</span><span class="p">);</span>
        <span class="nn">Solution</span><span class="p">::</span><span class="nf">combination_sum0</span><span class="p">(</span><span class="n">k</span><span class="p">,</span> <span class="n">target</span> <span class="o">-</span> <span class="n">item</span><span class="p">,</span> <span class="n">arr</span><span class="p">,</span> <span class="n">vis</span><span class="p">,</span> <span class="n">collector</span><span class="p">,</span> <span class="n">result</span><span class="p">);</span>
        <span class="n">collector</span><span class="nf">.pop</span><span class="p">();</span>
        <span class="n">vis</span><span class="p">[</span><span class="n">idx</span><span class="p">]</span> <span class="o">=</span> <span class="k">false</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">}</span>

}

不重复元素的全排列


原题链接

题目描述

回溯法1(使用 swap)

这个是网上流传的最简洁的版本,但是不是很好理解,这里用到了 swap 方法,直接在原数组中整理数据。

区间 [0, idx) 表示已经排列好了的部分,每一次需要选择 idx 可以放置的元素,直到 idx == len 的时候表示某个排列结束了。

对于 [idx, len) 的任何元素,都可以通过 swap 方法放置到 idx 的位置。

impl Solution {
    pub fn permute(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut result = vec![];
        Solution::permute0(&mut nums, 0, &mut result);
        return result
    }

    fn permute0<T:PartialEq + Clone>(arr: &mut Vec<T>, idx: usize, result: &mut Vec<Vec<T>>) {
        let len = arr.len();
        if idx == len {
            result.push(arr.clone());
            return;
        }
        for i in idx..len {
            arr.swap(i, idx);
            Solution::permute0(arr, idx + 1, result);
            arr.swap(i, idx);
        }
    }
}

回溯法2(使用 collector)

这个方法是我做了带重复元素的全排列后重新回来写这道题使用的。
代码中 idx 表示的是 collector 数组的当前长度,当 collector 数组排列满了之后,就得到了一个排列。
这里需要引入一个 vis 数组来记录 arr 中哪些元素已经参与排列了,每一次从 arr 中选择出所有还没有参与排列的元素 push 进 collector 参与排列,同时标记这个元素被使用过了。

impl Solution {
    pub fn permute(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut vis: Vec<bool> = (0..nums.len()).map(|x| false).collect();
        let mut result = vec![];
        Solution::permutation_collector(&mut nums, 0, &mut vis, &mut vec![], &mut result);
        return result;
    }

    pub fn permutation_collector<T: PartialEq + Copy>(arr: &mut Vec<T>, idx: usize, vis: &mut Vec<bool>, collector: &mut Vec<T>, res: &mut Vec<Vec<T>>) {
        if collector.len() == arr.len() {
            res.push(collector.clone());
            return;
        }
        for i in 0..arr.len() { //  arr 中所有还没有参与排列的元素都可以 push 进 collector
            if vis[i] {
                continue;
            }
            collector.push(arr[i]);
            vis[i] = true;
            Solution::permutation_collector(arr, idx + 1, vis, collector, res);
            collector.pop();
            vis[i] = false;
        }
    }
}

非回溯法(待续)

搜索旋转排序数组


原题链接

题目描述

一个升序数组,被切了一刀,分为两个部分,这两部分交换位置从新组合在一起,搜索旋转排序数组中的某个数字

方法一

分析

这题考察分类讨论的能力,首先我们画出这个数组的结构:

对该数组进行二分查找时,一定可以判断出 mid 的值处于「上」还是「下」,这样我们可以对 mid 进行分类讨论:

  1. 如果 mid 落在「上」:
    如果 target 也落在「上」且小于 mid,那么 target 在左半边,否则 target 在右半边
  2. 如果 mid 落在「下」:
    如果 target 也落在「下」且大于 mid,那么 target 在右半边,否则 target 在左半边

这里为什么是对 mid 进行分类讨论,而不是对 target 进行分类讨论呢? 原因在于,当我们求出 mid 的值的时候, 就已经可,以确定 mid 处于「上」还是「下」了,而 target 仍然处于 「上」、「下」叠加态。 同样的,我们也不会对「拐点」进行分类讨论,因为我们根本都还不知道拐点在哪里。

分类讨论的时候,如果不知道怎么讨论,最好先对已经可以确定的量去讨论

实现

class Solution {
    public int search(int[] nums, int target) {
        return search(nums, target, 0, nums.length - 1);
    }
<span class="kd">public</span> <span class="kt">int</span> <span class="nf">search</span><span class="o">(</span><span class="kt">int</span><span class="o">[]</span> <span class="n">nums</span><span class="o">,</span> <span class="kt">int</span> <span class="n">target</span><span class="o">,</span> <span class="kt">int</span> <span class="n">i</span><span class="o">,</span> <span class="kt">int</span> <span class="n">j</span><span class="o">)</span> <span class="o">{</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">i</span> <span class="o">&gt;</span> <span class="n">j</span><span class="o">)</span> <span class="k">return</span> <span class="o">-</span><span class="mi">1</span><span class="o">;</span>
    <span class="kt">int</span> <span class="n">idx</span> <span class="o">=</span> <span class="o">(</span><span class="n">i</span> <span class="o">+</span> <span class="n">j</span><span class="o">)</span> <span class="o">/</span> <span class="mi">2</span><span class="o">;</span>
    <span class="kt">int</span> <span class="n">l</span> <span class="o">=</span> <span class="n">nums</span><span class="o">[</span><span class="n">i</span><span class="o">],</span> <span class="n">r</span> <span class="o">=</span> <span class="n">nums</span><span class="o">[</span><span class="n">j</span><span class="o">],</span> <span class="n">n</span> <span class="o">=</span> <span class="n">nums</span><span class="o">[</span><span class="n">idx</span><span class="o">];</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">target</span> <span class="o">==</span> <span class="n">n</span><span class="o">)</span> <span class="k">return</span> <span class="n">idx</span><span class="o">;</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">target</span> <span class="o">==</span> <span class="n">l</span><span class="o">)</span> <span class="k">return</span> <span class="n">i</span><span class="o">;</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">target</span> <span class="o">==</span> <span class="n">r</span><span class="o">)</span> <span class="k">return</span> <span class="n">j</span><span class="o">;</span>
    <span class="c1">// 因为此时 n 的位置已经可以确定了,所以先讨论 n 的位置</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">n</span> <span class="o">&gt;</span> <span class="n">r</span><span class="o">)</span> <span class="o">{</span> <span class="c1">// 如果 n 在上</span>
        <span class="k">if</span> <span class="o">(</span><span class="n">l</span> <span class="o">&lt;</span> <span class="n">target</span> <span class="o">&amp;&amp;</span> <span class="n">target</span> <span class="o">&lt;</span> <span class="n">n</span><span class="o">)</span> <span class="o">{</span> <span class="c1">// target 也在上,并且小于 n</span>
            <span class="k">return</span> <span class="nf">search</span><span class="o">(</span><span class="n">nums</span><span class="o">,</span> <span class="n">target</span><span class="o">,</span> <span class="n">i</span> <span class="o">+</span> <span class="mi">1</span><span class="o">,</span> <span class="n">idx</span> <span class="o">-</span> <span class="mi">1</span><span class="o">);</span>
        <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
            <span class="k">return</span> <span class="nf">search</span><span class="o">(</span><span class="n">nums</span><span class="o">,</span> <span class="n">target</span><span class="o">,</span> <span class="n">idx</span> <span class="o">+</span> <span class="mi">1</span><span class="o">,</span> <span class="n">j</span> <span class="o">-</span> <span class="mi">1</span><span class="o">);</span>
        <span class="o">}</span>
    <span class="o">}</span> <span class="k">else</span> <span class="o">{</span> <span class="c1">// 如果 n 在下</span>
        <span class="k">if</span> <span class="o">(</span><span class="n">n</span> <span class="o">&lt;</span> <span class="n">target</span> <span class="o">&amp;&amp;</span> <span class="n">target</span> <span class="o">&lt;</span> <span class="n">r</span><span class="o">)</span> <span class="o">{</span> <span class="c1">// target 也在下,并且大于 n</span>
            <span class="k">return</span> <span class="nf">search</span><span class="o">(</span><span class="n">nums</span><span class="o">,</span> <span class="n">target</span><span class="o">,</span> <span class="n">idx</span> <span class="o">+</span> <span class="mi">1</span><span class="o">,</span> <span class="n">j</span> <span class="o">-</span> <span class="mi">1</span><span class="o">);</span>
        <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
            <span class="k">return</span> <span class="nf">search</span><span class="o">(</span><span class="n">nums</span><span class="o">,</span> <span class="n">target</span><span class="o">,</span> <span class="n">i</span> <span class="o">+</span> <span class="mi">1</span><span class="o">,</span> <span class="n">idx</span> <span class="o">-</span> <span class="mi">1</span><span class="o">);</span>
        <span class="o">}</span>
    <span class="o">}</span>
<span class="o">}</span>

}

方法二

分析

使用 模板法,由于 check 函数也需要引入 [l, r),参数,直接使用 r 会越界,因此先不搜索数组的最后一个元素,只考察[0, len - 2] 范围内的子数组,如果没有搜索到,此时 l 会位于 len-1 处。

实现

class Solution {
    boolean check(int l, int r, int mid, int[] nums, int target) {
        if (nums[l] <= nums[r]) { // 已经在递增区间了
            return nums[mid] >= target;
        } else {// 区间仍然是旋转数组,mid 和 target 的位置有六种情况,其中三种符合条件
            if (nums[l] <= target && target <= nums[mid]) return true;
            if (target <= nums[mid] && nums[mid] <= nums[r]) return true;
            if (nums[mid] <= nums[r] && nums[l] <= target) return true;
            return false;
        }
    }
    public int search(int[] nums, int target) {
        // 只搜索除了最后一个元素以外的位置
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + (r - l ) / 2;
            if (check(l, r, mid, nums, target)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        // 如果没有满足条件的, l 指向最后一个位置
        // 如果有满足条件的,l 也可能没有取等
        if (nums[l] != target) return -1;
        return l;
    }
}

谈谈 HashMap 实现中的若干数学问题


1. 为什么长度必须是 2 的倍数

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

答:因为某一个结点散列后的 index 是根据 hash & (len - 1) 计算得到的。如果 len 为 2 的整数倍,那么其二进制表示为:

len     : ...0001000...000
len - 1 : ...0000111...111

那么一定有 index = hash & (len - 1) <= len - 1,且如果 hash 是均匀分布的,那么 index 也是均匀分布的。

2. 为什么 TREEIFY_THRESHOLD 定为 8

/**
 * The bin count threshold for using a tree rather than list for a
 * bin.  Bins are converted to trees when adding an element to a
 * bin with at least this many nodes. The value must be greater
 * than 2 and should be at least 8 to mesh with assumptions in
 * tree removal about conversion back to plain bins upon
 * shrinkage.
 */
static final int TREEIFY_THRESHOLD = 8;

其实源码开头的注释里提到了,但是解释的不是很清楚。这里我试着来讲一下原因,先给出一个问题:

有 n 个抽屉,随机的往这些抽屉丢 m 个苹果,问某一个抽屉有 k 个苹果的概率。

设 X 为某个抽屉里的苹果数,即 X 是一个 m 重伯努利实验成功的次数,X 的分布列为
P(X=k)=(mk)pk(1−p)m−kP(X=k) = �inom{m}{k}p^k(1-p)^{m-k}P(X=k)=(km)pk(1p)mk
其中 p=1np = rac{1}{n}p=n1,这个分布列为二项分布,记为 X∼b(m,p)Xsim b(m,p)Xb(m,p),我们有 E(X)=mpE(X) = mpE(X)=mp
当 m 很大的时候,我们可以用泊松分布做近似,设 λ=E(X)lambda = E(X)λ=E(X),则
(mk)pk(1−p)m−k≈λkk!e−λ�inom{m}{k}p^k(1-p)^{m-k} approx rac{lambda^k}{k!}e^{-lambda}(km)pk(1p)mkk!λkeλ
有了以上结论,我们将情景换为 capacity 为 n 的 HashMap 往里面插入 n/2 个元素,假设 hash 是均匀分布的,设某个 bin 里元素的个数为 X,则
X∼b(n2,1n)Xsim b( rac{n}{2}, rac{1}{n})Xb(2n,n1)
使用泊松分布近似,取λ=n2×1n=0.5lambda = rac{n}{2} imes rac{1}{n} = 0.5λ=2n×n1=0.5,计算结果在源码的注释里已经给出:

k P(X=k)
0 0.60653066
1 0.30326533
2 0.07581633
3 0.01263606
4 0.00157952
6 0.00001316
7 0.00000094
8 0.00000006

可以发现,当 k=8 的时候,概率已经小于百万分之一了。

JCF -- Overview


Collection Consists

  • Collection interfaces: 描绘了不同的集合类型,比如setslistsmaps。这些接口建立了集合框架的基础。
  • General-purpose implementations: 对集合接口的通用实现。
  • Legacy implementations: 很早版本的集合类 Vector 和 Hashtable 也实现了新的接口。
  • Special-purpose implementations: 一些专用的实现。这些实现拥有非标准化的性能特性、使用限制和行为。
  • Concurrent implementations: 为高并发场景而设计的实现。
  • Wrapper implementations: 为其它实现增加了功能,比如同步。
  • Convenience implementations: 一组简化版高性能实现。
  • Abstract implementations: 一些加速某些实现构建的实现。
  • Algorithms: 在集合上运行的一些有用的静态方法,比如给列表排序。
  • Infrastructure: 对集合提供重要支持的接口
  • Array Utilities: 为数组提供了使用的函数。确切的说不是集合框架的一部分,但是是和集合框架同事加进Java平台的。

Collection Interfaces

java.util.Collection 的后代:

java.util.Map 的后代:

graph

Collection Implementations

Interface Hash Table Resizable Array Balanced Tree Linked List Hash Table + Linked List
Set HashSet   TreeSet   LinkedHashSet
List   ArrayList   LinkedList  
Deque   ArrayDeque   LinkedList  
Map HashMap   TreeMap   LinkedHashMap

Concurrent Collections

Interface

  • BlockingQueue
  • TransferQueue
  • BlockingDeque
  • ConcurrentMap
  • ConcurrentNavigableMap

Implementations

  • LinkedBlockingQueue
  • ArrayBlockingQueue
  • PriorityBlockingQueue
  • DelayQueue
  • SynchronousQueue
  • LinkedBlockingDeque
  • LinkedTransferQueue
  • CopyOnWriteArrayList
  • CopyOnWriteArraySet
  • ConcurrentSkipListSet
  • ConcurrentHashMap
  • ConcurrentSkipListMap

如何进行二分查找


模板

记住这个模板,它返回的是: 第一个满足 f(m) == true 的位置

想要知道数学推导,请参考[1]
想要知道模板的应用,请参考[2]

class Solution {
    public int binarySearch(int[] nums) {
        int l = 0, r = nums.length;
        if (l < r) {
            int m = l + (r - l) / 2;
            if (f(m)) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
}

参考资料

HashSet 源码分析


HashSet 构造

private transient HashMap<E,Object> map;

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

/**

  • Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
  • default initial capacity (16) and load factor (0.75).
    */
    public HashSet() {
    map = new HashMap<>();
    }

public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}

public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}

public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}

/**

  • Constructs a new, empty linked hash set. (This package private
  • constructor is only used by LinkedHashSet.) The backing
  • HashMap instance is a LinkedHashMap with the specified initial
  • capacity and the specified load factor.
    */
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

可以看到 HashSet 包裹了一个 HashMap,这里的 PRESENT 是一个空的对象,作为这个 HashMap 的 Value。注意到,HashMap 的默认初始容量为 16,默认负载因子为 0.75。

HashSet#add 调用链分析

//1.HashSet#add()
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}
//HashMap#hash
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//2.HashMap#put
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
//3.HashMap#putVal
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

调用链为:

  1. HashSet#add
  2. HashMap#put ( –> 使用到 HashMap#hash –> 使用到 Object#hashCode)
  3. HashMap#putVal ( –> 使用到了 Object#equals)

HashSet#equals 调用链分析

//1.AbstractSet#equals
public boolean equals(Object o) {
    if (o == this)
        return true;
    if (!(o instanceof Set))
        return false;
    Collection<?> c = (Collection<?>) o;
    if (c.size() != size())
        return false;
    try {
        return containsAll(c);
    } catch (ClassCastException unused)   {
        return false;
    } catch (NullPointerException unused) {
        return false;
    }
}
//2.AbstractCollection#containsAll
public boolean containsAll(Collection<?> c) {
    for (Object e : c)
        if (!contains(e))
            return false;
    return true;
}
//3.HashSet#contains
public boolean contains(Object o) {
    return map.containsKey(o);
}
//4.HashMap#containsKey
public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null;
}
//5.HashMap#getNode
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash &&
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

上面依次调用了:

  1. AbstractSet#equals
  2. AbstractCollection#containsAll
  3. HashSet#contains
  4. HashMap#containsKey ( –> 使用到 HashMap#hash –> 使用到 Object#hashCode)
  5. HashMap#getNode ( –> 使用到了 Object#equals)

由于 HashSet 其实是把 element 存储在 HashMap 的 key 上,HashMap#getNode 根据 key 来找结点,如果不为 null,则证明 HashMap 包含这个元素,也就是 HashSet 包含这个元素。所以对两个 HashMap 进行 equals 操作时,被包装类型必须重写 equals()hashCode() 方法,否则会导致
HashSet#contains 判断失效。

HashSet#remove 调用链分析

//1.HashSet#remove
public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}
//2.HashMap#remove
/**
 * Removes the mapping for the specified key from this map if present.
 *
 * @param  key key whose mapping is to be removed from the map
 * @return the previous value associated with <tt>key</tt>, or
 *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 *         (A <tt>null</tt> return can also indicate that the map
 *         previously associated <tt>null</tt> with <tt>key</tt>.)
 */
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}
//3.HashMap#removeNode
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

调用依次为:

  1. HashSet#remove
  2. HashMap#remove
  3. HashMap#removeNode

看上面 HashMap#remove 的注释说的:
“调用这个方法会删除键值为 key 的元素并且返回该 key 的 value。如果返回 null 代表不存在这个 key”。然而马上括号里面又说返回 null也有可能是这个 key 对应的 value 就是 null。这说明 HashMap 的 value 是可以为 null 的。(其实 key 也可以为 null

总结

1.现在回过头来看《阿里巴巴 Java 开发手册》编程规约的集合处理部分第一条:

1.【强制】关于 hashCode 和 equals 的处理,遵循如下规则:

1) 只要重写equals,就必须重写hashCode。

2) 因为Set存储的是不重复的对象,依据hashCode和equals进行判断,所以Set存储的 对象必须重写这两个方法。

3) 如果自定义对象做为Map的键,那么必须重写hashCode和equals。

说明:String 重写了 hashCode 和 equals 方法,所以我们可以非常愉快地使用 String 对象 作为 key 来使用。

2.你会发现 HashMap#putVal 方法里面怎么有 putTreeVal()treeifyBin() 这样的带 tree 字眼的方法。这其实是 Java8 相对 Java7 的升级,对于 HashMap、LinkedHashMap、ConcurrentHashMap 中存在大量冲突的位置,将用一颗平衡二叉树取代链表,可以看到代码里面定义了一些常量和操作:

常量 操作
TREEIFY_THRESHOLD=8 HashMap#treeifyBin
UNTREEIFY_THRESHOLD=6 TreeNode#untreeify
MIN_TREEIFY_CAPACITY=64 HashMap#resize

详见:

3.这一版本同时去掉了 JDK7 对 HashMap 增加的一个hash function,设置 jdk.map.althashing.threshold 后,当 Map 的 size 超过这个设置的值,对于 key 类型为 String 的 Map,将会采用一个特别设计的 hash function,默认不启用。
需要重点提醒的是,不论是 JDK7 采用 alternative hash function 或者是 JDK8 把 Map 的链表优化成平衡树,均可能导致某些情况下遍历其元素的顺序产生变化。因此我们的代码 不应该依赖于对Map遍历的顺序

在排序数组中查找元素的第一个和最后一个位置


题目描述

分析

实现

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int l = 0, r = nums.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        // 二分结束
        if (l == nums.length // 数组中没有满足性质的点
            || nums[l] != target // 满足性质的点并不是 target
        ) {
            return new int[]{-1, -1};
        }
        // 此时 l 是第一个等于 target 的点
        int l2 = l;
        // 处理 l 已经是最后一个点的情况
        for ( ; l2 < nums.length - 1 && nums[l] == nums[l2 + 1] ; l2++);
        return new int[]{l, l2};
    }
}

InnoDB存储引擎之 —— 索引算法(一)(草稿...)


InnoDB 存储引擎表示索引组织表,表中数据按照主键顺序存放。
索引应该在一开始开发的时候就进行添加。
索引太少,影响性能。索引太多,也影响性能,比如太多索引会导致磁盘使用率非常高。

索引的类型

  1. B+ 树索引
    传统意义上的索引,最常用,最有效。
    B+ 树索引不能定位到具体的行,只能定位到具体的页,然后把页读到内存中查找满足条件的行。
  2. 全文索引
  3. 哈希索引
    InnoDB 的哈希索引是自适应的,会根据表的使用情况自动为表生成,不能认为干预。

背景知识:
二分查找:
第一个二分查找在1946年出现,第一个正确的二分查找法在1962年才出现。

B+树:
省略

B+树索引:

  1. 聚集索引(clustered index)
    根据每张表的主键构建的一颗B+树(一张表只能有一个聚集索引),叶子节点存放的是一整行的信息。聚集索引的叶子也称作数据页,每个数据页通过双向链表链接。

  2. 辅助索引(secondary index)
    叶子节点存放的不是一整行的信息。

寻找峰值


原题链接

题目描述

峰值元素是指其值大于左右相邻值的元素。

给你一个输入数组nums,找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下,返回 任何一个峰值 所在位置即可。

你可以假设nums[-1] = nums[n] = -∞ 。
对于所有有效的 i 都有 nums[i] != nums[i + 1]

分析

使用二分模板:
原命题:

  1. 转化为找到第一个比右边大的元素。
  2. 或者找到最后一个比左边大的元素。
    由于二分模板比较擅长找「第一个」,所以用第一种来实现。

实现

这里直接使用二分模板

class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (check(mid, nums)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
    // 找到第一个比右边大的
    public boolean check(int mid, int[] nums) {
        return nums[mid] > nums[mid + 1];
    }
}

Longest Increasing Subsequence


原题链接

题目描述

最长增长子列(LIS)

分析

典型动态规划问题,设dp[i]为以第i个数结尾的最长增长子列的长度,则:

[mathrm{dp}[i] = max_{mathop{0leq k < i}limits_{mathrm{A}[i] > mathrm{A}[k]}}left {mathrm{dp}[k]+1
ight}]

初始时dp所有元素为1

实现

int lengthOfLIS(int* nums, int len) {
    if (len == 0) return 0;
    int *dp = (int*)malloc(len * sizeof(int));
    for (int i = 0; i < len; i++) dp[i] = 1;
    int maxSubLen = 1;
    for (int i = 1; i < len; i++) {
        for (int k = 0; k < i; k++) {
            if (nums[i] > nums[k]) {
                dp[i] = max(dp[i], dp[k] + 1);
                if (dp[i] >= maxSubLen) {
                    maxSubLen = dp[i];
                }
            }
        }
    }
    return maxSubLen;
}

Singleton Pattern


Intent

Ensure a class has only one instance, and provide a global point of access to it.

确保一个类只有一个实例,并提供一个全局访问点。[1]

Implements

Eager initialization

public class Singleton {
  public static Singleton instance = new Singleton();

private Singleton() {}

public static Singleton getInstance() {
return instance;
}
}

说明: 构造函数声明为private是为了防止用new创建类的实例。

Lazy initialization I

只有第一次调用getInstance()方法才会创建实例。

public final class Singleton {
    private static Singleton instance = null;
private Singleton() {}

public static Singleton getInstance() {
    if (instance == null) {
        instance = new Singleton();
    }
    return instance;
}

}

Lazy initialization II

Lazy initialization I 的实现在多线程环境下可能会产生多个实例。比如线程A判断instance == null后在执行new Singleton()之前,线程B也在判断instance == null,这样两个线程调用getInstance()返回的是不同的实例。解决办法是加一个重量级锁,保证同一时刻只有一个线程能进入getInstance()方法。

public final class Singleton {
    private static Singleton instance = null;
private Singleton() {}

public static synchronized Singleton getInstance() {
    if (instance == null) {
        instance = new Singleton();
    }
    return instance;
}

}

Lazy initialization III

Lazy initialization II 的实现虽然解决了可能创建多个实例的问题,但是当instance已经创建完毕后,之后线程每一次调用getInstance()获取单例时都需要同步,这会带来性能问题。为了减少同步,我们可以使用double-checked locking来减少同步代码块的规模。

public final class Singleton {
  private static volatile Singleton instance = null;

private Singleton() {}

public static Singleton getInstance() {
if (instance == null) { // a
synchronized(Singleton.class) { // b
if (instance == null) { // c
instance = new Singleton();
}
}
}
return instance;
}
}

说明:

  1. 我上面写的这种 dobule-checked locking [3]只适用于java 5+
  2. 假设多个线程同时调用getInstance()方法,首先在 a 处判断instance是否为null,假设大家都判断为null,然后执行到 b 处,只有一个线程能进入同步代码块执行 b 里面的代码,这个线程创建完instance实例离开同步区后,其它线程就可以一个一个的进入同步代码块了,由于volaile保证了instance可见性,当其它线程执行到 c 时,会发现instance不为null了,就不会创建新实例。

Lazy initialization IV

Lazy initialization III已经没什么问题了,但是性能还可以再提高一些。我们可以减少对volatile变量的访问。

public final class Singleton {
  private static volatile Singleton instance = null;

private Singleton() {}

public static Singleton getInstance() {
Singleton result = instance;
if (result == null) {
synchronized(Singleton.class) {
result = instance;
if (result == null) {
instance = result = new Singleton();
}
}
}
return result;
}

}

引入result中间变量,是因为大多数时候,instance已经被实例化了,这样代码对instance的访问就只有一次,《effectiv java》的作者说在他的电脑上这样做相对不引入临时变量,提高了25%的性能。

Lazy initialization V

使用 initialize-on-demand holder class [2]

public class Singleton {
    private Singleton() {}
public static Singleton getInstance() {
    return LazyHolder.instance;
}

private static class LazyHolder {
    private static Singleton instance = new Singleton();
}

}

补充说明:

  1. 如果我们要延迟加载的是instance filed,考虑使用 dobule-checked locking
  2. 如果我们要延迟加载的是static filed,考虑使用 initialize-on-demand holder class

Enum Singleton

上面的单利模式的实现可能会被反射或者序列化攻击,我们使用enum singleton

public enum Singleton {
    INSTANCE;
}

当我们第一次调用Singleton.INSTANCE的时候,Singleton就会被加载和初始化,翻译一下就是:

public final class Singleton {
    public final static Singleton INSTANCE = new Singleton();
}

这个方法被[4]的作者认为是单例模式最佳实践。

Reference

InnoDB存储引擎之 —— 锁(二)


锁的算法

  1. Record Lock
    只锁住行。总是去锁定索引,如果没有建索引,就锁主键。

  2. Gap Lock
    锁住一个范围,不包含记录本身

  3. Next-Key Lock (Previous-Key Lock)
    锁住一个范围,包含记录本身。

假设一个索引有10,11,13,20这四个值。那么有如下五个区间:

(-∞, 10)
(10, 11)
(11, 13)
(13, 20)
(20, +∞)
  • Gap Lock 锁的就是上述区间。
  • Next-Key Locking 锁的是上述区间的左开右闭区间。
  • Previous-Key Locking 锁的是上述区间的左闭右开区间。

InnoDB 加锁有如下三条特殊规则:

  1. 当查询的索引仅含有唯一索引的时候,Next-Key Lock 会降级为 Record Lock(联合唯一索引,每一个索引列都要查)
  2. InnoDB 还会对锁住的辅助索引加 Next-Key Lock,并且会给下一个键值加 Gap Lock
  3. 插入某记录时候,会检查插入记录的下一条记录是否被锁住了,如果锁住了,则不允许插入(阻塞)。

InnoDB 在默认的 REPETABLE READ 隔离级别下,使用 Next-Key Lock,在 READ COMMITED 隔离级别下,仅使用 Record Lock

锁的例子

下面举几个例子来讲解:

CREATE TABLE z (a INT, b, INT, PRIMARY KEY(a), KEY(b))

INSERT INTO z SELECT 1, 1;
INSERT INTO z SELECT 3, 1;
INSERT INTO z SELECT 5, 3;
INSERT INTO z SELECT 7, 6;
INSERT INTO z SELECT 10, 8

会话A:执行

SELECT * FROM z WHERE b=3 FOR UPDATE;

我们来分析会锁住哪些记录:
a 是聚集索引,加 Record Lock
b 是辅助索引,加 Next-Key Lock,下一个键值加 Gap Lock

索引 a 被锁住的记录为:

  • 5 — Record Lock

索引 b 被锁住的记录为:

  • (1, 3] — Next-Key Lock
  • (3, 6) — Gap Lock

会话B:如果执行下面这些 SQL ,则都会被阻塞:

  • SELECT FROM z WHERE a = 5 LOCK IN SHARE MODE;
    

    原因:a = 5 的索引已经被加了 Record Lock 的排它锁,所以无法再加一个共享锁了。

  • INSERT INTO z SELECT 4, 2;
    

    原因: 2 落在区间 (1, 3] Next-Key Lock 中

  • INSERT INTO z SELECT 6, 5;
    

    原因: 5 落在区间 (3, 6) Gap Lock 中

  • INSERT INTO z SELECT 2, 2;
    

    原因: 欲插入 b = 2 的记录,而 b = 3 的记录已经被锁住了。因此插入被阻塞。插入 b = 0 的记录没有问题,因为 b = 1 没有被锁。(实践发现这里 b 等于 1 的记录也可以插入,但是 b = 2 的记录被 next-key lock 锁住了呀,为什么呢?

实践了一些其它例子:

  • select * from z where b > 3;
    

    不会锁住 a = 5 的记录。同时 b 的 next-key lock 区间为 (3, +∞)
    可以给 b = 3 的记录加 S 锁 : select * from z where b = 3 lock in share mode;
    不可以 insert b = 3 的记录: INSERT INTO z SELECT 2, 3;

  • select * from z where b >= 3;
    

    会锁住 a = 5 的记录。同时 b 的 next-key lock 区间为 [3, +∞)
    不可以给 b = 3 的记录加 S 锁 : select * from z where b = 3 lock in share mode;
    不可以 insert b = 3 的记录: INSERT INTO z SELECT 2, 3;

阻塞&超时

错误代码: 1205

  • innodb_lock_wait_timeout: 用来控制等待的时间(默认是 50 秒),可以在 MYSQL 数据库运行时进行调整
  • innodb_rollback_on_timeout: 用来设定是否在等待超时时对进行中的事务进行回滚操作(默认是 OFF,代表不回滚)。不可在启动后进行修改。

当发生超时,MYSQL 数据库会抛出一个 1205 的错误,事务出现异常,在大多数情况下不会自动回滚,需要应用层自己去控制是commit还是rollback。

死锁

多个事务因争夺锁资源,造成相互等待,若无外力作用,无法推进下去。
错误代码: 1213
两种方案:

  1. 超时机制
    FIFO。谁先等待,谁先回滚。
  2. wait-for graph
    主动监测死锁,回滚 undo 代价最小的事务
    具体实现细节需要看源码,可能是通过如下两个数据结构去构造有向图:
    • Transaction Wait Lists
    • Lock Lists

      死锁检测通常采用深度优先的算法实现,在 INNODB1.2 版本之前,都是采用递归方式实现。而从 1.2 版本开始,对 wait- for graph 的死锁检测进行了优化,用非递归的方式实现。

死锁例子

  • 例子一
  • 例子二

锁升级

锁升级(Lock Escalation)是指将当前锁的粒度降低。举例来说,数据库可以把个表的 1000 个行锁升级为一个页锁,或者将页锁升级为表锁。如果在数据库的设计中认为锁是一种稀有资源,而且想避免锁的开销,那数据库中会频繁出现锁升级现象。
Microsoft SQL Server 数据库的设计认为锁是一种稀有的资源,在适合的时候会自动地将行、键或分页锁升级为更粗粒度的表级锁。这种升级保护了系统资源,防止系统使用太多的内存来维护锁,在一定程度上提高了效率。
即使在 Microsoft SQL Server20 版本之后,SQL Server 数据库支持了行锁,但是其设计和 INNODB 存储引擎完全不同,在以下情况下依然可能发生锁升级:

  1. 由一句单独的 SQL 语句在一个对象上持有的锁的数量超过了阈值,默认这个阈值为 5000。值得注意的是,如果是不同对象,则不会发生锁升级口
  2. 锁资源占用的内存超过了激活内存的 40%时就会发生锁升级

在 Microsoft SQL Server 数据库中,由于锁是一种稀有的资源,因此锁升级会带来一定的效率提高。但是锁升级带来的一个问题却是因为锁粒度的降低而导致并发性能的降低。

INNODB 存储引擎不存在锁升级的问题。因为其不是根据每个记录来产生行锁的,相反,其根据每个事务访问的每个页对锁进行管理的,采用的是位图的方式。因此不管个事务锁住页中一个记录还是多个记录,其开销通常都是一致的。

寻找山脉数组的峰值


题目描述

原题链接

分析

使用二分模板:
原命题可转化为:

  1. 找到第一个比右边大的元素。
  2. 或者找到最后一个比左边大的元素。
    由于二分模板比较擅长找「第一个」,所以用第一种来实现。

实现

这里直接使用二分模板

class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (check(mid, nums)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
    // 找到第一个比右边大的
    public boolean check(int mid, int[] nums) {
        return nums[mid] > nums[mid + 1];
    }
}

Longest Valid Parentheses


题目

求最长的有效括号的长度。题目对有效括号的定义没有说清楚,我以为是连续若干个(),实际上有效括号P的定义如下:

1. () is P
2. PP is P
3. (P) is P

求解

这道题分类在动态规划下面,我尝试做了一下没有做出来。然后看到讨论区的动态规划解法,觉得有点难想到。但是另一个使用栈的解法比较有意思。

使用栈解决

依次把括号的index入栈,如果遇到'('就push,如果遇到')'且栈顶是'('就pop,这样到最后,能匹配上的括号全部都出栈了,
在栈里剩下的括号是没有匹配到的。这里仔细看一下栈里面剩下的括号,可以发现有一个特点,它们是字符串里所有的连续有效括号的分隔点
每两个分割点之间一定是有效括号,我们遍历栈里剩下的元素,求出所有的有效括号的长度即可。

  str: )(()(())))()()   len:14
stack: ↑        ↑
分隔点: 0        9
int longestValidParentheses(string s) {
    stack<int> stack;
    int len = s.length();
    for (int i = 0; i < len; i ++) {
        if (s[i] == '(') {
            stack.push(i);
            continue;
        }
        if (!stack.empty() && s[stack.top()] == '(') {
            stack.pop();
        } else {
            stack.push(i);
        }
    }
    if (stack.empty()) return len;
    else {
        int maxNum = -1;
        int end = len;
        while(!stack.empty()) {
            int start = stack.top();
            stack.pop();
            maxNum = max(maxNum, end - start - 1);
            end = start;
        }
        maxNum = max(maxNum, end);// 这里容易漏掉,最后还要比较一次
        return maxNum;
    }
}

使用动态规划

思路来源自讨论区,不是很好想。

定义dp[i]是以第i个元素结尾的最长有效括号。

        ┏-0                             if str[i] == '('
dp[i] = ┠-dp[i-2] + 2                   if str[i] == ')' && str[i-1] == '('
        ┗-dp[i-1] + 2 + dp[i-dp[i-1]-2] if str[i] == ')' && str[i-1] == ')'


代码

组合总和


原题链接

题目描述

给定一个无重复元素的数组candidates和一个目标数target,找出candidates中所有可以使数字和为target的组合。

candidates中的数字可以无限制重复被选取。

分析

比较简单的搜索,需要注意通过限制结果是升序的来去重。

实现

impl Solution {
    pub fn combination_sum(mut candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
        let mut result = vec![];
        candidates.sort();
        Solution::combination_sum0(&candidates, target, &mut vec![], &mut result);
        return result;
    }
<span class="k">fn</span> <span class="nf">combination_sum0</span><span class="p">(</span><span class="n">candidates</span><span class="p">:</span> <span class="o">&amp;</span><span class="nb">Vec</span><span class="o">&lt;</span><span class="nb">i32</span><span class="o">&gt;</span><span class="p">,</span> <span class="n">target</span><span class="p">:</span> <span class="nb">i32</span><span class="p">,</span> <span class="n">cur</span><span class="p">:</span> <span class="o">&amp;</span><span class="k">mut</span> <span class="nb">Vec</span><span class="o">&lt;</span><span class="nb">i32</span><span class="o">&gt;</span><span class="p">,</span> <span class="n">result</span><span class="p">:</span> <span class="o">&amp;</span><span class="k">mut</span> <span class="nb">Vec</span><span class="o">&lt;</span><span class="nb">Vec</span><span class="o">&lt;</span><span class="nb">i32</span><span class="o">&gt;&gt;</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">if</span> <span class="n">target</span> <span class="o">==</span> <span class="mi">0</span> <span class="p">{</span>
        <span class="n">result</span><span class="nf">.push</span><span class="p">(</span><span class="n">cur</span><span class="nf">.clone</span><span class="p">());</span>
        <span class="k">return</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">let</span> <span class="n">filter</span><span class="p">:</span> <span class="nb">Vec</span><span class="o">&lt;</span><span class="mi">_</span><span class="o">&gt;</span> <span class="o">=</span> <span class="n">candidates</span><span class="nf">.iter</span><span class="p">()</span><span class="nf">.filter</span><span class="p">(|</span><span class="n">i</span><span class="p">|</span> <span class="p">{</span>
        <span class="k">return</span> <span class="k">if</span> <span class="k">let</span> <span class="nf">Some</span><span class="p">(</span><span class="n">l</span><span class="p">)</span> <span class="o">=</span> <span class="n">cur</span><span class="nf">.last</span><span class="p">()</span> <span class="p">{</span>
            <span class="n">i</span> <span class="o">&lt;=</span> <span class="o">&amp;&amp;</span><span class="n">target</span> <span class="o">&amp;&amp;</span> <span class="n">i</span> <span class="o">&gt;=</span> <span class="o">&amp;</span><span class="n">l</span>
        <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
            <span class="n">i</span> <span class="o">&lt;=</span> <span class="o">&amp;&amp;</span><span class="n">target</span>
        <span class="p">}</span>
    <span class="p">})</span><span class="nf">.collect</span><span class="p">();</span>
    <span class="k">for</span> <span class="n">it</span> <span class="n">in</span> <span class="n">filter</span> <span class="p">{</span>
        <span class="n">cur</span><span class="nf">.push</span><span class="p">(</span><span class="o">*</span><span class="n">it</span><span class="p">);</span>
        <span class="nn">Solution</span><span class="p">::</span><span class="nf">combination_sum0</span><span class="p">(</span><span class="n">candidates</span><span class="p">,</span> <span class="n">target</span> <span class="o">-</span> <span class="o">*</span><span class="n">it</span><span class="p">,</span> <span class="n">cur</span><span class="p">,</span> <span class="n">result</span><span class="p">);</span>
        <span class="n">cur</span><span class="nf">.pop</span><span class="p">();</span>
    <span class="p">}</span>
<span class="p">}</span>

}

Single Element in a Sorted Array


题目描述

升序数组,每个数组元素出现了两次,只有一个出现了一次,把这个数字揪出来。要求时间复杂度是log(n)

分析

这个复杂度,肯定需要二分,当我们求出 mid 的值之后,接下来怎样进一步的确定在左边还是在右边,是需要思考的。
方法是,二分之后,mid 如果有重复的,那么 mid 跟与它相同的数一起消掉后,数组被分成了两个部分,target 应该出现在长度为奇数的那半边。

实现

递归写法:

class Solution {
    public int singleNonDuplicate(int[] nums) {
        return singleNonDuplicate(nums, 0, nums.length - 1);
    }
<span class="kd">public</span> <span class="kt">int</span> <span class="nf">singleNonDuplicate</span><span class="o">(</span><span class="kt">int</span><span class="o">[]</span> <span class="n">nums</span><span class="o">,</span> <span class="kt">int</span> <span class="n">i</span><span class="o">,</span> <span class="kt">int</span> <span class="n">j</span><span class="o">)</span> <span class="o">{</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">i</span> <span class="o">==</span> <span class="n">j</span><span class="o">)</span> <span class="o">{</span>
        <span class="k">return</span> <span class="n">nums</span><span class="o">[</span><span class="n">i</span><span class="o">];</span>
    <span class="o">}</span>
    <span class="kt">int</span> <span class="n">mid</span> <span class="o">=</span> <span class="o">(</span><span class="n">i</span> <span class="o">+</span> <span class="n">j</span><span class="o">)</span> <span class="o">/</span> <span class="mi">2</span><span class="o">;</span>
    <span class="kt">int</span> <span class="n">l</span> <span class="o">=</span> <span class="n">nums</span><span class="o">[</span><span class="n">mid</span> <span class="o">-</span> <span class="mi">1</span><span class="o">],</span> <span class="n">m</span> <span class="o">=</span> <span class="n">nums</span><span class="o">[</span><span class="n">mid</span><span class="o">],</span> <span class="n">r</span> <span class="o">=</span> <span class="n">nums</span><span class="o">[</span><span class="n">mid</span> <span class="o">+</span> <span class="mi">1</span><span class="o">];</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">l</span> <span class="o">!=</span> <span class="n">m</span> <span class="o">&amp;&amp;</span> <span class="n">m</span> <span class="o">!=</span> <span class="n">r</span><span class="o">)</span> <span class="k">return</span> <span class="n">m</span><span class="o">;</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">l</span> <span class="o">==</span> <span class="n">m</span><span class="o">)</span> <span class="o">{</span> <span class="c1">// 跟左边的消了</span>
        <span class="k">if</span> <span class="o">((</span><span class="n">mid</span> <span class="o">-</span> <span class="mi">2</span> <span class="o">-</span> <span class="n">i</span> <span class="o">+</span> <span class="mi">1</span><span class="o">)</span> <span class="o">%</span> <span class="mi">2</span> <span class="o">==</span> <span class="mi">0</span><span class="o">)</span> <span class="o">{</span> <span class="c1">// 左边是偶数个,所以在右边</span>
            <span class="k">return</span> <span class="nf">singleNonDuplicate</span><span class="o">(</span><span class="n">nums</span><span class="o">,</span> <span class="n">mid</span> <span class="o">+</span> <span class="mi">1</span><span class="o">,</span> <span class="n">j</span><span class="o">);</span>
        <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
            <span class="k">return</span> <span class="nf">singleNonDuplicate</span><span class="o">(</span><span class="n">nums</span><span class="o">,</span> <span class="n">i</span><span class="o">,</span> <span class="n">mid</span> <span class="o">-</span> <span class="mi">2</span><span class="o">);</span>
        <span class="o">}</span>
    <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
        <span class="k">if</span> <span class="o">((</span><span class="n">j</span> <span class="o">-</span> <span class="o">(</span><span class="n">mid</span> <span class="o">+</span> <span class="mi">2</span><span class="o">)</span> <span class="o">+</span> <span class="mi">1</span><span class="o">)</span> <span class="o">%</span> <span class="mi">2</span> <span class="o">==</span> <span class="mi">0</span><span class="o">)</span> <span class="o">{</span> <span class="c1">// 右边是偶数个,所以在左边</span>
            <span class="k">return</span> <span class="nf">singleNonDuplicate</span><span class="o">(</span><span class="n">nums</span><span class="o">,</span> <span class="n">i</span><span class="o">,</span> <span class="n">mid</span> <span class="o">-</span> <span class="mi">1</span><span class="o">);</span>
        <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
            <span class="k">return</span> <span class="nf">singleNonDuplicate</span><span class="o">(</span><span class="n">nums</span><span class="o">,</span> <span class="n">mid</span> <span class="o">+</span> <span class="mi">2</span><span class="o">,</span> <span class="n">j</span><span class="o">);</span>
        <span class="o">}</span>
    <span class="o">}</span>
<span class="o">}</span>

}

由于递归的空间复杂度比较高,用 while 循环改写一下,也比较简单:

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int i = 0, j = nums.length - 1;
        while (true) {
            if (i == j) return nums[i];
            int mid = (i + j) / 2;
            int l = nums[mid - 1], m = nums[mid], r = nums[mid + 1];
            if (l != m && m != r) return m;
            if (l == m) { // 跟左边的消了
                if ((mid - 2 - i + 1) % 2 == 0) { // 左边是偶数个,所以在右边
                    i = mid + 1;
                } else {
                    j = mid - 2;
                }
            } else {
                if ((j - (mid + 2) + 1) % 2 == 0) { // 右边是偶数个,所以在左边
                    j = mid - 1;
                } else {
                    i = mid + 2;
                }
            }
        }
    }
}

重复元素的全排列


原题链接

题目描述

带重复元素的全排列。

回溯法

首先对数组进行排序,把重复的元素放到一起,所以这里不能用 swap 来破坏数组的有序性。

每一轮从 arr 中挑选一个元素放到 collector 中参与排列。

有两个条件来约束 arr 中位置 i 的元素是否可以参与排列:

  1. 如果位置 i 的元素已经被使用过了,那么 i 不可以重复参与排列(这个可以过第 46 题,不带重复元素的全排列)。
  2. 如果位置 i 的元素跟 i-1 位置的元素大小一样的,并且 i-1 的元素都没有参与排列,那么 i 也不能参与排列。
impl Solution {
    pub fn permute_unique(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut vis: Vec<bool> = (0..nums.len()).map(|x| false).collect();
        let mut result = vec![];
        nums.sort();
        Solution::permutation_dup(&mut nums, 0, &mut vis, &mut vec![], &mut result);
        return result;
    }

    fn permutation_dup<T: PartialEq + Copy>(arr: &mut Vec<T>, idx: usize, vis: &mut Vec<bool>, collector: &mut Vec<T>, res: &mut Vec<Vec<T>>) {
        if collector.len() == arr.len() {
            res.push(collector.clone());
            return;
        }
        for i in 0..arr.len() {
            if vis[i] || (i > 0 && arr[i] == arr[i - 1] && !vis[i - 1]) {
                continue;
            }
            vis[i] = true;
            collector.push(arr[i]);
            Solution::permutation_dup(arr, idx + 1, vis, collector, res);
            collector.pop();
            vis[i] = false;
        }
    }
}

组合总和 II


原题链接

题目描述

给定一个数组candidates和一个目标数target,找出candidates中所有可以使数字和为target的组合。

candidates中的每个数字在每个组合中只能使用一次。

分析

这道题有部分剪枝逻辑类似有重复元素的全排列。

实现

impl Solution {
    pub fn combination_sum2(mut candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
        let mut result = vec![];
        let mut vis: Vec<_> = candidates.iter().map(|i| false).collect();
        candidates.sort();
        Solution::combination_sum0(&candidates, target, &mut vec![], &mut vis, &mut result);
        return result;
    }
<span class="k">fn</span> <span class="nf">combination_sum0</span><span class="p">(</span><span class="n">candidates</span><span class="p">:</span> <span class="o">&amp;</span><span class="nb">Vec</span><span class="o">&lt;</span><span class="nb">i32</span><span class="o">&gt;</span><span class="p">,</span> <span class="n">target</span><span class="p">:</span> <span class="nb">i32</span><span class="p">,</span> <span class="n">cur</span><span class="p">:</span> <span class="o">&amp;</span><span class="k">mut</span> <span class="nb">Vec</span><span class="o">&lt;</span><span class="nb">i32</span><span class="o">&gt;</span><span class="p">,</span> <span class="n">vis</span><span class="p">:</span> <span class="o">&amp;</span><span class="k">mut</span> <span class="nb">Vec</span><span class="o">&lt;</span><span class="nb">bool</span><span class="o">&gt;</span><span class="p">,</span> <span class="n">result</span><span class="p">:</span> <span class="o">&amp;</span><span class="k">mut</span> <span class="nb">Vec</span><span class="o">&lt;</span><span class="nb">Vec</span><span class="o">&lt;</span><span class="nb">i32</span><span class="o">&gt;&gt;</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">if</span> <span class="n">target</span> <span class="o">==</span> <span class="mi">0</span> <span class="p">{</span>
        <span class="n">result</span><span class="nf">.push</span><span class="p">(</span><span class="n">cur</span><span class="nf">.clone</span><span class="p">());</span>
        <span class="k">return</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">for</span> <span class="p">(</span><span class="n">idx</span><span class="p">,</span> <span class="n">it</span><span class="p">)</span> <span class="n">in</span> <span class="n">candidates</span><span class="nf">.iter</span><span class="p">()</span><span class="nf">.enumerate</span><span class="p">()</span> <span class="p">{</span>
        <span class="c">// 已经使用过,或没有符合条件的数</span>
        <span class="k">if</span> <span class="n">it</span> <span class="o">&gt;</span> <span class="o">&amp;</span><span class="n">target</span> <span class="p">||</span> <span class="n">vis</span><span class="p">[</span><span class="n">idx</span><span class="p">]</span> <span class="p">{</span>
            <span class="k">continue</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="c">// 类似带重复元素的全排列,如果前一个元素跟这个元素相同,且没有使用过,那这个元素也不要使用了</span>
        <span class="k">if</span> <span class="n">idx</span> <span class="o">&gt;</span> <span class="mi">0</span> <span class="o">&amp;&amp;</span> <span class="n">candidates</span><span class="p">[</span><span class="n">idx</span><span class="p">]</span> <span class="o">==</span> <span class="n">candidates</span><span class="p">[</span><span class="n">idx</span> <span class="o">-</span> <span class="mi">1</span><span class="p">]</span> <span class="o">&amp;&amp;</span> <span class="n">vis</span><span class="p">[</span><span class="n">idx</span> <span class="o">-</span> <span class="mi">1</span><span class="p">]</span> <span class="o">==</span> <span class="k">false</span> <span class="p">{</span>
            <span class="k">continue</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="c">// 保证结果集数组是升序的</span>
        <span class="k">if</span> <span class="n">cur</span><span class="nf">.len</span><span class="p">()</span> <span class="o">&gt;</span> <span class="mi">0</span> <span class="o">&amp;&amp;</span> <span class="n">it</span> <span class="o">&lt;</span> <span class="n">cur</span><span class="nf">.last</span><span class="p">()</span><span class="nf">.unwrap</span><span class="p">()</span> <span class="p">{</span>
            <span class="k">continue</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="n">cur</span><span class="nf">.push</span><span class="p">(</span><span class="o">*</span><span class="n">it</span><span class="p">);</span>
        <span class="n">vis</span><span class="p">[</span><span class="n">idx</span><span class="p">]</span> <span class="o">=</span> <span class="k">true</span><span class="p">;</span>
        <span class="nn">Solution</span><span class="p">::</span><span class="nf">combination_sum0</span><span class="p">(</span><span class="n">candidates</span><span class="p">,</span> <span class="n">target</span> <span class="o">-</span> <span class="o">*</span><span class="n">it</span><span class="p">,</span> <span class="n">cur</span><span class="p">,</span> <span class="n">vis</span><span class="p">,</span> <span class="n">result</span><span class="p">);</span>
        <span class="n">vis</span><span class="p">[</span><span class="n">idx</span><span class="p">]</span> <span class="o">=</span> <span class="k">false</span><span class="p">;</span>
        <span class="n">cur</span><span class="nf">.pop</span><span class="p">();</span>
    <span class="p">}</span>
<span class="p">}</span>

}

第一个错误的版本


题目描述

分析

实现

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int l = 0, r = n;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (isBadVersion(m)) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
}

记录一次数据库迁移


前情提要

几个月前帮同学做了个新闻app,后端基本是(Spring Boot + Kotlin)技术栈,「后台管理」的前端用 react ,打包到 spring boot 的 jar 包里一起启动。服务器购买的华为云。

整个产品由以下几个模块组成:

  1. 爬虫(爬新闻,插入 MySQL 数据库)
  2. 后台管理(多用户登陆、用户管理、广告管理、报表展示)
  3. 新闻后端(给安卓客户端提供后端服务)
  4. 安卓客户端(请另一个同学写的)

同时我使用了给我发工资的优秀的网易有数来监控爬虫情况,每天发送爬虫日报。

问题发现

周一发现,连续三天新闻量没有增加。

登陆服务器后发现爬虫服务的日志如下:

使用 df -h 命令查看,发现硬盘已经满了(云服务默认40G硬盘)。

问题解决

首先,想着去数据库上删除一些记录来节省空间。结果发现,MySQL 只能执行 SELECT 语句,无法执行 DELETE 语句,哪怕一条记录也删不掉。(当磁盘满了之后,为什么delete语句也无法执行,有意思的问题)

存储新闻的 news 表有十几G,小水管根本备份不下来。删也删不掉,下载也下载不下来,数据又不能全部丢掉,因此只能考虑给硬盘扩容了。

华为云上可以在不重启的情况下,给已有的云硬盘扩容。我先花了十几块钱,买了一个 5 GB 的扩容包,发现果然所有服务都恢复正常了(可以正常插入数据)。

然后本着折腾的心态,申请了经费,又买了一块单独的 100 GB 云硬盘,决定用这个空白的 100 G 硬盘专门存放 MySQL 数据,防止数据过几天又满了的问题,同事等数据再多些,准备上 ELK 技术栈玩玩。


购买后,使用 fdisk -l 看到已经有新硬盘挂载上来了:

依次使用如下的命令初始化硬盘,并挂载硬盘到指定目录:

  1. 使用 fdisk /dev/vdb 格式化新硬盘
  2. 使用 fmkfs.ext4 /dev/vdb 创建分区
  3. 使用 mount /dev/vdb /root/dbDisk 挂载硬盘到指定目录(/root/dbDisk)

接下来,我们删除 MySQL 容器,把所有 MySQL 的数据文件移动到新目录。修改 docker-compose.yml 文件的 volumes 字段,使用 docker-compose up -d 命令启动 MySQL。

version: "3"
services:
  db:
    image: "mysql:8.0.16"
    restart: always
    command: --max_allowed_packet=20971520 --default-authentication-plugin=mysql_native_password
    environment:
        MYSQL_ROOT_PASSWORD: ''****************''
        MYSQL_USER: ''****************''
        MYSQL_PASSWORD: '****************'
        MYSQL_DATABASE: 'news'
        MYSQL_ROOT_HOST: '%'
        TZ: 'Asia/Shanghai'
    volumes:
       - /root/dbDisk/dbData:/var/lib/mysql
    ports:
      - '4396:3306'

至此,MySQL 数据迁移结束。

如何进行二分查找


模板

记住这个模板,它返回的是: 第一个满足 f(m) == true 的位置

想要知道数学推导,请参考[1]
想要知道模板的应用,请参考[2]

class Solution {
    public int binarySearch(int[] nums) {
        int l = 0, r = nums.length;
        if (l < r) {
            int m = l + (r - l) / 2;
            if (f(m)) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
}

参考资料

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.