程序员进阶之算法练习（六十九）
题目1
题目链接 题目大意： 给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成
示例 1: 给定数组 nums = [1,1,2], 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 你不需要考虑数组中超出新长度后面的元素。 示例 2: 给定 nums = [0,0,1,1,1,2,2,3,3,4], 函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。 你不需要考虑数组中超出新长度后面的元素。
题目解析： 我们用数字x1、x2、x3、x4来表示数组不同元素，那么最终的排列肯定是x1、x2、x3、x4； 容易知道数组a[0]=x1, a[1]=x2，a[2]=x3，a[3]=x4，那么我们只要知道数组中数字是第几个不同的数字，就可以知道它在数组a的位置； 题目给出的数组是有序数组，那么只要从左到右遍历，记住不同数字出现数量，将数字直接前移到对应位置即可。
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int cnt = 0;
for (int i = 1; i < nums.size(); ++i) {
if (nums[i] == nums[i - 1]) {
++cnt;
}
else {
nums[i - cnt] = nums[i];
}
}
return nums.size() - cnt;
}
};题目2
题目链接 题目大意： 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例： 输入：nums = [-1,2,1,-4], target = 1 输出：2 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。 提示： 3 <= nums.length <= 10^3 -10^3 <= nums[i] <= 10^3 -10^4 <= target <= 10^4
题目解析： 假如不考虑复杂度，可以枚举3个数，复杂度是O(N^3）； 加一个优化，先对数组排序，随机选择2个数之后，接下来可以用二分来查找剩下的数字，复杂度是O(N^2 · LogN)；
如果还想优化呢？ 在排序完之后，我们仍然使用枚举固定第一个元素a，并且要求剩下两个元素b和c在元素a的右边；（因为顺序并不重要） 问题变成了在区间中寻找两个数字，其和尽可能接近target-a，就是普通的双指针问题，比如说： 在一个从小到大的数组中有n个元素，找到两个元素b和c，使得和尽可能接近x； 令b=x[1], c=x[n]，假如b+c>x，那么x[2]、x[3]和x[n]的和 只会更大，所以可以直接跳过，令c=x[n-1]； 同理，如果b+c<x，那么b+x[n-1] <= b + x[n]，所以可以直接跳过，令 b=x[2]; 这样总的复杂度就是O(NLogN)的排序，加上O(N^2)的枚举；
这里考虑到实现成本，使用的是简单法。
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int n = nums.size();
int dif = 0x7fffffff, ret = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
for (int k = j + 1; k < n; ++k) {
int tmp = nums[i] + nums[j] + nums[k];
if (abs(tmp - target) < dif) {
dif = abs(tmp - target);
ret = tmp;
}
}
}
}
return ret;
}
}leetcode;题目3
题目链接 题目大意： 给出一个整形数组，返回数组的下一个排列(next permutation)，排列是按照字典序排序的； 如果数组已经是字典序最大值，则返回字典序最小的排列； 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1
题目解析： 题目的描述很直接--找数组的下一个排列，但是看起来毫无头绪。 我们先从一个简单例子入手： 对于数字1，2，4，5这样的数组，先求出其下一个排列1、2、5、4。 这个我们可以直接看出来，接下来尝试用程序化的语言来描述这个思维过程。 从右到左遍历数组，对于位置为index的数字nums[index]，我们从index+1开始往右查找一位数字，要求尽可能接近nums[index]； 如果能寻找到，则用其与nums[index]交换，接着从index+1开始的位置则从小到大排列。 比如说1，2，4，5；我们找到4，其右边有一个数字5，将4和5交换，得到1，2，5；剩下的部分从小到大排列，这样可以得到下一个排列。
特殊情况： 比如说数组是从大到小排列，比如说3，2，1。 此时下一个排列返回从小到大的排列，1，2，3即可。
class Solution {
public:
void nextPermutation(vector<int>& nums) {
for (int index = (int)nums.size() - 2; index >= 0; --index) {
int value = nums[index];
int minDiff = -1, minIndex = -1;
for (int j = index + 1; j < nums.size(); ++j) {
if (nums[j] > value) {
if (minDiff == -1 || nums[j] - value < minDiff) {
minDiff = nums[j] - value;
minIndex = j;
}
}
}
if (minIndex != -1) {
int tmp = nums[minIndex];
nums[minIndex] = nums[index];
nums[index] = tmp;
sort(nums.begin() + index + 1, nums.end());
return ;
}
}
sort(nums.begin(), nums.end());
}
}leetcode;题目4
题目链接 题目大意： 给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()" 示例 2:
输入: ")()())" 输出: 4 解释: 最长有效括号子串为 "()()"
题目解析： 先用栈，找到所有的匹配的括号，标记好01的位置，0是默认值，1表示该位置有匹配的括号； 然后遍历数组，统计连续1的长度；
复杂度解析： 时间复杂度是O(N) 空间复杂度是O(N)
特殊样例： (((((()) ()()()(() ( ( ( ) ( ) ) )
class Solution {
public:
int longestValidParentheses(string s) {
int ret = 0;
stack<int> stk;
vector<int> vis = vector<int>(s.length());
for (int i = 0; i < s.length(); ++i) {
char c = s[i];
if (c == '(') {
stk.push(i);
}
else {
if (stk.size() > 0) {
vis[stk.top()] = 1;
vis[i] = 1;
stk.pop();
}
}
}
int tmp = 0;
for (int i = 0; i < s.length(); ++i) {
if (vis[i]) {
++tmp;
ret = max(ret, tmp);
}
else {
tmp = 0;
}
}
return ret;
}
}leetcode;题目5
题目链接 题目大意： 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符 '*' 匹配零个或多个前面的那一个元素 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
说明: s 可能为空，且只包含从 a-z 的小写字母。 p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3:
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
示例 4:
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。题目解析： 用搜索是一种解法，但是搜索写起来比较麻烦，并且时间复杂度也有较大劣势； 这里使用动态规划会更加合适。 动态规划要优先考虑子问题和无后效性，我们用dp[i][j]表示字符串s前i个字符和字符串p前j个字符是否匹配，容易知道dp[i][j]的状态可以由dp[i-1][j-1]等前面的状态递推过来，并且dp[i][j]不会影响前面的结果。 接下来推导状态转移方程： 首先看字符p[j]，如果p[j]不是' * '字符，那么dp[i][j]就取决于s[i]是否等于p[j]，s[i]==p[j]或者p[j]==' . ' 则有dp[i][j]=dp[i-1][j-1]；否则有dp[i][j]=false; 如果p[j]是' * '字符，那么要分情况讨论，如果取的是0个，那么dp[i][j]就可以由dp[i][j-2]递推过来；如果是取1个以上，那么在满足s[i]和p[j-1]相同的情况，可以由dp[i-1][j]递推过来；
注意： 子状态的设计比较直接，状态转移也没有太多考虑点，但是在实现过程还是需要考虑越界等边界情况。
class Solution {
vector<vector<bool> > dp;
bool checkCharMatch(char c, char p) {
return (c == p) || (p == '.');
}
public:
bool isMatch(string s, string p) {
dp.clear();
for (int i = 0; i <= s.length(); ++i) {
vector<bool> vec(p.length() + 1, 0);
dp.push_back(vec);
}
dp[0][0] = 1;
for (int i = 0; i <= s.length(); ++i) {
for (int j = 1; j <= p.length(); ++j) {
if (p[j-1] == '*') {
if (j <= 1) { // 避免出现单个*开头的字符串
return false;
}
// x* *号表示0个，或者1到若干个)
dp[i][j] = dp[i][j-2]; // 表示*取0个，需要特殊考虑
if (i>0 && checkCharMatch(s[i - 1], p[j - 2])) { // 如果某个s[i-1]和p[j-2]匹配，则当s[i-1]没有出现过，直接看前面dp[i-1][j]是否匹配即可；
dp[i][j] = dp[i][j] || dp[i - 1][j];
}
}
else if (i>0 && checkCharMatch(s[i - 1], p[j - 1])) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
bool ret = dp[s.length()][p.length()];
return ret;
}
}ac;腾讯云开发者
