滑动窗口

AddTwoNumbers
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

1
2
3

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

背包九讲读书笔记

0-1 背包问题

基本题目套路

有 N 件物品和一个容量为 V 的背包，放入第 i 件物品消耗的费用是 Ci， 得到的价值是 Wi。 求解将哪些物品装入背包，可使总价值总和最大。

基本题目思路

• 特点：每件物品只有一个，选择：放 or 不放。
• 子问题：F[i, v]： 前 i 件物品恰好放入容量 v 的背包，可以获得的最大价值
• 状态转移：F[i, v] = max{F[i-1, v], F[i-1, v-Ci] + Wi}
• 当前的价值，只和之前的价值有关，因此两个选择下的价值为：
• 如果 i 不选，价值：前 i-1 件，放入容量 v 的背包（F[i-1, v]）
• 如果 i 选择，价值：前 i-1 件，放入容量（v-Ci）的背包（确保 i 能放下去，得减去 i 占用的容量）+ 放入 i 的价值 Wi

伪代码

1
2
3
4

F[0, 0..V] <- 0
for i <- 1 to N
    for v <- Ci to V
        F[i, v] <- max{F[i-1, v], F[i-1, v-Ci] + Wi}

优化

时间复杂度：O(VN)
空间复杂度：滚动数组（逆序计算 F[v]，才能保证正确的顺序）

1
2
3
4

F[0..V] <- 0
for i <- 1 to N
    for v <- V to Ci
        F[v] <- max{F[v], F[v-Ci] + Wi}

1
2
3

def ZeroOnePack(F,C,W)
    for v <- V to C
        F[v] <- max(F[v], F[C-v] + W)

1
2
3

F[0..V] <- 0
    for i <- 1 to N
        ZeroOnePack(F,Ci,Wi)

完全背包问题

题目基本套路

N 种物品和容量为 V 的背包，每种物品都有无限件可以用，放入第 i 件物品消耗的费用是 Ci， 得到的价值是 Wi。 求解将哪些物品装入背包，可使物品总消耗费用不超过背包容量，且价值总和最大。

基本套路

• 每种物品无限件，因此每个物品的策略不是：选和不选。而是选几件
• 状态转移：F[i, v] = max{F[i-1, v-kCi] + kWi | 0 ≤ kCi ≤ v}

简单有效的优化

• 若两件物品i, j 满足 Ci ≤ Cj 且 Wi ≥ Wj，则可以将 j 直接去掉，不用考虑 (任何情况下，都可以将价值小费用高的 j 换成物美价廉的 i)
• 或者 将费用大于 V 的物品去掉

转换为 0-1 背包问题

• 第 i 种物品最多选：V/Ci 种，把第 i 种物品转化为 V/Ci 件费用及价值不变的物品。 （将一种物品转化为多件只能选 0 或者 1 件的 0-1 背包问题）
• 二进制：第 i 种物品拆成费用为 Ci2^k，价值为 Wi2^k 的若干件物品。 k 满足 Ci2^k ≤ V 的非负整数。

问题由来

今天在做项目的时候，发现自定义的 NSTextView 出现了几种情况比较蛋疼

• 对齐问题，英文对齐，中文偏移

• 在中英文混输的情况下，会出现之前的文字上下抖动的情况，可以拿出来钉钉试试

先在输入框中输入中文（啊），空格上屏后，再输入一个英文字符 a

不断地尝试删除 a，再输入 a

你会看到 啊 会随着你的输入和删除上下做轻微的抖动，感觉在拍抖音，给个背景音乐很应景

自己的项目

出现了同样的问题，而且更严重的是，同样的输入框，在作为用户签名的时候，中文会有明显的偏移

英文对齐，中文上偏

解决

尝试了很多办法，其实比较简单，让自定义的 layoutManager 和 textContainer 去适配一下。
关键代码如下

1
2
3

textStorage.addLayoutManager(layoutManager)
layoutManager.addTextContainer(textContainer)
layoutManager.typesetterBehavior = .behavior_10_2_WithCompatibility

前后比较一下，所有问题都消失了

配置

经常用 VSCode 来开发 C++，但是调试和配置每次都很头疼，现记录一下配置，备忘

tasks.json

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

{
    // See https://go.microsoft.com/fwlink/?LinkId=733558
    // for the documentation about the tasks.json format
    "version": "2.0.0",
    "tasks": [
      {
        "type": "shell",
        "label": "clang++ build active file",
        "command": "/usr/bin/clang++",
        "args": [
          "-std=c++17",
          "-stdlib=libc++",
          "-g",
          // "${workspaceFolder}/*.cpp",
          "${file}",
          "-o",
          "${fileDirname}/${fileBasenameNoExtension}"
        ],
        "options": {
          "cwd": "${workspaceFolder}"
        },
        "problemMatcher": ["$gcc"],
        "group": {
          "kind": "build",
          "isDefault": true
        },
      }
    ]
  }

launch.json

build and debug

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

{
    "version": "0.2.0",
    "configurations": [
        {
            "name": "C++ - Build and debug active file",
            "type": "cppdbg",
            "request": "launch",
            "program": "${fileDirname}/${fileBasenameNoExtension}",
            "args": [],
            "stopAtEntry": true,
            "cwd": "${workspaceFolder}",
            "environment": [],
            "externalConsole": false,
            "MIMode": "lldb",
            "preLaunchTask": "clang++ build active file",
            "setupCommands": [
                {
                    "description": "Enable pretty-printing for gdb",
                    "text": "-enable-pretty-printing",
                    "ignoreFailures": true
                }
            ],
          }
    ]
}

c_cpp_cofiguration.json

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

{
    "configurations": [
      {
        "name": "Mac",
        "includePath": ["${workspaceFolder}/**", "/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/"],
        "defines": [],
        "macFrameworkPath": [
          "/System/Library/Frameworks",
          "/Library/Frameworks"
        ],
        "compilerPath": "/usr/bin/clang",
        "cStandard": "c11",
        "cppStandard": "c++17",
        "intelliSenseMode": "clang-x64"
      }
    ],
    "version": 4
  }

起因

今天做了一道题，LeetCode 560. Subarray Sum Equals K，有点蒙蔽，看了答案发现比较简单，记录一下

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

1
2
3
4
5
6
7
8

示例 1 :

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :

数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

位操作总结

基本上位操作就那么几个:

异或的特性

1
2
3
4
5
6
7
8
9

x ^ 0 = x

x ^ 11111……1111 = ~x

x ^ (~x) = 11111……1111

x ^ x = 0

a ^ b = c => a ^ c = b => b ^ c = a (交换律) a ^ b ^ c = a ^ (b ^ c) = (a ^ b）^ c (结合律)

构造特殊的Mask

• 将 x 最右边的 n 位清零， x & ( ~0 << n )
• 获取 x 的第 n 位值(0 或者 1)，(x >> n) & 1
• 获取 x 的第 n 位的幂值，x & (1 << (n - 1))
• 仅将第 n 位置为 1，x | (1 << n)
• 仅将第 n 位置为 0，x & (~(1 << n))
• 将 x 最⾼位⾄第 n 位(含)清零，x & ((1 << n) - 1)
• 将第 n 位⾄第 0 位(含)清零，x & (~((1 << (n + 1)) - 1)

X & 1 == 1 判断是否是奇数(偶数)
X & = (X - 1) 将最低位(LSB)的 1 清零
X & -X 得到最低位(LSB)的 1

X & ~X = 0

Range Sum Query Immutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:

1
2
3
4
5
6
7
8

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
Note:
You may assume that the array does not change.
There are many calls to sumRange function.

题目

Find K-th Smallest Pair Distance
Given an integer array, return the k-th smallest distance among all the pairs. The distance of a pair (A, B) is defined as the absolute difference between A and B.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Example 1:
Input:
nums = [1,3,1]
k = 1
Output: 0
Explanation:
Here are all the pairs:
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
Then the 1st smallest distance pair is (1,1), and its distance is 0.
Note:
2 <= len(nums) <= 10000.
0 <= nums[i] < 1000000.
1 <= k <= len(nums) * (len(nums) - 1) / 2.

链表总结

1
2
3
4
5

struct ListNode{
    int value;
    ListNode* next;
    ListNode(int v) : value(v), next(nullptr) { }
};

二叉树总结

1
2
3
4
5
6

struct TreeNode{
    int value;
    TreeNode *left;
    TreeNode *right
    TreeNode(int v): value(v),left(nullptr), right(nullptr) {}
};