你知道一些有趣的算法吗？_0

本文转载自微信公众号《微信大学前端技术》，作者孙凌志。转载本文请联系微一大学前端技术公众号。根据身份证号码计算性别和年龄1.身份证号码国家标准1.适用范围《公民身份号码》(GB11643-1999)本标准规定了公民身份证号码的编码对象、号码结构和表示形式，使每个编码对象得到一个唯一的、不可变的合法编号。2、号码的结构公民身份证号码是一个特征组合码，由一个17位的主体代码和一个校验码组成。从左到右排列顺序为：六位地址码、八位出生日期码、三位顺序码、一位校验码。2.1.地址代码表示编码对象常住地所在县（市、旗、区）的行政区划代码。2.2.出生日期代码表示编码对象出生的年月日。2.3.序号代表同一地址代码所标识的地区范围内，序号分配给同一年月日出生的人，序号的奇数分配给男性，偶数分配给男性分配给女性。2.4.校验码根据前面的17位数字代码和ISO7064:1983.MOD11-2中的校验码计算方法计算确定(1)17位数字体代码加权求和公式：S=Sum(Ai*Wi)编号11010519491231002加权系数7910584216379105842Ai*Wi7905020S=7+9+0+5+0+20+2+9+24+27+7+18+30+5+0+0+4=167(2)计算模数：Y=mod(S,11)Y=167%11=>2(3)通过取模得到对应的校验码对01234取模5678910校验码10X9876543当2的模为2时，校验码为X二、代码实现1、检查ID号是否正确constWEIGHT=[7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2]constMO=[1,0,'X',9,8,7,6,5,4,3,2]functionisRightId(id){constarr=id.split('')constcheckNumber=arr.pop()//去掉校验码并将pop的返回值赋值给checkNumberletsum=0arr.forEach((ele,index)=>{sum+=ele*WEIGHT[index]})constm=sum%11constresult=MO[m]returnresult+''===checkNumber}console.log(isRightId('11010519491231002X'))//trueconsole.log(isRightId('110105194912310029'))//false2、从身份证号计算年龄函数getAge(id){//1、判断身份首先证书号的正确性//2，判断是否存活constyear=id.substr(6,4)constmonth=id.substr(10,2)constday=id.substr(12,2)consttimeBrth=newDate(`${year}/${month}/${day}`).getTime()consttimeNow=newDate().getTime()constlongTime=timeNow-timeBrthconstdays=longTime/(1*24*60*60*1000)letresult=''if(days<31){result=parseInt(days)+'day'}elseif(days<365){result=`${parseInt(days/30)}月${parseInt(days%30)}day`}else{result=`${parseInt(days/365)}年${parseInt(days%365/30)}月${parseInt(days%365%30)}days`}returnresult}console.log(getAge('11010519491231002X'))//71岁8个月16天console.log(getAge('11010520210820002X'))//6天console.log(getAge('11010520210720002X'))//1个月7天3.通过身份证号判断性别函数getSex(id){//1，首先判断身份证号是否正确constsex=id.substr(16,1)returnsex%2?'male':'female'}console.log(getSex('11010519491231002X'))//女console.log(getSex('11010520210820001X'))//男3,其他1.变性手术后，身份证号有没有变？变性人身份证性别变更后，以户籍所在地派出所公示为准，变更身份证号码2.计算年龄前，首先确认自己是否健在。四、参考资料《公民身份号码》(GB11643-1999)动态规划1、定义动态规划（DynamicProgramming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。可以简单理解为对传统递归的优化。在DP的实践中重要的是递归关系和边界条件。2.简单：爬楼梯问题假设你正在爬楼梯。需要走n步才能到达建筑物的顶部。您一次可以爬1或2个台阶。您有多少种不同的方法可以到达建筑物的顶部？请注意，给定的n是一个正整数。输入：2输出：2解释：有两种方式可以爬到楼顶。1.1storder+1storder2.2ndorder示例2：输入：3输出：3解释：有三种方式可以爬到楼顶。1.1st+1storder+1storder2.1storder+2ndorder3.2order+1storder代码：//将数据缓存在数组中varclimbStairs=function(n){letdp=[]dp[0]=1;dp[1]=1;for(leti=2;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}returndp[n];};//使用递归varclimbStairs=函数(n){if(n===1)return1if(n===2)return2returnclimbStairs(n-1)+climbStairs(n-2)};idea:f(x)=f(_x_?1)+f(x_?2)爬到第x步的计划数是爬到第x-1步的计划数与第x步的计划数之和计划爬到x-第二步。LeetCode跑分：3.中等：最长回文子串题目给你一个字符串s，求s中最长的回文子串。示例1：输入：s="babad"输出："bab"解释："aba"也是符合问题意思的答案。例2：输入：s="cbbd"输出："bb"思路：当s[i+1:j-1]为回文，且s的i和j字母相同时，s[i:j]将是一个回文字符串。即：P(i,j)=P(i+1,j?1)和(Si==Sj)。边界条件：子串的长度为1或2。对于长度为1的子串，显然是回文；对于长度为2的子串，只要它的两个字母相同，就是回文。P(i,i)=trueP(i,i+1)=(Si==Si+1)代码：functionlongestPalindrome(s){//先判断字符串的长度，如果为1，直接返回letlen=s。lengthif(len<2)returns//初始化变量letmaxLen=1letbegin=0//dp[i][j]表示s[i..j]是否为回文letdp=[]//初始化：所有长度都是1的substrings都是回文串for(leti=0;i=len){break;}//判断是否为回文if(charArray[i]!==charArray[j]){dp[i][j]=false}else{//对于一个子串，如果是回文，且长度大于2，去掉首尾两个字母，还是回文。letflag=j-i<3dp[i][j]=flag?true:dp[i+1][j-1]}//当dp[i][L]==true成立时，表示子串s[i..L]为回文，记录回文长度和起始位置if(dp[i][j]&&j-i+1>maxLen){maxLen=j-i+1;begin=i;}}}returns.substring(begin,begin+maxLen);}console.log(longestPalindrome('babad'),'babad')//babbabadconsole.log(longestPalindrome('cbbd'),'cbbd')//bbcbbdLeetCode运行结果：4,难点：接雨水题目：给定n个非负整数代表每列宽度为1的高度图，计算下雨后这样排列的列能接收多少雨水。示例1：输入：height=[0,1,0,2,1,0,1,3,2,1,2,1]输出：6解释：上面由数组[0,1,0,2,1,0,1,3,2,1,2,1]代表高度图，在这种情况下，它可以接收6个单位的雨水（蓝色部分代表雨水）。示例2：输入：height=[4,2,0,3,2,5]输出：9代码：functiontrap(height){//如果不满足条件，直接返回letlen=height.length;if(len<=2)return0;letmaxLeft=[];//第i列左边最高列的高度letmaxRight=[];//第i列右边最高列的高度maxLeft[0]=height[0];for(leti=1;i=0;j--){maxRight[j]=Math.max(height[j],maxRight[j+1])//动态传递}letsum=0;for(leti=0;ir_hight)r_hight=height[r];}//找到第i列左边最高列的边的高度for(letl=i;l>=0;l--){if(height[l]>l_hight)l_hight=height[l];}ans+=Math.min(l_hight,r_hight)-height[i];}returnans;}LeetCode运行结果：5.参考来源：LeetCodehttps://leetcode-cn.com/problems/climbing-stairs/https://leetcode-cn.com/problems/longest-palindromic-substring/https://leetcode-cn.com/problems/trapping-rain-water/greedyalgorithm1.定义解决一个问题时，总是做出当前最好的选择。2.分饼干假设你是一位好父母，想给你的孩子一些饼干。但是，每个孩子最多只能得到一个饼干。对于每个孩子i，都有一个食欲值g[i]，它是满足孩子食欲的最小尺寸的饼干；对于每个饼干j，有一个大小s[j]。如果s[j]>=g[i]，我们可以将这个cookiej分配给孩子i，这个孩子就会满意。你的目标是让尽可能多的孩子满意，输出这个最大值。示例1：输入：g=[1,2,3]，s=[1,1]输出：1示例2：输入：g=[1,2]，s=[1,2,3]输出：2functionfindContentChildren1（孩子，饼干）{children=children.sort((a,b)=>a-b)cookies=cookies.sort((a,b)=>a-b)letchildrenLength=children.lengthletcookiesLength=cookies.lengthletcount=0for(leti=0,j=0;icookies[j]){j++}if(jcookies[j]，即当前cookie不能满足child时，j++选择下一个cookie进行比较。如果children[i]<=cookies[j]，即当前cookie能满足child，且j在范围内，则加1计数。转到下一个循环（即尝试满足下一个孩子）。3.买股票给定一个整数数组prices，第i个元素代表第i天的股票价格；整数费用代表交易股票的手续费。您可以无限次完成交易，但您需要为每笔交易支付交易费用。如果您已经购买了一只股票，则在您卖出之前不能继续购买另一只股票。返回利润的最大值。注：这里的一笔交易是指买入、持有和卖出股票的全过程，您只需为每笔交易支付手续费。示例1：输入：prices=[1,3,2,8,4,9],fee=2,输出：8解释：可以达到的最大利润：buyhereprices[0]=1hereSellprices[3]=8Buyhereprices[4]=4Sellhereprices[5]=9总利润：((8-1)-2)+((9-4)-2)=8示例2：输入:prices=[1,3,7,5,10,3],fee=3Output:6functionmaxProfit(list,fee){constlength=list.lengthletbuy=list[0]+fee//假设：买入机会是firstdayletprofit=0for(leti=1;ibuy){//有盈利则卖出profit+=list[i]-buy//计算盈利buy=list[i]//调整买入时机}}returnprofit}console.log(maxProfit([1,3,2,8,4,9],2))//8console.log(maxProfit([1,3,7,5,10,3],3))//6代码解释：定义函数maxProfit，接受2个参数，list为股价走势，fee定义利润为手续费，最后返回利润假设：买入时间为第一天（即：list[0]）如果股价下跌，将买入时间调整到第二天。如果有盈利，则卖出，并计算盈利，再次调整买入时间（即循环第3、4、5步）核心思想：假设：买入进场时机为第一天。如果股价下跌，则将买入时机调整到第二天。如果有利润，则卖出并重新计算利润-假设：买入时机（循环步骤1-3）4.N对情侣牵着手一对情侣坐在排成一排的2N个座位上，想握住对方的手手。计算使每对夫妇可以并排坐下的最少座位交换次数。交换选择任意两个人并要求他们站起来交换座位。人和座位用0到2N-1的整数表示，恋人按顺序编号，第一对是(0,1)，第二对是(2,3)，以此类推，最后一对是(2N-2,2N-1).这些情侣的初始座位row[i]由最初坐在第i个座位上的人决定。示例1：输入：row=[0,2,1,3]输出：1解释：我们只需要交换row[1]和row[2]的位置。示例2：输入：row=[3,2,0,1]输出：0解释：无需交换座位，所有情侣已经可以牵手了。/***@param{number[]}row*@return{number}*/varminSwapsCouples=function(row){lethashMap={};//{person:location}for(leti=0;i