# LeetCode Weekly Contest 29解题思路

## 赛题

• 563 Binary Tree Tilt (3分)
• 561 Array Partition I (6分)
• 562 Longest Line of Consecutive One in Matrix (8分)
• 564 Find the Closest Palindrome (10分)

## 563 Binary Tree Tilt

Problem:

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:

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

    public int findTilt(TreeNode root) {
dfs(root);
return sum;
}

int sum = 0;
private int dfs(TreeNode root) {
if (root == null)
return 0;
int left = dfs(root.left);
int right = dfs(root.right);
sum += Math.abs(left - right);
return root.val + left + right;
}

## 561 Array Partition I

Problem:

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

Example:

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

Note:

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

    public int arrayPairSum(int[] nums) {
Arrays.sort(nums);
int sum = 0;
for (int i = 0; i < nums.length; i += 2)
sum += nums[i];
return sum;
}

## 562 Longest Line of Consecutive One in Matrix

Problem:

Given a 01 matrix M, find the longest line of consecutive one in the matrix. The line could be horizontal, vertical, diagonal or anti-diagonal.

Example:

Input: [[0,1,1,0], [0,1,1,0], [0,0,0,1]] Output: 3

Hint:

The number of elements in the given matrix will not exceed 10,000.

public int longestLine(int[][] M) {
int row = M.length;
if (row == 0)
return 0;
int col = M[0].length;
if (col == 0)
return 0;

int[][][] dp = new int[row][col][4];

for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
dp[i][j][0] = M[i][j];
dp[i][j][1] = M[i][j];
dp[i][j][2] = M[i][j];
dp[i][j][3] = M[i][j];
}
}

int max = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {

if (j- 1 != -1 && M[i][j-1] == 1 && M[i][j] == M[i][j-1]){
dp[i][j][0] = dp[i][j-1][0] + 1;
max = Math.max(max, dp[i][j][0]);
}

if ((i != 0 && j != 0) && M[i-1][j-1] == 1 && M[i][j] == M[i-1][j-1]){
dp[i][j][1] = dp[i-1][j-1][1] + 1;
max = Math.max(max, dp[i][j][1]);
}

if (i != 0 && M[i-1][j] == 1 && M[i-1][j] == M[i][j]){
dp[i][j][2] = dp[i-1][j][2] + 1;
max = Math.max(max, dp[i][j][2]);
}

if ((i + 1 != row && j != 0) && M[i][j] == 1 && M[i][j] == M[i+1][j-1]){
dp[i+1][j-1][3] = dp[i][j][3] + 1;
max = Math.max(max, dp[i+1][j-1][3]);
}

max = Math.max(max, M[i][j]);
}
}

return max;
}
1. 用了个三维dp，其中第三维的[0,1,2,3]分别表示四种遍历方向，horizontal,vertical,diagonal和anti-diagonal
2. 注意越界问题，每种方向的遍历都可能导致不同的数组越界，需谨慎对待。

    public int longestLine(int[][] M) {
int row = M.length;
if (row == 0)
return 0;
int col = M[0].length;
if (col == 0)
return 0;

int[][][] dp = new int[row][col][4];

int max = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {

for (int k = 0; k < 4; k++) dp[i][j][k] = M[i][j];

if (j- 1 != -1 && M[i][j-1] == 1 && M[i][j] == M[i][j-1]){
dp[i][j][0] = dp[i][j-1][0] + 1;
}

if ((i != 0 && j != 0) && M[i-1][j-1] == 1 && M[i][j] == M[i-1][j-1]){
dp[i][j][1] = dp[i-1][j-1][1] + 1;
}

if (i != 0 && M[i-1][j] == 1 && M[i-1][j] == M[i][j]){
dp[i][j][2] = dp[i-1][j][2] + 1;
}

if ((i != 0 && j + 1 != col) && M[i-1][j+1] == 1 && M[i][j] == M[i-1][j+1]){
dp[i][j][3] = dp[i-1][j+1][3] + 1;
}

max = Math.max(max,Math.max(dp[i][j][0],dp[i][j][1]));
max = Math.max(max,Math.max(dp[i][j][2],dp[i][j][3]));

}
}

return max;
}

public boolean checkRecord(String s){
int countA = 0;
int countL = 0;

int maxL = 0;
for (int i = 0; i < s.length(); i++){
if (s.charAt(i) == 'A') countA ++;
countL = s.charAt(i) == 'L' ? countL + 1 : 0;
maxL = Math.max(maxL, countL);
}

if (countA > 1 || maxL > 2) return false;

return true;
}

public int longestLine(int[][] M) {
int row = M.length;
if (row == 0) return 0;
int col = M[0].length;
if (col == 0) return 0;

int max = 0;
for (int i = 0; i < row; i++){
for (int j = 0, hori = 0; j < col; j++){
hori = M[i][j] == 1 ? hori + 1 : 0;
max = Math.max(max, hori);
}
}

for (int j = 0; j < col; j++){
for (int i = 0, vert = 0; i < row; i++){
vert = M[i][j] == 1 ? vert + 1 : 0;
max = Math.max(max, vert);
}
}

for (int k = 0; k < row + col; k++){
for (int i = Math.min(k, row - 1), j = Math.max(0, k - row), diag = 0; i >= 0 && j < col; i--, j++) {
diag = M[i][j] == 1 ? diag + 1 : 0;
max = Math.max(max, diag);
}

for (int i = Math.max(row - 1 - k, 0), j = Math.max(0, k - row), anti = 0; i < row && j < col; j++, i++){
anti = M[i][j] == 1 ? anti + 1 : 0;
max = Math.max(max, anti);
}
}
return max;
}

## 564 Find the Closest Palindrome

Problem:

Given an integer n, find the closest integer (not including itself), which is a palindrome. The ‘closest’ is defined as absolute difference minimized between two integers.

Example:

Input: “123” Output: “121”

Note:

• The input n is a positive integer represented by string, whose length will not exceed 18.
• If there is a tie, return the smaller one as answer.

diff=∑i=017(xi−yi)×10i

diff = \sum_{i=0}^{17} (x_i-y_i) \times 10 ^ i

private long bigger (long u){
char[] origin = Long.toString(u).toCharArray();
int len = origin.length;
char[] palind = Arrays.copyOf(origin, len);

for (int i = 0; i < len / 2; i ++){
palind[len - 1 - i] = palind[i];
}

//检查生成的回文是否比原数大
for (int i = 0; i < len; i++){
if (origin[i] > palind[i]){
for (int j = (len-1) / 2; j >= 0; j--){
if (++palind[j] > '9'){
palind[j] = '0';
}else{
break;
}
}
for (int j = 0; j < len / 2; j++){
palind[len-j-1] = palind[j];
}
return Long.parseLong(new String(palind));

}else if (origin[i] < palind[i]){
return Long.parseLong(new String(palind));
}
}
return Long.parseLong(new String(palind));
}

private long smaller(long u) {
char[] origin = Long.toString(u).toCharArray();
int len = origin.length;
char[] palind = Arrays.copyOf(origin, len);
for (int i = 0; i < len / 2; i++) {
palind[len - 1 - i] = palind[i];
}
for (int i = 0; i < len; i++) {
if (origin[i] > palind[i]) {
return Long.parseLong(new String(palind));
} else if (origin[i] < palind[i]) {

for (int j = (len - 1) / 2; j >= 0; j--) {
if (--palind[j] < '0') {
palind[j] = '9';
} else {
break;
}
}

if(palind[0] == '0'){
if(palind.length == 1){
return 0;
}
palind = new char[len-1];
Arrays.fill(palind, '9');
return Long.parseLong(new String(palind));
}

for (int j = 0; j < len / 2; j++){
palind[len - j - 1] = palind[j];
}

return Long.parseLong(new String(palind));
}
}
return Long.parseLong(new String(palind));
}

public String nearestPalindromic(String n) {
long z = Long.parseLong(n);
long x = bigger(z + 1);
long y = smaller(z - 1);
if (x - z < z - y) return Long.toString(x);
else return Long.toString(y);
}

0 条评论

• ### LWC 56：718. Maximum Length of Repeated Subarray

LWC 56：718. Maximum Length of Repeated Subarray 传送门：718. Maximum Length of Repea...

• ### 挑战程序竞赛系列（41）：4.1中国剩余定理

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### LeetCode Weekly Contest 37解题思路

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### Golang Leetcode 581. Shortest Unsorted Continuous Subarray.go

a. 当我们找到第一个违反ascending 排序的数字 2的时候，我们不能是仅仅把beg 标记为2的前面一个数字7，而是要一直往前，找到一个合适的位置，找到在...

• ### codeforces 1366B（线段相交）

You are given an array consisting of n integers a1, a2, …, an. Initially ax=1, a...

• ### 挑战程序竞赛系列（41）：4.1中国剩余定理

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### 10个常见的 Java 错误及避免方法之第二集（后续持续发布）

当程序缺少关闭大括号（“}”）时，Java代码中就会发生此错误消息。 有时我们可以通过在代码的末尾放置大括号来快速修复错误。

• ### LeetCode Weekly Contest 37解题思路

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### 挑战程序竞赛系列（91）：3.6凸包（2）

挑战程序竞赛系列（91）：3.6凸包（2） 传送门：POJ 1113: Wall 题意参考hankcs： http://www.hankcs.com/pro...

• ### 763. Partition Labels

思路： 很暴力，直接找可以Partition的位置，如果不能Partition，继续向后搜索直到找到第一个可以Partition的位置为止，这样剩余问题就是...