• 抖音 UG 社招一面算法原题


    史上最严热点新机制

    或许是受到前段时间「巴黎丢作业」的影响,抖音近日(5月27日)实施了新的热点内容核实机制。

    具体来说,若用户在抖音以热点事件当事人身份发声,抖音将联系当事人进行身份认证。

    逾期未认证的用户,抖音将采取包括强提醒标注、禁言等一系列措施,直至用户提供可信材料。

    同时,对于演绎类内容,抖音要求发布者必须显著标注"虚构演绎"声明,对于部分疑似摆拍的热点内容,抖音称将主动请求各地相关部门核实或联动各地新闻机构调查。

    如此一来,基本上是把"造谣骗流量"的车门焊死了,但这也将大大增加抖音方面的运营成本。

    个人感觉:初心很好,但如果严格按照上述说的来做,其实很难达到好的效果。

    从以前的「纯算法」到现在的「人工介入」,以及认证材料的合理性,再到标记的及时性,都可能会让内容平台呈现的效果大打折扣。

    要知道,一个视频如果因为新规则晚了半天进入流量池,可能就已经错过了最佳传播时间了。

    而且任何打击类的新规则,也都无法避免的误伤问题。

    对于抖音提出的「史上最严热点新机制」,你怎么看?

    ...

    回归主题。

    来一道和「字节跳动」相关的题目。

    题目描述

    平台:LeetCode

    题号:907

    给定一个整数数组 arr,找到 min(b) 的总和,其中 b 的范围为 arr 的每个(连续)子数组。

    由于答案可能很大,因此 返回答案模

    示例 1:

    输入:arr = [3,1,2,4]

    输出:17

    解释:
    子数组为 [3],[1],[2],[4],[3,1],[1,2],[2,4],[3,1,2],[1,2,4],[3,1,2,4]。 
    最小值为 3,1,2,4,1,1,2,1,1,1,和为 17。

    示例 2:

    输入:arr = [11,81,94,43,3]

    输出:444

    提示:

    单调栈 + 数学

    原问题为求所有子数组的最小值之和。

    统计所有子数组需要枚举左右端点,复杂度为 ,对于每个子数组,我们还需要通过线性扫描的方式找到其最小值,复杂度为 ,因此朴素解法的整体复杂度为 ,题目给定数据范围为 ,会 TLE

    由于我们是从子数组中取最小值来进行累加,即参与答案构成的每个数必然某个具体的

    「因此我们可以将原问题转化为「考虑统计每个 对答案的贡献」。」

    对于某一个 而言,我们考虑其能够作为哪些子数组的最小值。

    我们可以想象以 为中心,分别往两端进行拓展,只要新拓展的边界不会改变「 为当前子数组的最小值」的性质即可。

    换句话说,我们需要找到 作为最小值的最远左右边界,即找到 左右最近一个比其小的位置 lr

    「在给定序列中,找到任意 最近一个比其大/小的位置,可使用「单调栈」进行求解。」

    到这里,我们会自然想到,通过单调栈的方式,分别预处理除 lr 数组:

    • l[i] = loc 含义为下标 i 左边最近一个比 arr[i] 小的位置是 loc(若在 左侧不存在比其小的数,则 loc = -1
    • r[i] = loc 含义为下标 i 右边最近一个比 arr[i] 小的位置是 loc(若在 左侧不存在比其小的数,则 loc = n

    当我们预处理两数组后,通过简单「乘法原理」即可统计以 为最小值时,子数组的个数:

    • 包含 的子数组左端点个数为
    • 包含 的子数组右端点个数为

    子数组的个数 X 子数组最小值 ,即是当前 对答案的贡献:

    「统计所有 对答案的贡献即是最终答案,但我们忽略了「当 arr 存在重复元素,且该元素作为子数组最小值时,最远左右端点的边界越过重复元素时,导致重复统计子数组」的问题。」

    我们不失一般性的举个 🌰 来理解(下图):

    alt

    为了消除这种重复统计,我们可以将「最远左右边界」的一端,从「严格小于」调整为「小于等于」,从而实现半开半闭的效果。

    Java 代码:

    class Solution {
        int MOD = (int)1e9+7;
        public int sumSubarrayMins(int[] arr) {
            int n = arr.length, ans = 0;
            int[] l = new int[n], r = new int[n];
            Arrays.fill(l, -1); Arrays.fill(r, n);
            Deque d = new ArrayDeque<>();
            for (int i = 0; i < n; i++) {
                while (!d.isEmpty() && arr[d.peekLast()] >= arr[i]) r[d.pollLast()] = i;
                d.addLast(i);
            }
            d.clear();
            for (int i = n - 1; i >= 0; i--) {
                while (!d.isEmpty() && arr[d.peekLast()] > arr[i]) l[d.pollLast()] = i;
                d.addLast(i);
            }
            for (int i = 0; i < n; i++) {
                int a = i - l[i], b = r[i] - i;
                ans += a * 1L * b % MOD * arr[i] % MOD;
                ans %= MOD;
            }
            return ans;
        }
    }

    C++ 代码:

    class Solution {
    public:
        int MOD = 1e9 + 7;
        int sumSubarrayMins(vector<int>& arr) {
            int n = arr.size(), ans = 0;
            vector<intl(n, -1)r(n, n);
            stack<int> d;
            for (int i = 0; i < n; i++) {
                while (!d.empty() && arr[d.top()] >= arr[i]) {
                    r[d.top()] = i;
                    d.pop();
                }
                d.push(i);
            }
            while (!d.empty()) d.pop();
            for (int i = n - 1; i >= 0; i--) {
                while (!d.empty() && arr[d.top()] > arr[i]) {
                    l[d.top()] = i;
                    d.pop();
                }
                d.push(i);
            }
            for (int i = 0; i < n; i++) {
                long long a = i - l[i], b = r[i] - i;
                ans = (ans + a * b % MOD * arr[i] % MOD) % MOD;
            }
            return ans;
        }
    };

    Python 代码:

    class Solution:
        def sumSubarrayMins(self, arr: List[int]) -> int:
            n, ans = len(arr), 0
            l, r = [-1] * n, [n] * n
            stk = []
            for i in range(n):
                while stk and arr[stk[-1]] >= arr[i]:
                    r[stk.pop()] = i
                stk.append(i)
            stk = []
            for i in range(n - 1-1-1):
                while stk and arr[stk[-1]] > arr[i]:
                    l[stk.pop()] = i
                stk.append(i)
            for i in range(n):
                a, b = i - l[i], r[i] - i
                ans += a * b * arr[i]
            return ans % (10 ** 9 + 7)

    TypeScript 代码:

    const MOD = 1000000007
    function sumSubarrayMins(arr: number[]): number {
        let n = arr.length, ans = 0
        const l = new Array<number>(n).fill(-1), r = new Array<number>(n).fill(n)
        const stk = new Array<number>(n).fill(0)
        let he = 0, ta = 0
        for (let i = 0; i < n; i++) {
            while (he < ta && arr[stk[ta - 1]] >= arr[i]) r[stk[--ta]] = i
            stk[ta++] = i
        }
        he = ta = 0
        for (let i = n - 1; i >= 0; i--) {
            while (he < ta && arr[stk[ta - 1]] > arr[i]) l[stk[--ta]] = i
            stk[ta++] = i
        }
        for (let i = 0; i < n; i++) {
            const a = i - l[i], b = r[i] - i
            ans += a * b % MOD * arr[i] % MOD
            ans %= MOD
        }
        return ans
    }
    • 时间复杂度:
    • 空间复杂度:

    优化

    实际上,当我们从栈中弹出某个 时,其右边界必然是导致其弹出的 arr[r](当前所遍历到的元素),而 若存在左边界,必然是位于 栈中的前一位置,即 弹出后的新栈顶元素(若不存在物理左边界,则左边界为 )。

    Java 代码:

    class Solution {
        int MOD = (int)1e9+7;
        public int sumSubarrayMins(int[] arr) {
            int n = arr.length, ans = 0;
            Deque d = new ArrayDeque<>();
            for (int r = 0; r <= n; r++) {
                int t = r < n ? arr[r] : 0;
                while (!d.isEmpty() && arr[d.peekLast()] >= t) {
                    int cur = d.pollLast();
                    int l = d.isEmpty() ? -1 : d.peekLast();
                    int a = cur - l, b = r - cur;
                    ans += a * 1L * b % MOD * arr[cur] % MOD;
                    ans %= MOD;
                }
                d.addLast(r);
            }
            return ans;
        }
    }

    C++ 代码:

    class Solution {
    public:
        int MOD = 1e9 + 7;
        int sumSubarrayMins(vector<int>& arr) {
            int n = arr.size(), ans = 0;
            deque<int> d;
            for (int r = 0; r <= n; r++) {
                int t = (r < n) ? arr[r] : 0;
                while (!d.empty() && arr[d.back()] >= t) {
                    int cur = d.back();
                    d.pop_back();
                    int l = d.empty() ? -1 : d.back();
                    long long a = cur - l, b = r - cur;
                    ans = (ans + a * b % MOD * arr[cur] % MOD) % MOD;
                }
                d.push_back(r);
            }
            return ans;
        }
    };

    Python 代码:

    class Solution:
        def sumSubarrayMins(self, arr: List[int]) -> int:
            n, ans = len(arr), 0
            stk = []
            for r in range(n + 1):
                t = arr[r] if r < n else 0
                while stk and arr[stk[-1]] >= t:
                    cur = stk.pop()
                    l = stk[-1if stk else -1
                    a, b = cur - l, r - cur
                    ans += a * b * arr[cur]
                stk.append(r)
            return ans % (10 ** 9 + 7)

    TypeScript 代码:

    const MOD = 1000000007
    function sumSubarrayMins(arr: number[]): number {
        let n = arr.length, ans = 0
        const stk = new Array<number>(n).fill(0)
        let he = 0, ta = 0
        for (let r = 0; r <= n; r++) {
            const t = r < n ? arr[r] : 0
            while (he < ta && arr[stk[ta - 1]] >= t) {
                const cur = stk[--ta]
                const l = he < ta ? stk[ta - 1] : -1
                const a = cur - l, b = r - cur
                ans += a * b % MOD * arr[cur] % MOD
                ans %= MOD
            }
            stk[ta++] = r
        }
        return ans
    }
    • 时间复杂度:
    • 空间复杂度:

    最后

    给大伙通知一下 📢 :

    全网最低价 LeetCode 会员目前仍可用 ~

    📅 年度会员:有效期加赠两个月!!; 季度会员:有效期加赠两周!!

    🧧 年度会员:获 66.66 现金红包!!; 季度会员:获 22.22 现金红包!!

    🎁 年度会员:参与当月丰厚专属实物抽奖(中奖率 > 30%)!!

    专属链接:leetcode.cn/premium/?promoChannel=acoier

    我是宫水三叶,每天都会分享算法知识,并和大家聊聊近期的所见所闻。

    欢迎关注,明天见。

    更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉

  • 相关阅读:
    Java底层面试知识学习
    什么是网络流量监控
    Qt图形视图、动画框架
    【C语言小游戏】详解三子棋,深刻掌握二维数组
    纷享销客数字化营销(一):企业专属微站和员工智能名片
    Hbase 之KeyValue结构详解
    redis未授权与权限获取
    STM32实战总结:HAL之modbus
    fastapi_No.14_中间件
    头歌-信息安全技术-用Python实现自己的区块链、支持以太坊的云笔记服务器端开发、编写并测试用于保存云笔记的智能合约、支持以太坊的云笔记小程序开发基础
  • 原文地址:https://blog.csdn.net/weixin_33243821/article/details/139324246