# LeetCode Weekly Contest 31解题思路

## 赛题

• 575 Distribute Candies (4分)
• 572 Subtree of Another Tree (6分)
• 573 Squirrel Simulation (7分)
• 576 Out of Boundary Paths (9分)

## 575. Distribute Candies

Problem:

Given an integer array with even length, where different numbers in this array represent different kinds of candies. Each number means one candy of the corresponding kind. You need to distribute these candies equally in number to brother and sister. Return the maximum number of kinds of candies the sister could gain.

Example 1:

Input: candies = [1,1,2,2,3,3] Output: 3 Explanation: There are three different kinds of candies (1, 2 and 3), and two candies for each kind. Optimal distribution: The sister has candies [1,2,3] and the brother has candies [1,2,3], too. The sister has three different kinds of candies.

Example 2:

Input: candies = [1,1,2,3] Output: 2 Explanation: For example, the sister has candies [2,3] and the brother has candies [1,1]. The sister has two different kinds of candies, the brother has only one kind of candies.

Note:

• The length of the given array is in range [2, 10,000], and will be even.
• The number in given array is in range [-100,000, 100,000].

    public int distributeCandies(int[] candies) {
Set<Integer> set = new HashSet<>();
for (int cand : candies){
}
return Math.min(set.size(), candies.length / 2);
}

## 572. Subtree of Another Tree

Problem:

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.

Example 1:

Return true, because t has the same structure and node values with a subtree of s.

Example 2:

• 判断两棵树是否相等。
• 判断树s的子树是否和树t相等。

public boolean isSubtree(TreeNode s, TreeNode t) {
if (s == null && t == null) return true;

if (s == null) return false;

List<TreeNode> t1 = new ArrayList<>();
List<TreeNode> t2 = new ArrayList<>();

preOrder(t, t1);
inOrder(t, t2);

List<TreeNode> s1 = new ArrayList<>();
List<TreeNode> s2 = new ArrayList<>();

preOrder(s, s1);
inOrder(s, s2);

if (t1.size() == s1.size()){
for (int i = 0; i < t1.size(); i++){
if (t1.get(i).val != s1.get(i).val) return false;
}

for (int i = 0; i < t1.size(); i++){
if (t2.get(i).val != s2.get(i).val) return false;
}
return true;
}

return isSubtree(s.left, t) || isSubtree(s.right, t);
}

private void preOrder(TreeNode root, List<TreeNode> list){
if (root == null) return;
preOrder(root.left, list);
preOrder(root.right, list);
}

private void inOrder(TreeNode root, List<TreeNode> list){
if (root == null) return;
inOrder(root.left, list);
inOrder(root.right, list);
}

    public boolean isSubtree(TreeNode s, TreeNode t) {
if (t == null) return true;
if (s == null) return false;
return isSame(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
}

private boolean isSame(TreeNode s, TreeNode t){
if (s == null && t == null) return true;
if (s == null || t == null) return false;
return s.val == t.val && isSame(s.left, t.left) && isSame(s.right, t.right);
}

## 573. Squirrel Simulation

Problem:

There’s a tree, a squirrel, and several nuts. Positions are represented by the cells in a 2D grid. Your goal is to find the minimal distance for the squirrel to collect all the nuts and put them under the tree one by one. The squirrel can only take at most one nut at one time and can move in four directions - up, down, left and right, to the adjacent cell. The distance is represented by the number of moves.

Example 1:

Input: Height : 5 Width : 7 Tree position : [2,2] Squirrel : [4,4] Nuts : [[3,0], [2,5]] Output: 12 Explanation:

Note:

• All given positions won’t overlap.
• The squirrel can take at most one nut at one time.
• The given positions of nuts have no order.
• Height and width are positive integers. 3 <= height * width <= 10,000.
• The given positions contain at least one nut, only one tree and one squirrel.

    public int minDistance(int height, int width, int[] tree, int[] squirrel, int[][] nuts) {

int n = nuts.length;
int[] s2n = new int[n];
int[] t2s = new int[n];

int sum = 0;
for (int i = 0; i < n; i++) {
s2n[i] = distance(squirrel[0], squirrel[1], nuts[i][0], nuts[i][1]);
t2s[i] = distance(tree[0], tree[1], nuts[i][0], nuts[i][1]);
sum += t2s[i] * 2;
}

int min = Integer.MAX_VALUE;
for (int i = 0; i< n; i++){
min = Math.min(min, sum - t2s[i] + s2n[i]);
}
return min;
}

private int distance(int x1, int y1,int x2, int y2){
return Math.abs((x1 - x2)) + Math.abs((y1 - y2));
}

## 576. Out of Boundary Paths

Problem:

There is an m by n grid with a ball. Given the start coordinate (i,j) of the ball, you can move the ball to adjacent cell or cross the grid boundary in four directions (up, down, left, right). However, you can at most move N times. Find out the number of paths to move the ball out of grid boundary. The answer may be very large, return it after mod 10^9 + 7.

Example 1:

Input:m = 2, n = 2, N = 2, i = 0, j = 0 Output: 6 Explanation:

Example 2:

Input:m = 1, n = 3, N = 3, i = 0, j = 1 Output: 12 Explanation:

    public int findPaths(int m, int n, int N, int i, int j) {

int MOD = 1000000000 + 7;
int[][] directions = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

int[] now = { i, j, 0 };

int ans = 0;
while (!queue.isEmpty()) {
int[] tmp = queue.poll();
if (tmp[2] == N)
break;
for (int l = 0; l < 4; l++) {
int cur_i = tmp[0] + directions[l][0];
int cur_j = tmp[1] + directions[l][1];
if (cur_i == -1 || cur_i == m || cur_j == -1 || cur_j == n) {
if (cur_i == -1)
ans = (ans + 1) % MOD;
if (cur_i == m)
ans = (ans + 1) % MOD;
if (cur_j == -1)
ans = (ans + 1) % MOD;
if (cur_j == n)
ans = (ans + 1) % MOD;
continue;
}
queue.add(new int[] { cur_i, cur_j, tmp[2] + 1 });
}
}
return ans;
}

dp[i][j][k]： 表示在第k轮中，在位置(i,j)上，皮球出现的次数。

dp[i][j][k] = dp[i-1][j][k-1] + dp[i][j-1][k-1] + dp[i+1][j][k-1] + dp[i][j+1][k-1];

public int findPaths(int m, int n, int N, int i, int j) {

if (N == 0) return 0;

int MOD = 1000000000 + 7;
int[][][] dp = new int[m][n][N];

int[][] directions = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

dp[i][j][0] = 1;
for (int k = 1; k < N; k++){
for (int x = 0; x < m; x++){
for (int y = 0; y < n; y++){
for (int l = 0; l < 4; l++){
int curr_x = x + directions[l][0];
int curr_y = y + directions[l][1];
if (curr_x >=0 && curr_x < m && curr_y >= 0 && curr_y < n){
dp[x][y][k] = (dp[x][y][k] + dp[curr_x][curr_y][k - 1]) % MOD;
}
}
}
}
}

int[][] hh = new int[m][n];

for (int x = 0; x < m; x++){
for (int y = 0; y < n; y++){
for (int k = 0; k < N; k++){
hh[x][y] = (hh[x][y] + dp[x][y][k]) % MOD;
}
}
}

int ans = 0;
for (int k = 0; k < n; k++){
ans = (ans + hh[0][k]) % MOD;
ans = (ans + hh[m-1][k]) % MOD;
}

for (int k = 0; k < m; k++){
ans = (ans + hh[k][0]) % MOD;
ans = (ans + hh[k][n-1]) % MOD;
}

return ans;
}

    static int row;
static int col;

public int findPaths(int m, int n, int N, int i, int j) {

row = m;
col = n;

if (N == 0) return 0;

int MOD = 1000000000 + 7;
int[][][] dp = new int[m][n][N];

int[][] directions = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

dp[i][j][0] = 1;

int ret = 0;
for (int k = 1; k < N; k++){
for (int x = 0; x < m; x++){
for (int y = 0; y < n; y++){
for (int l = 0; l < 4; l++){
int curr_x = x + directions[l][0];
int curr_y = y + directions[l][1];
if (valid(curr_x, curr_y)){
dp[x][y][k] = (dp[x][y][k] + dp[curr_x][curr_y][k - 1]) % MOD;
}else{
ret += dp[x][y][k-1];
ret %= MOD;
}
}
}
}
}

for (int x = 0; x < m; x++){
for (int y = 0; y < n; y++){
for (int l = 0; l < 4; l++){
int curr_x = x + directions[l][0];
int curr_y = y + directions[l][1];
if (!valid(curr_x, curr_y)){
ret += dp[x][y][N-1];
ret %= MOD;
}
}
}
}

return ret;
}

private boolean valid(int x, int y){
return x >= 0 && x < row && y >= 0 && y < col;
}

0 条评论

• ### 挑战程序竞赛系列（36）：3.3线段树和平方分割

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

• ### 挑战程序竞赛系列（81）：4.3 LCA（1）

挑战程序竞赛系列（81）：4.3 LCA（1） 传送门：POJ 2763: Housewife Wind 题意： XX村里有n个小屋，小屋之间有双向可达的道...

• ### 挑战程序竞赛系列（26）：3.5二分图匹配（1）

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

• ### hdu---（1280）前m大的数（计数排序）

前m大的数 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Jav...

• ### POJ 1804 Brainman(5种解法，好题，【暴力】，【归并排序】，【线段树单点更新】，【树状数组】，【平衡树】)

Brainman Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 1057...

• ### 【 HDU - 4456 】Crowd (二维树状数组、cdq分治)

给你一个n行n列的格子，一开始每个格子值都是0。有M个操作，p=1为第一种操作，给格子(x,y)增加z。p=2为询问与格子(x,y)的曼哈顿距离不超过z的格子值...

• ### Codeforces Round #536 (Div. 2) D. Lunar New Year and a Wander(bfs)

题目链接：http://codeforces.com/contest/1106/problem/D

• ### 算法系列 图数据结构探索（无向图搜索）

算法是基础，小蓝同学准备些总结一系列算法分享给大家，这是第10篇《无向图搜索》，非常赞！希望对大家有帮助，大家会喜欢！

• ### HDU 1878 欧拉回路

#include <bits/stdc++.h> using namespace std; const int N=1005; int in[N]; i...

• ### HDU 5157 Harry and magic string(回文树)

Harry and magic string Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: ...