Neo's Blog

不抽象就无法深入思考
不还原就看不到本来面目!

0%

Posted on Edited on In Valine:

Maximum sum such that no two elements are adjacent
Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).Answer the question in most efficient way.
Examples :
Input : arr[] = {5, 5, 10, 100, 10, 5}
Output : 110

Input : arr[] = {1, 2, 3}
Output : 4

Input : arr[] = {1, 20, 3}
Output : 20

不相邻序列最大和—思路

遍历array 中的所有元素，设置两个变量：

excl[i]: 不包含i元素的最大和

incl[i]: 包含i元素的最大和

更新当前元素的 excl 和 incl：

不包含当前元素的最大和 excl[i] = max(incl[i-1]， excl[i-1])

包含当前元素的最大和 incl = excl[i-1]+A[i] (元素不能相邻)

因为只与前一项有关，所以可以用空间压缩。

Posted on Edited on In , Valine:

我们把只包含质因子2、3和5的数称作丑数（Ugly Number）。

例如6、8都是丑数，但14不是，因为它包含质因子7。

求第n个丑数的值。

样例
输入：5

输出：5
注意：习惯上我们把1当做第一个丑数。

解答思路

第二种：创建数组保存已经找到丑数，用空间换时间的解法。
根据丑数的定义， 丑数应该是另一个丑数乘以 2、3 或者 5 的结果（1 除外）。因此我们可以创建一个数组，里面的数字是排好序的丑数，每一个丑数都是前面的丑数乘以 2、3 或者 5 得到的。

这种思路的关键在于怎样确保数组里面的丑数是排好序的。假设数组中已经有若干个丑数排好序后存放在数组中，并且把己有最大的丑数记做M，我们接下来分析如何生成下一个丑数。该丑数肯定是前面某一个丑数乘以 2、3 或者 5 的结果， 所以我们首先考虑把已有的每个丑数乘以 2。在乘以 2 的时钝能得到若干个小于或等于 M 的结果。由于是按照顺序生成的，小于或者等于 M 肯定己经在数组中了，我们不需再次考虑：还会得到若干个大于 M 的结果，但我们只需要第一个大于 M 的结果，因为我们希望丑数是按从小到大的顺序生成的，其他更大的结果以后再说。我们把得到的第一个乘以 2 后大于 M 的结果记为 M2，同样，我们把已有的每一个丑数乘以 3 和 5，能得到第一个大于 M 的结果 M3 和 M，那么下一个丑数应该是 M2、M3 和 M5 这 3 个数的最小者。

前面分析的时候，提到把已有的每个丑数分别都乘以 2、3 和 5。事实上这不是必须的，因为已有的丑数是按顺序存放在数组中的。对乘以 2 而言， 肯定存在某一个丑数 T2，排在它之前的每一个丑数乘以 2 得到的结果都会小于已有最大的丑数，在它之后的每一个丑数乘以 2 得到的结果都会太大。我们只需记下这个丑数的位置， 同时每次生成新的丑数的时候，去更新这个 T2。对乘以 3 和 5 而言， 也存在着同样的 T3 和 T5。

T2的更新是需要靠遍历来完成的，但是需要明确的是：T2不需要每次都从0开始，他是越来越大的。

Posted on Edited on In Valine:

求解一个矩阵中找一条最长的递增路径？

可能解法：有向图DFS和记忆化搜索处理

dp[i][j]表示以(i,j)出发的最长路径。

该题目用常规的DP很难完成，因为他没有base condition，不知道从何处开始计算。

Posted on Edited on In Valine:

给你一根长度为 n 绳子，请把绳子剪成 m 段（m、n 都是整数，2≤n≤58 并且 m≥2）。

每段的绳子的长度记为k[0]、k[1]、……、k[m]。k[0]k[1] … k[m] 可能的最大乘积是多少？

例如当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到最大的乘积18。

样例
输入：8

输出：18

自上而下 + 备忘录解法

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
class Solution {
public:
    vector<int> dp;
    
    int dfs(int n) {
        if (dp[n] > 0) {
            return dp[n];
        }
        
        if (n <= 3) {
            dp[n] = n - 1;
            return n - 1; 
        }
        if (n == 4) {
            dp[n] = 4;
            return dp[n];
        }
         if (n == 5) {
            dp[n] = 6;
            return dp[n];
        }
        int max_score = 0;
        for (int i = 2; i <= n - 2; ++i) {
            //分为两种情况：第一刀减在i处；剩下的那一部分可以有两种选择：不剪，或者继续剪
            max_score = max(max_score, max(i * (n - i), i * dfs(n - i)));
        }
        dp[n] = max_score;
        return dp[n];
    }

    int maxProductAfterCutting(int length) {
        dp = vector<int>(length + 5, 0);
        return dfs(length);
    }
};

Posted on Edited on In Valine:

在一个m×n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于0）。

你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格直到到达棋盘的右下角。

给定一个棋盘及其上面的礼物，请计算你最多能拿到多少价值的礼物？

注意：

m,n>0
样例：

输入：
[
[2,3,1],
[1,7,1],
[4,6,1]
]

输出：19

解释：沿着路径 2→3→7→6→1 可以得到拿到最大价值礼物。

解题思路：

  1. 自上而下 + 记忆化搜索
  2. 动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
public:
    typedef pair<int, int> PII;
    int res;
    int m;
    int n;
    vector<vector<int>> grid;
    vector<vector<int>> dp;
    
    /*
    void dfs(int x, int y, int sum) {
        if (x == m - 1 && y == n -1) {
            res = max(res, sum);
            return;
        }
        
        int dx[] = {0, 1};
        int dy[] = {1, 0};
        for (int k = 0; k < 2; ++k) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] >= 0) {
                int b = grid[nxa][ny];
                grid[nx][ny] = -1;
                dfs(nx, ny, sum + b);
                grid[nx][ny] = b;
            }
        }
    }
    
    int getMaxValue(vector<vector<int>>& _grid) {
        grid = _grid;
        m = grid.size();
        n = grid[0].size();
        dfs(0, 0, grid[0][0]);
        return res;
    }
    */
    

     int dfs(int i, int j) {
        if (dp[i][i] >= 0) {
            return dp[i][j];
        }
        
        if (i == 0 && j == 0) {
            return dp[i][j] = grid[i][j];
        }
        
        dp[i][j] = grid[i][j] + max(
                                j - 1 >= 0 ? dfs(i, j - 1) : INT_MIN, 
                                i - 1 >= 0 ? dfs(i - 1, j) : INT_MIN);
        return dp[i][j];
    }
    
    int getMaxValue(vector<vector<int>>& _grid) {
        grid = _grid;
        m = grid.size();
        n = grid[0].size();
        dp = vector<vector<int>>(m, vector<int>(n, -1));
        dfs(m - 1, n - 1);
        return dp[m - 1][n - 1];
    }
};

Posted on Edited on In , Valine:

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。

请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

样例
输入数组：

[
[1,2,8,9]，
[2,4,9,12]，
[4,7,10,13]，
[6,8,11,15]
]

如果输入查找数值为7，则返回true，

如果输入查找数值为5，则返回false。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool searchArray(vector<vector<int>> array, int target) {
        if (array.empty() || array[0].empty()) return false;
        int i = 0, j = array[0].size() - 1;
        while (i < array.size() && j >= 0) {
            if (array[i][j] == target) return true;
            if (array[i][j] > target) j--;
            else i++;
        }
        return false;
    }
};

Posted on Edited on In Valine:

关于二分

二分是分治的一种；问题收敛速度最快的一种。

通过每次把问题搜索空间排除一半，进而得到lgN的时间复杂度。

将区间分为两部分，第一部分满足某一个特征；第二部分满足另一个特征

通过二分来解决的问题包括：

  1. 二分查找一个数组
  2. 通过二分的方式，遍历所有可能的结果。然后判定结果是否ok。也就是把查找问题转换为判定问题。

二分答案：答案具有“单调性”，外层花费$logN$的时间转化为判定性问题.

答案具有“单调性”：注意是先0后1函数，还是先1后0函数，和二分的实现形式，是一直保持小于，还是能累加就累加？

一般定义判定是“是否存在一个小于等于、是否存在一个大于等于”，这么定义是显然有单调性的

二分出的答案一般对check的进行有所帮助

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
//整数二分算法模板 https://www.cnblogs.com/smallocean/p/11913963.html

bool check(int x) {return true;/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

    while (l < r) {
        int mid = l + r >> 1;
        if (nums[mid] < k) {
            l = mid + 1;
        }
        else {
            r = mid;
        }
    }
    if (nums[r] != k) return 0;
    int left = r;

    // 右边界
    l = 0, r = nums.size() - 1;
    while (l < r) {
        int mid = l + r  + 1 >> 1;
        if (nums[mid] > k) {
            r = mid - 1;
        }
        else {
            l = mid;
        }
    }

//浮点数二分算法模板 —— 模板题 AcWing 790. 数的三次方根
bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

二分相关题目索引

题目分类 题目名称 考察点 其他说明
查第一个出现的位置
递增找number与index相等
重复数字出现次数
旋转数组找最值
求两个有序数组前K大的数 考虑A的中间元素m/2和B的中间元素n/2
多路归并 求m个有序数组前K大的数 维护一个大小为m的堆

参考：

https://zhuanlan.zhihu.com/p/157779732

https://www.dazhuanlan.com/2019/12/16/5df6e82127d88/

https://blog.csdn.net/weixin_34355715/article/details/94465888

https://blog.csdn.net/weixin_43626741/article/details/104364387

Posted on Edited on In Valine:

分布式锁应该具备哪些条件

  1. 在分布式系统环境下，一个方法在同一时间只能被一个机器的一个线程执行
  2. 高可用的获取锁与释放锁
  3. 高性能的获取锁与释放锁
  4. 具备可重入特性（可理解为重新进入，由多于一个任务并发使用，而不必担心数据错误）
  5. 具备锁失效机制，防止死锁
  6. 具备非阻塞锁特性，即没有获取到锁将直接返回获取锁失败

ps. 考虑幂等性

分布式锁实现

基于数据库

基于Redis SET命令

wath dog去自动设置超时时间

通过 Redis 分布式锁的实现理解基本概念
https://www.jianshu.com/p/a1ebab8ce78a

基于Memcache CAS命令

基于Zookeeper

Posted on Edited on Valine:

设计目标：

  1. 高性能，更快的找到下一个超时的Task
  2. 高分辨率，例如毫秒定时器

实现方式：

  • 时间轮、多级时间轮
  • 堆
  • 基于排序链表 O(N)
  • 红黑树

Posted on Edited on Valine:

并发 = rt * qps

N = X * R

N表示系统中同时活动的用户，包括正在处理中和队列中的；X表示用户相继到达系统的速率，在平衡状态时即为系统吞吐量（到达=离开）；R表示每个用户在系统中平均的驻留时间

eg. 一个请求在系统中的停留时间，1s; 一秒钟平均过来100个请求（当然一秒钟也会离开100个请求）那么系统同时处理的请求数是多少？

应该是1s * 100 (个/s) = 100个。

Eric的估算公式 C = L * n / T

n表示同时在线；L表示平均停留时间；T表示高峰期持续时间；C为并发用户数量。

eg. 一个用户在系统中的停留时间，30分钟；晚高峰5～7点，有500在线；问系统的并发用户是多少？

假设系统后端维护session，那么这个session的长度即为30分钟，L=30minutes；用户活跃时长已经得知是从5点到7点共2个小时，T=2 hours；那么并发用户数C=nL/T=50030/(5*60)=50

等价性说明

我们再来从另外的角度分解Eric的估算公式：

C=nL/T 可以表示为 C=(n/T)L

n/T 是不是和我们刚才在上面Little中第一步一样，是计算到达率X的。

而L（session时长）不就是R（驻留时间）吗？都等同于session时间长度。

也就是说C=(n/T)L=XR=N

结论：由以上得知，Eric’s 估算公式跟Little定律是等价的.

参考：https://www.cnblogs.com/hundredsofyears/p/3360305.html

并发 = 到达率X * 停留时间R

并发 = （同时在线人数c / 高峰期持续时长T） * 平均停留时间L