Read N Characters Given Read4 -- Leetcode

Question:

The API: int read4(char *buf) reads 4 characters at a time from a file.

The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.

By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.

Note:
The read function will only be called once for each test case.

Answer:

// Forward declaration of the read4 API.
int read4(char *buf);

class Solution {
public:
    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    int read(char *buf, int n) {

        int readNumRes=0;
        int m = n/4;
         
        for(int i=0;i<m;++i){
   
            int readNum = read4(buf);
            buf+=readNum;
            readNumRes+=readNum;
         
            if(readNum < 4){
                return readNumRes;     //return firstly!
            }
        }
     

        // Last several bytes should be condsider seperately, still has chars to read in the file
        int q = n%4;
        char tmpBytes[5];  //tmp bytes space for last read4(), space is 5, include '\0'!
       
        //For example: "ab", read(1); can not use read4(buf) directly, lastNum = 1, q=1, readNum=2 in the case!

        int readNum = read4(tmpBytes);
        int lastNum = q < readNum ? q : readNum;
     
        for(int i=0;i<lastNum;++i){
            *(buf+i) = tmpBytes[i];           //!important
        }
        readNumRes += lastNum;
        return readNumRes;
    }
};

Find Minimum in Rotated Sorted Array II -- Leetcode

Question:

Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

Answer:

public class Solution {
    public int findMin(int[] num) {
       
        int start=0, end=num.length-1;
       
        while(start+1 < end){      //ensure: start != mid != end  
       
             int mid = start + (end-start)/2;
           
             if(num[mid] < num[end]){
                 end = mid;
             }
             else if(num[mid] > num[end]){
                 start = mid;
             }
             else{     //num[mid] == num[end], like [3 3 1 3]
           
                 int endtmp = end-1;
                 while(endtmp>mid && num[endtmp]==num[end]){
                     endtmp--;
                 }
                 if(num[endtmp] != num[mid]){     //there existeds peak point in the range!
                     start = mid;
                 }
                 else{
                     end = mid;     //include case: endtmp==mid, there are no peak point in the range!
                 }
             }
        }
       
        //start = end - 1
        if(num[start]<=num[end]){
            return num[start];
        }
        return num[end];
    }
}

Find Minimum in Rotated Sorted Array -- Leetcode

Question:

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

Answer:

public class Solution {
    public int findMin(int[] num) {
       
        int start=0, end=num.length-1;
       
        while(start+1 < end){      //ensure: start != mid != end  
             int mid = start + (end-start)/2;
           
             if(num[mid] < num[end]){
                 end = mid;
             }
             else{
                 start = mid;
             }
        }
       
        if(num[start]<num[end]){
            return num[start];
        }
        return num[end];
    }
}