My solution using c, Memory Limit Exceeded, anyone helps?


  • 0
    T

    my idea is using linklist to store the start of Repeated DNA Sequences. I use linklist because i donnot konw outputSize until i scan the input to the end. After scanning, I malloc memory for output and free memory for linklist, but the memory limit exceed. any one helps?

    #define TARGETLENGTH 10
    
    //store start of substring in linklist
    struct strLinkList
    {
    	char *s;
    	struct strLinkList * next;
    };
    
    char **findRepeatedDnaSequences(char *input, int *outputSize) {
    	*outputSize = 0;
    	char ** ret = NULL;
    	int slen = strlen(input);
    	if( strlen(input) <= TARGETLENGTH)
    		return NULL;
    
    	int hash[26] = {0};
    	hash['A'-'A']=0;
    	hash['C'-'A']=1;
    	hash['G'-'A']=2;
    	hash['T'-'A']=3;
    	int hashValue = 0;
    	//int freq[1048576];
    	int *freq = (int *)malloc(sizeof(int)*1048576);
    	for (int i = 0; i < 1048576; i++)
    	{
    		freq[i] = 0;
    	}
    	struct strLinkList * head = (struct strLinkList *)malloc(sizeof(struct strLinkList));
    	head->next = NULL;
    	struct strLinkList * end = head;
    	for (int i = 0; i < TARGETLENGTH; i++)
    		hashValue = (hashValue << 2) |(hash[*input++ - 'A']);
    	freq[hashValue]++;
    
    	char * s = NULL;
    	while (*input)
    	{
    		hashValue = ((hashValue<<2) &0xFFFFF) | (hash[*input-'A']);
    		freq[hashValue]++;
    		if (freq[hashValue]==2)
    		{
    			//store start of the subString in tempNode
    			(*outputSize)++;
    			struct strLinkList * tempNode = (struct strLinkList*)malloc(sizeof(struct strLinkList));
    			tempNode->next = NULL;
    			tempNode->s = input-TARGETLENGTH + 1;
    			end->next = tempNode;
    			end = end->next;
    		}
    		input++;
    	}
    	end = head;
    	head = head->next;
    	free(end);
    	ret = (char**)malloc(*outputSize * sizeof(char*));
    	char ** temp= ret;
    	while (head)
    	{
    		//malloc memory for substring and free memory of node
    		s = (char *) malloc(sizeof(char) * (TARGETLENGTH+1));
    		strncpy(s,head->s,TARGETLENGTH);
    		s[TARGETLENGTH]= '\0';
    		*temp++ = s;
    		end = head;
    		head = head->next;
    		free(end);
    	}
    	return ret;
    }

  • 0
    D

    I'm not expert in C/C++, but from your code I see the following. Instead of int freq[], try something like byte freq[], and stop incrementing it, when value of freq[hash] > 1. This will decrease memory usage of you program by factor of 4.
    Hope that helps


  • 0
    Y

    i have the same case as you.but i see the other's code which use int map[1024*1024].
    i only use char map[1024][1024] which is MLE..i can't figure it out.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.