Lizq的个人博客

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

540 有序数组中的单一元素

我的二分

  • 与右侧配对失败:
    • 右侧是奇数: l = m + 1
    • 右侧是偶数: r = m
  • 与右侧配对成功:
    • 右侧是奇数: l = m + 2
    • 右侧是偶数: r = m - 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int l = 0, r = nums.size()-1;
        while(l < r){ // 这样可以放心取m+1不越界
            int m = (l + r) >> 1;
            if(nums[m] != nums[m+1]){
                if((r-m) & 1) l = m + 1;
                else r = m;
            }else{
                if((r-m-1) & 1) l = m + 2;
                else r = m - 1;
            }
        }
        return nums[l];
    }
};

官方的全数组二分查找

阅读全文 »

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

1 寻找峰值

找到任意一个峰值，你可以假设 nums[-1] = nums[n] = -∞ 。

1.1 二分法（不怎么优雅）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l = 0, r = nums.size()-1;
        while(l <= r){
            int m = (l + r) / 2;
            if(m-1>=0 && nums[m-1]>nums[m])
                r = m - 1;
            else if(m+1<nums.size() && nums[m+1]>nums[m])
                l = m + 1;
            else
                return m;
        }
        return 0; // 永远不会走
    }
};

1.2 二分法（优雅）

阅读全文 »

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

83 删除排序链表中重复元素

前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head) return head;
        ListNode* ptr = head->next;
        while(ptr && head->val == ptr->val) ptr = ptr->next;

        // 下面俩方式效果一样
        head->next = deleteDuplicates(ptr);
        // head->next = ptr;
        // deleteDuplicates(ptr);
        return head;
    }
};

后续遍历

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head) return head;
        // 有点像并查集里的路径压缩
        head->next = deleteDuplicates(head->next);
        if(head->next && head->val == head->next->val)
            return head->next;
        return head;
    }
};
阅读全文 »

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

1143 最长公共子序列

  • 子序列是可以不连续的
  • dp[i][j]的含义是text1[:i]和text2[:j]最长公共子序列，这个最长公共子序列不一定包含text1[i]和text2[j]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(), n = text2.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0)); // 多一行一列
        for(int i=1; i<=m; ++i){
            for(int j=1; j<=n; ++j){
                if(text1[i-1] == text2[j-1]) dp[i][j] = dp[i-1][j-1] + 1; // 别忘了坐标偏移
                else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[m][n];
    }
};

718 最长重复子数组

  • 子数组是连续的
  • dp[i][j]的含义是以nums1[i]结尾的nums1[:i]和以nums2[j]结尾的nums2[:j]的最长重复子数组
阅读全文 »

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

零. 子集、组合和排列问题汇总

  • 组合问题和子集问题是等价的
  • 参考labuladong和优秀题解

一. 子集问题

78 子集划分

1.1 子集扩张

阅读全文 »

发表于 更新于 本文字数： 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:])))
阅读全文 »
0%