Day 122, #246 #247 #251 #259, Strobogrammatic Number, Strobogrammatic Number II, Flatten 2D Vector, 3Sum Smaller

Strobogrammatic Number

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to determine if a number is strobogrammatic. The number is represented as a string.

For example, the numbers "69", "88", and "818" are all strobogrammatic.

--------------------------------------------------------

class Solution {
public:
    bool isStrobogrammatic(string num) {
        int i = 0, j = num.length() - 1;
        while (i <= j) {
            if ((num[i] == '1' && num[j] == '1') 
                || (num[i] == '8' && num[j] == '8') 
                || (num[i] == '0' && num[j] == '0')
                || (num[i] == '6' && num[j] == '9')
                || (num[i] == '9' && num[j] == '6')){
                i++;
                j--;
            }else {
                return false;
            }
        }
        
        return true;
    }
};

Strobogrammatic Number II

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Find all strobogrammatic numbers that are of length = n.

For example,
Given n = 2, return ["11","69","88","96"].

Hint:

1. Try to use recursion and notice that it should recurse with n - 2 instead of n - 1.

-----------------------------------------------------------
也可递归

class Solution {
public:
    vector<string> findStrobogrammatic(int n) {
        vector<string> odd = {"1","8","0"};
        if (n == 1) return odd;

        vector<string> rt;
        if (n % 2 == 1) {
            rt = odd;
        }else {
            rt.push_back("");
        }
        
        int i = 0;
        while (i < n - 1) {
            vector<string> t;
            for (string s : rt) {
                if (i + 2 < n - 1) t.push_back("0" + s + "0");
                t.push_back("1" + s + "1");
                t.push_back("8" + s + "8");
                t.push_back("6" + s + "9");
                t.push_back("9" + s + "6");
            }
            i += 2;
            rt = t;
        }
        
        return rt;
    }
};

另一种方法

class Solution {
public:
    void helper(vector<string> &rt,string s,int left,int right) {
        if (left > right) {
            if (s[0] != 0) {
                rt.push_back(s);
            }
            return;
        }
        if (left != 0) {
            s[left] = '0',s[right] = '0';
            helper(rt,s,left + 1,right - 1);
        }
        s[left] = '1',s[right] = '1';
        helper(rt,s,left + 1,right - 1);
        s[left] = '8',s[right] = '8';
        helper(rt,s,left + 1,right - 1);
        if (left != right) {
            s[left] = '6',s[right] = '9';
            helper(rt,s,left + 1,right - 1);
            s[left] = '9',s[right] = '6';
            helper(rt,s,left + 1,right - 1);
        }
        
    }

    vector<string> findStrobogrammatic(int n) {
        vector<string> rt;
        string s(n,'\0');
        helper(rt,s,0,n - 1);
        if (n == 1) rt.push_back("0");
        return rt;
    }
};

Flatten 2D Vector

Implement an iterator to flatten a 2d vector.

For example,
Given 2d vector =

[
  [1,2],
  [3],
  [4,5,6]
]

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,2,3,4,5,6].

Hint:

1. How many variables do you need to keep track?
2. Two variables is all you need. Try with x and y.
3. Beware of empty rows. It could be the first few rows.
4. To write correct code, think about the invariant to maintain. What is it?
5. The invariant is x and y must always point to a valid point in the 2d vector. Should you maintain your invariant ahead of time or right when you need it?
6. Not sure? Think about how you would implement hasNext(). Which is more complex?
7. Common logic in two different places should be refactored into a common method.

Follow up:
As an added challenge, try to code it using only iterators in C++ or iterators in Java.

------------------------------------------------------------------------
Only with iterators
C++的iterator没有next或hasNext

class Vector2D {
public:
    Vector2D(vector<vector<int>>& vec2d) {
        itr1 = vec2d.begin();
        end1 = vec2d.end();
        if (itr1 != end1) {
            itr2 = itr1->begin();
        }
    }

    int next() {
        hasNext();
        int rt = *itr2;
        itr2++;
        return rt;
    }

    bool hasNext() {
        while (itr1 != end1) {
            if (itr2 != itr1->end()) return true;
            itr1++;
            if (itr1 != end1) {
                itr2 = itr1->begin();
            }
        }
        
        return false;
    }
private:
    vector<vector<int>>::iterator itr1, end1;
    vector<int>::iterator itr2;
};

/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D i(vec2d);
 * while (i.hasNext()) cout << i.next();
 */

3Sum Smaller

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

For example, given nums = [-2, 0, 1, 3], and target = 2.

Return 2. Because there are two triplets which sums are less than 2:

[-2, 0, 1]
[-2, 0, 3]

Follow up:
Could you solve it in O(n2) runtime?

--------------------------------------------------------
O(n^2), 给的条件 i < j < k一点用也没有

class Solution {
public:
    int threeSumSmaller(vector<int>& nums, int target) {
        int count = 0;
        sort(nums.begin(),nums.end());
        for (int i = 0; i < (int)nums.size() - 2; i++) {
            int left = i + 1, right = nums.size() - 1;
            int sum = target - nums[i];
            
            while (left < right) {
                if (nums[left] + nums[right] >= sum) {
                    right--;
                }else {
                    count += right - left;
                    left++;
                }
            }
        }
        
        return count;
    }
};