1.28回溯(中等）

本文主要是介绍1.28回溯(中等），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.格雷编码

2. 复原 IP 地址

3. 火柴拼正方形

1.格雷编码

n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：

每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）
第一个整数是 0
一个整数在序列中出现 不超过一次
每对相邻整数的二进制表示 恰好一位不同 ，且
第一个 和 最后一个 整数的二进制表示 恰好一位不同

给你一个整数 n ，返回任一有效的 n 位格雷码序列 。

示例 1：

输入：n = 2
输出：[0,1,3,2]
解释：
[0,1,3,2] 的二进制表示是 [00,01,11,10] 。
- 00 和 01 有一位不同
- 01 和 11 有一位不同
- 11 和 10 有一位不同
- 10 和 00 有一位不同
[0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。
- 00 和 10 有一位不同
- 10 和 11 有一位不同
- 11 和 01 有一位不同
- 01 和 00 有一位不同

示例 2：

输入：n = 1
输出：[0,1]

提示：

1 <= n <= 16

分析：感觉从题解来看，这个题好像和回溯没什么很大的关系力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

#include <bits/stdc++.h>
using namespace std;
main()
{int n,i,j,head=1;cin>>n;vector<int> res;res.push_back(0);cout<<0<<" ";for(i=0;i<n;i++){for(j=res.size()-1;j>=0;j--){res.push_back(head+res[j]);cout<<head+res[j]<<" ";}head<<=1;}
}

2. 复原 IP 地址

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示：

1 <= s.length <= 20
s 仅由数字组成

分析：这个就是要分割字符串了，刚开始只觉得和回文串是一样的，所以一直在想着一个字符一个字符去判断，结果到后面判断不清楚了，去看了别人的题解才想到完全可以直接用255来判断..

#include <bits/stdc++.h>
using namespace std;
bool isvaild(string s,int start,int end)
{if(start > end) return false;if(s[start]=='0' && start !=end) return false;int i,num=0;for(i=start;i<=end;i++){if(s[i]>'9' || s[i]<'0') return false;num=num*10+s[i]-'0';if(num>255) return false;}return true;
}
void f(string s,int index,int point)
{int i;if(point==3){if(isvaild(s,index,s.size()-1)){cout<<s<<endl;return;}}for(i=index;i<s.size();i++){if(isvaild(s,index,i)){s.insert(s.begin()+i+1,'.');point++;f(s,i+2,point);point--;s.erase(s.begin()+i+1);}else break;}
}
main()
{string s;cin>>s;if(s.size()<4 || s.size()>12) return 0;f(s,0,0);
}

3.火柴拼正方形

你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。

如果你能使这个正方形，则返回 true ，否则返回 false 。

示例 1:

输入: matchsticks = [1,1,2,2,2]
输出: true
解释: 能拼成一个边长为2的正方形，每边两根火柴。

示例 2:

输入: matchsticks = [3,3,3,3,4]
输出: false
解释: 不能用所有火柴拼成一个正方形。

提示:

1 <= matchsticks.length <= 15
1 <= matchsticks[i] <= 108

分析：之前有一道题用了排序，就让我想到了可以先排序，然后算一下总和，通过总和是不是4的倍数和总和/4是不是大于最大值来剪枝，之后就是要用到回溯，在回溯中，如果加和大于总和/4的话就要剪枝，这样可以减少计算量，然后剩下的就是回溯了，我本来想的是用一个字符串s1来记录然后放到4个result中，但是它直接就是result[4]，然后从这四个类似于堆的vector下手去做，就简单了好多，感觉真的非常的聪明欸

#include <bits/stdc++.h>
using namespace std;
int num[21],sum=0,n;
vector<int> result(4);
bool f(int index)
{int i;if(index==n) return true;for(i=0;i<4;i++){result[i]+=num[index];if(result[i]<=sum && f(index+1))return true;result[i]-=num[index];}return false;
}
main()
{int i=0,x;while(cin>>x){num[i]=x;sum+=x;i++;}n=i;sort(num,num+n);if(sum%4!=0) {cout<<"false"; return 0;}sum=sum/4;if(num[n-1]>sum) {cout<<"false"; return 0;}if(f(0)) {cout<<"true"; return 0;}else cout<<"false";}

这篇关于1.28回溯(中等）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！