首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

几道 BAT 算法面试中经常问的「字符串」问题

这道题目是 初级程序员 面试的时候经常遇到的一道算法题,而且面试官喜欢面试者手写! 题目描述 给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。...先假设是验证一个单词 level 是否是回文字符串,通过概念涉及到 正 与 反 ,那么很容易想到使用双指针,从字符的开头和结尾处开始遍历整个字符串,相同继续向前寻找,不同直接返回 false。...当左右指针都找到字母数字时,可以进行比较的时候,比较这两个字符,如果相等,两个指针向它们的前进方向挪动,然后继续比较下面两个分别找到的字母数字,若不相等,直接返回 false。 动画描述 ?...题目描述 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个字典中出现的单词。 说明: 拆分时可以重复使用字典的单词。...你可以假设字典没有重复的单词。 题目解析 与上面的第二题 分割回文串 有些类似,都是拆分,但是如果此题采取 深度优先搜索 的方法来解决的话,答案是超时的,不信的同学可以试一下~ 为什么会超时呢?

86920

几道 BAT 算法面试中经常问的「字符串」问题

这道题目是 初级程序员 面试的时候经常遇到的一道算法题,而且面试官喜欢面试者手写! 题目描述 给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。...先假设是验证一个单词 level 是否是回文字符串,通过概念涉及到 正 与 反 ,那么很容易想到使用双指针,从字符的开头和结尾处开始遍历整个字符串,相同继续向前寻找,不同直接返回 false。...当左右指针都找到字母数字时,可以进行比较的时候,比较这两个字符,如果相等,两个指针向它们的前进方向挪动,然后继续比较下面两个分别找到的字母数字,若不相等,直接返回 false。...题目描述 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个字典中出现的单词。 说明: 拆分时可以重复使用字典的单词。...你可以假设字典没有重复的单词。 题目解析 与上面的第二题 分割回文串 有些类似,都是拆分,但是如果此题采取 深度优先搜索 的方法来解决的话,答案是超时的,不信的同学可以试一下~ 为什么会超时呢?

78720
您找到你想要的搜索结果了吗?
是的
没有找到

Leetcode【60、79、93、131、842】

因此,我们可以一位一位的构造答案,根据 k 值判断落在哪个区间,找到开头数字加入结果;然后,从数组删除该开头数字,并确定 k 值位于当前区间的第几个,更新 k 值;按照上述方法进行操作,直到得到一个全排列...回溯函数,对于每个字符的上下左右四个位置进行深搜(要保证不越界),如果 board 的下一个位置的字符匹配 word 的下一个字符,修改 board 当前字符为 "" 进行递归调用。...如果可以,拓展回文串前缀列表。最后,遍历完所有字符后,列表存储的就是最终结果。...2 ,划分 s = "ab" 前缀 ab,ab 不是回文串,继续划分下一个前缀;没有前缀,返回步骤 1; 6、步骤 1 ,划分 s = "aab" 前缀 aa,aa 是回文串,将其加入 path...",说明划分完毕,将结果 path = [aa,b] 加入到 ans ,直接返回到步骤 7(没有前缀,继续返回)、步骤 6; 9、步骤 6 ,划分 s = "aab" 前缀 aab,aab 不是回文

64530

python 面试题-收集100+面试题笔试题

输出指定字符串A字符串B第一次出现的位置,如果B不包含A,输出-1 从 0 开始计数 A = “hello” B = “hi how are you hello world, hello yoyo...1.12 查找字符串最后一次出现位置 输出指定字符串A字符串B中最后出现的位置,如果B不包含A,输出-1 从 0 开始计数 A = “hello” B = “hi how are you hello...a = 12345 第2章 小学数学题 2.1.水仙花数 如果一个 3 位数等于各位数字的立方和,称这个数为水仙花数。...”, 1] 3.2列表切片 如果有一个列表a=[1,3,5,7,11] 问题:1如何让它反转成[11,7,5,3,1] 2.取到奇数位值的数字,如[1,5,11] 3.3列表大小排序 问题:对列表a 数字从小到大排序...nums 和一个目标值target ,请你数组找出和为目标值的那两个整数,并返回他 们的数组下标。

6.5K20

Python语法

update() 使用指定的键值对字典进行更新 values() 返回字典中所有值的列表 列表/数组的方法 方法 描述 append() 列表的末尾添加一个元素 clear() 删除列表的所有元素...index() 字符串搜索指定的值并返回它被找到的位置。 isalnum() 如果字符串的所有字符都是字母数字返回 True。...isdigit() 如果字符串的所有字符都是数字返回 True。 isidentifier() 如果字符串是标识符,返回 True。...x in y not in 如果对象存在具有指定值的序列,返回 True。...search 如果字符串的任意位置存在匹配,返回 Match 对象 split 返回每次匹配时拆分字符串的列表 sub 用字符串替换一个或多个匹配项 元字符 元字符是具有特殊含义的字符: 字符

3.2K20

六十六、Leetcode数组系列(中篇)

数组重复的数字 先来一个简单的,见面礼。题目来源于 LeetCode 上的剑指 Offer 系列 面试题03. 数组重复的数字。...#一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组任意一个重复的数字。...,就是字典,遍历整个数组,当这个数字没有出现过字典的时候将其加入进去,如果在哈希表直接返回即可。...# 回文的长度是奇数还是偶数的情况,如果是奇数形回文,就以当前字符为中心左右两边寻找,例如回文"bab";如果是偶数形回文,需要两个字符,并且这两个字符是相等的,则需要以当前字符和相邻的字符为中心向左右两边寻找...LeetCode 第 53 题:最大子序和 #给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回最大和。

54010

Leetcode 1-10

Two sum 问题描述:给定一个整数数组返回两个数字的索引,使它们加起来等于一个特定的目标。...,是列表长度为2,否则长度为1,只存储中间的值,存储完即返回,后面的值无需比较,这种方法大规模数据下更快占用内存更小。...,数组第i个元素表示以 i 为中心的最长回文的半径,利用回文数的对称性,一个大的回文数后面的索引可以利用对称性映射前面而大大简化计算。...如果不能执行有效的转换,返回一个零值。...方法:首先判断字符的长度,长度为0,返回0,长度为1,判断是否为数字,不为数字返回0,还要判断整个str是否都是空格,是返回0;然后找到第一个不是空格的索引,在这个索引下依次递加查询数字查询之前要判断第一个字母是否为负号或者正号

48730

LeetCode 刷题记录 1-5

同时,将 p 和 q 前进到下一个结点 检查 carry = 1 是否成立,如果成立,返回列表追加一个含有数字 1 的新结点 返回哑结点的下一个结点 image.png 代码 Java 解法...接下来我们根据两数组长度之和的「奇偶性」分开讨论: 「情况 1」:如果 A 数组和 B 数组的总长度是「偶数」,中位数的选择条件为: ❝左半部分的长度等于右半部分,且左半部分最大的值小于等于右半部分最小的值...❞ image.png 「情况 2」:如果 A 数组和 B 数组的总长度是「奇数」,中位数的选择条件为: ❝左半部分的长度比右半部分大 1,且左半部分最大的值小于等于右半部分最小的值。...新的字符串具有如下性质: 新字符串的任意一个回文子串原始字符串均有唯一回文子串与之对应 新字符串的回文子串一定以分隔符作为两边的边界 新字符串的回文子串的长度一定是奇数(如下图所示) ?...第二步:计算辅助数组 p 辅助数组 p 记录了新字符串以每个字符为中心,向左右两边同时扩散能够达到的「最大步数」。 以字符串 abbabb 为例,辅助数组 p 如下表所示: ?

43850

程序员进阶之算法练习(四十九)LeetCode

正文 题目1.两数之和 题目链接 题目大意: 给定一个整数数组 nums 和一个目标值 target,请你数组找出和为目标值的那 两个 整数,并返回他们的数组下标。...但是,数组同一个元素不能使用两遍。...假设我们的环境只能存储 32 位大小的有符号整数,那么数值范围为 [−231, 231 − 1]。...题目解析: 将数字转成字符串,然后开始从左右两边开始遍历,如果遇到不一样的字符串输出false; 如果没有发现不一样的字符,左右边界递进,最后输出true; class Solution {...5.最长公共前缀 题目链接 题目大意: 编写一个函数来查找字符串数组的最长公共前缀。 如果存在公共前缀,返回空字符串 ""。

44040

用于日常编程问题的 10 个 Python 代码片段

本文中,我们将深入研究十个可用于解决日常编程挑战的 Python 代码片段。我们将指导您完成每个片段,以简单的步骤阐明运作方式。 交换两个变量 切换两个变量的值是编程的常见任务。...列表查找所有唯一元素 如果你想在列表中找到所有独特的元素,你将能够利用Python的集合数据结构 - 例 your_list = [1, 2, 3, 2, 2, 4, 5, 6, 2, 7, 8, ...),如果数字小于 2,返回 False,然后确认该数字是否可以被 2 到数字平方根的任何数字整除(向上调整)。...找到任何除数时,它返回 False;别的东西,它返回正版。 合并两个词典 合并两个词典是一项常见的任务,尤其是使用配置或设置时。...如果存在重复键,dict2 的值将覆盖字典 1 的值。 从字符串删除标点符号 处理文本数据时,可能需要从字符串删除标点符号。

23520

TypeScript实现队列与双端队列

判断队列是否为空,判断队列的元素数量是否为0(队列大小 - 队首元素位置) 队首元素,获取当前队列的队首元素并返回。 队列大小,获取队列的元素数量并返回(队列大小 - 队首元素位置)。...实现思路 双端队列相比队列多了两端都可以出入元素,因此普通队列的获取队列大小、清空队列、队列判空、获取队列的所有元素这些方法同样存在于双端队列且实现代码与之相同。...实现思路 知道游戏规则后,我们来捋一下实现思路: 声明一个函数,参数为:参与人员数组,多少次为一轮 函数内部实例化一个队列,声明淘汰人员列表变量。...传进来的次数遍历完成(鼓声停止),队首元素出栈,将队首元素追加至淘汰人员列表。 队列只剩下一个元素时,剩余元素出队,返回胜利者和淘汰者列表。...遍历队列,队首出队和队尾出队 判断队首和队尾的字符是否相等,如果不想等回文结果为false 如果队列的大小大于1且会问结果为true继续比对队首元素和队尾元素 实现代码 我们捋清了回文的实现思路后,

55440

「数据结构与算法Javascript描述」栈

当向栈压入一个新元素时,需要将其保存在数组变量 top 所对应的位置,然后将 top 值加 1,让指向数组中下一个空位置。...持续将栈内元素弹出,直到栈为空,依次将这些元素排列,就得到转换后数字的字符串形式。 「此算法只针对基数为 2~9 的情况。」 使用栈, JavaScript 实现该算法就是小菜一碟。...比如,单词“dad”、“racecar”就是回文如果忽略空格和标点符号,下面这个句子也是回文,“A man, a plan, a canal: Panama”;数字 1001 也是回文。...使用栈,可以轻松判断一个字符串是否是回文。我们将拿到的字符串的每个字符按从左至右的顺序压入栈。当字符串的字符都入栈后,栈内就保存了一个反转后的字符串,最后的字符栈顶,第一个字符栈底。...字符串完整压入栈内后,通过持续弹出栈的每个字母就可以得到一个新字符串,该字符串刚好与原来的字符串顺序相反。我们只需要比较这两个字符串即可,如果它们相等,就是一个回文

40320

leetcode 双指针算法专题

2)判断链表是否有环:如果链表存在环,则在链表上不断前进的指针会一直环里绕圈子,且不能知道链表是否有环。使用快慢指针,当链表存在环时,两个指针最终会在环中相遇。...循环 下一步就是 对找到的这个数字 对他 数组 也就是nums里面 进行索引值的查找 最后返回找到的这两个数字数组的 索引 在这里要注意的一点就是 想要利用双指针进行遍历 前提是对这个数组进行排序...然后一个指针对nums1进行遍历 一个指针对nums2进行遍历,去比较他们的大小 谁小,谁就放到temp,然后指针记得移位置 如果nums1已经遍历完了,那么就把nums2的元素append...进temp 如果nums2已经遍历完了,那么就把nums1的元素append进temp 最后将temp数组 赋值 给 nums1数组 class Solution(object): def...创建一个全为0长度为n的列表 双指针进行首尾遍历 如果前面的平方大于后面的平方,那么就把前面的值加入到创建的列表,然后这个数字较大的指针加一,以此类推 class Solution(object)

51930

算法:字符串

最早的时候,人们制定了一个包含 127 个字符的编码表 ASCII 到计算机系统。ASCII 编码表的字符包含了大小写的英文字母、数字和一些符号。...而根据文本搜索模式串方式的不同,可以将单模式匹配 算法分为以下三种: 基于前缀搜索方法:搜索窗口内从前向后(沿着文本的正向)逐个读入文本字符,搜索窗口中文本和模式串的最长公共前缀。...例题 107 验证回文串 题目大意:描述:给定一个字符串 s。要求:验证它是否是回文串,如果回文串,返回 True,否则返回 False。只考虑字母和数字字符, 可以忽略字母的大小写。...,说明不是回文串,直接返回False 如果遇到 left==right ,跳出循环,说明该字符串是回文串,返回True。...words存放单词,使用字符串变量cur存放当前单词 遍历字符串,对于当前字符而 如果遇到空格,如果当前单词不为空,则将当前单词存入数组words,并将当前单词置为空串 如果遇到字符,: 将其存入当前单词

2.7K30

TypeScript 实战算法系列(二):实现队列与双端队列

判断队列是否为空,判断队列的元素数量是否为0(队列大小 - 队首元素位置) 队首元素,获取当前队列的队首元素并返回。 队列大小,获取队列的元素数量并返回(队列大小 - 队首元素位置)。...实现思路 双端队列相比队列多了两端都可以出入元素,因此普通队列的获取队列大小、清空队列、队列判空、获取队列的所有元素这些方法同样存在于双端队列且实现代码与之相同。...实现思路 知道游戏规则后,我们来捋一下实现思路: 声明一个函数,参数为:参与人员数组,多少次为一轮 函数内部实例化一个队列,声明淘汰人员列表变量。...传进来的次数遍历完成(鼓声停止),队首元素出栈,将队首元素追加至淘汰人员列表。 队列只剩下一个元素时,剩余元素出队,返回胜利者和淘汰者列表。...遍历队列,队首出队和队尾出队 判断队首和队尾的字符是否相等,如果不想等回文结果为false 如果队列的大小大于1且会问结果为true继续比对队首元素和队尾元素 实现代码 我们捋清了回文的实现思路后,

1.2K10

Python0基础(下)——期末不挂科

调用函数的时候可以指定(调用函数时,默认参数的值如果没有传入,被认为是默认值),即max(5,6) 可变参数:a代表可变参数,a使元组数据类型 def mysum(*;a)可变参数函数调用时候..., main函数输出。...,和我高中初赛差不多,都是入门,给定一个概念来考察循环+判断,也比较简单,但是很有必要学一下 水仙花数 所谓“水仙花数”是指一3位数,各位数字立方和等于该数本身。...: print('不是回文') 循环笨办法: s[0:len(s)//2]==s[-1:len(s)//2:-1] python很强大,可以逆着来判断,但是c可能要求比较多 列表插入 ls...方法就是:用数x对从2到x平方根依次取模,如果结果为0,说明x不是质数,如果一遍判断下来取模结果都不为0,说明x为素数 import math x = int(input()) f = 0 for

31220

扫码

添加站长 进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

活动推荐

    运营活动

    活动名称
    广告关闭
    领券