字节前端实习的两道算法题,看看强度如何

最长严格递增子序列
题目描述
给你一个整数数组nums,找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例:
输入:nums = [2,1,6,3,5,4]
输出:3
解释:最长递增子序列是 [1,3,4],因此长度为 3。
思路
这道题要求最长上升子序列的长度,可以使用动态规划或贪心+二分查找两种方法来解决。
-
动态规划
定义状态:dp[i]表示以第i个元素为结尾的最长上升子序列的长度。
状态转移方程:对于第i个元素,枚举其前面的元素j,如果nums[i] > nums[j],则dp[i] = dp[j] + 1。同时,在每次更新dp[i]时,更新ans为其最大值。 -
贪心+二分查找
定义一个数组d,d[i]记录长度为i的上升子序列的末尾元素的最小值。对于一个新的元素num[i],如果num[i]大于d[len],说明可以扩展当前的最长上升子序列,直接将其加入到d中;否则在d中查找第一个大于等于num[i]的元素位置pos,用num[i]替换它,使得可以扩展更长的上升子序列。
两种方法的时间复杂度分别为O(n^2)和O(nlogn),空间复杂度都是O(n)。
代码
// 方法一:动态规划:时间复杂度O(n^2) 空间复杂度O(n)
var lengthOfLIS = function(nums) {if(nums.length === 0) return 0const dp = new Array(nums.length).fill(1)let ans = 1;for(let i = 1 ; i < nums.length; i ++) {for(let j = 0 ; j < i ; j ++) {if(nums[i] > nums[j]) {dp[i] = Math.max(dp[i],dp[j] + 1);}}ans = Math.max(dp[i],ans);}console.log(dp);return ans;
}; // 方法二:贪心+二分查找:时间复杂度O(nlogn) 空间复杂度O(n)
var lenghtOfLIS = function(nums) {let n = nums.length;if(n === 0) return 0;let d = new Array(n + 1).fill(0);let len = 1;d[len] = nums[0];for(let i = 1; i < n ; i ++) {if(num[i] > d[len]) {d[++len] = nums[i];} else {let l = 1 , r = len , pos = 0;while(l <= r) {let mid = (l + r) >> 1;if(d[mid] < num[i]) {pos = mid;l = mid + 1;} else {r = mid - 1;}}d[pos + 1] = nums[i];}}return len;
}
路径总和 II
题目描述
给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
输入:nums = [10,9,2,5,3,7,101,18]
输出:4
解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。
思路
我们可以采用深度优先搜索的方式,枚举每一条从根节点到叶子节点的路径。当我们遍历到叶子节点,且此时路径和恰为目标和时,我们就找到了一条满足条件的路径。
代码
var pathSum = function(root, target) {let ans = [],path = [];let dfs = (root,target) => {if(!root) return;path.push(root.val);target -= root.val;if(root.left === null && root.right === null && target === 0) {ans.push([...path]);}dfs(root.left,target);dfs(root.right,target);path.pop(root.val);}dfs(root,target);return ans;
};
相关文章:
字节前端实习的两道算法题,看看强度如何
最长严格递增子序列 题目描述 给你一个整数数组nums,找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7…...
设计模式—策略模式
目录 一、定义 二、特点 三、优点 四、缺点 五、实例 六.涉及到的知识点 1、一个类里面有哪些东西? 2、类和实例 什么是类? 什么是实例? 什么是实例化? 3、字段和属性 什么是字段? 属性是什么࿱…...
LPDDR4、DDR4
核心信息: 2400Mbps(每秒传输2400*1百万bit) 2400MT/s(百万次/秒) 信号...
ESP32C3 LuatOS RC522①写入数据并读取M1卡
LuatOS RC522官方示例 官方示例没有针对具体开发板,现以ESP32C3开发板为例。 选用的RC522模块 ESP32C3-CORE开发板 注意ESP32C3的 SPI引脚位置,SPI的id2 示例代码 -- LuaTools需要PROJECT和VERSION这两个信息 PROJECT "helloworld" VERSIO…...
MusicBrainz Picard for Mac :音乐文件ID3编辑器
MusicBrainz Picard for Mac是一款macOS平台的音乐文件ID3编辑器,能够帮助我们在Mac电脑上编辑音乐文件的ID3标签信息,包括艺人、专辑等信息,非常快速和简单方便。Picard是下一代MusicBrainz标记应用程序。 这个新的标签概念是面向专辑的&…...
❤ Uniapp使用
❤ Uniapp使用 一、介绍 uni-app官网:https://uniapp.dcloud.io/api/media/image?idpreviewimage 微信小程序官网:https://developers.weixin.qq.com/miniprogram/dev/api/media/image/wx.previewImage.html 二、使用 1、uniapp 实现图片预览 单图预…...
解密Spring事务生效的内部机制
声明式事务和编程式事务对比: 声明式事务: 使用注解或XML配置的方式,在代码中声明事务的属性和行为。通过AOP和代理模式实现,将事务管理与业务逻辑代码解耦。适用于大多数情况,简化了代码,提高了可维护性和…...
大数据时代下的数据安全防护
随着大数据时代的来临,数据安全防护成为了一个重要的问题。在大数据时代,数据的规模和价值都得到了极大的提升,因此数据安全的重要性也变得越来越突出。本文将从数据加密、访问控制、网络安全和人员管理四个方面来介绍大数据时代下的数据安全…...
RabbitMQ-常用命令
RabbitMQ常用命令 3.1 启动停止rabbitMQ命令 # 前台启动Erlang VM 和 RabbitMQ 当窗口关闭或者ctrlc时,使退出了。 rabbitmq-server# 使用系统命令启动 systemctl start rabbitmq-server# 后台启动 rabbitmq-server -detached# 停止rabbitMQ和Erlang VM rabbitmq-…...
Spring中依赖注入的继承bean的细节问题
介绍 有时我们会对一种类型的bean进行继承,在Spring生成bean的时候,返回类型有时是子类类型,有时会父类类型。那么到底在什么情况下用哪种类型呢?肯定有不少人会忽略这点,本篇文章就是把这个细节讲清楚 案例 父类Ba…...
海外腾讯云服务器手机上无法访问外网怎么办??
本文将介绍腾讯云服务器无法访问外网的一些常见原因以及解决办法,同时解答了手机无法访问腾讯云服务器的问题。 腾讯云服务器(Tencent Cloud Server)是一种基于云计算技术的虚拟服务器,可以满足用户对于计算、存储、网络等方面的需…...
python3+requests:接口自动化测试(二)
前言:上篇文章python3requestsunittest:接口自动化测试(一):已经介绍了基于unittest框架的实现接口自动化,但是也存在一些问题,比如最明显的测试数据和业务没有区分开,接口用例不便于…...
uni-app:允许字符间能自动换行(英文字符、数字等)
<template><view class"container"><!-- 这里是你的文本内容 -->{{ multilineText }}</view> </template><style> .container {word-break: break-all; } </style>例如: <template><view class"…...
day 42 |● 121. 买卖股票的最佳时机 ● 122.买卖股票的最佳时机II
121. 买卖股票的最佳时机 dp数组需要记录两种状态,一种是当天时手中还持有股票,一种是当天时手中已卖出股票。 func maxProfit(prices []int) int {dp : make([][]int, len(prices))dp[0] []int{-prices[0], 0}for i : 1; i < len(prices); i{val0…...
SQLserver基础入门理论(超基础)
♥️作者:小刘在C站 ♥️个人主页: 小刘主页 ♥️努力不一定有回报,但一定会有收获加油!一起努力,共赴美好人生! ♥️学习两年总结出的运维经验,以及思科模拟器全套网络实验教程。专栏…...
(三)行为模式:7、观察者模式(Observer Pattern)(C++示例)
目录 1、观察者模式(Observer Pattern)含义 2、观察者模式的UML图学习 3、观察者模式的应用场景 4、观察者模式的优缺点 (1)优点: (2)缺点 5、C实现观察者模式的实例 1、观察者模式&…...
2019CVPR Semantic Graph Convolutional Networks for 3D Human Pose Regression
基于语义图卷积网络的三维人体姿态回归 源码 https://github.com/garyzhao/SemGCN 摘要 在本文中,我们研究了学习图卷积网络(GCN)回归的问题。GCN的当前体系结构受限于卷积滤波器和共享的变换矩阵为的小感受野。为了解决这些限制ÿ…...
大数据课程K16——Spark的梯度下降法
文章作者邮箱:yugongshiyesina.cn 地址:广东惠州 ▲ 本章节目的 ⚪ 了解Spark的梯度下降法; ⚪ 了解Spark的梯度下降法家族(BGD,SGD,MBGD); ⚪ 掌握Spark的MLlib实现…...
springboot:时间格式化的5种方法(解决后端传给前端的时间格式转换问题)推荐使用第4和第5种!
本文转载自:springboot:时间格式化的5种方法(解决后端传给前端的时间显示不一致)_为什么前端格式化日期了后端还要格式化_洛泞的博客-CSDN博客 时间问题演示 为了方便演示,我写了一个简单 Spring Boot 项目ÿ…...
六、vim编辑器的使用
1、编辑器 (1)编辑器就是一款软件。 (2)作用就是用来编辑文件,譬如编辑文字、编写代码。 (3)Windows中常用的编辑器,有自带的有记事本(notepad),比较好用的notepad、VSCode等。 (4)Linux中常用的编辑器,自带的最古老的vi&…...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...
【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...
安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件
在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...
(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
C++.OpenGL (14/64)多光源(Multiple Lights)
多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...
Qemu arm操作系统开发环境
使用qemu虚拟arm硬件比较合适。 步骤如下: 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载,下载地址:https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...
