当前位置: 首页 > news >正文

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

在这里插入图片描述

最长严格递增子序列

题目描述

给你一个整数数组nums,找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例:
输入:nums = [2,1,6,3,5,4]
输出:3
解释:最长递增子序列是 [1,3,4],因此长度为 3。

思路

这道题要求最长上升子序列的长度,可以使用动态规划或贪心+二分查找两种方法来解决。

  1. 动态规划
    定义状态:dp[i]表示以第i个元素为结尾的最长上升子序列的长度。
    状态转移方程:对于第i个元素,枚举其前面的元素j,如果nums[i] > nums[j],则dp[i] = dp[j] + 1。同时,在每次更新dp[i]时,更新ans为其最大值。

  2. 贪心+二分查找
    定义一个数组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&#xff0c;找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列&#xff0c;删除&#xff08;或不删除&#xff09;数组中的元素而不改变其余元素的顺序。例如&#xff0c;[3,6,2,7] 是数组 [0,3,1,6,2,2,7…...

设计模式—策略模式

目录 一、定义 二、特点 三、优点 四、缺点 五、实例 六.涉及到的知识点 1、一个类里面有哪些东西&#xff1f; 2、类和实例 什么是类&#xff1f; 什么是实例&#xff1f; 什么是实例化&#xff1f; 3、字段和属性 什么是字段&#xff1f; 属性是什么&#xff1…...

LPDDR4、DDR4

核心信息&#xff1a; 2400Mbps&#xff08;每秒传输2400*1百万bit&#xff09; 2400MT/s&#xff08;百万次/秒&#xff09; 信号...

ESP32C3 LuatOS RC522①写入数据并读取M1卡

LuatOS RC522官方示例 官方示例没有针对具体开发板&#xff0c;现以ESP32C3开发板为例。 选用的RC522模块 ESP32C3-CORE开发板 注意ESP32C3的 SPI引脚位置&#xff0c;SPI的id2 示例代码 -- LuaTools需要PROJECT和VERSION这两个信息 PROJECT "helloworld" VERSIO…...

MusicBrainz Picard for Mac :音乐文件ID3编辑器

MusicBrainz Picard for Mac是一款macOS平台的音乐文件ID3编辑器&#xff0c;能够帮助我们在Mac电脑上编辑音乐文件的ID3标签信息&#xff0c;包括艺人、专辑等信息&#xff0c;非常快速和简单方便。Picard是下一代MusicBrainz标记应用程序。 这个新的标签概念是面向专辑的&…...

❤ Uniapp使用

❤ Uniapp使用 一、介绍 uni-app官网&#xff1a;https://uniapp.dcloud.io/api/media/image?idpreviewimage 微信小程序官网&#xff1a;https://developers.weixin.qq.com/miniprogram/dev/api/media/image/wx.previewImage.html 二、使用 1、uniapp 实现图片预览 单图预…...

解密Spring事务生效的内部机制

声明式事务和编程式事务对比&#xff1a; 声明式事务&#xff1a; 使用注解或XML配置的方式&#xff0c;在代码中声明事务的属性和行为。通过AOP和代理模式实现&#xff0c;将事务管理与业务逻辑代码解耦。适用于大多数情况&#xff0c;简化了代码&#xff0c;提高了可维护性和…...

大数据时代下的数据安全防护

随着大数据时代的来临&#xff0c;数据安全防护成为了一个重要的问题。在大数据时代&#xff0c;数据的规模和价值都得到了极大的提升&#xff0c;因此数据安全的重要性也变得越来越突出。本文将从数据加密、访问控制、网络安全和人员管理四个方面来介绍大数据时代下的数据安全…...

RabbitMQ-常用命令

RabbitMQ常用命令 3.1 启动停止rabbitMQ命令 # 前台启动Erlang VM 和 RabbitMQ 当窗口关闭或者ctrlc时&#xff0c;使退出了。 rabbitmq-server# 使用系统命令启动 systemctl start rabbitmq-server# 后台启动 rabbitmq-server -detached# 停止rabbitMQ和Erlang VM rabbitmq-…...

Spring中依赖注入的继承bean的细节问题

介绍 有时我们会对一种类型的bean进行继承&#xff0c;在Spring生成bean的时候&#xff0c;返回类型有时是子类类型&#xff0c;有时会父类类型。那么到底在什么情况下用哪种类型呢&#xff1f;肯定有不少人会忽略这点&#xff0c;本篇文章就是把这个细节讲清楚 案例 父类Ba…...

海外腾讯云服务器手机上无法访问外网怎么办??

本文将介绍腾讯云服务器无法访问外网的一些常见原因以及解决办法&#xff0c;同时解答了手机无法访问腾讯云服务器的问题。 腾讯云服务器&#xff08;Tencent Cloud Server&#xff09;是一种基于云计算技术的虚拟服务器&#xff0c;可以满足用户对于计算、存储、网络等方面的需…...

python3+requests:接口自动化测试(二)

前言&#xff1a;上篇文章python3requestsunittest&#xff1a;接口自动化测试&#xff08;一&#xff09;&#xff1a;已经介绍了基于unittest框架的实现接口自动化&#xff0c;但是也存在一些问题&#xff0c;比如最明显的测试数据和业务没有区分开&#xff0c;接口用例不便于…...

uni-app:允许字符间能自动换行(英文字符、数字等)

<template><view class"container"><!-- 这里是你的文本内容 -->{{ multilineText }}</view> </template><style> .container {word-break: break-all; } </style>例如&#xff1a; <template><view class"…...

day 42 |● 121. 买卖股票的最佳时机 ● 122.买卖股票的最佳时机II

121. 买卖股票的最佳时机 dp数组需要记录两种状态&#xff0c;一种是当天时手中还持有股票&#xff0c;一种是当天时手中已卖出股票。 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基础入门理论(超基础)

♥️作者&#xff1a;小刘在C站 ♥️个人主页&#xff1a; 小刘主页 ♥️努力不一定有回报&#xff0c;但一定会有收获加油&#xff01;一起努力&#xff0c;共赴美好人生&#xff01; ♥️学习两年总结出的运维经验&#xff0c;以及思科模拟器全套网络实验教程。专栏&#xf…...

(三)行为模式:7、观察者模式(Observer Pattern)(C++示例)

目录 1、观察者模式&#xff08;Observer Pattern&#xff09;含义 2、观察者模式的UML图学习 3、观察者模式的应用场景 4、观察者模式的优缺点 &#xff08;1&#xff09;优点&#xff1a; &#xff08;2&#xff09;缺点 5、C实现观察者模式的实例 1、观察者模式&…...

2019CVPR Semantic Graph Convolutional Networks for 3D Human Pose Regression

基于语义图卷积网络的三维人体姿态回归 源码 https://github.com/garyzhao/SemGCN 摘要 在本文中&#xff0c;我们研究了学习图卷积网络&#xff08;GCN&#xff09;回归的问题。GCN的当前体系结构受限于卷积滤波器和共享的变换矩阵为的小感受野。为了解决这些限制&#xff…...

大数据课程K16——Spark的梯度下降法

文章作者邮箱&#xff1a;yugongshiyesina.cn 地址&#xff1a;广东惠州 ▲ 本章节目的 ⚪ 了解Spark的梯度下降法&#xff1b; ⚪ 了解Spark的梯度下降法家族&#xff08;BGD&#xff0c;SGD&#xff0c;MBGD&#xff09;&#xff1b; ⚪ 掌握Spark的MLlib实现…...

springboot:时间格式化的5种方法(解决后端传给前端的时间格式转换问题)推荐使用第4和第5种!

本文转载自&#xff1a;springboot&#xff1a;时间格式化的5种方法&#xff08;解决后端传给前端的时间显示不一致&#xff09;_为什么前端格式化日期了后端还要格式化_洛泞的博客-CSDN博客 时间问题演示 为了方便演示&#xff0c;我写了一个简单 Spring Boot 项目&#xff…...

六、vim编辑器的使用

1、编辑器 (1)编辑器就是一款软件。 (2)作用就是用来编辑文件&#xff0c;譬如编辑文字、编写代码。 (3)Windows中常用的编辑器&#xff0c;有自带的有记事本(notepad)&#xff0c;比较好用的notepad、VSCode等。 (4)Linux中常用的编辑器&#xff0c;自带的最古老的vi&…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

uniapp 小程序 学习(一)

利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 &#xff1a;开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置&#xff0c;将微信开发者工具放入到Hbuilder中&#xff0c; 打开后出现 如下 bug 解…...

【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统

Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...

Android写一个捕获全局异常的工具类

项目开发和实际运行过程中难免会遇到异常发生&#xff0c;系统提供了一个可以捕获全局异常的工具Uncaughtexceptionhandler&#xff0c;它是Thread的子类&#xff08;就是package java.lang;里线程的Thread&#xff09;。本文将利用它将设备信息、报错信息以及错误的发生时间都…...

字符串哈希+KMP

P10468 兔子与兔子 #include<bits/stdc.h> using namespace std; typedef unsigned long long ull; const int N 1000010; ull a[N], pw[N]; int n; ull gethash(int l, int r){return a[r] - a[l - 1] * pw[r - l 1]; } signed main(){ios::sync_with_stdio(false), …...