Code – 第100页

LeetCode 657. Judge Route Circle

Initially, there is a Robot at position (0, 0). Given a sequence of its moves, judge if this robot makes a circle, which means it moves back to the original place.

The move sequence is represented by a string. And each move is represent by a character. The valid robot moves are R (Right), L (Left), U (Up) and D (down). The output should be true or false representing whether the robot makes a circle.

Example 1:
Input: “UD”
Output: true
Example 2:
Input: “LL”
Output: false

题目大意：最初，位置（0，0）处有一个机器人。给出它的一系列动作，判断这个机器人是否有一个圆圈，这意味着它回到原来的位置。移动顺序由一个字符串表示。而每一个动作都是由一个人物来表现的。有效的机器人移动R（右），L（左），U（上）和D（下）。输出应该是真或假，表示机器人是否成圈。

分析：计算UDLR出现的次数保存在map中，如果U和D出现的次数相同且L和R出现的次数相同则为true～

class Solution {
public:
    bool judgeCircle(string moves) {
        map<char, int> m;
        for(int i = 0; i < moves.length(); i++) m[moves[i]]++;
        return (m['L'] == m['R'] && m['U'] == m['D']);
    }
};

class Solution {

public:

bool judgeCircle(string moves) {

map<char, int> m;

for(int i = 0; i < moves.length(); i++) m[moves[i]]++;

return (m['L'] == m['R'] && m['U'] == m['D']);

}

};

LeetCode 637. Average of Levels in Binary Tree

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.
Example 1:
Input:
3
/ \
9 20
/ \
15 7
Output: [3, 14.5, 11]
Explanation:
The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].
Note:
The range of node’s value is in the range of 32-bit signed integer.

题目大意：计算一棵树的每一层结点的值的平均值。

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        dfs(root, 0);    
        vector<double> res;
        for(int i = 0; i <= ma ;i++) res.push_back(1.0*sum[i]/cnt[i]);
        return res;
    }
private: 
    int ma = 0;
    long long sum[1000], cnt[1000];
    void dfs(TreeNode* root, int lev) {
        if(root == NULL) return;
        sum[lev] += root->val;
        ma = max(ma,lev);
        cnt[lev]++;
        dfs(root->left, lev + 1);
        dfs(root->right, lev + 1);
    }
};

class Solution {

public:

vector<double> averageOfLevels(TreeNode* root) {

dfs(root, 0);

vector<double> res;

for(int i = 0; i <= ma ;i++) res.push_back(1.0*sum[i]/cnt[i]);

return res;

}

private:

int ma = 0;

long long sum[1000], cnt[1000];

void dfs(TreeNode* root, int lev) {

if(root == NULL) return;

sum[lev] += root->val;

ma = max(ma,lev);

cnt[lev]++;

dfs(root->left, lev + 1);

dfs(root->right, lev + 1);

}

};

LeetCode 575. Distribute Candies

Given an integer array with even length, where different numbers in this array represent different kinds of candies. Each number means one candy of the corresponding kind. You need to distribute these candies equally in number to brother and sister. Return the maximum number of kinds of candies the sister could gain.
Example 1:
Input: candies = [1,1,2,2,3,3]
Output: 3
Explanation:
There are three different kinds of candies (1, 2 and 3), and two candies for each kind.
Optimal distribution: The sister has candies [1,2,3] and the brother has candies [1,2,3], too.
The sister has three different kinds of candies.
Example 2:
Input: candies = [1,1,2,3]
Output: 2
Explanation: For example, the sister has candies [2,3] and the brother has candies [1,1].
The sister has two different kinds of candies, the brother has only one kind of candies.
Note:

The length of the given array is in range [2, 10,000], and will be even.
The number in given array is in range [-100,000, 100,000].

题目大意：给定一个长度为偶数的整型数组，这个数组中的不同数字表示不同类型的糖果。每个数字表示相应种类的一个糖果。你需要把这些糖果平均分配给弟弟和姐姐。返回姐姐可以获得的最大数量的糖果种类。

分析：放入unorder_set的集合中，集合中元素的个数就是糖果的种类，如果种类大于一半则返回一半的值，否则返回集合内的元素种类即可～

class Solution {
public:
    int distributeCandies(vector<int>& candies) {
        unordered_set<int> s;
        for (int i = 0; i < candies.size(); i++) s.insert(candies[i]);
        return min(s.size(), candies.size() / 2);
    }
};

class Solution {

public:

int distributeCandies(vector<int>& candies) {

unordered_set<int> s;

for (int i = 0; i < candies.size(); i++) s.insert(candies[i]);

return min(s.size(), candies.size() / 2);

}

};

LeetCode 572. Subtree of Another Tree

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.

Example 1:
Given tree s:

3
/ \
4 5
/ \
1 2
Given tree t:
4
/ \
1 2
Return true, because t has the same structure and node values with a subtree of s.
Example 2:
Given tree s:

3
/ \
4 5
/ \
1 2
/
0
Given tree t:
4
/ \
1 2
Return false.

题目大意：给定两个非空的二叉树s和t，检查树t是否具有与s的子树完全相同的结构和节点值。 s的子树是由s中的一个节点和所有这个节点的后代组成的一棵树。树也可以被认为是它自己的一个子树。

分析：isSame判断两棵树是否相等，isSubtree中如果s->val == t->val && isSame(s, t)则返回true表示以s为根结点和以t为根结点的树相等，否则判断s->left和t是否相等，s->right和t是否相等，只要有一个相等即可返回true～

class Solution {
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if (s == NULL && t == NULL) return true;
        if (s == NULL || t == NULL) return false;
        if (s->val == t->val && isSame(s, t)) return true;
        return isSubtree(s->left, t) || isSubtree(s->right, t);
    }
private:
    bool isSame(TreeNode* r, TreeNode* t) {
        if (r == NULL && t == NULL) return true;
        if (r == NULL || t == NULL || r->val != t->val) return false;
        return (isSame(r->left, t->left) && isSame(r->right, t->right));
    }
};

class Solution {

public:

bool isSubtree(TreeNode* s, TreeNode* t) {

if (s == NULL && t == NULL) return true;

if (s == NULL || t == NULL) return false;

if (s->val == t->val && isSame(s, t)) return true;

return isSubtree(s->left, t) || isSubtree(s->right, t);

}

private:

bool isSame(TreeNode* r, TreeNode* t) {

if (r == NULL && t == NULL) return true;

if (r == NULL || t == NULL || r->val != t->val) return false;

return (isSame(r->left, t->left) && isSame(r->right, t->right));

}

};

LeetCode 566. Reshape the Matrix

In MATLAB, there is a very useful function called ‘reshape’, which can reshape a matrix into a new one with different size but keep its original data.

You’re given a matrix represented by a two-dimensional array, and two positive integers r and c representing the row number and column number of the wanted reshaped matrix, respectively.

The reshaped matrix need to be filled with all the elements of the original matrix in the same row-traversing order as they were.

If the ‘reshape operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.

Example 1:
Input:
nums =
[[1,2],
[3,4]]
r = 1, c = 4
Output:
[[1,2,3,4]]
Explanation:
The row-traversing of nums is [1,2,3,4]. The new reshaped matrix is a 1 * 4 matrix, fill it row by row by using the previous list.
Example 2:
Input:
nums =
[[1,2],
[3,4]]
r = 2, c = 4
Output:
[[1,2],
[3,4]]
Explanation:
There is no way to reshape a 2 * 2 matrix to a 2 * 4 matrix. So output the original matrix.
Note:
The height and width of the given matrix is in range [1, 100].
The given r and c are all positive.

题目大意：给出一个由二维数组表示的矩阵，两个正整数r和c分别代表所需的整形矩阵的行号和列号。重构后的矩阵需要以原始矩阵的所有元素按照相同的行遍数顺序填充。如果“给定参数的重塑操作是可能的和合法的，则输出新的重塑矩阵; 否则，输出原始矩阵。

分析：如果原nums的行列乘积等于r*c则返回nums，否则建立r行c列的数组，将ans[i/c][i%c] = nums[i/m][i%m]即可～

class Solution {
public:
    vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) {
        int n = nums.size(), m = nums[0].size();
        if (n * m != r * c) return nums;
        vector<vector<int>> ans(r, vector<int>(c));
        for (int i = 0; i < r * c; i++) ans[i/c][i%c] = nums[i/m][i%m];
        return ans;
    }
};

class Solution {

public:

vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) {

int n = nums.size(), m = nums[0].size();

if (n * m != r * c) return nums;

vector<vector<int>> ans(r, vector<int>(c));

for (int i = 0; i < r * c; i++) ans[i/c][i%c] = nums[i/m][i%m];

return ans;

}

};

LeetCode 563. Binary Tree Tilt

Given a binary tree, return the tilt of the whole tree.

The tilt of a tree node is defined as the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values. Null node has tilt 0.

The tilt of the whole tree is defined as the sum of all nodes’ tilt.

Example:
Input:
1
/ \
2 3
Output: 1
Explanation:
Tilt of node 2 : 0
Tilt of node 3 : 0
Tilt of node 1 : |2-3| = 1
Tilt of binary tree : 0 + 0 + 1 = 1
Note:

The sum of node values in any subtree won’t exceed the range of 32-bit integer.
All the tilt values won’t exceed the range of 32-bit integer.

题目大意：给定一棵二叉树，返回整棵树的倾斜度。树节点的倾斜度被定义为所有左子树节点值的总和与所有右节点值的总和之间的绝对差值。空节点具有倾斜0。

分析：getSum函数用来计算以当前结点为根的子树的结点值总和，dfs用来遍历树，对于每个节点计算getSum的左子树和右子树之差累加，最后返回累加值～

class Solution {
public:
    int findTilt(TreeNode* root) {
        dfs(root);
        return ans;
    }
private:
    int ans = 0;
    int getSum(TreeNode* root) {
        if (root == NULL) return 0;
        int l = getSum(root->left), r = getSum(root->right);
        return l + r + root->val;
    }
    void dfs(TreeNode* root) {
        if (root == NULL) return;
        ans += abs(getSum(root->left)-getSum(root->right));
        dfs(root->left);
        dfs(root->right);
    }
};

class Solution {

public:

int findTilt(TreeNode* root) {

dfs(root);

return ans;

}

private:

int ans = 0;

int getSum(TreeNode* root) {

if (root == NULL) return 0;

int l = getSum(root->left), r = getSum(root->right);

return l + r + root->val;

}

void dfs(TreeNode* root) {

if (root == NULL) return;

ans += abs(getSum(root->left)-getSum(root->right));

dfs(root->left);

dfs(root->right);

}

};