剑指OFFER

又tm一天cfunclongestPalindrome(sstring)string{varn=len(s)vardp=make([][]bool,n)varmax=1varstartintfori:=0;i<n;i++{dp[i]=make([]bool,n)}forj:=0;j<n;j++{fori:=0;i<=j;i++{ifj-i<2{dp[i][j]=(s[i]==s[j])}else{dp[i][j]=(dp[i+1][j-1]&&s[i]==s[j])}ifdp[i][j]&&j-i+1>max{max=j-i+1start=i}}}returns[start:start+max]}注意到两个循环，必须要在保证判断dp[i][j]时，dp[i+1][j+1]里这个区间所有的元素都已经正确赋值，一开始写的循环“aaaaa”，一直报错，就是因为判断s[4]的时候，dp[0][3]虽然true了，但是dp[1][4]还是false，还有个问题就是之前的循环一个元素和两个字符比如“aa”这样的回文子串判断不出来，原因也是遍历不到位的原因，dp[i+1][j-1]还是原来那个元素，并没有正确赋值。

mb，错了一天，D了一天bug，真爽。脑子秀逗的感觉。funclengthOfLongestSubstring(sstring)int{varstart,end=0,0varmax=0varhashMap=make(map[byte]int,100)//hashMap[s[0]]=0//t,ok:=hashMap[s[end+1]]for;end<len(s);{t,ok:=hashMap[s[end]]ifok&&t>=start{//这里之前没有判断t，导致在map中，start之前位置可能有重复字符，导致失败。ifmax<end-start{max=end-start}start=hashMap[s[end]]+1}else{hashMap[s[end]]=endend++}}ifmax<end-start{//如果整个字符串一个重复字符没有，那么end=lenl（s）直接退出，不会执行循环里的长度判断max=end-start}returnmax}又写了一个切片的funclengthOfLongestSubstring(sstring)int{varmax=0varlocations=[128]int{0}fori:=0;i<len(s);i++{//切片下标为字母，所以一开始没设置为-1时，下面读的locations可能为0，等于了start，但实际第一个元素还没有存入locations[s[i]]=-1}n:=len(s)varstart,end=0,0for;end<len(s);end++{iflocations[s[end]]>=start{start=locations[s[end]]+1}ifend-start+1>max{max=end-start+1ifmax>=n-start{break}}locations[s[end]]=end}returnmax}

1.i标记偶数，j标记奇数，碰到的第一个奇数和第一个偶数互换位置，直到没有奇数funcexchange(nums[]int)[]int{fori,j:=0,0;i<len(nums);i++{ifnums[i]%2==1{nums[i],nums[j]=nums[j],nums[i]j++}}returnnums}

短路求值：作为“&&”和“||”操作数表达式，这些表达式在进行求值时，只要最终的结果已经确定真或假，求值过程便告终，这就是短路求值。因此可以利用左边的表达式来作为递归结束的判断条件。因此递归的表达式就在右边了。使用&&,表示两边都为真，才为真，左边为假，右边就没用了。因此在不断递归时，直到左边为假时，才不执行右边。因此在第一次进行右边的判断时，就进入递归的调用。funcSum_Solution(nint)int{varffunc(ret*int,nint)boolf=func(ret*int,nint)bool{*ret+=nreturnn>0&&f(ret,n-1)}varsumintf(&sum,n)returnsum}

1.闭包funcFibonacci(nint)int{//writecodeherea,b:=0,1returnfunc()int{fori:=0;i<n;i++{a,b=b,a+b}returna}()}2.递归funcFibonacci2(nint)int{//writecodehereifn==0{return0}elseifn==1||n==2{return1}else{returnFibonacci2(n-1)+Fibonacci2(n-2)}}

占用空间太大funcreConstructBinaryTree(pre[]int,vin[]int)*TreeNode{//writecodehereiflen(pre)==0{returnnil}varleft_pre,right_pre,left_vin,right_vin[]intvarroot=&TreeNode{pre[0],nil,nil}varroot_son=0fori:=0;i<len(vin);i++{ifvin[i]==pre[0]{root_son=ibreak}}fori:=0;i<root_son;i++{left_vin=append(left_vin,vin[i])left_pre=append(left_pre,pre[i+1])}fori:=root_son+1;i<len(vin);i++{right_vin=append(right_vin,vin[i])right_pre=append(right_pre,pre[i])}root.Left=reConstructBinaryTree(left_pre,left_vin)root.Right=reConstructBinaryTree(right_pre,right_vin)returnroot}第二种写法，差不多，没第一个好想funcrebuild(pre[]int,pre_leftint,pre_rightint,vin[]int,vin_leftint,vin_rightint)*TreeNode{if(pre_left>pre_right){returnnil}varroot=&TreeNode{pre[pre_left],nil,nil}fori:=vin_left;i<=vin_right;i++{ifvin[i]==root.Val{root.Left=rebuild(pre,pre_left+1,pre_left+i-vin_left,vin,vin_left,i-1)root.Right=rebuild(pre,pre_left+i-vin_left+1,pre_right,vin,i+1,vin_right)}}returnroot}funcreConstructBinaryTree(pre[]int,vin[]int)*TreeNode{//writecodeherereturnrebuild(pre,0,len(pre)-1,vin,0,len(vin)-1)}