【算法】算法思想合集

news/2024/9/21 17:29:29 标签: 算法

数组分块

  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.niftyadmin.cn/n/5669162.html

相关文章

Oracle11g安装配置详细教程

Oracle卸载重装比较麻烦,尽量一次成功,如果遇到问题实在解决不了,请后台私信我! 1、下载oracle安装包 下载方式1:官网下载地址: https://docs.oracle.com/en/database/oracle/oracle-database/index.html …

Net core 环境变量

Environment.ExpandEnvironmentVariables(“资源名称”)

张养浩,文坛政坛的双重巨匠

张养浩,字希孟,号云庄,又称齐东野人,生于元世祖至元七年(公元1270年),卒于元英宗至治三年(公元1329年),享年59岁。他是中国元代著名的文学家、政治家&#xf…

SpringDataJpa自关联映射时出现StackOverflowError

使用Jpa自关联时,存在子数据的记录会报内存溢出问题StackOverflowError 原因: 使用了 lombok 插件中的Data注解来标注类,生成 gettet/setter 以及 toString lombok 在生成时会出现循环比较两类中的 hashcode,导致内存溢出。 解决…

海外大带宽服务器连接失败怎么办?

在全球化日益加深的今天,海外大带宽服务器已成为企业拓展国际市场、提升业务效率的重要工具。然而,面对复杂多变的网络环境和技术挑战,服务器连接失败的问题时有发生,这不仅影响了企业的正常运营,还可能带来经济损失和…

安卓13设置动态显示隐藏第一页的某一项 动态显示隐藏无障碍 android13设置动态显示隐藏第一页的某一项

总纲 android13 rom 开发总纲说明 文章目录 1.前言2.问题分析3.代码分析4.代码修改4.1修改方法14.2修改方法25.编译6.彩蛋1.前言 有时候,我们的设置里面显示的信息,需要根据不同的情况显示不同的信息,例如,动态的显示或者隐藏 “无障碍” 这一项。 2.问题分析 像这个问题…

PHP基础语法入门指南

前言 PHP(Hypertext Preprocessor)是一种广泛使用的开源服务器端脚本语言,特别适合Web开发,并可以嵌入到HTML中使用。PHP能够执行动态内容、创建交互式的Web页面、与数据库进行通信等。本文将带领你走进PHP的世界,从最…

GPU使用

0. 写这篇文章的背景 最近还是在使用GPU、连接远程服务器上出现了一点问题,发现在这方面的知识还是学得很模糊。(最让人感到困惑的是之前GPU的使用都没有问题) 总结一下最近的问题: 1.每一次连接远程服务器(选择的Ubuntu22.04),使用服务器的文件夹还好(关键是现在用…