60天带你刷完Leetcode【第13天】551 ~ 541

2017-11-13 PKU GoodSpeed 美国加群小助手 美国加群小助手

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

551. Student Attendance Record I

给你一个代表学生出勤记录的字符串。记录只包含以下三个字符:  ‘A’:缺席。 ‘L’:晚了。 ‘P’:现在。 如果学生的出席记录不包含多于一 “A”(缺席)或多于两个连续的“L”, 学生能得到表扬。问学生是否能得到表扬。

Example 1:

Input: “PPALLP” Output: True

Example 2:

Input: “PPALLL” Output: False

class Solution {
public:
    bool checkRecord(string s) {
        int cntA = 0, cntL = 0;
        for(auto c:s){
            if(c == 'A') cntA++;
            if(c == 'L'){
                cntL++;
                if(cntL>2) return false;
            }
            else cntL = 0;
        }
        return cntA<=1;
    }
};

549. Binary Tree Longest Consecutive Sequence II

给 定一个二叉树,你需要找到二叉树中最长的连续路径的长度。  特别是,这条道路可以增加或减少。例如,[1,2,3,4]和[4,3,2,1]都被认为是有效的,但路径[1,2,4,3]无效。另一方 面,路径可以在子 - 父 - 子顺序中,不一定是父 - 子顺序。

Example 1:

Input:
        1
       / \
      2   3
Output:
2
Explanation: The longest consecutive path is [1, 2] or [2, 1].

Example 2:

Input:
        2
       / \
      1   3
Output: 3
Explanation:
The longest consecutive path is [1, 2, 3] or [3, 2, 1].

题解:对每一个节点,算一个从上到下的最长的increasing consecutive sequence,和decreasing consecutive sequence,然后把它们接起来就行了。

class Solution {
    unordered_map<TreeNode *, int> dpinc, dpdec;
    int longestInc(TreeNode* r){
        if(!r) return 0;
        if(dpinc.count(r)) return dpinc[r];
        dpinc[r] = 1;
        if(r->left && r->left->val == r->val+1) dpinc[r] += longestInc(r->left);
        if(r->right && r->right->val == r->val+1) dpinc[r] = max(dpinc[r], longestInc(r->right) + 1);
        return dpinc[r];
    }
    int longestDec(TreeNode *r){
        if(!r) return 0;
        if(dpdec.count(r)) return dpdec[r];
        dpdec[r] = 1;
        if(r->left && r->left->val == r->val-1) dpdec[r] += longestDec(r->left);
        if(r->right && r->right->val == r->val-1) dpdec[r] = max(dpdec[r], longestDec(r->right) + 1);
        return dpdec[r];
    }
public:
    int longestConsecutive(TreeNode* root) {
        if(!root) return 0;
        int ans = longestInc(root) + longestDec(root) - 1;
        return max(ans, max(longestConsecutive(root->left), longestConsecutive(root->right)));
        return ans;
    }
};

548. Split Array with Equal Sum

题解:比较烦,就是用一个map<int, set

先对 i 进行 brute force

对于每一个 i, k 是确定的,从刚才那个 map 里找

然后再对 j 进行brute force: j 可取的值很少,也记录在刚才那个map里面

时间复杂度最差不超过 O(N^2)

Input: [1,2,1,2,1,2,1]Output: TrueExplanation:i = 1, j = 3, k = 5.  sum(0, i - 1) = sum(0, 0) = 1 sum(i + 1, j - 1) = sum(2, 2) = 1 sum(j + 1, k - 1) = sum(4, 4) = 1 sum(k + 1, n - 1) = sum(6, 6) = 1

class Solution {
public:
    bool splitArray(vector<int>& nums) {
        if(nums.size() < 7) return false;
        vector<int> p(nums.size()+1,0);
        unordered_map<int, set<int>> pos;
        for(int i=0;i<nums.size();++i) p[i+1]=p[i]+nums[i],pos[p[i+1]].insert(i+1);
        for(int i=1;i<nums.size()-5;++i) if(pos.count(p[nums.size()] - p[i])){
            for(auto k: pos[p[nums.size()] - p[i]]) if(k>i+4 && k<nums.size()){
                --k;
                for(auto it = pos[p[i+1]+p[i]].upper_bound(i+1);it!=pos[p[i+1]+p[i]].end() && *it<k-1;++it){
                    int j = *it;
                    if(p[k] - p[j+1] == p[i]) return true;
                }
            }
        }
        return false;
    }
};

547. Friend Circles:

班上有N个学生。有些是朋友,有些则不是。他们的友谊本质上是传递性的。例如,如果A是B的直接朋友,B是C的直接朋友,那么A是C的间接朋友。我们定义了一个朋友圈是一群直接或间接的朋友。

给定N * N矩阵M代表班级中学生之间的朋友关系。如果M [i] [j] = 1,那么第i和第j个学生是彼此直接的朋友,否则不是。你必须输出所有学生中的朋友圈总数。

Input: [[1,1,0],  [1,1,0],  [0,0,1]]
Output: 2
Explanation:The 0th and 1st students are direct friends, so they are
in a friend circle.
The 2nd student himself is in a friend circle. So return 2.

Input: [[1,1,0],  [1,1,1],  [0,1,1]]
Output: 1
Explanation:The 0th and 1st students are direct friends, the 1st and
2nd students are direct friends,
so the 0th and 2nd students are indirect friends.
All of them are in the same friend circle, so return 1.

题解:这题居然是medium,一个 BFS 就 over 了。(开始的时候,如果把矩阵变成 neighbor list 来表示两个人是否是直接朋友关系,BFS可能会快点。但即使是下面这个完全没用经过加工的 code ,离超时还有点远。)

class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        unordered_set<int> rest;
        for(int i=0;i<M.size();++i) rest.insert(i);
        int ans = 0;
        while(!rest.empty()){
            int i = *rest.begin();
            rest.erase(i);
            queue<int> Q;
            Q.push(i);
            while(!Q.empty()){
                int j = Q.front();
                Q.pop();
                for(int k=0;k<M.size();++k) if(M[k][j] && rest.count(k)){
                    rest.erase(k);
                    Q.push(k);
                }
            }
            ++ans;
        }
        return ans;
    }
};

546. Remove Boxes

给定由不同正数表示的不同颜色的几个盒子。
您可能会经历几轮移除箱子,直到没有箱子。每次你可以选择一些颜色相同的连续盒子(由k个盒子组成,k> = 1),去掉它们并得到k * k个点。
Input:

[1, 3, 2, 2, 2, 3, 4, 3, 1]

Output:

23

Explanation:

[1, 3, 2, 2, 2, 3, 4, 3, 1]  —→ [1, 3, 3, 4, 3, 1] (33=9 points)  —→ [1, 3, 3, 3, 1] (11=1 points)  —→ [1, 1] (33=9 points)  —→ [] (22=4 points)

引用                     fun4LeetCode大神的解法:
T(i,j,k)表示通过去除与盒子[i]相同颜色左边附加的k个盒子的子阵列盒子[i,j]的可能的最大points。我们原来的问题现在变成了T(0,n  -  1,0),因为开始时在输入数组的左边没有框。

终止条件现在将是:
a:T(i,i  -  1,k)= 0:没有盒子,所以没有points,任何k都是如此(你可以把它解释为无处附上盒子)。
b:T(i,i,k)=(k + 1)(k + 1):在子数组中只剩下一个盒子,但是我们已经有了左边相同颜色的k盒子, (k + 1),最大points是(k + 1)(k + 1)。

递归关系如下,最大points将是这两种情况中的较大者:
a:(k + 1)(k + 1)+ T(i + 1,j,0)points,第一项代替1,我们再次得到(k + 1)(k + 1)点,用于移除由于所附框位于其左侧的框[i];而第二学期将不会有附加框,所以我们在这个学期中有0个。
b: 如果我们决定把box [i]附加到相同颜色的其他box上,比如box [m],那么从我们上面的分析中,总的点数是T(i + 1,m  -  1,0)+ T (m,j,k + 1),其中对于第一项,由于子集数组[i + 1,m-1]没有附加框,所以对于该部分我们有k = 0; 而对于第二个term,子矩阵box[m,j]的附加箱子总数将增加1,因为除了原来的k箱子,我们现在必须考虑箱子[i],所以我们有k + 1个。但我们还没有完成。如果在子阵列框[i + 1,j]内有多个与框[i]具有相同颜色的框,该怎么办?我们必须尝试其中的每一个,并选择产生最高points的那个。因此,这种情况下的最终答案将 是:max(T(i + 1,m-1,0)+ T(m,j,k + 1))其中i <m <= j && boxes [i] ==box[M]。

public int removeBoxes(int[] boxes) {
    int n = boxes.length;
    int[][][] dp = new int[n][n][n];
    return removeBoxesSub(boxes, 0, n - 1, 0, dp);
}

private int removeBoxesSub(int[] boxes, int i, int j, int k, int[][][] dp) {
    if (i > j) return 0;
    if (dp[i][j][k] > 0) return dp[i][j][k];

    for (; i + 1 <= j && boxes[i + 1] == boxes[i]; i++, k++); // optimization: all boxes of the same color counted continuously from the first box should be grouped together
    int res = (k + 1) * (k + 1) + removeBoxesSub(boxes, i + 1, j, 0, dp);

    for (int m = i + 1; m <= j; m++) {
        if (boxes[i] == boxes[m]) {
            res = Math.max(res, removeBoxesSub(boxes, i + 1, m - 1, 0, dp) + removeBoxesSub(boxes, m, j, k + 1, dp));
        }
    }

    dp[i][j][k] = res;
    return res;
}

545. Boundary of Binary Tree

题目:给定一个二叉树,逆时针输出这个树的边界

Input:   1    \     2    / \   3   4
Ouput:[1, 3, 4, 2]
Explanation:The root doesn’t have left subtree, so the root itself
is left boundary. The leaves are node 3 and 4. The right boundary are node 1,2,4. Note the anti-clockwise direction
means you should output reversed right boundary. So order them in anti-clockwise without duplicates and
we have [1,3,4,2].

Input:
  1
   \
    2
   / \
  3   4
Ouput:
[1, 3, 4, 2]
Explanation:
The root doesn't have left subtree,
so the root itself is left boundary. The leaves are node 3 and 4. The right boundary are node 1,2,4.
Note the anti-clockwise direction means you should output
reversed right boundary. So order them in anti-clockwise without duplicates and
we have [1,3,4,2].

题解:就严格按照定义,用三次 preorder traversal , 依次求出该树的左边界,右边界,以及叶节点。然后把这三个数组 concatenate 起来即可。(理论上 one pass 就能搞定,小编比较笨,想不出来。)

class Solution {
    bool isLeaf(TreeNode *root){
        return root && !root->left && !root->right;
    }
public:
    vector<int> boundaryOfBinaryTree(TreeNode* root) {
        if(!root) return vector<int>();
        vector<int> left_bdry, right_bdry;
        left_bdry.push_back(root->val);
        stack<TreeNode *> stk;
        bool ok = true;
        for(auto p=root->left; (p||!stk.empty()) && ok;){
            while(p && ok){
                if(!isLeaf(p)) left_bdry.push_back(p->val);
                else ok = false;
                if(p->right) stk.push(p->right);
                p = p->left;
            }
            if(!stk.empty()){
                p = stk.top();
                stk.pop();
            }
        }
        ok = true;
        stk = stack<TreeNode*>();
        for(auto p = root->right; (p||!stk.empty()) && ok;){
            while(p && ok){
                if(!isLeaf(p)) right_bdry.push_back(p->val);
                else ok = false;
                if(p->left) stk.push(p->left);
                p = p->right;
            }
            if(!stk.empty()){
                p = stk.top();
                stk.pop();
            }
        }
        reverse(right_bdry.begin(), right_bdry.end());
        stk = stack<TreeNode*>();
        for(auto p=root; p||!stk.empty();){
            while(p){
                if(isLeaf(p) && p!=root) left_bdry.push_back(p->val);
                if(p->right) stk.push(p->right);
                p = p->left;
            }
            if(!stk.empty()){
                p = stk.top();
                stk.pop();
            }
        }
        left_bdry.resize(left_bdry.size() + right_bdry.size());
        copy(right_bdry.begin(), right_bdry.end(), 
             left_bdry.begin() + left_bdry.size() - right_bdry.size());
        return left_bdry;
    }
};

544. Output Contest Matches
在NBA季后赛期间,我们总是安排一支相当强壮的队伍与比较弱的队伍一起比赛,就像在排名第一的队伍中一样,这是一个让比赛更有趣的好策略。现在,你有n个队伍,你需要以字符串的形式输出他们的决赛。

n 个队以1到n的正整数形式表示,这是他们的初始排名。 (等级1是最强的队伍,而等级n是最弱的队伍)。我们将使用括号(’(’,’)’)和逗号(’,’)来表示比赛队伍的配对 - 括号(’(’ ‘)’)用于分区的配对和逗号(’,’)。在每一轮的配对过程中,你总是需要按照比较弱的那一对来做出相当强的一对。

Input: 2
Output: (1,2)
Explanation: Initially, we have the team 1 and the team 2,
placed like: 1,2. Then we pair the team (1,2) together with ‘(‘, ‘)’
and ‘,’, which is the final answer.

Input: 4
Output: ((1,4),(2,3))
Explanation: In the first round, we pair the team 1 and 4,
the team 2 and 3 together, as we need to make the strong
team and weak team together. And we got (1,4),(2,3). In the second round, the winners of (1,4) and (2,3)
need to play again to generate the final winner,
so you need to add the paratheses outside them. And we got the final answer ((1,4),(2,3)).

Input: 8
Output: (((1,8),(4,5)),((2,7),(3,6)))
Explanation: First round: (1,8),(2,7),(3,6),(4,5) Second round: ((1,8),(4,5)),((2,7),(3,6)) Third round: (((1,8),(4,5)),((2,7),(3,6))) Since the third round will generate the final winner,
you need to output the answer (((1,8),(4,5)),((2,7),(3,6))).

题解:小编比较笨,只能用recursion,也就是先把 n/2 的情况算出来,然后把里面的数字用 pair 替代掉。看了后面一个大神的解法之后,茅塞顿开,也佩服得五体投地。

class Solution {
public:
    string findContestMatch(int n) {
        if(n == 2) return "(1,2)";
        string tmp = findContestMatch(n/2);
        string ans;
        auto j = tmp.find_first_not_of("(),");
        ans += tmp.substr(0, j);
        while(j<tmp.size() && j!=string::npos){
            int k = stoi(tmp.substr(j));
            ans += "(" + to_string(k) +","+to_string(n+1-k)+")";
            auto i = tmp.find_first_of("(),", j);
            j = tmp.find_first_not_of("(),", i);
            ans += tmp.substr(i, j-i);
        }
        return ans;
    }
};

大神解法如下,精炼而优美:

class Solution {
public:
    string findContestMatch(int n) {
        vector<string> m(n);
        for(int i=0;i<n;++i) m[i] = to_string(i+1);
        while(n){
            for(int i=0;i<n/2;++i)
                m[i] = "("+m[i]+','+ m[n-i-1]+')';
            n/=2;
        }
        return m[0];
    }
};

543. Diameter of Binary Tree

给定一个二叉树,你需要计算树的直径的长度。二叉树的直径是树中任意两个节点之间最长路径的长度。这条路可能通过也可能不通过根。

Given a binary tree

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].


题解:小编实在不想用recursion,可惜太笨,想不出来其他更好的方法。

class Solution {
    unordered_map<TreeNode*,int> dp;
    int depth(TreeNode *r){
        if(!r) return 0;
        if(dp.count(r)) return dp[r];
        return dp[r] = 1+max(depth(r->left), depth(r->right));
    }
public:
    int diameterOfBinaryTree(TreeNode* root) {
        if(!root) return 0;
        int ans = depth(root->left) + depth(root->right);
        return max(ans, max(diameterOfBinaryTree(root->left), 
                            diameterOfBinaryTree(root->right)));
    }
};

542. 01 Matrix

给定一个由0和1组成的矩阵,找出每个单元最近的0的距离。
两个相邻单元之间的距离是1。
Example 1:
Input:

0 0 0 0 1 0 0 0 0

Output:

0 0 0 0 1 0 0 0 0

Example 2:
Input:

0 0 0 0 1 0 1 1 1

Output:

0 0 0 0 1 0 1 2 1

题解:这个题比较简单,小编自己就handle的了,一个BFS就够了。开始把所有是 0 的位置放入队列,然后依次 pop 并将其相邻 cell 依次放入队列。(学过BFS应该一看就懂了。)

class Solution {
    typedef vector<int> vi;
    int di[4] = {1,-1,0,0};
    int dj[4] = {0,0,-1,1};
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        if(matrix.empty() || matrix[0].empty()) return vector<vi>();
        int n = matrix.size(), m = matrix[0].size();
        vector<vi> ans(n,vi(m, -1));
        queue<int> Q;
        for(int i=0;i<n;++i) for(int j=0;j<m;++j) 
            if(!matrix[i][j]) Q.push(i*m + j), ans[i][j] = 0;
        while(!Q.empty()){
            int i = Q.front()/m, j = Q.front()%m;
            Q.pop();
            for(int k=0;k<4;++k){
                int i1 = i+di[k], j1 = j+dj[k];
                if(i1>=0 && i1<n && j1>=0 && j1<m && ans[i1][j1]==-1){
                    Q.push(i1*m+j1);
                    ans[i1][j1] = ans[i][j]+1;
                }
            }
        }
        return ans;
    }
};

541. Reverse String II
给定一个字符串和一个整数k,你需要对从字符串开头算起的每2k个字符的前k个字符进行反转。如果还有少于k个字符,则将其全部撤消。如果小于2k但大于或等于k个字符,则反转前k个字符,并将其他字符作为原始字符。

Example:

Input: s = “abcdefg”, k = 2
Output: “bacdfeg”

题解:Easy 的problem总是这么friendly,要是这个世界上只有 Easy 的问题多好啊。

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

长按扫码加微信公众号



阅读 5697

微信扫一扫
关注该公众号