LeetCode Weekly Contest 117

发布时间：2020-12-14 05:17:51 所属栏目：大数据来源：网络整理

导读：已经正式在实习了，好久都没有刷题了（应该有半年了吧），感觉还是不能把思维锻炼落下，所以决定每周末刷一次LeetCode。这是第一周（菜的真实，只做了两题，还有半小时不想看了，冷~）。第一题： 965.?Univalued Binary Tree A binary tree is? univalued

已经正式在实习了，好久都没有刷题了（应该有半年了吧），感觉还是不能把思维锻炼落下，所以决定每周末刷一次LeetCode。

这是第一周（菜的真实，只做了两题，还有半小时不想看了，冷~）。

第一题：

965.?Univalued Binary Tree

A binary tree is? univalued?if every node in the tree has the same value.

Return?true?if and only if the given tree is univalued.

Example 1:

Input: [1,1,null,1]
Output: true

Example 2:

Input: [2,2,5,2]
Output: false

Note:

The number of nodes in the given tree will be in the range?[1,100].
Each node‘s value will be an integer in the range?[0,99].

题目意思很简单，就是给你一棵树，让你判断这棵树所有节点的值是不是都是同一个数。

直接遍历节点，然后记录下来再判断就好。（其实可以边遍历边判断）

/**
 * 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 {
private:
    int a[100];
public:

    void view(TreeNode* root) {
        if( root != NULL ) a[root->val] ++;
        if( root->right != NULL ) view(root->right);
        if( root->left != NULL ) view(root->left);
    }

    bool isUnivalTree(TreeNode* root) {
        memset(a,0,sizeof(a));
        view(root);
        int cnt = 0;
        for(int i=0; i<100; i++) {
            if( a[i] != 0 ) cnt ++;
        }
        return cnt == 1;
    }
};

View Code

第二题：

967.?Numbers With Same Consecutive Differences

Return all?non-negative?integers of length?N?such that the absolute difference between every two consecutive digits is?K.

Note that?every?number in the answer?must not?have leading zeros?except?for the number?0?itself. For example,?01?has one leading zero and is invalid,but?0?is valid.

You may return the answer in any order.

Example 1:

Input: N = 3,K = 7 Output: [181,292,707,818,929] Explanation: Note that 070 is not a valid number,because it has leading zeroes.

Example 2:

Input: N = 2,K = 1 Output: [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]

Note:

1 <= N <= 9
0 <= K <= 9

?题目意思很简单，看样例基本能明白，给你一个长度n，和一个限定差值k，让你找出所有长度为n并且相邻数位之间的差值等于k的这些数（任何顺序），除0之外不能有任何数是以0开头。

有两个坑点：

1、当N为1的时候，0是正确的数。

2、当K为0的时候，注意不要重复计算。

class Solution {
public:
    vector<int> numsSameConsecDiff(int N,int K) {
        vector<int> ans;
        if( N == 1 ) ans.push_back(0);
        for(int i=1; i<10; i++) {
            queue<int> q;
            q.push(i);
            int len = N-1;
            while( len!=0 ) {
                int si = q.size();
                while( si -- ) {
                    int st = q.front(); q.pop();
                    int last = st % 10;
                    if( last + K < 10 ) q.push(st*10+last+K);
                    if( last - K >= 0 && (last+K != last-K) ) q.push(st*10+(last-K));
                }
                len --;
            }
            while( !q.empty() ) {
                int top = q.front();
                ans.push_back(top);
                q.pop();
            }
        }
        return ans;
    }
};

点击查看代码

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!