LeetCode 1191
链接：https://leetcode.com/problems/k-concatenation-maximum-sum/
方法：前缀和、找规律
时间复杂度：O(n)
想法：其实主要是找规律。这个最大的和，要么是在一个数组当中，那么就是数组当中的最大子数组和（O(n)算法一直记录前面的最小前缀https://leetcode.com/problems/maximum-subarray/）。要么是两个数组拼在一起，这种情况下结果是原数组的最大前缀和加最大后缀和。要么是所有数组拼在一起，这种情况下结果是(k - 2) * sum + 原数组最大前缀和 + 原数组最大后缀和。所以说LeetCode有些题是真要仔细观察题目的规律，真要说算法这个题也没什么多复杂的算法。我当时周赛调到后面这个题也调出来了，但我那时候写的比较麻烦。我当时的错误在于还是没有对题目结果所能包含的所有结果想清楚，我记得我考虑到了上面说的第三种可能性，但我觉得第二种可能性会被包含在第三种里面，对应k=2的情况。但不是的，在k>2的情况下，第二种情况也可以独立成为最终的答案，第二种情况算出来的得数有可能比第三种算出来的还要大。
代码：
class Solution {
public int kConcatenationMaxSum(int[] arr, int k) {
long maxPre = 0, sum = 0, res = 0, minPre = 0;
long mod = 1000000007;
for (int a : arr) {
sum += a;
maxPre = Math.max(sum, maxPre);
minPre = Math.min(sum, minPre);
res = Math.max(res, sum - minPre);
}
if (k >= 2) {
res = Math.max(
res,
Math.max(
maxPre + sum - minPre,
sum * (k - 2) + maxPre + sum - minPre
)
);
}
return (int) (res % mod);
}
}
LeetCode 1382
链接：https://leetcode.com/problems/balance-a-binary-search-tree/
方法：BST性质
时间复杂度：O(n)，n为节点个数
想法：这个倒是比较简单。BST无非就是中序遍历有序，那如果想按题目的要求balance的话，比方说你有一个数组代表了一棵子树的中序遍历，那么根节点一定得选这个数组中间的那个点，然后左右子树分别再去建，这样的话对于这个根节点来说，它左子树和右子树的高度差就不会超过1。
代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode balanceBST(TreeNode root) {
List<TreeNode> nodes = new ArrayList<>();
inorder(root, nodes);
int n = nodes.size();
int index = (n - 1) / 2;
return build(root, nodes, 0, nodes.size() - 1);
}
private TreeNode build(TreeNode root, List<TreeNode> nodes, int l, int r) {
if (l > r) return null;
int m = l + (r - l) / 2;
TreeNode node = nodes.get(m);
node.left = build(root, nodes, l, m - 1);
node.right = build(root, nodes, m + 1, r);
return node;
}
private void inorder(TreeNode root, List<TreeNode> nodes) {
if (root == null) {
return;
}
inorder(root.left, nodes);
nodes.add(root);
inorder(root.right, nodes);
}
}
LeetCode 1143
链接：https://leetcode.com/problems/longest-common-subsequence/
方法：DP
时间复杂度：O(mn)，m、n分别为text1、text2的长度
想法：经典DP题目放送。双序列型DP。
代码：dp开二维数组，dp[i][j]表示text1前i个位置和text2前j个位置，它们的最长公共子序列是多长。转移到dp[i][j]时，如果i - 1和j - 1指向的字符相同，结果是dp[i - 1][j - 1] + 1，这个情况很简单。但如果这两个地方指向的字符不相同，那这个地方是对不上的，那就只能在dp[i - 1][j], dp[i][j - 1]里面取一个最大值。
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int n1 = text1.length(), n2 = text2.length();
int[][] dp = new int[n1 + 1][n2 + 1];
for (int i = 1; i <= n1; i++) {
for (int j = 1; j <= n2; j++) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
}
}
}
return dp[n1][n2];
}
}
