深圳福田 外贸网站建设,定制化网站开发多少钱,网商之家,滁州网站建设价格LeetCode 习题 1 - 101. 两数之和2. 两数相加3. 无重复字符的最长子串4. 寻找两个正序数组的中位数5. 最长回文子串6. N 字形变换7. 整数反转8. 字符串转换整数 (atoi)9. 回文数10. 正则表达式匹配1. 两数之和 给定一个整数数组 nums 和一个整数目标值 target#xff0c;请你在…
LeetCode 习题 1 - 101. 两数之和2. 两数相加3. 无重复字符的最长子串4. 寻找两个正序数组的中位数5. 最长回文子串6. N 字形变换7. 整数反转8. 字符串转换整数 (atoi)9. 回文数10. 正则表达式匹配1. 两数之和 给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 示例 1 输入nums [2,7,11,15], target 9 输出[0,1] 解释因为 nums[0] nums[1] 9 返回 [0, 1] 。 示例 2 输入nums [3,2,4], target 6 输出[1,2] 示例 3 输入nums [3,3], target 6 输出[0,1] 提示 2 nums.length 104 -109 nums[i] 109 -109 target 109 只会存在一个有效答案 进阶你可以想出一个时间复杂度小于 O(n2) 的算法吗 通过次数4,194,521提交次数7,931,754 来源力扣LeetCode 链接https://leetcode.cn/problems/two-sum 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 第一遍暴力计算复杂度 O(n^2)
class Solution:def twoSum(self, nums: List[int], target: int) - List[int]:n len(nums)for i in range(n-1):for j in range(i1,n):if nums[i] nums[j] target:return [i,j] 竟然还能击败这么多人吗难道这不是最土的办法吗 然后想办法优化下利用一下 python 本身的方法
第二遍排序后计算嗯其实我也不知道复杂度是多少但他就是运行时间减少了那么多
class Solution:def twoSum(self, nums: List[int], target: int) - List[int]:arr [_ for _ in nums]arr.sort(reverseTrue)n len(arr)for i in range(n-1):for j in range(1,n):if arr[i] arr[j] target:pos nums.index(arr[i])if arr[i] ! arr[j]:return [pos,nums.index(arr[j])]else:return [pos,nums[pos1:].index(arr[j])pos1] 第三遍利用集合set来看看
class Solution:def twoSum(self, nums: List[int], target: int) - List[int]:n {}for i in range(len(nums)):if nums[i] in n.keys():n[nums[i]] (n[nums[i]] [i])[:2]else:n[nums[i]] [i]for i in n.keys():if target i * 2:if len(n[i])1:return n[i]continueif target - i in n.keys():return [n[i][0],n[target - i][0]]
https://leetcode.cn/submissions/detail/403539238/ 内存消耗越来越大了。。。到底怎么能把内存消耗也减掉一些呢 第四遍实在搞不懂抄一下官方题解吧
class Solution:def twoSum(self, nums: List[int], target: int) - List[int]:hashtable dict()for i, num in enumerate(nums):if target - num in hashtable:return [hashtable[target - num], i]hashtable[nums[i]] ireturn []诧异了执行时间居然比我第三遍的还多一点。。。吓得我多执行了几次第三遍代码哦赶巧了啊平均用时还是40多一点嗯这个题目就确定了用hashtable、dict之类的方法就是最好的办法了
2. 两数相加 给你两个 非空 的链表表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的并且每个节点只能存储 一位 数字。 请你将两个数相加并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外这两个数都不会以 0 开头。 示例 1 输入l1 [2,4,3], l2 [5,6,4] 输出[7,0,8] 解释342 465 807. 示例 2 输入l1 [0], l2 [0] 输出[0] 示例 3 输入l1 [9,9,9,9,9,9,9], l2 [9,9,9,9] 输出[8,9,9,9,0,0,0,1] 提示 每个链表中的节点数在范围 [1, 100] 内 0 Node.val 9 题目数据保证列表表示的数字不含前导零 通过次数1,641,150提交次数3,875,235 来源力扣LeetCode 链接https://leetcode.cn/problems/add-two-numbers 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 老顾是个野路子链表是个啥东西也都是最近才开始接触平时工作里真就没用上过这东西。。。 还好题目中代码给了个 ListNode 的构造不用一头雾水的琢磨了然后大概也明白 Node 是个什么东西了就琢磨了第一个版本的代码
class Solution:def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) - Optional[ListNode]:u l1d l2r ListNode()z rf 0n 0while u or d or n0:if f:r.next ListNode()r r.nexts (u.val if u else 0) (d.val if d else 0) nr.val s % 10n s // 10u u.next if u else Noned d.next if d else Nonef 1return z其实这个题就是逆序的10进制加法不过所有数都是倒着的第一个是各位数第二位是十位数第三位是千位数这样的。。。最后返回的链表要求也是逆序的这就ok
嗯。。。。用了很多没啥意义的变量纯粹是懒得改了提交的时候就是这样算法好像也没啥算法老顾对链表真的不懂不知道这种单向链表也不知道对不对怎么就能方便的返回每个节点的值就这么用本办法弄出来了然后开始学习去看官方题解。。。好吧竟然没有 python 版本的题解而 java 的和 c# 的居然方法内的内容一毛一样。。。除了变量更容易让人读懂和老顾的写法也没啥本质区别了。。。瞎猫碰到死耗子了
3. 无重复字符的最长子串 给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: s “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”所以其长度为 3。 示例 2: 输入: s “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”所以其长度为 1。 示例 3: 输入: s “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”所以其长度为 3。 请注意你的答案必须是 子串 的长度“pwke” 是一个子序列不是子串。 提示 0 s.length 5 * 104 s 由英文字母、数字、符号和空格组成 通过次数2,182,219提交次数5,580,531 来源力扣LeetCode 链接https://leetcode.cn/problems/longest-substring-without-repeating-characters 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 还好这个题目看着就很简单嗯从第一个字符遍历然后记录遍历的起始位置碰到重复的字符记录长度并和最大长度比较然后遍历的起始位置从重复的字符后一个开始。。。嗯思路很清晰来写代码了
class Solution:def lengthOfLongestSubstring(self, s: str) - int:n len(s)if n2:return nmx 1# 576ms,15.1mbpos 0while pos n:nxt 1if pos nxt n:breakfinal 0while s[pos nxt] not in s[pos:pos nxt]:if mx nxt 1:mx nxt 1nxt 1if pos nxt n:final 1breakif final 1:breakpos s[pos:pos nxt].index(s[pos nxt]) 1return mx额。。。。这个成绩有点惨不忍睹啊。。。。倒数的前8%。。。。。琢磨琢磨怎么给优化一下思路应该没什么大问题吧 嗯pos 和 nxt 意义不大不如取消这两个变量直接用字符串代替也不再用 s[pos:posnxt] 方式计算直接用一个字符串代替这一堆
class Solution:def lengthOfLongestSubstring(self, s: str) - int:n len(s)if n2:return nmx 1# 100ms,15.1mbl for i in range(n):while s[i] in l:l l[1:]l s[i]mx max(mx,len(l))return mx嗯。。。。看着舒服很多这次不至于那么惨的成绩了吧看看先 https://leetcode.cn/submissions/detail/403660974/ 嗯碰到一次赶巧的成绩那估计我的这个代码也没啥问题了翻了翻官方题解。。。。好吧不能说没啥区别只能说完全一个路子
4. 寻找两个正序数组的中位数 给定两个大小分别为 m 和 n 的正序从小到大数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 算法的时间复杂度应该为 O(log (mn)) 。 示例 1 输入nums1 [1,3], nums2 [2] 输出2.00000 解释合并数组 [1,2,3] 中位数 2 示例 2 输入nums1 [1,2], nums2 [3,4] 输出2.50000 解释合并数组 [1,2,3,4] 中位数 (2 3) / 2 2.5 提示 nums1.length m nums2.length n 0 m 1000 0 n 1000 1 m n 2000 -106 nums1[i], nums2[i] 106 通过次数889,905提交次数2,135,574 来源力扣LeetCode 链接https://leetcode.cn/problems/median-of-two-sorted-arrays 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 其实题目到是真不难问题在于要理解题意。。。开始没弄明白什么叫中位数看了看两个示例还以为是平均数一提交人家不认。。。 额。。。。那中位数是啥难道是两个数组中合并后最中间的那一个或两个数的平均数那就再试试吧
一通操作猛如虎还好成绩不是250
class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) - float:arr nums1 nums2arr.sort()n (len(arr) 1) // 2 - 1if len(arr) % 2 1:return arr[n]else:return (arr[n] arr[n1]) / 2当然这里的运算取巧了毕竟不管 js 也好python 也好排序已经不是主要目标了通常都会直接用系统提供的办法完成这次只是确定了中位数的概念。。。。嗯试着不用自身的 sort 自己来按顺序插入数字。。。反而慢了一半算了不折腾了。。。估计这个题考的目的就是排序插入新数组70ms完成应该也可以了就当我过了嘿嘿 说句题外话这个题目的评价难度居然是困难没看出困难在哪里。。。。
5. 最长回文子串 给你一个字符串 s找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同则该字符串称为回文字符串。 示例 1 输入s “babad” 输出“bab” 解释“aba” 同样是符合题意的答案。 示例 2 输入s “cbbd” 输出“bb” 提示 1 s.length 1000 s 仅由数字和英文字母组成 通过次数1,322,154提交次数3,534,763 来源力扣LeetCode 链接https://leetcode.cn/problems/longest-palindromic-substring 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 第一遍还是暴力思路这人呐脑子闲置的久了就用不上了。。。
class Solution:def longestPalindrome(self, s: str) - str:n len(s)if n 2:return sr s[0]for i in range(n):for j in range(i1,n1):if s[i:j] s[i:j][::-1]:if j-ilen(r):r s[i:j]return r然后不出所料的没有能通过 这个是真没想法啊。。。。只好去看题解嗯嗯嗯嗯学了很多写法印象最深刻的并且自己能理解透的也就是那个Manacher算法。。。设计真精巧啊
class Solution:def longestPalindrome(self, s: str) - str:r t ^# #.join(s) #$n len(t)p [0 for _ in range(n)]for i in range(1,n-1):while t[i - p[i] - 1] t[i p[i] 1]:p[i] 1mx max(p)idx p.index(mx)b (idx - mx) // 2r s[b:bmx]return r这。。。。跑了好几遍基本都在1000ms左右点开提交结果一看。。。排不上号啊。。。 看来还得继续学习而且看官方题解已经不够了得学别人的写法了好在可以点执行用时分布里的时间点看别人的代码真棒
先找了个900ms左右的答案。。。嗯中心扩散法学习学习
# 以下内容抄自leetcode第5题908ms答案实际运行能达到600ms左右
class Solution:def longestPalindrome(self, s: str) - str:#暴力解法# cur_str max_str # for i in range(len(s)):# for j in s[i:]:# cur_str j# if cur_str cur_str[::-1] and len(cur_str) len(max_str):# max_str cur_str# cur_str # return max_str#中心扩散法left right start 0cur_len max_len 1 for i in range(len(s)):left i - 1right i 1while left 0 and s[i] s[left]:left - 1cur_len 1while right len(s) and s[i] s[right]:right 1cur_len 1while left 0 and right len(s) and s[left] s[right]:left - 1right 1cur_len 2print(s[left], cur_len,end QWQ )while cur_len max_len:max_len cur_lenstart left 1cur_len 1 #少了这句找了一小时bugprint(start, end)print(max_len)return s[start: start max_len]
# 以下内容抄自leetcode第5题800ms答案实际运行能达到600ms左右
class Solution:def longestPalindrome(self, s: str) - str:palindrome for i in range(len(s)):len1 len(self.getLongestPalindrome(s,i,i))if len1 len(palindrome):palindrome self.getLongestPalindrome(s,i,i)len2 len(self.getLongestPalindrome(s,i,i1))if len2 len(palindrome):palindrome self.getLongestPalindrome(s,i,i1)return palindromedef getLongestPalindrome(self,s,l,r):while l0 and rlen(s) and s[l]s[r]:l-1r1return s[l1:r]可惜只能看到答案不知道是哪位同学提交的嗯都是提交的源代码我一个字符都没改动过的。 这两个答案都是中心扩散法老顾就不说题解了自己写一遍试试看其他同学关于中心扩散法的说明很多官方题解里也有
# 老顾自己搞一版
class Solution:def longestPalindrome(self, s: str) - str:n len(s)if n 2 or s s[::-1]:return st s[0]for i in range(n):mx 1while i - mx 0 and i mx n and s[i - mx] s[i mx]:r s[i - mx:i mx 1]mx 1if len(r) len(t):t rmx 1while i - mx 1 0 and i mx n and s[i - mx 1] s[i mx]:r s[i - mx 1:i mx 1]mx 1if len(r) len(t):t rreturn t 额。。。。。。这执行用时超出我的预料啊我还以为也就600ms左右呢。。。。
然后我们来抄个最厉害的答案吧40ms执行时间的。。。
# 以下内容抄自leetcode第5题40ms答案
class Solution:def longestPalindrome(self, s: str) - str: if len(s) 2 or s s[::-1]: return s res s[0] maxlen 1 for i in range(1, len(s)): odd s[i - maxlen - 1: i 1]even s[i - maxlen: i 1]if even even[::-1] and i - maxlen 0:res evenmaxlen 1continueif odd odd[::-1] and i - maxlen - 1 0:res oddmaxlen 2continuereturn reshttps://leetcode.cn/submissions/detail/403938742/ 肯定是我的电脑和网络问题竟然跑了几次都没挨到40人家的最高成绩是36ms。。。。 这位的办法更直接直接判断当前位置按最大长度中心扩散得到单双两个字符串如果其中一个是回文。。。省略了前边的判定估计在python中好用其他语言环境就难言了
另一个更暴力的
# 以下内容抄自leetcode第5题56ms答案
class Solution:def longestPalindrome(self, s: str) - str:#resfor i in range(len(s)):startmax(0,i-len(res)-1)temps[start:i1]if temptemp[::-1]:restempelse:temptemp[1:]if temptemp[::-1]:restempreturn res效率虽然略有不如前边的但他的思路更简洁实现起来更简单啊。。。。
抄个java的40ms看看。。。其实也差不多。。。
// 以下内容抄自leetcode第5题40ms答案
class Solution {public String longestPalindrome(String s) {if(s.length()0){return s;}if(s.length()1){return s;}if(s.length()2){if(s.charAt(0)s.charAt(1)){return s;}else{return s.substring(0,1);}}String result;for(int i 1;is.length();i){char a s.charAt(i);int start i-1;int end i1;while (start0ends.length()-1){if(end-i1){while (s.charAt(start)a){start - 1;if(start0){break;}}while (s.charAt(end)a){end 1;if(ends.length()-1){break;}}String temp s.substring(start1,end);if(temp.length()result.length()){resulttemp;}}if(start0||ends.length()-1){break;}if(s.charAt(start)s.charAt(end)){String temp s.substring(start,end1);if(temp.length()result.length()){resulttemp;}start--;end;continue;}else{break;}}}return result;}
}也是中心扩散法嗯确定了manacher方法很精巧很容易记但效率真不如中心扩散
6. N 字形变换 将一个给定字符串 s 根据给定的行数 numRows 以从上往下、从左到右进行 Z 字形排列。 比如输入字符串为 “PAYPALISHIRING” 行数为 3 时排列如下 P A H N A P L S I I G Y I R 之后你的输出需要从左往右逐行读取产生出一个新的字符串比如“PAHNAPLSIIGYIR”。 请你实现这个将字符串进行指定行数变换的函数 string convert(string s, int numRows); 示例 1 输入s “PAYPALISHIRING”, numRows 3 输出“PAHNAPLSIIGYIR” 示例 2 输入s “PAYPALISHIRING”, numRows 4 输出“PINALSIGYAHRPI” 解释 P I N A L S I G Y A H R P I 示例 3 输入s “A”, numRows 1 输出“A” 提示 1 s.length 1000 s 由英文字母小写和大写、‘,’ 和 ‘.’ 组成 1 numRows 1000 通过次数531,132提交次数1,019,546 来源力扣LeetCode 链接https://leetcode.cn/problems/zigzag-conversion 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 呦这个应该不难吧结果老顾自己琢磨了半天才弄出第一个版本
class Solution:def convert(self, s: str, numRows: int) - str:n len(s)if n numRows:return sif numRows1:return sr [ for _ in range(numRows)]x numRows*2-2for i in range(numRows):r[i] [s[_] if _%xi or (_%xnumRows and numRows-(_%x-numRows1)-1i) else for _ in range(n)]#for i in r:# print(.join(i))return .join([.join(i) for i in r])其实就是一个折叠位置的取余与原有高度的差问题。。。嗯这个效率太感人了 惨不忍睹啊。。赶紧简化 代码
class Solution:def convert(self, s: str, numRows: int) - str:n len(s)if n numRows:return sif numRows1:return sx numRows*2-2r [ for _ in range(numRows)]for i in range(n):r[min(i % x,x-i%x)] s[i]return .join(r)好像也诶怎么动就是把按行循环改成按字符循环。。。第一版是按行从字符串里提取应该在该行的字符第二版是按字符分配到应该去的行。。。。结果效率。。。 效率还是不错的。。。问题是才53% 这得抄作业来个36ms的答案看看
# 以下内容抄自leetcode第6题36ms答案
class Solution:def convert(self, s: str, numRows: int) - str:ans []*numRowsflag -1cnt 0if numRows2:return s for ch in s:ans[cnt] ch if cnt 0 or cnt numRows-1:flag flag * -1 cnt flagreturn .join(ans)额。。。。感觉差不多啊为什么比不过呢算了这个答案分布基本就差那么几ms老顾是不懂的了不跟你们这帮牲口拼了继续做下一题去了
7. 整数反转 给你一个 32 位的有符号整数 x 返回将 x 中的数字部分反转后的结果。 如果反转后整数超过 32 位的有符号整数的范围 [−2^31, 2^31 − 1] 就返回 0。 假设环境不允许存储 64 位整数有符号或无符号。 示例 1 输入x 123 输出321 示例 2 输入x -123 输出-321 示例 3 输入x 120 输出21 示例 4 输入x 0 输出0 提示 -231 x 231 - 1 通过次数1,150,381提交次数3,247,643 来源力扣LeetCode 链接https://leetcode.cn/problems/reverse-integer 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 Hmmmmmmm我的电脑难道是32位的
class Solution:def reverse(self, x: int) - int:s str(x)f 1 if s[0] -:f -1s s[1:]e int(s[::-1]) * freturn e if e-2**31 and e2**31-1 else 0额。。。。。。我都作弊了居然还不是头部10% 算了这个题还是按照不作弊的方式自己尝试下吧。
class Solution:def reverse(self, x: int) - int:y 0z 1 if x 0:z -1x * zwhile x 0:y y * 10 x % 10x // 10y * zif y (2**31 - 1) or y (2**31 * -1):return 0return y https://leetcode.cn/submissions/detail/403955924/ 嗯。。。。老顾真的不知道怎么装作不支持64位。。。所以最后的那个比大小估计是有问题的然后答案估计也很集中在几个时间点上就不抄答案了这次
8. 字符串转换整数 (atoi) 请你来实现一个 myAtoi(string s) 函数使其能将字符串转换成一个 32 位有符号整数类似 C/C 中的 atoi 函数。 函数 myAtoi(string s) 的算法如下 读入字符串并丢弃无用的前导空格 检查下一个字符假设还未到字符末尾为正还是负号读取该字符如果有。 确定最终结果是负数还是正数。 如果两者都不存在则假定结果为正。 读入下一个字符直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。 将前面步骤读入的这些数字转换为整数即“123” - 123 “0032” - 32。如果没有读入数字则整数为 0 。必要时更改符号从步骤 2 开始。 如果整数数超过 32 位有符号整数范围 [−2^31, 2^31 − 1] 需要截断这个整数使其保持在这个范围内。具体来说小于 −231 的整数应该被固定为 −2^31 大于 2^31 − 1 的整数应该被固定为 2^31 − 1 。 返回整数作为最终结果。 注意 本题中的空白字符只包括空格字符 ’ ’ 。 除前导空格或数字后的其余字符串外请勿忽略 任何其他字符。 示例 1 输入s “42” 输出42 解释加粗的字符串为已经读入的字符插入符号是当前读取的字符。 第 1 步“42”当前没有读入字符因为没有前导空格 ^ 第 2 步“42”当前没有读入字符因为这里不存在 ‘-’ 或者 ‘’ ^ 第 3 步“42”读入 “42” ^ 解析得到整数 42 。 由于 “42” 在范围 [-2^31, 2^31 - 1] 内最终结果为 42 。 示例 2 输入s -42 输出-42 解释 第 1 步 -42读入前导空格但忽视掉 ^ 第 2 步 -42读入 ‘-’ 字符所以结果应该是负数 ^ 第 3 步 -42读入 “42” ^ 解析得到整数 -42 。 由于 “-42” 在范围 [-2^31, 2^31 - 1] 内最终结果为 -42 。 示例 3 输入s “4193 with words” 输出4193 解释 第 1 步“4193 with words”当前没有读入字符因为没有前导空格 ^ 第 2 步“4193 with words”当前没有读入字符因为这里不存在 ‘-’ 或者 ‘’ ^ 第 3 步“4193 with words”读入 “4193”由于下一个字符不是一个数字所以读入停止 ^ 解析得到整数 4193 。 由于 “4193” 在范围 [-2^31, 2^31 - 1] 内最终结果为 4193 。 提示 0 s.length 200 s 由英文字母大写和小写、数字0-9、’ ‘、’‘、’-’ 和 ‘.’ 组成 通过次数544,287提交次数2,544,799 来源力扣LeetCode 链接https://leetcode.cn/problems/string-to-integer-atoi 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 嗯这个题其实非常简单主要就是从读入符号看是后边必须是数字这么一个隐藏条件
class Solution:def myAtoi(self, s: str) - int:s s.strip()x f 1if len(s)0:return 0if s[0] in -:if s[0] -:f * -1s s[1:]while len(s)0 and s[0].isnumeric():x s[0]s s[1:]e int(x) if len(x)0 and x ! - else 0e * fif e 2**31 * -1:e 2**31 * -1if e 2**31:e 2**31 - 1return e牲口太多了。。。才30%不到的名次
竟然还有20ms的答案。。。比不了比不了
9. 回文数 给你一个整数 x 如果 x 是一个回文整数返回 true 否则返回 false 。 回文数是指正序从左向右和倒序从右向左读都是一样的整数。 例如121 是回文而 123 不是。 示例 1 输入x 121 输出true 示例 2 输入x -121 输出false 解释从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。 示例 3 输入x 10 输出false 解释从右向左读, 为 01 。因此它不是一个回文数。 提示 -2^31 x 2^31 - 1 进阶你能不将整数转为字符串来解决这个问题吗 通过次数1,279,736提交次数2,268,913 来源力扣LeetCode 链接https://leetcode.cn/problems/palindrome-number 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 class Solution:def isPalindrome(self, x: int) - bool:return str(x) str(x)[::-1]你说不转字符串我就不转
嗯那就不转吧
class Solution:def isPalindrome(self, x: int) - bool:if x 0:return Trueif x 0 or x % 10 0:return Falsey xz 0while y 0:z z * 10 y % 10y // 10if y z:return Truereturn x z最好成绩52ms题目评价简单也就这样了
10. 正则表达式匹配 给你一个字符串 s 和一个字符规律 p请你来实现一个支持 ‘.’ 和 ‘’ 的正则表达式匹配。 ‘.’ 匹配任意单个字符 ’ 匹配零个或多个前面的那一个元素 所谓匹配是要涵盖 整个 字符串 s的而不是部分字符串。 示例 1 输入s “aa”, p “a” 输出false 解释“a” 无法匹配 “aa” 整个字符串。 示例 2: 输入s “aa”, p “a*” 输出true 解释因为 ‘’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此字符串 “aa” 可被视为 ‘a’ 重复了一次。 示例 3 输入s “ab”, p . 输出true 解释. 表示可匹配零个或多个’任意字符‘.’。 提示 1 s.length 20 1 p.length 30 s 只包含从 a-z 的小写字母。 p 只包含从 a-z 的小写字母以及字符 . 和 *。 保证每次出现字符 * 时前面都匹配到有效的字符 通过次数345,735提交次数1,118,182 来源力扣LeetCode 链接https://leetcode.cn/problems/regular-expression-matching 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 老顾自认自己的正则还不错这个题目就是根据正则来的不过只要求实现长度*和字符集. 先用正则包来完成下看看情况
import re
class Solution:def isMatch(self, s: str, p: str) - bool:return True if re.match(p$,s) else False我去。。。。这成绩倒数了啊大佬这么多都自己实现的正则算法
嗯自己写个尝试看看第一步整理正则为什么要整理正则呢因为很多时候新手的正则写得很冗余有效部分其实并不多
# 两个正则片段完全等价的哦
a*b*.*c* .*
a*aaa a{3,}
a*a*a*a*a*a* a*
a*.*b*.*a*aa*a* .*a{1,}这么一整理需要处理的片段就会少很多了 def formatRegexPattern(self,p):pattern []for i in p:if len(pattern) 0:pattern.append({c:i,l:1,r:1})continueif i *:pattern[-1][r] -1pattern[-1][l] - 1while len(pattern) 1 and pattern[-1][c] .:isPop Falseif pattern[-2][r] -1 and pattern[-2][l] 0:pattern.pop(-2)isPop Trueif not isPop:breakwhile len(pattern) 1 and pattern[-2][c] . and pattern[-2][r] -1:isPop Falseif pattern[-1][l] 0:# and pattern[-2][l] 0:pattern.pop(-1)isPop Trueif not isPop:breakwhile len(pattern) 1 and pattern[-1][c] . and pattern[-2][c] .:pattern[-2][l] pattern[-1][l]if pattern[-2][r] -1 or pattern[-1][r] -1:pattern[-2][r] -1pattern.pop(-1)continueif i pattern[-1][c]:pattern[-1][l] 1pattern[-1][r] 1 if pattern[-1][r] 0 else 0continuepattern.append({c:i,l:1,r:1})return pattern
嗯弄好了正则合并后老顾开始琢磨怎么实现正则了开始写了一大片代码。。。问题是没递归没调用纯用循环判断各种情况最后写不下去了。。。。自己把自己恶心到了
换个思路正则匹配是按片段进行的当上一个片段符合就匹配下一个片段
那么用递归去匹配当前片段当前字符串然后将剩余的片段递归到下一次匹配传递剩余字符串就好了
再然后唯一需要注意的就是长度问题了最后好歹实现出来了帖个代码先
class Solution:def formatRegexPattern(self,p):pattern []for i in p:if len(pattern) 0:pattern.append({c:i,l:1,r:1})continueif i *:pattern[-1][r] -1pattern[-1][l] - 1while len(pattern) 1 and pattern[-1][c] .:isPop Falseif pattern[-2][r] -1 and pattern[-2][l] 0:pattern.pop(-2)isPop Trueif not isPop:breakwhile len(pattern) 1 and pattern[-2][c] . and pattern[-2][r] -1:isPop Falseif pattern[-1][l] 0:# and pattern[-2][l] 0:pattern.pop(-1)isPop Trueif not isPop:breakwhile len(pattern) 1 and pattern[-1][c] . and pattern[-2][c] .:pattern[-2][l] pattern[-1][l]if pattern[-2][r] -1 or pattern[-1][r] -1:pattern[-2][r] -1pattern.pop(-1)continueif i pattern[-1][c]:pattern[-1][l] 1pattern[-1][r] 1 if pattern[-1][r] 0 else 0continuepattern.append({c:i,l:1,r:1})return patterndef IsMatch(self,s,p):if len(s) 0 and len(p) 0:return Trueif len(s) 0 and sum([n[l] for n in p]) 0:return Falseif len(s) 0 and sum([n[l] for n in p]) 0:return Trueif len(s) 0 and len(p) 0:return Falser Falsef p[0]c f[c]l f[l]m f[r]if l 0:if l len(s):return Falsev s[:l]if c ! . and c * l ! v:return Falses s[l:]if m l:for i in range(m - l 1):if c * i s[:i] or c .:r r or self.IsMatch(s[i:],p[1:])if r:breakelif m -1:for i in range(len(s) 1):if c * i s[:i] or c .:r r or self.IsMatch(s[i:],p[1:])if r:breakelse:r r or self.IsMatch(s,p[1:])return rdef isMatch(self, s: str, p: str) - bool:pattern self.formatRegexPattern(p)return self.IsMatch(s,pattern)https://leetcode.cn/submissions/detail/404116311/ 呦呵成绩还不错差一点就到头部了一个正则实现琢磨了两天终于搞定学习告一段落下次继续学习
