【动态规划】常见动态规划题目总结
此博客是为总结动态规划常见题目。
嗯，当然也包含了大量非动态规划问题。
题目类型真乱。
题目1：word break
1.1 题目描述：
Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s =“leetcode”,
dict =[“leet”, “code”].
Return true because"leetcode"can be segmented as"leet code".
1.2 思路
状态方程，dp大小为字符串的长度+1，dp[i]表示字符串s[0,i]是否可以分词。
如何更新状态方程，
默认初始化所有的dp[i]=false;dp[0]=true;
遍历i从1到s.length()
对所有的0<=j<i，更新如下，
dp[i]= dp[j] && (s[j+1,i] in dict)
即如果dp[j]为true，切s[j+1,i]在字典dict中，dp[i]更新为true；
1.3 代码
class Solution {
public:
bool wordBreak(string s, unordered_set<string> &dict) {
if (s.length() <= 0)
return true;
if (dict.size() <= 0)
return false;
vector<bool>dp(s.length() + 1, false);
dp[0] = true;
for (int i = 1; i < dp.size();i++)
{
for (int j = 0; j < i;j++)
{
if (dp[j] && dict.find(s.substr(j,i-j))!=dict.end())
{
dp[i] = true;
break;
}
}
}
return dp[dp.size() - 1];
}
};
题目2：Word Break II
2.1 问题描述
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given
s =“catsanddog”,
dict =[“cat”, “cats”, “and”, “sand”, “dog”].
A solution is[“cats and dog”, “cat sand dog”].
2.2 思路
参考链接：http://www.cnblogs.com/grandyang/p/4576240.html
思路：利用递归思想。首先看dict中是否有可以当s是头的字符串，如果有，则s为去掉头的子串，如cat可以当s的头，s变为"sanddog"，然后继续在dict中找，找到sand，dog；另一种开头，cats，s变为“anddog”，继续找，找到and，dog。最后返回这两种结果。
但是为了节省查找，保存中间过程中的查找结果，比如字符串查到“anddog”的时候，就把当前的字符串得到的结果保存到map中。以便下次遇到直接拿出来用。
2.3 代码
class Solution_1 {
//递归http://www.cnblogs.com/grandyang/p/4576240.html
public:
vector<string> wordBreak(string s, unordered_set<string> &dict) {
unordered_map<string, vector<string>>m;
vector<string>ss = helper(s, dict, m);
return ss;
}
vector<string> helper(string s, unordered_set<string>&dict, unordered_map<string, vector<string>>&m)
{
if (m.count(s))
return m[s];
if (s.length() == 0)
return { "" };
vector<string>res;
unordered_set<string>::iterator it;
for (it = dict.begin(); it != dict.end();it++)
{
if (s.substr(0,(*it).length())!=*it)
continue;
vector<string>rem = helper(s.substr((*it).length()), dict, m);
for (int i = 0; i < rem.size();i++)
{
res.push_back(*it + (rem[i].length() == 0 ? "" : " ") + rem[i]);
}
}
m[s] = res;
return res;
}
};
题目3：Island Perimeter
3.1 问题描述
https://leetcode.com/problems/island-perimeter/description/
You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn’t have “lakes” (water inside that isn’t connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don’t exceed 100. Determine the perimeter of the island.
Example:
[[0,1,0,0],
[1,1,1,0],
[0,1,0,0],
[1,1,0,0]]
Answer: 16
3.2 思路
当判断一块格子的周长是否能当做岛屿的周长时，可以分上下左右四条边分别判断：
加边的条件是：只有边是网格边界或者是其临近的网格不是1时，这条边才加进来。
3.3 代码
class Solution {
public:
int islandPerimeter(vector<vector<int>>& grid) {
if (grid.size() == 0 || grid[0].size() == 0)
return 0;
int plong = 0;
for (int i = 0; i < grid.size();i++)
{
for (int j = 0; j < grid[0].size();j++)
{
if (grid[i][j]==0)
continue;
if (j == 0 || grid[i][j - 1] == 0)
plong++;
if (j == grid[0].size() - 1 || grid[i][j + 1] == 0)
plong++;
if (i == 0 || grid[i - 1][j] == 0)
plong++;
if (i == grid.size() - 1 || grid[i + 1][j] == 0)
plong++;
}
}
return plong;
}
};
题目4：Number of Islands
4.1 问题描述
https://leetcode.com/problems/number-of-islands/description/
Given a 2d grid map of '1’s (land) and '0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input:
11110
11010
11000
00000
Output: 1
Example 2:
Input:
11000
11000
00100
00011
Output: 3
4.2 思路
遍历数组
如果为1，则直接nums++；然后修改该点以及其领域都置为0；
修改邻域为递归方式；
4.3 代码
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if (grid.size() <= 0 || grid[0].size() <= 0)
return 0;
int nums = 0;
for (int i = 0; i < grid.size(); i++)
{
for (int j = 0; j < grid[0].size(); j++)
{
if (grid[i][j] == '1')
{
fix_grid(grid, i, j);
nums++;
}
}
}
return nums;
}
void fix_grid(vector<vector<char>>&grid, int x, int y)
{
if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size())
return;
if (grid[x][y] == '0')
return;
grid[x][y] = '0';
fix_grid(grid, x - 1, y);
fix_grid(grid, x + 1, y);
fix_grid(grid, x, y - 1);
fix_grid(grid, x, y + 1);
}
};
题目5：Max Area of Island
5.1 问题描述
https://leetcode.com/problems/max-area-of-island/
Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)
Example 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Example 2:
[[0,0,0,0,0,0,0,0]]
Given the above grid, return 0.
Note: The length of each dimension in the given grid does not exceed 50.
5.2 思路
在number of island的基础上，加一个计数器，计算面积；
5.3 代码
class Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
if (grid.size() <= 0 || grid[0].size() <= 0)
return 0;
int max_area = 0;
for (int i = 0; i < grid.size();i++)
{
for (int j = 0; j < grid[0].size(); j++)
{
if (grid[i][j] == 1)
{
int temp_area = 0;
fix_grid(grid, temp_area, i, j);
max_area = max_area < temp_area ? temp_area : max_area;
}
}
}
return max_area;
}
void fix_grid(vector<vector<int>>&grid, int &area, int x, int y)
{
if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size())
return;
if (grid[x][y] == 0)
return;
area++;
grid[x][y] = 0;
fix_grid(grid, area, x - 1, y);
fix_grid(grid, area, x + 1, y);
fix_grid(grid, area, x, y - 1);
fix_grid(grid, area, x, y + 1);
}
};
题目6：Number of Distinct Islands
6.1 问题描述
https://leetcode.com/problems/number-of-distinct-islands
Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
Count the number of distinct islands. An island is considered to be the same as another if and only if one island can be translated (and not rotated or reflected) to equal the other.
Example 1:
11000
11000
00011
00011
Given the above grid map, return 1.
Example 2:
11011
10000
00001
11011
Given the above grid map, return 3.
Notice that:
11
1
and
1
11
are considered different island shapes, because we do not consider reflection / rotation.
Note: The length of each dimension in the given grid does not exceed 50.
6.2 思路
同样的遍历套路，不过保存每个岛的每个节点相对于左上角节点的相对坐标位置。
然后放入set中，最后set的大小就是岛的个数。
6.3 代码
class Solution {
public:
int numDistinctIslands(vector<vector<int>>& grid) {
if (grid.size() <= 0 || grid[0].size() <= 0)
return 0;
set<vector<int>>islands;
for (int i = 0; i < grid.size();i++)
{
for (int j = 0; j < grid[0].size();j++)
{
if (grid[i][j]==0)
continue;
vector<int>island;
fix_grid(grid, island, i, j, i, j);
islands.insert(island);
}
}
return islands.size();
}
void fix_grid(vector<vector<int>>&grid, vector<int>&island, int x, int y, int ex, int ey)
{
if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size())
return;
if (grid[x][y] == 0)
return;
grid[x][y] = 0;
island.push_back(ex - x);
island.push_back(ey - y);
fix_grid(grid, island, x - 1, y, ex, ey);
fix_grid(grid, island, x + 1, y, ex, ey);
fix_grid(grid, island, x, y - 1, ex, ey);
fix_grid(grid, island, x, y + 1, ex, ey);
}
};
题目7：House Robber
7.1 问题描述
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 2:
Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.
7.2 思路
下面代码给出了三种方法，其中方法一和方法二思路是相同的。
7.3.1 思路一
维护一个size为n+1的数组，f[i]表示抢前i户人家最高钱。
其中，f[0]=0，f[1]=a[0]
f(n)=max{f(n-1), f(n-2)+a[i]}
7.3.2 思路二
思路等同于一，但是空间复杂度减小。不需要维护一个数组，只需要维护三个变量，分别记录f(n)、f(n-1)、f(n-2)就可以。其中初始化时，
f(n-2)=0
f(n-1)=a[0]
f(n)=a[0]
7.3.3 思路三
维护两个变量，a和b，按照奇偶来更新a，b，
a记录抢偶的，b记录抢奇的，
更新方式：
if (i % 2 == 0)
a = (a + nums[i]) > b ? (a + nums[i]) : b;
else
b = (b + nums[i]) > a ? (b + nums[i]) : a;
7.3 代码
class Solution {
public:
int rob(vector<int>& nums) {
if (nums.size() == 0)
return 0;
if (nums.size() == 1)
return nums[0];
vector<int>a(nums.size() + 1, 0);
a[1] = nums[0];
for (int i = 2; i<a.size();i++)
{
int temp = a[i - 2] + nums[i-1];
a[i] = a[i - 1] > temp ? a[i - 1] : temp;
}
return a[a.size() - 1];
}
};
class Solution1 {
public:
int rob(vector<int>& nums) {
if (nums.size() == 0)
return 0;
if (nums.size() == 1)
return nums[0];
int f_n_2 = 0;
int f_n_1 = nums[0];
int f_n_0;
for (int i = 1; i < nums.size();i++)
{
int temp = f_n_2 + nums[i];
f_n_0 = f_n_1>temp ? f_n_1 : temp;
f_n_2 = f_n_1;
f_n_1 = f_n_0;
}
return f_n_0;
}
};
class Solution2 {
public:
int rob(vector<int>& nums) {
if (nums.size() == 0)
return 0;
if (nums.size() == 1)
return nums[0];
int a = 0, b = 0;
for (int i = 0; i < nums.size();i++)
{
if (i % 2 == 0)
a = (a + nums[i]) > b ? (a + nums[i]) : b;
else
b = (b + nums[i]) > a ? (b + nums[i]) : a;
}
return a > b ? a : b;
}
};
题目8：House Robber II
8.1 问题描述
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
because they are adjacent houses.
Example 2:
Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
8.2 思路
首尾相连。
8.2.1 思路一
延续上一题中思路二，但是不同的是分情况讨论，
即第一户人家抢，则最后一户不抢；
第一户人家不抢，最后一户爱抢不抢；
最后返回这两种情况的大数就可以。
8.2.2 思路二
等同于思路一，但是不同的是对代码进行封装。
思路一种两种情况说到底就是上下限的不同。
第一户人家抢，就是从1到（n-1）户人家中找最大值；
第一户人家不抢，就是从2到n户人家中找最大值；
所以完全可以用上一题的代码，直接对函数进行封装，标明数组上下界就可以。
8.3 代码
class Solution {
public:
int rob(vector<int>& nums) {
if (nums.size() == 0)
return 0;
if (nums.size() == 1)
return nums[0];
if (nums.size() == 2)
return nums[0] > nums[1] ? nums[0] : nums[1];
//抢
int f_n_2 = nums[0];
int f_n_1 = nums[0];
int f_n_0 = nums[0];
for (int i = 2; i < nums.size()-1; i++)
{
int temp = f_n_2 + nums[i];
f_n_0 = f_n_1>temp ? f_n_1 : temp;
f_n_2 = f_n_1;
f_n_1 = f_n_0;
}
int max_temp = f_n_0;
//不抢
f_n_2 = 0;
f_n_1 = nums[1];
for (int i = 2; i < nums.size(); i++)
{
int temp = f_n_2 + nums[i];
f_n_0 = f_n_1>temp ? f_n_1 : temp;
f_n_2 = f_n_1;
f_n_1 = f_n_0;
}
return (f_n_0 > max_temp ? f_n_0 : max_temp);
}
};
class Solution1 {
public:
int rob(vector<int>& nums) {
if (nums.size() == 0)
return 0;
if (nums.size() == 1)
return nums[0];
int temp1 = temp_rob(nums, 0, nums.size() - 1);
int temp2 = temp_rob(nums, 1, nums.size());
return temp1 > temp2 ? temp1 : temp2;
}
int temp_rob(vector<int>&nums, int start, int end)
{
if (nums.size() == 0)
return 0;
if (nums.size() == 1)
return nums[start];
int f_n_2 = 0;
int f_n_1 = nums[start];
int f_n_0 = f_n_1;
for (int i = start + 1; i < end; i++)
{
int temp = f_n_2 + nums[i];
f_n_0 = f_n_1>temp ? f_n_1 : temp;
f_n_2 = f_n_1;
f_n_1 = f_n_0;
}
return f_n_0;
}
};
题目9：House Robber III
9.1 问题描述
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.
Determine the maximum amount of money the thief can rob tonight without alerting the police.
Example 1:
Input: [3,2,3,null,3,null,1]
3
/ \
2 3
\ \
3 1
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
Input: [3,4,5,1,3,null,1]
3
/ \
4 5
/ \ \
1 3 1
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.
9.2 思路
9.2.1 思路一
首先，超时。
递归：对于一个节点，
1、如果其左孩子存在，则递归调用，返回不包含左孩子本身的值A，即返回左孩子的左孩子+左孩子的右孩子；
2、如果其右孩子存在，则递归调用，返回不包含右孩子本身的值B，即返回右孩子的左孩子+右孩子的右孩子；
3、计算此节点+A+B；
4、递归调用左孩子，返回包含左孩子本身的值C；
5、递归调用右孩子，返回包含右孩子本身的值D；
6、计算C+D；
7、返回步骤3与步骤6中的大数。
当然，进一步要改进，设置map，存放计算过程中每个节点的最大值，即再次递归调用时不必计算，直接查找map；
但是仍然超时。
9.2.2 思路二
仍然采用递归，设置一个长度为2的数组res；
res[0]：不包含当前节点值的最大值；
res[1]：包含当前节点值的最大值；
这样，当遍历到某个节点时，
1、递归左孩子，返回左孩子的res数组，记为left；
2、递归右孩子，返回右孩子的res数组，记为right；
3、则res[0]=max{left[0], left[1]} + max{right[0], right[1]};
4、res[1]=left[0] + right[0]；
5、返回max(res[0], res[1])。
9.3 代码
class Solution {
public:
//超时
int rob(TreeNode* root) {
if (root == NULL)
return 0;
map<TreeNode*, int>m;
return dfs(root, m);
}
int dfs(TreeNode *root, map<TreeNode*, int>m)
{
if (root == NULL)
return 0;
if (m.count(root))
return m[root];
int sum = 0;
if (root->left)
sum += (dfs(root->left->left, m) + dfs(root->left->right, m));
if (root->right)
sum += (dfs(root->right->left, m) + dfs(root->right->right, m));
sum = max(root->val + sum, dfs(root->left, m) + dfs(root->right, m));
m[root] = sum;
return sum;
}
};
class Solution1 {
public:
int rob(TreeNode* root) {
if (root == NULL)
return 0;
vector<int>res = dfs(root);
return max(res[0], res[1]);
}
vector<int> dfs(TreeNode* root)
{
if (root == NULL)
return vector<int>(2, 0);
vector<int>left = dfs(root->left);
vector<int>right = dfs(root->right);
vector<int>res(2, 0);
res[0] = max(left[0], left[1]) + max(right[0], right[1]);
res[1] = left[0] + right[0] + root->val;
return res;
}
};
题目10：robber v
10.1 问题描述
在第八题的基础加上一个条件：要求每户抢的钱要越来越大；
10.2 思路
f(n)=max{f(n-1), f(n-2)+a[i]},
但是除了1,2户，每次在计算 f(n-2)+a[i]时，加一个判断，除非a[i]>a[i-2]，才进行更新temp= f(n-2)+a[i]，否则，temp=0，即，f(n)=max{f(n-1),temp}=f(n-1)；
10.3 代码
int temp_rob(vector<int>&nums, int start, int end)
{
if (nums.size() == 0)
return 0;
if (nums.size() == 1)
return nums[start];
int f_n_2 = 0;
int f_n_1 = nums[start];
int f_n_0 = f_n_1;
for (int i = start + 1; i < end; i++)
{
int temp = 0;
if (i == start + 1)
temp = f_n_2 + nums[i];
if (i > start + 1 && nums[i]>nums[i-2])
temp = f_n_2 + nums[i];
f_n_0 = f_n_1 > temp ? f_n_1 : temp;
f_n_2 = f_n_1;
f_n_1 = f_n_0;
}
return f_n_0;
}
int rob(vector<int>& nums) {
if (nums.size() == 0)
return 0;
if (nums.size() == 1)
return nums[0];
int temp1 = temp_rob(nums, 0, nums.size() - 1);
int temp2 = temp_rob(nums, 1, nums.size());
return temp1 > temp2 ? temp1 : temp2;
}
题目11：Permutations
11.1 问题描述
Given a collection of distinct integers, return all possible permutations.
Example:
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
11.2 思路
全排列问题；
从第一位开始，与后面每一位进行交换，得到新的数组，然后push到结果中；
当然每次交换完成后，要再交换回来，用来做下次交换。
比如，a={1,2,3}
1与1交换，得到123，然后23重复这个过程，得到123, 得到132；
重新变回123，1与2交换，得到213，然后13再重复这个过程，得到213,231；
重新变回123，1再与3交换；得到321，然后21再重复这个过程，得到321,312；
11.3 代码
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums)
{
if (nums.size() == 0)
return { {} };
if (nums.size() == 1)
return{ nums };
vector<vector<int>>all;
get_one(nums, 0, all);
return all;
}
void get_one(vector<int>&nums, int start, vector<vector<int>>&all)
{
if (start >= nums.size())
all.push_back(nums);
for (int i = start; i < nums.size();i++)
{
swap(nums[start], nums[i]);
get_one(nums, start + 1, all);
swap(nums[start], nums[i]);
}
}
void swap(int &x, int &y)
{
int temp = x;
x = y;
y = temp;
}
};
题目12：Permutations II
12.1 问题描述
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example:
Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
12.2 思路
思路类似上一题，不过这次数组有存在的重复元素；
一开始的思路时，再交换的时候做一个判断，除了本身交换外，其他交换如果相等则不进行交换；
然后发现这个方法不行，还是会有重复排列；
后来将存放结果的vector改用set，这样重复的排列就不会在insert进去。
为了减少递归次数，仍然可以将刚开始的思路中的那个判断加上去。
12.3 代码
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
if (nums.size() == 0)
return{ {} };
if (nums.size() == 1)
return{ nums };
set<vector<int>>all;
get_one(nums, 0, all);
vector<vector<int>>new_all(all.begin(), all.end());
return new_all;
}
void get_one(vector<int>&nums, int start, set<vector<int>>&all)
{
if (start >= nums.size())
all.insert(nums);
for (int i = start; i < nums.size(); i++)
{
//这个判断加与不加都可以，因为用了set了
//if (start != i && nums[start] == nums[i])
//continue;
swap(nums[start], nums[i]);
get_one(nums, start + 1, all);
swap(nums[start], nums[i]);
}
}
void swap(int &x, int &y)
{
int temp = x;
x = y;
y = temp;
}
};
题目13：Permutation Sequence
13.1 问题描述
The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order, we get the following sequence for n = 3:
“123”
“132”
“213”
“231”
“312”
“321”
Given n and k, return the kth permutation sequence.
Note:
Given n will be between 1 and 9 inclusive.
Given k will be between 1 and n! inclusive.
Example 1:
Input: n = 3, k = 3
Output: "213"
Example 2:
Input: n = 4, k = 9
Output: "2314"
13.2 思路
寻找1-n之间所有的排列组合，第k个排列组合是什么；
如果先求出全排列，再返回第k个，则过于复杂了。
所以直接的方法是直接放回第k个的排列组合。
那这个排列组合是如何产生的呢？
我们可以看一个例子，n=4，k=15；
1234 0
1243 1
1324 2
1342 3
1423 4
1432 5
2134 6
2143 7
2314 8
2341 9
2413 10
2431 11
3124 12
3142 13
3214 14
3241 15
3412 16
3421 17
4123 18
4132 19
4213 20
4231 21
4312 22
4321 23
可以发现这样一个规律，
在第一位上，每个数字都出现了6次，即3！
确定第一位后，在第二位上，每个数字各出现了2次，即2！
确定第一二位后，在第三位上，每个数字各出现了1次，即1！
确定第一二三位后，在第四位上，每个数字各出现了1次，即0！
所以，第15个排列，即下标14时，
14/6=2，第一位是2；
14%6=2，2/2=1，第二位是3；
2%2=0，0/1=0，第三位是1；
0%1=0，0/1=0，第四位是4；
最后结果是3214，可以看到与上面全排列中的14结果相同。
由于题目规定了n属于1-9，所以可以提前存放s=123456789；
然后至于每一位数字各出现几次，可以提前计算好放在数组中；
最后，在每次确定一位后，将其从s中移出。
13.3 代码
class Solution {
public:
string getPermutation(int n, int k) {
if (n == 0)
return "";
string s = "123456789";
vector<int>f(n, 1);
for (int i = 1; i <n;i++)
{
f[i] = i*f[i - 1];
}
string ks = "";
k = k - 1;
for (int i = n; i > 0;i--)
{
int num = k / f[i - 1];
k = k % f[i - 1];
ks = ks + s[num];
s.erase(num, 1);
}
return ks;
}
};
题目14：Permutation in String
14.1 问题描述
Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string’s permutations is the substring of the second string.
Example 1:
Input:s1 = "ab" s2 = "eidbaooo"
Output:True
Explanation: s2 contains one permutation of s1 ("ba").
Example 2:
Input:s1= "ab" s2 = "eidboaoo"
Output: False
Note:
The input strings only contain lower case letters.
The length of both given strings is in range [1, 10,000].
14.2 思路
求s1字符串的任意一个排列组合是否是s2的子串。
当然也不是直接就求出s1的全排列，然后遍历s2的子串，是否包含全排列中一个。
设置一个滑动范围，长度是s1的长度；
设置两个数组m1，m2，用来存放在滑动范围中，s1、s2中每个字符出现的个数。
第一次在s1,s2上同时遍历s1的长度，得到数组m1,m2，如果两者相等，说明是true；
然后重新遍历，在s2上，从上一次遍历的位置开始，每次减去m2中滑动窗口头部字符的个数 ，新增一个字符，即s2新遍历的位置。
然后再次判断m1与m2是否相等，相等则为true。
如果s2遍历完，函数都未返回，则返回false。
14.3 代码
class Solution {
public:
bool checkInclusion(string s1, string s2) {
if (s1.length() == 0)
return true;
if(s2.length()<s1.length())
return false;
int n1 = s1.length();
int n2 = s2.length();
vector<int>m1(26, 0);
vector<int>m2(26, 0);
for (int i = 0; i < n1; i++)
{
m1[s1[i] - 'a']++;
m2[s2[i] - 'a']++;
}
if (m1 == m2)
return true;
for (int i = n1; i < n2;i++)
{
m2[s2[i] - 'a']++;
m2[s2[i - n1] - 'a']--;
if (m1 == m2)
return true;
}
return false;
}
};
题目15：Two Sum
15.1 问题描述
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
15.2 思路
15.2.1 思路一
暴力方法，两层遍历即可；
15.2.2 思路二
用一个map记录数组中每个数字的下标；
当遍历数组时，如果target-nums[i]在map中，并且这个值的下标不是i，说明找到这个数，返回即可；
进一步精炼代码，即为第三个代码；
不需要第一次遍历数组，记录每个元素下标。而是只采取一次遍历，在遍历的时候，如果target-nums[i]在map中，直接返回；否则在map中记录nums[i]。
15.3 代码
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target)
{
if (nums.size() < 2)
return{ -1, -1 };
vector<int>a(2);
for (int i = 0; i < nums.size();i++)
{
a[0] = i;
for (int j = i + 1; j < nums.size();j++)
{
if (target - nums[i] == nums[j])
{
a[1] = j;
return a;
}
}
}
}
};
class Solution1 {
public:
vector<int> twoSum(vector<int>& nums, int target) {
if (nums.size() < 2)
return{ -1, -1 };
vector<int>a(2);
map<int, int>m;
for (int i = 0; i < nums.size(); i++)
m[nums[i]] = i;
for (int i = 0; i < nums.size(); i++)
{
int other = target - nums[i];
if (m.count(other) != 0 && m[other] != i)
{
a[0] = m[other];
a[1] = i;
return a;
}
}
}
};
class Solution2 {
public:
vector<int> twoSum(vector<int>& nums, int target)
{
if (nums.size() < 2)
return{ -1, -1 };
map<int, int>m;
for (int i = 0; i < nums.size(); i++)
{
int other = target - nums[i];
if (m.count(other))
return{ m[other], i};
m[nums[i]] = i;
}
}
};
题目16：Longest Repeating Character Replacement
16.1 问题描述
Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations.
Note:
Both the string’s length and k will not exceed 104.
Example 1:
Input:
s = "ABAB", k = 2
Output:
4
Explanation:
Replace the two 'A's with two 'B's or vice versa.
Example 2:
Input:
s = "AABABBA", k = 1
Output:
4
Explanation:
Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.
16.2 思路
其实就是求一个子串，其长度-子串中出先次数最多的字符的个数>=k即可。这个子串的长度就是答案。
维持一个滑动窗口，记录窗口的起始位置start，初始值为0；
设置counts数组，用来记录每个字符的个数；
设置一个maxlen，用来记录窗口内出现最多字符的个数；
设置len，用来记录最大子串，根据窗口的大小进行更新；
16.3 代码
class Solution {
public:
int characterReplacement(string s, int k) {
if (s.length() <= k)
return s.length();
vector<int>count(26, 0);
int maxlen = 0;
int start = 0;
int len = 0;
for (int i = 0; i < s.length();i++)
{
maxlen = max(maxlen, ++count[s[i] - 'A']);
while (i-start+1-maxlen>k)
{
count[s[start] - 'A']--;
start++;
}
len = max(len, i - start + 1);
}
return len;
}
};
题目17：Best Time to Buy and Sell Stock
17.1 问题描述
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
17.2 思路
只进行一次交易，其实就是在遍历中找最小值，
用当前值减去最小值，如果大于最大交易值，就更新最大交易值；
17.3 代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
int pmin = INT_MAX;
int value = 0;
if (prices.size() < 1)
return 0;
for (int i = 0; i < prices.size();i++)
{
pmin = min(pmin, prices[i]);
value = max(value, prices[i] - pmin);
}
return value;
}
};
题目18：Best Time to Buy and Sell Stock II
18.1 问题描述
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Example 1:
Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Example 2:
Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
18.2 思路
18.2.1 思路一
记录一个pmax和pmin，pmax表示在一路大于pmin的股票价格中最高的价格；
pmin记录可交易的最小价格；
如果符合prices[i]>pmin && prices[i]>pmax，则更新pmax = prices[i];
否则，就计算交易值value += max(0, pmax - pmin);
并充值pmin，pmax；pmin = prices[i];pmax = prices[i];
18.2.2 思路二
遍历时，只要当前价格比前一天价格高，就进行一次交易，
如果后一天还是比当前价格高，也会进行一次交易，
这是因为题目没有限制交易次数，可以当天卖出，再当天买进；
思路一和思路二的不同是，思路二只有有利润，就买进卖出；
思路一是一次交易有最大利润，才买进卖出，然后计算多次交易的最大利润之和。
18.3 代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() < 2)
return 0;
int value = 0;
int pmin = prices[0];
int pmax = prices[0];
for (int i = 1; i < prices.size();i++)
{
if (prices[i]>pmin && prices[i]>pmax)
{
pmax = prices[i];
}
else
{
value += max(0, pmax - pmin);
pmin = prices[i];
pmax = prices[i];
}
}
value += max(0, pmax - pmin);
return value;
}
};
class Solution1 {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() < 2)
return 0;
int value = 0;
for (int i = 1; i < prices.size();i++)
{
if (prices[i]>prices[i - 1])
value += (prices[i] - prices[i - 1]);
}
return value;
}
}；
题目19：Best Time to Buy and Sell Stock III
19.1 问题描述
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Example 1:
Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
Example 2:
Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
19.2 思路
19.3 代码
题目20：Best Time to Buy and Sell Stock IV
20.1 问题描述
Say you have an array for which the ith 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:
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:
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.
20.2 思路
20.3 代码
题目21：无重复字符的最大子串
21.1 问题描述
找出一个字符串中，没有重复字符的最长的一个子串。返回其长度。
如“abccdefa”，结果为“cdefa”
21.2 思路
设置一个字符数组，记录每个字符出现在字符串s中的位置。
维持一个滑动窗口，遍历字符串，如果位置数组中存在当前字符，则窗口开始位置调整到与当前字符相同的字符位置的后一个位置。记录窗口的大小，并更新最大子串长度，即最大的窗口。
21.3 代码
int max_len(string s)
{
if (s.length() < 2)
return s.length();
vector<int>index(256, -1);
int len = 0;
int left = 0;
for (int i = 0; i < s.length();i++)
{
if (index[s[i]] == -1 || index[s[i]]<left)
{
len = max(len, i - left + 1);
}
else
{
left = index[s[i]] + 1;
}
index[s[i]] = i;
}
return len;
}
题目22：IP数量
22.1 问题描述
给一个字符串，表示ip地址，但是字符"."被去掉了，求出这个字符串可能存在的合法ip种类数。
如8888，合法ip只有"88.88"，所以返回1；
22.2 思路
利用递归。
首先ip必须是四位地址。设置n记录得到了几位Ip。
然后遍历组成每位的数字位数，即1，2，3，因为最大为255，不会超过3位。
22.3 代码
void haha(string s, int n, int &count)
{
if (n == 4)
{
if (s.size() == 0)
count++;
return;
}
for (int i = 1; i < 4;i++)
{
if (s.size()<i)
break;
stringstream stream;
int num;
stream << s.substr(0, i);
stream >> num;
if (num>255 || to_string(num).length()!=i)
continue;
haha(s.substr(i), n + 1, count);
}
}
题目23：UTF-8 Validation
23.1 问题描述
A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:
For 1-byte character, the first bit is a 0, followed by its unicode code.
For n-bytes character, the first n-bits are all one’s, the n+1 bit is 0, followed by n-1 bytes with most significant 2 bits being 10.
This is how the UTF-8 encoding would work:
Char. number range | UTF-8 octet sequence
(hexadecimal) | (binary)
--------------------±--------------------------------------------
0000 0000-0000 007F | 0xxxxxxx
0000 0080-0000 07FF | 110xxxxx 10xxxxxx
0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
Given an array of integers representing the data, return whether it is a valid utf-8 encoding.
Note:
The input is an array of integers. Only the least significant 8 bits of each integer is used to store the data. This means each integer represents only 1 byte of data.
Example 1:
data = [197, 130, 1], which represents the octet sequence: 11000101 10000010 00000001.
Return true.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.
Example 2:
data = [235, 140, 4], which represented the octet sequence: 11101011 10001100 00000100.
Return false.
The first 3 bits are all one's and the 4th bit is 0 means it is a 3-bytes character.
The next byte is a continuation byte which starts with 10 and that's correct.
But the second continuation byte does not start with 10, so it is invalid.
23.2 思路
即存在四种情况，
1、data[i] < 128，表示一个数，有效；
2、data[i] >= 192 && data[i] <= 223，表示后面跟着1个数，且这个数data[i + 1] >= 128 && data[i + 1] < 192；
3、data[i] >= 224 && data[i] <= 239，表示后面跟着2个数，且这两个数都符合data[i + 1] >= 128 && data[i + 1] < 192；
4、data[i] >= 240 && data[i] <= 247，表示后面跟着3个数，且这三个数都符合data[i + 1] >= 128 && data[i + 1] < 192；
5、其他情况，直接返回FALSE
23.3 代码
class Solution {
public:
bool validUtf8(vector<int>& data) {
if (data.size() == 1)
return data[0] < 128;
int i = 0;
while (i < data.size())
{
if (data[i] < 128)
i++;
else if (data[i] >= 192 && data[i] <= 223)
{
if (i+1<data.size() && data[i + 1] >= 128 && data[i + 1] < 192)
i = i + 2;
else
return false;
}
else if (data[i] >= 224 && data[i] <= 239)
{
if (i + 2<data.size() && data[i + 1] >= 128 && data[i + 1] < 192 && data[i + 2] >= 128 && data[i + 2] < 192)
i = i + 3;
else
return false;
}
else if (data[i] >= 240 && data[i] <= 247)
{
if (i + 3 < data.size() && data[i + 1] >= 128 && data[i + 1] < 192 && data[i + 2] >= 128 && data[i + 2] < 192 && data[i + 3] >= 128 && data[i + 3] < 192)
i = i + 4;
else
return false;
}
else
{
return false;
}
}
return true;
}
};
题目24：微博大V
24.1 问题描述
有关系A,B，表示A关注了B，关系具有传递性，如果AB,BC，则A也关注了C。
给定一组关系，如果存在某个人被其他所有人关注，则这个人是微博大V。
请找出所有微博大V的数量。
24.2 思路
设置结构体关系，有两个属性，粉丝和微博大V；
对每一个关系，进行find和union操作。
find：如果该人的根节点是-1，说明他自己关注了自己，返回自己；如果不是1，继续find，并更新他的根节点；
union：找到粉丝的根节点，微博大V的根节点，如果两个人关注的是同一个人，则不进行操作。否则，将粉丝的根节点置为微博大V的根节点。
设置count数组，表示每个人的粉丝数。查找每个人的根节点，如果是-1，表示只有自己，count[自己]++；否则，该人的根节点count++，表示粉丝数增加一个。
然后遍历count数组，如果存在粉丝数等于n，表示这个人是真微博大V。res++。
24.3 代码
struct relation
{
int fans;
int hongren;
};
int find(vector<int>& uni, int aim)
{
if (uni[aim] == -1)
return aim;
else
return uni[aim] = find(uni, uni[aim]);
}
void myUnion(vector<int> &uni, int a, int b)
{
auto alike = find(uni, a);
auto blike = find(uni, b);
if (alike == blike)
return;
uni[a] = blike;
return;
}
int douyinhongren(vector<relation> vRelation, int n, int m)
{
vector<int> unionSet(n + 1, -1);
for (int i = 0; i < m; i++)
{
myUnion(unionSet, vRelation[i].fans, vRelation[i].hongren);
}
vector<int> count(n + 1);
for (int i = 0; i < n; i++)
{
auto root = find(unionSet, i + 1);
if (root != -1)
count[root]++;
else
count[i + 1]++;
}
int res = 0;
for (int i = 0; i < n; i++)
{
if (count[i + 1] == n)
res++;
}
return res;
}
int main()
{
int n, m;
cin >> n;
cin >> m;
vector<relation> vRelation(m);
vector<int> unionSet(n + 1, -1);
for (int i = 0; i < m; i++)
{
relation temp;
cin >> temp.fans;
cin >> temp.hongren;
vRelation[i] = temp;
}
cout << douyinhongren(vRelation, n, m) << endl;
system("pause");
return 0;
}
题目25：合并区间
25.1 问题描述
给定几组区间，可能存在重叠。将区间进行合并。
如：
1,10；32,45；
78,94；5,16；
80,100；200,220；16,32；
合并后为：
1,45；78,100；200,220；
25.2 思路
分别将每个区间的左边界排序、右边界排序；
然后同时遍历这两个边界。i=0；j=0；
如果i到了末尾，或者左边界的下一个大于当前的右边界first[i + 1] > last[i]，说明可以合并，first[j]，last[i]合并为大区间；更新j=i+1。
25.3 代码
vector<int> get_groups(vector<int>a)
{
vector<int>answer;
if (a.size() == 0)
return answer;
if (a.size() == 2)
return a;
vector<int>first;
vector<int>last;
for (int i = 0; i < a.size()-1;i=i+2)
{
first.push_back(a[i]);
last.push_back(a[i + 1]);
}
sort(first.begin(), first.end());
sort(last.begin(), last.end());
int n = first.size();
for (int i = 0, j = 0; i < n; i++)
{
if (i == n - 1 || first[i + 1] > last[i])
{
answer.push_back(first[j]);
answer.push_back(last[i]);
j = i + 1;
}
}
return answer;
}
题目26：
26.1 问题描述
26.2 思路
26.3 代码
上一篇： 阿里云大学：百度贴吧自动签到实现
下一篇： jquary