【算法练习】做题总结

【算法练习】做题总结

一、LeetCode hot 100

原题链接：hot 100

1、两数之和

问题描述： 输入一个数组和一个目标值，找出数组中和为目标值的两个数，输出这两个数在数组中的标号。数组中每个元素不重复使用。

算法：

• 首先考虑朴素做法，两层循环遍历数组。第二层遍历仅需遍历大于第一层的数即可。
• 然后考虑优化做法，第一层遍历是必须的，第二层遍历实际要寻找数组中是否存在 target - t 的数。实现快速的查找可以用 hash 表。

代码：

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {vector<int> res;unordered_map<int, int> hash;for (int i = 0; i < nums.size(); i++){hash[nums[i]] = i;}for (int i = 0; i < nums.size(); i++){int t = nums[i];auto t1 = hash.find(target - t);if (t1 != d() && t1->second != i){res = {i, t1->second};return res;}}return res;        }
};      

unordered_map:

• hash.find ：返回元素指针，使用 -> 获取元素值；当找不到时，返回 end 指针。
• 哈希表遍历：for (auto &item:hash)。

2、字母异位词分组

问题描述： 输入一个字符串数组，从中把字母异位词分到一组，然后输出所有组别。字母异位词，有完全相同的字母（种类和数量相同，仅仅是字母顺序不同）组成的单词互为字母异位词。

样例：

思路：

• 采用哈希表高效解决分组问题。我们把一组字母异位数分到个哈希键，把单词 sort 后的结果作为 key。把 value 设置成数组，组中每多一个单词，value 就插入一个值进去。

代码：

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, vector<string>> hash;vector<vector<string>> res;for (int i = 0; i < strs.size(); i++){string oderStr = strs[i];sort(oderStr.begin(), d());hash[oderStr].push_back(strs[i]);}for (auto itm:hash){res.push_back(itm.second);}return res;}
};

3、最长连续子序列

问题描述： 给定一个乱序数组，求出其中最长的连续序列。

算法1：暴力做法。 将数组排序，遍历有序数组，检查 nums[i]-1 == nums[i-1]，将每个连续序列都找出来。取其中的最大值。

代码：

class Solution {
public:int longestConsecutive(vector<int>& nums) {int n = nums.size();if (n < 1) return 0;sort(nums.begin(), d());// for (int i = 0; i < n; i++)//     cout << nums[i] << endl;int res = 1, t = 1;for (int i = 1; i < n; i++){// printf("%d %dn", nums[i] - 1, nums[i - 1]);if (nums[i] == nums[i - 1])continue;if (nums[i] - 1 == nums[i - 1]){t++;}else{res = max(res, t);t = 1;}}res = max(res, t);return res;}
};

算法2：哈希表。 先把数组转化成hash表，然后进行一次遍历。当遍历到非序列开始元素，即 nums[i]-1 在数组中，跳过本次循环。反之，则统计以 nums[i] 开始的子序列长度。时间复杂度 O(n)，但是有点怪花的时间比暴力做长，还超时了。

代码：

class Solution {
public:int longestConsecutive(vector<int>& nums) {unordered_map<int, int> hash;for (int i = 0; i < nums.size(); i++)hash[nums[i]] = 1;int res = 0;for (int i = 0; i < nums.size(); i++){if (hash[nums[i] - 1])continue;int t = 1, tNum = nums[i];while (hash[tNum + 1]){t++;tNum++;}res = max(res, t);}return res;}
};

4、移动零

Tag： 双指针算法

问题描述： 将数组中的 0 全部移动到数组最后，并且不改变数组中非零元素的相对次序。要求不复制数组。

算法1：朴素双指针
外层循环遍历数组，如果遍历到 0，在内层 while 中，找到一个非零元素位置，交换两个位置元素。

class Solution {
public:void moveZeroes(vector<int>& nums) {for (int i = 0, j = 0; i < nums.size(); i++){if (nums[i] == 0){j = i + 1;while (j < nums.size() && nums[j] == 0)j++;if (j >= nums.size()) break;swap(nums[i], nums[j]);}}}
};

算法2：直接把非零元素放到结果数组中的对应位置

class Solution {
public:void moveZeroes(vector<int>& nums) {for (int i = 0, j = 0; i < nums.size(); i++){if (nums[i] != 0){swap(nums[i], nums[j]);j++;}   }}
};

5、盛最多水的容器

Tag：双指针算法

问题描述： 求出两条垂线和 x 轴组成的容器的最大面积。

思路： 初始时刻，指针1在左端点，指针2在右端点。将指针不断向内移动，直至两指针相遇。面积计算公式为 s = (j-i)*min(height[i], height[j])。发现面积的计算仅与两端高度的较小值有关，向内移动较大值指针，s 一定在下降。所以每次移动高度小的指针即可。因为这个规律，我们可以在 n^2 的状态空间内去除很多不必要的状态，最终达到复杂度 O(n)。

class Solution {
public:int maxArea(vector<int>& height) {int i = 0, j = height.size() - 1;int res = (j - i) * min(height[i], height[j]);while (i < j){if (height[i] < height[j])i++;elsej--;res = max(res, (j - i) * min(height[i], height[j]));}return res;}
};

6、三数之和

Tag：双指针

问题描述： 从一个数组中找出所有三个数之和为0的组合，输出所有不重复的组合，不考虑排列顺序。

算法： 首先给数组按从小到大排序。选定起始点 i，定义两个指针 k(i+1) 和 j(end)。把 k 和 j 不断往中间移动，找出选中 i 时所有满足条件的组合情况。并且在移动 i、j、k 的过程中去重，即遇到相同的数就跳过。

// code1
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(), d());int i = 0, j, k;vector<vector<int>> res;for (int i = 0; i < nums.size() && nums[i] <= 0; i++){if (i > 0 && nums[i] == nums[i - 1]) continue;j = i + 1, k = nums.size() - 1;while (j < k){int sum = nums[i] + nums[j] + nums[k];if (sum == 0){res.push_back({nums[i], nums[j], nums[k]});j++, k--;while (j < k && nums[j] == nums[j - 1]) j++;while (j < k && nums[k] == nums[k + 1]) k--;}else{if (sum > 0) k--;else j++;}}}return res;}
};// code2
class Solution {
public:int trap(vector<int>& height) {int n = height.size();int l = 0, r = n - 1, l_max = height[l], r_max = height[r];int res = 0;while (l < r){l_max = max(height[l], l_max), r_max = max(height[r], r_max);if (l_max < r_max){res += (l_max - height[l]);l++;}else{res += (r_max - height[r]);r--;}}return res;}
};

7、接雨水

Tag：单调栈&&双指针
思路1：(从横向考虑) 从左往右遍历，每每遇到 height 高于栈顶的值就可以计算一次雨水；反之则入栈，所以栈内元素一定是从上往下递增的。每次计算的雨水是以当前栈顶为雨水槽底部，次栈顶为左边界，当前位置为右边界。每次只计算底部和两边界之间的雨水，不重不漏。
思路2：(从纵向考虑) 畸形的水槽区域难以处理，为了做到不重不漏，将其分隔考虑。要么从横向，考虑整块的水槽区域；要么从纵向，逐列计算水槽。利用双指针从左右分别往中间移动。
Code：

class Solution {
public:int trap(vector<int>& height) {stack<int> st;int res = 0;for (int i = 0; i < height.size(); i++){while (!st.empty() && p()] < height[i]){int botl = p()];st.pop();if (st.empty()) break;int a = st.top(), b = i;int bon = min(height[a], height[b]);// cout << bon << " " << botl << " " << b << " " << a << endl;res += (bon - botl) * (b - a - 1);  // 计算该层面积}st.push(i);}return res;}
};

8、无重复字符的最长子串

题目描述： 从字符串中找出最长的无重复元素的子串。
样例：
“a b c a b c b b”
答案是3
思路：
（1）从左往右遍历字符串，检查当前元素是否与窗口内元素重复；
（2）若没有重复，窗口右端点为当前位置，窗口长度加1；
（3）若重复，窗口左端点为重复位置的下一个位置，窗口右端点为当前位置，窗口内的元素仍然没有重复，窗口长度发生变化，可能减小。
TAG： 滑动窗口
使用begin，end坐标，动态维护窗口，使其满足题目要求。
使用hash表优化的代码：

// 优化了窗口移动的部分
class Solution {
public:int lengthOfLongestSubstring(string s) {unordered_map<char, int> window;const int sz = s.size();int l = 0, r = 0;int res = 0;while (r < sz){char c = s[r++];++window[c];while (l < r && window[c] > 1){char d = s[l++];--window[d];}res = max(res, r - l);}return res;}
};

#9、

二、CodeForces 800

1 Rigged!

题目链接： Educational Codeforces Round 155 (Rated for Div. 2)

问题描述： s和e 是一个 pair。给定一个目标 st 和 et，以及一系列的 si 和 ei 值，确定一个小于等于 st 的值 w 使得在所有 s 大于 w 的 e 中 et 是最大的。

思路： 找规律。

代码：

#include <iostream>
#include <algorithm>using namespace std;typedef pair<int, int> PII;const int N = 110;PII p[N];
int t, n;int main()
{scanf("%d", &t);while (t--){scanf("%d", &n);int st, et;scanf("%d%d", &st, &et);for (int i = 0; i < n - 1; i++){int s, e;scanf("%d%d", &s, &e);p[i] = {e, s};}int w = 0;for (int i = 0; i < n - 1; i++){int ei = p[i].first, si = p[i].second;if (ei >= et){if (si >= st){w = -1;break;}w = max(w, si + 1);  //第一次写的时候，因为没有取max值错了}}if (w == 0){w = 1;}printf("%dn", w);}return 0;
}

2 Eraser!

问题描述： 给定一个长度为 n 的有 W 和 B 组成的字符序列，现要将 B 字符全部替换成 W，一次可以替换连续 k 个字符，求解最小的操作次数。

思路： 贪心，遍历字符序列 s，每当遇到 B 就往后修改 k 个字符。

代码：

#include <iostream>
#include <string>using namespace std;int m, n, k;
string s;int main()
{scanf("%d", &m);while (m --){cin >> n >> k;cin >> s;int res = 0;for (int i = 0; i < s.size(); i++){if (s[i] == 'B'){res++;i += k - 1;}}printf("%dn", res);}return 0;
}

3 Target Practice

Tag：找规律 + 模拟

题目链接： Traget Practice

问题描述： 给定 10*10 的靶子，越接近中心得分越高。现给定 10*10 的输入，计算得分。

思路步骤： 先把得分矩阵计算存储起来。遍历 10*10 的输入，查询得分矩阵得到得分。

代码：

#include <iostream>
#include <string.h>
#include <math.h>using namespace std;const int N = 15;int score[N][N];
char g[N][N];
int t;int main()
{//计算得分矩阵for (int i = 4; i >= 0; i--){score[i][i] = i + 1;int j = i + 1;while (j < 5){score[i][j] = i + 1;score[j][i] = i + 1;j++;}}cin >> t;while (t --){memset(g, 0, sizeof(g));for (int i = 0; i < 10; i++)for (int j = 0; j < 10; j++)cin >> g[i][j];/*    for (int i = 0; i < 10; i++){for (int j = 0; j < 10; j++)cout << g[i][j] << " ";cout << endl;}*/int res = 0;for (int i = 0; i < 10; i++)for (int j = 0; j < 10; j++){if (g[i][j] == 'X'){int x = i, y = j;if (x > 4) x = 9 - x;  //利用靶子的对称性if (y > 4) y = 9 - y;res += score[x][y];}}cout << res << endl;}return 0;
}

4 Good Kid

Tag：贪心

题目链接： Good Kid

问题描述： 输入一个整数数组，选择数组中的一个元素+1，使得数组元素的乘积最大。

思路： 选择最小的数+1。假设一个数组中存在 s[i] < s[i+1]，且除去 i 和 i+1 外，数组的乘积为 TOT。当我们给 s[i]+1，结果增加 TOT*s[i+1]；给 s[i+1]+1，结果增加 TOT*s[i]。所以给小数+1，能取得更大的乘积和。

代码：

#include <iostream>using namespace std;const int N = 10;int a[N];
int t, n;int main()
{cin >> t;while (t --){cin >> n;int mini = 0;for (int i = 0; i < n; i++){cin >> a[i];if (a[i] < a[mini]) mini = i;}a[mini] += 1;int res = 1;for (int i = 0; i < n; i++)res *= a[i];cout << res << endl;}return 0;
}