網(wǎng)易首頁(yè) > 網(wǎng)易號(hào) > 正文申請(qǐng)入駐

2025-12-17：優(yōu)惠券校驗(yàn)器。用go語(yǔ)言，你有三個(gè)等長(zhǎng)數(shù)組 code、businessLine 和 isActive，分別

2025-12-17 00:17:55　來源: moonfdd

北京舉報(bào)

分享至

2025-12-17：優(yōu)惠券校驗(yàn)器。用go語(yǔ)言，你有三個(gè)等長(zhǎng)數(shù)組 code、businessLine 和 isActive，分別記錄 n 個(gè)優(yōu)惠券的標(biāo)識(shí)符、所屬業(yè)務(wù)線和是否有效。

把某張券視為“合格”的條件是：標(biāo)識(shí)符非空且只包含字母、數(shù)字或下劃線；所屬業(yè)務(wù)線為四種中的一種："electronics"、"grocery"、"pharmacy" 或 "restaurant"；并且 isActive 為 true。

結(jié)果應(yīng)返回所有合格券的標(biāo)識(shí)符組成的列表，排序規(guī)則是先按業(yè)務(wù)線的固定順序（electronics → grocery → pharmacy → restaurant）分組，然后在每個(gè)組內(nèi)按標(biāo)識(shí)符的字典序從小到大排列。

n == code.length == businessLine.length == isActive.length。

1 <= n <= 100。

0 <= code[i].length, businessLine[i].length <= 100。

code[i] 和 businessLine[i] 由可打印的 ASCII 字符組成。

isActive[i] 的值為 true 或 false。

輸入： code = ["SAVE20","","PHARMA5","SAVE@20"], businessLine = ["restaurant","grocery","pharmacy","restaurant"], isActive = [true,true,true,true]。

輸出： ["PHARMA5","SAVE20"]。

解釋：

第一個(gè)優(yōu)惠券有效。

第二個(gè)優(yōu)惠券的標(biāo)識(shí)符為空（無效）。

第三個(gè)優(yōu)惠券有效。

第四個(gè)優(yōu)惠券的標(biāo)識(shí)符包含特殊字符 @（無效）。

題目來自力扣3606。

步驟描述

1.初始化容器
程序創(chuàng)建了一個(gè)長(zhǎng)度為 4 的切片groups，里面每個(gè)元素是一個(gè)字符串切片，對(duì)應(yīng) 4 個(gè)業(yè)務(wù)線的分組順序：

?groups[0]→ electronics
?groups[1]→ grocery
?groups[2]→ pharmacy
?groups[3]→ restaurant
另外還創(chuàng)建一個(gè)空的ans切片，用于存放最終結(jié)果。

2.遍歷輸入數(shù)據(jù)
依次對(duì)每個(gè) i (0 ≤ i < n) 做以下判斷：

? 檢查code[i]是否非空字符串。
? 調(diào)用check函數(shù)判斷code[i]是否只包含字母、數(shù)字或下劃線，并且isActive[i]為 true。
- ?check內(nèi)部遍歷code[i]的每個(gè)字符，用unicode.IsLetter和unicode.IsDigit判斷，如果出現(xiàn)非字母/數(shù)字/下劃線則返回 false。
- ? 如果check返回 true，說明券是“合格”的。
? 對(duì)合格的券，根據(jù)businessLine[i]決定放入哪個(gè)分組：
- ? 如果是"electronics"，放入groups[0]
- ? 如果是"grocery"，放入groups[1]
- ? 如果是"pharmacy"，放入groups[2]
- ? 如果是"restaurant"，放入groups[3]
? 不合格的券（包括空字符串、非法字符、業(yè)務(wù)線不匹配（但題中業(yè)務(wù)線只有四種合法，如果給的業(yè)務(wù)線不在四個(gè)之中則不放入，代碼中switch默認(rèn)不處理））就忽略。

3.分組內(nèi)部排序
遍歷groups里的四個(gè)切片，對(duì)每個(gè)業(yè)務(wù)線分組內(nèi)的標(biāo)識(shí)符列表調(diào)用sort.Strings進(jìn)行字典序排序。

4.結(jié)果合并
按順序（electronics → grocery → pharmacy → restaurant）將每個(gè)分組排序后的內(nèi)容依次追加到ans中。

5.返回結(jié)果
最終ans就是按照先業(yè)務(wù)線固定順序、再組內(nèi)字典序排列的所有合格券標(biāo)識(shí)符列表。

在給定輸入的例子中：

?"SAVE20"→ 合格，業(yè)務(wù)線"restaurant"→ 放入groups[3]
?""→ 空字符串 → 不合格
?"PHARMA5"→ 合格，業(yè)務(wù)線"pharmacy"→ 放入groups[2]
?"SAVE@20"→ 包含@字符 → 不合格
最后：
?groups[2]排序后為["PHARMA5"]
?groups[3]排序后為["SAVE20"]
先electronics組（空）→grocery組（空）→pharmacy組（"PHARMA5"）→restaurant組（"SAVE20"）
最終結(jié)果：["PHARMA5", "SAVE20"]

時(shí)間復(fù)雜度分析

? 遍歷 n 張券：O(n)
? 對(duì)每個(gè)券，check函數(shù)要遍歷其標(biāo)識(shí)符的每個(gè)字符，設(shè)所有code[i]總長(zhǎng)度為 L，則總檢查字符次數(shù)為 O(L)
? 分組內(nèi)部排序：最多 n 個(gè)字符串，分成 4 組，最壞情況（所有合格券在同一組）需要對(duì)該組 m 個(gè)字符串排序，比較開銷是 O(m log m)，m ≤ n，所以排序總時(shí)間 O(n log n)（因?yàn)?4 組總和 ≤ n，每組排序復(fù)雜度相加 ≤ n log n 級(jí)別）
? 最終遍歷 groups 合并結(jié)果 O(n)
總時(shí)間復(fù)雜度O(L + n log n)，其中 L 是所有code[i]字符總數(shù)。

空間復(fù)雜度分析：

?groups數(shù)組及其內(nèi)部切片存儲(chǔ)所有合格券標(biāo)識(shí)符，總空間 O(n)
? 排序可能需額外 O(log n) 遞歸?？臻g（Go 的sort.Strings用快速排序）
? 結(jié)果ans額外存儲(chǔ) n 個(gè)字符串引用（和groups里的引用相同，不重復(fù)占用字符串本身空間，但切片結(jié)構(gòu)占用 O(n)）
? 因此總額外空間復(fù)雜度O(n)（主要是存儲(chǔ)合格券標(biāo)識(shí)符的引用和分組結(jié)構(gòu)，不包括輸入數(shù)據(jù)占用的空間）。

Go完整代碼如下：

package main

 import (
    "fmt"
    "sort"
    "unicode"
)

 func check(code string, isActive bool)bool {
    for _, c := range code {
        if c != '_' && !unicode.IsLetter(c) && !unicode.IsDigit(c) {
            returnfalse
        }
    }
    return isActive
}

 func validateCoupons(code []string, businessLine []string, isActive []bool) []string {
    groups := make([][]string, 4)
    for i := range groups {
        groups[i] = make([]string, 0)
    }

     ans := make([]string, 0)

     for i := 0; i < len(code); i++ {
        if code[i] != "" && check(code[i], isActive[i]) {
            switch businessLine[i] {
            case"electronics":
                groups[0] = append(groups[0], code[i])
            case"grocery":
                groups[1] = append(groups[1], code[i])
            case"pharmacy":
                groups[2] = append(groups[2], code[i])
            case"restaurant":
                groups[3] = append(groups[3], code[i])
            }
        }
    }

     for _, group := range groups {
        sort.Strings(group)
        ans = append(ans, group...)
    }

     return ans
}

 func main() {
    code := []string{"SAVE20", "", "PHARMA5", "SAVE@20"}
    businessLine := []string{"restaurant", "grocery", "pharmacy", "restaurant"}
    isActive := []bool{true, true, true, true}
    result := validateCoupons(code, businessLine, isActive)
    fmt.Println(result)
}

Python完整代碼如下：

# -*-coding:utf-8-*-

 import re
from typing import List

 def check(code: str, is_active: bool) -> bool:
    """檢查優(yōu)惠碼是否只包含字母、數(shù)字和下劃線，并且處于激活狀態(tài)"""
    if not code:
        return False
    # 使用正則表達(dá)式檢查是否只包含字母、數(shù)字和下劃線
    if not re.fullmatch(r'[\w]+', code):
        return False
    return is_active

 def validate_coupons(code: List[str], 
                     business_line: List[str], 
                     is_active: List[bool]) -> List[str]:
    """驗(yàn)證優(yōu)惠碼并按業(yè)務(wù)線分類排序"""
    # 定義業(yè)務(wù)線分組順序
    business_order = ["electronics", "grocery", "pharmacy", "restaurant"]
    # 初始化分組字典
    groups = {biz: [] for biz in business_order}
    # 遍歷所有優(yōu)惠碼
    for i in range(len(code)):
        # 驗(yàn)證優(yōu)惠碼
        if check(code[i], is_active[i]):
            biz = business_line[i]
            # 如果業(yè)務(wù)線在預(yù)定義列表中，則添加到對(duì)應(yīng)分組
            if biz in groups:
                groups[biz].append(code[i])
    # 對(duì)每個(gè)分組進(jìn)行排序，并按順序合并結(jié)果
    result = []
    for biz in business_order:
        groups[biz].sort()
        result.extend(groups[biz])
    return result

 def main():
    # 測(cè)試數(shù)據(jù)
    code = ["SAVE20", "", "PHARMA5", "SAVE@20"]
    business_line = ["restaurant", "grocery", "pharmacy", "restaurant"]
    is_active = [True, True, True, True]
    # 調(diào)用驗(yàn)證函數(shù)
    result = validate_coupons(code, business_line, is_active)
    # 輸出結(jié)果
    print(result)
    # 預(yù)期輸出: ['SAVE20'] (因?yàn)? ""為空, "SAVE@20"包含非法字符, 只有"SAVE20"和"PHARMA5"有效，但"PHARMA5"屬于pharmacy分組排在restaurant之后)

 if __name__ == "__main__":
    main()

C++完整代碼如下：

  

  

   


 using namespace std;

 bool check(conststring& code, bool isActive) {
    // 檢查優(yōu)惠碼是否只包含字母、數(shù)字和下劃線
    for (char c : code) {
        if (c != '_' && !isalnum(c)) {
            returnfalse;
        }
    }
    return isActive;
}

 vector validateCoupons(const vector& code,
                               const vector& businessLine,
                               const vector& isActive) {
    // 初始化4個(gè)分組，對(duì)應(yīng)electronics, grocery, pharmacy, restaurant
    vector 
 
 string 
 >> groups( 
 4 
 ); 
 
 
     vector< 
 string 
 > result; 
 
 
 
 
      
 for 
  (size_t i =  
 0 
 ; i < code.size(); i++) { 
 
 
          
 // 驗(yàn)證優(yōu)惠碼 
 
 
          
 if 
  (!code[i].empty() && check(code[i], isActive[i])) { 
 
 
              
 // 根據(jù)業(yè)務(wù)線添加到對(duì)應(yīng)分組 
 
 
              
 if 
  (businessLine[i] ==  
 "electronics" 
 ) { 
 
 
                 groups[ 
 0 
 ].push_back(code[i]); 
 
 
             }  
 else 
 if 
  (businessLine[i] ==  
 "grocery" 
 ) { 
 
 
                 groups[ 
 1 
 ].push_back(code[i]); 
 
 
             }  
 else 
 if 
  (businessLine[i] ==  
 "pharmacy" 
 ) { 
 
 
                 groups[ 
 2 
 ].push_back(code[i]); 
 
 
             }  
 else 
 if 
  (businessLine[i] ==  
 "restaurant" 
 ) { 
 
 
                 groups[ 
 3 
 ].push_back(code[i]); 
 
 
             } 
 
 
         } 
 
 
     } 
 
 
 
 
      
 // 對(duì)每個(gè)分組排序并合并結(jié)果 
 
 
      
 for 
  (auto& group : groups) { 
 
 
         sort(group.begin(), group.end()); 
 
 
          
 for 
  ( 
 const 
  auto& coupon : group) { 
 
 
             result.push_back(coupon); 
 
 
         } 
 
 
     } 
 
 
 
 
      
 return 
  result; 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
     vector< 
 string 
 > code = { 
 "SAVE20" 
 ,  
 "" 
 ,  
 "PHARMA5" 
 ,  
 "SAVE@20" 
 }; 
 
 
     vector< 
 string 
 > businessLine = { 
 "restaurant" 
 ,  
 "grocery" 
 ,  
 "pharmacy" 
 ,  
 "restaurant" 
 }; 
 
 
     vector< 
 bool 
 > isActive = { 
 true 
 ,  
 true 
 ,  
 true 
 ,  
 true 
 }; 
 
 
 
 
     vector< 
 string 
 > result = validateCoupons(code, businessLine, isActive); 
 
 
 
 
      
 // 輸出結(jié)果 
 
 
     cout <<  
 "[" 
 ; 
 
 
      
 for 
  (size_t i =  
 0 
 ; i < result.size(); i++) { 
 
 
         cout <<  
 "\"" 
  << result[i] <<  
 "\"" 
 ; 
 
 
          
 if 
  (i != result.size() -  
 1 
 ) { 
 
 
             cout <<  
 ", " 
 ; 
 
 
         } 
 
 
     } 
 
 
     cout <<  
 "]" 
  << endl; 
 
 
 
 
      
 return 
 0 
 ; 
 
 
 }

我們相信人工智能為普通人提供了一種“增強(qiáng)工具”，并致力于分享全方位的AI知識(shí)。在這里，您可以找到最新的AI科普文章、工具評(píng)測(cè)、提升效率的秘籍以及行業(yè)洞察。歡迎關(guān)注“福大大架構(gòu)師每日一題”，發(fā)消息可獲得面試資料，讓AI助力您的未來發(fā)展。

特別聲明：以上內(nèi)容(如有圖片或視頻亦包括在內(nèi))為自媒體平臺(tái)“網(wǎng)易號(hào)”用戶上傳并發(fā)布，本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.