Any one can help,passed in VS but failed in OJ?


  • 0
    Q
       bool compareStr(string str1, string str2)
        {
        
        	int len1 = str1.length();
        	int len2 = str2.length();
        
        	if (len1 <= len2)
        	{
        		for (size_t i = 0; i < len1;++i)
        		{
        			if (str1[i] < str2[i])
        				return false;
        		}
        	}
        	else
        	{
        		for (size_t i = 0; i < len2; ++i)
        		{
        			if (str1[i] < str2[i])
        				return false;
        		}
        	}
        
        	return true;
        }
        
        string largestNumber(vector<int> &num) {
        
        	if (num.empty())
        		return NULL;
        
        	int size = num.size();
        	string *num_string = new string[size];
        	string result;
        
        
        	// convert int to string 
        	for (size_t i = 0; i < size; ++i)
        	{
        		char temp[10];
        		sprintf_s(temp, "%d", num[i]);
        		num_string[i] = temp;
        		
        	}
        
        	for (size_t i = 0; i < size; ++i)
        	{
            
        		string max = num_string[i];
        		for (size_t j = i + 1; j < size;++j)
        		{
        			if (!compareStr(max, num_string[j]))
        			{
        				num_string[i] = num_string[j];
        				num_string[j] = max;
        				max = num_string[i];
        			}
        		}
        		result.append(max);
        	}
        
        	if (result.front() == '0')
        		return "0";
        
        	return result;
        }
    
    
    failed on test case {123,321},but seems VS returns the right result?

  • 0
    Q

    well ,it seems my sort algorithm has some problems , for example {12, 129} will return 12129 and it is wrong!


  • 0
    Q

    finnaly I edit my sort algorithm like this, but it costs 40ms ,not a good answer ,if any one can improve the efficiency,please help!
    bool compareStr(string str1, string str2)
    {
    string str1_str2 = str1 + str2;
    string str2_str1 = str2 + str1;

    int len = str1_str2.length();
    size_t i = 0;
    while (i < len)
    {
    	if (str1_str2[i] < str2_str1[i])
    		return false;
    	else if (str1_str2[i] > str2_str1[i])
    		return true;
    	++i;
    }
    return true;
    

    }


  • 0
    Q

    In the end I use C char*, it is faster than C++ string.

    bool compareStr(const char* str1, const char* str2)
    {

    int len = sizeof(str1) + sizeof(str2) + 1;
    char* str1_str2 = new char[len];
    char* str2_str1 = new char[len];
    
    strcpy(str1_str2, str1);
    strcat(str1_str2, str2);
    
    strcpy(str2_str1, str2);
    strcat(str2_str1, str1);
    
    size_t i = 0;
    while (i < len)
    {
    	if (str1_str2[i] < str2_str1[i])
    		return false;
    	else if (str1_str2[i] > str2_str1[i])
    		return true;
    	++i;
    }
    return true;
    

    }

    string largestNumber(vector<int> &num)
    {

    if (num.empty())
    	return NULL;
    
    int size = num.size();
    char **num_string = new char*[size];
    string result;
    
    
    // convert int to string 
    for (size_t i = 0; i < size; ++i)
    {
    	num_string[i] = new char[11];
    	sprintf(num_string[i], "%d", num[i]);
    }
    
    size_t max_index;
    for (size_t i = 0; i < size; ++i)
    {
    	char* max = num_string[i];
    	max_index = i;
    	for (size_t j = i + 1; j < size;++j)
    	{
    		if (!compareStr(max, num_string[j]))
    		{
    			max = num_string[j];
    			max_index = j;
    		}
    	}
    	num_string[max_index] = num_string[i];
    	num_string[i] = max;
    
    	result.append(max);
    }
    
        // clean memory
        for (size_t i = 0; i < size; ++i)
    	delete[] num_string[i];
    
    delete[] num_string;
    if (result.front() == '0')
    	return "0";
    
    return result;
    

    }

    Welcome any good idea!


Log in to reply
 

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