LeetCode 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

Note:

1. The length of the input array is [1, 10].
2. Elements in the given array will be in range [2, 1000].
3. There is only one optimal division for each test case.

---

给定一个正整数数组，数据范围是[2,1000]，初始每个数依次除以后一个数，现在要给数组加上括号，使得整个数组相除的结果最大。 首先来个暴力方法，对区间[start, end]，枚举每一个分割位置i，也就是[start, i]算除法，[i+1, end]也算除法，然后把前者的结果除以后者。结果的最大值为前者的最大值除以后者的最小值，结果的最小值为前者的最小值除以后者的最大值。一直递归下去，最后就能得到整个区间[0,n-1]的最大值了。 代码如下： [cpp] struct T { double lfMax, lfMin; string strMax, strMin; }; class Solution { private: T optimal(vector<int>& nums, int start, int end){ T t; if(start == end){ t.lfMax = t.lfMin = nums[start]; t.strMax = t.strMin = to_string(nums[start]); return t; } t.lfMax = std::numeric_limits<double>::min(); t.lfMin = std::numeric_limits<double>::max(); for(int i = start; i < end; ++i){ T tl = optimal(nums, start, i); T tr = optimal(nums, i + 1, end); if(tl.lfMax / tr.lfMin > t.lfMax){ t.lfMax = tl.lfMax / tr.lfMin; t.strMax = tl.strMax + "/" + (i + 1 != end ? "(" : "") + tr.strMin + (i + 1 != end ? ")" : ""); } if(tl.lfMin / tr.lfMax < t.lfMin){ t.lfMin = tl.lfMin / tr.lfMax; t.strMin = tl.strMin + "/" + (i + 1 != end ? "(" : "") + tr.strMax + (i + 1 != end ? ")" : ""); } } return t; } public: string optimalDivision(vector<int>& nums) { T t = optimal(nums, 0, nums.size() – 1); return t.strMax; } }; [/cpp] 本代码提交AC，用时86MS。暴力方法相当于枚举数组的所有排列情况，时间复杂度为O(n!)。 上述方法对某一小段区间会有很多重复计算，我们可以用数组把结果存起来达到加速的目的。使用数组memo[i][j]存储[i,j]的最大值最小值结果，递归的时候如果发现memo[start][end]已经有结果了，则直接返回。代码如下： [cpp] struct T { double lfMax, lfMin; string strMax, strMin; }; class Solution { private: T optimal(vector<int>& nums, int start, int end, vector<vector<T>>& memo){ if(memo[start][end].strMax != "" || memo[start][end].strMin != "") return memo[start][end]; T t; if(start == end){ t.lfMax = t.lfMin = nums[start]; t.strMax = t.strMin = to_string(nums[start]); memo[start][end] = t; return t; } t.lfMax = std::numeric_limits<double>::min(); t.lfMin = std::numeric_limits<double>::max(); for(int i = start; i < end; ++i){ T tl = optimal(nums, start, i, memo); T tr = optimal(nums, i + 1, end, memo); if(tl.lfMax / tr.lfMin > t.lfMax){ t.lfMax = tl.lfMax / tr.lfMin; t.strMax = tl.strMax + "/" + (i + 1 != end ? "(" : "") + tr.strMin + (i + 1 != end ? ")" : ""); } if(tl.lfMin / tr.lfMax < t.lfMin){ t.lfMin = tl.lfMin / tr.lfMax; t.strMin = tl.strMin + "/" + (i + 1 != end ? "(" : "") + tr.strMax + (i + 1 != end ? ")" : ""); } } memo[start][end] = t; return t; } public: string optimalDivision(vector<int>& nums) { vector<vector<T>> memo(nums.size(), vector<T>(nums.size())); T t = optimal(nums, 0, nums.size() – 1, memo); return t.strMax; } }; [/cpp] 本代码提交AC，用时6MS。一下快了不少。 还有一种纯数学的方法。假设我们要对a/b/c/d加括号使得结果最大，则a肯定是分子不能动了，那么就相当于最小化b/c/d。b/c/d有两种加括号的方案：b/(c/d)和(b/c)/d。如果令b/(c/d)>b/c/d，因为b,c,d都是正数，推出d>1。又题目中的数据范围是[2,1000]，所以b/(c/d)>b/c/d显然成立。也就是b/c/d这种方案是最小的，使得a/(b/c/d)结果最大。所以只需要把a后面的数加一个括号整体括起来就好了。 代码如下： [cpp] class Solution { public: string optimalDivision(vector<int>& nums) { int n = nums.size(); if(n == 1) return to_string(nums[0]); else if(n == 2) return to_string(nums[0]) + "/" + to_string(nums[1]); string ans = to_string(nums[0]) + "/("; for(int i = 1; i < n – 1; ++i){ ans += to_string(nums[i]) + "/"; } return ans + to_string(nums[n-1]) + ")"; } }; [/cpp] 本代码提交AC，用时3MS。 参考：https://leetcode.com/articles/optimal-division/]]>

LeetCode 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:

1. The sum of node values in any subtree won’t exceed the range of 32-bit integer.
2. All the tilt values won’t exceed the range of 32-bit integer.

---

定义二叉树一个节点的tilt为其左子树元素之和与右子树元素之和的差的绝对值。整棵二叉树的tilt为所有节点的tilt之和。现在要求一棵二叉树的tilt。 简单题，递归求解元素之和，然后更新tilt。都是递归到叶子节点，然后累加和往父亲节点走。 代码如下： [cpp] class Solution { private: void dfs(TreeNode* root, int& sum, int& tilt){ if(root == NULL) { sum = 0; tilt = 0; } else { int lsum = 0, rsum = 0, ltilt = 0, rtilt = 0; dfs(root->left, lsum, ltilt); dfs(root->right, rsum, rtilt); sum = lsum + rsum + root->val; tilt = ltilt + rtilt + abs(lsum – rsum); } } public: int findTilt(TreeNode* root) { int sum = 0, tilt = 0; dfs(root, sum, tilt); return tilt; } }; [/cpp] 本代码提交AC，用时16MS。]]>

LeetCode Array Partition I Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a₁, b₁), (a₂, b₂), …, (a_n, b_n) which makes sum of min(a_i, b_i) for all i from 1 to n as large as possible. Example 1:

Input: [1,4,3,2]
Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4.

Note:

1. n is a positive integer, which is in the range of [1, 10000].
2. All the integers in the array will be in the range of [-10000, 10000].

---

给定一个长度为2n的数组，要求把数组分成n组，即(a₁, b₁), (a₂, b₂), …, (a_n, b_n) ，使得每组的最小值之和最大。 使用贪心策略，比如样例中，4和3肯定不能和1配对，因为1肯定是最小的，不能拿很大的数和1陪葬，所以只拿2和1配对；然后3、4配对。所以规律就是对数组排序，从小到大每两个配对。那么每组最小值之和就是第0、2、4…个数之和。 代码如下： [cpp] 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; } }; [/cpp] 本代码提交AC，用时92MS。]]>

LeetCode Student Attendance Record I You are given a string representing an attendance record for a student. The record only contains the following three characters:

1. ‘A’ : Absent.
2. ‘L’ : Late.
3. ‘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

---

给定一个学生出席字符串，P表示出席了，A表示未出席，L表示迟到。如果有超过1个A或者超过2个L，则该同学不能被评奖，否则可以。先给定一个字符串，问该同学能否被评奖。 简单题，一遍扫描，记录A的数量以及连续L的数量，根据规则判断就好。 代码如下： [cpp] class Solution { public: bool checkRecord(string s) { int n = s.size(); int A = 0, L = 0; for(size_t i = 0; i < n; ++i){ if(s[i] == ‘A’){ ++A; if(A > 1) return false; } else if(s[i] == ‘L’){ int tmp = 0; while(i < n && s[i] == ‘L’){ ++tmp; ++i; } –i; // caution L = max(tmp, L); if(L > 2) return false; } } return true; } }; [/cpp] 本代码提交AC，用时3MS。]]>

LeetCode Longest Uncommon Subsequence I Given a group of two strings, you need to find the longest uncommon subsequence of this group of two strings. The longest uncommon subsequence is defined as the longest subsequence of one of these strings and this subsequence should not be any subsequence of the other strings. A subsequence is a sequence that can be derived from one sequence by deleting some characters without changing the order of the remaining elements. Trivially, any string is a subsequence of itself and an empty string is a subsequence of any string. The input will be two strings, and the output needs to be the length of the longest uncommon subsequence. If the longest uncommon subsequence doesn’t exist, return -1. Example 1:

Input: "aba", "cdc"
Output: 3
Explanation: The longest uncommon subsequence is "aba" (or "cdc"),
because "aba" is a subsequence of "aba",
but not a subsequence of any other strings in the group of two strings.

Note:

1. Both strings’ lengths will not exceed 100.
2. Only letters from a ~ z will appear in input strings.

---

求两个字符串的最长非公共子序列。以前都是用DP求最长公共子序列，现在是要求最长非公共子序列。 其实很简单的一个题，如果两个字符串完全相等的话，肯定没有非公共子序列的，因为A字符串的任意一个子序列一定也是B字符串的子序列，所以返回-1。但是如果A和B不相等，则可以取A,B中较长的字符串，假设是A的话，则A肯定不是B的子序列，因为A的长度大于B，而且A不等于B。 所以就很简单了，如果A和B相等的话，返回-1，否则返回A,B中较大的长度。 代码如下： [cpp] class Solution { public: int findLUSlength(string a, string b) { return a == b ? -1 : max(a.size(), b.size()); } }; [/cpp] 本代码提交AC，用时0MS。]]>

LeetCode 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 1:

Input: "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"

Note: In the string, each word is separated by single space and there will not be any extra space in the string.

---

给定一个句子，要求把句子中的每个单词都逆序。 简单题，找空格，然后对每个单词reverse，直接调string::reverse或者自己写都可以。 代码如下： [cpp] class Solution { public: string reverseWords(string s) { int i = 0, j = 0, n = s.size(); while (j < n) { while (j < n&&s[j] != ‘ ‘)++j; reverse(s.begin() + i, s.begin() + j); i = ++j; } return s; } }; [/cpp] 本代码提交AC，用时23MS。]]>