Nicksxs's Blog

题目介绍

Given an integer array nums, return the sum of floor(nums[i] / nums[j]) for all pairs of indices 0 <= i, j < nums.length in the array. Since the answer may be too large, return it modulo 10^9 + 7.

The floor() function returns the integer part of the division.

对应中文
给你一个整数数组 nums ，请你返回所有下标对 0 <= i, j < nums.length 的 floor(nums[i] / nums[j]) 结果之和。由于答案可能会很大，请你返回答案对10^9 + 7 取余 的结果。

函数 floor() 返回输入数字的整数部分。

示例

Example 1:

Input: nums = [2,5,9]
Output: 10
Explanation:
floor(2 / 5) = floor(2 / 9) = floor(5 / 9) = 0
floor(2 / 2) = floor(5 / 5) = floor(9 / 9) = 1
floor(5 / 2) = 2
floor(9 / 2) = 4
floor(9 / 5) = 1
We calculate the floor of the division for every pair of indices in the array then sum them up.

Example 2:

Input: nums = [7,7,7,7,7,7,7]
Output: 49

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

简析

这题不愧是 hard，要不是看了讨论区的一个大神的解答感觉从头做得想好久，
主要是两点，对于任何一个在里面的数，随便举个例子是 k，最简单的就是循环所有数对 k 除一下，
这样效率会很低，那么对于 k 有什么规律呢，就是对于所有小于 k 的数，往下取整都是 0，所以不用考虑，
对于所有大于 k 的数我们可以分成一个个的区间，[k,2k-1),[2k,3k-1),[3k,4k-1)……对于这些区间的
除了 k 往下取整，每个区间内的都是一样的，所以可以简化为对于任意一个 k，我只要知道与k 相同的有多少个，然后比 k 大的各个区间各有多少个数就可以了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

static final int MAXE5 = 100_000;

static final int MODULUSE9 = 1_000_000_000 + 7;

public int sumOfFlooredPairs(int[] nums) {
    int[] counts = new int[MAXE5+1];
    for (int num : nums) {
        counts[num]++;
    }
    // 这里就是很巧妙的给后一个加上前一个的值，这样其实前后任意两者之差就是这中间的元素数量
    for (int i = 1; i <= MAXE5; i++) {
        counts[i] += counts[i - 1];
    }
    long total = 0;
    for (int i = 1; i <= MAXE5; i++) {
        long sum = 0;
        if (counts[i] == counts[i-1]) {
            continue;
        }
        for (int j = 1; i*j <= MAXE5; j++) {
            int min = i * j - 1;
            int upper = i * (j + 1) - 1;
            // 在每一个区间内的数量，
            sum += (counts[Math.min(upper, MAXE5)] - counts[min]) * (long)j;
        }
        // 左边乘数的数量，即 i 位置的元素数量
        total = (total + (sum % MODULUSE9  ) * (counts[i] - counts[i-1])) % MODULUSE9;
    }
    return (int)total;
}

贴出来大神的解析,解析

结果

在用 Apollo 作为配置中心的过程中才到过几个坑，这边记录下，因为运行 java 服务的启动参数一般比较固定，所以我们在一个新环境里运行的时候没有特意去检查，然后突然发现业务上有一些数据异常，排查之后才发现java 服务连接了测试环境的 apollo，而原因是因为环境变量传了-Denv=fat，而在我们的环境配置中 fat 就是代表测试环境， 其实应该是-Denv=pro，而 apollo 总共有这些环境

1
2
3
4
5
6
7
8
9

public enum Env{
  LOCAL, DEV, FWS, FAT, UAT, LPT, PRO, TOOLS, UNKNOWN;

  public static Env fromString(String env) {
    Env environment = EnvUtils.transformEnv(env);
    Preconditions.checkArgument(environment != UNKNOWN, String.format("Env %s is invalid", env));
    return environment;
  }
}

而这些解释

1
2
3
4
5
6
7
8
9
10
11
12
13
14

/**
 * Here is the brief description for all the predefined environments:
 * <ul>
 *   <li>LOCAL: Local Development environment, assume you are working at the beach with no network access</li>
 *   <li>DEV: Development environment</li>
 *   <li>FWS: Feature Web Service Test environment</li>
 *   <li>FAT: Feature Acceptance Test environment</li>
 *   <li>UAT: User Acceptance Test environment</li>
 *   <li>LPT: Load and Performance Test environment</li>
 *   <li>PRO: Production environment</li>
 *   <li>TOOLS: Tooling environment, a special area in production environment which allows
 * access to test environment, e.g. Apollo Portal should be deployed in tools environment</li>
 * </ul>
 */

那如果要在运行时知道 apollo 当前使用的环境可以用这个

1

Env apolloEnv = ApolloInjector.getInstance(ConfigUtil.class).getApolloEnv();

简单记录下。

题目介绍

You start at the cell (rStart, cStart) of an rows x cols grid facing east. The northwest corner is at the first row and column in the grid, and the southeast corner is at the last row and column.

You will walk in a clockwise spiral shape to visit every position in this grid. Whenever you move outside the grid’s boundary, we continue our walk outside the grid (but may return to the grid boundary later.). Eventually, we reach all rows * cols spaces of the grid.

Return an array of coordinates representing the positions of the grid in the order you visited them.

Example 1:

Input: rows = 1, cols = 4, rStart = 0, cStart = 0
Output: [[0,0],[0,1],[0,2],[0,3]]

Example 2:

Input: rows = 5, cols = 6, rStart = 1, cStart = 4
Output: [[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]

Constraints:

• 1 <= rows, cols <= 100
• 0 <= rStart < rows
• 0 <= cStart < cols

简析

这个题主要是要相同螺旋矩阵的转变方向的边界判断，已经相同步长会行进两次这个规律，写代码倒不复杂

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

public int[][] spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
        int size = rows * cols;
        int x = rStart, y = cStart;
        // 返回的二维矩阵
        int[][] matrix = new int[size][2];
        // 传入的参数就是入口第一个
        matrix[0][0] = rStart;
        matrix[0][1] = cStart;
        // 作为数量
        int z = 1;
        // 步进，1，1，2，2，3，3，4 ... 螺旋矩阵的增长
        int a = 1;
        // 方向 1 表示右，2 表示下，3 表示左，4 表示上
        int dir = 1;
        while (z < size) {
            for (int i = 0; i < 2; i++) {
                for (int j= 0; j < a; j++) {
                    // 处理方向
                    if (dir % 4 == 1) {
                        y++;
                    } else if (dir % 4 == 2) {
                        x++;
                    } else if (dir % 4 == 3) {
                        y--;
                    } else {
                        x--;
                    }
                    // 如果在实际矩阵内
                    if (x < rows && y < cols && x >= 0 && y >= 0) {
                        matrix[z][0] = x;
                        matrix[z][1] = y;
                        z++;
                    }
                }
                // 转变方向
                dir++;
            }
            // 步进++
            a++;
        }
        return matrix;
    }

结果

上周在处理一个 nginx 配置的时候，发现了一个之前不理解的小点，说一个场景，就是我们一般的处理方式就是一个 ip 端口只能配置一个域名的服务，比如 https://nicksxs.me 对应配置到 127.0.0.1:443，如果我想要把 https://nicksxs.com 也解析到这个服务器，并转发到不同的下游，这里就需要借助所谓的 SNI 的功能

Server Name Indication

A more generic solution for running several HTTPS servers on a single IP address is TLS Server Name Indication extension (SNI, RFC 6066), which allows a browser to pass a requested server name during the SSL handshake and, therefore, the server will know which certificate it should use for the connection. SNI is currently supported by most modern browsers, though may not be used by some old or special clients.
来源
机翻一下：在单个 IP 地址上运行多个 HTTPS 服务器的更通用的解决方案是 TLS 服务器名称指示扩展（SNI，RFC 6066），它允许浏览器在 SSL 握手期间传递请求的服务器名称，因此，服务器将知道哪个 它应该用于连接的证书。 目前大多数现代浏览器都支持 SNI，但某些旧的或特殊的客户端可能不使用 SNI。

首先我们需要确认 sni 已被支持

在实际的配置中就可以这样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

stream {
  map $ssl_preread_server_name $stream_map {
    nicksxs.me nme;
    nicksxs.com ncom;
  }

  upstream nme {
    server 127.0.0.1:8000;
  }
  upstream ncom {
    server 127.0.0.1:8001;
  }

  server {
    listen 443 reuseport;
    proxy_pass $stream_map;
    ssl_preread on;
  }
}

类似这样，但是这个理解是非常肤浅和不完善的，只是简单记忆下，后续再进行补充完整

还有一点就是我们在配置的时候经常配置就是 server_name，但是会看到直接在使用 ssl_server_name，
其实在listen 标识了 ssl, 对应的 ssl_server_name 就等于 server_name，不需要额外处理了。

题目介绍

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

示例

Example 1:

Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

Example 2:

Input: n = 1, bad = 1
Output: 1

简析

简单来说就是一个二分查找，但是这个问题其实处理起来还是需要搞清楚一些边界问题

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public int firstBadVersion(int n) {
    // 类似于双指针法
    int left = 1, right = n, mid;
    while (left < right) {
        // 取中点
        mid = left + (right - left) / 2;
        // 如果不是错误版本，就往右找
        if (!isBadVersion(mid)) {
            left = mid + 1;
        } else {
        // 如果是的话就往左查找
            right = mid;
        }
    }
    // 这里考虑交界情况是，在上面循环中如果 left 是好的，right 是坏的，那进入循环的时候 mid == left
    // 然后 left = mid + 1 就会等于 right，循环条件就跳出了，此时 left 就是那个起始的错误点了
    // 其实这两个是同一个值
    return left;
}

往右移动示例

往左移动示例

结果