Lizq的个人博客

发表于 更新于 本文字数： 472 阅读时长 ≈ 2 分钟

43 字符串相乘

两数A位和B位，相加后位数最大为max(A, B)+1；相乘后最大位数为A+B

1.1 常规法

将两个串的指针位置m和n、进位c统一放入while循环，代码就会很优美。 代码可以继续优化速度存储：addtion函数改为原地相加，但是会破坏代码的逻辑性，就不改了。

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
class Solution {
public:
    string addtion(string& num1, string& num2){
        int m = num1.size()-1, n = num2.size()-1;
        int c = 0;
        string ret;
        while(m>=0 || n>=0 || c){
            int a = m>=0 ? num1[m]-'0' : 0; // 越界定0技巧
            int b = n>=0 ? num2[n]-'0' : 0; // 越界定0技巧
            int s = a + b + c;
            ret.push_back('0' + s % 10);
            c = s / 10;
            --m, --n;
        }
        reverse(ret.begin(), ret.end()); // 反转
        return ret;
    }
    
    string multiply(string num1, string num2) {
        if(num1=="0" || num2=="0") return "0";
        string res = "0";
        int cnt = 0; // 记录表示每次乘完左移的0的个数
        int m = num2.size()-1;
        while(m >= 0){
            int n = num1.size()-1;
            int b = num2[m] - '0';
            int c = 0;
            string ret(cnt, '0'); // 初始化"左移"0
            while(n>=0 || c){
                int a = n>=0 ? num1[n]-'0' : 0; // 越界定0技巧
                int s = a * b + c;
                ret.push_back('0' + s % 10);
                c = s / 10;
                --n;
            }
            reverse(ret.begin(), ret.end()); // 反转
            res = addtion(res, ret);
            --m, ++cnt;
        }
        return res;
    }
};
阅读全文 »

发表于 更新于 本文字数： 543 阅读时长 ≈ 2 分钟

1. 124 二叉树中的最大路径和

1.1 两个递归的笨方法

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
class Solution {
public:
    int ans = INT_MIN;
    int core(TreeNode* root) { // 找到以root为起点，深入向下的最大路径一条线（分叉只走一条）
        if(!root) return 0;
        int lv = core(root->left);
        int rv = core(root->right);
        int res = max(max(lv, rv), 0) + root->val;
        return res;
    }
    
    void recursion(TreeNode* root){ // 遍历树中每个结点，尝试寻找本题答案的“起点根”
        if(!root) return;
        recursion(root->left);
        recursion(root->right);
        int lv = core(root->left); // 以左孩子为起点的“线”
        int rv = core(root->right); // 以右孩子为起点的“线”
        if(lv < 0) lv = 0;
        if(rv < 0) rv = 0;
        ans = max(ans, lv + rv + root->val);
    }
    
    int maxPathSum(TreeNode* root) {
        recursion(root);
        return ans;
    }
};

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
class Solution {
public:
    int ans = INT_MIN;
    int core(TreeNode* root) {
        if(!root) return 0;
        
        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int lv = max(core(root->left), 0);
        int rv = max(core(root->right), 0);
        
        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int ifAnsRoot = root->val + lv + rv;
        ans = max(ans, ifAnsRoot);
        
        // 返回
        return max(lv, rv) + root->val;
    }
    
    int maxPathSum(TreeNode* root) {
        core(root);
        return ans;
    }
};
阅读全文 »

发表于 更新于 本文字数： 268 阅读时长 ≈ 1 分钟

470 用 Rand7() 实现 Rand10()

1. 拒绝采样

在解LC-470前先介绍一道拒绝采样的经典问题：利用频率近似概率的方式求出 $\pi$ 的值。在 $1\times1$ 的方块内随机坐标采样，记录落入以原点为圆心，半径为1的 $\frac{1}{4}$ 圆内的次数。

由 $\frac{1}{4}\pi r^2 = \frac{cnt}{N}$ 可得 $\pi = \frac{4\times cnt}{N\times r^2}$ ，由于 $r=1$ ，所以 $\pi = \frac{4\times cnt}{N}$

1
2
3
4
5
6
7
8
9
10
11
int main() {
    srand((unsigned)time(0)); // time(0)表示从1970到现在的秒数
    int N = (int)1e7, cnt = 0;
    for (int i = 0; i < N; i++) {
        double a = (1.0 * rand() / RAND_MAX); // 除以RAND_MAX归一化0~1
        double b = (1.0 * rand() / RAND_MAX);
        if (a * a + b * b < 1.0) cnt++; // 落入1/4圆则加一
    }
    printf("%lf", (4.0 * cnt) / N);
    return 0;
}
阅读全文 »

发表于 更新于 本文字数： 1k 阅读时长 ≈ 4 分钟

32 最长有效括号

方法1：动态规划

1.1 错误1

无法解决诸如(())的问题。 要考虑到当前碰到右括号后，前面的是左括号还是右括号，然后分别进行处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        int l = 0;
        vector<int> dp(n);
        int ret = 0;
        for(int i=0; i<n; ++i){
            if(s[i] == '('){
                ++l; 
                continue;
            }
            if(l){
                --l;
                dp[i] = 2;
                if(i-2 >= 0) dp[i] += dp[i-2]; // BUG
                ret = max(ret, dp[i]);
            }
        }
        return ret;
    }
};
阅读全文 »

发表于 更新于 本文字数： 1.1k 阅读时长 ≈ 4 分钟

目标检测SSD

1. 锚框的长和宽

1.1 书上代码解析

s指的是长宽的缩放比例而非面积的缩放比例，比如s=0.5，则面积就是原图像的0.5^2=0.25倍。r是宽高比，指的是将原图像归一化为正方形后截取的锚框的宽高比；或者说是在原图像的宽高比基础上乘以r，才是锚框的宽高比。锚框的实际宽高比即$\frac{w}{h}r$。之所以r=1时你看到的是方形，之后会解释。
由此，可得以下方程组
$$\begin{cases}
w_0h_0=s^2wh\
\frac{w_0}{h_0}=\frac{w}{h} * r
\end{cases}$$
解得
$$
\begin{cases}
w_0=sw\sqrt{r}\
h_0=sh/\sqrt{r}
\end{cases}
$$
$w_0和h_0$分别处以w和h进行归一化，可得
$$
\begin{cases}
w_0=s\sqrt{r} \
h_0=s/\sqrt{r}
\end{cases}
$$
而在代码中我们可以看到：

1
2
3
4
5
w0 = torch.cat((size_tensor * torch.sqrt(ratio_tensor[0]),
                   sizes[0] * torch.sqrt(ratio_tensor[1:])))\
                   * in_height / in_width
h0 = torch.cat((size_tensor / torch.sqrt(ratio_tensor[0]),
                   sizes[0] / torch.sqrt(ratio_tensor[1:])))
阅读全文 »

发表于 更新于 本文字数： 357 阅读时长 ≈ 1 分钟

C++ priority_queue自定义排序总结

方法一：函数指针

以下几种都可以，具体可参考《C++ Primer》

1
2
3
4
5
6
7
8
9
10
typedef int elem;
bool cmp(elem a, elem b) {
    return a < b;
}
priority_queue<elem, vector<elem>, decltype(&cmp)> q(arr.begin(), arr.end(), cmp);
priority_queue<elem, vector<elem>, decltype(cmp)*> q(arr.begin(), arr.end(), cmp);
priority_queue<elem, vector<elem>, bool(*)(elem, elem)> q(arr.begin(), arr.end(), cmp);
// 构造函数前两个可以不填，但是必须传入cmp
// 前面模板只是告诉它是一个函数指针bool(*)(elem, elem)，但并没有传入函数地址（实体）
priority_queue<elem, vector<elem>, bool(*)(elem, elem)> q(cmp);

对于cmp和&cmp你应该这样理解，cmp是函数的首地址，它的类型是bool(elem, elem)，&cmp表示一个指向函数cmp这个对象的地址，它的类型是bool(*)(elem, elem)，因此test和&test所代表的地址的值是一样的，但类型不一样！

阅读全文 »

发表于 更新于 本文字数： 406 阅读时长 ≈ 1 分钟

数组指针和指针数组

s的类型是二维数组，但是其本身也是一个一维指针（数组指针），其静态类型是char(*)[10]，每次移动是10个char长度也就是10字节。其解引用后静态类型是char*，每次移动是1个char长度也就是1字节。

值得注意的是，类似函数指针，s、*s、&s其值都是一样的，都是该二维数组首个元素的地址，因此不能将数组名当成是一个值为元素首地址的常规变量！因为永远无法取得其地址。

因此，下面代码中将s赋值给双重指针ps是完全错误的；双重指针要经过两次间接跳转访问元素：比如ps的值为0x0000ff33，*ps首先跳转到该位置后取其值，比如说那个地址的值为0x0000eedd，将*ps当成字符串输出时，会再次跳转到地址为0x0000eedd的位置取出char，完全乱了。

而作为对比，数组指针解引用不会跳转，只会修改其步幅跨度

阅读全文 »

发表于 更新于 本文字数： 240 阅读时长 ≈ 1 分钟

经典读者写者问题

读者写者问题

1、读者优先
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
int readcount=0; 
semaphore RCSignal=1, fileSrc=1;
// RCSignal readcount修改互斥量
// fileSrc 文件资源互斥量：实现读者优先

// 读者进程：
    P(RCSignal);
    readcount++;	
    if (readcount == 1)
        P(fileSrc);
    V(RCSignal);
    // ...
    // reading is performed
    // ...
    P(RCSignal);
    readcount--;
    if (readcount == 0)
        V(fileSrc);
    V(RCSignal);
 
// 写者进程：     
    P(fileSrc);
    //...
    //writing is performed
    //...
    V(fileSrc);
2、写者优先
阅读全文 »

发表于 更新于 本文字数： 1.8k 阅读时长 ≈ 6 分钟

记录本书（对我来说）的一些重点内容

1 C++编程基础

  1. 初始化方法：构造函数法（constructor syntax）
1
2
int var(66);
int var2{66}; // ok
  1. srand()随机数种子；rand()则产生一个介于0和int所能表示的最大整数；需包含头文件cstdlib
  2. cerr（standard error）代表标准错误设备，与cout唯一区别就是不带缓冲，立即显示于用户终端
阅读全文 »

发表于 更新于 本文字数： 459 阅读时长 ≈ 2 分钟

Hexo相关说明

安装Hexo

安装hexo

Hexo基本语法

hexo n 我的博客 == hexo new 我的博客 //新建文章
hexo g == hexo generate //生成
hexo s == hexo server //启动服务预览
hexo d == hexo deploy //部署

阅读全文 »
0%