程序员进阶之算法练习（八十九）leetcode
题目1 组合总和
题目链接 题目大意： 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
题目解析： 题目要找出所有组合，并且一个数字可以无限选，那么可以用这样的枚举方式： 初始化状态，curTarget=target，记录剩下的数字和； 对于数字a[0]，不断选择从curTarget减去a[0]，直到curTarget<=0截止； 此时再恢复一个a[0]，curTarget+=a[0]，然后同样方式枚举a[1]、a[2]...
DFS的方式，中间curTarget=0则表示出现一个解，当前栈数字就是答案。
class Solution {
vector<vector<int>> ans;
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<int> cur;
while (!ans.empty()) {
ans.pop_back();
}
dfs(cur, candidates, 0, target);
return ans;
}
void dfs(vector<int> &cur, vector<int>& candidates, int index, int left) {
if (left == 0) {
ans.push_back(cur);
return ;
}
if (index >= candidates.size()) {
return ;
}
if (left >= candidates[index]) {
cur.push_back(candidates[index]);
dfs(cur, candidates, index, left - candidates[index]);
cur.pop_back();
}
dfs(cur, candidates, index + 1, left);
}
}leetcode;题目2 接雨水
题目链接 题目大意： 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6
题目解析： 先找出一个递增的子序列，直到遇到一个数组的最大值； 如何快速计算两个数字之间能乘的雨水？排除法。 矩形，去掉中间数字的和。
最后反着计算，考虑高度相同的情况即可。
class Solution {
public:
int trap(vector<int>& height) {
int curHeight = -1, sum = 0, pos = -1, ans = 0;
for (int i = 0; i < height.size(); ++i) {
if (height[i] > curHeight) {
ans += curHeight * (i - pos - 1) - sum;
curHeight = height[i];
sum = 0;
pos = i;
}
else {
sum += height[i];
}
}
int highPos = pos;
curHeight = -1, sum = 0,
pos = height.size();
for (int i = height.size() - 1; i >= highPos && i >= 0; --i) {
if (height[i] >= curHeight) {
ans += curHeight * (pos - i - 1) - sum;
curHeight = height[i];
sum = 0;
pos = i;
}
else {
sum += height[i];
}
}
return ans;
}
}lc;题目3 全排列
题目链接 题目大意： 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1： 输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 示例 2： 输入：nums = [0,1] 输出：[[0,1],[1,0]] 示例 3： 输入：nums = [1] 输出：[[1]]
提示： 1 <= nums.length <= 6 -10 <= nums[i] <= 10 nums 中的所有整数 互不相同
题目解析： 只要完成1到n的全排列，那么输出的时候把1到n换成数组元素nums[1]到nums[n]就可以得到全排列； 全排列的做法： 深度优先遍历（DFS），1、2、3、、、n，每个数字有取和不取的选择； 因为数字不相同，所以不会出现不一致的情况；（每一位至少存在不一样的数字） 用递归更容易实现。
class Solution {
public:
int vis[N];
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int> > ans;
memset(vis, 0, sizeof(int) * nums.size());
vector<int> tmp;
look(ans, nums, tmp, 0);
return ans;
}
void look(vector<vector<int> > &ans, vector<int> &num, vector<int> &tmp, int count) {
if (count == num.size()) {
ans.push_back(tmp);
return ;
}
int id;
for (id = 0; id < num.size(); ++id) {
if (!vis[id]) {
vis[id] = 1;
tmp.push_back(num[id]);
look(ans, num, tmp, count + 1);
tmp.pop_back();
vis[id] = 0;
}
}
}
}leetcode;题目4 字母异位词分组
题目链接 题目大意： 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ] 说明：
所有输入均为小写字母。 不考虑答案输出的顺序。
题目解析： 字母异位词相当于每个字符出现的次数一致，那么字符串中位置信息是无用的，可以统计每个字符串中字母的数量，每个字符可以转为长度为26的数组； 接下来用排序的方式，将所有的数组进行排序，这样数组一样的就会变得相邻，最后遍历数组即可。
思考： hash的做法，将每个字符串排序，从小到大，然后用hash的方法将字符串映射为整数；（unorder_map + string）
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
int n = strs.size();
Node dot[n];
for (int i = 0; i < n; ++i) {
memset(dot[i].cnt, 0, sizeof(dot[i].cnt));
for (int j = 0; j < strs[i].length(); ++j) {
dot[i].cnt[strs[i][j] - 'a']++;
}
dot[i].index = i;
}
sort(dot, dot + n);
vector<vector<string>> ret;
vector<string> tmp;
tmp.push_back(strs[dot[0].index]);
for (int i = 1; i < n; ++i) {
if (!dot[i].isEqual(dot[i - 1])) {
ret.push_back(tmp);
tmp.clear();
}
tmp.push_back(strs[dot[i].index]);
}
ret.push_back(tmp);
return ret;
}
}leetcode;题目5 最大子数组和
题目链接 题目大意： 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。 示例 2：
输入：nums = [1] 输出：1 示例 3：
输入：nums = [5,4,-1,7,8] 输出：23
题目解析： 暴力的做法，枚举每个子区间[i, j]，算出每个区间的和，总的复杂度是O(N ^ 2)；
动态规划的做法： 1、子问题拆解，dp[i]表示前i个数字中，区间以第i个数字结尾的最大和； 2、状态转移，两个选择，要么取a[i-1]的区间，要么不取前i-1个字数字，得状态转移方程：dp[i] = max(dp[i - 1] + a[i], a[i])； 复杂度为O(N)；
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int ret = nums[0], n = nums.size();
vector<int> dp(n);
dp[0] = nums[0];
for (int i = 1; i < n; ++i) {
dp[i] = max(dp[i - 1] + nums[i], nums[i]);
ret = max(ret, dp[i]);
}
return ret;
}
}leetcode;