26 October 2019
LeetCode(49) -- 1013, 1018, 1021, 1022, 1029
by Jerry Zhang
P1013. Partition Array Into Three Parts With Equal Sum (Easy)
一个整数数组，问能否分成三份，使每一部分的和都相等。
我的思路
先把总和求出来，然后算出来1/3。然后依次遍历，看是否是出现三次这个目标值（总和的1/3）
我的代码
class Solution {
public boolean canThreePartsEqualSum(int[] A) {
int sum = 0;
for (int i : A) {
sum += i;
}
if (sum % 3 != 0) {
return false;
}
int oneThird = sum / 3;
int sum2 = 0;
int i = 0;
for (int j = 0; j < 2; j++) {
while (i < A.length && sum2 != oneThird) {
sum2 += A[i];
i++;
}
if (i == A.length) {
return false;
}
sum2 = 0;
}
while (i < A.length) {
sum2 += A[i];
i++;
}
return sum2 == oneThird;
}
}
100%
最优解
class Solution {
public boolean canThreePartsEqualSum(int[] A) {
int sum = 0;
for (int i : A) {
sum += i;
}
if (sum % 3 != 0) {
return false;
}
int target = sum / 3;
int cur_sum = 0;
int separation = 0;
for (int i : A) {
cur_sum += i;
if (cur_sum == target) {
separation++;
cur_sum = 0;
}
}
return (separation == 3) ? true : false;
}
}
答案的代码比我的好。我一开始担心分出三份后，最后还有一些数比如-6，6。其实没必要，因为只要分出来三份，每份的和都是三分之一，最后即使有剩余的，和也必然为0，不影响结果。
P1018. Binary Prefix Divisible By 5 (Easy)
一个只包含0或1的数组，N_i是指第i个substring从A[0]到A[i].
返回一个boolean的list，如果N_i能被5整除，返回true,否则返回false.
我的思路
一开始想把截止到当前的数累计加起来，然后查看是否能被5整除，结果越界了。因为数组长度为30000， 所以很容易越界。看了一眼答案，每次其实只需要保留余数即可。如果余数乘以2再加下一个数能被5整除，就能被5整除。
我的代码
class Solution {
public List<Boolean> prefixesDivBy5(int[] A) {
int curr = 0;
ArrayList<Boolean> ans = new ArrayList<>();
for (int i = 0; i < A.length; i++) {
curr = (int)(((curr * 2 ) + A[i]) % 5);
ans.add(curr == 0);
}
return ans;
}
}
100%
最优解
class Solution {
public List<Boolean> prefixesDivBy5(int[] A) {
if (A == null || A.length == 0) return null;
List<Boolean> result = new ArrayList<>();
int[] dp = new int[A.length];
dp[0] = A[0];
for (int i = 1; i < A.length; i++) {
dp[i] = ((dp[i - 1] << 1) + A[i]) % 5;
}
for (int i = 0; i < dp.length; i++) {
result.add(dp[i] == 0);
}
return result;
}
}
P1021. Remove Outermost Parentheses (Easy)
一个有效的括号字符串，移除每个部分最外层的括号
Input: "(()())(())"
Output: "()()()"
我的思路
每遇到一个完整的括号，就取中间的substring，拼接到最终结果中。
我的代码
class Solution {
public String removeOuterParentheses(String S) {
char[] chars = S.toCharArray();
StringBuilder sb = new StringBuilder();
int start = 1;
int primitive = 0;
for (int i = 0; i < chars.length && start < chars.length; i++) {
if (chars[i] == '(') {
primitive++;
} else if (chars[i] == ')') {
primitive--;
}
if (primitive == 0) {
String s = S.substring(start, i);
sb.append(s);
start = i + 2;
}
}
return sb.toString();
}
}
98%
最优解
class Solution {
public String removeOuterParentheses(String S) {
StringBuilder p = new StringBuilder();
char[] s = S.toCharArray();
int push_count = 0;
for(int i=0;i<s.length;i++){
if(s[i] == '('){
if(push_count>0)
p.append(s[i]);
++push_count;
}
else{
--push_count;
if(push_count>0)
p.append(s[i]);
}
}
return p.toString();
}
}
比我的方法好。每次只需要检查count是否是0即可确定是不是要加到里面。
P1022. Sum of Root To Leaf Binary Numbers (Easy)
一个二叉树，只包含0或1。从根节点到每个叶节点构成的一条路径，就组成了一个二进制的数。返回所有的二进制数的和。
我的思路
前序遍历，每到一个节点都保存到当前为止的路径累加的和。遇到叶节点，就添加到结果中。
我的代码
public class E_1022_SumOfRootToLeafBinaryNumbers {
int sum = 0;
public int sumRootToLeaf(TreeNode root) {
dfs(root, 0);
return sum;
}
private void dfs(TreeNode node, int sumOfParent) {
if (node == null) {
return;
}
if (node.left == null && node.right == null) {
sum += sumOfParent * 2 + node.val;
return;
}
dfs(node.left, sumOfParent * 2 + node.val);
dfs(node.right, sumOfParent * 2 + node.val);
}
}
100%
最优解
class Solution {
public int sumRootToLeaf(TreeNode root){
return dfs(root, 0);
}
private int dfs(TreeNode x, int val){
if (x == null) return 0;
val = val * 2 + x.val;
return (x.left == null && x.right == null)
? val
: dfs(x.left, val) + dfs(x.right, val);
}
}
P1025. Divisor Game (Easy)
两个人玩一个游戏，黑板上有一个数N。A先选一个x, 使得0 < x < N 同时x能被N整除。最后无法选择的人算输。
我的思路
递归，如果能选出一个数，然后剩下的数导致对方必败，则本方必胜。
答案
class Solution {
public boolean divisorGame(int N) {
return N % 2 == 0;
}
}
偶数必赢，奇数必输。
P1029. Two City Scheduling (Easy)
一个公司计划面试2N个人，第i个人去A城市的成本和B城市的成本，分别用cost[i][0]和cost[i][1]来表示。 A和B各分配N个人。求最小的成本总和。
我的思路
先算出来每个人去A和去B成本的差，用A-B。这个差就是我选择A的影响因子，数值越小，越应该选A。所以把difference排序，选出前N个人。
我的代码
public class E_1029_TwoCityScheduling {
public int twoCitySchedCost(int[][] costs) {
int sum = 0;
int[][] diff = new int[costs.length][2];
for (int i = 0; i < costs.length; i++) {
diff[i][0] = costs[i][0] - costs[i][1];
diff[i][1] = i;
}
Arrays.sort(diff, Comparator.comparingInt(o -> o[0]));
for (int i = 0; i < costs.length; i++) {
int index = diff[i][1];
if (i < costs.length / 2) {
sum += costs[index][0];
} else {
sum += costs[index][1];
}
}
return sum;
}
}
7%
最优解
class Solution {
public int twoCitySchedCost(int[][] costs) {
int N2 = costs.length;
int[] costs_new = new int[N2];
int ans = 0;
for (int i=0; i<N2; i++) {
costs_new[i] = costs[i][1] - costs[i][0];
ans += costs[i][0];
}
Arrays.sort(costs_new);
for (int i=0; i<(int)N2/2; i++) {
ans += costs_new[i];
}
return ans;
}
}
先把前所有人都选A，然后计算B-A，最后把B-A排序后，加回到总和里，也就是说，A + (B - A)就是对应的需要选B的那些人。
tags: LeetCode