展开菜单

字符串匹配算法基础版

字符串匹配算法基础版

最近小谭又被问了一个问题,编程语言中的字符串匹配函数是怎么实现的,是啥原理。 看来大猫又要展示他靠才华吃面的大招了。 小谭一边心里犯嘀咕,这还能有啥原理,直接用不就行了,管那么多干啥,一边对大猫说,今天又想要吃啥面了。 大猫就是这样,经常问你一个问题,你要不会,然后让你请他吃碗面,他给你讲清楚。 大猫腼腆一笑表示今天吃一碗拉面就行,估计是今天这个大招的技术含量不够高吧,一碗拉面就给应付了。 果然,大猫仅用 5 个字就形容了他的大招,暴力匹配法,小谭一听暴力法,...

数组中重复的数

之前有写过 找出数组中只出现一次的数,今天再来看下怎么找出数组中重复出现的数。 有一个长度为 n 的数组,所有的数字都在 0~n-1 的范围,现在要求找出数组中任意一个重复的数字。 这个题目看起来很简单,看看下面几种思路。 思路一: 先给数组排序,然后再遍历一遍有序数组,依次比较相邻元素,就很容易能找出数组中重复的值。使用快排排序的话时间复杂度为 O(nlogn) 。...

找出链表中倒数第K个节点

找出链表中倒数第K个节点

今天来看一道有意思的链表算法题目。 给到一个单向链表,要求找出该链表中倒数第 k 个节点,要求只能遍历一次链表,且空间复杂度为 O(1)。 思路1:如果能从链表尾部开始遍历,那只需倒序遍历 k 个节点即是要找出的节点,但是由于是单链表,只能从头结点开始遍历。 思路2:先遍历一遍该单链表,获取链表的总节点数 n,那么第 n-k+1 这个节点就是倒数第 k 个节点。所以第二次再遍历到第 n-k+1 这个节点即可,但是题目要求只能遍历一遍链表。 ...

打开一个网页背后都发生了什么

打开一个网页背后都发生了什么

这是一个老生常谈的话题,我今天还是想凭我自己的理解,用自己的话来捋一捋这个过程。 对于我们用户来说,只需要在浏览器中输入或者点开一个 url ,我们就直接可以看到网页内容了,但是这背后却经历非常复杂的故事,简单来说主要有下面四大过程: 1、浏览器根据域名找到对应的 ip 地址(远程服务器)。 2、浏览器与远程服务器建立连接(tcp 连接,三次握手)。 3、浏览器与远程服务器发送和接收数据。 4、浏览器与远程服务器断开连接。 ...

交换两个变量的骚操作

交换两个变量的骚操作

交换两个变量的值,我们常规做法是申请一个第三方变量,如果要求不能使用第三方变量,该怎么交换两变量呢? 今天介绍两种不依赖第三方变量的交换方法。 1、算术运算法 就是最基本的加减法,这里主要是利用了坐标思想。坐标轴上两个点,通过计算两点之间的距离来完成交换操作。大家可以参考下面这张坐标图来理解。 a = 5 b = 8 #计算a和b两个点到原点的距离之和 #并且赋值给a,这一步a的值已经发生...

找出数组中只出现一次的数

今天来看一道有意思的题,看起来很简单,但是要想到满足要求的答案没那么容易。 有一个非空整形数组,除了有一个只出现过一次的数,其他的数都出现且只出现过两次,现要求找出这个只出现过一次的数。时间复杂度不能超过 O(n),而且不能使用额外空间。 大概意思就是,比如从 [5,5,8,8,6,9,9] 数组中找出 6 这个只出现过一次的数。 本来可以想到对数组先进行排序,再遍历数组判断当前元素和前后元素是否相同,从而来找出那个只出现一次的元素。 但是题目要求时间复杂度...

三分钟看懂插入排序算法

今天我们还来聊一聊另一种排序算法,插入排序。 插入排序,顾名思义,插入操作是整个排序过程中的重要步骤。 首先有必要说明一点,一种特定的算法都是基于某种特定的数据结构的,我们这里的算法都是指数据存放于数组结构中的。 先来用人话给插入排序来个定义: 把数组分成已排序和未排序两个区间,以数组第一个元素当做已排序区间,剩下的即被当做未排序区间,每次都从未排序区间中找出一个元素来和已排序区间中的元素比较,并插入到已排序区间中的合适位置,直到未排序区间元素为 0 。 ...

经典小鸡算法

经典小鸡算法

小鸡问题是经典的基础算法问题,今天我们使用php解释并优化小鸡算法问题。 1、问题描述 公鸡5文钱一只,母鸡3文钱一只,小鸡3只一文钱,用100文钱买一百只鸡,其中公鸡,母鸡,小鸡都必须要有,问公鸡,母鸡,小鸡要买多少只刚好凑足100文钱。 2、算法分析 这是这个问题最常规的解法,看下程序的运行结果。 ...

通俗理解快排算法

通俗理解快排算法

快排是一种排序算法,是冒泡算法的一个优化。 快排的思想也比较简单,对于一个数据长度大于1的数组,随机找出其中一个元素来作为基准元素,然后再遍历一遍该数组,同时将每个元素与基准元素进行比较,如果某元素的值大于基准元素则把该元素放在基准元素的右边,反之如果某元素的值小于基准元素则把该元素放在基准元素的左边,这样遍历一遍下来基准元素左边的元素都小于基准元素,基准元素右边的元素都大于基准元素。接下来再依次把基准元素左右两边的元素按照上面同样的步骤做同样的处理,最终得到的就是一个有序数组。 下面分别使用php和pytho...

通俗理解二叉树重建

通俗理解二叉树重建

今天分享一个关于重建二叉树的算法。 首先简单介绍下二叉树的概念,树是计算机中的一种数据结构,二叉树又是一种特殊的树,每个节点至多只有两颗子树的树被称为二叉树。 二叉树的子树被称作左右子树,在节点左侧的被称作左子树,在节点右侧的被称作右子树,二叉树主要有三种遍历方式,分别是前序(也称先序)、中序、后序遍历,前序是指从根节点开始遍历,再到左子树,再到右子树,即:根 -> 左 -> 右,中序和后序遍历顺序分别为: 左 -> 根 -> 右,左 -> 右 -> 根。下面的图分别展示了二叉树的三种不同遍历方式。 ...

青蛙跳台阶算法分析

青蛙跳台阶问题在面试中经常会被问到,如果你之前没听过这个算法问题,那么在面试短时间内能给出完整的答案还是有一定的难度的,但是其实也并不算很难,看完这篇文章,相信你会恍然大悟的。 一只青蛙一次可以跳一级台阶,也可以一次跳两级台阶,现在有 n 级台阶,问青蛙一共有多少种跳法? 咋一看到这种问题,好像没有什么思路,不知道从哪里着手分析,那么我们就从最简单的情况开始分析,假如 n = 1,即一共只有一级台阶,显然一共就只有一种跳法,假如...

单链表反转问题

今天聊一个关于单链表反转的问题,已知一个单链表,给出头结点,现要求定义一个函数,输入头结点然后输出反转后的链表。 #链表反转前 1->2->3->4->5->6->7->8->9 #链表反转后 1<-2<-3<-4<-5<-6<-7<-8<-9 首先我一看到这个问题,想到的是利用一个数组,将单链表按顺序遍历并把每个节点的值依次存放到数组中,然后再将数组倒序输出即是反转后的链表。这种办法其实也没错,但是不够好,因为需要浪费额外的空间,且时间复...