字节跳动(社招)四面算法原题

TikTok 进展

又是一期定时汇报 TikTok 进展的推文。

上周,美国总统拜登签署了价值 950 亿美元的一揽子对外援助法案。

该法案涉及强制字节跳动剥离旗下应用 TikTok 美国业务,即 针对 TikTok 非卖即禁的"强抢行为"开始进入九个月(270 天)的倒计时

签署法案后,TikTok 官号进行了回应:

TikTok 在社交媒体上的回应(原文)
TikTok 在社交媒体上的回应(原文)
TikTok 在社交媒体上的回应(译文)
TikTok 在社交媒体上的回应(译文)

之后的几天,陆续出现过一些谣言,其中不乏「传字节跳动已经在密谋出售 TikTok 事宜」这样的消息。

但很快,就被官号高调辟谣了这些「外媒消息」:

alt

TikTok 代言人,也是现任 CEO 周受资也在海外社交媒体中出镜重申:我们哪儿也不去,准备起诉。事实和宪法都站在我们这一边,期待再次获胜。

alt

...

回归主线。

来一道和「字节跳动(社招)」四面相关的算法题。

据投稿人描述,当时其他问题回答得一般,但该算法题顺利做出,最终通过四面,感觉是被这道题救了一命。

题目描述

平台:LeetCode

题号:1879

给你两个整数数组 nums1nums2,它们长度都为 n

两个数组的 异或值之和 为 (nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + ... + (nums1[n - 1] XOR nums2[n - 1]) (下标从 0 开始)。

比方说,[1,2,3][3,2,1] 的 异或值之和 等于 (1 XOR 3) + (2 XOR 2) + (3 XOR 1) = 2 + 0 + 2 = 4

请你将 nums2 中的元素重新排列,使得异或值之和最小 。

请你返回重新排列之后的 异或值之和 。

示例 1:

输入:nums1 = [1,2], nums2 = [2,3]

输出:2

解释:将 nums2 重新排列得到 [3,2] 。
异或值之和为 (1 XOR 3) + (2 XOR 2) = 2 + 0 = 2 。

示例 2:

输入:nums1 = [1,0,3], nums2 = [5,3,4]

输出:8

解释:将 nums2 重新排列得到 [5,4,3] 。
异或值之和为 (1 XOR 5) + (0 XOR 4) + (3 XOR 3) = 4 + 4 + 0 = 8 。

提示:

状压 DP

这是一道「状压 DP」模板题。

为了方便,我们令下标从 开始。

「定义 为考虑前 个元素,且对 nums2 的使用情况为 时的最小异或值」。其中 是一个长度为 的二进制数:若 中的第 位为 ,说明 nums2[k] 已被使用;若 中的第 位为 ,说明 nums2[k] 未被使用。

起始时,只有 ,其余均为无穷大 INF 含义为在不考虑任何数,对 nums2 没有任何占用情况时,最小异或值为 。最终 即为答案。

不失一般性考虑 该如何转移,可以以 nums1[i] 是与哪个 nums2[j] 进行配对作为切入点:

  • 由于总共考虑了前 个成员,因此 的数量必然为 ,否则 就不是一个合法状态,跳过转移

  • 枚举 nums1[i] 是与哪一个 nums2[j] 进行配对的,且枚举的 需满足在 中的第 位值为 ,若满足则有

其中 prev 为将 中的第 位进行置零后的二进制数,即 prev = s ^ (1 << j),符号 ⊕ 代表异或操作。

Java 代码:

class Solution {
    public int minimumXORSum(int[] nums1, int[] nums2) {
        int n = nums1.length, mask = 1 << n, INF = 0x3f3f3f3f;
        int[][] f = new int[n + 10][mask];
        for (int i = 0; i <= n; i++) Arrays.fill(f[i], INF);
        f[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int s = 0; s < mask; s++) {
                if (getCnt(s, n) != i) continue;
                for (int j = 1; j <= n; j++) {
                    if (((s >> (j - 1)) & 1) == 0continue;
                    f[i][s] = Math.min(f[i][s], f[i - 1][s ^ (1 << (j - 1))] + (nums1[i - 1] ^ nums2[j - 1]));
                }
            }
        }
        return f[n][mask - 1];
    }
    int getCnt(int s, int n) {
        int ans = 0;
        for (int i = 0; i < n; i++) ans += (s >> i) & 1;
        return ans;
    }
}

C++ 代码:

class Solution {
public:
    int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), mask = 1 << n, INF = 0x3f3f3f3f;
        vector<vector<int>> f(n + 10vector<int>(mask, INF));
        f[0][0] = 0;
        auto getCnt = [&](int s, int n) {
            int ans = 0;
            for (int i = 0; i < n; i++) ans += (s >> i) & 1;
            return ans;
        };
        for (int i = 1; i <= n; i++) {
            for (int s = 0; s < mask; s++) {
                if (getCnt(s, n) != i) continue;
                for (int j = 1; j <= n; j++) {
                    if (((s >> (j - 1)) & 1) == 0continue;
                    f[i][s] = min(f[i][s], f[i - 1][s ^ (1 << (j - 1))] + (nums1[i - 1] ^ nums2[j - 1]));
                }
            }
        }
        return f[n][mask - 1];
    }
};

Python 代码:

class Solution:
    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:
        n, mask, INF = len(nums1), 1 << len(nums1), 0x3f3f3f3f
        f = [[INF] * mask for _ in range(n + 10)]
        f[0][0] = 0
        for i in range(1, n + 1):
            for s in range(mask):
                if sum([1 for i in range(n) if (s >> i) & 1]) != i:
                    continue
                for j in range(1, n + 1):
                    if ((s >> (j - 1)) & 1) == 0:
                        continue
                    f[i][s] = min(f[i][s], f[i - 1][s ^ (1 << (j - 1))] + (nums1[i - 1] ^ nums2[j - 1]))
        return f[n][mask - 1]

TypeScript 代码:

function minimumXORSum(nums1: number[], nums2: number[]): number {
    const n = nums1.length, mask = 1 << n, INF = 0x3f3f3f3f;
    const f: number[][] = new Array(n + 10).fill([]).map(() => new Array(mask).fill(INF));
    f[0][0] = 0;
    const getCnt = (s: number, n: number): number => {
        let ans = 0;
        for (let i = 0; i < n; i++) ans += (s >> i) & 1;
        return ans;
    };
    for (let i = 1; i <= n; i++) {
        for (let s = 0; s < mask; s++) {
            if (getCnt(s, n) !== i) continue;
            for (let j = 1; j <= n; j++) {
                if (((s >> (j - 1)) & 1) === 0continue;
                f[i][s] = Math.min(f[i][s], f[i - 1][s ^ (1 << (j - 1))] + (nums1[i - 1] ^ nums2[j - 1]));
            }
        }
    }
    return f[n][mask - 1];
};
  • 时间复杂度:
  • 空间复杂度:

模拟退火

事实上,这道题还能使用「模拟退火」进行求解。

由于我们可以无限次对 nums2 进行打乱互换,先来思考如何衡量一个 nums2 排列的“好坏”。

一个简单的方式:固定计算 (nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + ... + (nums1[n - 1] XOR nums2[n - 1]) 作为衡量当前 nums2 的得分,得分越小,当前的 nums2 排列越好。

迭代开始前先对 nums2 进行一次随机打乱,随后每个回合随机选择 nums2 的两个成员进行互换,并比较互换前后的得分情况,若互换后变好,那么保留该互换操作;若变差,则以一定概率进行重置(重新换回来)。

重复迭代多次,使用一个全局变量 ans 保存下最小异或值之和。

即「模拟退火」的单次迭代基本流程:

  1. 随机选择两个下标,计算「交换下标元素前对应序列的得分」&「交换下标元素后对应序列的得分」
  2. 如果温度下降(交换后的序列更优),进入下一次迭代
  3. 如果温度上升(交换前的序列更优),以「一定的概率」恢复现场(再交换回来)

对于一个能够运用模拟退火求解的问题,最核心的是如何实现 calc 方法(即如何定义一个具体方案的得分),其余均为模板内容。

Java 代码(2024/04/29 可过):

class Solution {
    int N = 400;
    double hi = 1e5, lo = 1e-5, fa = 0.90;
    Random random = new Random(20230823);
    void swap(int[] n, int a, int b) {
        int c = n[a];
        n[a] = n[b];
        n[b] = c;
    }
    int calc() {
        int res = 0;
        for (int i = 0; i < n; i++) res += n1[i] ^ n2[i];
        ans = Math.min(ans, res);
        return res;
    }
    void shuffle(int[] nums) {
        for (int i = n; i > 0; i--) swap(nums, random.nextInt(i), i - 1);
    }
    void sa() {
        shuffle(n2);
        for (double t = hi; t > lo; t *= fa) {
            int a = random.nextInt(n), b = random.nextInt(n);
            int prev = calc();
            swap(n2, a, b);
            int cur = calc(); 
            int diff = cur - prev; 
            if (Math.log(diff / t) >= random.nextDouble()) swap(n2, a, b);
        }
    }
    int[] n1, n2;
    int n;
    int ans = Integer.MAX_VALUE;
    public int minimumXORSum(int[] nums1, int[] nums2) {
        n1 = nums1; n2 = nums2;
        n = n1.length;
        while (N-- > 0) sa();
        return ans;
    }
}
  • 时间复杂度:启发式搜索不讨论时空复杂度
  • 空间复杂度:启发式搜索不讨论时空复杂度

最后

给大伙通知一下 📢 :

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

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

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

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

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

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

欢迎关注,明天见。

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/3019479.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

某云eHR PtFjk.mob 任意文件上传漏洞复现

0x01 产品简介 某云eHR是大中型企业广泛采用人力资源管理系统。红海云是国内顶尖的HR软件供应商,是新一代eHR系统的领导者。 0x02 漏洞概述 某云EHR系统PtFjk.mob接口处存在未授权文件上传漏洞,攻击者可上传webshell来命令执行,获取服务器权限。 0x03 复现环境 FOFA:b…

大模型市场爆发式增长,但生成式AI成功的关键是什么?

进入2024年&#xff0c;大模型市场正在爆发式增长。根据相关媒体的总结&#xff0c;2024年1-4 月被统计到的大模型相关中标金额已经达到2023年全部中标项目披露金额的77%左右&#xff1b;其中&#xff0c;从项目数量来看&#xff0c;应用类占63%、算力类占21%、大模型类占13%、…

交换机端口隔离

拓扑图 配置 port-isolate mode命令用来配置端口隔离模式。 缺省情况下&#xff0c;端口隔离模式为二层隔离三层互通。 端口隔离包括双向隔离和单向隔离。接口的单向隔离是指若在接口A上配置它与接口B隔离&#xff0c;则从接口A发送的报文不能到达接口B&#xff0c;但从接口…

MATLAB画图,重磅教程MATLAB的美图及强大的绘图功能|

目录 1.plot() 函数&#xff1a; 2.scatter() 函数&#xff1a; 3.histogram() 函数&#xff1a; 4.bar() 函数&#xff1a; 5.plot3() 函数&#xff1a; 6.imshow() 函数&#xff1a; 7.surf() 函数&#xff1a; 福利&#xff1a;免费送资料 MATLAB&#xff08;Matrix…

【基于 PyTorch 的 Python深度学习】5 机器学习基础(1)

前言 文章性质&#xff1a;学习笔记 &#x1f4d6; 学习资料&#xff1a;吴茂贵《 Python 深度学习基于 PyTorch ( 第 2 版 ) 》【ISBN】978-7-111-71880-2 主要内容&#xff1a;根据学习资料撰写的学习笔记&#xff0c;该篇主要介绍了机器学习的基本任务、机器学习的一般流程&…

第七章 TypeScript函数的介绍和使用

函数&#xff0c;一个再熟悉不过的话题了&#xff0c;之前几章里面我们也多次提到过&#xff0c;而且提到过各种各样的 TS 内和函数相关的内容今天&#xff0c;咱们来详细说一下函数内的各种详细内容的使用 文章目录 一、函数的可选参数二、函数内的虚拟 this三、函数的重载 一…

DInet

&#xff08;1&#xff09;数据&#xff1a; 1&#xff09;&#xff1a;随机获取5帧参考帧 2&#xff09;&#xff1a;处理这5帧连续帧&#xff0c;:source_frames:连续5帧的crop_moth b)audio_list:连续5帧的每一帧对应的5帧音频mel特征 c):refs:fintune 固定参考帧&#xff0…

懒洋洋作业讲解

懒洋洋作业讲解 环境配置 1.软件下载&#xff1a;DCloud - HBuilder、HBuilderX、uni-app、uniapp、5、5plus、mui、wap2app、流应用、HTML5、小程序开发、跨平台App、多端框架 2.软件介绍 HBuilder是由DCloud&#xff08;数字天堂&#xff09;推出的一款面向HTML5的Web开发…

【ArcGISPro】后台选项卡详解

添加后台选项卡 添加后的界面 文件变化 Config.daml修改内容对应文件详情 Classname就是我们在点击控件后具体执行的内容 BackstageTab1ViewModel与BackstageTab1 BackstageTabButton 1 执行效果 执行代码 读者直接往OnClick中添加执行的代码即可 尝试修改 代码 效果 Backs…

Java性能优化(一):Java基础-ArrayList和LinkedList

引言 集合作为一种存储数据的容器&#xff0c;是我们日常开发中使用最频繁的对象类型之一。JDK为开发者提供了一系列的集合类型&#xff0c;这些集合类型使用不同的数据结构来实现。因此&#xff0c;不同的集合类型&#xff0c;使用场景也不同。 很多同学在面试的时候&#x…

打破次元壁!Stable Diffusion将现实影像转成二次元动画,推特转赞10k+,网友:都可以重做《神奇宝贝》动漫了

破次元壁计划已启动&#xff01; 就在最近&#xff0c;有网友分享了一个用Stable Diffusion打造二次元动画的工具&#xff0c;直接在网上爆火。 先快来看一波效果。 万物皆可妙化为二次元&#xff0c;耳机也可蜕变成小兔兔&#xff1a; 瞧&#xff01;连易拉罐的拉环也化身成…

考研管理类联考(专业代码199)数学基础【3】函数、方程、不等式

一、函数 1.一次函数 y kx b(k≠0) 的图象及性质 2.二次函数y ax^2 bx c的图象和性质 3.指数函数y a^x &#xff08; a&#xff1e;0&#xff0c;且a≠1&#xff09;的图象和性质 4.对数函数y logₐx ( a&#xff1e;0&#xff0c;且a≠1)的图象与性质 二、方程 1.一元…

开抖音小店需要交多少保证金?全类目选择,一篇了解

哈喽~我是电商月月 做抖音小店前大家都会搜索“入驻抖音小店需要准备什么东西&#xff1f;”其中就包含了一项&#xff1a;类目保证金的缴纳 那到底要交多少钱&#xff1f;很多新手朋友还是不太了解 今天我就给大家解答这个问题&#xff0c;首先&#xff0c;我们要知道抖店的…

Mybatis 源码分析

《黑马架构师_源码系列-主流框架&中间件》-- MyBatis &#xff08;讲师&#xff1a;子慕&#xff09; * 手写持久层框架-仿写mybatis * Mybatis架构设计&主要组件 * Mybatis如何完成的初始化? * Mybatis如何完成的sql解析及执行? * Mybatis如何设置的参数? * Mybat…

List的两种实现

前置知识&#xff1a; 数组 baseAddress&#xff1a;数组的首地址 dataTypeSize&#xff1a;数组中元素类型的大小&#xff0c;如int为4字节 为什么数组索引从0开始&#xff0c;假如从1开始不行吗&#xff1f; 在根据数组索引获取元素的时候&#xff0c;会用索引和寻址公式来计…

网络安全之DHCP详解

DHCP&#xff1a;Dynamic Host Configration Protocol 动态主机配置协议 某一协议的数据是基于UDP封装的&#xff0c;当它想确保自己的可靠性时&#xff0c;这个协议要么选确认重传机制&#xff0c;要么选周期性传输。 DHCP是确认重传&#xff0c;【UDP|DHCP】,当DHCP分配完地…

这个Python库Streamlit,5分钟内搭建可视化WEB应用

在数据科学的世界里&#xff0c;将分析结果快速、直观地呈现给非技术背景的决策者&#xff0c;是一项重要的技能。而Streamlit&#xff0c;这个开源的Python库&#xff0c;正是为此而生。它允许数据科学家和工程师通过少量的代码&#xff0c;快速创建和分享数据应用。今天&…

citylava:城市场景中VLMs的有效微调

citylava:城市场景中VLMs的有效微调 摘要IntroductionRelated WorkVision-Language ModelsVLMs in Driving Methodology CityLLaVA: Efficient Fine-Tuning for VLMs in City Scenario 摘要 在城市广阔且动态的场景中&#xff0c;交通安全描述与分析在从保险检查到事故预防的各…

QGraphicsItem的prepareGeometryChange 和 update方法区别

prepareGeometryChange 这个函数用于为图形的几何形状变化做准备。在改变一个项目的边界矩形之前调用此函数&#xff0c;以保持 QGraphicsScene 的索引是最新的。如果必要的话&#xff0c;prepareGeometryChange() 会调用 update()。QGraphicsScene认为所有图元的boundingRect…

一个圈圈的机制玩法

什么是一个圈圈&#xff0c;说白了就是一个撸广告的平台&#xff0c;只是引入了减产机制&#xff0c;九维机制和分成机制&#xff0c;再加上有央企背景&#xff0c;做的一个区块链平台。 玩法很简单&#xff0c;就是撸广告获取能量&#xff0c;然后获取绿色能量&#xff0c;等…