60天带你刷完Leetcode【第12天】563~552

2017-11-06 PKUGoodSpeed 美国加群小助手 美国加群小助手

每天30分钟 关注【北美加群小助手Jogchat.com】60天就能刷完Leetcode,学渣学酥也能跻身硅谷一线公司、升职加薪、当上总经理、出任CEO、迎娶白富美、从此走上人生巅峰!想想还有点小激动😏

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 的和,一定是两个部分和之差。这样我们其实想求有多少种 i,j pair,s.t.:
partial_sum[j] - partial_sum[i] == k  且  j>i
上 面的问题可以再 O(N) 的复杂度下完成:先把所有的 {partial_sum} 放进一个 Hash map 中,记录其出现次数,然后正向开始扫,没遇到一个 i, check map 中 key 为 partial_sum[i] + k 的元素的出现个数,并将其加入 ans 中。为了保证 j>i,每次扫过一个 i ,将 partial_sum[i] 在map中的出现次数减1,或者移除。下面题解并没有 explicitly 创建一个partial sum的数组,这样省了一些空间,但makes no difference,就是本学渣用来装逼的。

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 nand 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.
Specifically, to find the lexicographically biggest string, you need to experience two phases:

Concatenate all the strings into a loop, where you can reverse some strings or not and connect them in the same order as given.

Cut and make one breakpoint in any place of the loop, which will make the looped string into a regular one starting from the character at the cutpoint.

And your job is to find the lexicographically biggest one among all the possible regular strings.
题解:学渣就是学渣,做这种Medium的题都错了好几次,原因是理解错题意了:以为 Concatenate all the strings into a loop的时候,所有string随便放。后来才意识到这些string要维持原来顺序。
规模不大,直接 Bruce Force 即可。
假设第 ith string 刚好是被cut那个,那么剩下的string肯定是以 lexicographically 最大的次序排列。这样对 ith string 进行 Bruce Force 即可。

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.
The brick wall is represented by a list of rows. Each row is a list of integers representing the width of each brick in this row from left to right.
If your line go through the edge of a brick, then the brick is not considered as crossed. You need to find out how to draw the line to cross the least bricks and return the number of crossed bricks.
You cannot draw a line just along one of the two vertical edges of the wall, in which case the line will obviously cross no bricks.
Example:
Input:
[[1,2,2,1],
[3,1,2],
[1,3,2],
[2,4],
[3,1,2],
[1,3,1,1]]
Output: 2

Explanation:

题解:用一个 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.
However, you can add any number of parenthesis at any position to change the priority of operations. You should find out how to add parenthesis to get the maximum result, and return the corresponding expression in string format. Your expression should NOT contain redundant parenthesis.
Example:
Input: [1000,100,10,2]
Output: “1000/(100/10/2)”
Explanation:
1000/(100/10/2) = 1000/((100/10)/2) = 200
However, the bold parenthesis in “1000/((100/10)/2)” are redundant,
since they don’t influence the operation priority. So you should return “1000/(100/10/2)”.

Other cases:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2
题解:基本用脚想也知道,一个序列{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. The answer may be very large, return it after mod 109 + 7.
A student attendance record is a string that only contains the following three characters:

‘A’ : Absent.

‘L’ : Late.

‘P’ : Present.

A record is regarded as rewardable if it doesn’t contain more than one ‘A’ (absent) or more than two continuous ‘L’ (late).
Example 1:
Input: n = 2
Output: 8
Explanation:
There are 8 records with length 2 will be regarded as rewardable:
“PP” , “AP”, “PA”, “LP”, “PL”, “AL”, “LA”, “LL”
Only “AA” won’t be regarded as rewardable owing to more than one absent times.
题解:这题居然是hard,不可思议。用 dp 标记状态,依次类推就行了: dp[i][k] 表示长为 i 且状态为 k 的 rewardable 可能性的个数。一共有六种不同的状态:
k=0:结尾不是L,且没有A出现过:    记为 P + 0A
k=1: 结尾不是L,且A出现了一次:   记为 P + 1A
k=2: 结尾是一个L,且没有A出现过:  记为 L + 0A
k=3: 结尾是一个L,且A出现了一次:  记为 L + 1A
k=4: 结尾是两个L,且没有A出现过:  记为 LL + 0A
k=5: 结尾是两个L,且A出现了一次:  记为 LL + 1A
递归关系很简答。实际上二维数组都不需要,如下。

class Solution {    
   const long mod = 1E9 + 7;
   public
:    
       int checkRecord(int n) {        
           vector
<long>
dp(6,0);        // P+0A, P+1A, L+0A, L+1A, LL+0A, LL+1A            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;    } };


献给真正的大神,有兴趣的同学可以试一试。

长按扫码订阅

阅读 5758

微信扫一扫
关注该公众号