讨论/题目交流/🏆 第 174 场力扣周赛/
🏆 第 174 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 方阵中战斗力最弱的 K 行
4 分 - 数组大小减半
5 分 - 分裂二叉树的最大乘积
6 分 - 跳跃游戏 V

展开讨论
  1. 方阵中战斗力最弱的 K 行
    方法:简单排序+统计,复杂度o(nlogn)o(nlogn)
    题解:就是维护一个二元组<军人个数,行号>,然后按题意排序一下就行了。
import java.util.Arrays;
import java.util.Comparator;

public class test4 {

    class Point
    {
        public int ju;
        public int row;

        public Point(int ju, int row) {
            this.ju = ju;
            this.row = row;
        }
    }

    class myCom implements Comparator<Point>
    {
        @Override
        public int compare(Point o1, Point o2) {

            if(o1.ju < o2.ju)
            {
                return -1;
            }
            else if(o1.ju == o2.ju)
            {
                if(o1.row < o2.row) return -1;
                return 1;
            }
            return 1;
        }
    }

    public int[] kWeakestRows(int[][] mat, int k) {


        Point[] point= new Point[mat.length];

        for(int i = 0;i < mat.length;i++)
        {
            int sum = 0;
            for(int j = 0;j < mat[i].length;j++)
            {
                if(mat[i][j] == 1) sum++;
            }
            point[i] = new Point(sum,i);
        }

        Arrays.sort(point,new myCom());

        int [] ans = new int[k];

        for(int i = 0;i < k;i++)
        {
            ans[i] = point[i].row;
//            System.out.println(ans[i]);
        }

        return ans;
    }

    public static void main(String[] args) {


        int[][]mat ={{1,1,0,0,0},
                {1,1,1,1,0},
                {1,0,0,0,0},
                {1,1,0,0,0},
                {1,1,1,1,1}};

        int k = 3;

        test4 of = new test4();
        System.out.println(of.kWeakestRows(mat,k));

    }
}
  1. 数组大小减半
    方法:简单统计+排序(贪心),复杂度O(nlogn)O(nlogn)
    题解:我没想多复杂,就是统计一下每个数的个数,然后排个序,从最大的个数开始减,直到满足length<arr.length/2length<arr.length/2
import java.util.*;

public class test5
{
    class MyCom implements Comparator<Integer>
    {

        @Override
        public int compare(Integer o1, Integer o2) {

            if(o1 > o2) return -1;
            else if(o1 < o2) return 1;
            return 0;
        }
    }

    public int minSetSize(int[] arr) {

        int ans = 0;
        int length = arr.length;
        Map<Integer,Integer> maps = new HashMap<>();

        for(int i = 0;i < arr.length;i++)
        {
            maps.put(arr[i],maps.getOrDefault(arr[i],0)+1);
        }

        int i = 0;
        Integer[] key = new Integer[maps.size()];
        Collection<Integer> as = maps.values();

        Iterator<Integer> it = as.iterator();
        while (it.hasNext())
        {
            key[i] = it.next();
            i++;
        }

        Arrays.sort(key,new MyCom());
        for(i = 0;i < key.length;i++)
        {
            length -= key[i];
            ans++;
            if(length<=(arr.length/2)) break;
        }

        return ans;
    }

    public static void main(String[] args) {

        test5 of = new test5();
        int[] arr = new int[]{1,2,3,4,5,6,7,8,9,10};
        System.out.println(of.minSetSize(arr));
    }
}
  1. 分裂二叉树的最大乘积
    方法:遍历,复杂度O(n)O(n)
    题解:首先计算整棵树的sumsum,然后从开始剪边,其实就是遍历一个节点的左右子树,同时得到子树的sonSum,这样就相当于剪边,然后计算sonSum*(sum-sonSum),找到最大值,要记得用long来存,否则会爆数。
public class test6
{
    private long max = 0;
    private final long mod = (int) (1e9+7);
    private long sum = 0;

    public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
    }

    int getsum(TreeNode root)
    {
        if(root == null) return 0;

        int left = getsum(root.left);
        int right = getsum(root.right);

        return left  + right + root.val;
    }


    long find(TreeNode root)
    {
        long tmp;
        if(root == null) return 0;

        long left = find(root.left);
        tmp = left * (sum - left);
        max = Math.max(tmp,max);

        long right = find(root.right);
        tmp = right * (sum - right);
        max = Math.max(tmp,max);

        return left + right + root.val;
    }

    public int maxProduct(TreeNode root) {

        sum = getsum(root);
        find(root);

        return (int)(max % mod);
    }


    public static void main(String[] args) {

        test6 of = new test6();
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);

        node1.right = node2;
        node2.left = node3;
        node2.right = node4;
        node4.left = node5;
        node4.right = node6;

        System.out.println(of.maxProduct(node1));

    }
}
  1. 跳跃游戏 V
    方法:dp,复杂度O(n2)O(n^2)
    题解:这道题我用滚动的数组来做,其实可以从题意上看出全局的点不管怎么跳,一定会达到一个收敛条件,就是所在的位置都不能再跳了,就代表收敛,所以dp[last][j]代表的是上一次跳动后,到达j点时最大次数dp[now][i]代表的是这次跳动后,到达i点时最大的次数,假设dp[last][j]=0的时候,这个点的在上一次没有跳过来,其实没必要再要这个点了;当dp[last][j]>0,说明这个点上一步有其他点跳过来了,那么尝试这次跳i=(j-d<=j<=j+d),如果能跳,状态转移就为dp[now][i]=dp[last][j]+1dp[now][i]=dp[last][j]+1
public class test7
{

    public void  clear(int[] arr,int val)
    {
        for(int i = 0;i < arr.length;i++) arr[i] = val;
    }

    public int maxJumps(int[] arr, int d) {

        int max = 1;
        int[][] dp = new int[2][arr.length];

        clear(dp[0],1);
        clear(dp[1],0);
        int now = 1;
        int last = now ^ 1;
        boolean flag = true;

        while (flag)
        {
            flag = false;

            for(int i = 0;i < dp[last].length;i++)
            {
                if(dp[last][i] == 0) continue;

                for(int j = i - 1,index = 0;j >= 0 && index < d;j--,index++)
                {
                    if(arr[i] <= arr[j]) break;

                    if(dp[last][i] + 1 > dp[now][j])
                    {
                        flag = true;
                        dp[now][j] = dp[last][i] + 1;
                        max = Math.max(dp[now][j],max);
                    }
                }

                for(int j = i + 1,index = 0;j < dp[last].length && index < d;j++,index++)
                {
                    if(arr[i] <= arr[j]) break;
                    if(dp[last][i] + 1 > dp[now][j])
                    {
                        flag = true;
                        dp[now][j] = dp[last][i] + 1;
                        max = Math.max(dp[now][j],max);
                    }
                }
            }
            now = now ^ 1;
            last = now ^ 1;
            clear(dp[now],0);
        }

        return max;
    }

    public static void main(String[] args) {
        test7 of = new test7();
        int[] arr = new int[]{6,4,14,6,8,13,9,7,10,6,12};
        int d = 2;
        System.out.println(of.maxJumps(arr,d));
    }
}
1
展开全部 18 讨论