专栏首页机器学习入门LeetCode Weekly Contest 31解题思路

LeetCode Weekly Contest 31解题思路

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u014688145/article/details/71204570

LeetCode Weekly Contest 31解题思路

详细代码可以fork下Github上leetcode项目,不定期更新。

赛题

本次周赛主要分为以下4道题:

  • 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].

水题,求有多少种不同的Candy,超过一半,姐姐分到不同的candy即为糖果总数的一半。代码如下:

    public int distributeCandies(int[] candies) {
        Set<Integer> set = new HashSet<>();
        for (int cand : candies){
            set.add(cand);
        }
        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相等。

判断两棵树是否相等: 1. 先序遍历&&中序遍历,如果遍历的顺序均一致,则说明两棵树相等。(该遍历丢弃了空结点的信息,如果序列化空结点,同样只需遍历一次。) 2. 直接递归比较,此法只需遍历一次。

我的代码:

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;
        list.add(root);
        preOrder(root.left, list);
        preOrder(root.right, list);
    }

    private void inOrder(TreeNode root, List<TreeNode> list){
        if (root == null) return;
        inOrder(root.left, list);
        list.add(root);
        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.

思路: 松鼠 ——> 坚果 ——> 树 树——> 坚果 ——> 树 树——> 坚果 ——> 树 …..

所以一旦到达了树,后续的路径累加无优化可言,单纯的全部累加即可。而唯一可以求min的地方就在于松鼠的初始位置。所以想法就是:min(松鼠到坚果再到树的路径长度),但遇到一个问题,如果有很多路线的长度均为最小值,那么此时需要遍历每种可能的路径求最小,所以代码如下:

    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:

思路: BFS,N减少一次,就踢出四个分身球,一旦被踢出边界,进行计数操作,可惜TLE了。代码如下:

    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 };
        Queue<int[]> queue = new LinkedList<>();
        queue.add(now);

        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;
    }

上述代码之所以会TLE,原因在于每当皮球踢到四个方向后,就把四个位置加入队列。如果没有踢出边界,那么每次都会扩展到原来的4倍,经过N轮后,它的时间复杂度为O(4N)O(4^N)。

优化的思路: 可以想象,经过N-1轮操作后,在m×nm\times n的空间里,会出现一个位置有多个球的情况,我们没必要一个个往四个方向踢,而是把这些皮球看成一个整体往四周踢。所以有必要在每轮踢球时,记录该位置皮球出现的次数,采用DP。

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...

    用户1147447
  • 挑战程序竞赛系列(81):4.3 LCA(1)

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

    用户1147447
  • 挑战程序竞赛系列(26):3.5二分图匹配(1)

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

    用户1147447
  • hdu---(1280)前m大的数(计数排序)

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

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

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

    Angel_Kitty
  • 【 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

    Ch_Zaqdt
  • 算法系列 图数据结构探索(无向图搜索)

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

    大数据和云计算技术
  • HDU 1878 欧拉回路

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

    用户2965768
  • HDU 5157 Harry and magic string(回文树)

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

    ShenduCC

扫码关注云+社区

领取腾讯云代金券