leetcode解题: 132 Pattern (456)

发表于 2017-02-04 | 分类于刷题总结

Given a sequence of n integers a1, a2, …, an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.

Note: n will be less than 15,000.

Example 1:

Input: [1, 2, 3, 4]
Output: False
Explanation: There is no 132 pattern in the sequence.

Example 2:

Input: [3, 1, 4, 2]
Output: True
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Example 3:

Input: [-1, 3, 2, 0]
Output: True
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

解法1： O(N) Time

参考了discussion的解答, 基本思想是我们从后往前扫描. 用一个stack维护一个递增的序列, stack中的值则是s2的备选. 每当扫描一个新数时,先比较是否比s3小,如果比s3小则说明已找到答案.如果比s3大则更新s3和s2的值.
更新的时候: 把stack中所有比当前值小的数弹出, 每一个弹出的数都是s3的备选.
C++

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        
        int s3 = INT_MIN;
        stack<int> s2;
        for (int i = nums.size() - 1; i >= 0; --i) {
            if (nums[i] < s3) {
                return true;   
            }
            
            while (!s2.empty() && s2.top() < nums[i]) {
                s3 = s2.top(); s2.pop();
            }
            s2.push(nums[i]);
        }
        return false;
    }
};

Java

leetcode解题: Remove K Digits (402)

发表于 2017-02-04 | 分类于刷题总结

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note:
The length of num is less than 10002 and will be ≥ k.
The given num does not contain any leading zero.
Example 1:

1
2
3

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

1
2
3

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

1
2
3

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

解法1：贪心算法

这题用贪心的算法, 观察可以发现如果每次remove的时候满足if (num[i] > num[i + 1]), 那么得到的数一定是最小的.
这里可以用一个string来存储当前扫描的结果,如果发现现在的字符比string的最后一个字符小,那么就把string的最后一个字符去掉. (目的是维护一个递增的数列)
最后呢,我们只需要去前num.size() - k个数即可.要注意的是因为每次去除数字的时候k数会变,所以一开始需要用一个变量存储初值.
最后返回的时候要去掉leading zero.
C++

class Solution {
public:
    string removeKdigits(string num, int k) {
        if (k >= num.size()) {
            return "0";
        }
        string res = "";
        int n = k;
        
        for (auto ch : num) {
            while (!res.empty() && res.back() > ch && k > 0) {
                k--;
                res.pop_back();
            }
            res.push_back(ch);
        }
        
        int start = 0;
        while (res[start] == '0') {start++;}
        
        // Take first num.size() - k elements
        
        if (start >= res.size()) {
            return "0";
        } else {
            return res.substr(start, min(start + num.size() - n, res.size()));
        }
        
    }
};

Java

leetcode解题: Simplify Path (71)

发表于 2017-02-04 | 分类于刷题总结

Total Accepted: 74685
Total Submissions: 309287
Difficulty: Medium
Contributors: Admin
Given an absolute path for a file (Unix-style), simplify it.

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

Corner Cases:
Did you consider the case where path = "/../"?
In this case, you should return "/".
Another corner case is the path might contain multiple slashes ‘/‘ together, such as "/home//foo/".
In this case, you should ignore redundant slashes and return "/home/foo".

解法1： Stack

比较清楚的思路是, 用一个stack来存储每一级的path, 如果遇到”.”则跳过,如果遇到”..”表明要前进一级, 那就把当前的栈顶的path弹出
最后栈就是存放的reverse过的path,一个个把他们串起来就可以了.
C++

class Solution {
public:
	string simplifyPath(string path) {
		stack<string> items;
		string item = "";
		stringstream ss(path);
		while(getline(ss, item, '/')) {
			if (item.size() == 0 || item == ".") {
				continue;
			} else if (item == "..") {
				if (!items.empty()) {
					items.pop();
				}
			} else {
				items.push(item);
			}
		}
		string res = "";
		while (!items.empty()) {
			res += "/" + items.top() + res;
		}
		return res.empty() ? "/" : res;
	}
};

也可以用一个deque来解决，这样在结束了之后不需要reverse stack里的结果。

class Solution {
    public String simplifyPath(String path) {
        Deque<String> deque = new LinkedList<String>();
        String[] comps = path.split("/");
        for (String comp : comps) {
            if (comp.equals("..")) {
                deque.pollLast();
            } else if (comp.equals(".") || comp.equals("")) {
                continue;
            } else {
                deque.offerLast(comp);
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!deque.isEmpty()) {
            sb.append("/" + deque.pollFirst());
        }
        return sb.length() == 0 ? "/" : sb.toString();
    }
}

leetcode解题: Decode String (394)

发表于 2017-02-04 | 分类于刷题总结

Given an encoded string, return it’s decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].

Examples:

1
2
3

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

解法1：递归

主要的想法就是，每一个数字后面一定跟着一个左括号。而左括号里面的东西是另外一个decode的过程，一个decode结束的标志是要么string结束了，或者是遇到了右括号（[),
要注意的是,为了要不停的往前扫描,我们在递归函数返回的时候需要记录当前扫描到的位置. 可以用辅助class解决,在c++里也可以用引用解决这个问题.
C++

class Solution {
public:
	string decodeString(string s) {
		int pos = 0;
		string res = decode(s, pos);
		return res;
	}
	string decode(string s, int& pos) {
		string res = "";
		while (pos < s.size() && s[pos] != ']') {
			if (!isdigit(s[pos])) {
				res += s[pos];
			} else {
				int start = pos;
				while (pos < s.size() && isdigit(s[pos])) {
					pos++;
				}
				int number = stoi(s.substr(start, pos));
				pos++;	// skip the [
				string next = decode(s, pos);
				pos++;	// since decode stops at ] or at the end of string, we need to skip ]
				for (int i = 0; i < number; ++i) {
					res += next;
				}
			}
		}
		return res;
	}	 
};

Java

解法2: Stack

用递归的算法如果要用iteration的办法解决一般会用到Stack. 基本的思路是用两个stack分别记录数字和字符, 当遇到”]”时使用当前栈顶的字母和数字来进行decode, 然后decode的结果要存入字母的栈顶.
最后的结果要么是当前的字符串, 要么是栈顶的字符串.
C++

lang: cpp

class Solution {
public:
	string decodeString(string s) {
		stack<int> numbers;
		stack<string> decoded;
		string t;	// 记录在遇到"["之前的string
		int number = 0;	
		for (int i = 0; i < s.size(); ++i) {
			if (isdigit(s[i])) {
				number = number * 10 + s[i] - '0';
			} else if (s[i] == '[') {
				numbers.push(number);
				number = 0;
				decoded.push(t);	// 把当前所记录到的string存入栈中
				t = "";
			} else if (s[i] == ']') {
				int rep = numbers.top();
				numbers.pop();
				for (int j = 0; j < rep; ++j) {
					decoded.top() += t;	// t记录了当前扫描到还没有decode的string
				}
				t = decoded.top();	
				decoded.pop();	
			} else {
				t += s[i];
			}
		}
		return decoded.empty()? t : decoded.top();
	}
};

leetcode解题: Mini Parser (385)

发表于 2017-01-26 | 分类于刷题总结

Given a nested list of integers represented as a string, implement a parser to deserialize it.

Each element is either an integer, or a list – whose elements may also be integers or other lists.

Note: You may assume that the string is well-formed:

String is non-empty.
String does not contain white spaces.
String contains only digits 0-9, [, - ,, ].
Example 1:

1
2
3

Given s = "324",
You should return a NestedInteger object which contains a single integer 324.

Example 2:

Given s = "[123,[456,[789]]]",
Return a NestedInteger object containing a nested list with 2 elements:
1. An integer containing value 123.
2. A nested list containing two elements:
    i.  An integer containing value 456.
    ii. A nested list with one element:
         a. An integer containing value 789.

解法1： Iterative

这题自己写的stack版本怎么也过不了OJ，参考了这篇帖子的解法
C++

class Solution {
public:
    NestedInteger deserialize(string s) {
        if (s.empty()) return NestedInteger();
        if (s[0] != '[') return NestedInteger(stoi(s));
        stack<NestedInteger> st;
        int start = 1;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '[') {
                st.push(NestedInteger());
                start = i + 1;
            } else if (s[i] == ',' || s[i] == ']') {
                if (i > start) {
                    st.top().add(NestedInteger(stoi(s.substr(start, i - start))));
                }
                start = i + 1;
                if (s[i] == ']') {
                    if (st.size() > 1) {
                        NestedInteger t = st.top(); st.pop();
                        st.top().add(t);
                    }
                }
            }
        }
        return st.top();
    }
};

Java

leetcode解题: Flatten Nested List Iterator (341)

发表于 2017-01-23 | 分类于刷题总结

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list – whose elements may also be integers or other lists.

Example 1:
Given the list [[1,1],2,[1,1]],

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

Example 2:
Given the list [1,[4,[6]]],

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

解法1： Stack， O(N) Time, O(N) Space, N is the number of total items

这题是用iteration的办法解决递归的问题，一般此类问题容易想到用stack解决。这题哪里可以用stack呢？每一个nestedInteger都可能是一个list of nestedInteger，那么我们对于每一个元素，如果是单数，则任务完成，如果是一个list，那么我们把所有的元素都推入栈中，直到第一个元素是单数或者到遍历结束为止。由于栈是FILO, 所以每次推入的时候需要从后往前推。

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   public:
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     bool isInteger() const;
 *
 *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 *     // The result is undefined if this NestedInteger holds a nested list
 *     int getInteger() const;
 *
 *     // Return the nested list that this NestedInteger holds, if it holds a nested list
 *     // The result is undefined if this NestedInteger holds a single integer
 *     const vector<NestedInteger> &getList() const;
 * };
 */
class NestedIterator {
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        for (int i = nestedList.size() - 1; i >= 0; --i) {
            s.push(nestedList[i]);
        }
    }
    int next() {
        int res = s.top().getInteger();
        s.pop();
        return res;
    }
    bool hasNext() {
        while (!s.empty()) {
            if (s.top().isInteger()) {
                return true;
            }
            vector<NestedInteger> cur = s.top().getList();
            s.pop();
            for (int i = cur.size() - 1; i >= 0; --i) {
                s.push(cur[i]);
            }
        }
        return false;
    }
private:
    stack<NestedInteger> s;
};
/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i(nestedList);
 * while (i.hasNext()) cout << i.next();
 */

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
public class NestedIterator implements Iterator<Integer> {
    Stack<NestedInteger> stack;
    public NestedIterator(List<NestedInteger> nestedList) {
        stack = new Stack<NestedInteger>();
        for (int i = nestedList.size() - 1; i >= 0; i--) {
            stack.push(nestedList.get(i));
        }
    }
    @Override
    public Integer next() {
        int res = stack.pop().getInteger();
        return res;        
    }
    @Override
    public boolean hasNext() {
        while (!stack.isEmpty()) {
            if (stack.peek().isInteger()) {
                return true;
            }
            NestedInteger top = stack.pop();
            List<NestedInteger> list = top.getList();
            for (int i = list.size() - 1; i >= 0; i--) {
                stack.push(list.get(i));
            }
        }
        return false;
    }
}
/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i = new NestedIterator(nestedList);
 * while (i.hasNext()) v[f()] = i.next();
 */

leetcode解题: Letter Combinations of a Phone Number (17)

发表于 2017-01-23 | 分类于刷题总结

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.

1 2	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.

解法1：

先建一个map来存储每一个字母可以映射的字母，然后就是常规的backtracking的解法。没有特殊的地方。
C++

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        unordered_map<char, vector<char>> map;
        map['2'] = vector<char> {'a','b','c'};
        map['3'] = vector<char> {'d','e','f'};
        map['4'] = vector<char> {'g','h','i'};
        map['5'] = vector<char> {'j','k','l'};
        map['6'] = vector<char> {'m','n','o'};
        map['7'] = vector<char> {'p','q','r','s'};
        map['8'] = vector<char> {'t','u','v'};
        map['9'] = vector<char> {'w','x','y','z'};
        
        vector<string> res;
        string cur = "";
        if (digits.size() == 0) {
            return res;
        }
        helper(digits, 0, cur, res, map);
        return res;
        
        
    }
    
    void helper(string digits, int pos, string cur, vector<string>& res, unordered_map<char, vector<char>>& map) {
        if (cur.size() == digits.size()) {
            res.push_back(cur);
            return;
        }
        
        for (int i = pos; i < digits.size(); ++i) {
            char digit = digits[i];
            if (!map.count(digit)) {
                continue;
            } else {
                vector<char> dict = map[digit];
                for (int j = 0; j < dict.size(); ++j) {
                    string temp = cur + dict[j];
                    helper(digits, i + 1, temp, res, map);
                }
            }
        }
    }
};

Java

leetcode解题: Permutation II (47)

发表于 2017-01-21 | 分类于刷题总结

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]
]

解法1： O(n!)

主要是理解在递归的过程中，怎么算一个重复的数字。这里重复是指如果当前数和前一个数相同（排序后），并且前面一个数还没有被使用过的情况下，那么这个数算重复了（因为可能的答案已经被从前一个数字出发的递归中概括了）。
C++

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        if (nums.empty()) {
            return res;
        }
        
        vector<int> cur;
        vector<bool> visited (nums.size(), false);
        std::sort(nums.begin(), nums.end());
        helper(nums, visited, cur, res);
        return res;
    }
    
    void helper(vector<int>& nums, vector<bool>& visited, vector<int>& cur, vector<vector<int>>& res) {
        
        if (cur.size() == nums.size()) {
            res.push_back(cur);
            return;
        }
        
        for (int i = 0; i < nums.size(); ++i) {
            if (visited[i]) continue;
            if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) continue;
            cur.push_back(nums[i]);
            visited[i] = true;
            helper(nums, visited, cur, res);
            cur.pop_back();
            visited[i] = false;
            }
        return;
        }
};

Java

leetcode解题: Permutations (46)

发表于 2017-01-21 | 分类于刷题总结

Given a collection of distinct numbers, return all possible permutations.

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

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

解法1： O(n!)

也是经典的backtracking的问题，对于这种permutation的问题，要维护一个visited数组来记录每一个元素是否被选取了，因为这里每次都是从头开始扫描。递归终止的条件是当选取的答案的长度和原数组的长度一致的时候就说明一个permutation已经完成。
因为有n!个组合，每一个组合访问一次，总的复杂度是O（n!).
C++

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        if (nums.empty()) {
            return res;
        }
        
        vector<bool> visited (nums.size(), false);
        vector<int> cur;
        helper(nums, visited, cur, res);
        return res;
    }
    
    void helper(vector<int>& nums, vector<bool>& visited, vector<int>& cur, vector<vector<int>>& res) {
        
        if (cur.size() == nums.size()) {
            res.push_back(cur);
            return;
        }
        
        for (int i = 0; i < nums.size(); ++i) {
            if (!visited[i]) {
                cur.push_back(nums[i]);
                visited[i] = true;
                helper(nums, visited, cur, res);
                cur.pop_back();
                visited[i] = false;
            }
        }
        return;
        
    }
};

Java

leetcode解题: Combination Sum II (40)

发表于 2017-01-21 | 分类于刷题总结

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

解法1：

这题和Combination Sum的唯一区别是每一个数字只能使用一次，那么每一次挑选的时候无论是否有解都往前进一格就可以了。
C++

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    vector<vector<int>> res;
    vector<int> current;
    sort(candidates.begin(),candidates.end());
    backTracking(candidates.begin(),current,res,candidates,target);
    return res;
}
void backTracking(vector<int>::iterator n, vector<int>& current,vector<vector<int>>& res, const vector<int>& candidates, int target){
    if(!target) res.push_back(current);
    else if(target>0){
        for(;n!=candidates.end()&&*n<=target;++n){
            current.push_back(*n);
            backTracking(n+1,current,res,candidates,target-*n);
            current.pop_back();
            while(n+1!=candidates.end()&&*(n+1)==*n) ++n;
        }
    }
}
};

Java

解法1： O(N) Time

解法1： 贪心算法

解法1： Stack

解法1： 递归

解法2: Stack

解法1： Iterative

解法1： Stack， O(N) Time, O(N) Space, N is the number of total items

解法1：

解法1： O(n!)

解法1： O(n!)

解法1：

解法1：贪心算法

解法1：递归