有营养的算法笔记五
合法的路径条数
1.题目描述
来自美团
给定一个无向图
从任何一个点x出发，比如有一条路径 : x->a->b->c->y
这条路径上有5个点并且5个点都不一样的话，我们说(x, a, b, c, y)是一条合法路径。这条合法路径的代表，就是x, a, b, c, y所组成的集合，我们叫做代表集合如果从b到y，还有一条路径叫(b, a, c, x, y)，那么(x, a, b, c, y)和(b, a, c, x, y)是同一个代表集合，返回这个无向图中所有合法路径的代表集合数量
题目给定点的数量n <= 15，边的数量m <= 60。所有的点编号都是从0~n - 1的
2.解题思路
首先我们看到这个题目的数据范围点的数量只有15个。这是本题的突破口我们可以使用一个整形来表示某个节点有没有被访问过，依次尝试从每个节点作为开头的情况下合法的路径。而这个合法的路径我们可以使用整型的32个比特位来表示，当我们发现已经有5个合法的节点了。我们将其加入到哈西表当中，这样就算哈西表能过给我们自动的去除重复的元素。最后我们返回最终哈西表当中的元素的个数就可以了。是不是很简单下面我们直接上代码
3.对应代码
void dfs(int status, int len, int cur, unordered_set<int>& cnt, vector<vector<int>>& grap)
{
//说明之前没有来过
if (((1 << cur) & status) == 0)
{
len++;
status |= (1 << cur);//将这一位标记为1
if (len == 5)
{
cnt.insert(status);
return;
}
//遍历他的孩子节点
for (auto next : grap[cur])
{
dfs(status, len, next, cnt, grap);
}
}
}
int validPathSets(vector<vector<int>>& graph) {
//由于给定点的数量只有15个所有我们可以用一个整型来表示某个节点是否来到过
int N = graph.size();
//自动去除
unordered_set<int>hashSet;
//每个点都开始尝试遍历可能存在的路径
for (int from = 0; from < N; from++) {
dfs(0, 0, from, hashSet, graph);
}
return hashSet.size();
//自动去重
}
int main()
{
vector<vector<int>>graph{
{1, 2, 3, 4, 5},
{0, 2, 3, 4, 5},
{0, 1, 3, 4, 5},
{0, 1, 2, 4, 5},
{0, 1, 2, 3, 5},
{0, 1, 2, 3, 4} };
//给定的是一个无向图
cout << validPathSets(graph) << endl;
return 0;
}
合并地区
1.题目描述
class AreaResource {
String area; // area表示的是地区全路径,最多可能有6级，比如： 中国,四川,成都 或者 中国,浙江,杭州
String spliter; // 比如：逗号 -> ,
long count; // 表示地区的门店数量
}
现在需要把 List 进行转换，需要做到同级的地域能合并
比如：area为中国, 四川, 成都 ，有10个门店；
area为中国, 浙江, 杭州，有25个门店；area为中国, 浙江, 义乌，有22个门店
最终生成的JSON字符串为：{ “中国”:{ “四川”:{“成都”:10}},“浙江” : {“义乌”:22,“杭州” : 25} }
}
请实现下面的方法 public String mergeCount(List areas)
2.解题思路
本题了是经典的前缀树的应用。我们首先先将area切分好将其放入到前缀树当中去。但是请注意门店的数量我们只放到最后一个节点上，我们就以上面的为例将所有的节点加入到前缀树当中，如下图所示：
我们将节点加入到前缀树当中之后我们就可以开始进行深度优先遍历如果是这条路不为空那么我们将其加入到这个到答案中然后了在递归遍历其子节点即可。下面废话不多说我们一起来看看这个代码如何来写
//来自北京北明数科信息技术有限公司
//class AreaResource {
// String area; // area表示的是地区全路径,最多可能有6级，比如： 中国,四川,成都 或者 中国,浙江,杭州
// String spliter; // 比如：逗号 -> ,
// long count; // 表示地区的门店数量
//}
//现在需要把 List<AreaResource> 进行转换，需要做到同级的地域能合并
//比如：area为中国, 四川, 成都 ，有10个门店；
// area为中国, 浙江, 杭州，有25个门店；area为中国, 浙江, 义乌，有22个门店
//最终生成的JSON字符串为：{ "中国":{ "四川":{"成都":10}},"浙江" : {"义乌":22,"杭州" : 25} }
// }
//请实现下面的方法 public String mergeCount(List<AreaResource> areas)
#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
using namespace std;
class AreaResource
{
public:
AreaResource(string a,string s,long c)
:area(a),spliter(s),count(c)
{}
string area;
string spliter;
long count;
};
//前缀数加递归
class Soulution {
public:
struct TireNode
{
TireNode(string n, long long c = 0)
:name(n), cnt(c)
{}
unordered_map<string, TireNode*>next;
long long cnt;
string name;
string ToString()
{
string ans;
if (!name.empty())
{
ans = """ + name + """+":";
}
if (next.empty())
{
ans += to_string(cnt);
return ans;
}
ans += "{";
//遍历其孩子节点
for (auto child : next)
{
ans += child.second->ToString() + ",";
}
ans.pop_back();//删除末尾的空格
ans += "}";
return ans;
}
};
vector<string>Split(const string& str, const string sep)
{
vector<string>ans;
int N = str.size();
int start = 0;
while (start < N)
{
int pos = str.find(sep, start);
pos = (pos == -1 ? N : pos);
ans.push_back(move(str.substr(start, pos - start)));
start = pos + sep.size();
}
return ans;
}
string MerageCount(vector<AreaResource>& arr)
{
TireNode* root = new TireNode("");
for (auto& Area : arr)
{
vector<string>word = Split(Area.area,Area.spliter);
Add(root, word, 0, Area.count);
}
return root->ToString();
}
void Add(TireNode* root, vector<string>& word, int index,long long cnt)
{
if (index == word.size()) {
root->cnt += cnt;
return;
}
string& cur = word[index];
if (!root->next[cur])
{
root->next[cur] = new TireNode(cur);
}
Add(root->next[cur], word, index + 1, cnt);
}
};
int main()
{
Soulution a;
vector< AreaResource>arr = { {"中国,浙江,宁波", ",", 16},{"中国,四川,攀枝花", ",", 12},
{"中国,四川,成都", ",", 15},{"中国,浙江,义乌", ",", 22},{"中国,浙江,杭州", ",", 25}
,{"中国,浙江,杭州", ",", 50},{"中国,四川,成都", ",", 10} };
//string sep = ",";
//string word = "中国,浙江,宁波";
//vector<string>ans = a.Split(word, sep);
//for (int i = 0; i < ans.size(); i++) {
// cout << ans[i] << endl;
//}
cout << a.MerageCount(arr) << endl;
return 0;
}
钝角三角形的数量
1.题目描述
来自hulu
有一个以原点为圆心，半径为1的圆 在这个圆的圆周上，有一些点 因为所有的点都在圆周上，所以每个点可以有很简练的表达 比如：用0来表示一个圆周上的点，这个点就在(1,0)位置
比如：用6000来表示一个点，这个点是(1,0)点沿着圆周逆时针转60.00度之后所在的位置
比如：用18034来表示一个点，这个点是(1,0)点沿着圆周逆时针转180.34度之后所在的位置。 这样一来，所有的点都可以用[0, 36000)范围上的数字来表示， 那么任意三个点都可以组成一个三角形，返回能组成钝角三角形的数量
2.解题思路
首先我们需要知道这个钝角三角形，钝角三角形一定会以某个位置开头。下面我们来画一个图来解释一下
我们可以看到我们确定一个点然后通过圆心也就是直径那么在这条线范围内的任意两个点和a连成的三角形一定是钝角三角形。圆心所对应的角是直角三角形注意此时这个钝角三角形是以a作为开头的钝角三角形，所以我们只要看这个范围内点的个数有几个在利用排列组合就可以求出以a作为开头的钝角三角形的个数，同样的我们在求以b开头以d开头的情况下钝角三角形的数量就可以了。我们只需要一个L指针和R指针就可以实现了，并且这个R指针不需要回退，但是这也带来了一个问题但我们来到以f开头情况下钝角三角形的数量时，我们发现此时已经转了360度了角度在开始变小，此时R指针不回退好像就进行不下去了。但是我们可以这样搞一下假设a是10度它其实也是370度，我们可以将每个点加360度放到数组的末尾位置。这样我们可以玩下去了。下面我们来看看代码
3.对应代码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
/*来自hulu
有一个以原点为圆心，半径为1的圆
在这个圆的圆周上，有一些点
因为所有的点都在圆周上，所以每个点可以有很简练的表达
比如：用0来表示一个圆周上的点，这个点就在(1,0)位置
比如：用6000来表示一个点，这个点是(1,0)点沿着圆周逆时针转60.00度之后所在的位置
比如：用18034来表示一个点，这个点是(1,0)点沿着圆周逆时针转180.34度之后所在的位置
这样一来，所有的点都可以用[0, 36000)范围上的数字来表示
那么任意三个点都可以组成一个三角形，返回能组成钝角三角形的数量*/
class Solution
{
public:
//钝角三角形一定会以某个位置开头，穿过圆心划定一个范围看有几个点
//计算从某个点开始出发穿过圆心,看有几个点利用排列组合即可
long obtuseAngles(vector<int>& nums)
{
int N = nums.size();
sort(nums.begin(), nums.end());//先将度数进行排序
vector<int>enlarge(N << 1);//开两倍的空间用来存储每个值+360度
for (int i = 0; i < N; i++)
{
enlarge[i] = nums[i];
enlarge[i + N] = nums[i] + 36000;//用来处理吧边界防止变得不对了绕过360度,解决回过去的问题
}
int M = enlarge.size();
int L = 0;
int R = 0;
//计算每个位置作为开头的情况下钝角三角形的数量
int ans = 0;
while (L < N)
{
while (R<M&&enlarge[R] - enlarge[L] < 18000)
{
R++;
}
ans += GetNum(R - L - 1);//计算在(L,R)范围内有几个点
L++;//尝试下一个点开头的情况下钝角三角形的数量
}
return ans;
}
int GetNum(int len)//排列组合计算钝角三角形的个数
{
return len<2?0:len * (len - 1) / 2;
}
};
int main()
{
return 0;
}
可见点的数量
1.对应letecode链接
2.题目描述
3.解题思路
本题如果会了上面那个题这个题不就算上面那个题的变形题目吗？可能有老铁不太明白为什么就是上面那个题目的变形题目了?首先我们可以将这个人所在的点平移到原点，将所有的点都减去这个点的横纵坐标，此时我们在把每个点和原点的夹角求出来。上面那个题是180度以内不回退这道题不就就是在视线角度之内不回退吗？至于如何求这个夹角可以自行百度这个不是重点，下面我们来看看这个代码
4.对应代码
class Solution {
public:
int visiblePoints(vector<vector<int>>& points, int angle, vector<int>& location) {
int N=points.size();
int m=location[0];
int n=location[1];
int zero=0;
int index=0;
vector<double>arr(N<<1);
for(int i=0;i<N;i++)
{
int x=points[i][0]-m;
int y=points[i][1]-n;
if(x==0&&y==0){//需要统计平移之后到了原点的数量因为自己所在的位置是可以看到的
zero++;
}
else{
double tmp=atan2(y, x) * 180 / M_PI;//计算角度
arr[index]=tmp;
arr[index+1]=tmp+360.0;
index+=2;
}
}
sort(arr.begin(),arr.begin()+index);
//注意不能全部排序有可能会有元素没有放进去
int L=0;
int R=0;
int ans=0;
//双指针不回退
while(L<N)
{
//视线角度内不回退
while(R<index&&arr[R]-arr[L]<=angle){
R++;
}
ans=max(ans,R-L);
L++;
}
return ans+zero;
}
};
分苹果
1.对应OJ链接
2.题目描述
3.解题思路
这题是典型的动态规划题目，我们首先进行尝试就是m个苹果放到n个盘子里面，在允许有空盘子的情况下有多少种不同的方法数。下面我们来分析这个可能性：
首先我们看如果盘子的数量大于苹果的数量，每个盘子又是一样的。那么多出来的盘子是没用的所以我们可以把它给砸了让苹果的数量和盘子的数量一样。
如果苹果的数量大于这个盘子的数量，我们就要想了。可能性1：盘子我都要用，所以我们可以往每个盘子都放一个苹果。可能性2：盘子不是都用，那么我们可以砸了一个盘子后面再讨论去让递归函数。至此我们可能性就分析完毕了，下面让我们来看看代码如何实现
4.对应代码
#include <iostream>
#include<vector>
using namespace std;
class Solution {
public:
vector<vector<int>>dp;
int Way1(int m, int n) {
dp.resize(m+1,vector<int>(n+1,-1));
return process(m, n);
}
int process(int m, int n) {
if (m == 0) { //0个苹果盘子全是空的一种方法
return 1;
}
if (n == 0) { //没有盘子了一定是0种方法
return 0;
}
if(dp[m][n]!=-1){
return dp[m][n];
}
if (m < n) {
//盘子太多了没用反正都会有剩余
dp[m][n]= process(m, m);
return dp[m][n];
}
//盘子全用和盘子不全用
//每个盘子都放一个或者只放一个在盘子里面
int ans= process(m - n, n) + process(m, n - 1);
dp[m][n]=ans;
return ans;
}
};
int main() {
int m, n;
cin >> m >> n;
cout << Solution().Way1(m, n) << endl;
}
本题还有另外一种尝试的方法但是了这种尝试的方法没有上面那种方法那么优秀，这个题也等价于将m裂成最多n个数可以不是n个但是最多n个并且裂开的数字前一个数字不能够比下一个要大，有多少种裂开的方法数。下面我们来看看这个代码怎么来写
#include <iostream>
#include<vector>
using namespace std;
class Solution {
public:
vector<vector<int>>dp;
int Way1(int m, int n) {
dp.resize(m + 1, vector<int>(n + 1, -1));
return process(m, n);
}
int Ways2(int m, int n) {
return process2(1, m, n);
}
//将m分裂最多n个数但是分列的数必须大于等于pre也就是前面的数
int process2(int pre, int m, int n) {
if (m == 0) {
return 1;
}
if (n == 0) {
return 0;
}
if (pre > m) {
return 0;
}
int ways = 0;
for (int i = pre; i <= m; i++) {
ways += process2(i, m - i, n - 1);
}
return ways;
}
int process(int m, int n) {
if (m == 0) { //0个苹果盘子全是空的一种方法
return 1;
}
if (n == 0) { //没有盘子了一定是0种方法
return 0;
}
if (dp[m][n] != -1) {
return dp[m][n];
}
if (m < n) {
//盘子太多了没用反正都会有剩余
dp[m][n] = process(m, m);
return dp[m][n];
}
//盘子全用和盘子不全用
//每个盘子都放一个或者只放一个在盘子里面
int ans = process(m - n, n) + process(m, n - 1);
dp[m][n] = ans;
return ans;
}
};
int main() {
int m, n;
cin >> m >> n;
cout << Solution().Ways2(m, n) << endl;
}