佛山按天网站优化服务,网站建设及托管合同,网站推广包括,深圳感染数据统计喵喵喵#xff0c;小夕最近准备复习一下数学和基础算法#xff0c;尽量每篇推送下面会附带点数学和基础算法的小文章。说不定哪天就用#xff08;考#xff09;到了呢(#xffe3;∇#xffe3;)注意哦#xff0c;与头条位的文章推送不同#xff0c;「小公式」和「小算… 喵喵喵小夕最近准备复习一下数学和基础算法尽量每篇推送下面会附带点数学和基础算法的小文章。说不定哪天就用考到了呢(∇)注意哦与头条位的文章推送不同「小公式」和「小算法」里的小标题之间可能并无逻辑关联。回文数链接https://leetcode.com/problems/palindrome-number/description/判断一个整数是否是回文数是leetcode上的一个简单算法题。回文数是指正序从左向右和倒序从右向左读都是一样的整数。例1:输入121
输出true例2:输入-121
输出false
解释从右往左读为121-。例3:输入10
输出false解这个题的话一个很自然而简单的想法就是将整数转换为字符串并检查字符串是否为回文。但是这需要额外的非常量空间来创建问题描述中所不允许的字符串。第二个想法是将数字本身反转然后将反转后的数字与原始数字进行比较如果它们是相同的那么这个数字就是回文。 但是如果反转后的数字大于 int.MAX会发生数值溢出啦不过按照第二个想法为了避免数字反转可能导致的溢出问题为什么不考虑只反转 int 数字的一半毕竟如果该数字是回文其后半部分反转后肯定与原始数字的前半部分相同的呀。所以直接上代码原谅我用python写\(//∇//)\class Solution(object):def isPalindrome(self, x)::type x: int:rtype: boolif x 0 or (x ! 0 and x % 10 0):return Falseinvx 0while invx x:invx invx * 10 x % 10x // 10return invx x or invx // 10 x当然得益于python自带大数运算的特性即不存在撞枪int.MAX的情况在python里直接用第二种方法解也是可以acc的。class Solution(object):def isPalindrome(self, x)::type x: int:rtype: boolif x 0:return Falserawx xinvx 0while x 0:invx invx * 10 x % 10x // 10return invx rawx数值合法性检验链接https://leetcode.com/problems/valid-number/description/这个算法题是一个对初学者写到吐对有基础的人写着玩儿的一道题。题目很简单就是判断用户的输入字符串形式是不是一个合法的数值。这里合法的数值其实就是我们平常所说的数字啦比如123,-1.0,423,.4234,2.345e21都是合法数值。当然这里还允许用户在合法数值的前后插入若干空格。这个问题如果直接用if else while生写的话会写到吐而且极难debug。但是这个问题一个机智的做法就是直接上确定有限状态自动机deterministic finite automation, DFA。DFA是由一个非空有限的状态集合Q一个输入字母表非空有限的字符集合一组转移函数如)一个开始状态一个接受终止状态的集合所组成的5元组。这个在编译原理、NLP基础里都有讲忘了的同学自行补上哦。所以很自然的这个题目画出的状态机如下图有了状态机代码就变得简洁多了。这里贴出python实现来自leetcode讨论区小夕在此题悲剧class Solution(object):def isNumber(self, s)::type s: str:rtype: bool#define a DFAstate [{}, {blank: 1, sign: 2, digit:3, .:4}, {digit:3, .:4},{digit:3, .:5, e:6, blank:9},{digit:5},{digit:5, e:6, blank:9},{sign:7, digit:8},{digit:8},{digit:8, blank:9},{blank:9}]currentState 1for c in s:if c 0 and c 9:c digitif c :c blankif c in [, -]:c signif c not in state[currentState].keys():return FalsecurrentState state[currentState][c]if currentState not in [3,5,8,9]:return Falsereturn True嗯就酱╮(╯▽╰)╭
