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
- b個a相乘，每次均進行取余（%1000000007），復雜度為O(N)
- a^b = a^(b的二進制轉換)，復雜度為O(logN)，此方法即為快速取余法（利用二進制便于理解）
上述代碼的quickPow()即為取b的二進制進行相乘操作
二進制中的1個數15
本題中是以二進制形式輸入一個int，進行判斷二進制數中有多少個1
直接利用int十進制解決的話涉及到補碼問題，需要多個if判斷，并不方便，所以使用移位和與操作較好
兩種思路：
- 每次和1與操作
- 每次進行
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;
}
}
此外，還可以利用遞回，不再詳細贅述，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/279198.html
標籤：其他
上一篇：為什么 DNS 協議使用 UDP？只使用了 UDP 嗎？
下一篇：java基本使用及方法的多載遞回