info2021-homework1

Two Sum

• Approach 1:
  Iterate through all possible combinations, and check if the sum of combination is equal to target value, return index of two numbers.
  Time complexity: O(

  $n^2$). For each element, we try to find its complement by looping through the rest of the array which takes O(n) time. Therefore, the time complexity is O(
  $n^2$).
  ​​​​vector<int> twoSum(vector<int>& nums, int target) {
  ​​​​    for(int i=0; i<nums.size(); i++) {
  ​​​​        for(int j=i+1; j<nums.size(); j++) {
  ​​​​            if(nums[i]+nums[j] == target) return {i, j};
  ​​​​        }
  ​​​​    }
  ​​​​    return {-1, -1};
  ​​​​}
  

• Approach 2:
  Walk through all elements in the array, and use unordered_map to store the complement value of visited element, if the value is equal to the complement of any visited value, return the index of the two number.
  Time Complexity: O(n). For each element, we check if any of visited value's complement is equal to it, since unordered_map is hashmap which takes O(1). Therefore, the time complexity is O(n).

  ​​​​vector<int> twoSum(vector<int>& nums, int target) {
  ​​​​    unordered_map<int, int> h;
  ​​​​    for(int i=0; i<nums.size(); i++) {
  ​​​​        if(h.find(nums[i]) != h.end()) {
  ​​​​            return {h[nums[i]], i};
  ​​​​        }
  ​​​​        h[target-nums[i]] = i;
  ​​​​    }
  ​​​​    return {-1, -1};
  ​​​​}
  

Reverse only letters

• Solution:
  Keep find the character in string S with two pointer, exchange two character when both pointer points to English character.
  Time complexity: O(n). Visit all character once, which takes O(n).
  ​​​​class Solution {
  ​​​​private:
  ​​​​    bool isletter(char c) {
  ​​​​        if(c >= 'A' && c <= 'Z') return true;
  ​​​​        if(c >= 'a' && c <= 'z') return true;
  ​​​​        return false;
  ​​​​    }
  ​​​​public:
  ​​​​    string reverseOnlyLetters(string s) {
  ​​​​        int i=0, j=s.size()-1;
  ​​​​        while(i <= j) {
  ​​​​            while(!isletter(s[i]) && i<j) ++i;
  ​​​​            while(!isletter(s[j]) && i<j) --j;
  ​​​​            if(i >= j) return s;
  ​​​​            char tmp = s[i];
  ​​​​            s[i++] = s[j];
  ​​​​            s[j--] = tmp;
  ​​​​        }
  ​​​​        return s;
  ​​​​    }
  ​​​​};
  

Jump Game

• Solution:
  Iterating right-to-left, for each position we check if there is a potential jump that reaches a GOOD index (currPosition - leftmostGoodIndex <= nums[currPosition]). If we can reach a GOOD index, then our position is itself GOOD. Also, this new GOOD position will be the new leftmost GOOD index. Iteration continues until the beginning of the array. If first position is a GOOD index then we can reach the last index from the first position.
  Time complexity: O(n). Iterate right-to-left takes O(n).
  ​​​​bool canJump(vector<int>& nums) {
  ​​​​    int last = nums.size()-1;
  ​​​​    for(int i=nums.size()-1; i>=0; --i) {
  ​​​​        if(last-i <= nums[i]) last = i;
  ​​​​    }
  ​​​​    return last == 0 ? true : false;
  ​​​​}