CourageHe's Blog

有勇须知方

0%

第 99 双周赛&第335场周赛

发表于 分类于
本文字数： 6k 阅读时长 ≈ 5 分钟

第 99 双周赛&第335场周赛

本周同时参加了第99场双周赛和第335场周赛，因此本文将两场比赛的题目一起整理如下！这次竞赛

第 99 场双周赛

双周赛解决了1，2题，第三题超时一直没解决。下次努力！

01.最小和分割

这是参赛时想出来的思路：

  1. num由0-9组合，用长度为10的数组存储数字数量，数组索引代表存储的数，值代表个数
  2. 将数组中存储的的的数字从0-9依次分配至builder1和builder2，
  3. 将两数字串解析为数字相加，即为答案！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution01 {
    public int splitNum(int num) {
        //统计各数字数量
        int[] nums = new int[10];
        int helper = num;
        while (helper >= 10) {
            nums[helper % 10]++;
            helper = helper / 10;
        }
        nums[helper % 10]++;
        //这里初始化0，以防Integer.valueOf传参为空字符串报错。
        StringBuilder builder1 = new StringBuilder("0");
        StringBuilder builder2 = new StringBuilder("0");
        for (int i = 1; i < nums.length;) {
            if (nums[i] == 0) {
                //i 对应的数量为0，分配下一个是数字
                i++;
                continue;
            } else if (builder1.length() < builder2.length()) {
                builder1.append(i);
            } else {
                builder2.append(i);
            }
            //数量减-1
            nums[i]--;
        }
        return Integer.valueOf(builder1.toString())+Integer.valueOf(builder2.toString());
    }
}

这是赛后参考大佬的解答：

佬似乎都喜欢使用lambda表达式，看起来非常简洁。

  1. 将nums转换为字符数组，并从小到大排序
  2. 将字符数组数字从前往后依次分配至num1和num2
  3. 将两数字相加，即为答案！
1
2
3
4
5
6
7
8
9
10
11
class Solution01_2 {
    public int splitNum(int num) {
        int[] nums = String.valueOf(num).chars().sorted().toArray();
        int num1 = 0,num2 = 0;
        for (int i = 0; i < nums.length; i++) {
            if(i%2== 0) num1 = num1*10+nums[i]-'0';
            else num2 = num2*10+nums[i]-'0';
        }
        return num1+num2;
    }
}

02.统计染色格子数

找规律咯！

1 <= n <= 10^5^，题目中已经给了取值范围，最大到100000，因此不可能采用建二维数组模拟的办法进行统计染色格子数。因此试试研究这个格子分钟数和格子数的关系，画出第4分钟的网格图，可数出25个格子。

分钟 染色格子
1 1
2 5
3 13
4 25

数字关系可以得到公式为：（n-1）^2^+n^2^ ==> 2n^2^+-2n+1

由于n是int类型，公式所求的值默认为int类型，需要强转为long类型。

1
2
3
4
5
6
7
class Solution02 {

    public long coloredCells(int n) {
        return (long) 2*n*n - 2*n + 1;
    }
}

03.统计将重叠区间合并成组的方案数

这是参赛时想出来的思路：

这种算法一直超时，采用BigInteger来模拟的想法时彻底错误的，BigInteger虽然可以存储超长的整数（超过long的长度），但是随着数值越大，运算也会变慢！像这种需要累乘的题目，一般都不能采用模拟的方式进行解答，而应该从乘数的因子入手。

思路：

  • 将ranges数组根据第一位的值从小到大排序
  • 统计ranges不属于一个组的数量count，ranges[i][1] < ranges[i+1][0]则代表两者之间为不同组
  • 统计完组的数量，根据题目描述的方式进行统计总方案数，实际上为count抓取[0,count]的排列组合

由于计算这个排列组合的值太大太繁琐了，无论如何优化都会超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.math.BigInteger;

class Solution03 {
  	public static int mod = 1000000007;//模数
    public int countWays(int[][] ranges) {
        //根据第一位的值从小到大排序
        Arrays.sort(ranges, (a, b) -> a[0] - b[0]);
        int count = 0;
       	for (int i = 0, j = -1; i < ranges.length; j = Math.max(j, ranges[i++][1])) {
            if (j < ranges[i][0]) count++;
        }

        BigInteger ans = BigInteger.ZERO;
        for (int i = 0; i <= count / 2; i++) {
            BigInteger temp = BigInteger.ONE;
            int num = count;
            for (int j = 1; j <= i; j++, num--) {
                temp = temp.multiply(BigInteger.valueOf(num)).divide(BigInteger.valueOf(j));
            }
            if (i == count / 2 && count % 2 == 0) {
                ans = (ans.add(temp)).divideAndRemainder(BigInteger.valueOf(mod))[1];
            } else {
                ans = (ans.add(temp.multiply(BigInteger.valueOf(2)))).divideAndRemainder(BigInteger.valueOf(mod))[1];
            }
        }
        return ans.intValue();
    }
}

这是赛后参考大佬的解答：

和上述解答思路类似，首先给ranges数组排序，然后统计组别数量，每新统计一个组别，原方案数量*2。

这个乘2倍怎来的呢？？？在超时难以解决的情况下，另辟蹊径，手动计算前几个数字的排列组合，统计得来。也有可能是一个数字公理！

1
2
3
4
5
6
7
8
9
10
11
12
class Solution03 {
  	public static int mod = 1000000007;//模数

     public int countWays(int[][] ranges) {
        Arrays.sort(ranges, (a, b) -> a[0] - b[0]);
        int count = 1;
        for (int i = 0, j = -1; i < ranges.length; j = Math.max(j, ranges[i++][1])) {
            count = j < ranges[i][0] ? count * 2 % mod : count;
        }
        return count;
    }
}

04.统计可能的树根数目

待做~

第335场周赛

周赛解决了1，2题，第三题超时也一直没解决。下次努力！！！

01.递枕头

找规律，根据题意容易得知，经过2(n-1)秒正投回到原点。因此首先将time取余得到num，这是决定关键走向的几秒。

1
2
3
4
5
6
class Solution01 {
    public int passThePillow(int n, int time) {
        int num =time % (2*(n-1));
        return (num < n ? num : (2*(n-1)-num)) +1;
    }
}

02.二叉树中的第 K 大层和

层序遍历，优先队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution02 {
      public long kthLargestLevelSum(TreeNode root, int k) {
        if (root == null) return -1;
        PriorityQueue<Long> pq = new PriorityQueue<Long>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            Long sum = 0l;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                sum = sum + (long) node.val;
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            pq.add(sum);
        }
        if (pq.size() < k) return -1;
        long ans = 0l;
        int size = pq.size();
        for (int i = 0; i <= size - k; i++) {
            ans = pq.poll();
        }
        return ans;

    }
}

03.分割数组使乘积互质

模拟！结果超时！如果所想的思路会导致long范围不够的话，一般都会超时，及时更改思路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution03 {
    public int findValidSplit(int[] nums) {
        BigInteger[] mul = getMultipy(nums, 0);
        if (gcd(mul[0], mul[1])) return 0;
        for (int i = 1; i < nums.length - 1; i++) {
            mul[0] = mul[0].multiply(BigInteger.valueOf(nums[i]));
            mul[1] = mul[1].divide(BigInteger.valueOf(nums[i]));
            if (gcd(mul[0], mul[1])) return i;
        }
        return -1;
    }

    public BigInteger[] getMultipy(int[] nums, int k) {
        BigInteger[] ans = {BigInteger.valueOf(1), BigInteger.valueOf(1)};
        for (int i = 0; i < nums.length; i++) {
            if (i <= k) ans[0] = ans[0].multiply(BigInteger.valueOf(nums[i]));
            else ans[1] = ans[1].multiply(BigInteger.valueOf(nums[i]));
        }
        return ans;
    }
 
    public boolean gcd(BigInteger num1, BigInteger num2) {
        if (num1.equals(1) || num2.equals(1)) return true;
        while (true) {
            BigInteger t = num1.divideAndRemainder(num2)[1];
            if (t.equals(BigInteger.valueOf(0))) {
                break;
            } else {
                num1 = num2;
                num2 = t;
            }
        }
        if (num2.compareTo(BigInteger.valueOf(1)) > 0) return false;
        else return true;

    }
}

竞赛结束后尝试的思路：

从乘数的因子出发，找出互质数的最小范围即可得到答案。

[0,max]之间的值不与后面的值存在公约数，那么两个范围的乘机就会互质！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution03 {
    public int findValidSplit(int[] nums) {
        if (nums.length == 1) return -1;
        //存在公约数的标志
        boolean[] arr = new boolean[nums.length];
        int max = nums.length - 1;
        for (int i = 0; i < max; i++) {
            if (arr[i]) continue;
            for (int j = arr[max] ? max + 1 : i + 1; j < nums.length; j++) {
                if (!gcd(nums[i], nums[j])) {
                    arr[j] = true;
                    max = j;
                }
            }
        }
        return arr[nums.length - 1] ? -1 : max;
    }

    /**
     * 用于判断num1 和 num2 是否互质，num2>1时num2为最小公约数，返回false；否则互质返回false;
     * @param num1
     * @param num2
     * @return
     */
    public boolean gcd(int num1, int num2) {
        if (num1 == 1 || num2 == 1) return true;
        while (true) {
            int t = num1 % num2;
            if (t == 0) {
                break;
            } else {
                num1 = num2;
                num2 = t;
            }
        }
        if (num2 > 1) return false;
        else return true;
    }
}

04.获得分数的方法数

待做~

-------------本文结束感谢您的阅读-------------
坚持原创技术分享，您的支持将鼓励我继续创作！

欢迎关注我的其它发布渠道