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

LeetCode Weekly Contest 47解题思路

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

LeetCode Weekly Contest 47解题思路

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

赛题

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

Leetcode 665. Non-decreasing Array

Problem:

Given an array with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element. We define an array is non-decreasing if array[i] <= array[i + 1] holds for every i (1 <= i < n).

Example 1:

Input: [4,2,3] Output: True Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

Example 2:

Input: [4,2,1] Output: False Explanation: You can’t get a non-decreasing array by modify at most one element.

Note:

The n belongs to [1, 10,000].

思路:直接检测出合法状态(说白了,就是找到合法状态的充分必要条件),开始构思。

第一:可以找寻所有arra[i] < arra[i - 1] 的状态,对其计数,所以很简单,如果非法状态>=2,直接return false.

可以想象,cnt = 0 ,说明arra是非递减的,一定合法,直接return true。

那么cnt = 1的情况呢?我是提交时才发现的问题,主要是因为单纯的计数cnt,有一种状态检测不出,即在检测到非法状态的下标j后,前数组满足非递减,后数组满足非递减,而删除j后,这两种状态不能合法叠加。

删除即合并,想复杂了,合并的情况直接考察是否满足即可,那么删除j还是删除j-1?如果删除j,这意味着j+1的元素和j-1的元素符合非递减,需要检测一波。如果删除j-1,需要检测j元素和j-2的元素是否符合非递减。

所以该问题就是两个步骤:找非法状态,非法状态太多,不符合,非法状态在指定范围内,检测能否合并,是个模拟啊!

代码如下:

    public boolean checkPossibility(int[] nums) {
        int n = nums.length;
        int cnt = 0;
        int j = -1;
        for (int i = 1; i < n; ++i){
            if (nums[i] < nums[i - 1]){
                cnt ++;
                j = i;
            }
        }

        if (cnt == 0) return true;
        if (cnt == 1){
            if (j == 1 || (j - 2 >= 0) && nums[j] >= nums[j - 2]) return true;
            if (j == n - 1 || (j + 1 < n) && nums[j + 1] >= nums[j - 1]) return true;
        }
        return false;
    }

discuss还有一种做法,代码简单,思路还是一个,只不过更有技巧性,巧妙的改变值,来替代合并操作。

也分为两种情况,要么i-2的元素比i小,要么比i大,比i小的将i-1改为i,比i大的将i改为i-1,接着再来检测。

代码如下:

    public boolean checkPossibility(int[] nums) {
        int n = nums.length;
        int cnt = 0;
        for (int i = 1; i < n; ++i){
            if (nums[i] < nums[i - 1]){
                cnt ++;
                if (i - 2 >= 0 && nums[i - 2] > nums[i]) nums[i] = nums[i - 1];
                else nums[i - 1] = nums[i];
            }
        }
        return cnt <= 1;
    }

Leetcode 666. Path Sum IV

Problem:

If the depth of a tree is smaller than 5, then this tree can be represented by a list of three-digits integers. For each integer in this list:

  • The hundreds digit represents the depth D of this node, 1 <= D <= 4.
  • The tens digit represents the position P of this node in the level it belongs to, 1 <= P <= 8. The position is the same as that in a full binary tree.
  • The units digit represents the value V of this node, 0 <= V <= 9.

Given a list of ascending three-digits integers representing a binary with the depth smaller than 5. You need to return the sum of all paths from the root towards the leaves.

Example 1:

Input: [113, 215, 221] Output: 12 Explanation: The tree that the list represents is: 3 / \ 5 1 The path sum is (3 + 5) + (3 + 1) = 12.

Example 2:

Input: [113, 221] Output: 4 Explanation: The tree that the list represents is: 3 \ 1 The path sum is (3 + 1) = 4.

思路: 这道题我的思路很暴力,从叶子结点开始搜索一条有效路径,并且累加,当然搜索路径的过程中,被访问过的结点一定不属于叶子结点,用一个visited数组记录,接着直到所有的叶子结点被访问过,程序结束。

至于如何访问叶子结点到根结点的路径,可以直接借用堆的建树规则。

我的初级代码如下:

    public int pathSum(int[] nums) {
        int sum = 0;
        int i = nums.length - 1;
        boolean[] leaf = new boolean[nums.length];
        Arrays.fill(leaf, true);
        while (i >= 0){
            if (leaf[i]){
                int val = nums[i] % 10;
                int pos = nums[i] / 10 % 10;
                int dep = nums[i] / 100;
                int layer = dep;
                sum += val;
                for (int k = 1; k < dep; ++k){
                    for (int j = i - 1; j >= 0; --j){
                        int pp = nums[j] / 10 % 10;
                        int vl = nums[j] % 10;
                        int ll = nums[j] / 100;
                        if ((pos + 1) / 2== pp && ll < layer){
                            leaf[j] = false;
                            sum += vl;
                            pos = pp;
                            layer = ll;
                            break;
                        }
                    }
                }
                i--;
            }
            else i--;
        }
        return sum;
    }

当然你可以用for循环,因为if和else都需要i–,所以代码如下:

    public int pathSum(int[] nums) {
        int sum = 0;
        int n = nums.length;
        boolean[] leaf = new boolean[nums.length];
        Arrays.fill(leaf, true);
        for (int i = n - 1; i >= 0; --i){
            if (leaf[i]){
                int val = nums[i] % 10;
                int pos = nums[i] / 10 % 10;
                int dep = nums[i] / 100;
                int layer = dep;
                sum += val;
                for (int k = 1; k < dep; ++k){
                    for (int j = i - 1; j >= 0; --j){
                        int pp = nums[j] / 10 % 10;
                        int vl = nums[j] % 10;
                        int ll = nums[j] / 100;
                        if ((pos + 1) / 2== pp && ll < layer){
                            leaf[j] = false;
                            sum += vl;
                            pos = pp;
                            layer = ll;
                            break;
                        }
                    }
                }
            }
        }
        return sum;
    }

当然,如果面对一棵大树,上述代码理论上还不够快,因为我们可以直接定位每一层的结点,思路还是一个,只是先用map记录层数和位置,接着拿到叶子结点后, 直接定位,代码如下:

    public int pathSum(int[] nums) {
        int sum = 0;
        int n = nums.length;

        boolean[][] nleaf = new boolean[5][12];

        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums){
            int val = num % 10;
            int pos = num / 10 % 10;
            int dep = num / 100;
            map.put(dep * 8 + pos, val);
        }

        for (int i = n - 1; i >= 0; --i){
                int val = nums[i] % 10;
                int pos = nums[i] / 10 % 10;
                int dep = nums[i] / 100;
                if (!nleaf[dep][pos]){
                    sum += val;
                    for (int k = 1; k < dep; ++k){
                        pos = (pos + 1 ) / 2;
                        int key = (dep - k) * 8 + pos;
                        nleaf[dep - k][pos] = true;
                        sum += map.get(key);
                    }
                }
        }
        return sum;
    }

当然map你也可以用一个二维数组做,这里就不写了,map更加直观。上述是迭代版本,你也可以用递归哟,这样就不需要记录是否为叶子结点咯。

Leetcode 667. Beautiful Arrangement II

Problem:

Given two integers n and k, you need to construct a list which contains n different positive integers ranging from 1 to n and obeys the following requirement: Suppose this list is [a1, a2, a3, … , an], then the list [|a1 - a2|, |a2 - a3|, |a3 - a4|, … , |an-1 - an|] has exactly k distinct integers. If there are multiple answers, print any of them.

Example 1:

Input: n = 3, k = 1 Output: [1, 2, 3] Explanation: The [1, 2, 3] has three different positive integers ranging from 1 to 3, and the [1, 1] has exactly 1 distinct integer: 1.

Example 2:

Input: n = 3, k = 2 Output: [1, 3, 2] Explanation: The [1, 3, 2] has three different positive integers ranging from 1 to 3, and the [2, 1] has exactly 2 distinct integers: 1 and 2.

Note:

The n and k are in the range 1 <= k < n <= 104.

思路: 此题其实很简单,因为k一定比n小,而我们知道,对于1toN的整数来说,最大的gap为n-1,所以当给定一个k时,一定优先满足k的gap,再满足k-1的gap,直到k=0。

这里可以证明下,假设某个数a,优先满足较小的gap,那么下一个数为a+k′a + k',再下一个数满足最大的k,则有a′=a+k′−ka' = a + k' - k,很显然a′<aa' < a,如果取a=1a = 1,则有a′<1a' < 1,属于非法状态。因此为了避免上述情况的发生,优先满足k,再k′k'。

那么,从哪个数开始构建数组呢?从a=1a = 1,因为当a=2,k=n−1a = 2, k = n - 1的情况出现时,会有2+n−1=n+12 + n - 1 = n + 1,也属于非法状态。所以有了从1开始,先加k,接着减(k - 1),直到k=0k = 0。

那么如何保证没有被安排的元素是否会出现新的gap?哈哈,其实也很好理解,因为在构造时,我们的策略是一加一减,把一加一减看成一个整体,两次操作,末尾元素+1,那么当迭代结束时,末尾元素为:1+(k+1)/2{1 + (k + 1) / 2},下一个被安排的元素为k+2k + 2,而它们之间的gap在[1,k]的范围之内。

举个简单的例子就能理解了:

n = 12, k = 5;
 +5-4+3-2+1
1 6 2 5 3 4 | 7 8 9 10 11 12

n = 12, k = 6;
 +6-5+4-3+2-1
1 7 2 6 3 5 4 | 8 9 10 11 12

所以代码如下:

    public int[] constructArray(int n, int k) {
        int[] ans = new int[n];
        ans[0] = 1;
        int j = 0;
        boolean[] used = new boolean[n + 1];
        used[1] = true;
        used[0] = true;
        while (k > 0){
            j ++;
            if (j % 2 != 0){
                ans[j] = ans[j - 1] + k;
                used[ans[j]] = true;
            }
            else{
                ans[j] = ans[j - 1] - k;
                used[ans[j]] = true;
            }
            k--;
        }

        for (int i = 1; i < used.length; ++i){
            if (!used[i]){
                ans[++j] = i;
            }
        }
        return ans;
    }

有了上述结论,这初级代码可以优化成:

    public int[] constructArray(int n, int k) {
        int[] ans = new int[n];
        ans[0] = 1;
        int j = 0;
        int iter = k;
        while (iter > 0){
            j ++;
            if (j % 2 != 0){
                ans[j] = ans[j - 1] + iter;
            }
            else{
                ans[j] = ans[j - 1] - iter;
            }
            iter--;
        }

        for (int i = k + 2; i <= n; ++i){
            ans[++j] = i;
        }
        return ans;
    }

Leetcode 668. Kth Smallest Number in Multiplication Table

Problem:

Nearly every one have used the Multiplication Table. But could you find out the k-th smallest number quickly from the multiplication table? Given the height m and the length n of a m * n Multiplication Table, and a positive integer k, you need to return the k-th smallest number in this table.

Example 1:

Input: m = 3, n = 3, k = 5 Output: Explanation: The Multiplication Table: 1 2 3 2 4 6 3 6 9 The 5-th smallest number is 3 (1, 2, 2, 3, 3).

Example 2:

Input: m = 2, n = 3, k = 6 Output: Explanation: The Multiplication Table: 1 2 3 2 4 6 The 6-th smallest number is 6 (1, 2, 2, 3, 4, 6).

Note:

  • The m and n will be in the range [1, 30000].
  • The k will be in the range [1, m * n]

二分题,还是挺简单的,对于每一行,对要猜的答案进行个数统计,kth-smallest的充分必要条件为:

  • 不超过x的数不少于k个
  • 小于x的数有不到k个

所以二分很好写,有点类似区间搜索,[lo, hi),其中lo满足 count(lo) < k,而count(hi) >= k,如何写count函数?对于每一行分别统计,一开始想用binarySearch,但没必要,统计函数为:cnt += Math.min(mid / i, n);

嘿嘿,整体代码如下:

    public int findKthNumber(int m, int n, int k) {
        int lo = 0, hi = 1000000000;
        while (hi - lo > 1){
            int mid = (lo + hi) / 2;
            int cnt = 0;
            for (int i = 1; i <= m; ++i){
                cnt += Math.min(mid / i, n);
            }
            if (cnt < k){
                lo = mid;
            }
            else{
                hi = mid;
            }
        }

        return hi;
    }

起初纠结 hi为什么是最终的答案,该答案一定会在m*n这张表里么?答案是一定的,因为if-else在更新mid时,始终满足lo < k && hi >= k,如果hi不在表里,那么计数器是不会increase的,那么自然的也不可能是这个答案了,所以只有hi在表格里时,counter才会增加。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 挑战程序竞赛系列(23):3.2折半枚举

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

    用户1147447
  • 挑战程序竞赛系列(21):3.2反转

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

    用户1147447
  • 挑战程序竞赛系列(19):3.1最小化第k大的值

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

    用户1147447
  • vs---错误收集并自己解决后归纳

    1。C++编译时,出现这样的错误 d:\program files\microsoft visual studio\vc98\include\stdio.h(3...

    Gxjun
  • 1545 最简单排序

    个人博客:double.win 1545 最简单排序  时间限制: 1 s  空间限制: 1000 KB  题目等级 : 青铜 Bronze 题解 题目描述 D...

    attack
  • P2658 汽车拉力比赛

    题目描述 博艾市将要举行一场汽车拉力比赛。 赛场凹凸不平,所以被描述为M*N的网格来表示海拔高度(1≤ M,N ≤500),每个单元格的海拔范围在0到10^9之...

    attack
  • BZOJ3143: [Hnoi2013]游走(期望DP 高斯消元)

    Description 一个无向连通图,顶点从1编号到N,边从1编号到M。  小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当...

    attack
  • #628 DIV2 题解

    组样例,每组给一个和个数 。将同一个序列重复次得到一个新序列,问可以从新序列中严格最长上升子序列长度为多少。

    ACM算法日常
  • 数组的简单练习题

    1.将一个给定的整型数组转置输出, 例如: 源数组,1 2 3 4 5 6 转置之后的数组,6 5 4 3 2 1

    阮键
  • cf1000F. One Occurrence(线段树 set)

    首先把询问离线,预处理每个数的\(pre, nxt\),同时线段树维护\(pre\)(下标是\(pre\),值是\(i\)),同时维护一下最大值

    attack

扫码关注云+社区

领取腾讯云代金券