liuchuo – 第101页 – 我不管，反正我最萌～

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);

}

};

LeetCode 551. Student Attendance Record I

You are given a string representing an attendance record for a student. The record only contains the following three characters:
‘A’ : Absent.
‘L’ : Late.
‘P’ : Present.
A student could be rewarded if his attendance record doesn’t contain more than one ‘A’ (absent) or more than two continuous ‘L’ (late).

You need to return whether the student could be rewarded according to his attendance record.

Example 1:
Input: “PPALLP”
Output: True
Example 2:
Input: “PPALLL”
Output: False

分析：正则表达式匹配，如果出现三次连续的LLL或者两次AA则返回false

class Solution {
public:
    bool checkRecord(string s) {
        return !regex_match(s, regex(".*LLL.*|.*A.*A.*"));
    }
};

class Solution {

public:

bool checkRecord(string s) {

return !regex_match(s, regex(".*LLL.*|.*A.*A.*"));

}

};

LeetCode 543. Diameter of Binary Tree

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree
1
/ \
2 3
/ \
4 5
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

题目大意：给一个二叉树，计算出任意两个节点中最长的长度并返回结果～

分析：计算每个节点的深度，并在dfs过程中将每个节点左边深度+右边深度的值的最大的值保存在ans中返回～

class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        dfs(root);
        return ans;
    }
private:
    int ans = 0;
    int dfs(TreeNode* root) {
        if (root == NULL) return 0;
        int l = dfs(root->left), r = dfs(root->right);
        ans = max(ans, l + r);
        return max(l, r) + 1;
    }
};

class Solution {

public:

int diameterOfBinaryTree(TreeNode* root) {

dfs(root);

return ans;

}

private:

int ans = 0;

int dfs(TreeNode* root) {

if (root == NULL) return 0;

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

ans = max(ans, l + r);

return max(l, r) + 1;

}

};

LeetCode 541. Reverse String II

Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and left the other as original.
Example:
Input: s = “abcdefg”, k = 2
Output: “bacdfeg”
Restrictions:
The string consists of lower English letters only.
Length of the given string and k will in the range [1, 10000]

题目大意：给一个字符串s和一个整数k，每2k长度倒置前k个字符串，如果最后剩余的长度小于k则全都倒置，否则如果剩余的长度大于k小于2k，倒置前k个，返回倒置后的字符串～

分析：遍历字符串，步长为2k，每次倒置s.begin() + i～s.begin() + i + k的字符串，如果i + k > s.length()就倒置s.begin() + i～s.begin() + s.length()即可～O(∩_∩)O～

class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.length(); i+=2*k) {
            int t = min((i + k), (int)s.length());
            reverse(s.begin() + i, s.begin() + t);
        }
        return s;
    }
};

class Solution {

public:

string reverseStr(string s, int k) {

for (int i = 0; i < s.length(); i+=2*k) {

int t = min((i + k), (int)s.length());

reverse(s.begin() + i, s.begin() + t);

}

return s;

}

};

LeetCode 739. Daily Temperatures

Given a list of daily temperatures, produce a list that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list temperatures = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

分析：用栈解决，i从0～len-1，每次将栈顶元素小于temperatures[i]的出栈，因为对于出栈的元素来说它已经找到了第一个大于它的值，剩余在栈中的都是未找到大于它本身的值的元素，则继续等待下一个temperatures[i]。每次将temperatures[i]压入栈中，等待接下来遇到比它大的值时出栈～将i与栈顶元素下标的差值保存在栈顶元素的下标所对应的ans中，最后返回ans即可～

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<pair<int, int>> s;
        int len = temperatures.size();
        vector<int> ans(len);
        for (int i = 0; i < len; i++) {
            while(!s.empty() && temperatures[i] > s.top().first) {
                ans[s.top().second] = i - s.top().second;
                s.pop();
            }
            s.push(pair<int, int>(temperatures[i], i));
        }
        return ans;
    }
};

class Solution {

public:

vector<int> dailyTemperatures(vector<int>& temperatures) {

stack<pair<int, int>> s;

int len = temperatures.size();

vector<int> ans(len);

for (int i = 0; i < len; i++) {

while(!s.empty() && temperatures[i] > s.top().first) {

ans[s.top().second] = i - s.top().second;

s.pop();

}

s.push(pair<int, int>(temperatures[i], i));

}

return ans;

}

};