如何解hard算法題？-創(chuàng)新互聯(lián)

如何解困難題？
  • 前言
  • 一、案例
  • 二、困難題拆解
    • 1、自己的思路
    • 2、官方的思路
    • 3、源碼
      • Java
      • golang
  • 總結(jié)
  • 參考文獻

成都創(chuàng)新互聯(lián)成立與2013年，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務公司，擁有項目網(wǎng)站設(shè)計、網(wǎng)站制作網(wǎng)站策劃，項目實施與項目整合能力。我們以讓每一個夢想脫穎而出為使命，1280元西夏做網(wǎng)站,已為上家服務,為西夏各地企業(yè)和個人服務,聯(lián)系電話:18982081108前言

上一篇文章寫bitCount源碼解析，對困難題有一些抽象的理解。
困難題就是一個個簡單的知識點組成，加上其內(nèi)在的邏輯聯(lián)系。所以一個困難題，應該是先觀其規(guī)律，再進行邏輯轉(zhuǎn)換問題，再拆解小問題，用積累的知識點解決。
當然，如果沒有積累到/思考角度不對，就看題解，多調(diào)研，別浪費時間！

一、案例

在這里插入圖片描述

二、困難題拆解 1、自己的思路
// target：從兩個數(shù)組選出兩組數(shù)據(jù)，合并倒序，就得到一個大組合值。
    // 轉(zhuǎn)換成有規(guī)律的問題。
    // 問題
    // 兩數(shù)組肯定盡量單調(diào)（大的那個單調(diào)），但是取出的單調(diào)棧合并長度并不一定為k
    // 如果兩者合并長度大于等于k，倒排之后（依次選擇），取前k個即可。
    // 如果不夠k怎么辦？

很明顯，我的角度錯了，但也有可取之處，比如單調(diào)棧。
而我角度錯了的原因，就是沒有將問題從模擬問題轉(zhuǎn)化為有規(guī)律的問題，這樣才能用代碼實現(xiàn)！

2、官方的思路

將k分解為k = x + y，不斷模擬兩個數(shù)值數(shù)組的大拼接，記錄大的那一個。
現(xiàn)在已經(jīng)將問題規(guī)律化了，然后拆解小問題，就涉及到小知識點了
1.帶remain的單調(diào)棧來取數(shù)值數(shù)數(shù)組指定長度大子序列。
2.O(N)合并兩個數(shù)值數(shù)組，使其該數(shù)值數(shù)組大值。
3.兩數(shù)值數(shù)組比較大小的處理方式。

3、源碼 Java
class Solution {// target：從兩個數(shù)組選出兩組數(shù)據(jù)，合并倒序，就得到一個大組合值。
    // 轉(zhuǎn)換成有規(guī)律的問題。
    // 問題
    // 兩數(shù)組肯定盡量單調(diào)（大的那個單調(diào)），但是取出的單調(diào)棧合并長度并不一定為k
    // 如果兩者合并長度大于等于k，倒排之后（依次選擇），取前k個即可。
    // 如果不夠k怎么辦？

    // 調(diào)研思路
    // 將k分成 k = x + y，不斷尋找x和y，然后拼接，比較，記錄大值。 
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {int m = nums1.length,n = nums2.length;

        int start = Math.max(0,k - n);
        int end = Math.min(k,m);
        int[] maxRs = new int[k];
        // 強行分解k = x + y，進行遍歷記錄大值。
        // hard-mark：問題轉(zhuǎn)換(規(guī)律非模擬問題)+問題拆解(多個小知識點)+多個小問題的邏輯聯(lián)系。
        for(int i = start;i<= end;i++){int[] seq1 = getSeq(nums1,i);
            int[] seq2 = getSeq(nums2,k - i);

            int[] curRs = merge(seq1,seq2);

            if(compare(maxRs,0,curRs,0)< 0) System.arraycopy(curRs,0,maxRs,0,k);
        }
        return maxRs;
    }
    // 知識點1：O(N)合并兩個數(shù)值數(shù)組，使其該數(shù)值數(shù)組大值。
    public int[] merge(int[] nums1,int[] nums2){int m = nums1.length,n = nums2.length;
        if(m == 0) return nums2;
        if(n == 0) return nums1;

        int i = 0,j = 0;
        int[] rs = new int[m + n];

        for(int k = 0;k< m + n;k++){if(compare(nums1,i,nums2,j) >0) rs[k] = nums1[i++];
            else rs[k] = nums2[j++];
        }
        return rs;
    }
    // 知識點2：兩數(shù)值數(shù)組比較大小，盡量返回int，而不是boolean
    public int compare(int[] nums1,int i,int[] nums2,int j){int m = nums1.length,n = nums2.length;

        while(i< m && j< n){int gap = nums1[i] - nums2[j];
            if(gap != 0) return gap;

            ++i;
            ++j;
        }
        return (m - i) - (n - j);
    }
    // 知識點3：單調(diào)減棧 配合 remain，可以做到求指定長度的大子序列。
    public int[] getSeq(int[] nums,int k){int[] stack = new int[k];
        int top = 0,remain = nums.length - k;

        for(int cur : nums){while(top >0 && stack[top - 1]< cur && remain >0){top--;
                remain--;// 不需要的上限
            }
            if(top< k){stack[top++] = cur;
            }else remain--;
        }
        return stack;
    }
}
golang
func maxNumber(nums1 []int, nums2 []int, k int) []int {m,n := len(nums1),len(nums2)
    start,end := max(0,k - n),min(k,m)
    maxRs := make([]int,k)
    // k = x + y,取子序列，再合并，最后比較大小，并記錄。
    for i := start;i<= end;i++ {seq1 := getSeq(nums1,i)
        seq2 := getSeq(nums2,k - i)

        curRs := merge(seq1,seq2)

        if compare(curRs,0,maxRs,0) >0 {copy(maxRs,curRs)
        }
    }
    return maxRs
}
// 知識點1：O(N)合并兩個數(shù)值數(shù)組，使其該數(shù)值數(shù)組大值。
func merge(nums1 []int,nums2 []int) []int {m,n := len(nums1),len(nums2)
    if m == 0 {return nums2
    }
    if n == 0 {return nums1
    }
    i,j := 0,0
    rs := make([]int,m + n)
    for k := 0;k< m + n;k++ {if compare(nums1,i,nums2,j) >0 {rs[k] = nums1[i]
            i++
        }else {rs[k] = nums2[j]
            j++
        }
    }
    return rs
}
// 知識點2：兩數(shù)值數(shù)組比較大小，盡量返回int，而不是boolean
func compare(nums1 []int,i int,nums2 []int,j int) int {m,n := len(nums1),len(nums2)
    for ; i< m && j< n; {gap := nums1[i] - nums2[j]
        if gap != 0 {return gap
        }
        i++
        j++
    }
    return (m - i) - (n - j)
}
// 知識點3：單調(diào)減棧 配合 remain，可以做到求指定長度的大子序列。
func getSeq(nums []int,k int) []int {stack := make([]int,k)
    top := 0
    remain := len(nums) - k

    for _,cur := range nums {for ; top >0 && stack[top - 1]< cur && remain >0; {top--;
            remain--;
        }
        if top< k {stack[top] = cur;
            top++
        }else {remain--
        }
    }
    return stack
}
// 取大值
func max(i int,j int) int {if i >j {return i
    }
    return j
}
// 取小值
func min(i int,j int) int {if i< j {return i
    }
    return j
}
總結(jié)

1）一個困難題，應該是先觀其規(guī)律，再進行邏輯轉(zhuǎn)換問題，再拆解小問題，用積累的知識點解決。
2）如果沒有積累到/思考角度不對，就看題解，多調(diào)研，別浪費時間！
3）多解決困難題，對提升解決問題能力有幫助，但是這是長期提升，而短期需要找工作則邊界收益不大，性價比低。

參考文獻

[1] LeetCode 321.拼接大數(shù)
[2] LeetCode 321.拼接大數(shù)-官方題解
[3] go 數(shù)組copy用法
[4] go foreach用法

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

分享文章：如何解hard算法題？-創(chuàng)新互聯(lián)
當前路徑：http://bm7419.com/article0/hdhoo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)頁設(shè)計公司、定制開發(fā)、服務器托管、自適應網(wǎng)站、企業(yè)網(wǎng)站制作、用戶體驗

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

h5響應式網(wǎng)站建設(shè)