今天不学习明天变垃圾-学习笔记1129

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）操作，最后就能按规定完成汉诺塔的移动。

上面这段话怎么理解，拿个示例一步一步操作一下，示例图加说明如下（原创画图不易，转载请注明）：

http://blog.qianxiao.fun/wp-content/uploads/2020/11/未命名文件-1024x955.png

这下意思明白了，代码实现起来也就容易了：

#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;
}

1.三角形最大周长：

2.汉诺塔问题

发表评论 取消回复

发表评论取消回复