[LeetCode] Repeated DNA Sequences

2016-01-17

Analysis:

If we use the string sequence as the hash map’s key, then the space limitation will be exceeded. Therefore we should use the bit to represent the genome elements and the bit mask as well.

Time Complexity:

O(n)

Space Complexity：

O(n)

Code

class Solution(object):
    def findRepeatedDnaSequences(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        retStr = []
        mapcnt = dict()

        mapdict = {'A':0, 'C':1, 'G':2, 'T':3}

        sum = 0
        for n in xrange(0, len(s)):
        	sum = (4*sum + mapdict[s[n]]) & 0xFFFFF
        	if n < 9:
        		continue
        	mapcnt[sum] = mapcnt.get(sum, 0) + 1
        	if mapcnt[sum] == 2:
        		retStr.append(s[n-9:n+1])

        return retStr

展开全文 >>

[LeetCode] H-Index II

2016-01-15

Analysis:

Since the array has already been sorted, we can use binary search to find the pivot point

Time Complexity:

O(logn)

Space Complexity：

O(1)

Code

class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        l, r = 0, len(citations)-1
        length = len(citations)-1
        while l <= r:
            mid = l + (r-l)/2
            idx = length-mid
            if citations[mid] >= idx+1:
                r = mid-1
            else:
                l = mid+1
        return length-l+1

展开全文 >>

[LeetCode] H-Index

2016-01-14

Analysis:

Sort it first, then you can find the index when citation[idx] >= idx+1

Time Complexity:

O(nlogn)

Space Complexity：

O(1)

Code

class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        citations.sort(reverse = True)
        idx = 0

        for x in xrange(len(citations)):
            if citations[x] >= x+1:
                idx += 1
        return idx

展开全文 >>

atoi implementation

2015-12-06

需要注意的地方

1、检查字符串是否为空
2、对非法输入，返回0，并设置全局变量
3、溢出
4、空字符串””
输入字符串只有”+”或”-“号

long long StrToIntCore(const char* str, bool minus);

enum Status {kValid = 0, kInvalid};
int g_nStatus = kValid;

int StrToInt(const char* str)
{
    g_nStatus = kInvalid;
    long long num = 0;

    if(str != NULL && *str != '\0') 
    {
        bool minus = false;
        if(*str == '+')
            str ++;
        else if(*str == '-') 
        {
            str ++;
            minus = true;
        }

        if(*str != '\0') 
        {
            num = StrToIntCore(str, minus);
        }
    }

    return (int)num;
}

long long StrToIntCore(const char* digit, bool minus)
{
    long long num = 0;

    while(*digit != '\0') 
    {
        if(*digit >= '0' && *digit <= '9') 
        {
            int flag = minus ? -1 : 1;
            num = num * 10 + flag * (*digit - '0');

            if((!minus && num > 0x7FFFFFFF) 
                || (minus && num < (signed int)0x80000000))
            {
                num = 0;
                break;
            }

            digit++;
        }
        else 
        {
            num = 0;
            break;
        }
    }

    if(*digit == '\0') 
    {
        g_nStatus = kValid;
    }

    return num;
}

展开全文 >>

[Leetcode] Minimum Height Trees

2015-11-30

For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Example 1:

Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]

return [1]

Example 2:

Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

return [3, 4]

Analysis:

The first thought is permuting the whole graph and depth first traversal them. But exceeding the time limit.

The second solution is from other guys (http://bookshadow.com/weblog/2015/11/26/leetcode-minimum-height-trees/), very elegant.

Its thought is to eliminate the leaves and remove the edge connected to leaves and add the newly leaves to a list. Finally the remaining node is the roots we want which are less or equal to two.

Solution 1

Time Complexity:

O(n^2)

class VertexNode {  
public:  
     VertexNode(int num) : label(num) {};  
     int label;  
     vector<int> edges;  
};  
class Solution {  
public:  
     void buildAdjcentList(vector<pair<int, int>>& edges, unordered_map<int, VertexNode*> & adjList)  
     {  
          for (pair<int, int> p : edges)  
          {  
               VertexNode * newnode1, *newnode2;  
               if (adjList.find(p.first) == adjList.end())  
               {  
                    newnode1 = new VertexNode(p.first);  
                    adjList[p.first] = newnode1;  
               }  
               else  
               {  
                    newnode1 = adjList[p.first];  
               }  
               if (adjList.find(p.second) == adjList.end())  
               {  
                    newnode2 = new VertexNode(p.second);  
                    adjList[p.second] = newnode2;  
               }  
               else  
               {  
                    newnode2 = adjList[p.second];  
               }  
               newnode1->edges.push_back(newnode2->label);  
               newnode2->edges.push_back(newnode1->label);  
          }  
     }  
     void DFSMHT(unordered_map<int, VertexNode*> & adjList, int curlabel, int prevlabel, int depth, int & minDepth)  
     {  
          VertexNode * curNode = adjList[curlabel];  
          if (!curNode) return;  
          if (curNode->edges.size() == 1 && curNode->edges[0] == prevlabel)  
          {  
               if (minDepth > depth)  
               {  
                    minDepth = depth;  
               }  
               return;  
          }  
          for (int i : curNode->edges)  
          {  
            if (i == prevlabel) continue;  
               DFSMHT(adjList, i, curNode->label, depth+1, minDepth);  
          }  
     }  
  vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {  
       unordered_map<int, VertexNode*> adjList;  
       buildAdjcentList(edges, adjList);  
       int minDepth = INT_MAX;  
       int curdepth = INT_MAX;  
       vector<int> retList;  
       for (pair<int, VertexNode*> it : adjList)  
       {  
            DFSMHT(adjList, it.second->label, -1, 1, curdepth);  
            if (curdepth <= minDepth)  
            {  
                 if (curdepth < minDepth)  
                      retList.clear();  
                 retList.push_back(it.second->label);  
                 minDepth = curdepth;  
            }  
            curdepth = INT_MAX;  
       }  
       return retList;  
  }  
};

Solution 2

Time Complexity:

O(n)

class Solution(object):
    def findMinHeightTrees(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        children = collections.defaultdict(set)
        for x, y in edges:
        	children[x].add(y)
        	children[y].add(x)

        vertices = set(children.keys())

        while len(vertices) > 2:
        	leaves = [x for x in children if len(children[x]) == 1]
        	for x in leaves:
        		for y in children[x]:
        			children[y].remove(x)
        		del children[x]
        		vertices.remove(x)

        return list(vertices) if n != 1 else [0]

展开全文 >>