最长公共子序列

一、题目

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

例子：

1
2
3

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

本文对于 nSum 问题进行分析。先从最简单的 twoSum 问题来看。

一、twoSum 问题

如果假设输入一个数组 nums 和一个目标和 target，请你返回 nums 中能够凑出 target 的两个元素的值，比如输入 nums = [1,3,5,6], target = 9，那么算法返回两个元素 [3,6]。可以假设只有且仅有一对儿元素可以凑出 target。

针对这个题目，我们可以使用双指针的方式，分别从最左边和最右边进行遍历数组。

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

std::vector<int> twoSum(const std::vector<int>& nums, int target) {
    if (nums.size() < 2) {
        return std::vector<int>();
    }
    int left = 0, right = nums.size()-1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            return std::vector<int>{nums[left], nums[right]};
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return std::vector<int>();
}

一、题目

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

1
2
3
4
5
6
7
8

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

从5随机到7随机及其扩展

一、题目

给定一个等概率随机产生 1 - 5 的随机函数 rand1To5。如下：

1
2
3

int rand1To5() {
	return (int)((random() * 5) + 1);
}

除此之外，不能使用任何额外的随机机制，请用 rand1To5 实现等概率随机产生 1-7 的随机函数 rand1To7

二、解析

先解决原问题，具体步骤如下：

一、题目

在二维坐标系中，所有的值都是 double 类型，那么一个矩形可以由 4 个点来代表。 (x1, y1) 为最左的点，(x2, y2) 为最上的点，(x3, y3) 为最下的点，(x4, y4) 为最右的点。给定 4 个点代表的矩形，在给定一个点 (x, y) ，判断 (x, y) 是否在矩形中。

二、分析

矩形在一个二维坐标系中，如果矩形和横坐标或者纵坐标轴平行。那么好办，只需要选取对角线上的两个坐标点，然后判断这个点，是否在两个坐标点之内即可。如下：

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

bool is_inside_parallel(double x1, double y1, double x4, double y4, double x, double y) {
		if (x <= x1) {
				return false;
		}
		if (x >= x4) {
				return false;
		}
		if (y >= y1) {
				return false;
		}
		if (y <= y4) {
				return false;
		}
		return true;
}

如果矩形的边不平行于坐标轴呢？我们可以通过将矩形进行旋转成平行的，需要判断的点也跟着旋转。旋转完成后，按照如上的规则进行判断即可。

一、题目

Leetcode：https://leetcode.cn/problems/design-authentication-manager/description/

你需要设计一个包含验证码的验证系统。每一次验证中，用户会收到一个新的验证码，这个验证码在 currentTime 时刻之后 timeToLive 秒过期。如果验证码被更新了，那么它会在 currentTime （可能与之前的 currentTime 不同）时刻延长 timeToLive 秒。

请你实现 AuthenticationManager 类：

• AuthenticationManager(int timeToLive) 构造 AuthenticationManager 并设置 timeToLive 参数。

一、题目

给定一个长度为N的整型数组 arr，可以划分成左右两个部分： 左部分 arr[0..K]，右部分 arr[K+1..arr.length-1]，K 可以取值的范围是 [0,arr.length-2] 求这么多划分方案中，左部分中的最大值减去右部分最大值的绝对值，最大是多少？

例如： [2,7,3,1,1] 当左部分为[2,7]，右部分为 [3,1,1] 时，左部分中的最大值减去右部分最大值的绝对值为4; 当左部分为[2,7,3]，右部分为[1,1]时，左部分中的最大值减去右部分最大值的绝对值为 6; 最后返回的结果为 6。 注意：如果数组的长度为 N，请尽量做到时间复杂度 O(N)，额外空间复杂度 O(1)

二、分析

最笨的办法是，在数组的每个位置 i 都做一次这种划分，找到 arr[0 ... i] 的最大值 maxLeft，找到 arr[i+1 ... N-1] 的最大值 maxRight。然后计算两个值相减的绝对值。每次划分都这样求一下，可以得到最大的相减的绝对值。但是时间复杂度：O(N^2)，额外的空间复杂度：O(1)

稍加优化，将中间结果存储一下，准备两个数组 leftArr、rightArr，对原数组先从左向右遍历一次，leftArr[i] 就存储 arr[0 ... i] 中的最大值。再从右向左遍历一次，rightArr[i] 存储 arr[i ... N-1] 中的最大值。然后最后一次遍历看那种划分的情况下可以得到两部分最大的相减绝对值。这种情况下，时间复杂度：O(N)，空间复杂度：O(N)

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

int maxABS(const std::vector<int>& arr) {
    if (arr.empty()) {
        return 0;
    }
    std::vector<int> leftArr(arr.size(), 0);
    leftArr[0] = arr[0];
    std::vector<int> rightArr(arr.size(), 0);
    rightArr[arr.size()-1] = arr[arr.size()-1];
    for (int i = 1; i < arr.size(); i++) {
        leftArr[i] = std::max(leftArr[i-1], arr[i]);
    }
    for (int i = arr.size()-2; i >= 0; i--) {
        rightArr[i] = std::max(rightArr[i+1], arr[i]);
    }
    int res = 0;
    for (int i = 0; i <= arr.size()-2; i++) {
        res = std::max(res, std::abs(leftArr[i] - rightArr[i+1]));
    }
    return res;
}

一、题目

给定一个数组，求如何排序之后，相邻两数的最大差值。要求时间复杂度 O(N)，且要求不能用非基于比较的排序

二、分析

我们一般的排序的时间复杂度最小为 N*logN。这里我们假设有 N 个数，我们定义 N+1 长度的容器，相当于 N+1 个桶。先求出这 N 个数的最大值和最小值。然后将这些数等分为 N+1 份，分布在这 N+1 个桶中。

此时必然有数的最小值存在于最左边的桶，数的最大值存在于最右边的桶。并且一定会有一个空桶，因为 N 个桶有 N+1 个桶。

每个桶保存两个数，当前桶所表示的范围中的最大值和最小值。那么最终相邻两数的最大差值一定来自于两桶之间的差值，也就是左边桶的最大值和相邻右边桶的最小值。

为什么要 N+1 个桶呢？为了就是去掉那些平凡解。这些桶中相邻差值，要么来自于桶内、要么来自于相邻桶。增加一个桶相当于去掉了桶内的解，让相邻桶的差值一定大于桶内元素的差值。增加一个桶相当于缩小了一个桶本应该表示的范围。

一、题目

给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

Leetcode：https://leetcode.cn/problems/max-points-on-a-line/description/

二、分析

如果点 i 和点 j 所连直线的斜率等于点 i 和点 k 所连直线的斜率。那么我们说 i、j、k 三个点在同一条直线上。

我们可以统计其他所有点与点 i 所连直线的斜率，出现次数最多的斜率即为经过点数最多的直线的斜率，其经过的点数为该斜率出现的次数加一（点 i 自身也要被统计）。

斜率如何计算，比如两个点：(x1, y1), (x2, y2)。他们的斜率为：(y1-y2)/(x1-x2)。注意对于 1/2 和 2/4 这两个斜率是相同的，因此我们需要将他们化简为最简分数的形式。最大公约数的求法可以使用辗转相除法。

阶乘问题

一、题目

给定一个非负整数 N，返回 N! 结果的末尾为 0 的数量。例如 3! = 6，结果的末尾没有 0，则返回 0。5! = 120，结果的末尾有 1 个 0。返回 1。

二、分析

末尾为 0 说明可以凑成 10，又因为一个数中如果有 5 的因子，那么一定会有 2 的因子。因此我们只需要求 1,2,3, ..., N-1,N，这 N 个数中一共有多少个因子 5。因子 2 的数目比因子 5 的数目多，所以不管有多少个因子 5，都有足够的因子 2 可以与其相乘得到 10。所以这个问题我们只需要求 1 - N 所有的数中，一共含有多少个因子 5 就可以。

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

int zeroNum1(int num) {
		if (num < 0) {
				return 0;
		}
		int res = 0;
		int cur = 0;
		for (int i = 5; i < num+1; i=i+5) {
				cur = i;
				while (cur % 5 == 0) {
						res++;
						cur /= 5;
				}
		}
		return res;
}

以上的方法对于每一个数 i 来说，处理的代价是 logi（以 5 为底），一共有 N 个数，所以时间复杂度为：O(N*logN)