力扣(LeetCode)刷題，簡單+中等題(第29期)第3題：尋找旋轉排序數組中的最小值

目錄

第1題：分割數組為連續子序列

第2題：翻轉矩陣後的得分

第3題：尋找旋轉排序數組中的最小值

第4題：乘積最大子數組

第5題：不同路徑

第6題：判斷路徑是否相交

第7題：擺動序列

第8題：單調遞增的數字

第9題：移除連結清單元素

第10題：計數二進制子串

力扣(LeetCode)定期刷題，每期10道題，業務繁重的同志可以看看我分享的思路，不是最高效解決方案，隻求互相提升。

試題要求如下：

回答（C語言）：

#define SIZE 10001
bool isPossible(int* nums, int numsSize){
    int one[SIZE] = {0};
    int two[SIZE] = {0};
    int safe[SIZE] = {0};
    int oneSize = 0;
    int twoSize = 0;
    int now;
    int minValue = nums[0] - 1;
    for (int i = 0; i < numsSize; ++i) {
        now = nums[i] - 1 - minValue;
       
        if (one[now] == 0 && two[now] == 0 && safe[now] == 0) {
            ++one[now + 1];
            ++oneSize;
        } else if (one[now] > 0) {
            ++two[now + 1];
            --one[now];
            --oneSize;
            ++twoSize;
        } else if (two[now] > 0) {
            ++safe[now + 1];
            --two[now];
            --twoSize;
        } else{
            ++safe[now + 1];
            --safe[now];
        }
    }
    return twoSize == 0 && oneSize == 0;
}      

運作效率如下所示：

解題思路：

為了得到最高的分數，矩陣的每一行的最左邊的數都必須為 1。為了做到這一點，可以翻轉那些最左邊的數不為 1 的那些行，而其他的行則保持不動。

當将每一行的最左邊的數都變為 1 之後，就隻能進行列翻轉了。為了使得總得分最大，我們要讓每個列中 1 的數目盡可能多。

是以，掃描除了最左邊的列以外的每一列，如果該列 0 的數目多于 1 的數目，就翻轉該列，其他的列則保持不變。

int matrixScore(int** A, int ASize, int* AColSize) {
    int m = ASize, n = AColSize[0];
    int ret = m * (1 << (n - 1));
    for (int j = 1; j < n; j++) {
        int nOnes = 0;
        for (int i = 0; i < m; i++) {
            if (A[i][0] == 1) {
                nOnes += A[i][j];
            } else {
                nOnes += (1 - A[i][j]);  // 如果這一行進行了行反轉，則該元素的實際取值為 1 - A[i][j]
            }
        }
        int k = fmax(nOnes, m - nOnes);
        ret += k * (1 << (n - j - 1));
    }
    return ret;
}
運作效率如下所示：
第3題：尋找旋轉排序數組中的最小值
試題要求如下：
回答（C語言）：
int findMin(int* nums, int numsSize){
    int left = 0,right = numsSize-1,mid;
    while(left < right)
    {
        mid = left + (right - left)/2;
        if(nums[mid]>nums[right])
        {
            left = mid + 1;
        }
        else
        {
            right = mid;
        }
    }
    return nums[left];
}      

第3題： 尋找旋轉排序數組中的最小值

int findMin(int* nums, int numsSize){
    int left = 0,right = numsSize-1,mid;
    while(left < right)
    {
        mid = left + (right - left)/2;
        if(nums[mid]>nums[right])
        {
            left = mid + 1;
        }
        else
        {
            right = mid;
        }
    }
    return nums[left];
}      

#define MAX(A,B) A>B?A:B
#define MIN(A,B) A<B?A:B
int maxProduct(int* nums, int numsSize){
    int imax = 1, imin = 1, res = nums[0];
    int tmp,i;
   
    for(i = 0; i < numsSize; i++)
    {
        if(nums[i] < 0)
        {
            tmp = imax;
            imax = imin;
            imin = tmp;
        }
       
        imax = MAX(imax * nums[i], nums[i]);
        imin = MIN(imin * nums[i], nums[i]);
       
        res = MAX(imax, res); 
    }
    return res;
}      

int uniquePaths(int m, int n) {
    int f[m][n];
   
    for (int i = 0; i < m; ++i) {
        f[i][0] = 1;
    }
    for (int j = 0; j < n; ++j) {
        f[0][j] = 1;
    }
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            f[i][j] = f[i - 1][j] + f[i][j - 1];
        }
    }
    return f[m - 1][n - 1];
}      

#define MAX 1001
bool isPathCrossing(char * path){
    if(path==NULL)  return false;
    int hash[MAX][MAX]={0};
    int x=500,y=500;
    hash[x][y]=1;//zero point is 1
    for(int i=0; i<strlen(path); i++){
        if(path[i]=='N'){
            if(hash[x][y+1]==1) return true;
            else hash[x][++y]=1;
        }
        if(path[i]=='S'){
            if(hash[x][y-1]==1) return true;
            else hash[x][--y]=1;
        }
        if(path[i]=='W'){
            if(hash[x-1][y]==1) return true;
            else hash[--x][y]=1;
        }
        if(path[i]=='E'){
            if(hash[x+1][y]==1) return true;
            else hash[++x][y]=1;
        }
    }
    return false;
}      

int wiggleMaxLength(int* nums, int numsSize) {
    if (numsSize < 2) {
        return numsSize;
    }
    int up = 1, down = 1;
    for (int i = 1; i < numsSize; i++) {
        if (nums[i] > nums[i - 1]) {
            up = fmax(up, down + 1);
        } else if (nums[i] < nums[i - 1]) {
            down = fmax(up + 1, down);
        }
    }
   
    return fmax(up, down);
}      

int monotoneIncreasingDigits(int N){
    bool isInc = true;
    int mod = N % 10;
    int curr = N / 10;
    int multi = 10;
    int lastNum = curr;
    int lastMulti = multi;
    while(curr > 0) {
        if (mod < curr % 10) {
            isInc = false;
            lastNum = curr;
            lastMulti = multi;
            curr -= 1; // 不單調遞減時去前面借一位
        }
        mod = curr % 10;
        curr /= 10;
        multi *= 10;
    }
    if (isInc == false) {
        return lastNum * lastMulti - 1;
    }
   
    return N;
}      

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val){ 
    if (head == NULL) {
        return NULL;
    }     
    /* 删除 head 節點後面值為 val 的元素的節點 */
    struct ListNode* res = removeElements(head->next, val);
    /* head 節點是要删除的節點 */
    if (head->val == val) {
        return res;
    } else {
        head->next = res;
        return head;
    }
}      

int countBinarySubstrings(char* s) {
    int ptr = 0, n = strlen(s), last = 0, ans = 0;
    while (ptr < n) {
        char c = s[ptr];
        int count = 0;
       
        while (ptr < n && s[ptr] == c) {
            ++ptr;
            ++count;
        }
        ans += fmin(count, last);
        last = count;
    }
    return ans;
}      

運作效率如下所示