比較多的思維題，涉及位運算、快速冪、二進制、約瑟夫問題、佇列、貪心、dp等等，

難度	題目	知識點
☆	12、數值的整數次方	細節，快速冪
☆☆	47、求1+2+3+···+n	思維發散
☆☆	48、不用加減乘除做加法	二進制運算
☆☆☆	11、二進制中1的個數	補碼，位運算
☆☆☆☆	29、最小的K個數	查找第K大，或各種排序演算法
☆	31、從1到n整數中1出現的次數	思維
☆	33、丑數	思維
	41、和為S的連續正數序列	滑動視窗，雙指標
	42、和為S的兩個數字	滑動視窗，雙指標
	45、撲克牌順子	多種情況判斷
☆☆☆	46、圓圈中最后剩下的數	約瑟夫環，數學
☆☆☆	63、資料流中的中位數	妙用堆，PriorityQueue
☆☆☆	64、滑動視窗的最大值	模擬，滑動視窗，雙端佇列
☆☆☆	67、剪繩子	貪心，動態規劃

12、數值的整數次方+

細節，快速冪

給定一個double型別的浮點數 base 和 int 型別的整數exponent，求base的exponent次方，保證base和exponent不同時為0

題意分析

指數可能為負數，

Java Code


class Solution {
public:
    double Power(double base, int exponent) {
        double ans=1;
        bool neg= false;
        if(exponent<0){
            neg=true;
            exponent=-exponent;
        }
        for( ; exponent; base*=base,exponent/=2){
            if(exponent&1){
                ans*=base;
            }
        }
        return neg?1/ans:ans;
    }
};

47、求1+2+3+···+n ++

思維發散

求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等關鍵字及條件判斷陳述句（A?B:C），

題意分析

需要思維發散，善用遞回和短路運算，見代碼，

Java Code


class Solution {
public:
    int Sum_Solution(int n) {
        int ans = n;
        ans && (ans += Sum_Solution(n - 1));
        return ans;
    }
};

48、不用加減乘除做加法++

二進制運算

寫一個函式，求兩個整數之和，要求在函式體內不得使用+、-、*、/四則運算子號，

題意分析

第一步：相加各位的值，不算進位，得到010，二進制每位相加就相當于各位做異或操作，101^111，
第二步：計算進位值，得到1010，相當于各位做與操作得到101，再向左移一位得到1010，(101&111)<<1，第三步：重復上述兩步，各位相加 010^1010=1000，進位值為100=(010&1010)<<1，

繼續重復上述兩步：1000^100 = 1100，進位值為0，跳出回圈，1100為最終結果，

注意回圈終止條件，有負數相加的情況，

Java Code


class Solution {
public:
    int Add(int num1, int num2)
    {    
        while(num2!=0){
            int tmp=num1^num2;
            num2=(num1 & num2)<< 1;
            num1=tmp;
        }
        return num1;
    }
};

11、二進制中1的個數 ++

補碼，位運算

輸入一個整數，輸出該數二進制表示中1的個數，其中負數用補碼表示，

題意分析

注意對于負數，右移一位會補 1 而非補零，

CPP Code


// 1. 去掉符號位 1
class Solution {
public:
     int  NumberOf1(int n) {
         int cnt=0;
         if(n<0) {
             n &=0x7fffffff;
             cnt++;
         }
         while(n){
             cnt+=(n&1);
             n>>=1;
         }
         return cnt;
     }
};
// 2. 轉為 unsigned int
class Solution {
public:
     int  NumberOf1(int n) {
         unsigned int nn=n;
         int cnt=0;
         while(nn){
             cnt+=(nn&1);
             nn>>=1;
         }
         return cnt;
     }
};
// 3. 每次 n&(n-1) 將從右邊起的第一個 1 變為 0
public class Solution {
    public int NumberOf1(int n) {
        int count = 0;
        while(n!= 0){
            count++;
            n = n & (n - 1);
         }
        return count;
    }
}

29、最小的K個數+++

查找第K大，或各種排序演算法

輸入n個整數，找出其中最小的K個數，例如輸入4,5,1,6,2,7,3,8這8個數字，則最小的4個數字是1,2,3,4,，

題意分析

用Partition O(n)找到第K大，然后遍歷輸出前K個數，

檢查資料合法情況
partition撰寫
不用IDE的話出現了全角字符、忘記匯入包的問題

Java Code


import java.util.Arrays;
import java.util.ArrayList;
public class Solution {
    public ArrayList GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList ans=new ArrayList<>();
        if(input==null|| k==0 || k>input.length) return ans;
        int x=k+1,st=0,ed=input.length-1;
        do{
            x=Partition(input,st,ed);
            if(xk-1){ed=x-1;}
        }while(x!=k-1);
        //Arrays.sort(input,0,k);
        for(int i=0;i < k;i++){
            ans.add(input[i]);
        }
        return ans;
    }
    private int Partition(int[] arr,int st,int ed){//[, ]
        int pivot=arr[st];
        int i=st,j=ed;
        while(i < j){
            while(j > i && arr[j] >= pivot)j--;
            arr[i]=arr[j];
            while(i < j && arr[i] <= pivot)i++;
            arr[j]=arr[i];
        }
        arr[i]=pivot;
        return i;
    }
}

31、從1到n整數中1出現的次數++++

思維

題目描述

求出1~13的整數中1出現的次數,并算出100~1300的整數中1出現的次數？為此他特別數了一下1~13中包含1的數字有1、10、11、12、13因此共出現6次,但是對于后面問題他就沒轍了，ACMer希望你們幫幫他,并把問題更加普遍化,可以很快的求出任意非負整數區間中1出現的次數（從1 到 n 中1出現的次數），

題意分析

將n的各個位分為兩類：個位與其它位，
對個位來說：

若個位大于0，1出現的次數為round*1+1
若個位等于0，1出現的次數為round*1

對其它位來說，記每一位的權值為base，位值為weight，該位之前的數是former，舉例如圖：
這里寫圖片描述

則：

若weight為0，則1出現次數為round*base
若weight為1，則1出現次數為round*base+former+1
若weight大于1，則1出現次數為rount*base+base

比如：

534 = （個位1出現次數）+（十位1出現次數）+（百位1出現次數）
	=（53*1+1）+（5*10+10）+（0*100+100）= 214
530 = （53*1）+（5*10+10）+（0*100+100） = 213
504 = （50*1+1）+（5*10）+（0*100+100） = 201
514 = （51*1+1）+（5*10+4+1）+（0*100+100） = 207
10 = (1*1)+(0*10+0+1) = 2

————————————————
著作權宣告：本文為CSDN博主「yi_afly」的原創文章，遵循 CC 4.0 BY-SA 著作權協議，轉載請附上原文出處鏈接及本宣告，
原文鏈接：https://blog.csdn.net/yi_afly/article/details/52012593

Java Code


public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int base=1,round=n,weight,former;
        int cnt=0;
        while(base <= n){
            weight=round%10;
            round=round/10;
            cnt+=round*base;
            former=n%base;
            if(weight==1)    cnt+=former+1;
            else if(weight > 1)cnt+=base;
            base*=10;
        }
        return cnt;
    }
}

33、丑數 +

思維

把只包含質因子2、3和5的數稱作丑數（Ugly Number），例如6、8都是丑數，但14不是，因為它包含質因子7，習慣上我們把1當做是第一個丑數，求按從小到大的順序的第N個丑數，

題意分析

根據丑數的定義，丑數應該是另一個丑數乘以2、3或者5的結果（1除外），因此，我們可以創建一個陣列，里面保存的是排好序的丑數，每一個丑數都可以由前面的丑數乘以2、3或者5得到，

問題在于，如何保證生成的丑書序列是有序的，解決方法是，維護3個“指標”，分別指向2、3、5當前要乘的數，然后取三個乘積中的最小加入丑數序列，同時，維護指標所指位置，要注意的是，為了避免重復，如果出現minn==2*num[p2]==5*nums[p5]的情況，那么兩個指標都需要后移，

細節 - 重復不計

Java Code


import java.util.ArrayList;
public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if (index <= 0) return 0;
        int cnt = 0;
        ArrayList nums = new ArrayList<>();
        nums.add(1);
        int p2 = 0, p3 = 0, p5 = 0;
        while (cnt < index) {
            int x = Math.min(2 * nums.get(p2), Math.min(3 * nums.get(p3), 5 * nums.get(p5)));
            nums.add(x);
            cnt++;
            if (x == 2 * nums.get(p2)) p2++;
            if (x == 3 * nums.get(p3)) p3++;// 不是else if
            if (x == 5 * nums.get(p5)) p5++;
        }
        return nums.get(index - 1);
    }
}

41、和為S的連續正數序列

滑動視窗，雙指標

題目描述

小明很喜歡數學,有一天他在做數學作業時,要求計算出9~16的和,他馬上就寫出了正確答案是100，但是他并不滿足于此,他在想究竟有多少種連續的正數序列的和為100(至少包括兩個數)，沒多久,他就得到另一組連續正數和為100的序列:18,19,20,21,22，現在把問題交給你,你能不能也很快的找出所有和為S的連續正數序列? Good Luck!

輸出描述:

輸出所有和為S的連續正數序列，序列內按照從小至大的順序，序列間按照開始數字從小到大的順序

題意分析

n從1開始遞增，長度從sum開始遞減，檢查是否滿足序列和為sum，

審題 - 序列長大于1

Java Code


import java.util.ArrayList;
public class Solution {
    public ArrayList> FindContinuousSequence(int sum) {
        ArrayList> ans = new ArrayList<>();
        ArrayList cur;
        if (sum <= 0) return ans;
        int n = 1, l = sum;
        while (n <= sum && l > 1) {
            while ((n + n + l - 1) * l / 2 > sum) l--;
            if (l > 1 && (n + n + l - 1) * l / 2 == sum) {
                cur = new ArrayList<>();
                for (int i = n; i < n + l; i++) cur.add(i);
                ans.add(cur);
            }
            n++;
        }
        return ans;
    }
}

42、和為S的兩個數字

滑動視窗，雙指標

題目描述

輸入一個遞增排序的陣列和一個數字S，在陣列中查找兩個數，使得他們的和正好是S，如果有多對數字的和等于S，輸出兩個數的乘積最小的，

輸出描述:

對應每個測驗案例，輸出兩個數，小的先輸出，

題意分析

和上題類似的滑動視窗，雙指標，

Java Code


import java.util.ArrayList;
public class Solution {
    public ArrayList FindNumbersWithSum(int[] array, int sum) {
        ArrayList ans = new ArrayList<>();
        if (array == null || array.length < 2 || sum < array[0])
            return ans;
        int p1 = 0, p2 = array.length - 1;
        while (p1 < p2) {
            while (array[p2] + array[p1] > sum && p1 < p2) p2--;
            if (p1 < p2 && array[p2] + array[p1] == sum) {
                ans.add(array[p1]);
                ans.add(array[p2]);
                return ans;
            }
            p1++;
        }
        return ans;
    }
}

45、撲克牌順子

多種情況判斷

題目描述

LL今天心情特別好,因為他去買了一副撲克牌,發現里面居然有2個大王,2個小王(一副牌原本是54張^_^)...他隨機從中抽出了5張牌,想測測自己的手氣,看看能不能抽到順子,如果抽到的話,他決定去買體育彩票,嘿嘿！！“紅心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是順子.....LL不高興了,他想了想,決定大\小王可以看成任何數字,并且A看作1,J為11,Q為12,K為13，上面的5張牌就可以變成“1,2,3,4,5”(大小王分別看作2和4),“So Lucky!”，LL決定去買體育彩票啦，現在,要求你使用這幅牌模擬上面的程序,然后告訴我們LL的運氣如何，如果牌能組成順子就輸出true，否則就輸出false，為了方便起見,你可以認為大小王是0，

題意分析

有四張王一定為順子，其余情況下，一副牌為順子當且僅當最大數字牌和最小數字牌之差小于5且沒有重復的數字牌，

輸入資料檢查
陣列邊界

Java Code


import java.util.Arrays;
public class Solution {
    public boolean isContinuous(int[] numbers) {
        if (numbers == null || numbers.length != 5) return false;
        Arrays.sort(numbers);
        int minn = 0, maxx = numbers[numbers.length - 1];
        int loc = -1;
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] > 0) {
                loc = i;
                minn = numbers[i];
                break;
            }
        }
        if (loc == numbers.length - 1) return true;// 4 king
        if (maxx - minn + 1 > 5) return false;
        for (int i = loc; i + 1 < numbers.length; i++) {
            if (numbers[i] == numbers[i + 1])
                return false;
        }
        return true;
    }
}

46、圓圈中最后剩下的數+++

約瑟夫環，數學

題目描述

每年六一兒童節,牛客都會準備一些小禮物去看望孤兒院的小朋友,今年亦是如此，HF作為牛客的資深元老,自然也準備了一些小游戲，其中,有個游戲是這樣的:首先,讓小朋友們圍成一個大圈，然后,他隨機指定一個數m,讓編號為0的小朋友開始報數，每次喊到m-1的那個小朋友要出列唱首歌,然后可以在禮品箱中任意的挑選禮物,并且不再回到圈中,從他的下一個小朋友開始,繼續0...m-1報數....這樣下去....直到剩下最后一個小朋友,可以不用表演,并且拿到牛客名貴的“名偵探柯南”典藏版(名額有限哦!!^_^)，請你試著想下,哪個小朋友會得到這份禮品呢？(注：小朋友的編號是從0到n-1)

如果沒有小朋友，請回傳-1

題意分析

用模擬來做自然是可以的，但復雜度是O(n*m)，看了一下別人的數學推導思路，

原問題是從0...n-1中回圈去掉第m個數，求剩下的最后一個數是多少，我們假設原求解問題是f(n,m)，

去掉第一個數k=(m-1)%n之后，還剩下k+1...n-1,0...k-1這n-1個數，問題變成了從這n-1個數中回圈刪去第m個數，求最后剩下的一個數，記這個問題為f'(n-1,m)，那么f(n,m)與f'(n-1,m)最終得到的結果是相同的，即①f(n,m)=f'(n-1,m)，

而如果把k+1...n-1,0...k-1與0..n-1作置換，那么②f'(n-1,m)=(f(n-1,m)+k+1)%n，①②式聯合，得到f(n,m)=(f(n-1,m)+k+1)%n，于是遞回關系就找到了，這樣計算的時間復雜度是O(n)，

最后注意遞回的出口，見代碼，

Java Code


public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if (n == 0) return -1;
        if (n == 1) return 0;
        return (LastRemaining_Solution(n - 1, m) + m) % n;
    }
}

63、資料流中的中位數+++

妙用堆，PriorityQueue

題目描述

如何得到一個資料流中的中位數？如果從資料流中讀出奇數個數值，那么中位數就是所有數值排序之后位于中間的數值，如果從資料流中讀出偶數個數值，那么中位數就是所有數值排序之后中間兩個數的平均值，我們使用Insert()方法讀取資料流，使用GetMedian()方法獲取當前讀取資料的中位數，

題意分析

gzshan的分析很清晰，

方法五：最大堆和最小堆，我們注意到當資料保存到容器中時，可以分為兩部分，左邊一部分的資料要比右邊一部分的資料小，如下圖所示，P1是左邊最大的數，P2是右邊最小的數，即使左右兩部分資料不是有序的，我們也有一個結論就是：左邊最大的數小于右邊最小的數，

因此，我們可以有如下的思路：向堆中插入一個資料的時間是O(logn)，而中位數就是堆頂的資料，只需要O(1)的時間就可得到，

而在具體實作上，首先要保證資料平均分配到兩個堆中，兩個堆中的資料數目之差不超過1，為了實作平均分配，可以在資料的總數目是偶數時，將資料插入最小堆，否則插入最大堆，

此外，還要保證所有最大堆中的資料要小于最小堆中的資料，所以，新傳入的資料要和最大堆中最大值或者最小堆中的最小值比較，當總數目是偶數時，我們會插入最小堆，但是在這之前，我們需要判斷這個資料和最大堆中的最大值哪個更大，如果最大值中的最大值比較大，那么將這個資料插入最大堆，并把最大堆中的最大值彈出插入最小堆，由于最終插入到最小堆的是原最大堆中最大的，所以保證了最小堆中所有的資料都大于最大堆中的資料，

Java Code


import java.util.Comparator;
import java.util.PriorityQueue;
public class Solution {
    PriorityQueue minQ = new PriorityQueue<>();// default
    PriorityQueue maxQ = new PriorityQueue<>(new Comparator() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });
    int cnt = 0;
    public void Insert(Integer num) {
        cnt++;
        if ((cnt & 1) == 1) {
            int candidate = num + 1;
            if (!minQ.isEmpty()) candidate = minQ.peek();
            if (num <= candidate) maxQ.add(num);
            else {
                maxQ.offer(candidate);
                minQ.poll();
                minQ.offer(num);
            }
        } else {
            int candidate = num - 1;
            if (!maxQ.isEmpty()) candidate = maxQ.peek();
            if (num >= candidate) minQ.offer(num);
            else {
                minQ.offer(candidate);
                maxQ.poll();
                maxQ.offer(num);
            }
        }
    }
    public Double GetMedian() {
        if ((cnt & 1) == 1) return (double) maxQ.peek();
        else return (minQ.peek() + maxQ.peek()) / 2.0;
    }
}

64、滑動視窗的最大值+++

模擬，滑動視窗，雙端佇列

題目描述

給定一個陣列和滑動視窗的大小，找出所有滑動視窗里數值的最大值，例如，如果輸入陣列{2,3,4,2,6,2,5,1}及滑動視窗的大小3，那么一共存在6個滑動視窗，他們的最大值分別為{4,4,6,6,6,5}；針對陣列{2,3,4,2,6,2,5,1}的滑動視窗有以下6個： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}，

題意分析

用雙端佇列，維護隊首元素為當前視窗的最大值的下標，隊中元素為后續視窗可能的最大值的下標，具體為，每次后移一格成為新的滑動視窗時，【如果隊首過期，那么將隊首刪去】，【如果刪掉佇列中所有比新元素小的元素】，【再將新元素下標加入】，此時，隊首值就是當前視窗的最大值下標，

第一個操作保證及時刪掉了過期的最大值，第二個操作保證了佇列中都是可能為最大值的元素下標，及時剔除了不可能為最大值的元素，第三個操作是由于隨著視窗后移，新的元素可能成為最大元素，

舉例

Java Code


import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
public class Solution {
    public ArrayList maxInWindows(int[] num, int size) {
        ArrayList ans = new ArrayList<>();
        if (num == null || num.length == 0 || size <= 0 || size > num.length)
            return ans;
        Deque dq = new LinkedList<>();// 存的是下標
        for (int i = 0; i < size - 1; i++) {// 前size-1個
            while (!dq.isEmpty() && num[dq.peekLast()] < num[i]) 
                dq.pollLast();
            dq.offerLast(i);
        }
        for (int i = size - 1; i < num.length; i++) {
            if (!dq.isEmpty() && i - dq.peekFirst() >= size) dq.pollFirst();
            while (!dq.isEmpty() && num[dq.peekLast()] < num[i]) 
                dq.pollLast();
            dq.offerLast(i);
            ans.add(num[dq.peekFirst()]);
        }
        return ans;
    }
}

67、剪繩子+++

貪心，動態規劃

題目描述

給你一根長度為n的繩子，請把繩子剪成m段（m、n都是整數，n>1并且m>1），每段繩子的長度記為k[0],k[1],...,k[m]，請問k[0]xk[1]x...xk[m]可能的最大乘積是多少？例如，當繩子的長度是8時，我們把它剪成長度分別為2、3、3的三段，此時得到的最大乘積是18，

題意分析

方法一貪心，盡可能分成3*3*3*..*3或2*3*3*...*3或2*2*3*...*3，因為2*2*2<3*3，

方法二動態規劃，dp[i]定義為，長度為i的繩子，分割或者不分割，得到的最大乘積，

Java Code


public class Solution {
    public int cutRope(int target) {
        int[] dp = new int[60 + 5];
        dp[0] = dp[1] = 0;
        dp[2] = 1;
        dp[3] = 2;
        dp[4] = 4;
        if (target <= 4) return dp[target];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for (int i = 5; i <= target; i++) {
            for (int j = 1; j <= i / 2; j++) {
                dp[i] = Math.max(dp[i], dp[j] * dp[i - j]);
            }
        }
        return dp[target];
    }
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/135947.html

標籤：其他

上一篇：問如何在梯度上添加噪音

下一篇：Airtest 學習 Airtest 的一些經驗分享，新手指引部分

《劍指offer》數學題及其它 (牛客11.05)

12、數值的整數次方+

細節，快速冪

47、求1+2+3+···+n ++

思維發散

48、不用加減乘除做加法++

二進制運算

11、二進制中1的個數 ++

補碼，位運算

29、最小的K個數+++

查找第K大，或各種排序演算法

31、從1到n整數中1出現的次數++++

思維

題目描述

33、丑數 +

思維

41、和為S的連續正數序列

滑動視窗，雙指標

題目描述

輸出描述:

42、和為S的兩個數字

滑動視窗，雙指標

題目描述

輸出描述:

45、撲克牌順子

多種情況判斷

題目描述

46、圓圈中最后剩下的數+++

約瑟夫環，數學

題目描述

63、資料流中的中位數+++

妙用堆，PriorityQueue

題目描述

64、滑動視窗的最大值+++

模擬，滑動視窗，雙端佇列

題目描述

67、剪繩子+++

貪心，動態規劃

題目描述