百度360必应搜狗淘宝本站头条
当前位置:网站首页 > 文章教程 > 正文

一些可以装逼的算法技巧总结!值得拥有简单实用算法思想

xsobi 2024-11-23 10:51 20 浏览

今天和大家讲讲,在做算法题时常用的一些技巧。对于平时没用过这些技巧的人,或许你可以考虑试着去看看在实践中能否用的上这些技巧来优化问题的解。

1. 巧用数组下标 数组的下标是一个隐含的很有用的数组,特别是在统计一些数字,或者判断一些整型数是否出现过的时候。例如,给你一串字母,让你判断这些字母出现的次数时,我们就可以把这些字母作为下标,在遍历的时候,如果字母a遍历到,则arr[a]就可以加1了,即 arr[a]++; 通过这种巧用下标的方法,我们不需要逐个字母去判断。

我再举个例子: 问题:给你n个无序的int整型数组arr,并且这些整数的取值范围都在0-20之间,要你在 O(n) 的时间复杂度中把这 n 个数按照从小到大的顺序打印出来。 对于这道题,如果你是先把这 n 个数先排序,再打印,是不可能O(n)的时间打印出来的。但是数值范围在 0-20。我们就可以巧用数组下标了。把对应的数值作为数组下标,如果这个数出现过,则对应的数组加1。 代码如下:

编辑切换为居中

添加图片注释,不超过 140 字(可选)

利用数组下标的应用还有很多,大家以后在遇到某些题的时候可以考虑是否可以巧用数组下标来优化.

2. 巧用取余 有时候我们在遍历数组的时候,会进行越界判断,如果下标差不多要越界了,我们就把它置为0重新遍历。特别是在一些环形的数组中,例如用数组实现的队列。往往会写出这样的代码:

?

编辑切换为居中

添加图片注释,不超过 140 字(可选)

实际上我们可以通过取余的方法来简化代码 for (int i = 0; i < N; i++) { //使用数组arr[pos] (我们假设刚开始的时候pos < N) pos = (pos + 1) % N; }

3. 巧用双指针 对于双指针,在做关于单链表的题是特别有用,比如“判断单链表是否有环”、“如何一次遍历就找到链表中间位置节点”、“单链表中倒数第 k 个节点”等问题。对于这种问题,我们就可以使用双指针了,会方便很多。我顺便说下这三个问题怎么用双指针解决吧。

例如对于第一个问题 我们就可以设置一个慢指针和一个快指针来遍历这个链表。慢指针一次移动一个节点,而快指针一次移动两个节点,如果该链表没有环,则快指针会先遍历完这个表,如果有环,则快指针会在第二次遍历时和慢指针相遇。

对于第二个问题 一样是设置一个快指针和慢指针。慢的一次移动一个节点,而快的两个。在遍历链表的时候,当快指针遍历完成时,慢指针刚好达到中点。

对于第三个问题 设置两个指针,其中一个指针先移动k个节点。之后两个指针以相同速度移动。当那个先移动的指针遍历完成的时候,第二个指针正好处于倒数第k个节点。 你看,采用双指针方便多了吧。所以以后在处理与链表相关的一些问题的时候,可以考虑双指针哦。

4. 巧用移位运算 有时候我们在进行除数或乘数运算的时候,例如n / 2,n / 4, n / 8这些运算的时候,我们就可以用移位的方法来运算了,这样会快很多。 例如: n / 2 等价于 n >> 1 n / 4 等价于 n >> 2 n / 8 等价于 n >> 3。 这样通过移位的运算在执行速度上是会比较快的,也可以显的你很厉害的样子,哈哈。 还有一些 &(与)、|(或)的运算,也可以加快运算的速度。例如判断一个数是否是奇数,你可能会这样做 if(n % 2 == 1){ dosomething(); } 不过我们用与或运算的话会快很多。例如判断是否是奇数,我们就可以把n和1相与了,如果结果为1,则是奇数,否则就不会。即if(n & 1 == 1){ dosomething(); ) 具体的一些运算技巧,还得需要你们多在实践中尝试着去使用,这样用久后就会比较熟练了。

5. 设置哨兵位 在链表的相关问题中,我们经常会设置一个头指针,而且这个头指针是不存任何有效数据的,只是为了操作方便,这个头指针我们就可以称之为哨兵位了。 例如我们要删除头第一个节点是时候,如果没有设置一个哨兵位,那么在操作上,它会与删除第二个节点的操作有所不同。但是我们设置了哨兵,那么删除第一个节点和删除第二个节点那么在操作上就一样了,不用做额外的判断。当然,插入节点的时候也一样。 有时候我们在操作数组的时候,也是可以设置一个哨兵的,把arr[0]作为哨兵。例如,要判断两个相邻的元素是否相等时,设置了哨兵就不怕越界等问题了,可以直接arr[i] == arr[i-1]?了。不用怕i = 0时出现越界。 当然我这只是举一个例子,具体的应用还有很多,例如插入排序,环形链表等。

6. 与递归有关的一些优化 (1).对于可以递归的问题考虑状态保存 当我们使用递归来解决一个问题的时候,容易产生重复去算同一个子问题,这个时候我们要考虑状态保存以防止重复计算。例如我随便举一个之前举过的问题

问题:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法? 这个问题用递归很好解决。假设 f(n) 表示n级台阶的总跳数法,则有 f(n) = f(n-1) + f(n - 2)。 递归的结束条件是当0 <= n <= 2时, f(n) = n。因此我们可以很容易写出递归的代码 int f(int n) { if (n <= 2) { return n; } else { return f(n - 1) + f(n - 2); } } 不过对于可以使用递归解决的问题,我们一定要考虑是否有很多重复计算。显然对于 f(n) = f(n-1) + f(n-2) 的递归,是有很多重复计算的。如

?

编辑切换为居中

添加图片注释,不超过 140 字(可选)

就有很多重复计算了。这个时候我们要考虑状态保存。例如用hashMap来进行保存,当然用一个数组也是可以的,这个时候就像我们上面说的巧用数组下标了。可以当arr[n] = 0时,表示n还没计算过,当arr[n] != 0时,表示f(n)已经计算过,这时就可以把计算过的值直接返回回去了。因此我们考虑用状态保存的做法代码如下:

?

编辑切换为居中

添加图片注释,不超过 140 字(可选)

这样,可以极大着提高算法的效率。也有人把这种状态保存称之为备忘录法。 (2).考虑自底向上 对于递归的问题,我们一般都是从上往下递归的,直到递归到最底,再一层一层着把值返回。 不过,有时候当n比较大的时候,例如当 n = 10000时,那么必须要往下递归10000层直到 n <=2 才将结果慢慢返回,如果n太大的话,可能栈空间会不够用。 对于这种情况,其实我们是可以考虑自底向上的做法的。例如我知道 f(1) = 1; f(2) = 2; 那么我们就可以推出 f(3) = f(2) + f(1) = 3。从而可以推出f(4),f(5)等直到f(n)。因此,我们可以考虑使用自底向上的方法来做。 代码如下:

?

编辑切换为居中

添加图片注释,不超过 140 字(可选)

我们也把这种自底向上的做法称之为递推。

总结一下

当你在使用递归解决问题的时候,要考虑以下两个问题

是否有状态重复计算的,可不可以使用备忘录法来优化。

是否可以采取递推的方法来自底向上做,减少一味递归的开销。


我的C/C++编程学习基地:点击正在跳转即可加入,欢迎大家一起来学习交流嗷~

相关推荐

在 Linux 系统中安装 Redis 的详细步骤

以下是在Linux系统中安装Redis的详细步骤,支持通过包管理器安装(简单快捷)和源码编译安装(获取最新版本)两种方式:方法1:使用包管理器安装(推荐新手)适用于Ubuntu/De...

在Linux系统上安装Redis集群的详细步骤

以下是在Linux系统上安装Redis集群的详细步骤,基于Redis6.x+版本,采用三主三从(6个节点)的典型配置模式:1.安装前准备环境要求系统:Ubuntu/CentOS等主流Linux发行...

Linux入门使用教程

Linux入门一、初始化配置CentOS初始化安装在开始熟悉Linux操作命令之前,我们必须先搭建好Linux操作系统环境,我们这里选用的是Linux的发行版本CentOS7,在安装好CentOS操作...

06新手学习:Linux入门级命令教程

1、开启终端问题:什么是终端(Terminal)答:Linux操作系统中用于输入命令的位置打开后,效果如下图所示:2、Linux命令格式什么是Linux的命令?答:就是指在Linux终端(命令行)...

【笔记】windows10安装linux双系统教程(可能是现今最简单方法)

这周测试成功了大牛漂移菌教的树莓派系统镜像的压缩方法(【树莓派】小空间树莓派镜像系统备份方法img镜像文件压缩方法),虚拟机下备份镜像不太方便,无论是存储空间还是读卡操作都不方便。所以打算装个linu...

网络安全工程师:小白是如何让Kali Linux操作系统从U盘成功启动

一、背景介绍作为一名渗透测试工作人员(或者小白),在我们的日常工作或者学习中,我们不可能时时刻刻将自己的个人电脑(安装好KaliLinux的个人主机)带在身边,当我们没有带自己的个人电脑而需要进行渗...

Linux配置ip地址的两种方法

Linux配置ip地址的两种方法,实验环境为centos7.6方法1:nmcli工具配置(centos7以下版本不支持该方法)第一步,通过nmcliconnection查看网卡名称[root@lo...

Linux man 命令使用教程

简介man=manual(手册)命令用来查看Linux系统命令、函数、配置文件、系统调用等的官方文档。几乎所有标准程序和工具都有对应的man手册。基本语法man[options][s...

Linux程序安装与管理指南

在Linux系统中,安装和管理程序主要通过包管理器和手动编译安装两种主要方式实现。以下是详细的操作指南,涵盖常见发行版(如Ubuntu/Debian、CentOS/RHEL、Fedora等)的用法。一...

零基础保姆级教程!手把手教你免费玩转Linux安装+学习环境搭建!

前期准备安装VMware虚拟机首先你要安装VMware虚拟机,如果你还不知道VMware是什么可以去看我的VMware相关教程,里面有详细解答检查V-CPU虚拟化是否开启当我们在虚拟机安装系统的...

网络安全工程师:小白如何使用Kali Linux生成木马后门并实现免沙

1.背景介绍msfvenom是msfpayload和msfencode的结合体,可利用msfvenom生成木马程序,并在目标机上执行,在本地监听上线,在黑客圈子,这款工具略有名气。本次教程是Msfve...

Linux详解系列一:如何安装系统及客户端工具的使用

Linux是一种开放源码的操作系统,和Windows不同的是,由于其具有开源,稳定性强,安全,多用户操作等特点,它的使用场景非常广泛,比如企业中所使用的服务器中的操作系统,以及移动端的Andr...

4种方案供你选,微软发布《如何下载和安装Linux》教程

IT之家10月14日消息,微软近日发布了一个教程指南《如何下载和安装Linux》,介绍了使用WSL、本地安装、本地虚拟机和云端虚拟机4种方案。该指南重点介绍了用户在PC上运行Li...

嵌入式Linux开发教程:Linux Shell

本章重点介绍Linux的常用操作和命令。在介绍命令之前,先对Linux的Shell进行了简单介绍,然后按照大多数用户的使用习惯,对各种操作和相关命令进行了分类介绍。对相关命令的介绍都力求通俗易懂,都给...

Linux基础手把手教学:使用22.04系统

Linux基础手把手教学:使用Ubuntu22.04系统。1.这节来讲一下下边的目录结构,因为只有清楚了解linux下边的目录结构,才能很方便地进行操作。linux下边的目录结构较为简单...