Largest Odd Number in String[E,Math,String,Greedy]

https://leetcode.com/problems/largest-odd-number-in-string/description/

You are given a string num, representing a large integer. Return the largest-valued odd integer (as a string) that is a non-empty substring of num, or an empty string "" if no odd integer exists.

A substring is a contiguous sequence of characters within a string.

 

Example 1:

Input: num = "52"
Output: "5"
Explanation: The only non-empty substrings are "5", "2", and "52". "5" is the only odd number.

Example 2:

Input: num = "4206"
Output: ""
Explanation: There are no odd numbers in "4206".

Example 3:

Input: num = "35427"
Output: "35427"
Explanation: "35427" is already an odd number.

 

Constraints:

• 1 <= num.length <= 105
• num only consists of digits and does not contain any leading zeros.

1. Python

 

나의 풀이..! 단순하게 밖에 생각이 안 난다.

class Solution:
    def largestOddNumber(self, num: str) -> str:
        idx = -1
        for i in range(len(num)):
            if int(num[i]) % 2 == 1 :
                idx = i
        if idx == -1 : return ""
        return num[:idx+1]

 

2. C

 

단순 풀이!

포인터를 써줄 떄는 무조건 malloc을 해주고, 특히 이놈이 string 일 때는 끝에 \0을 만들어 줘야 한다.

그리고 malloc 할 때도 무조건 크게 크게 메모리 잡지 말고 적정값을 잡아야 헌다..

 

그리고!! C에선 char을 숫자로 할 때 Char-'0' 이렇게 꼼수를 쓴다!

char* largestOddNumber(char* num) {
    int n = strlen(num);
    int idx = -1;

    for(int i=0;i<n;i++){
        if((num[i]-'0') % 2 == 1) idx=i;
    }
    if(idx!=-1){
        char* ans = (char*)malloc((idx+2)*sizeof(char));
        for(int j=0;j<=idx;j++){
            ans[j] = num[j];
        }
        ans[idx+1] = '\0';
        return ans;
    }else{
        char* a = (char*)malloc(2*sizeof(char));
        a[0] = '\0';
        return a;
    }
}

 

사실 이게, 제일 후방부 홀수를 찾는 문제라고 여겨지기에,

idx를 뒤에서부터 찾으면 Search 속도를 더 올릴 수 있다.

char* largestOddNumber(char* num) {
    int n = strlen(num);
    int idx = -1;

    for(int i=n-1;i>-1;i--){
        if((num[i]-'0') % 2 == 1){
            idx=i;
            break;}
    }

    if(idx!=-1){
        char* ans = (char*)malloc((n+1)*sizeof(char));
        for(int j=0;j<=idx;j++){
            ans[j] = num[j];
        }
        ans[idx+1] = '\0';
        return ans;
    }else{
        char* a = (char*)malloc(2*sizeof(char));
        a[0] = '\0';
        return a;
    }
}

 

 

3. C++

string.substr(start idx, end idx) 요렇게 string을 쪼개버릴 수 있네.

 

그리고 return을 꼭 variable로 하지 않아도 된다.

class Solution {
public:
    string largestOddNumber(string num) {
        int n = num.length();
        int idx = -1;
        // string ans;

        for(int i = n-1 ; i>-1; i--){
            if((num[i]-'0')%2 == 1){
                idx = i;
                break;
            }
        }
        if(idx == -1){
            // ans = "";
            return "";
        }
        else{
            // for(int j=0;j<=idx;j++){
            //     ans[j] = num[j];
            // }
            return num.substr(0,idx+1);
        }
    }
};

 

굳이 string을 하나 더 만들어서 answer로 반환하고 싶으면

아래와 같이 하면 된다.

 

string 선언 할때, string ans(크기(idx+1), ' '(초기값 아무 characher)) 이렇게 해야 한다.

 

그냥 string ans; 이렇게 하면 공간이 0인 친구가 나와서 ans[0] 이렇게 index를 이용할 수가 없다.

 

그냥 string ans; 는 ans ="askd jslkd jlaskd j" 이렇게 한 번에 집어넣는 것은 가능!

class Solution {
public:
    string largestOddNumber(string num) {
        int n = num.length();
        int idx = -1;

        for(int i = n-1 ; i>-1; i--){
            if((num[i]-'0')%2 == 1){
                idx = i;
                break;
            }
        }
        if(idx == -1){
            return "";
        }
        else{
            string ans(idx+1,'\0');
            for(int j=0;j<=idx;j++){
                ans[j] = num[j];
            }
            return ans;
        }
    }
};