LeetCode剑指Offer刷题总结（二）

LeetCode过程中值得反思的细节（二）

本周10道题，此栏目将每周定期更新。题号为LeetCode剑指Offer题库中的题号。

剪绳子14

这道题需要思考剪绳子的过程

public int cuttingRope(int n) {  if(n<=3) return n-1;  if(n%3==0)return (int)Math.pow(3,(n/3));  if(n%3==2)return (int)Math.pow(3,n/3)*2;  if(n%3==1)return (int)Math.pow(3,n/3-1)*4;  return 0; }

首先算术平均数大于等于几何平均数，当剪的每段长度相等时达到两个平均数互等条件。

当每段都取3时，可达到极大值，从以下公式求导可知：

动态规划算法：

public int cuttingRope(int n) {  int[] dp = new int[n + 1];  dp[2] = 1;  for(int i = 3; i < n + 1; i++){   for(int j = 2; j < i; j++){    dp[i] = Math.max(dp[i],Math.max(j * (i - j), j * dp[i - j]));   }  }  return dp[n]; }

这个算法同样成立，但是如果不知道数学推导的话还是比较难理解这个算法，这里面包含了很多可能性都进行了比较。

剪绳子Ⅱ 14

public int cuttingRope(int n) {  if(n<=3)return n-1;  int b = n/3;  long a,rem;  if(n%3==0)return quickPow(3,n/3);  if(n%3==1){   rem = ((long)quickPow(3,n/3-1))*4%1000000007;   return (int)rem;  }  if(n%3==2)return quickPow(3,n/3)*2%1000000007;  return 0; } public int quickPow(long a,int b){  long temp = 1;  while(b>0){   if(b%2==1) temp=(a*temp)%1000000007;   a=a*a%1000000007;   b=b/2;  }  return (int)temp; }

本题中，n的范围增大，故取余是一个必要操作

取余的操作有两种：例如a^b

1. b个a相乘，每次均进行取余（%1000000007），复杂度为O(N)
2. a^b = a^(b的二进制转换)，复杂度为O(logN)，此方法即为快速取余法（利用二进制便于理解）

上述代码的quickPow()即为取b的二进制进行相乘操作

二进制中的1个数15

本题中是以二进制形式输入一个int，进行判断二进制数中有多少个1

直接利用int十进制解决的话涉及到补码问题，需要多个if判断，并不方便，所以使用移位和与操作较好

两种思路：

1. 每次和1与操作
2. 每次进行 n&(n-1)，这个操作是将n最右边的1变为0，有多少次循环即有多少个1（while条件n==0）

数值的整数次方16

该题仍然是利用快速幂法的一道题，不再详细赘述，可看剪绳子14

这题的一个细节在于

int的取值范围为：

• 最小值是 -2,147,483,648（-2^31）；
• 最大值是 2,147,483,647（2^31 - 1）；

当int取最小值-2^31时，取反会越界而赋值出错，所以需要转换类型long

做题时，首要目标在于审题，观察数据的取值范围，进而进行if的合理安排

打印1到最大的n位数17（包含大数版）

首先第一个易错点是 Math.pow()返回的是double类型，注意强制转换。

大数需要将数字转为String形式，可调用递归返回包含所有数字的字符串。以n=2举例，共用100种全排列。

class Solution { int[] res; int n,count=0,nine=0; int start; String ans; char[] num,loop={'0','1','2','3','4','5','6','7','8','9'};//num并没有初始化 public int[] printNumbers(int n) {  this.n = n;  start=n-1;  num = new char[n];  res = new int[((int)Math.pow(10,n))-1];  dfs(0);  return res; } public void dfs(int x){  if(x==n){   ans = String.valueOf(num).substring(start);   if(!ans.equals("0")) res[count++]=Integer.parseInt(ans);   if(n-start == nine) start--;   return ;  }  for(char i :loop){   if(i=='9') nine++;   num[x]=i;   dfs(x+1);  }  nine--; //注意，这里相当于，例n=3,当'009'时，nine=1，当'010'时，nine=0，当'099'时，nine=2 }}

这里注意substring中全小写，Integer.parseInt为将String转为int

正则表达式匹配19

注意，boolean的默认值为false

先上答案：

class Solution { public boolean isMatch(String s, String p) {  int m = s.length();  int n = p.length();  boolean[][] f = new boolean[m+1][n+1];  f[0][0]=true;  for(int i = 0; i < m+1 ; i++)   for(int j = 1 ; j < n+1 ; j++){    if(p.charAt(j-1)!='*'){     if(i>0 && (s.charAt(i-1)==p.charAt(j-1) || p.charAt(j-1)=='.'))      f[i][j]=f[i-1][j-1];    }    else{     if(j>=2){      f[i][j]=f[i][j-2];     }     if(i>0 && (s.charAt(i-1)==p.charAt(j-2) || p.charAt(j-2)=='.'))      f[i][j] |= f[i-1][j];    }   }  return f[m][n]; }}

这里利用的是动态规划，f[m][n]表示s的前m个字符和p的前n个字符是否匹配

f[m][0]均为false除f[0][0]外

因为空串匹配空表达式，但是非空串一定不匹配空表达式

而空串不一定匹配非空表达式

这里需要注意的是.charAt()中的索引值和数组中的索引值实际上相差1

当遇到*时，两种情况：1.当前s串的字符和a*不匹配，即直接返回f[i][j-2]。2.当前s串的字符和a*匹配，直接返回f[i-1][j]，因为如果匹配的话，i-1必然也匹配。

表示数值的字符串20

有一个比较暴力的解法，利用异常自动判断

public boolean isNumber(String s) {  s=s.trim();  int len = s.length();  try{   double res = Double.parseDouble(s);  }catch (Exception e){   return false;  }  char a = s.substring(len-1).charAt(0);  if(a>='0'&&a<='9'||(a=='.'))   return true;  return false; }

但是正常思路是利用自动机，建立状态：

共判断了8到10种状态，不同解法状态数可能不同，个人不喜欢这种解法，不再解释了。

不过，自动机解法有利于理解计算机的词法器语法器等。

数组顺序奇数前偶数后21

这道题首先可以暴力求解，遍历两次，建立新数组，时间复杂度：O(N)

双指针解法：（首尾双指针和快慢双指针）

public int[] exchange(int[] nums) {  if(nums.length==0)   return new int[]{};  int left=0,right=nums.length-1;  int temp;  while(left!=right){   if(nums[left]%2==1){    left++;    continue;   }   if(nums[right]%2==0){    right--;    continue;   }   temp=nums[left];   nums[left]=nums[right];   nums[right]=temp;  }  return nums; }

demo为首尾双指针算法，快慢双指针为：快指针去找后面的奇数，而慢指针指向当前最左的偶数。

class Solution { public int[] exchange(int[] nums) {  int i=0,j=0; //i为慢指针，j为快指针  while(j<nums.length){   if((nums[j]&1)!=0){    int tmp=nums[i];    nums[i]=nums[j];    nums[j]=tmp;    i++;   }   j++;  }  return nums; }}

链表中倒数第k个节点22

利用快慢双指针即可解，可参考21，（easy题目不再详细解释）

class Solution { public ListNode getKthFromEnd(ListNode head, int k) {  ListNode res = head;  for(int i = 0 ; i < k ; i++){   res = res.next;  }  while(res!=null){   head = head.next;   res = res.next;  }  return head; }}

反转链表24

class Solution { public ListNode reverseList(ListNode head) {  ListNode first=null,sec=null,thi=null;  first = head;  if(first!=null && first.next!=null){   sec = first.next;   thi = sec.next;  }  if(first!=null)   first.next = null;  while(sec!=null){   sec.next = first;   first = sec;   sec = thi;   if(thi!=null)    thi = thi.next;  }  return first; }}

这个方法是建立了三个临时节点，进行链表反转，easy题目不再详细解释。

官方解法，减少了判断条件：

class Solution { public ListNode reverseList(ListNode head) {  ListNode prev = null;  ListNode curr = head;  while (curr != null) {   ListNode next = curr.next;   curr.next = prev;   prev = curr;   curr = next;  }  return prev; }}

此外，还可以利用递归，不再详细赘述。

原文转载：http://www.shaoqun.com/a/701746.html

跨境电商：https://www.ikjzd.com/

worldfirst：https://www.ikjzd.com/w/289

慧聪商务网：https://www.ikjzd.com/w/1836

LeetCode过程中值得反思的细节（二）本周10道题，此栏目将每周定期更新。题号为LeetCode剑指Offer题库中的题号。剪绳子14这道题需要思考剪绳子的过程publicintcuttingRope(intn){if(n<=3)returnn-1;if(n%3==0)return(int)Math.pow(3,(n/3));if(n%3==2)return(int)Math.pow(3
unsplash：https://www.ikjzd.com/w/756.html
gtc：https://www.ikjzd.com/w/974
淘粉8：https://www.ikjzd.com/w/1725.html
口述：爱爱后老婆总把狗抱上床 受不了口述爱爱老婆：http://lady.shaoqun.com/m/a/25294.html
权威解读！你知道亚马逊跨境电商园吗？：https://www.ikjzd.com/home/20095
（精品分析）亚马逊美国站夜灯类目市场调查数据报告：https://www.ikjzd.com/home/102790