leetcode解题思路分析（六十五）552 - 558 题

野性酷女 2022-10-29 13:26 129阅读 0赞

1.  学生出勤记录2  
    给定一个正整数 n，返回长度为 n 的所有可被视为可奖励的出勤记录的数量。 答案可能非常大，你只需返回结果mod 109 + 7的值。

**和1相反，这里需要输出所有可能性。由于A只能有一次，所以先考虑L和P然后加入A即可。考虑L和P，可以采用动态规划求解。dp\[i\]\[j\]\[k\],0<=i<=n-1,j=0/1,k=0/1/2表示长为i的、里面不包含/包含‘A‘的、以k个‘L‘结尾的、可奖励的出勤数量。dp\[i\]只与dp\[i-1\]有关，因此去掉维度i即可**

class Solution { 
    public:
        long mod = 1e9 + 7;
        int checkRecord(int n) { 
            if(n == 1) return 3;
            vector<vector<long>> dp(2, vector<long>(3, 0));
            dp[0][0] = 1;
            dp[0][1] = 1;
            dp[0][2] = 0;
            dp[1][0] = 1;
            dp[1][1] = 0;
            dp[1][2] = 0;
            vector<vector<long>> cur(2, vector<long>(3, 0));
            for(long i = 2; i <= n; i++){ 
                cur[0][0] = (dp[0][0] + dp[0][1] + dp[0][2]) % mod;
                cur[0][1] = dp[0][0];
                cur[0][2] = dp[0][1];
                cur[1][0] = (dp[0][0] + dp[0][1] + dp[0][2] + dp[1][0] + dp[1][1] + dp[1][2]) % mod;
                cur[1][1] = dp[1][0];
                cur[1][2] = dp[1][1];
                dp = cur;
            }
            int ans = (dp[0][0] + dp[0][1] + dp[0][2] + dp[1][0] + dp[1][1] + dp[1][2]) % mod;
            return ans;
        }
    };

1.  最优除法  
    给定一组正整数，相邻的整数之间将会进行浮点除法操作。例如， \[2,3,4\] -> 2 / 3 / 4 。但是，你可以在任意位置添加任意数目的括号，来改变算数的优先级。你需要找出怎么添加括号，才能得到最大的结果，并且返回相应的字符串格式的表达式。你的表达式不应该含有冗余的括号。

**我们知道为了最大化 p/qp/q，分母 qq 应该最小化，所以为了最大化 a/b/c/da/b/c/d 我们首先需要最小化 b/c/d，现在我们的目标变成了最小化表达式 b/c/d。有 2 种可能的表达式组合方法，分别是 b/(c/d) 和 (b/c)/d。对于d>1，显然有b/c/d更小。所以结果必然是在第二个数到最后一个数加一个括号即可。**

class Solution { 
    public:
        string optimalDivision(vector<int> &nums) { 
            if (nums.size() == 1)       //注意考虑size为1和2的特殊情况
                return  to_string(nums[0]);
            if (nums.size() == 2) { 
                return to_string(nums[0]) + "/" + to_string(nums[1]);
            }
            string re(to_string(nums[0]) + "/(");
            for (int i = 1; i < nums.size() - 1; ++i) { 
                re += to_string(nums[i]) + "/";
            }
            re += to_string(nums.back()) + ")";     //最后一个数 和括号
            return re;
        }
    };

1.  砖墙  
    你的面前有一堵矩形的、由多行砖块组成的砖墙。 这些砖块高度相同但是宽度不同。你现在要画一条自顶向下的、穿过最少砖块的垂线。

**用哈希表记录间隙的位置，然后编译一遍即可**

class Solution { 
    public:
        int leastBricks(vector<vector<int>>& wall) { 
            unordered_map<int,int> mp;//统计缝的重复数量
            for(int i=0;i<wall.size();++i){ 
                int len=0;
                for(int j=0;j<wall[i].size()-1;++j){ //注意不统计最后一个位置
                    len+=wall[i][j];//该层的各个长度
                    ++mp[len];
                }
            }
            int res=0;
            for(auto& it:mp){ //找出最大值
                res=max(res,it.second);
            }
            return wall.size()-res;//返回最多的穿过的缝隙
        }
    };

1.  下一个更大元素  
    给你一个正整数 n ，请你找出符合条件的最小整数，其由重新排列 n 中存在的每位数字组成，并且其值大于 n 。如果不存在这样的正整数，则返回 -1 。注意 ，返回的整数应当是一个 32 位整数 ，如果存在满足题意的答案，但不是 32 位整数 ，同样返回 -1 。

**将正整数保存为一系列的数，然后从低位开始遍历，找到更小的数则往回寻找到最后一个数，交换即可**

class Solution { 
    public:
        int nextGreaterElement(int n) { 
            long long ans = 0;
            string src = to_string(n);
            int size = src.size();
            stack<int> stack;
            int idx = 0;
            int i = size - 1;
            for (; i >= 0; i--) { 
                //维护一个单调递增栈，如果当前元素比栈顶元素小，则将栈顶元素出栈，并更新索引，栈顶元素越来越小，最后一个出栈的元素就是比当前元素大的最小值
                while (!stack.empty() && (src[i] < src[stack.top()])) { 
                    idx = stack.top();
                    stack.pop();
                }
                //将两个元素进行交换
                if (idx != 0) { 
                    int tmp = src[i];
                    src[i] = src[idx];
                    src[idx] = tmp;
                    break;
                }
                stack.push(i);
            }
            if (idx == 0) { 
                return -1;
            }
            //将i+1以后的数字从小到大排序
            sort(src.begin() + i + 1, src.end());
            ans = stoll(src);
            if (ans > INT_MAX) { 
                return -1;
            }
            return ans;
        }
    };

1.  反转字符串中的单词3  
    给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

**遍历一遍，双指针记录首尾即可**

class Solution { 
    public: 
        string reverseWords(string s) { 
            int length = s.length();
            int i = 0;
            while (i < length) { 
                int start = i;
                while (i < length && s[i] != ' ') { 
                    i++;
                }
    
                int left = start, right = i - 1;
                while (left < right) { 
                    swap(s[left], s[right]);
                    left++;
                    right--;
                }
                while (i < length && s[i] == ' ') { 
                    i++;
                }
            }
            return s;
        }
    };

1.  四叉树交集  
    给你两个四叉树，quadTree1 和 quadTree2。其中 quadTree1 表示一个 n \* n 二进制矩阵，而 quadTree2 表示另一个 n \* n 二进制矩阵。请你返回一个表示 n \* n 二进制矩阵的四叉树，它是 quadTree1 和 quadTree2 所表示的两个二进制矩阵进行 按位逻辑或运算 的结果。

**已知四叉树A B 的两个节点 a b, 需要根据a,b构造相应的四叉树C的节点c。 可以分两种情况考虑  
1.a b 其中至少有一个节点为叶子节点：  
如果a b 均为叶子节点，则返回一个new Node() 叶子节点，节点的val为 (a->val || b->val)  
如果只有一个节点为叶子节点，假设a为叶子结点，b为非叶子节点。  
如果a->val == false, 则a的值对b不会产生影响，直接返回b；  
如果a->val == true,则b的值不会对a产生影响，b的所有叶子节点会全变为true，并且会合并成一个大节点（题目中四叉树节点的定义：对于每个结点, 它将被等分成四个孩子结点直到这个区域内的值都是相同的），合并结果其实和a一样，因此可以直接返回a。  
2. a b 均不为叶子节点 则创建一个非叶子节点c， c下的4个节点分别由a，b的4个子节点构造  
c = new Node(false, false, nullptr, nullptr, nullptr, nullptr);  
c->topLeft = f(a->topLeft, b->topLeft)  
c->topRight = f(a->topRight, b->right)  
……  
3. 需要额外考虑  
构造完节点c后，我们还需要考虑，是否需要把c合并成大节点（c下的子节点都是叶子节点，且val都相等）**

/* // Definition for a QuadTree node. class Node { public: bool val; bool isLeaf; Node* topLeft; Node* topRight; Node* bottomLeft; Node* bottomRight; Node() { val = false; isLeaf = false; topLeft = NULL; topRight = NULL; bottomLeft = NULL; bottomRight = NULL; } Node(bool _val, bool _isLeaf) { val = _val; isLeaf = _isLeaf; topLeft = NULL; topRight = NULL; bottomLeft = NULL; bottomRight = NULL; } Node(bool _val, bool _isLeaf, Node* _topLeft, Node* _topRight, Node* _bottomLeft, Node* _bottomRight) { val = _val; isLeaf = _isLeaf; topLeft = _topLeft; topRight = _topRight; bottomLeft = _bottomLeft; bottomRight = _bottomRight; } }; */
    
    class Solution { 
    public:
        Node* intersect(Node* quadTree1, Node* quadTree2) 
        {    
            if(quadTree1 ->isLeaf && quadTree2->isLeaf)
            { 
                return new Node(quadTree1->val || quadTree2->val, true, NULL, NULL, NULL, NULL);
            }
            else if(quadTree1->isLeaf)
            { 
                return quadTree1->val == true ? quadTree1 : quadTree2;
            }
            else if(quadTree2->isLeaf)
            { 
                return quadTree2->val == true ? quadTree2 : quadTree1;
            }
            else
            { 
                Node* node = new Node(false, false, NULL, NULL, NULL, NULL);
                node->topLeft = intersect(quadTree1->topLeft, quadTree2->topLeft);
                node->topRight = intersect(quadTree1->topRight, quadTree2->topRight);
                node->bottomLeft = intersect(quadTree1->bottomLeft, quadTree2->bottomLeft);
                node->bottomRight = intersect(quadTree1->bottomRight, quadTree2->bottomRight);
                //如果四个节点均为叶子节点，且值相等 则合并为一个主节点
                if(node->topLeft->isLeaf && node->topRight->isLeaf && node->bottomLeft->isLeaf && node->bottomRight->isLeaf 
                   && node->topLeft->val == node->topRight->val && node->topLeft->val == node->bottomLeft->val 
                   && node->topLeft->val == node->bottomRight->val)
                { 
                        node->isLeaf = true;
                        node->val = node->topLeft->val;
                        node->topLeft = node->topRight = node->bottomLeft = node->bottomRight = NULL;
                }
                return node;
            }
        }
    };