起因

今天做了一道题，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) {}
};

题目

Find the Duplicated Number
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

1
2

Input: [1,3,4,2,2]
Output: 2

Example 2:

1
2

Input: [3,1,3,4,2]
Output: 3

Note:

You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.

题目

Basic Calculator
Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

Example 1:

1
2

Input: "1 + 1"
Output: 2

Example 2:

1
2

Input: " 2-1 + 2 "
Output: 3

Example 3:

1
2

Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23

Note:
You may assume that the given expression is always valid.
Do not use the eval built-in library function.

题目

Best Time to Buy and Sell Stock IV
Say you have an array for which the i-th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Example 1:

1
2
3

Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

1
2
3
4

Input: [3,2,6,5,0,3], k = 2
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
             Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

动态规划套路

有一个 m*n 大小的矩阵迷宫，每次移动只能向右或者向下，文聪左上角到右下角有多少种不同的走法

暴力解法

• 从(1,1)->(m,n)的不同路径中有大量的重复，比如(1,1)->(i,j)有 k 条不同的路径，那么对于任何一条固定的路线(i,j)->(m,n)的路径，都需要走 k 遍来模拟。
• 不关心具体的走法，只关心状态，也就是走法的数量
• 同理，如果知道(i,j)->(m,n)有 k 条不同的路径，那么(1,1)->(i,j)->(m,n)的不同路径总数是k*s

动态规划

• 令(i,j)表示从(1,1)->(i,j)的不同路径数量，f(i,j) = f(i-1,j) + f(i,j-1)
• 如果要求出 f(i,j) 只需要上一个结果即可， 也就是求解f(i,j) 需要求出子问题f(i',j')

动态规划适用前提

无后效性

• 一旦确定f(i,j)，就不用关心如何计算出f(i,j)
• 想要确定f(i,j)，只要知道f(i-1,j)和f(i,j-1)

最优子结构

• f(i,j)的定义已经蕴含最优
• 大问题的最优解可以由若干小问题的最优解推出(min, max, sum)

  DP 适用的问题：可以将大问题拆成几个小问题，且无后效性，具有最优子结构的性质

记忆化递归

• 可以使用递归求解
• 有重复子问题，overlaping subproblem