【算法】算法思想合集

embedded/2024/9/24 5:20:56/

数组分块

  1. 将数组分成具有某些特征的段
  2. 使用双指针算法(如果是数组,使用下标充当指针)
  3. 存在信息丢失的问题,可以考虑从后向前进行
  4. 利用单调性进行定性分析(盛最多的水)
    滑动窗口
  5. 同向移动的双指针
  6. 出窗口一般是while
  7. 必须具备单调性

二分查找

  1. 如果left=mid,那么mid就应该是右边的
  2. 如果right=mid,那么mid就应该是左边的
    这两点是为了防止取中的时候,left或right会在原地不动,造成死循环
  3. 只要有二段性,就是根据各段的性质,对于mid位置进行判断,看其符合哪段的性质
  4. 找二段性是非常重要的一环

前缀和

  1. 和可被k整除的子数组:
    a. 同余定理:(a-b)%p = k —> a%k = b%k
    b. 负数 % 正数 修正为正数: ((a % p) +p ) % p
  2. 前缀和需要考虑的特殊情况:
    a. 从后往前倒着来
    b. 可以不使用前缀和数组,而是使用hash表进行记录

位运算

  1. 提取最低位1(low bit)
    a. n & (-n)
  2. 干掉最低位1
    a. n & (n-1)
    本质就是低位的0减不动1,只能一直向前直到最低位的1才能开始减
  3. 异或
    a. 三个数异或 就相当于给这三个数做无进位相加,就相当于给这三个数的1进行抵消,并且不考虑顺序问题

动态规划

  1. 状态表示
    经验 + 题目要求:以 i 位置为结尾 / 开头,xxx
    明确 dp 的每个位置的含义。
  2. 结尾:这个位置的状态不需要使用到后面的信息
    这种方式也可以使用 贪心
  3. 开头:需要用到后面的信息
  4. 状态转移方程
    以 i 位置最近的状态进行分析 i 位置的状态应该怎么来。
    就是 i-1,i-2 等位置的状态怎么能到 i。
  5. 初始化
    dp 表需要明确最开始的几个状态,有了这几个状态,后续的才能开展。
  6. 填表顺序
    状态的填充应该是从哪里到哪里。
  7. 返回值
    题目中需要的是不是最后一个状态。

http://www.ppmy.cn/embedded/114677.html

相关文章

09年408考研真题-数据结构

数据结构 10.【2009统考真题】为解决计算机主机与打印机之间速度不匹配的问题,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是(B)。 A.栈 …

计算机网络:物理层 --- 基本概念、编码与调制

目录 一. 物理层的基本概念 二. 数据通信系统的模型 三. 编码 3.1 基本概念 3.2 不归零制编码 3.3 归零制编码 3.4 曼切斯特编码 3.5 差分曼切斯特编码 ​编辑 四. 调制 4.1 调幅 4.2 调频 4.3 调相 4.4 混合调制 今天我们讲的是物理…

极狐GitLab DevSecOps 功能合集(七大安全功能)

极狐GitLab 是 GitLab 在中国的发行版,专门面向中国程序员和企业提供企业级一体化 DevOps 平台,用来帮助用户实现需求管理、源代码托管、CI/CD、安全合规,而且所有的操作都是在一个平台上进行,省事省心省钱。可以一键安装极狐GitL…

第二十节:学习Redis缓存数据库实现增删改查(自学Spring boot 3.x的第五天)

这节记录下如何使用redis缓存数据库。 第一步: 先在服务器端安装redis, 下载地址:Releases tporadowski/redis GitHub。 第二步: 安装redis客户端可视化管理软件redisDesktopmanager Redis Desktop Manager - Download 第…

【可测试性实践】C++单元测试:gtest gmock

引言 google test是目前C主流的单元测试框架,本文介绍如何在工程引入gtest和gmock,并提供入门参考示例。根据黄金圈思维我们先思考Why(为什么做),为什么我们要进行单元测试,为什么要引入mock手段来测试代码…

【艾思科蓝】Spring全家桶使用深度教程:从入门到精通

【IEEE出版 | 连续4届稳定EI检索】第五届计算机工程与智能控制国际学术会议(ICCEIC 2024)_艾思科蓝_学术一站式服务平台 更多学术会议请看 学术会议-学术交流征稿-学术会议在线-艾思科蓝 目录 引言 一、Spring Framework基础 1.1 Spring Framework简…

HTTP中的Cookie与Session

一、背景 HTTP协议是无状态无连接的。 无状态:服务器不会保存客户端历史请求记录,每一次请求都是全新的。 无连接:服务器应答后关闭连接,每次请求都是独立的。 无状态就导致服务器不认识每一个请求的客户端是否登陆过。 这时…

网络安全(黑客技术) 最新三个月学习计划

🤟 基于入门网络安全/黑客打造的:👉黑客&网络安全入门&进阶学习资源包 前言 什么是网络安全 网络安全可以基于攻击和防御视角来分类,我们经常听到的 “红队”、“渗透测试” 等就是研究攻击技术,而“蓝队”、…