leetcode-678 Valid Parenthesis String

題意: 給定一含括弧字串,內另含*符號,可替代為  (  or  ) or 不替代

解題思路: 這題的基本概念,可先參見筆者對另一題的解法,總之就是要確保一路上左括弧都會大於等於右括弧,且最後左括弧數能等於右括弧數

可以用區間概念來處理,區間右端表示左括弧最多能比右括弧多幾個
                                                 左端表示左括弧最少能比右括弧多幾個(一定要大於等於零)

當遇到 ( 時, 區間左右端都加一
             ) 時, 區間左右端都減一
             *時, 區間左端減一,右端加一(因為可為左括弧或右括弧)
如此即可解

c++ code如下:

class Solution {
public:
    bool checkValidString(string s) {
        int top=0;
        int bottom=0;
        int len=s.length();
        for(int i=0;i<len;i++)
        {
            if(s[i]=='(')
            {
                top++;
                bottom++;
            }
            else if(s[i]==')')
            {
                top--;
                bottom--;                   
            }
            else
            {
                top++;
                bottom--;
            }
            if(top<0)
                return false;
            if(bottom<0)
                bottom=0;
        }
        if(bottom==0)
            return true;
        return false;
    }
};

leetcode-680 Valid Palindrome II

題意: 給定一字串,最多可以消去一個字,返回是否為回文字串

解題思路: 簡單,因為只能削去一個字,所以當遇到第一個不符合回文字串的字時,有兩種處理方式, 削去目前的字(即表示從下一個位置開始處理),或削去比對的另一個字,將對方處理位置減一
,考慮這兩種處理方式,即為所求

c++ code:

class Solution {
public:
    bool validPalindrome(string s) {
        int len=s.length()-1;
        int ch=len/2;
        int i;
        int ok=1;
        for(i=0;i<=ch;i++)
        {
            if(s[i]!=s[len-i])
              break;  
        }
        for(int j=i+1;j<=ch;j++)
        {
            if(s[j]!=s[len+1-j])
            {
                ok=0;
                break;
            } 
        }
        if(ok)
            return true;
        ok=1;
        for(int j=i;j<=ch;j++)
        {
            if(s[j]!=s[len-1-j])
            {
                ok=0;
                break;
            } 
        }
        if(ok)
            return true;
        return false;
        
    }
};

binary search

二分搜索說簡單也算簡單 說難也算難 有時寫不好 就會變成無窮迴圈
關鍵在哪裡呢  讓我來介紹一下巴

二分搜索的原理很簡單 就是針對以排序數列 利用比大小 每次捨去一半數列

至於為何會寫不好呢 有個小技巧可以克服 就是利用開閉區間的概念

開區間  (a,b) 意思是數會在a,b間  但不等於a 也不等於b
閉區間  [a,b] 意思是數會在a,b間  但可以等於a 也可以等於b

搞懂了這個之後  我們來看一道題: 連結
題目是從leetcode來的
題意是給一以排序數列,插入值為target的數,維持依然排序,返回插入點

先看兩端開區間寫法:
可注意到left取-1, right取總數,剛好確保為開區間

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left=-1;
        int right=nums.size();
        int mid;
        while(right-left>1)
        {
            mid=(left+right)/2;
            if(target>nums[mid])
                left=mid;
            else if(target<nums[mid])
                right=mid;
            else
                return mid;
        }
        return left+1;
    }
};

再看兩端閉區間寫法:

可注意到left取0,right取數量減一,因為允許區間和數字相等,所以取數列兩端點,
終止條件也完全不同,允許>=,因為閉區間本來就允許兩端相等,此外每次更新也不同,
left=mid+1 和 right=mid-1 因為閉區間允許相同 所以每次可往前推進一個
最後就是return的也不同 因為left是確定至少會大於等於這個數 所以返回left

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left=0;
        int right=nums.size()-1;
        int mid;
        while(right>=left)
        {
            mid=(left+right)/2;
            if(target>nums[mid])
                left=mid+1;
            else if(target<nums[mid])
                right=mid-1;
            else
                return mid;
        }
        return left;
    }
};

總結:
搞懂了以上概念後 還可以自行變化 比如說 [ ) or ( ], 原理和上面也差不多,就自己嘗試囉

leetcode-36 Valid Soduku

題意: 給定一數獨盤面,確定目前盤面是否合法

解題思路: 大水題, 依規則,橫向確認,直向確認,九宮格確認即可

C++ code:

class Solution {
public:
    int count[200];
    int count1[200];
    int square[10][10][200];
    bool isValidSudoku(vector<vector<char>>& board) {
        for(int i=0;i<9;i++)
        {
            memset(count,0,sizeof(count));
            memset(count1,0,sizeof(count));
            for(int j=0;j<9;j++)
            {
                if(board[i][j]!='.')
                {
                    if(count[board[i][j]])
                        return false;
                    if(square[i/3][j/3][board[i][j]])
                        return false;
                    square[i/3][j/3][board[i][j]]++;
                    count[board[i][j]]++;
                }
                if(count1[board[j][i]]&&board[j][i]!='.')
                    return false;
                count1[board[j][i]]++;       
            }
        }
        return true;
    }
};

leetcode-35

leetcode-34 Search Insert Position

題意: 對一內部元素不重複的已排序數列,插入數字

解題思路: 就是二分搜索,原理可見筆者文章

c++ code:

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left=-1;
        int right=nums.size();
        int mid;
        while(right-left>1)
        {
            mid=(left+right)/2;
            if(target>nums[mid])
                left=mid;
            else if(target<nums[mid])
                right=mid;
            else
                return mid;
        }
        return left+1;
    }
};

血尿臨床思路

Hematuria 在臨床上很常見   茲將臨床思路整理如下

先看病人是哪一種血尿
1.  如果是gross hematuria(肉眼可見): 考慮泌尿道問題=>
若病人無外傷或UTI=>考慮影像學檢查(CT, renal echo, IVP)=>r/o malignancy, nephrolithiasis
                                  => cystoscopy=> r/o BPH, bladder tumor

2. 若為microscopic hematuria(>=3/HPF): 先驗sediment=>確定是否真的為血尿
因為若只有驗U/A=>未必為真正血尿(可能受myoglobulin, MC影響)

=> 若sediment 亦為postive=> confirm hematuria
=>  可藉由病史詢問 , PE and U/A=> 確認是否為UTI, APN,MC, recently urological surgery影響
=> 看sediment 是否有dysmorphic RBC, RBC cast, WBC cast
=> 若有=>考慮medical renal disease=> 包括glomerulonephritis, nephrotic syndrome, AIN....
(亦需沿下面流程r/o urinary tract tumor)
=> 若無=> consider malignancy risk
=> if high risk=> CT=>r/o malignancy, nephrolithiasis
=>if low risk or contrast allergy or poor renal function=> MRI,non-contrast CT, renal echo=> r/o malignancy, nephrolithiasis

=> cystoscopy=> r/o BPH, bladder tumor


reference:
1. Harrison's principles of internal medicine
2. AUA guidelinde
3. AAFP website
4. Massachusetts pocket medicine of internal medicine

leetcode-667 Beautiful Arrangement II

題意: 給定n和k, 求出由1-n組成的array,其相鄰數的差值洽有k種

解題思路: 這題是大水題,稍微試一下就可以解決,構作 1,k+1,(k+1)-(k-1),k,..... ; 即可發現符合需求

C++code:

class Solution {
public:
    vector<int> constructArray(int n, int k) {
        vector<int>ans;
        int cur=1;
        int s=1;
        ans.push_back(1);
        for(int i=k;i>=1;i--)
        { 
            cur=cur+s*i;
            ans.push_back(cur);
            s=-s;
        }
        for(int i=k+2;i<=n;i++)
            ans.push_back(i);
        return ans;
    }
};

leetcode-33 Search in Rotated Sorted Array

題意: 在一個rotate array內找出目標值,返回index

解法:做兩次二分查找,第一次找出rotate的點,第二次找出目標值,複雜度O(log n)

我的解法是第一次利用nums[i]>nums[i+1]來判別,但缺點是有時array根本沒被rotate,因此須設定count,若count超過特定值,則中斷,得知array未被rotate,第二次則為一般二分查找

leetcode上有人有更簡潔寫法,第一次查找找出最小值,第二次利用二分查找加移位


我的解法c++ code:

class Solution {
public:
    int search(vector<int>& nums, int target) {
        
        int len=nums.size();
        int left=0;
        int right=len-1;
        int mid=(left+right)/2;
        if(len==0)
            return -1;
        if(len==1)
        {
            if(nums[0]==target)
                return 0;
            else
                return -1;
        }
        int count=0;
        while(nums[mid]<nums[mid+1])
        {
            if(nums[mid]<nums[len-1])
                right=mid-1;
            else
                left=mid+1;
            mid=(left+right)/2;
            count++;
            if(count>100)
                break;
        }
        if(target>nums[0])
        {
            right=mid;
            left=0;
        }
        else
        {
            if(target<nums[0])
            {
                left=mid+1;
                right=len-1;
            }
            else
                return 0;                
        }
        if(count>100)
        {
            left=0;
            right=len-1;
        }
        mid=(left+right)/2;
        count=0;
        while(nums[mid]!=target)
        {
            if(nums[mid]>target)
                right=mid;
            else
                left=mid+1;
            mid=(left+right)/2;
            count++;
            if(count>100)
                return -1;
        }
        return mid;
    }
};

leetcode-32 Longest Valid Parentheses

leetcode-31 Next Permutation

待補