Neo's Blog

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

0%

Posted on Edited on Valine:

请实现一个函数，把字符串中的每个空格替换成”%20”。

你可以假定输入字符串的长度最大是1000。
注意输出字符串的长度可能大于1000。

样例
输入：”We are happy.”

输出：”We%20are%20happy.”

考察点： 从后往前遍历，逆向思维。

与之类似的题目： memcpy实现。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    string replaceSpaces(string &str) {
        string r;
        for (auto x : str) {
            if (x != ' ') r += x;
            else r += "%20";
        }
        return r;
    }
};

Posted on Edited on Valine:

DFS

BFS

A*算法

f(i)估价函数 = g(i)原路径长度 + h(i)启发函数

到达目标就终止

Posted on Edited on In , Valine:

题目描述

从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。

2～10为数字本身，A为1，J为11，Q为12，K为13，大小王可以看做任意数字。

为了方便，大小王均以0来表示，并且假设这副牌中大小王均有两张。

样例1
输入：[8,9,10,11,12]

输出：true
样例2
输入：[0,8,9,11,12]

输出：true

思路

  1. 排序，移除0，确保相邻元素不相同

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isContinuous( vector<int> nums ) {
        if (nums.empty()) return false;
        sort(nums.begin(), nums.end());
        int k = 0;
        while (!nums[k]) k++;
        
        for (int i = k + 1; i < nums.size(); ++i) {
            if (nums[i] == nums[i - 1])
                return false;
        }
        
        return nums.back() - nums[k] <= 4;
    }
};

Posted on Edited on In Valine:

字符串匹配算法

单模匹配

BruteForce

暴力匹配算法

Rabin-Karp

P进制Hash算法 O(N)时间复杂度

Boyer-Moore

BM算法核心思想是，利用模式串本身的特点，在模式串中某个字符与主串不能匹配的时候，将模式串往后多滑动几位，

以此来减少不必要的字符比较，提高匹配的效率。BM算法构建的规则有两类，坏字符规则和好后缀规则。

好后缀规则可以独立于坏字符规则使用。因为坏字符规则的实现比较耗内存，为了节省内存，我们可以只用好后缀规则来实现BM算法

KMP

KMP算法借鉴BM算法的思想，可以总结成好前缀规则

多模匹配

Trie

可以对Trie进行内存优化，有序数组、平衡数、跳表等

AC自动机

Posted on Edited on In Valine:

题目描述

给定一个数组A[0, 1, …, n-1]，请构建一个数组B[0, 1, …, n-1]，其中B中的元素B[i]=A[0]×A[1]×… ×A[i-1]×A[i+1]×…×A[n-1]。

不能使用除法。

暴力做法

时间复杂度：$O(n^2)$

空间复杂度：除结果数组外，$O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int> res(A.size(), 1);
        
        //i表示要计算的B数组的下标
        for (int i = 0; i < A.size(); ++i) {
            int multi = 1;
            //j表示A数组的下标，下面的循环是做累乘
            for (int j = 0; j < A.size(); j++ ) {
                if (i != i) {
                    multi *= A[i];
                }
            }
            res[i] = multi;
        }        
        return res;
    }
};

优化思路

前缀和思想:当需要多次计算从i到j的累加和时，我们可以考虑计算序列的前缀和序列，把i到j的累加和转换为前缀和序列中i,j下标的元素之差。

重复计算必可优化原则：当一套解法中存在重复计算时，我们总是可以依照空间换时间原则，将可能存在重复的计算结果存下来。存下来之后，算法的执行效率便提升了。

注意到，前面的暴力解法中，对于i与i+1两个下标的计算，总是会重复计算A[1]到A[i]，我们是否可以仅计算一次呢？

时间优化版代码

时间复杂度：$O(n)$

空间复杂度：除结果数组外，$O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int> res(A.size(), 1);
        
        vector<int> pre_part(A.size(), 1); //前半部分的累乘结果
        for (int i = 1; i < A.size(); ++i) {
            pre_part[i] = pre_part[i - 1] * A[i - 1];
        }

        vector<int> post_part(A.size(), 1); //后半部分的累乘结果
        for (int i = A.size() - 2; i >= 0; --i) {
            post_part[i] = post_part[i + 1] * A[i + 1];
        }

         //i表示要计算的B数组的下标
        for (int i = 0; i < A.size(); ++i) {
            res[i] = pre_part[i - 1] * post_part[i + 1];
        }   
        
        return res;
    }
};

进一步优化思路

考虑上面代码中的第3步，res[i]的计算仅与pre_part数组中的i - 1项有关，我们是否可以把pre_part的计算结果存放在res中呢？

如果把第3步的迭代顺序反一下，那么第2部分与第3部分的迭代顺序就一致了。并且post_part[i]仅与前一项有关，我们可以做空间压缩（动态规划背包问题的常见套路），仅使用一个变量即可。

空间优化版代码

时间复杂度：$O(n)$

空间复杂度：除结果数组外，$O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int> res(A.size(), 1);
        
        //先将前半部分的计算结果存起来
        for (int i = 1; i < A.size(); ++i) {
            res[i] = res[i - 1] * A[i - 1];
        }

        //逆序遍历，只用一个变量multi来存储后半部分的计算结果。
        for (int i = A.size() - 2; i >= 0; --i) {
            multi = multi * A[i + 1];
            res[i] = res[i - 1] * multi;
        }
 
        return res;
    }
};

Posted on Edited on In , Valine:

题目描述

将一个骰子投掷n次，获得的总点数为s，s的可能范围为n~6n。

掷出某一点数，可能有多种掷法，例如投掷2次，掷出3点，共有[1,2],[2,1]两种掷法。

请求出投掷n次，掷出n~6n点分别有多少种掷法。

样例1
输入：n=1

输出：[1, 1, 1, 1, 1, 1]

解释：投掷1次，可能出现的点数为1-6，共计6种。每种点数都只有1种掷法。所以输出[1, 1, 1, 1, 1, 1]。
样例2
输入：n=2

输出：[1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]

解释：投掷2次，可能出现的点数为2-12，共计11种。每种点数可能掷法数目分别为1,2,3,4,5,6,5,4,3,2,1。

所以输出[1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]。

思路

  1. DFS
  2. 因为有很多重复计算，所以考虑用DP来优化，状态转移方程：

表示i次骰子透出j的投法数量。

DFS代码

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
class Solution {
public:
    vector<int> path;
    vector<int> res;

    void dfs(int n, int sum) {
        if (n == 0) {
            res[sum]++;
            return;
        }

        for (int i = 1; i <= 6; ++i) {
            dfs(n - 1, sum + i);
        }
    }

    vector<int> numberOfDice(int n) {
        res.resize(6 * n + 1);
        dfs(n, 0);

        vector<int> ret;
        for (auto x : res) {
            if (x > 0) ret.push_back(x);
        }

        return ret;
    }
};

Posted on Edited on In , Valine:

请实现一个函数用来匹配包括’.’和’*’的正则表达式。

模式中的字符’.’表示任意一个字符，而’*’表示它前面的字符可以出现任意次（含0次）。

在本题中，匹配是指字符串的所有字符匹配整个模式。

例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但是与”aa.a”和”ab*a”均不匹配。

样例
输入：

s=”aa”
p=”a*”

输出:true

动态规则
f(i,j)表示字符串a从i到结尾是否匹配字符串b从j到结尾
f(m,n) => f(0,0)

Posted on Edited on In Valine:

题目描述

给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。

例如，如果输入数组[2, 3, 4, 2, 6, 2, 5, 1]及滑动窗口的大小3,那么一共存在6个滑动窗口，它们的最大值分别为[4, 4, 6, 6, 6, 5]。

注意：

数据保证k大于0，且k小于等于数组长度。
样例
输入：[2, 3, 4, 2, 6, 2, 5, 1] , k=3

输出: [4, 4, 6, 6, 6, 5]

思路

  1. 借助单调队列
  2. 从队头到队尾，元素依次变小，所以称之为单调队列。
  3. 队列中存放数组元素下标

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
  public:
    vector<int> maxInWindows(vector<int>& nums, int k) {
        deque<int> dq; //双端队列
        vector<int> res;
        for (int i = 0; i < nums.size(); ++i) {
            while (dq.size() && dq.back() - dq.front() >= k - 1) dq.pop_front();
            while (dq.size() && nums[i] >= nums[dq.back()]) dq.pop_back();
            dq.push_back(i);
            if (i >= k - 1) {
                res.push_back(nums[dq.front()]);
            }
        }

        return res;
    }
};

Posted on Edited on Valine:

两类埋点类型

前端（客户端）埋点

使用场景：
第一，产品运营初期阶段，产品功能相对简单
第二，需要分析与后端无关的前端用户行为等，例如用户点击、鼠标移动等

服务端埋点

使用场景：
第一，追求精细化运营，需要进行多维数据分析的企业
第二，包含用户资产数据、用户账户体系相关数据、风控辅助数据等重要业务数据的网站或APP的企业
第三，对数据安全要求比较高的企业

哪种埋点更科学

总结下来：
第一，没有任何一种通用数据采集方式，是适合所有企业业务诉求的。
第二，结合行业特性、自身实际需求，设定特定的数据采集方案。