Lizq的个人博客

发表于 更新于 本文字数： 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 //部署

阅读全文 »

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

两种bitcpy的实现方式

1. 显示数据bits

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#define HALF_WORD   uint16_t
#define WORD        uint32_t
void showBits(void* d, int len) {
    int bytes = len / 8;
    unsigned char* p = (unsigned char*)d;
    for (int i = 0; i < bytes; i++) {
        unsigned char tmp = 0x80;
        for (int j = 0; j < 8; j++) {
            if (tmp & *p)
                printf("1");
            else
                printf("0");
            tmp >>= 1;
        }
        printf(" ");
        ++p;
    }
    printf("\n");
}

2. bitcpy 算术方式

拷贝方式是从单个字节的低位开始拷贝，进位式拷贝。

阅读全文 »
0%