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

力扣算法---总结篇

5.13 数组总结

数组是存放在连续内存空间上的相同类型数据的集合。

数组可以方便的通过下标索引的方式获取到下标对应的数据。

正是因为数组在内存空间的地址是连续的,所以我们在删除或者增添元素的时候,就难免要移动其他元素的地址。

数组的元素是不能删的,只能覆盖。

  • 二分法:循环不变量原则,只有在循环中坚持对区间的定义,才能清楚的把握循环中的各种细节。

    二分法是算法面试中的常考题,建议通过这道题目,锻炼自己手撕二分的能力

  • 双指针法:移除一个数字

    双指针法(快慢指针法):通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

  • class Solution {
    public:int removeElement(vector<int>& nums, int val) {int slowIndex = 0;for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {if (val != nums[fastIndex]) {nums[slowIndex++] = nums[fastIndex];}}return slowIndex;}
    };
    
  • 滑动窗口:

    滑动窗口如何移动 窗口起始位置,达到动态更新窗口大小的,从而得出长度最小的符合条件的长度。

    滑动窗口的精妙之处在于根据当前子序列和大小的情况,不断调节子序列的起始位置。从而将O(n^2)的暴力解法降为O(n)。

= g.length - 1 ; i >= 0 ; i–){
if(sIndex >= 0 && s[sIndex] >= g[i]){
res++;
sIndex–;
}
}
return res;
};


总结:这一道题就是典型的贪心算法问题,大饼干肯定满足大胃口和小胃口,所以从最大的饼干开始遍历,依次遍历大胃口到小胃口。注意判断条件,因为sIndex是饼干,它要大于0才能进行比较和移动指针。# 4.30 数组合集---二分查找\704. 二分查找已解答简单相关企业给定一个 `n` 个元素有序的(升序)整型数组 `nums` 和一个目标值 `target`  ,写一个函数搜索 `nums` 中的 `target`,如果目标值存在返回下标,否则返回 `-1`。**示例 1:**

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4


**示例 2:**

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

**提示:**1. 你可以假设 `nums` 中的所有元素是不重复的。
2. `n` 将在 `[1, 10000]`之间。
3. `nums` 的每个元素都将在 `[-9999, 9999]`之间。因为学校有算法课,但是用的c++,我就一直没有听,在写这个题目之前我真的觉得这个很简单,因为我已经写过很多次了,但是真正写了才发现什么是一写就废。首先ts里面的除法是会有小数点的,应该使用math里面的四舍五入

mid = Math.floor((low + up) / 2 );


没有正确理解区间:它可以是左闭右闭区间:while (left <= right) 要使用 <= ,因为left == right是有意义的,所以使用 <=if (nums[middle] > target) right 要赋值为 middle - 1,因为当前这个nums[middle]一定不是target,那么接下来要查找的左区间结束下标位置就是 middle - 1也可以是左闭右开区间:while (left < right),这里使用 < ,因为left == right在区间[left, right)是没有意义的if (nums[middle] > target) right 更新为 middle,因为当前nums[middle]不等于target,去左区间继续寻找,而寻找区间是左闭右开区间,所以right更新为middle,即:下一个查询区间不会去比较nums[middle]最终代码:

function search(nums: number[], target: number): number {
let low : number = 0 ;
let up : number = nums.length;
let mid : number;
while(low < up){
mid = Math.floor((low + up) / 2 );
if(nums[mid] === target) return mid;
else if (nums[mid] > target) up = mid ;
else low = mid + 1;
}
return -1;

};


# 5.8 数组合集---有序数组的平方给你一个按 **非递减顺序** 排序的整数数组 `nums`,返回 **每个数字的平方** 组成的新数组,要求也按 **非递减顺序** 排序。**示例 1:**

输入:nums = [-4,-1,0,3,10]
输出:[0,1,9,16,100]
解释:平方后,数组变为 [16,1,0,9,100]
排序后,数组变为 [0,1,9,16,100]


**示例 2:**

输入:nums = [-7,-3,2,3,11]
输出:[4,9,9,49,121]

**提示:**- `1 <= nums.length <= 104`
- `-104 <= nums[i] <= 104`
- `nums` 已按 **非递减顺序** 排序我的思路:暴力解法每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。我的思路:遍历平方之后使用sort代码:

function sortedSquares(nums: number[]): number[] {

for(let i = 0 ; i < nums.length ; i++){nums[i] = nums[i] * nums[i];}nums.sort((a , b) => {return a - b});return nums;

};


双指针思路:因为要求是递增嘛,我们设两个指针指向原数组的首尾端,设置一个新的数组,从最后开始插入数字我的代码:

let i = 0 , j = nums.length - 1;
let k = nums.length - 1; ;
let res = [];
while( i <= j){
let ans1 = nums[i] * nums[i];
let ans2 = nums[j] * nums[j];
if(ans1 > ans2){
res[k] = ans1;
k–;
i++;
}else {
res[k] = ans2;
k–;
j–;
}
}
return res;


总结:在数组中,双指针是一个很好的方法# 5.9 数组合集---长度最小的子数组给定一个含有 `n` 个正整数的数组和一个正整数 `target` **。**找出该数组中满足其总和大于等于 `target` 的长度最小的 **子数组** `[numsl, numsl+1, ..., numsr-1, numsr]` ,并返回其长度**。**如果不存在符合条件的子数组,返回 `0` 。**示例 1:**

输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。


**示例 2:**

输入:target = 4, nums = [1,4,4]
输出:1


**示例 3:**

输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0

**提示:**- `1 <= target <= 109`
- `1 <= nums.length <= 105`
- `1 <= nums[i] <= 104`**进阶:**- 如果你已经实现 `O(n)` 时间复杂度的解法, 请尝试设计一个 `O(n log(n))` 时间复杂度的解法。我的思路:双指针,滑窗思想[2,3,1,2,4,3]​         *​           *2<7 res++ j++2 + 3 < 7  res++ j++5 + 1 < 7  res++ j++6 + 2 > 7 res-- i++ 8-2 = 66 < 7 j++  6 + 4 > 7 res-- i++  10-3 = 7 = 7 res-- i++7 - 2 = 5 5 + 3 = 8 res-- i++   8-2 = 6当sum<target => res++ , j++ sum+=当sum >= tartget => res-- , i++ sum-=  缩小窗口总的来说sum>=target的时候进行缩小窗口操作,其他的进行扩大窗口的操作我的代码:

function minSubArrayLen(target: number, nums: number[]): number {
let i = 0 ;
let j = 0;
let min = Infinity;
// [1,4,4]
let sum = 0 ;
while(j < nums.length ){
sum += nums[j];
while(sum >= target){
min = Math.min(min , j - i + 1);
sum -= nums[i];
i++;
}
j++;
}
return min === Infinity ? 0 : min;
};


# 5.12 数组合集---59.螺旋矩阵给你一个正整数 `n` ,生成一个包含 `1` 到 `n2` 所有元素,且元素按顺时针顺序螺旋排列的 `n x n` 正方形矩阵 `matrix` 。**示例 1:**

输入:n = 3
输出:[[1,2,3],[8,9,4],[7,6,5]]


**示例 2:**

输入:n = 1
输出:[[1]]

**提示:**- `1 <= n <= 20`这道题目可以说在面试中出现频率较高的题目,**本题并不涉及到什么算法,就是模拟过程,但却十分考察对代码的掌控能力。**我的思路:其实我最开始是没有思路的,除了一昧的循环,我没有任何思路,看到题解使用的边界方法,我突然领悟了

生成一个包含 1 到 n2 所有元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix
生成一个正方形的矩阵,它的值是元素按顺时针螺旋排列得到的
i j
00 01 02
10 11 12
20 21 22
定义边界
r=2 l=0 t=0 b=2
for(int i = 0 ; i < r ; i++){
[top][i]
top++
}
for(let j = top ; j < b ; j++){
[j][r]
r–;
}
for(let k = r ; k > l ; k-- ){
[b][k]
b–;
}
for(let m = b ; m > t ; m==){
[m][l];
l++
}


但是实现起来却没有这么简单:- 矩阵声明问题:我最开始是用的- ```let res : number[][] = [];

但是这样的声明不会创建一个n x n的二维数组,而是创建了一个空数组

  • let res = new Array(n).fill(0).map(() => new Array(n).fill(0));
    

最终代码:

function generateMatrix(n: number): number[][] {// 定义边界let r = n - 1 , l = 0 , t = 0 , b = n - 1;const total = n * n ; let num = 1 ; // 这样的声明不会创建一个n x n的二维数组,而是创建了一个空数组。let res = new Array(n).fill(0).map(() => new Array(n).fill(0));while(num <= total){for(let i = l ; i <= r ; i++){res[t][i] = num;num++;}t++;for(let j = t ; j <= b ; j++){res[j][r] = num;num++;}r--;for(let k = r ; k >= l ; k--){res[b][k] = num;num++;}b--;for(let m = b ; m >= t ; m--){res[m][l] = num;num++;}l++;}return res;};

总结:这样的螺旋问题可以使用边界法,边界是动态的,我们循环的时候注意一下边界就好啦

5.13 数组总结

数组是存放在连续内存空间上的相同类型数据的集合。

数组可以方便的通过下标索引的方式获取到下标对应的数据。

正是因为数组在内存空间的地址是连续的,所以我们在删除或者增添元素的时候,就难免要移动其他元素的地址。

数组的元素是不能删的,只能覆盖。

  • 二分法:循环不变量原则,只有在循环中坚持对区间的定义,才能清楚的把握循环中的各种细节。

    二分法是算法面试中的常考题,建议通过这道题目,锻炼自己手撕二分的能力

  • 双指针法:移除一个数字

    双指针法(快慢指针法):通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

  • class Solution {
    public:int removeElement(vector<int>& nums, int val) {int slowIndex = 0;for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {if (val != nums[fastIndex]) {nums[slowIndex++] = nums[fastIndex];}}return slowIndex;}
    };
    
  • 滑动窗口:

    滑动窗口如何移动 窗口起始位置,达到动态更新窗口大小的,从而得出长度最小的符合条件的长度。

    滑动窗口的精妙之处在于根据当前子序列和大小的情况,不断调节子序列的起始位置。从而将O(n^2)的暴力解法降为O(n)。

相关文章:

力扣算法---总结篇

5.13 数组总结 数组是存放在连续内存空间上的相同类型数据的集合。 数组可以方便的通过下标索引的方式获取到下标对应的数据。 正是因为数组在内存空间的地址是连续的&#xff0c;所以我们在删除或者增添元素的时候&#xff0c;就难免要移动其他元素的地址。 数组的元素是不…...

ABAP+旧数据接管的会计年度未确定

导资产主数据时&#xff0c;报错旧数据接管的会计年度未确定 是因为程序里面使用了下列函数AISCO_CALCULATE_FIRST_DAY&#xff0c;输入公司代码&#xff0c;获取会计年度&#xff0c;这个数据是在后台表T093C表中取数的&#xff0c;通过SE16N可以看到后台表数据没有数&#xf…...

Java【10_1】用户注册登录(面向过程与面向对象)

测试题 1、基于文本界面实现登录注册的需求(要求可以满足多个用户的注册和登录) 通过工具去完成 公共类&#xff1a; public class User { private int id;//用户编号 private int username;//用户名 private int password;//密码 private String name;//真…...

养生:打造健康生活的全方位策略

在生活节奏不断加快的当下&#xff0c;养生已成为提升生活质量、维护身心平衡的重要方式。从饮食、运动到睡眠&#xff0c;再到心态调节&#xff0c;各个方面的养生之道共同构建起健康生活的坚实基础。以下为您详细介绍养生的关键要点&#xff0c;助您拥抱健康生活。 饮食养生…...

贪吃蛇游戏排行榜模块开发总结:从数据到视觉的实现

一、项目背景与成果概览 在完成贪吃蛇游戏核心玩法后,本次开发重点聚焦于排行榜系统的实现。该系统具备以下核心特性: 🌐 双数据源支持:本地存储(localStorage)与远程API自由切换 🕒 时间维度统计:日榜/周榜/月榜/全时段数据筛选 🎮 模式区分:闯关模式(关卡进度…...

pytorch 数据预处理和常用工具

文章目录 NumPyNumpy数据结构安装和使用NumPy Matplotlib的安装和导入安装和导入Matplotlib绘制基础图画折线图散点图柱状图图例 数据清洗据清洗的作用Pandas进行数据清洗Pandas数据结构Series 数据结构DataFrame数据结构 Pandas数据清洗常用代码 特征工程主成分分析线性判别分…...

如何界定合法收集数据?

首席数据官高鹏律师团队 在当今数字化时代&#xff0c;数据的价值日益凸显&#xff0c;而合法收集数据成为了企业、机构以及各类组织必须严守的关键准则。作为律师&#xff0c;深入理解并准确界定合法收集数据的范畴&#xff0c;对于保障各方权益、维护法律秩序至关重要。 一…...

企业对数据集成工具的需求及 ETL 工具工作原理详解

当下&#xff0c;数据已然成为企业运营发展过程中的关键生产要素&#xff0c;其重要性不言而喻。 海量的数据分散在企业的各类系统、平台以及不同的业务部门之中&#xff0c;企业要充分挖掘这些数据背后所蕴含的巨大价值&#xff0c;实现数据驱动的精准决策&#xff0c;数据集…...

内核深入学习3——分析ARM32和ARM64体系架构下的Linux内存区域示意图与页表的建立流程

内核深入学习3——ARM32/ARM64在Linux内核中的实现&#xff08;2&#xff09; ​ 今天我们来讨论的是一个硬核的内容&#xff0c;也是一个老生常谈的话题——那就是分析ARM32和ARM64体系架构下的Linux内存区域示意图的内容。对于ARM64的部分&#xff0c;我们早就知道一个基本的…...

MapReduce基本介绍

核心思想 分而治之&#xff1a;将大规模的数据处理任务分解成多个可以并行处理的子任务&#xff0c;然后将这些子任务分配到不同的计算节点上进行处理&#xff0c;最后将各个子任务的处理结果合并起来&#xff0c;得到最终的结果。 工作流程 Map 阶段&#xff1a; 输入数据被…...

屏幕与触摸调试

本章配套视频介绍: 《28-屏幕与触摸设置》 【鲁班猫】28-屏幕与触摸设置_哔哩哔哩_bilibili LubanCat-RK3588系列板卡都支持mipi屏以及hdmi显示屏的显示。 19.1. 旋转触摸屏 参考文章 触摸校准 参考文章 旋转触摸方向 配置触摸旋转方向 1 2 # 1.查看触摸输入设备 xinput…...

使用 百度云大模型平台 做 【提示词优化】

1. 百度云大模型平台 百度智能云千帆大模型平台 &#xfeff; 平台功能&#xff1a;演示了阿里云大模型的百炼平台&#xff0c;该平台提供Prompt工程功能&#xff0c;支持在线创建和优化Prompt模板模板类型&#xff1a;平台提供多种预制模板&#xff0c;同时也支持用户自定义…...

C 语言_常见排序算法全解析

排序算法是计算机科学中的基础内容,本文将介绍 C 语言中几种常见的排序算法,包括实现代码、时间复杂度分析、适用场景和详细解析。 一、冒泡排序(Bubble Sort) 基本思想:重复遍历数组,比较相邻元素,将较大元素交换到右侧。 代码实现: void bubbleSort(int arr[], i…...

IJCAI 2025 | 高德首个原生3D生成基座大模型「G3PT」重塑3D生成的未来

国际人工智能联合会议&#xff08;IJCAI&#xff09;是人工智能领域最古老、最具权威性的学术会议之一&#xff0c;自1969年首次举办以来&#xff0c;至今已有近六十年的历史。它见证了人工智能从萌芽到蓬勃发展的全过程&#xff0c;是全球人工智能研究者、学者、工程师和行业专…...

Samtec助力电视广播行业

【摘要前言】 现代广播电视技术最有趣的方面之一就是界限的模糊。过去&#xff0c;音频和视频是通过射频电缆传输的模拟技术采集的&#xff0c;而现在&#xff0c;数字世界已经取代了模拟技术。物理胶片和磁带已让位于数字存储设备和流媒体。 在这个过程中&#xff0c;连接器…...

密码学--仿射密码

一、实验目的 1、通过实现简单的古典密码算法&#xff0c;理解密码学的相关概念 2、理解明文、密文、加密密钥、解密密钥、加密算法、解密算法、流密码与分组密码等。 二、实验内容 1、题目内容描述 ①随机生成加密密钥&#xff0c;并验证密钥的可行性 ②从plain文件读入待…...

生成式图像水印研究综述

生成式图像水印研究综述 一、引言二、生成式图像水印研究背景三、生成式图像水印算法研究进展3.1 基于流模型的方案3.2 基于生成对抗网络的方案3.3 基于扩散模型的方案3.3.1 修改图像数据3.3.2 调整生成模型3.3.3 修改隐变量空间四、算法的性能与评价指标五、常用数据集六、本章…...

TCP协议详细讲解及C++代码实例

目录 一. TCP协议详细讲解及C代码实例1、TCP协议概述2、TCP通信流程1&#xff09; 三次握手2) 数据传输3) 四次挥手 3、关键点解析1&#xff09; 套接字创建2&#xff09; 三次握手实现3&#xff09; 数据传输4&#xff09; 四次挥手实现 4、TCP与UDP对比 一. TCP协议详细讲解及…...

深度剖析:Vue2 项目兼容第三方库模块格式的终极解决方案

当我们为 Vue2 项目引入某些现代 JavaScript 库时&#xff0c;常常会遇到这样的报错&#xff1a; error in ./node_modules/some-lib/lib/index.mjs Cant import the named export xxx from non EcmaScript module这类问题的本质是模块格式的世纪之争 —— ES Module&#xff…...

APISQL免费版安装教程(视频)

APISQL 一款通用的API开发管理软件&#xff0c;支持将主流数据库中的表、视图、SQL语句、存储过程等快速封装为标准的 RESTful API&#xff0c;支持多种安全认证方式和可视化管理界面。适用于接口开发、系统集成、数据共享等场景。 支持主流数据库的表、视图、自定义函数、存储…...

SpringBoot整合MQTT实战:基于EMQX实现双向设备通信(附源码)

简言&#xff1a; 在万物互联的时代&#xff0c;MQTT协议凭借其轻量级、高效率的特性&#xff0c;已成为物联网通信的事实标准。本教程将带领您在Ubuntu系统上搭建EMQX 5.9.0消息服务器&#xff0c;并使用Spring Boot快速实现两个客户端的高效通信。通过本指南&#xff0c;您将…...

从零开始掌握FreeRTOS(2)链表之节点的定义

目录 节点 节点定义 节点实现 根节点 根节点定义 精简节点定义 根节点实现 在上篇文章,我们完成了 FreeRTOS 的移植。在创建任务之前,我们需要先了解FreeRTOS的运转机制。 FreeRTOS是一个多任务系统,由操作系统来管理执行每个任务。这些任务全都挂载到一个双向循…...

Java的While循环写的出票简单程序

import java.util.Scanner;public class Hello {public static void main(String[] args) {Scanner in new Scanner(System.in);int balance 0;while(true){System.out.print("请投币: ");int amount in.nextInt();balance balance amount;if(balance >10 )…...

详解Windows(十一)——网络连接设置

Windows网络连接设置完全指南 1. Windows网络连接基础 网络连接类型 有线连接&#xff1a; 通过网线将电脑连接到路由器或调制解调器优点&#xff1a;连接稳定&#xff0c;速度快&#xff0c;延迟低适合&#xff1a;需要高速稳定网络的场景&#xff0c;如游戏、大文件下载、…...

多线程爬虫语言选择与实现

之前文中有人提到&#xff1a;想要一个简单易用、能快速实现多线程爬虫的方案&#xff0c;而且目标是小网站&#xff0c;基本可以确定对反爬虫措施要求不高&#xff0c;这些就比较简单了。 以往我肯定要考虑常见的编程语言中哪些适合爬虫。Python、JavaScript&#xff08;Node…...

【数据结构】——双向链表

一、链表的分类 我们前面学习了单链表&#xff0c;其是我们链表中的其中一种&#xff0c;我们前面的单链表其实全称是单向无头不循环链表&#xff0c;我们的链表从三个维度进行分类&#xff0c;一共分为八种。 1、单向和双向 可以看到第一个链表&#xff0c;其只能找到其后一个…...

AI助力:零基础开启编程之旅

一、代码调试 三步解决BUG 1. 错误信息翻译 指令模板&#xff1a; 错误诊断模式我遇到【编程语言】报错“粘贴报错信息“ 请&#xff1a; 用小白能懂的话解释问题本质标注可能引发该错误的三个场景给出最可能的修复方案和其他备选方案 2. 上下文分析 进阶指令 结合上下文代…...

mybatis中${}和#{}的区别

先测试&#xff0c;再说结论 userService.selectStudentByClssIds(10000, "wzh or 11");List<StudentEntity> selectStudentByClssIds(Param("stuId") int stuId, Param("field") String field);<select id"selectStudentByClssI…...

【计算机组成原理】第二部分 存储器--分类、层次结构

文章目录 分类&层次结构0x01 分类按存储介质分类按存取方式分类按在计算机中的作用分类 0x02 层次结构 分类&层次结构 0x01 分类 按存储介质分类 半导体存储器磁表面存储器磁芯存储器光盘存储器 按存取方式分类 存取时间与物理地址无关&#xff08;随机访问&#…...

抗量子计算攻击的数据安全体系构建:从理论突破到工程实践

在“端 - 边 - 云”三级智能协同理论中&#xff0c;端 - 边、边 - 云之间要进行数据传输&#xff0c;网络的安全尤为重要&#xff0c;为了实现系统总体的安全可控&#xff0c;将构建安全网络。 可先了解我的前文&#xff1a;“端 - 边 - 云”三级智能协同平台的理论建构与技术实…...