60天带你刷完Leetcode【第12天】563~552
563.Binary Tree Tilt
**题目：**求一个二叉树所有节点 tilt 之和，tilt 定义为一个左子树跟右子树节点和之差的绝对值。
**题解：**现求每个节点子节点之和，再求 tilt。
class Solution {
unordered_map<TreeNode *, int> dp,dp2;
int sum(TreeNode *r){
if(!r) return 0;
if(dp.count(r)) return dp[r];
return dp[r]=sum(r->left)+sum(r->right)+r->val;
}
public:
int findTilt(TreeNode* root) {
if(!root) return 0;
int ans = abs(sum(root->left)-sum(root->right));
ans += findTilt(root->left)+findTilt(root->right);
return ans;
}
};
562.Longest Line of Consecutive One in Matrix
**题目：**Given a 01 matrix M, find the longest line of consecutive one in the matrix. The line could be horizontal, vertical, diagonal or anti-diagonal.
**题解：**每个方向定义一个 dp 然后递归。One pass 就够了！
typedef vector<int> vi;
class Solution {
public:
int longestLine(vector<vector<int>>& M) {
if(M.empty() || M[0].empty()) return 0;
int n = M.size(), m = M[0].size(), ans = 0;
vi h(n,0), v(m,0), hv(n+m, 0), vh(n+m,0);
for(int i=0;i<n;++i) for(int j=0;j<m;++j){
if(!M[i][j]){
h[i] = v[j] = hv[i-j+m] = vh[i+j] = 0; continue;
}
h[i] = 1 + (j?h[i]:0);
v[j] = 1 + (i?v[j]:0);
hv[i-j+m] = 1 + (i&&j? hv[i-j+m]:0);
vh[i+j] = 1 + (i&&(m-j-1)? vh[i+j]:0);
ans = max(ans, max(max(h[i],v[j]),max(hv[i-j+m],vh[i+j])));
}
return ans;
}
};
561.Array Partition I
**题目：**Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.
**题解：**可以简单证明，这个 max min (ai, bi) 其实就是第二大的数 + 第四大的数 + … + 最小的数。
class Solution {
public:
int arrayPairSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
int ans = 0;
for(int i=0;i<nums.size();i+=2)
ans += nums[i];
return ans;
}
};
560.Subarray Sum Equals K
**题目：**Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.
**题解：**规模有点大，开始本学渣想正向一层层推，结果超时了。
**正解是：**首先记录这个序列的部分和 (partial sum) . 这样每一个 continuous subarray 的和，一定是两个部分和之差。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int,int> cnt;
for(int i=0,m=0;i<nums.size();++i){
m += nums[i];
cnt[m]++;
}
int ans = 0;
for(int i=0,m=0;i<nums.size();++i){
if(cnt.count(m+k))
ans += cnt[m+k];
m += nums[i];
cnt[m]--;
if(!cnt[m]) cnt.erase(m);
}
return ans;
}
};
557.Reverse Words in a String III
**题目：**Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.
Example:
Input: “Let’s take LeetCode contest”
Output: “s’teL ekat edoCteeL tsetnoc”
**题解：**正常的string操作。
class Solution {
public:
string reverseWords(string s) {
for(int j=0;j<s.size();){
int i = s.find(" ",j);
if(i==string::npos)
i = s.size();
reverse(s.begin()+j, s.begin()+i);
j = i+1;
}
return s;
}
};
556.Next Greater Element III
**题目：**Given a positive 32-bit integer n, you need to find the smallest 32-bit integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive 32-bit integer exists, you need to return -1.
**题解：**C++ 中有个函数叫 next_permutation ，正好为这个题设计的。其他语言没有，就自己写一个。
class Solution {
public:
int nextGreaterElement(int n) {
string s = to_string(n);
if(!next_permutation(s.begin(),s.end()))
return -1;
long ans = stol(s);
if(ans>(long)INT_MAX) return -1;
return (int)ans;
}
};
555.Split Concatenated Strings
**题目：**Given a list of strings, you could concatenate these strings together into a loop, where for each string you could choose to reverse it or not. Among all the possible loops, you need to find the lexicographically biggest string after cutting the loop, which will make the looped string into a regular one.
**题解：**学渣就是学渣，做这种Medium的题都错了好几次，原因是理解错题意了：以为 Concatenate all the strings into a loop的时候，所有string随便放。
class Solution {
public:
string splitLoopedString(vector<string>& strs) {
string ans, rest;
for(auto &s:strs){
string rs = s;
reverse(rs.begin(), rs.end());
rest += max(s, rs);
}
for(int i=0,l=0;i<strs.size();++i){
string s = strs[i];
string tmp=rest.substr(l+s.size())+rest.substr(0,l);
for(int j=0;j<s.size();++j){
string new_str = s.substr(j)+tmp+s.substr(0,j);
if(new_str>ans) ans = new_str;
}
reverse(s.begin(), s.end());
for(int j=0;j<s.size();++j){
string new_str = s.substr(j)+tmp+s.substr(0,j);
if(new_str>ans) ans = new_str;
}
l += s.size();
}
return ans;
}
};
554.Brick Wall
**题目：**There is a brick wall in front of you. The wall is rectangular and has several rows of bricks. The bricks have the same height but different width. You want to draw a vertical line from the top to the bottom and cross the least bricks.
**题解：**用一个 Hash map 记录每个横向位置出现边界的次数，最后选出现边界次数最大的位置cut即可。
class Solution {
public:
int leastBricks(vector<vector<int>>& wall) {
unordered_map<int, int> cnt;
for(auto vec:wall){
for(int m = vec[0], i=1;i<vec.size();++i){
cnt[m]++;
m += vec[i];
}
}
int ans = 0;
for(auto p: cnt) ans = max(ans, p.second);
return wall.size() - ans;
}
};
553.Optimal Division
**题目：**Given a list of positive integers, the adjacent integers will perform the float division. For example, [2,3,4] -> 2 / 3 / 4.
**题解：**基本用脚想也知道，一个序列{a1, a2, a3 …, an}, 组成的最大分数是 a1/(a2/a3/a4../an) 。
class Solution {
public:
string optimalDivision(vector<int>& nums) {
string ans = to_string(nums[0]);
if(nums.size() == 2) return ans+"/"+to_string(nums[1]);
for(int i=1;i<nums.size();++i) ans += (i==1?"/(":"/")+to_string(nums[i])+(i==nums.size()-1?")":"");
return ans;
}
};
552.Student Attendance Record II
**题目：**Given a positive integer n, return the number of all possible attendance records with length n, which will be regarded as rewardable.
**题解：**用 dp 标记状态，依次类推就行了： dp[i][k] 表示长为 i 且状态为 k 的 rewardable 可能性的个数。共六种状态：
class Solution {
const long mod = 1E9 + 7;
public:
int checkRecord(int n) {
vector<long> dp(6,0);
dp[0] = dp[1] = dp[2] = 1;
for(int i=1;i<n;++i){
vector<long> tmp(6,0);
tmp[0] = dp[0]+dp[2]+dp[4];
tmp[1] = dp[0]+dp[1]+dp[2]+dp[3]+dp[4]+dp[5];
tmp[2] = dp[0];
tmp[3] = dp[1];
tmp[4] = dp[2];
tmp[5] = dp[3];
dp.swap(tmp);
for(int j=0;j<6;++j)
if(dp[j]>=mod) dp[j]%=mod;
}
long ans = 0;
for(auto k:dp) ans+=k;
return ans%mod;
}
};