Tuesday, March 31, 2015

LeetCode [31] Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place and use only constant extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1





 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        if(n<=1) return;

        //find the first decreasing position from the end;
        int i=n-2;
        while(i>=0 && nums[i]>=nums[i+1]) i--;
        
        //this is the greatest number. return the smallest number;
        if(i<0)
        {
            sort(nums.begin(), nums.end());
            return;
        }

        //find the smallest number (from the end) greater than nums[i]
        int j=n-1;
        while(j>i && nums[j]<=nums[i]) j--;
        swap(nums[i], nums[j]);
        sort(nums.begin()+i+1, nums.end());
    }
};


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;

        int i = n-2;
        for(; i>=0; --i){
            if(nums[i]<nums[i+1]) break;
        }
        
        if(i<0){
            Arrays.sort(nums);
            return;
        }
        
        int j = n-1;
        for(; j>i; --j){
            if(nums[j]>nums[i]) break;
        }
        
        //swap i and j
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
        Arrays.sort(nums,i+1,n);
    }
}
Posted by at No comments:
Labels: , , ,

LeetCode [28] Implement strStr()

Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = "hello", needle = "ll"
Output: 2
Example 2:
Input: haystack = "aaaaa", needle = "bba"
Output: -1
Clarification:
What should we return when needle is an empty string? This is a great question to ask during an interview.
For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    int strStr(string haystack, string needle) {
        if(haystack==needle) return 0;
        int szh = haystack.size();
        int szn = needle.size();
        for(int i=0; i<szh; ++i){
            if(i+szn-1>=szh) break;
            if(haystack.substr(i, szn)==needle) return i;
        }
        return -1;
    }
};
Posted by at No comments:
Labels: , , ,

LeetCode [27] Remove Element

Ref
[1] https://leetcode.com/problems/remove-element/
OJ
Posted by at No comments:
Labels: , ,

LeetCode [26] Remove Duplicates from Sorted Array

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
Example 1:
Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

It doesn't matter what you leave beyond the returned length.
Example 2:
Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn't matter what values are set beyond the returned length.
Clarification:
Confused why the returned value is an integer but your answer is an array?
Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.
Internally you can think of this:
// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size(), i = 0, j = 0;
        while(j<n){
            while(j<n && i>0 && nums[j]==nums[i-1]) j++;
            if(j<n) nums[i++] = nums[j++];
        }
        return i;
    }
};
Posted by at No comments:
Labels: , ,

LeetCode [14] Longest Common Prefix

 14. Longest Common Prefix

Easy

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

 

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

 

Constraints:

  • 0 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] consists of only lower-case English letters.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    string longestCommonPrefix(vector<string> &strs) {
        int n = strs.size();
        if(n==0) return "";

        for(int index = 0; ;index++){
            if(strs[0].size()==index) return strs[0].substr(0,index);
            int c = strs[0][index];
            for(int i=1; i<n; ++i){
                if(strs[i].size()==index) return strs[0].substr(0,index);
                if(c!=strs[i][index]) return strs[0].substr(0,index);
            }
        }
        return strs[0];
    }
};


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string ret = "";
        int n = strs.size();
        if(!n) return ret;

        int index = 0;
        while(true){
            if(index>=strs[0].size()) return ret;
            char c = strs[0][index];
            for(int i=1; i<n; ++i){
                if(index>=strs[i].size() || c!=strs[i][index]) return ret;
            }
            ret += c;
            index++;
        }
    }
};


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public String longestCommonPrefix(String[] strs) {
        String r = "";
        if(strs.length==0) return r;
        int index = 0;
        while(true){
            char c = '.';
            for(String s : strs){
                if(index==s.length()) return r;
                else if(c!='.' && c!=s.charAt(index)) return r;
                else{
                    c = s.charAt(index);
                }
            }
            index++;
            r += c;
        }
    }
}
Posted by at No comments:
Labels: , ,

LeetCode [11] Container With Most Water

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49
Note: always skip the shorter line because we can't compose a larger container with narrower space.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int l = 0, r = n-1, res = 0;
        while(l<r){
            res = max(res, min(height[l], height[r])*(r-l));
            if(height[l]<=height[r]){
                l++;
            }else
                r--;
        }
        return res;
    }
};
Posted by at No comments:
Labels: , , ,

Monday, March 30, 2015

LeetCote [6] ZigZag Conversion


Ref
[1] https://leetcode.com/problems/zigzag-conversion/
OJ
Posted by at No comments:
Labels: , ,

Saturday, March 7, 2015

LeetCode [126] Word Ladder II

 126. Word Ladder II

Hard

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) 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.

Note:

  • Return an empty list if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
  • You may assume no duplicates in the word list.
  • You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

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

Output:
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]

Example 2:

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

Output: []

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dict(wordList.begin(), wordList.end());
        vector<vector<string>> ret;
        queue<vector<string>> que;
        int n = beginWord.size(), minLen = INT_MAX, curLevel = 1;
        que.push(vector<string>(1, beginWord));
        dict.erase(beginWord);
        unordered_set<string> usedWords;
        while(!que.empty()){
            vector<string> vec = que.front();
            que.pop();
            string s  = vec.back();
            int level = vec.size();
            if(level>curLevel){
                for(auto w:usedWords) dict.erase(w);
                usedWords.clear();
                curLevel = level;
            }
            if(level<=minLen){
                if(s==endWord){
                    ret.push_back(vec);
                    minLen = min(minLen, level);
                }else if(level<minLen){
                    for(int i=0; i<n; ++i){
                        for(char c='a'; c<='z'; ++c){
                            string ss = s;
                            ss[i] = c;
                            if(dict.count(ss)==1){
                                usedWords.insert(ss);
                                vec.push_back(ss);
                                que.push(vec);
                                vec.pop_back();
                            }
                        }
                    }
                }
            }
        }
        return ret;
    }
};
Posted by at No comments:
Labels:

Friday, March 6, 2015

LeetCode [127] Word Ladder

 127. Word Ladder

Medium

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:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
  • You may assume no duplicates in the word list.
  • You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

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

Output: 5

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

Example 2:

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

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//C++: 308ms
class Solution {
public:
    int ladderLength(string beginWord, string endWord, unordered_set<string>& wordDict) {
        queue<pair<string, int>> que;
        que.push(pair<string, int>(beginWord, 1));
        int n = beginWord.size();

        while(!que.empty()){
            string w = que.front().first;
            int cur_step = que.front().second;
            que.pop();
            for(int i=0; i<n; ++i){
                string ww = w;
                for(char c='a'; c<='z'; ++c){
                    ww[i] = c;
                    if(ww==endWord){
                        return cur_step+1;
                    }else if(wordDict.find(ww)!=wordDict.end()){
                        wordDict.erase(ww);
                        que.push(pair<string, int>(ww, cur_step+1));
                    }
                }
            }
        }
    }
};

//Java
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int sz = beginWord.length();
        Queue<String> que = new LinkedList<>();
        int step = 0;
        Set<String> dict = new HashSet<>();
        for (String w : wordList) dict.add(w);
        que.add(beginWord);
        dict.remove(beginWord);

        while (!que.isEmpty()) {
            int len = que.size();
            for (int k = 0; k < len; ++k) {
                String w = que.poll();
                if (w.equals(endWord)) return step + 1;
                for (int i = 0; i < sz; ++i) {
                    for (char c = 'a'; c <= 'z'; ++c) {
                        StringBuilder sb = new StringBuilder(w);
                        sb.setCharAt(i, c);
                        if (dict.contains(sb.toString())) {
                            que.add(sb.toString());
                            dict.remove(sb.toString());
                        }
                    }
                }
            }
            step++;
        }
        return 0;
    }
}
Posted by at No comments:
Labels:
Subscribe to: Posts (Atom)