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

965.Univalued Binary Tree & 965.单值二叉树

简单的思路就是:我们先获得这颗单值二叉树的目标单值(因为合法情况下所有节点的值均相同,所以我们取根节点的值为目标单值即可),然后遍历一下这颗二叉树,检查一下每一个节点的值是不是等于之前获得的目标单值
时间复杂度:O(n)

/**
 * 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:
    bool check(TreeNode* x, int v){
        if (x==NULL) return true;
        if (x->val!=v) return false;
        return check(x->left, v) && check(x->right, v);

    }
    bool isUnivalTree(TreeNode* root) {
        return check(root, root->val);
    }
};

967.Numbers With Same Consecutive Differences & 967.连续差相同的数字

这是一个简单的搜索问题,分开考虑结果的每一位,当前位能取的值之于它的前一个位的数值有关系,所以我们在搜索的时候只需要简单的记录上一位取的是多少即可。
另外一点小Trick就是,当N=1的时候,答案应该是[0, 1, 2, 3, 4, 5, 6, 7, 8, 9],其他情况下,只需要枚举开头是(0, 9]中的哪一个,然后搜索所有可能情况就行了。
时间复杂度:O(9\cdot 2^{(n-1)})

class Solution {
public:
    void dfs(int N, int K, int last, int rate, vector<int> &ans){
        if (N==0) { // When Comes To 0 Digit, we get an answer
            ans.push_back(rate); 
            return;
        }

        if (last==-1) { 
            // last=-1 => First Digit of Number [1, 9]
            for (int x=1; x<=9; x++)
                dfs(N-1, K, x, rate*10+x, ans);
        }else{ 
            // Second ... Last Digit, Try Last-K & Last+K
            if (last-K>=0) dfs(N-1, K, last-K, rate*10+last-K, ans);
            if (K!=0 && last+K<=9) dfs(N-1, K, last+K, rate*10+last+K, ans);
        }
    }

    vector<int> numsSameConsecDiff(int N, int K) {
        vector<int> ans; ans.clear();
        if (N==1) { // Special Solution When N=1
            for (int i=0; i<10; i++) ans.push_back(i);
            return ans;
        }
        dfs(N, K, -1, 0, ans);
        return ans;
    }
};

966.Vowel Spellchecker & 966.元音拼写检查器

因为数据范围并不是很大,所以我们可以针对题目中的三种不同情况,从query中取出一个单词,然后与wordlist中的所有单词按顺序挨个匹配。
* 对于完全相同的情况,我们只需要直接使用字符串进行匹配就可以了。
* 对于大小写不区分的情况,我们可以将匹配的目标字符串与模式字符串都转换成大写/小写,然后在比较这两个串是否完全相同就可以了。
* 对于元音字母可以相互转化的情况,我们可以发现元音字母是什么并不重要,把他们看成某一个相同记号就可以了(因为元音之间可以相互转化),所以我们先把匹配的目标字符串与模式字符串都转换成大写/小写,然后再将这两个串中间的元音字母替换为#,最后再判断两个字符串是否相同就可以了。
* 如果上面三种情况,都无法匹配,那就是题目中的没有匹配项的情况。
时间复杂度:O(n^2 \cdot Len)

class Solution {
public:
    char toLower(char x){
        if ('A'<=x && x<='Z') return x-'A'+'a';
        return x;
    }

    char tranChar(char x){
        x=toLower(x);
        if (x=='a' || x=='e' || x=='i' || x=='o' || x=='u') return '#';
        return x; 
    }

    vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {
        vector<string> ans; ans.clear(); // Save Answer

        int siz=wordlist.size(); // Get Size Of Wordlist

        for (auto str: queries){
            int len=str.length();
            int a=siz, b=siz, c=siz; // March Id in Wordlist for Three Situation

            for (int k=0, check; k<siz; k++){
                if (len!=wordlist[k].length()) continue;
                // Perfect March
                check=1;
                for (int i=0; i<len && check; i++) 
                    if (str[i]!=wordlist[k][i]) check=false;
                if (check) a=min(a, k);
                // Matches a word up to capitlization
                check=1;
                for (int i=0; i<len && check; i++) 
                    if (toLower(str[i])!=toLower(wordlist[k][i])) check=false;
                if (check) b=min(b, k);
                // Matches a word up to vowel errors
                check=1;
                for (int i=0; i<len && check; i++) 
                    if (tranChar(str[i])!=tranChar(wordlist[k][i])) check=false;
                if (check) c=min(c, k);
            }

            // Find Answer According to Rules
            if (a<siz) ans.push_back(wordlist[a]); 
            else if (b<siz) ans.push_back(wordlist[b]);
            else if (c<siz) ans.push_back(wordlist[c]);
            else ans.push_back("");
        }

        return ans;
    }
};
// ["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"]

968.Binary Tree Cameras & 968.监控二叉树

这是一道简单的动态规划题目,设计好状态表示与转移方程就可以通过这道题目。
通过阅读题目,我们可以发现树上每一个被监控的节点只有三种状态:被子节点的监控器监视、被自身的监控器监视、被父节点的监控器监视。

所以我们可以这样设计状态表示DP[x][0/1/2]表示以x为根的子树内,除了根节点其他节点全部都被监视,根节点被子节点的监控器监视(0) / 被自身的监控器监视(1) / 未来要被父节点的监控器监视(2),所需要使用的最少的监控器的数量。
显然,如果一个节点p是叶子节点,那么应该有DP[p][0]=\infty, DP[p][1]=1, DP[p][2]=0
如果这个节点x不是叶子节点,那么分当前节点的状态进行转移:
* 被子节点的监控器监视(0),那么DP[x][0]=\sum_{s_i~is~the~son~of~x} min(DP[s_i][0/1])同时所转移子节点的状态中至少要有一个子节点自身安放了监控器。
* 被自身的监控器监视(1) ,那么它的子节点是什么状态都可以,那么DP[x][1]=\sum_{s_i~is~the~son~of~x} min(DP[s_i][0/1/2])+1
* 未来要被父节点的监控器监视(2),那么子节点应该都是已经被监控但是没有放置监控器,所以DP[x][2]=\sum_{s_i~is~the~son~of~x} DP[s_i][0]

按照这种方法进行转移,最终根节点的min(dp[root][0], dp[root][1])就是答案。
时间复杂度:O(n\cdot 9)

P.S. 为了赶时间,比赛的时候代码写得比较冗长,使用循环3^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 dp[1000+50][3], idx;
    // 0 => Be Covered
    // 1 => Set
    // 2 => Gonna be Covered

    int dfs(TreeNode* x){
        int i=++idx, cnt=0; 
        vector<int> ch; ch.clear();

        if (x->left!=NULL) ch.push_back(dfs(x->left));
        if (x->right!=NULL) ch.push_back(dfs(x->right));
        cnt=ch.size();

        if (cnt==0){ // Leaf
            dp[i][0]=1050;
            dp[i][1]=1;
            dp[i][2]=0;
        }

        if (cnt==1){ // Single Son
            dp[i][0]=dp[ch[0]][1];
            dp[i][1]=min(dp[ch[0]][2], min(dp[ch[0]][0], dp[ch[0]][1]))+1;
            dp[i][2]=dp[ch[0]][0]; 
        }

        if (cnt==2){ // Tow Children
            dp[i][0]=min(dp[ch[0]][1]+dp[ch[1]][1], min(dp[ch[0]][0]+dp[ch[1]][1], dp[ch[0]][1]+dp[ch[1]][0]));

            dp[i][1]=min(dp[i][0], dp[ch[0]][0]+dp[ch[1]][0])+1;
            dp[i][1]=min(dp[i][1], dp[ch[0]][2]+dp[ch[1]][2]+1);
            dp[i][1]=min(dp[i][1], dp[ch[0]][2]+dp[ch[1]][1]+1);
            dp[i][1]=min(dp[i][1], dp[ch[0]][2]+dp[ch[1]][0]+1);
            dp[i][1]=min(dp[i][1], dp[ch[0]][1]+dp[ch[1]][2]+1);
            dp[i][1]=min(dp[i][1], dp[ch[0]][0]+dp[ch[1]][2]+1);

            dp[i][2]=dp[ch[0]][0]+dp[ch[1]][0];
        }

        return i;
    }

    int minCameraCover(TreeNode* root) {
        idx=0; int i=dfs(root);
        return min(dp[i][1], dp[i][0]);
    }
};
赞赏
https://secure.gravatar.com/avatar/f83b57c055136369e9feba5d6671d6b5?s=256&r=g

WNJXYK

文章作者

一个蒟蒻

推荐文章

发表评论

textsms
account_circle
email

WNJXYKのBlog

LeetCode Weekly Contest 117
965.Univalued Binary Tree & 965.单值二叉树 简单的思路就是:我们先获得这颗单值二叉树的目标单值(因为合法情况下所有节点的值均相同,所以我们取根节点的值为目标单值即可),然…
扫描二维码继续阅读
2018-12-30
<--! http2https -->