Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int count = 1;
        int ans = 0, size = nums.size();
        if (size == 0 || size == 1) {
            return size;
        }
     
        for (int i = 0; i < nums.size() - 1; i++) {
            if (nums[i] != nums[i + 1]) {
                nums[ans++] = nums[i];
                count = 1;
            } else {
                count++;
                if (count == 2) {
                    nums[ans++] = nums[i];
                }
            }
        }
        nums[ans] = nums[size - 1];
        return ans + 1;
    }
};

============= Another attempt ==========
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int size = 0, iter = 1, count = 1;
       
        if (nums.size() == 0) {
            return size;
        }
       
        while (iter < nums.size()) {
            if (nums[iter] == nums[size]) {
                count++;
                if (count == 2) {
                    nums[size + 1] = nums[iter];
                    size++;
                }
            } else {
                count = 1;
                nums[size + 1] = nums[iter];
                size++;
            }
            iter++;
        }
        nums.resize(size + 1);
        return size + 1;
    }
};

============= Optimized ==============
class Solution { public: int removeDuplicates(vector<int>& nums) { if(nums.size()<3) return nums.size(); int index=2; for(int i=2;i<nums.size();i++){ if(nums[i]!=nums[index-2]) nums[index++] = nums[i]; } return index; } };

Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

class Solution {
public:
    bool dfs(vector<vector<char>>& board, vector<vector<bool>>& visited,
             int i, int j, string word, int start) {          
        if (start == word.size()) {
            return true;
        }    
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() ||
            visited[i][j] || board[i][j] != word[start]) {
            return false;
        }
     
        visited[i][j] = true;
        bool ans = dfs(board, visited, i + 1, j, word, start + 1) ||
                   dfs(board, visited, i, j + 1, word, start + 1) ||
                   dfs(board, visited, i, j - 1, word, start + 1) ||
                   dfs(board, visited, i - 1, j, word, start + 1);
        if (ans == true) {
            return ans;
        }
        visited[i][j] = false;
        return false;
     
    }
 
    bool exist(vector<vector<char>>& board, string word) {
        bool ans = false;
        if (word.empty()) {
            return ans;
        }
        int row = board.size();
        int col = (board.size() != 0 ? board[0].size() : 0);
     
        vector<vector<bool>> visited(row, vector<bool>(col, false));
     
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                ans = dfs(board, visited, i, j, word, 0);
                if (ans) {
                    return true;
                }
            }
        }
        return false;
    }
};



=============== Faster if don't used visited matrix, instead use the same board =========
char letter = board[ y ][ x ]; board[ y ][ x ] = '*'; bool success = DFS( board, y, x + 1, word, index + 1 ) || DFS( board, y, x - 1, word, index + 1 ) || DFS( board, y + 1, x, word, index + 1 ) || DFS( board, y - 1, x, word, index + 1 ); board[ y ][ x ] = letter;

Simplify Path

Solution:

Problem:

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"




class Solution {
public:
 
    void split(string str, vector<string>& folders, char dil) {
        stringstream ss(str);
        string split_str;
        while (getline(ss, split_str, dil)) {
            folders.push_back(split_str);
        }
        return;
    }
    string simplifyPath(string path) {
        stack<string> st;
     
        vector<string> folders;
        split(path, folders, '/');
     
        for (int i = 0; i < folders.size(); i++) {
            if (folders[i] == "..") {
                if(!st.empty()) {
                    st.pop();
                }
            } else if (folders[i] != "." && folders[i] != "") {
                st.push(folders[i]);
            }
        }
        string ans;
        while (!st.empty()) {
            ans = "/" + st.top() + ans;
            st.pop();
        }
        return (ans.empty() ? "/": ans);
    }
};


============= Updated ========
class Solution {
public:
    vector<string> split(string str, char delim) {
        vector<string> ans;
        stringstream ss(str);
        string token;
        while(getline(ss, token, delim)) {
            ans.push_back(token);
        }
        return ans;
    }
   
    string form_ans(stack<string> st) {
        string ans;
       
        while (!st.empty()) {
            ans = st.top() + ans;
            ans = "/" + ans;
            st.pop();
        }
        if (ans == "") {
            return "/";
        }
        return ans;
       
    }
   
    string simplifyPath(string path) {
        stack<string> st;
        vector<string> strs = split(path, '/');
       
        for (int i = 0; i < strs.size(); i++) {
            if (strs[i] != ".." && strs[i] != "." && strs[i] != "") {
                st.push(strs[i]);
            } else if (strs[i] == "..") {
                if (!st.empty()) {
                    st.pop();
                }
            }
        }
        string ans = form_ans(st);
        return ans;
    }
};

Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

class Solution {
public:
    void LC(string digits, map<char, string> mp, vector<string>& sol) {
        for (int i = 0; i < digits.size(); i++) {
            string letter = mp[digits[i]];
            int sol_size = sol.size();
            vector<string> tmp;
            for (int k = 0; k < sol_size; k++) {
                for (int j = 0; j < letter.size(); j++) {
                    tmp.push_back(sol[k] + string(1, letter[j]));
                }
            }
            sol = tmp;
            tmp.clear();
        }
        return;
    }
 
    vector<string> letterCombinations(string digits) {
        vector<string> sol;
     
        if (digits.empty()) {
            return sol;
        }
        sol.push_back("");
     
        map<char,string> mp;
        mp['1'] = "";mp['0'] = "";
        mp['2'] = "abc";mp['3'] = "def";mp['4'] = "ghi";mp['5'] = "jkl";
        mp['6'] = "mno";mp['7'] = "pqrs";mp['8'] = "tuv";mp['9'] = "wxyz";
     
        LC(digits, mp, sol);
        return sol;
    }
};




==== online backtracking =====

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> lettComb;
        string dict[] = {" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        string comb(digits.size(),'\0');
        findLettComb(digits, 0, dict, comb, lettComb);
        return lettComb;
    }
    
    void findLettComb(string &digits, int index, string dict[], string &comb, vector<string> &lettComb) {
        if(index==digits.size()) {
            lettComb.push_back(comb);
            return;
        }
        
        string lett= dict[digits[index] - '0'];
        for(int i=0; i<lett.size(); i++) {
            comb[index] = lett[i];
            findLettComb(digits, index+1, dict, comb, lettComb);
        }
    }
};

Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Solution:

class Solution {
public:
    void process_vector(vector<int>& tmp, vector<pair<int, int> >& nums) {
        for (int i = 0; i < tmp.size(); i++) {
            nums.push_back(make_pair(tmp[i], i));
        }
    }
   
    static bool comp(pair<int, int> first, pair<int, int> second) {
        return first.first < second.first;
    }
   
    vector<int> twoSum(vector<int>& tmp, int target) {
        vector<int> sol;
        vector<pair<int, int> > nums;
        process_vector(tmp, nums);
        sort(nums.begin(), nums.end(), comp);
        if (nums.size() == 0) {
            return sol;
        }
       
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int temp_sum = nums[left].first + nums[right].first;
            if (temp_sum == target) {
                sol.push_back(nums[left].second);
                sol.push_back(nums[right].second);
                return sol;
            } else if (temp_sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return sol;
    }
};

Diameter of Binary Tree

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree 

          1
         / \
        2   3
       / \     
      4   5    

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

Solution:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        int dia = 0, height = 0;
        height = helper(root, dia);
        // Get edges from number of nodes.
        return dia > 1 ? dia  - 1: 0;
    }
   
    int helper(TreeNode *root, int& dia) {
        if (root == NULL) {
            return 0;
        }
        int left_height = 0, right_height = 0, left_dia = 0, right_dia = 0;
       
        left_height = helper(root -> left, left_dia);
        right_height = helper(root -> right, right_dia);
       
        dia = max(left_height + right_height + 1, max(left_dia, right_dia));
        return max(left_height, right_height) + 1;
    }
};

Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int size = nums.size();
        int sum = 0, maxSum = nums[0];
        for (int i = 0; i < size; i++) {
            if (sum < 0) {
                sum = nums[i];
            } else {
                sum += nums[i];
            }
            maxSum = max(maxSum, sum);
        }
        return maxSum;
    }
};