WNJXYK
Thanks to the cruel world.
WNJXYKのBlog
LeetCode Weekly Contest 118
LeetCode Weekly Contest 118

970.强整数 / Powerful Integers

因为bound范围[1, 1e6]较小,所以两个参数的最高幂次应该不会很大。
两重循环分别对两个参数的幂次进行枚举,然后使用一个map<int,bool>对数字是否重复加入答案集合判断一下即可。
特别需要注意一下,如果参数x=1y=1,这个时候某些写法可能会出现一些问题导致死循环。

class Solution {
public:
    vector<int> powerfulIntegers(int x, int y, int bound) {
        vector<int> ans; ans.clear();
        map<int, bool> vis; vis.clear();

        for (int a=1; a<=bound; a*=x){
            for (int b=1; b<=bound; b*=y){
                if (a+b<=bound && !vis[a+b]){
                    vis[a+b]=true;
                    ans.push_back(a+b);
                }
                if (y==1) break;
            }
            if (x==1) break;
        }

        sort(ans.begin(), ans.end());
        return ans;
    }
};

969.煎饼排序 / Pancake Sorting

将一个在位置P的数字放到位置Q上,只需要两步:翻转[1, P],翻转[1, Q]。(但是这种有一个缺点:会将[1, max(P, Q)-1]中的数字打乱)
但是由于最终操作序列的长度限制非常宽松,所以我们很容易想到一个长度序列不超过2\times A.length()的构造方法:从最大的数字到最小的数字依次将它们使用如上方法放到最终位置上(这样让序列逐渐从后往前有序,这样打乱前面的数字对我们来说无所谓)

class Solution {
public:
    vector<int> pancakeSort(vector<int>& A) {
        vector<int> ans; ans.clear();
        int n=A.size();

        for (int x=n, p; x>=1; x--){
            for (int i=0; i<n; i++) if (A[i]==x) {p=i; break;}
            if (p+1==x) continue; // No need
            if (p!=0) {
                ans.push_back(p+1);
                reverse(A.begin(), A.begin()+p+1);   
            }
            for (int i=0; i<n; i++) if (A[i]==x) {p=i; break;}
            ans.push_back(x);
            reverse(A.begin(), A.begin()+x);
        }

        return ans;
    }
};

971.翻转二叉树以匹配先序遍历 / Flip Binary Tree To Match Preorder Traversal

看到题目之后,可以明确的一点就是,如果先序遍历序列可以构造成Voyage序列,那么需要翻转左右孩子的节点一定是固定的。我们的任务就是确定这些节点,就不用管什么最大最小了。

我们先序列遍历这棵树,假设当前节点root已经在Voyage序列里匹配完成了,我们接下来要匹配它的子节点,分三种情况:
1. root没有子节点,那么直接完成对它的匹配就可以了。
2. root有一个子节点,那么这一个子节点的值一定要等于Voyage序列下一个期望的值,否则无法构造了。
3. root有两个子节点,那么这两个子节点中其中一个的值一定要等于Voyage序列下一个期望的值,如果不巧这个节点是一个右孩子,那么root就是一个需要翻转的节点了。在Voyage序列中匹配这个子节点,然后对这个子节点进行先序遍历(并假装这个子节点在root中删除了)。等到先序遍历回到root节点的时候,按照情况2处理就行了。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int mv=0;
    bool succ=true;

    void dfs(TreeNode* root, vector<int>& voyage, vector<int>& ans){
        if (!succ) return;
        if (root->left==NULL && root->right==NULL) return;

        if (root->left==NULL || root->right==NULL){
            ++mv;
            if (root->left!=NULL){
                if (root->left->val!=voyage[mv]){ succ=false; return; }
                dfs(root->left, voyage, ans);
            }else{
                if (root->right->val!=voyage[mv]){ succ=false; return; }
                dfs(root->right, voyage, ans);
            }
            return;
        }

        ++mv;
        if (voyage[mv]!=root->left->val 
            && voyage[mv]!=root->right->val) { succ=false;  return; }

        if (voyage[mv]==root->left->val){
            dfs(root->left, voyage, ans);
            ++mv;
            if (voyage[mv]!=root->right->val) { succ=false;  return; }
            dfs(root->right, voyage, ans);
        }else{
            ans.push_back(root->val);
            dfs(root->right, voyage, ans);
            ++mv;
            if (voyage[mv]!=root->left->val) { succ=false;  return; }
            dfs(root->left, voyage, ans);
        }
    }

    vector<int> flipMatchVoyage(TreeNode* root, vector<int>& voyage) {
        vector<int> ans; ans.clear();

        if (root->val!=voyage[0]) succ=false; else succ=true;
        dfs(root, voyage, ans);

        if (!succ){
            ans.clear(); ans.push_back(-1);
            return ans;
        }else return ans;
    }
};

972.相等的有理数 / Equal Rational Numbers

恕我直言,我觉得这道题目是最简单的题目。。。
判断两个数字是否相等,(不同的表示方法可能会表示同一个值,例如0.999(9)1
因为要比较的数字的长度很短[1, 12],所以我们直接可以使用long double类型将这两个数字转化为整数部分+不循环小数+循环小数循环20遍,然后判断这两个long double类型的误差是否在可接受范围内(例如:1e-20)即可。

class Solution {
public:
    long double A=0, B=0;

    long double str2ldouble(string S){
        int n=S.length();
        long double z=0, s=0, x=0;
        long double rs=1, rx=1;

        int state=0;

        for (int i=0; i<n; i++){
            if (S[i]=='.') {state=1; continue;}
            if (S[i]=='(') {state=2; continue;}
            if (S[i]==')') break;
            if (state==0){
                z=z*10.0+(S[i]-'0');
            }else if (state==1){
                rs/=10.0;
                s+=rs*(S[i]-'0');
            }else{
                rx/=10.0;
                x+=rx*(S[i]-'0');
            }
        }

        long double ret=z+s;
        for (int i=0; i<20; i++) ret+=rs*x, x*=rx;

        return ret;
    }


    bool isRationalEqual(string S, string T) {
        long double A=str2ldouble(S);
        long double B=str2ldouble(T);

        // printf("%.10lf\n", (double)A);
        // printf("%.10lf\n", (double)B);
        long double EPS=1e-15;
        return fabs(A-B)<EPS;
    }
};
赞赏
https://secure.gravatar.com/avatar/f83b57c055136369e9feba5d6671d6b5?s=256&r=g

WNJXYK

文章作者

一个蒟蒻

推荐文章

发表评论

textsms
account_circle
email

WNJXYKのBlog

LeetCode Weekly Contest 118
970.强整数 / Powerful Integers 因为bound范围$[1, 1e6]$较小,所以两个参数的最高幂次应该不会很大。 两重循环分别对两个参数的幂次进行枚举,然后使用一个map<int,bool>对数字…
扫描二维码继续阅读
2019-01-06
<--! http2https -->