Лицензийн түлхүүр форматлах Leetcode шийдэл


Хэцүү байдлын түвшин Easy
Байнга асуудаг Капитал Нэг Google-ийн
String StringBuilder

Асуудлын мэдэгдэл

"Лицензийн түлхүүрийг форматлах" асуудалд оролт нь a-ээс бүрдэнэ мөр лицензийн түлхүүрийг илэрхийлсэн тэмдэгтүүд. Эхэндээ мөрийг N + 1 бүлэгт (үгс) хооронд нь N зураасаар тусгаарладаг. Бидэнд бүхэл бүтэн K өгөгдсөн бөгөөд мөрийг форматлах зорилго нь бүлэг бүр яг K тэмдэгт агуулсан байх бөгөөд эхнийхээс бусад тэмдэгтүүдээс бага тэмдэгтүүдийг оруулахыг зөвшөөрнө. Цаашилбал, бүлгүүдийг '- '(зураас) ба зөвхөн том үсэгтэй байна.

Жишээ нь

S = "5F3Z-2e-9-w", K = 4
5F3Z-2E9W
S = "2-5g-3-J", K = 2
2-5G-3J

арга барил

S мөрөнд (оролт) арагшаа давтаж байхдаа шинэ мөр үүсгэх нь ойлгомжтой юм. Эхний бүлгээс бусад бүх бүлгүүд яг "k" үсэгтэй байх ёстойг бид мэддэг тул энэ нь чухал юм. Хэрэв бид s мөрөнд дахин давтаж байвал a-г хадгалж чадна эсрэг бүлэгт нэмэгдсэн тэмдэгтүүдийн тоог тоолох. Хэрэв энэ нь ямар ч үед 'k' -тэй тэнцэх юм бол бид үүнийг тэг болгож дахин тохируулж болно. Ингэснээр бид шинэ мөрөнд элементүүдийг нэмж оруулаад буцааж өгөхөөсөө өмнө дарааллыг нь буцааж өгдөг.

Лицензийн түлхүүр форматлах Leetcode шийдлийг хэрэгжүүлэх

C ++ програм

#include <bits/stdc++.h>

using namespace std;

string licenseKeyFormatting(string s , int k) {
    string ans;
    int cnt = 0 , n = s.size();

    for(int i = n - 1 ; i >= 0 ; i--) {
        if(s[i] != '-') {
            if(cnt == k) {
                ans += '-';
                cnt = 0;
            }
            cnt++;
            if(s[i] >= 'a' && s[i] <= 'z') {
                s[i] += 'A' - 'a';
            }
            ans += s[i];
        }
    }

    reverse(ans.begin() , ans.end());
    return ans;
}

int main() {
    string s = "5F3Z-2e-9-w";
    int K = 4;
    cout << licenseKeyFormatting(s, K) << endl;
    return 0;
}

Java програм

import java.lang.*;
import java.io.*;
import java.util.*;

class license_key {
    public static void main(String args[]) {
        String s = "5F3Z-2e-9-w";
        int K = 4;
        System.out.println(licenseKeyFormatting(s , K));
    }

    public static String licenseKeyFormatting(String s , int k) {
        StringBuilder ans = new StringBuilder();
        int cnt = 0 , n = s.length();

        char c;
        for(int i = n - 1 ; i >= 0 ; i--) {
            c = s.charAt(i);
            if(c != '-') {
                if(cnt == k) {
                    ans.append('-');
                    cnt = 0;
                }
                cnt++;
                if(c >= 'a' && c <= 'z') {
                    c += 'A' - 'a';
                }
                ans.append(c);
            }
        }
        return ans.reverse().toString();
    }
}
5F3Z-2E9W

Лицензийн түлхүүр форматлах Leetcode шийдлийн нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N), N = мөрний урт. Бид мөрийг нэг удаа давтах тул програм нь шугаман байна.

Сансрын нарийн төвөгтэй байдал 

O (1), бид санах ойн байнгын зайг ашигладаг тул.