1.三角形最大周长:
https://leetcode-cn.com/problems/largest-perimeter-triangle/
蛮力法:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int largestPerimeter(vector<int>& A) {
int max = 0;
for(int i = 0;i < A.size();i++){
for (int j = 0; j < A.size(); j++)
{
if(i == j){
continue;
}
for (int k = 0; k < A.size(); k++)
{
if(j == k || i == k){
continue;
}
if(A[i]+A[j]>A[k]&&A[j]+A[k]>A[i]&&A[k]+A[i]>A[j]&&A[i]+A[j]+A[k]>max){
max = A[i]+A[j]+A[k];
}
}
}
}
return max;
}
};
蛮力法最终运行结果TLE。
更换思路,因为比较任意2边之和大于第三边,其实只需要比较较短的2边是否大于第三边,因此先排序,然后依次比较,而如果排序后前面的2个数和没有大于他们紧后面的数,那么就也不可能再大于更后面的数了,如{1,2,4,7,9},2+4<7不能构成△,那2,4,9更不能构成了。因此,排序后连续3次进行比较判断。
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int largestPerimeter(vector<int>& A) {
sort(A.begin(),A.end());
int max = 0;
for(int i = 0;i < A.size()-2;i++){
if(A[i]+A[i+1]>A[i+2]&&A[i]+A[i+1]+A[i+2]>max){
max = A[i]+A[i+1]+A[i+2];
}
}
return max;
}
};
优化
由于返回的结果是最大的周长,我们可以在排序后从后往前遍历比较判断,如果有,直接返回即可。因为,排序后,越后面的数若能构成△,则周长也越大。因此,从后面开始遍历,可以更快返回答案。
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int largestPerimeter(vector<int>& A) {
sort(A.begin(),A.end());
for(int i = A.size()-3;i >= 0;i--){
if(A[i]+A[i+1]>A[i+2]){
return A[i]+A[i+1]+A[i+2];
}
}
return 0;
}
};
2.汉诺塔问题
https://leetcode-cn.com/problems/hanota-lcci/
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
move(A.size(), A, B, C);
}
private:
void move(size_t n, vector<int>& A, vector<int>& B, vector<int>& C){
if(n == 1){
C.push_back(A.back());
A.pop_back();
}else{
move(n-1, A, C, B);
move(1, A, B, C);
move(n-1, B, A, C);
}
}
};
优雅的递归解法,n>1个盘子从A->C(借助B),我们需要先把n-1个盘子递归地从A->B(借助C),然后直接把第n个盘子从A->C,最后把n-1个盘子递归地从B->C(借助A)。
算法效率分析:
选择盘子数量n作为输入规模的一个指标,盘子移动视基本操作。
T(n) = 2T(n-1)+1=…(反向替换法)…=2^i T(n-i)+2^i -1=(令i=n-1)…=2^n -1
求移动次数:
使用全局变量每次move +1
#include <bits/stdc++.h>
using namespace std;
int num;//0
class Solution {
public:
void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
move(A.size(), A, B, C);
}
private:
void move(size_t n, vector<int>& A, vector<int>& B, vector<int>& C){
if(n == 1){
C.push_back(A.back());
A.pop_back();
num++;
}else{
move(n-1, A, C, B);
move(1, A, B, C);
move(n-1, B, A, C);
}
}
};
int main(){
vector<int> a = {3,2,1},b,c;
Solution s;
s.hanota(a,b,c);
cout<<num<<endl;
}
直接返回
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
return move(A.size(), A, B, C);
}
private:
int move(size_t n, vector<int>& A, vector<int>& B, vector<int>& C){
if(n == 1){
C.push_back(A.back());
A.pop_back();
return 1;
}else{
int a = move(n-1, A, C, B);
move(1, A, B, C);
int b = move(n-1, B, A, C);
return a+b+1;
}
}
};
int main(){
vector<int> a = {3,2,1},b,c;
Solution s;
cout<<s.hanota(a,b,c)<<endl;
}
输出过程
多传3个参数,代表柱号A B C
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
return move(A.size(), A, B, C, 'A', 'B', 'C');
}
private:
int move(size_t n, vector<int>& A, vector<int>& B, vector<int>& C, char a, char b, char c){
if(n == 1){
C.push_back(A.back());
cout<< a <<"-"<< A.back() <<"->"<< c <<endl;
A.pop_back();
return 1;
}else{
int n1 = move(n-1, A, C, B, a, c, b);//这里应该注意如果返回结果赋值给的变量被定义为a,b,则传字符时会与int的变量a,b混淆导致输出过程乱码,所以定义为n1,n2
move(1, A, B, C, a, b, c);
int n2 = move(n-1, B, A, C, b, a, c);
return n1+n2+1;
}
}
};
int main(){
vector<int> a = {3,2,1},b,c;
Solution s;
cout<<s.hanota(a,b,c)<<endl;
}
输出结果:
A-1->C
A-2->B
C-1->B
A-3->C
B-1->A
B-2->C
A-1->C
7
非递归
参考:https://blog.csdn.net/shiliang97/article/details/100150223
这里使用一种三角顺时移动法。
一位美国学者发现一种出人意料的方法,只要轮流进行两步操作就可以了。
首先把三根柱子按顺序排成品字型,把所有的圆盘按从大到小的顺序放在柱子A上。
根据圆盘的数量确定柱子的排放顺序:若n为偶数,按顺时针方向依次摆放 A B C;若n为奇数或0,按顺时针方向依次摆放 A C B。
(1)按顺时针方向把圆盘1(最小的)从现在的柱子移动到下一根柱子。
(2)接着把另外两根柱子(没有最小圆盘的那两个)上可以移动的圆盘移动到新的柱子上。
(3)反复进行(1)(2)操作,最后就能按规定完成汉诺塔的移动。
上面这段话怎么理解,拿个示例一步一步操作一下,示例图加说明如下(原创画图不易,转载请注明):

这下意思明白了,代码实现起来也就容易了:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
vector<int> *pillars[3];//3个柱子放到一个数组里通过下标访问 并依次定义下标0 1 2分别为顺时针方向的3个柱子 还需注意需要使用指针,而不是vector<int> pillars[3],不然无法真实改变传入引用A B C的值
pillars[0] = &A;
//根据奇偶先摆法
if(A.size()%2==1){
pillars[1] = &C;
pillars[2] = &B;
}else{
pillars[1] = &B;
pillars[2] = &C;
}
int i = 0;
//借助一个变量递增并模3取余来实现顺时针轮流 i非移动次数
while (++i){
move(*pillars[(i-1)%3], *pillars[(i)%3]);//顺时针移动1号(最小)盘子 此步每次都能返回true
if(!move(*pillars[(i-1)%3], *pillars[(i+1)%3]) && !move(*pillars[(i+1)%3], *pillars[(i-1)%3])){//移动其他2个盘子,由于不能再往上一步移动后的的拿个柱子上移(因为它最上面为1号(最小)盘子),所以即其他两个盘子中一个移动到另一个上,这里虽然是&&,但如果前者移动成功后者肯定移动不成功
break;
}
}
}
private:
bool move(vector<int>& z1, vector<int>& z2){
if(z1.empty() || (!z2.empty()&&z1.back()>z2.back())){
return false;
}
z2.push_back(z1.back());
z1.pop_back();
return true;
}
};
需要注意的细节:函数接受传入的引用,放到一个数组里时需要注意使用的是vector<int>指针数组,而非vector<int>数组。
问题拓展:4柱汉诺塔
即A借助B、C移到D。问最少步数?
我们可以先将盘子分成k和n-k两个部分,将A柱子上面的K个盘子使用Hanoi4方法将其借助C,D柱子移动到B柱子上面,然后将A柱子上面剩下的n-k个盘子使用Hanoi3方法将其借助C柱子移动到D柱子上面,最后将B柱子上面的K个盘子使用Hanoi4方法将其移动到D柱子上面。k取多少不知道,每次都试一遍呗。
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
int hanota4(int n) {
if(n == 1){
return 1;
}
int res = (int)10e9;
for (int k = 1; k < n; k++)
{
res = min(res,(int)(2*hanota4(k)+1<<(n-k)-1));
}
return res;
}
int main(){
cout<<hanota4(3)<<endl;
}
T(n) = 2T(k)+2^(n-k)-1 n>1,1<=k<n; T(1) = 1
优化
参考:https://blog.csdn.net/zwt_csdn/article/details/109089748
输出多组结果观察规律:
1 1
2 3 = f(1) +2
3 5 = f(2) +2
4 9 = f(3) +4
5 13 = f(4) +4
6 1 = f(5) +4
7 25 = f(6) +8
8 33 = f(7) +8
9 41 = f(8) +8
10 49 = f(9) +8
11 65 = f(10)+16
12 81 = f(11)+16
13 97 = f(12)+16
14 113 = f(13)+16
15 129 = f(14)+16
16 161 = f(15)+32
观察可得,盘数每增加1,答案增加是有规律的。所以可以从f(2)开始求并存储答案,一直求到f(n)。
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
int hanota4(int n) {
long res[64];
int add[64],index = 0;
//构造add递增序列 也可以常量定义
for (int j = 0; j < 100; j++){
for (int k = 0; k < j; k++){
add[index++] = 1<<(j-1);
if(index>=64){
break;
}
}
if(index>=64){
break;
}
}
res[0] = 0;
for (int i = 1; i <= n; i++){
res[i] = res[i-1] + add[i-1];
}
return res[n];
}
int main(){
cout<<hanota4(16)<<endl;
}
推到出公式即:
参考自https://blog.csdn.net/willmu/article/details/7963976
f(n)=f(n-1)+2^((int)(sqrt(8*n-7)-1)/2) (n>1); f(n)=1 (n=1)
拓展:判断汉诺塔状态
https://www.nowcoder.com/questionTerminal/5e6750d93d23456fbe47b9ebf2cb1059
1.在移动的时候对于Hanoi(n)来说,进行完Hanoi(n-1)的辅助之后,是直接把n放到目标上的,所以不会出现n在mid上的情况。
2.所以从大到小对圆盘进行考察,若是它在left上,则是正在进行Hanoi(n-1)的操作,即正在借助right转移到mid上。还未全部完成,不需要计算。(其部分完成的交给递归来计算)
3.若是n已经在right上了,说明已经完成了目标,当前正在进行借助left从mid到right的操作,则将其结果加起来就是答案
递归:
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
//a b c 分别代表源 借助 目标
int hano_nc(int *arr, int n, int a, int b, int c){
if(n == -1){
return 0;
}
if(arr[n] == b){
return -1;
}
if(arr[n] == a){
return hano_nc(arr, n-1, a, c, b);
}
int rest = hano_nc(arr, n-1, b, a ,c);
if(rest == -1) {
return -1;
}
//由于此时处于将n-1个从b借助a移到c,已经完成了前2步(共2^(n-1)-1 + 1 = 2^(n-1))
return ((1<<n) + rest)%1000000007;
}
int main(){
int n;
cin >> n;
int arr[n];
for(int i = 0; i < n; i++){
cin >> arr[i];
}
cout << hano_nc(arr, n-1, 1, 2, 3) << endl;
}
非递归:
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
int main(){
int n;
cin >> n;
int arr[n];
for(int i = 0; i < n; i++){
cin >> arr[i];
}
int a = 1, b = 2, c = 3;
vector<bool> flag(n, false);
for (int i = n-1; i >= 0; i--){
if(arr[i] == b){
cout << -1 << endl;
return 0;//程序结束
}
if(arr[i] == a){//还没移动最小面的这个盘子 此时正移上面i-1个盘子(A-C->B)
c = (c+b)-(b=c);
}else{//此时正移i-1盘 (B-A->C)
flag[i] = true;
a = (a+b)-(b=a);
}
}
int res = 0;
// for(int i = 0; i <n; i++){
// if(flag[i]){
// long t = (1<<i)%1000000007;
// res = (res+t)%1000000007;
// }
// }
for(int i = 0, base = 1; i < n; i++, base = (base<<1)%1000000007){
if(flag[i]){
res = (res+base)%1000000007;
}
}
cout << res << endl;
}
发表评论