ໃບອະນຸຍາດການແກ້ໄຂຮູບແບບ Leetcode


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Capital One ກູໂກ
string StringBuilder

ຖະແຫຼງການບັນຫາ

ໃນບັນຫາ“ ການ ກຳ ນົດຮູບແບບໃບອະນຸຍາດ”, ການປ້ອນຂໍ້ມູນປະກອບດ້ວຍກ string ຂອງຕົວອັກສອນ, ທີ່ເປັນຕົວແທນໃຫ້ກຸນແຈໃບອະນຸຍາດ. ໃນເບື້ອງຕົ້ນ, ສະຕິງຖືກແຍກອອກເປັນ N + 1 ກຸ່ມ (ຄຳ ສັບ) ໂດຍ N dashes ໃນລະຫວ່າງ. ພວກເຮົາຍັງໄດ້ຮັບຕົວເລກ K, ແລະເປົ້າ ໝາຍ ແມ່ນການຈັດຮູບແບບດັ່ງກ່າວວ່າທຸກໆກຸ່ມມີຕົວອັກສອນ K ແທ້, ຍົກເວັ້ນຕົວອັກສອນ ທຳ ອິດ, ເຊິ່ງອະນຸຍາດໃຫ້ຕົວອັກສອນນ້ອຍກ່ວາ K. ນອກຈາກນັ້ນ, ກຸ່ມຕ້ອງແຍກດ້ວຍ '- '(dash) ແລະມີຕົວອັກສອນໃຫຍ່ເທົ່ານັ້ນ.

ຍົກຕົວຢ່າງ

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

ວິທີການ

ມັນມີຄວາມຕັ້ງໃຈທີ່ພວກເຮົາຄວນສ້າງສາຍສະຕິງ ໃໝ່ ໃນຂະນະທີ່ມັນກັບໄປທາງຫລັງໃນຊ່ອຍແນ່ s (input). ນີ້ແມ່ນສິ່ງທີ່ ສຳ ຄັນເພາະວ່າພວກເຮົາຮູ້ຍົກເວັ້ນກຸ່ມ ທຳ ອິດ, ກຸ່ມອື່ນທັງ ໝົດ ຕ້ອງມີຕົວອັກສອນ '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), ດັ່ງທີ່ພວກເຮົາໃຊ້ພື້ນທີ່ ໜ່ວຍ ຄວາມ ຈຳ ຢູ່ຕະຫຼອດເວລາ.