Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        int ans;
        stack<int> st;
       
        for (int i = 0; i < tokens.size(); i++) {
            if (tokens[i] != "+" && tokens[i] != "-" &&
                tokens[i] != "*" && tokens[i] != "/") {
                st.push(stoi(tokens[i]));
            } else {
                if (st.size() < 2) {
                    return -1;
                }
                int first = st.top(); st.pop();
                int second = st.top(); st.pop();
                int new_val;
                if (tokens[i] == "+") {
                    new_val = first + second;
                } else if  (tokens[i] == "-") {
                    new_val = second - first;
                } else if (tokens[i] == "*") {
                    new_val = first * second;
                } else {
                    new_val = second / first;
                }
                st.push(new_val);
            }
        }
        ans = st.top(); st.pop();
        return ans;
    }
};

Edit Distance

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

1. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dict(wordList.begin(), wordList.end());
        queue<pair<string, int> > q;
        q.push(make_pair(beginWord, 1));

        while (!q.empty()) {
            pair<string, int> poped = q.front(); q.pop();
            if (poped.first == endWord) {
                return poped.second;
            } else {
                string poped_str = poped.first;
                for (int i = 0; i < poped_str.size(); i++) {
                    for (char ch = 'a'; ch <= 'z'; ch++) {
                        if (poped_str[i] != ch) {
                            char temp = poped_str[i];
                            poped_str[i] = ch;
                            if (dict.count(poped_str)) {
                                q.push(make_pair(poped_str, poped.second + 1));
                                dict.erase(poped_str);
                            }
                            poped_str[i] = temp;
                        }
                    }
                }
            }
        }
        return 0;
    }
};

Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:

[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

 

class Solution {

public:

    void permute(vector<int> num, int st, int end,

                 vector<vector<int> >& ans) {

        if (st == end) {

            ans.push_back(num);

        } else {

            for (int i = st; i < end; i++) {

                // Continue if num[i] exists b/w indexes [st, i].

                int iter_back = i - 1;

                bool exists = false;

                while (iter_back >= st) {

                    if (num[iter_back] == num[i]) {

                        exists = true;

                        break;

                    }

                    iter_back--;

                }

                if (exists == true) {

                    continue;

                }

                iter_swap(num.begin() + st, num.begin() + i);

                permute(num, st + 1, end, ans);

                iter_swap(num.begin() + i, num.begin() + st); 

            }

        }

    }

    vector<vector<int> > permuteUnique(vector<int> &num) {

        // Start typing your C/C++ solution below

        // DO NOT write int main() function

        vector<vector<int> > ans;

        if (num.size() == 0) {

            return ans;

        }

        permute(num, 0, num.size(), ans);

        return ans;

    }

};

Search for a range

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

class Solution {
public:
    int leftMost(vector<int>& nums, int target) {       
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left)/2;
            if (nums[mid] == target) {
                if (mid == left || nums[mid] != nums[mid - 1]) {
                    return mid;
                } else {
                    right = mid - 1;
                }
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
   
    int rightMost(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left)/2;
            if (nums[mid] == target) {
                if (mid == right || nums[mid] != nums[mid + 1]) {
                    return mid;
                } else {
                    left = mid + 1;
                }
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
   
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> ans;
        ans.push_back(leftMost(nums, target));
        ans.push_back(rightMost(nums, target));
        return ans;
    }
};