8.3 细节实现

边备考做点简单滴

to do

1] Reverse Integer

want to check if overflowed, reduce the bigger number INT_MAX for comparison

• version 1: note using int sign instead of bool

    int reverse(int x) {
        int sign = x<0? -1 : 1;
        x = abs(x);
        int r = 0;
        for (; x; x/=10) {
            if (r > INT_MAX/10 || r*10 > INT_MAX - x%10) return 0;
            r = r*10 + x%10;
        }
        return sign*r;
    }

• version 2: checking if overflowed at each step

    int reverse(int x) {
        int r = 0;
        for (; x; x/=10) {
            int tail = x%10;
            int newr = r*10 + tail;
            if ((newr-tail)/10 != r) return 0;
            r = newr;
        }
        return r;
    }

2] Palindrome Number

    bool isPalindrome(int x) {
        if (x<0) return false;
        
        int divisor = 1;
        while (x/divisor>=10) divisor *= 10;
        
        while (x>0) {
            int first = x/divisor;
            int last = x%10;
            if (first!=last) return false;
            x = x % divisor /10;
            divisor /= 100;
        }
        return true;
    }

• here is my failed one
  cannot handle 100021 F, 10022001 T at the same time
  Tho if this function is used a lot, can implement binary search and hardcode the vector powOf10s to aoivd the linear look up of the first divisor.

class Solution {
public:
    // if n < 0, return 1 which will not function;
    // binary search to improve
    int  findPowOf10(int n, vector<int>& powOf10s) {
        for (int i=0; i<powOf10s.size(); ++i) {
            if (n <= powOf10s[i]) return pow(10, i);
        }
        return -1;
    }
    
    bool isPalindrome(int x) {
        if (x<0) return false;
        if (x<10) return true;
        // val at index i represents inclusive upper bound of numbers that can get its first digit by:
        // number / (10^i), corresponding lower bound is 10^i
        vector<int> powOf10s;   
        for (int i=0;; ++i) {
            int upperBound = pow(10, i+1)-1;
            if (upperBound < 0) break;
            powOf10s.push_back(upperBound);
        }
        
        while (x>0) {
            int last = x%10;
            int divisor = findPowOf10(x, powOf10s); 
            int first = x / divisor;
            if (first != last) return false;
            x = x % divisor /10;
        }
        return true;
    }
};

3] Insert Interval

ehh why running error? runs fine on vm

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public: 
    struct info {
      int ct;
      bool gap;
      info(): ct(0), gap(true){};
      info(int c, bool g): ct(c), gap(g){};
    };
    
    // count number of occurrences of intervals, before the section that contains val
    info sectionCtsBefore(vector<Interval>& intervals, int val) {
        int lastb = INT_MIN;
        int i=0;
        for (; i<intervals.size(); ++i) {
            int f = intervals[i].start;
            int b = intervals[i].end;
            if (lastb<val && val<f) {
                return info(i, true);
            } else if (f<=val && val<=b) {
                return info(i, false);
            }
            lastb = b;
        }
        return info(i, true);
    }
    // remove elements within given inclusive bound
    void removeElements(vector<Interval>& intervals, int starti, int endi) {
        if (starti>endi || starti>=intervals.size()) return;
        intervals.erase(intervals.begin()+starti, intervals.begin()+endi+1);
        cout<<"erased\n";
    }
    
    vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
        if (intervals.empty()) {
            intervals.push_back(newInterval);
            return intervals;
        }
        int fst = newInterval.start;
        int snd = newInterval.end;
        info fsti = sectionCtsBefore(intervals, fst);
        cout<<"fsti: "<<fsti.gap<<" "<<fsti.ct<<endl;
        info sndi = sectionCtsBefore(intervals, snd);
        cout<<"sndi: "<<sndi.gap<<" "<<sndi.ct<<endl;
        int newf = 0;
        int newb = 0;
        if (fsti.gap) {
            newf = fst;
            if (sndi.gap) {
               newb = snd;
               removeElements(intervals, fsti.ct, sndi.ct-1);
            } else {
               newb = intervals[sndi.ct].end;
               removeElements(intervals, fsti.ct, sndi.ct);
            }
        } else {
            newf = intervals[fsti.ct].start;
            if (sndi.gap) {
                newb = snd;
                removeElements(intervals, fsti.ct, sndi.ct-1);
            } else {
                newb = intervals[sndi.ct].end;
                removeElements(intervals, fsti.ct, sndi.ct);
            }
        }
        intervals.insert(intervals.begin() + fsti.ct, Interval(newf, newb));
        return intervals;
        
    }
};

这个也run code runtime error，不信╭(╯^╰)╮.but accp

class Solution {
public:
    vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
        int fst = newInterval.start;
        int snd = newInterval.end;
        for (auto it = intervals.begin(); it<intervals.end(); ) {
            if (snd < it->start) {
                intervals.insert(it, Interval(fst, snd));
                return intervals;
            } else if (fst <= it->end) {
                fst = min(fst, it->start);
                snd = max(snd, it->end);
                it = intervals.erase(it);
            } else {
                ++it;
            }
        }
        intervals.insert(intervals.end(), Interval(fst, snd));
        return intervals;
    }
};