@TOC

有效的括號

給定一個只包括 '('，')'始腾，'{'，'}'踪宠，'['，']' 的字符串 s 妈嘹，判斷字符串是否有效。
有效字符串需滿足：
左括號必須用相同類型的右括號閉合绍妨。
左括號必須以正確的順序閉合润脸。
每個右括號都有一個對應(yīng)的相同類型的左括號。

示例 1：
輸入：s = "()"
輸出：true
示例 2：
輸入：s = "()[]{}"
輸出：true
示例 3：
輸入：s = "(]"
輸出：false

+ (BOOL)hy_isValidParenthesis:(NSString *)s {
    NSMutableArray<NSString *> *stack = [NSMutableArray array];
    
    for (NSInteger i = 0; i < s.length; i++) {
        NSString *ch = [s substringWithRange:NSMakeRange(i, 1)];
        
        if ([ch isEqualToString:@"("] || [ch isEqualToString:@"{"] || [ch isEqualToString:@"["]) {
            // 如果是左括號他去，則將其推入棧中
            [stack addObject:ch];
        } else {
            // 否則毙驯，彈出棧頂元素并檢查它是否與當(dāng)前括號匹配
            NSString *top = stack.lastObject;
            [stack removeLastObject];
            
            if (([ch isEqualToString:@")"] && ![top isEqualToString:@"("]) ||
                ([ch isEqualToString:@"}"] && ![top isEqualToString:@"{"]) ||
                ([ch isEqualToString:@"]"] && ![top isEqualToString:@"["])) {
                return NO;
            }
        }
    }
    
    // 最后，如果棧為空灾测，則說明所有括號都正確閉合
    return stack.count == 0;
}

該算法使用棧來跟蹤未關(guān)閉的左括號爆价。遍歷字符串中的每個字符，如果當(dāng)前字符是左括號媳搪，則將其推入棧中铭段；否則，彈出棧頂元素并檢查它是否與當(dāng)前括號匹配秦爆。如果不匹配或棧為空序愚，則說明字符串無效。

最后等限，如果棧為空爸吮，則說明所有括號都正確地閉合了芬膝。

括號生成

數(shù)字 n 代表生成括號的對數(shù)，請你設(shè)計一個函數(shù)形娇，用于能夠生成所有可能的并且 有效的 括號組合锰霜。

示例 1：
輸入：n = 3
輸出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
輸入：n = 1
輸出：["()"]

+ (NSArray<NSString *> *)hy_generateParenthesis:(NSInteger)n {
    NSMutableArray<NSString *> *result = [NSMutableArray array];
    
    void (^backtrack)(NSString *, NSInteger, NSInteger) = ^(NSString *s, NSInteger left, NSInteger right) {
        if (s.length == n * 2) {
            [result addObject:s];
            return;
        }
        
        if (left < n) {
            // 如果左括號數(shù)量小于 n，則可以添加一個左括號
            backtrack([s stringByAppendingString:@"("], left + 1, right);
        }
        
        if (right < left) {
            // 如果右括號數(shù)量小于左括號數(shù)量桐早，則可以添加一個右括號
            backtrack([s stringByAppendingString:@")"], left, right + 1);
        }
    };
    
    backtrack(@"", 0, 0);
    
    return result;
}

該算法使用回溯方法生成所有可能的括號組合癣缅。定義一個輔助函數(shù) backtrack，它維護(hù)當(dāng)前括號字符串 s勘畔、已使用的左括號數(shù) left 和已使用的右括號數(shù) right所灸。

如果 s 的長度等于 n 的兩倍，則說明我們已經(jīng)產(chǎn)生了一個有效的括號組合炫七，將其推入結(jié)果數(shù)組中并返回爬立。否則，我們有兩種選擇：添加一個左括號或添加一個右括號万哪。

當(dāng)左括號數(shù)量小于 n 時侠驯，我們可以添加一個左括號。當(dāng)右括號數(shù)量小于左括號數(shù)量時奕巍，我們可以添加一個右括號吟策。這兩個條件都滿足時，我們需要分別嘗試添加左括號和右括號的止。

找出字符串中第一個匹配項的下標(biāo)

給你兩個字符串 haystack 和 needle 檩坚，請你在 haystack 字符串中找出 needle 字符串的第一個匹配項的下標(biāo)（下標(biāo)從 0 開始）。如果 needle 不是 haystack 的一部分诅福，則返回 -1 匾委。

示例 1：

輸入：haystack = "sadbutsad", needle = "sad"
輸出：0
解釋："sad" 在下標(biāo) 0 和 6 處匹配。
第一個匹配項的下標(biāo)是 0 氓润，所以返回 0 赂乐。
示例 2：

輸入：haystack = "leetcode", needle = "leeto"
輸出：-1
解釋："leeto" 沒有在 "leetcode" 中出現(xiàn)，所以返回 -1 咖气。

`+ (NSInteger)hy_findSubscripMatchString:(NSString *)haystack needle:(NSString *)needle {
    if (needle.length == 0) {
        return 0;
    }
    
    NSInteger n = needle.length;
    
    // 遍歷 haystack 中所有長度為 n 的子串
    for (NSInteger i = 0; i < haystack.length - n + 1; i++) {
        NSString *sub = [haystack substringWithRange:NSMakeRange(i, n)];
        
        if ([sub isEqualToString:needle]) {
            return i;
        }
    }
    
    return -1;
}

該算法使用暴力枚舉方法挨措，在 haystack 中逐一查找長度為 n 的子串是否與 needle 相等。如果相等崩溪，則返回該子串在 haystack 中的下標(biāo)浅役。

最后，如果沒有找到匹配項悯舟，則返回 -1担租。

要使用該函數(shù)，請調(diào)用 strStr 方法抵怎，并將要查詢的字符串作為參數(shù)傳遞給它奋救。它將返回第一個匹配項的下標(biāo)或 -1岭参。

注釋已經(jīng)盡可能詳細(xì)地解釋了算法的實(shí)現(xiàn)過程。此外尝艘，我們使用了 NSString 的 substringWithRange: 方法來提取子串演侯。它的語法是 [string substringWithRange:NSMakeRange(location, length)]，其中 location 是起始位置背亥，length 是子串的長度

串聯(lián)所有單詞的子串

給定一個字符串 s 和一個字符串?dāng)?shù)組 words秒际。 words 中所有字符串 長度相同。
s 中的 串聯(lián)子串 是指一個包含 words 中所有字符串以任意順序排列連接起來的子串狡汉。
例如娄徊，如果 words = ["ab","cd","ef"]， 那么 "abcdef"盾戴， "abefcd"寄锐，"cdabef"， "cdefab"尖啡，"efabcd"橄仆， 和 "efcdab" 都是串聯(lián)子串。 "acdbef" 不是串聯(lián)子串衅斩，因為他不是任何 words 排列的連接盆顾。
返回所有串聯(lián)字串在 s 中的開始索引。你可以以 任意順序 返回答案畏梆。

示例 1：
輸入：s = "barfoothefoobarman", words = ["foo","bar"]
輸出：[0,9]
解釋：因為 words.length == 2 同時 words[i].length == 3您宪，連接的子字符串的長度必須為 6。
子串 "barfoo" 開始位置是 0奠涌。它是 words 中以 ["bar","foo"] 順序排列的連接映跟。
子串 "foobar" 開始位置是 9凭需。它是 words 中以 ["foo","bar"] 順序排列的連接吟宦。
輸出順序無關(guān)緊要喳资。返回 [9,0] 也是可以的罗捎。
示例 2：
輸入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
輸出：[]
解釋：因為 words.length == 4 并且 words[i].length == 4柿隙，所以串聯(lián)子串的長度必須為 16大审。
s 中沒有子串長度為 16 并且等于 words 的任何順序排列的連接芥牌。
所以我們返回一個空數(shù)組贿肩。
示例 3：
輸入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
輸出：[6,9,12]
解釋：因為 words.length == 3 并且 words[i].length == 3峦椰，所以串聯(lián)子串的長度必須為 9。
子串 "foobarthe" 開始位置是 6汰规。它是 words 中以 ["foo","bar","the"] 順序排列的連接汤功。
子串 "barthefoo" 開始位置是 9。它是 words 中以 ["bar","the","foo"] 順序排列的連接溜哮。
子串 "thefoobar" 開始位置是 12滔金。它是 words 中以 ["the","foo","bar"] 順序排列的連接色解。

+ (NSArray<NSNumber *> *)hy_substringConnectsWords:(NSString *)s withWords:(NSArray<NSString *> *)words {
    NSMutableArray<NSNumber *> *res = [NSMutableArray array]; // 用于存儲結(jié)果
    
    if (!s || !words || words.count == 0) return res; // 特判，若s和words有一個不存在餐茵，則返回res
    
    NSInteger wordLen = words[0].length; // 獲取單詞長度
    NSMutableDictionary<NSString *, NSNumber *> *wordsCount = [NSMutableDictionary dictionary];
    for (NSString *word in words) { // 將words數(shù)組中所有字符串存入哈希表科阎，并統(tǒng)計每個字符串出現(xiàn)的次數(shù)
        NSNumber *count = wordsCount[word];
        wordsCount[word] = count ? @(count.integerValue + 1) : @1;
    }
    
    for (NSInteger i = 0; i < wordLen; i++) { // 在0到wordLen-1范圍內(nèi)枚舉起點(diǎn)
        NSInteger left = i, right = i, count = 0; // 已經(jīng)匹配的字符串?dāng)?shù)量
        NSMutableDictionary<NSString *, NSNumber *> *currWordsCount = [NSMutableDictionary dictionary]; // 當(dāng)前已經(jīng)匹配的字符串以及它們出現(xiàn)的次數(shù)
        
        while (right + wordLen <= s.length) { // 枚舉終點(diǎn)
            NSString *word = [s substringWithRange:NSMakeRange(right, wordLen)]; // 獲取當(dāng)前的單詞
            right += wordLen; // 更新右指針
            
            NSNumber *wordCount = wordsCount[word];
            if (!wordCount) { // 如果這個單詞不在哈希表中，則說明從當(dāng)前左指針開始沒有一個符合要求的子串了忿族，直接跳過
                left = right;
                count = 0; // 此時需要重新統(tǒng)計已經(jīng)匹配的字符串?dāng)?shù)量锣笨，以及當(dāng)前已經(jīng)匹配的字符串以及它們出現(xiàn)的次數(shù)
                currWordsCount = [NSMutableDictionary dictionary];
            } else {
                NSNumber *currWordCount = currWordsCount[word];
                currWordsCount[word] = currWordCount ? @(currWordCount.integerValue + 1) : @1; // 將當(dāng)前單詞存入哈希表中，并更新它的出現(xiàn)次數(shù)
                
                while (currWordsCount[word].integerValue > wordCount.integerValue) { // 如果當(dāng)前單詞的出現(xiàn)次數(shù)大于哈希表中該單詞的出現(xiàn)次數(shù)道批，則說明當(dāng)前的子串不符合要求错英，需要將左指針右移
                    NSString *removeWord = [s substringWithRange:NSMakeRange(left, wordLen)];
                    left += wordLen;
                    currWordsCount[removeWord] = @(currWordsCount[removeWord].integerValue - 1);
                    count--; // 更新統(tǒng)計值
                }
                
                count++; // 已經(jīng)匹配的字符串?dāng)?shù)量加1
                
                if (count == words.count) { // 如果已經(jīng)匹配的字符串?dāng)?shù)量等于words數(shù)組的長度，則說明找到了一個符合要求的子串隆豹，記錄下其起始位置
                    [res addObject:@(left)];
                    NSString *removeWord = [s substringWithRange:NSMakeRange(left, wordLen)];
                    left += wordLen;
                    currWordsCount[removeWord] = @(currWordsCount[removeWord].integerValue - 1);
                    count--;
                }
            }
        }
    }
    
    return res; // 返回結(jié)果數(shù)組
}

主要思路是：遍歷s字符串椭岩，依次截取長度為words數(shù)組中所有單詞長度之和的子串，判斷該子串是否由words數(shù)組中所有單詞組成噪伊。具體步驟：

1簿煌、根據(jù)words[0]的長度計算出每個單詞的長度；
2鉴吹、計算所有單詞組成的子串長度subStringLength姨伟；
3、將words數(shù)組轉(zhuǎn)換成字典wordCounts豆励，key是單詞夺荒，value是該單詞出現(xiàn)的次數(shù)（因為可以重復(fù)）；
4.遍歷s字符串良蒸，依次截取長度為subStringLength的子串技扼，判斷該子串是否符合條件；
5嫩痰、對于每個子串剿吻，將其按照單詞的長度拆分成多個單詞，判斷這些單詞是否可以組成words數(shù)組中所有單詞的組合串纺；
6丽旅、如果符合條件，將該子串的起始位置添加到結(jié)果數(shù)組中纺棺。

時間復(fù)雜度為O(n^2)榄笙，空間復(fù)雜度為O(n)，其中n為s字符串的長度祷蝌。

最長有效括號

給你一個只包含 '(' 和 ')' 的字符串茅撞，找出最長有效（格式正確且連續(xù)）括號子串的長度。

示例 1：
輸入：s = "(()"
輸出：2
解釋：最長有效括號子串是 "()"
示例 2：
輸入：s = ")()())"
輸出：4
解釋：最長有效括號子串是 "()()"
示例 3：
輸入：s = ""
輸出：0

+ (NSInteger)hy_longestValidParentheses:(NSString *)s {
    // 用棧來保存左括號的下標(biāo)
    NSMutableArray<NSNumber *> *stack = [NSMutableArray arrayWithObject:@(-1)];
    NSInteger maxLength = 0;

    for (NSInteger i = 0; i < s.length; i++) {
        NSString *c = [s substringWithRange:NSMakeRange(i, 1)];
        if ([c isEqualToString:@"("]) {
            // 如果當(dāng)前字符是左括號，則將其下標(biāo)入棧
            [stack addObject:@(i)];
        } else {
            // 如果當(dāng)前字符是右括號米丘，則將棧頂元素彈出
            [stack removeLastObject];
            if (stack.count == 0) {
                // 如果棧為空剑令，說明沒有左括號與該右括號匹配，則將該右括號的下標(biāo)入棧作為新的起點(diǎn)
                [stack addObject:@(i)];
            } else {
                // 如果棧不為空蠕蚜，則計算以當(dāng)前右括號結(jié)尾的最長有效括號子串長度
                NSInteger length = i - stack.lastObject.integerValue;
                maxLength = MAX(maxLength, length);
            }
        }
    }

    return maxLength;
}

主要思路是：使用棧來判斷是否有有效的括號匹配尚洽。具體步驟：
將-1壓入棧底，在后面計算長度時可以方便地得到以第一個左括號開頭的子串長度靶累；
遍歷字符串s腺毫，如果當(dāng)前字符是左括號，則將其下標(biāo)入棧挣柬；
如果當(dāng)前字符是右括號潮酒，則將棧頂元素彈出，如果棧為空邪蛔，說明沒有左括號與該右括號匹配急黎，則將該右括號的下標(biāo)入棧作為新的起點(diǎn)；
如果棧不為空侧到，則計算以當(dāng)前右括號結(jié)尾的最長有效括號子串長度勃教，即當(dāng)前右括號下標(biāo)減去棧頂元素下標(biāo)，取這些長度的最大值匠抗；
返回最大長度故源。
時間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)汞贸，其中n為s字符串的長度绳军。

字符串相乘

給定兩個以字符串形式表示的非負(fù)整數(shù) num1 和 num2，返回 num1 和 num2 的乘積矢腻，它們的乘積也表示為字符串形式门驾。

注意：不能使用任何內(nèi)置的 BigInteger 庫或直接將輸入轉(zhuǎn)換為整數(shù)。

示例 1:

輸入: num1 = "2", num2 = "3"
輸出: "6"
示例 2:

輸入: num1 = "123", num2 = "456"
輸出: "56088"

+ (NSString *)hy_multiply:(NSString *)num1 with:(NSString *)num2 {
    // 處理特殊情況
    if ([num1 isEqualToString:@"0"] || [num2 isEqualToString:@"0"]) {
        return @"0";
    }

    // 將num1和num2翻轉(zhuǎn)多柑，并轉(zhuǎn)換成整數(shù)數(shù)組奶是，方便計算
    NSMutableArray<NSNumber *> *num1Arr = [NSMutableArray array];
    for (NSInteger i = num1.length - 1; i >= 0; i--) {
        NSString *digitStr = [num1 substringWithRange:NSMakeRange(i, 1)];
        [num1Arr addObject:@(digitStr.integerValue)];
    }
    NSMutableArray<NSNumber *> *num2Arr = [NSMutableArray array];
    for (NSInteger i = num2.length - 1; i >= 0; i--) {
        NSString *digitStr = [num2 substringWithRange:NSMakeRange(i, 1)];
        [num2Arr addObject:@(digitStr.integerValue)];
    }

    // 計算乘積并保存到result數(shù)組中
    NSMutableArray<NSNumber *> *result = [NSMutableArray arrayWithCapacity:num1Arr.count + num2Arr.count];
    for (NSInteger i = 0; i < num1Arr.count + num2Arr.count; i++) {
        [result addObject:@(0)];
    }
    for (NSInteger i = 0; i < num1Arr.count; i++) {
        for (NSInteger j = 0; j < num2Arr.count; j++) {
            NSInteger product = num1Arr[i].integerValue * num2Arr[j].integerValue;
            NSInteger sum = result[i+j].integerValue + product % 10;
            NSInteger carry = sum / 10;
            NSInteger digit = sum % 10;
            
            // 將NSNumber對象轉(zhuǎn)換成可變類型，修改其值竣灌，再重新封裝成NSNumber對象
            NSMutableArray<NSNumber *> *mutableResult = [NSMutableArray arrayWithArray:result];
            mutableResult[i+j] = @(digit);
            mutableResult[i+j+1] = @(mutableResult[i+j+1].integerValue + carry + product / 10);
            result = [NSMutableArray arrayWithArray:mutableResult];
        }
    }

    // 對result數(shù)組進(jìn)行進(jìn)位處理
    for (NSInteger i = 0; i < result.count - 1; i++) {
        NSInteger carry = [result[i] integerValue] / 10;
        result[i] = @([result[i] integerValue] % 10);
        
        // 同上诫隅，將NSNumber對象轉(zhuǎn)換成可變類型，修改其值帐偎，再重新封裝成NSNumber對象
        NSMutableArray<NSNumber *> *mutableResult = [NSMutableArray arrayWithArray:result];
        mutableResult[i+1] = @(mutableResult[i+1].integerValue + carry);
        result = [NSMutableArray arrayWithArray:mutableResult];
    }

    // 將result數(shù)組翻轉(zhuǎn)并去掉前導(dǎo)0，將數(shù)組轉(zhuǎn)換成字符串返回
    while (result.count > 1 && result.lastObject.integerValue == 0) {
        [result removeLastObject];
    }
    NSMutableString *resultStr = [NSMutableString string];
    for (NSInteger i = result.count - 1; i >= 0; i--) {
        [resultStr appendFormat:@"%ld", result[i].integerValue];
    }
    return resultStr;
}

主要思路:
從低位到高位逐位相乘蛔屹，將結(jié)果保存到一個數(shù)組中削樊，再對數(shù)組進(jìn)行進(jìn)位處理。具體步驟：
處理特殊情況，如果有一個字符串為0漫贞，則直接返回"0"甸箱；
將num1和num2翻轉(zhuǎn)，并轉(zhuǎn)換成整數(shù)數(shù)組迅脐，方便計算芍殖；
創(chuàng)建一個長度為len(num1)+len(num2)的數(shù)組result，用于保存乘積谴蔑；
從低位到高位逐位相乘豌骏，將結(jié)果保存到result數(shù)組中；
對result數(shù)組進(jìn)行進(jìn)位處理隐锭，具體方法是：對于result[i]窃躲，將其除以10得到進(jìn)位carry，將result[i]對10取模得到當(dāng)前位的值钦睡，將carry加到result[i+1]中蒂窒；
將result數(shù)組翻轉(zhuǎn)并去掉前導(dǎo)0，將數(shù)組轉(zhuǎn)換成字符串返回荞怒。
時間復(fù)雜度為O(n^2)洒琢，其中n為num1和num2中較長的那個字符串的長度。對于每一位的乘積都需要計算一次褐桌，并且需要進(jìn)行進(jìn)位處理衰抑。空間復(fù)雜度為O(n)撩嚼。

最接近的三數(shù)之和

給你一個長度為 n 的整數(shù)數(shù)組 nums 和 一個目標(biāo)值 target停士。請你從 nums 中選出三個整數(shù)，使它們的和與 target 最接近完丽。
返回這三個數(shù)的和恋技。
假定每組輸入只存在恰好一個解。

示例 1：
輸入：nums = [-1,2,1,-4], target = 1
輸出：2
解釋：與 target 最接近的和是 2 (-1 + 2 + 1 = 2) 逻族。
示例 2：
輸入：nums = [0,0,0], target = 1
輸出：0

+ (NSInteger)hy_threeSumClosest:(NSArray<NSNumber *> *)nums target:(NSInteger)target {
    // 對數(shù)組進(jìn)行排序
    NSArray<NSNumber *> *sortedNums = [nums sortedArrayUsingSelector:@selector(compare:)];
    
    NSInteger closestSum = sortedNums[0].integerValue + sortedNums[1].integerValue + sortedNums[2].integerValue;
    
    for (NSInteger i = 0; i < sortedNums.count - 2; i++) {
        NSInteger left = i + 1;
        NSInteger right = sortedNums.count - 1;
        
        while (left < right) {
            NSInteger sum = sortedNums[i].integerValue + sortedNums[left].integerValue + sortedNums[right].integerValue;
            
            // 如果新的和更接近目標(biāo)值蜻底，則更新結(jié)果
            if (labs(target - sum) < labs(target - closestSum)) {
                closestSum = sum;
            }
            
            // 根據(jù)當(dāng)前和與目標(biāo)值的大小關(guān)系移動指針
            if (sum < target) {
                left++;
            } else if (sum > target) {
                right--;
            } else {
                return sum;
            }
        }
    }
    
    return closestSum;
}

該算法首先對數(shù)組進(jìn)行排序。然后聘鳞，遍歷排序后的數(shù)組并選擇一個數(shù)字作為三元組中的第一個數(shù)字薄辅。接下來，使用雙指針?biāo)惴ㄔ谑Ｓ嗟臄?shù)字中查找兩個數(shù)字抠璃，使它們的和等于目標(biāo)值（即 target 減去當(dāng)前數(shù)字）站楚。

如果當(dāng)前和與目標(biāo)值的差比當(dāng)前最接近的和與目標(biāo)值的差更小，則更新結(jié)果搏嗡。最后返回最接近目標(biāo)值的三數(shù)之和窿春。

三數(shù)之和

給你一個整數(shù)數(shù)組 nums 拉一，判斷是否存在三元組 [nums[i], nums[j], nums[k]] 滿足 i != j、i != k 且 j != k 旧乞，同時還滿足 nums[i] + nums[j] + nums[k] == 0 蔚润。請你返回所有和為 0 且不重復(fù)的三元組。
注意：答案中不可以包含重復(fù)的三元組尺栖。

示例 1：
輸入：nums = [-1,0,1,2,-1,-4]
輸出：[[-1,-1,2],[-1,0,1]]
解釋：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 嫡纠。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 延赌。
不同的三元組是 [-1,0,1] 和 [-1,-1,2] 除盏。
注意，輸出的順序和三元組的順序并不重要皮胡。
示例 2：
輸入：nums = [0,1,1]
輸出：[]
解釋：唯一可能的三元組和不為 0 痴颊。
示例 3：
輸入：nums = [0,0,0]
輸出：[[0,0,0]]
解釋：唯一可能的三元組和為 0 。

以下是 Objective-C 代碼屡贺，用于查找三數(shù)之和為 0 的唯一三元組：

+ (NSArray<NSArray<NSNumber *> *> *)hy_threeSum:(NSArray<NSNumber *> *)nums {
    NSMutableArray<NSArray<NSNumber *> *> *result = [NSMutableArray array];
    
    if (nums.count < 3) {
        return result;
    }
    
    // 對數(shù)組進(jìn)行排序
    NSArray<NSNumber *> *sortedNums = [nums sortedArrayUsingSelector:@selector(compare:)];
    
    for (NSInteger i = 0; i < sortedNums.count - 2; i++) {
        // 如果當(dāng)前數(shù)字與上一個數(shù)字相同蠢棱，則跳過以避免重復(fù)結(jié)果
        if (i > 0 && [sortedNums[i] isEqualToNumber:sortedNums[i - 1]]) {
            continue;
        }
        
        NSInteger left = i + 1;
        NSInteger right = sortedNums.count - 1;
        
        while (left < right) {
            NSInteger sum = sortedNums[i].integerValue + sortedNums[left].integerValue + sortedNums[right].integerValue;
            
            if (sum == 0) {
                [result addObject:@[sortedNums[i], sortedNums[left], sortedNums[right]]];
                
                // 跳過重復(fù)的數(shù)字
                while (left < right && [sortedNums[left] isEqualToNumber:sortedNums[left + 1]]) {
                    left++;
                }
                
                while (left < right && [sortedNums[right] isEqualToNumber:sortedNums[right - 1]]) {
                    right--;
                }
                
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    
    return result;
}

該算法首先對數(shù)組進(jìn)行排序，然后遍歷排序后的數(shù)組并選擇一個數(shù)字作為三元組中的第一個數(shù)字甩栈。接下來泻仙，使用雙指針?biāo)惴ㄔ谑Ｓ嗟臄?shù)字中查找兩個數(shù)字，使它們的和等于目標(biāo)值（即當(dāng)前數(shù)字的相反數(shù)）量没。

由于答案不能包含重復(fù)的三元組玉转，因此我們需要跳過具有相同值的數(shù)字。這可以通過檢查左右指針?biāo)谖恢玫那耙粋€或后一個數(shù)字來實(shí)現(xiàn)殴蹄。

回文數(shù)

給你一個整數(shù) x 究抓，如果 x 是一個回文整數(shù)，返回 true 袭灯；否則刺下，返回 false 。
回文數(shù)是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數(shù)稽荧。

例如橘茉，121 是回文，而 123 不是姨丈。

示例 1：
輸入：x = 121
輸出：true
示例 2：
輸入：x = -121
輸出：false
解釋：從左向右讀, 為 -121 畅卓。 從右向左讀, 為 121- 。因此它不是一個回文數(shù)蟋恬。
示例 3：
輸入：x = 10
輸出：false
解釋：從右向左讀, 為 01 翁潘。因此它不是一個回文數(shù)。

+ (BOOL)hy_isPalindrome:(NSInteger)x {
    // 如果x小于0或者最后一位是0且x不等于0歼争，則不是回文數(shù)
    if (x < 0 || (x % 10 == 0 && x != 0)) {
        return NO;
    }
    
    NSInteger reversed = 0;
    while (x > reversed) {
        // 取出最后一位數(shù)字
        NSInteger digit = x % 10;
        // 將該位數(shù)字加入反轉(zhuǎn)后的結(jié)果中
        reversed = reversed * 10 + digit;
        // 去掉已經(jīng)處理過的數(shù)字
        x /= 10;
    }
    
    // 如果x有奇數(shù)位唐础，則reversed比x多一位箱歧，需要去掉中間的那一位
    return x == reversed || x == reversed / 10;
}

注解：

• isPalindrome: 是該方法的名稱，輸入?yún)?shù)為一個 NSInteger 類型的整數(shù)一膨，輸出也是一個 BOOL 類型的值。
• i如果給定整數(shù)小于 0 或者最后一位是 0 且整數(shù)不為 0洒沦，則肯定不是回文數(shù)豹绪，直接返回 NO。
• i初始化反轉(zhuǎn)后的結(jié)果為 0申眼。
• i循環(huán)取出給定整數(shù)的最后一位數(shù)字瞒津，并將其加入反轉(zhuǎn)后的結(jié)果中。
• i在每次循環(huán)中判斷反轉(zhuǎn)后的結(jié)果是否超過了給定整數(shù)的一半長度括尸，如果超過了巷蚪，則說明已經(jīng)處理完了一半位數(shù)，可以開始比較了濒翻。
• i如果給定整數(shù)有奇數(shù)位屁柏，則反轉(zhuǎn)后的結(jié)果比給定整數(shù)多一位，需要去掉中間的那一位有送，然后比較是否相等淌喻。
• i最后返回比較結(jié)果。

該算法的時間復(fù)雜度為 O(log n)雀摘，空間復(fù)雜度為 O(1)裸删。

最長公共前綴

編寫一個函數(shù)來查找字符串?dāng)?shù)組中的最長公共前綴。
如果不存在公共前綴阵赠，返回空字符串 ""涯塔。

示例 1：

輸入：strs = ["flower","flow","flight"]
輸出："fl"
示例 2：

輸入：strs = ["dog","racecar","car"]
輸出：""
解釋：輸入不存在公共前綴。

+ (NSString *)longestCommonPrefix:(NSArray<NSString *> *)strs {
    if (strs == nil || strs.count == 0) { // 如果輸入數(shù)組為空清蚀，則返回空字符串
        return @"";
    }
    
    NSUInteger minLength = NSUIntegerMax;
    for (NSString *s in strs) { // 先找出所有字符串中長度最短的那個
        minLength = MIN(minLength, s.length);
    }
    
    NSMutableString *prefix = [NSMutableString stringWithCapacity:minLength];
    for (NSUInteger i = 0; i < minLength; i++) {
        unichar c = [strs[0] characterAtIndex:i]; // 取出第一個字符串的第i個字符
        for (NSUInteger j = 1; j < strs.count; j++) { // 遍歷剩余的字符串匕荸，判斷是否都包含該字符
            NSString *s = strs[j];
            if ([s characterAtIndex:i] != c) { // 如果遇到不同的字符，則返回當(dāng)前已經(jīng)匹配的前綴
                return prefix;
            }
        }
        [prefix appendFormat:@"%C", c]; // 如果所有字符串中都包含該字符轧铁，則將其加入結(jié)果中
    }
    
    return prefix;
}

注解：
longestCommonPrefix 是該函數(shù)的名稱每聪，輸入?yún)?shù)為一個字符串?dāng)?shù)組，輸出也是一個字符串齿风。
如果輸入數(shù)組為空药薯，則直接返回空字符串。
先找出所有字符串中長度最短的那個救斑。
創(chuàng)建一個空字符串用于存儲公共前綴童本，然后循環(huán)遍歷所有字符串中的每個字符，判斷它們是否都相同脸候，如果是穷娱，則將該字符加入到結(jié)果字符串中绑蔫；否則，直接返回當(dāng)前已經(jīng)匹配的前綴泵额。
最后返回結(jié)果字符串配深。

這種方法的時間復(fù)雜度為 O(nm)，其中 n 是字符串?dāng)?shù)組的長度嫁盲，m 是所有字符串中的字符數(shù)的最小值篓叶。

整數(shù)反轉(zhuǎn)

給你一個 32 位的有符號整數(shù) x ，返回將 x 中的數(shù)字部分反轉(zhuǎn)后的結(jié)果羞秤。
如果反轉(zhuǎn)后整數(shù)超過 32 位的有符號整數(shù)的范圍 [?231, 231 ? 1] 缸托，就返回 0。
假設(shè)環(huán)境不允許存儲 64 位整數(shù)（有符號或無符號）瘾蛋。

示例 1：
輸入：x = 123
輸出：321
示例 2：
輸入：x = -123
輸出：-321
示例 3：
輸入：x = 120
輸出：21
示例 4：
輸入：x = 0
輸出：0

+ (NSInteger)hy_reverseInteger:(NSInteger)x {
    NSInteger result = 0;
    while (x != 0) {
        // 取出最后一位數(shù)字
        NSInteger digit = x % 10;
        // 判斷是否會溢出
        if (result > INT_MAX / 10 || (result == INT_MAX / 10 && digit > 7)) {
            return 0;
        }
        if (result < INT_MIN / 10 || (result == INT_MIN / 10 && digit < -8)) {
            return 0;
        }
        // 將該位數(shù)字加入結(jié)果中
        result = result * 10 + digit;
        // 去掉已經(jīng)處理過的數(shù)字
        x /= 10;
    }
    return result;
}

注解：

• reverseInteger: 是該方法的名稱俐镐，輸入?yún)?shù)為一個 NSInteger 類型的整數(shù)，輸出也是一個 NSInteger 類型的整數(shù)哺哼。
• 初始化結(jié)果為 0佩抹。
• 循環(huán)取出給定整數(shù)的最后一位數(shù)字，并將其加入結(jié)果中幸斥。
• 在每次循環(huán)中判斷是否會溢出匹摇，如果超過了 32 位整數(shù)的范圍，則返回 0甲葬。
• 返回結(jié)果廊勃。
  該算法的時間復(fù)雜度為 O(log n)，空間復(fù)雜度為 O(1)经窖。

最長回文子串

給你一個字符串 s坡垫，找到 s 中最長的回文子串。
如果字符串的反序與原始字符串相同画侣，則該字符串稱為回文字符串冰悠。

示例 1：
輸入：s = "babad"
輸出："bab"
解釋："aba" 同樣是符合題意的答案。
示例 2：
輸入：s = "cbbd"
輸出："bb"

+ (NSString *)hy_longestPalindrome:(NSString *)s {
    NSInteger length = s.length;
    if (length < 2) {
        return s;
    }
    
    NSInteger start = 0;
    NSInteger maxLength = 1;
    for (NSInteger i = 0; i < length; i++) {
        // 尋找以i為中心的奇數(shù)長度的回文串
        NSInteger left = i - 1;
        NSInteger right = i + 1;
        while (left >= 0 && right < length && [s characterAtIndex:left] == [s characterAtIndex:right]) {
            left--;
            right++;
        }
        NSInteger oddLength = right - left - 1;
        
        // 尋找以i和i+1為中心的偶數(shù)長度的回文串
        left = i;
        right = i + 1;
        while (left >= 0 && right < length && [s characterAtIndex:left] == [s characterAtIndex:right]) {
            left--;
            right++;
        }
        NSInteger evenLength = right - left - 1;
        
        // 取最長的回文串
        NSInteger currentMaxLength = MAX(oddLength, evenLength);
        if (currentMaxLength > maxLength) {
            maxLength = currentMaxLength;
            start = i - (maxLength - 1) / 2;
        }
    }
    
    NSRange range = NSMakeRange(start, maxLength);
    NSString *result = [s substringWithRange:range];
    return result;
}

longestPalindrome: 是該方法的名稱配乱，輸入?yún)?shù)為一個 NSString 對象溉卓，輸出也是一個 NSString 對象。
首先判斷字符串長度是否小于 2搬泥，如果是桑寨，則直接返回原字符串。
初始化最長回文子串的起始位置為 0忿檩，長度為 1尉尾。
遍歷字符串中每個字符，以該字符為中心分別向左右擴(kuò)展燥透，尋找奇數(shù)長度和偶數(shù)長度的回文串沙咏，并記錄其長度辨图。
取兩種回文串中長度較大的一個，判斷是否比當(dāng)前最長回文子串的長度更長肢藐，如果是故河，則更新最長回文子串的起始位置和長度。
最后利用 substringWithRange 函數(shù)獲取最長回文子串吆豹，并返回忧勿。

通配符匹配

給你一個輸入字符串 (s) 和一個字符模式 (p) ，請你實(shí)現(xiàn)一個支持 '?' 和 '*' 匹配規(guī)則的通配符匹配： '?' 可以匹配任何單個字符瞻讽。
'*' 可以匹配任意字符序列（包括空字符序列）。
判定匹配成功的充要條件是：字符模式必須能夠 完全匹配 輸入字符串（而不是部分匹配）熏挎。

示例 1：
輸入：s = "aa", p = "a"
輸出：false
解釋："a" 無法匹配 "aa" 整個字符串速勇。
示例 2：
輸入：s = "aa", p = "*"
輸出：true
解釋：'*' 可以匹配任意字符串。
示例 3：
輸入：s = "cb", p = "?a"
輸出：false
解釋：'?' 可以匹配 'c', 但第二個 'a' 無法匹配 'b'坎拐。

- (BOOL)hy_isMatch:(NSString *)s pattern:(NSString *)p {
    NSInteger m = s.length;
    NSInteger n = p.length;
    
    // 創(chuàng)建一個二維數(shù)組 dp烦磁，用于存儲中間結(jié)果
    NSMutableArray<NSMutableArray<NSNumber *> *> *dp = [NSMutableArray arrayWithCapacity:m + 1];
    for (NSInteger i = 0; i <= m; i++) {
        NSMutableArray<NSNumber *> *row = [NSMutableArray arrayWithCapacity:n + 1];
        
        for (NSInteger j = 0; j <= n; j++) {
            [row addObject:@NO];
        }
        
        [dp addObject:row];
    }
    
    // 空字符串和空模式匹配
    dp[0][0] = @YES;
    
    // 處理第一行，即空字符串與非空模式
    for (NSInteger j = 1; j <= n; j++) {
        if ([p characterAtIndex:j - 1] == '*') {
            dp[0][j] = dp[0][j - 1];
        }
    }
    
    // 處理其余子問題
    for (NSInteger i = 1; i <= m; i++) {
        for (NSInteger j = 1; j <= n; j++) {
            unichar sc = [s characterAtIndex:i - 1];
            unichar pc = [p characterAtIndex:j - 1];
            
            // 如果當(dāng)前模式字符是通配符哼勇，則可以使用前面的結(jié)果
            if (pc == '*') {
                dp[i][j] = [NSNumber numberWithBool:(dp[i - 1][j].boolValue || dp[i][j - 1].boolValue)];

            } else if (pc == '?' || sc == pc) { // 如果當(dāng)前字符匹配都伪，則可以使用前面的結(jié)果
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }
    
    return [[dp lastObject] lastObject].boolValue;
}

該算法使用動態(tài)規(guī)劃方法實(shí)現(xiàn)通配符匹配。我們首先創(chuàng)建一個二維數(shù)組 dp积担，用于存儲中間結(jié)果陨晶。然后，我們將空字符串和空模式設(shè)置為匹配帝璧，并處理第一行先誉，即空字符串與非空模式。
接下來的烁，我們處理其余子問題褐耳。對于每個字符和模式字符組合，我們檢查以下三種情況：

• 如果當(dāng)前模式字符是通配符渴庆，則可以使用前面的結(jié)果铃芦。
• 如果當(dāng)前字符匹配，則可以使用前面的結(jié)果襟雷。
• 否則刃滓，當(dāng)前字符和模式字符無法匹配，因此不能使用前面的結(jié)果嗤军。
• 最終注盈，我們返回 dp[m][n]，其中 m 是輸入字符串的長度叙赚，n 是字符模式的長度老客。

找出字符串中第一個匹配項的下標(biāo)

給你兩個字符串 haystack 和 needle 僚饭，請你在 haystack 字符串中找出 needle 字符串的第一個匹配項的下標(biāo)（下標(biāo)從 0 開始）。如果 needle 不是 haystack 的一部分胧砰，則返回 -1 鳍鸵。

示例 1：

輸入：haystack = "sadbutsad", needle = "sad"
輸出：0
解釋："sad" 在下標(biāo) 0 和 6 處匹配。
第一個匹配項的下標(biāo)是 0 尉间，所以返回 0 偿乖。
示例 2：

輸入：haystack = "leetcode", needle = "leeto"
輸出：-1
解釋："leeto" 沒有在 "leetcode" 中出現(xiàn)，所以返回 -1 哲嘲。

+ (NSInteger)hy_strStr:(NSString *)haystack needle:(NSString *)needle {
    // 如果 needle 為空贪薪，則返回 0
    if (needle.length == 0) {
        return 0;
    }
    
    // 如果 haystack 長度小于 needle 長度，則直接返回 -1
    if (haystack.length < needle.length) {
        return -1;
    }
    
    NSInteger n = haystack.length;
    NSInteger m = needle.length;
    
    // 在 haystack 中滑動窗口眠副，并比較每個子串是否等于 needle
    for (NSInteger i = 0; i <= n - m; i++) {
        NSString *substring = [haystack substringWithRange:NSMakeRange(i, m)];
        
        if ([substring isEqualToString:needle]) {
            return i;
        }
    }
    
    // 如果找不到匹配項画切，則返回 -1
    return -1;
}

該算法使用滑動窗口方法，在輸入字符串 haystack 中查找字符串 needle 的第一個匹配項的下標(biāo)囱怕。

我們首先檢查 needle 是否為空霍弹。如果為空，則 haystack 中的任何位置都是匹配項娃弓，因此我們返回 0典格。

然后，我們檢查 haystack 的長度是否小于 needle 的長度台丛。如果是耍缴，則 needle 沒有可能成為 haystack 的子字符串，因此我們直接返回 -1齐佳。

接下來私恬，我們使用滑動窗口方法在 haystack 中遍歷每個子字符串，并比較其是否與 needle 相等炼吴。如果找到匹配項本鸣，則返回其下標(biāo)。

如果遍歷完 haystack 中的所有子字符串硅蹦，仍然找不到匹配項荣德，則返回 -1涮瞻。

電話號碼的字母組合

給定一個僅包含數(shù)字 2-9 的字符串假褪，返回所有它能表示的字母組合。答案可以按 任意順序 返回宁否。

給出數(shù)字到字母的映射如下（與電話按鍵相同）慕匠。注意 1 不對應(yīng)任何字母。

[圖片上傳失敗...(image-20567e-1683713324737)]

示例 1：
輸入：digits = "23"
輸出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
輸入：digits = ""
輸出：[]
示例 3：
輸入：digits = "2"
輸出：["a","b","c"]

+ (NSArray<NSString *> *)hy_letterCombinations:(NSString *)digits {
    // 創(chuàng)建字典台谊，用于存儲數(shù)字到字母的映射關(guān)系
    NSDictionary *keypad = @{
        @"2": @"abc",
        @"3": @"def",
        @"4": @"ghi",
        @"5": @"jkl",
        @"6": @"mno",
        @"7": @"pqrs",
        @"8": @"tuv",
        @"9": @"wxyz"
    };
    
    NSMutableArray<NSString *> *result = [NSMutableArray array];
    
    // 如果輸入字符串為空蓉媳，則直接返回空數(shù)組
    if (digits.length == 0) {
        return result;
    }
    
    // 初始化結(jié)果字符串和數(shù)字字符索引列表
    NSMutableString *current = [NSMutableString string];
    NSMutableArray<NSNumber *> *indices = [NSMutableArray arrayWithCapacity:digits.length];
    for (NSInteger i = 0; i < digits.length; i++) {
        [indices addObject:@(0)];
    }

    NSInteger pos = 0;
    
    while (pos >= 0) {
        NSString *digit = [digits substringWithRange:NSMakeRange(pos, 1)];
        NSString *letters = [keypad objectForKey:digit];
        NSInteger index = [[indices objectAtIndex:pos] integerValue];
        
        // 如果當(dāng)前位置已經(jīng)到達(dá)該數(shù)字對應(yīng)的字母末尾，則回溯到前一個數(shù)字
        if (index == letters.length) {
            pos--;
            continue;
        }
        
        // 否則锅铅，將當(dāng)前位置的字母添加到結(jié)果字符串中酪呻，并更新數(shù)字字符索引列表
        unichar letter = [letters characterAtIndex:index];
        [current appendFormat:@"%c", letter];
        [indices replaceObjectAtIndex:pos withObject:@(index + 1)];
        
        // 如果已經(jīng)處理完最后一個數(shù)字，則將結(jié)果字符串添加到結(jié)果列表中盐须，并回溯到前一個數(shù)字
        if (pos == digits.length - 1) {
            [result addObject:[NSString stringWithString:current]];
            pos--;
        } else {
            // 否則号杠，繼續(xù)處理下一個數(shù)字
            pos++;
            [indices replaceObjectAtIndex:pos withObject:@(0)];
        }
    }
    
    return result;
}

該算法使用回溯方法來生成所有可能的字母組合。我們首先創(chuàng)建一個字典丰歌，用于存儲數(shù)字到字母的映射關(guān)系。然后屉凯，我們初始化一個空數(shù)組作為結(jié)果列表立帖，并檢查輸入字符串是否為空。如果輸入字符串為空悠砚，則直接返回空數(shù)組晓勇。
在主循環(huán)中，我們從左到右遍歷數(shù)字字符灌旧，并使用數(shù)字到字母映射字典獲取對應(yīng)的字母集合绑咱。我們使用一個數(shù)字字符索引列表來跟蹤每個數(shù)字字符當(dāng)前使用的字母位置。
如果當(dāng)前數(shù)字字符已經(jīng)在其字母集合的末尾枢泰，則回溯到前一個數(shù)字字符，并繼續(xù)尋找可用的字母窿克。否則年叮，我們將當(dāng)前字母添加到結(jié)果字符串中，并更新數(shù)字字符索引列表跃惫。
如果已經(jīng)處理了最后一個數(shù)字字符衬横，則將結(jié)果字符串添加到結(jié)果列表中蜂林，并回溯到前一個數(shù)字字符。否則睁蕾，我們繼續(xù)處理下一個數(shù)字字符，并將其對應(yīng)的字母作為結(jié)果字符串的下一個字符臭杰。

最終，我們返回生成的所有結(jié)果字符串作為字母組合的列表磁奖。

羅馬數(shù)字轉(zhuǎn)整數(shù)

羅馬數(shù)字包含以下七種字符： I， V敢辩， X， L同廉，C锅劝，D 和 M。

例如诬垂， 羅馬數(shù)字 2 寫做 II ，即為兩個并列的 1隧枫。12 寫做 XII ，即為 X + II 确买。 27 寫做 XXVII, 即為 XX + V + II 芭商。

通常情況下榜苫，羅馬數(shù)字中小的數(shù)字在大的數(shù)字的右邊鉴竭。但也存在特例，例如 4 不寫做 IIII璧眠，而是 IV袁滥。數(shù)字 1 在數(shù)字 5 的左邊，所表示的數(shù)等于大數(shù) 5 減小數(shù) 1 得到的數(shù)值 4 嵌赠。同樣地，數(shù)字 9 表示為 IX初家。這個特殊的規(guī)則只適用于以下六種情況：

I 可以放在 V (5) 和 X (10) 的左邊，來表示 4 和 9掖肋。
X 可以放在 L (50) 和 C (100) 的左邊，來表示 40 和 90纫溃。
C 可以放在 D (500) 和 M (1000) 的左邊，來表示 400 和 900坊谁。

給定一個羅馬數(shù)字，將其轉(zhuǎn)換成整數(shù)阶界。

示例 1:

輸入: s = "III"
輸出: 3
示例 2:

輸入: s = "IV"
輸出: 4
示例 3:

輸入: s = "IX"
輸出: 9
示例 4:

輸入: s = "LVIII"
輸出: 58
解釋: L = 50, V= 5, III = 3.
示例 5:

輸入: s = "MCMXCIV"
輸出: 1994
解釋: M = 1000, CM = 900, XC = 90, IV = 4.

+ (NSInteger)hy_romanToInt:(NSString *)s {
    // 創(chuàng)建字典芙粱，用于存儲羅馬數(shù)字符號和對應(yīng)的阿拉伯?dāng)?shù)字值
    NSDictionary *romanValues = @{@"I": @1, @"V": @5, @"X": @10, @"L": @50, @"C": @100, @"D": @500, @"M": @1000};
    
    NSInteger result = 0;
    NSInteger prevValue = 0;
    
    // 從右到左遍歷羅馬數(shù)字字符
    for (NSInteger i = s.length - 1; i >= 0; i--) {
        NSString *symbol = [s substringWithRange:NSMakeRange(i, 1)];
        NSInteger value = [[romanValues objectForKey:symbol] integerValue];
        
        // 如果當(dāng)前值小于前一個值，則減去當(dāng)前值律姨；否則加上當(dāng)前值
        if (value < prevValue) {
            result -= value;
        } else {
            result += value;
        }
        
        prevValue = value;
    }
    
    return result;
}

該算法使用字典來存儲羅馬數(shù)字符號和對應(yīng)的阿拉伯?dāng)?shù)字值。然后荣赶，我們從右到左遍歷羅馬數(shù)字字符拔创，并計算每個字符的值。

如果當(dāng)前字符的值小于前一個字符的值灭红，則意味著需要減去當(dāng)前值。例如，在 IV 中澈段，第一個字符 I 的值為 1败富，而第二個字符 V 的值為 5芬骄。由于 I 在 V 的左邊，所以我們需要在 V 的值中減去 I 的值淘太，得到 4蒲牧。

如果當(dāng)前字符的值大于或等于前一個字符的值，則需要將該值添加到結(jié)果中。例如鼓鲁，在 IX 中骇吭，第一個字符 I 的值為 1，而第二個字符 X 的值為 10龙致。由于 I 在 X 的左邊，所以我們需要在 X 的值中加上 I 的值榛了，得到 9。

最終革答，我們返回計算出的整數(shù)值碟嘴。

整數(shù)轉(zhuǎn)羅馬數(shù)字

羅馬數(shù)字包含以下七種字符： I臀防， V， X致燥， L断傲，C箱蝠，D 和 M。

例如， 羅馬數(shù)字 2 寫做 II 憔足，即為兩個并列的 1滓彰。12 寫做 XII 稳析，即為 X + II 彰居。 27 寫做 XXVII, 即為 XX + V + II 畦徘。

通常情況下，羅馬數(shù)字中小的數(shù)字在大的數(shù)字的右邊。但也存在特例萍肆，例如 4 不寫做 IIII，而是 IV亲铡。數(shù)字 1 在數(shù)字 5 的左邊铁孵，所表示的數(shù)等于大數(shù) 5 減小數(shù) 1 得到的數(shù)值 4 。同樣地暑始，數(shù)字 9 表示為 IX唉俗。這個特殊的規(guī)則只適用于以下六種情況：

I 可以放在 V (5) 和 X (10) 的左邊雹姊，來表示 4 和 9股缸。
X 可以放在 L (50) 和 C (100) 的左邊，來表示 40 和 90吱雏。
C 可以放在 D (500) 和 M (1000) 的左邊敦姻，來表示 400 和 900。
給你一個整數(shù)歧杏，將其轉(zhuǎn)為羅馬數(shù)字镰惦。

示例 1:
輸入: num = 3
輸出: "III"

示例 2:
輸入: num = 4
輸出: "IV"

示例 3:
輸入: num = 9
輸出: "IX"

示例 4:
輸入: num = 58
輸出: "LVIII"
解釋: L = 50, V = 5, III = 3.

示例 5:
輸入: num = 1994
輸出: "MCMXCIV"
解釋: M = 1000, CM = 900, XC = 90, IV = 4.

+ (NSString *)hy_intToRoman:(NSInteger)num {
    // 創(chuàng)建兩個數(shù)組龄捡，分別存儲羅馬數(shù)字和對應(yīng)的阿拉伯?dāng)?shù)字值
    NSArray *romanValues = @[@1000, @900, @500, @400, @100, @90, @50, @40, @10, @9, @5, @4, @1];
    NSArray *romanSymbols = @[@"M", @"CM", @"D", @"CD", @"C", @"XC", @"L", @"XL", @"X", @"IX", @"V", @"IV", @"I"];
    
    NSMutableString *result = [NSMutableString string];
    
    // 從高位到低位遍歷每個阿拉伯?dāng)?shù)字值
    for (NSInteger i = 0; i < romanValues.count && num > 0; i++) {
        NSInteger value = [[romanValues objectAtIndex:i] integerValue];
        NSString *symbol = [romanSymbols objectAtIndex:i];
        
        // 計算當(dāng)前羅馬數(shù)字可以重復(fù)的次數(shù)
        NSInteger numSymbols = num / value;
        
        // 將當(dāng)前羅馬數(shù)字添加到結(jié)果字符串中血久，并減去相應(yīng)的值
        for (NSInteger j = 0; j < numSymbols; j++) {
            [result appendString:symbol];
        }
        
        num -= value * numSymbols;
    }
    
    return result;
}

該算法使用貪心策略來將整數(shù)轉(zhuǎn)換為羅馬數(shù)字翠拣。我們首先創(chuàng)建兩個數(shù)組畦娄，一個包含羅馬數(shù)字的符號，另一個包含羅馬數(shù)字的值乐严。然后，我們按遞減順序遍歷這兩個數(shù)組中的元素填物，直到整數(shù)值為零阅茶。
在每次迭代中蝌诡，我們計算當(dāng)前羅馬數(shù)字可以重復(fù)的次數(shù)植影，并將其添加到結(jié)果字符串中博投。同時，我們從整數(shù)值中減去相應(yīng)的阿拉伯?dāng)?shù)字值檐涝。

最終，我們返回結(jié)果字符串作為羅馬數(shù)字的表示形式。

字符串轉(zhuǎn)換整數(shù) (atoi)

請你來實(shí)現(xiàn)一個 myAtoi(string s) 函數(shù)招狸，使其能將字符串轉(zhuǎn)換成一個 32 位有符號整數(shù)（類似 C/C++ 中的 atoi 函數(shù)）。
函數(shù) myAtoi(string s) 的算法如下：
讀入字符串并丟棄無用的前導(dǎo)空格
檢查下一個字符（假設(shè)還未到字符末尾）為正還是負(fù)號绍傲，讀取該字符（如果有）群凶。 確定最終結(jié)果是負(fù)數(shù)還是正數(shù)巫员。 如果兩者都不存在司致，則假定結(jié)果為正恨搓。
讀入下一個字符茎辐，直到到達(dá)下一個非數(shù)字字符或到達(dá)輸入的結(jié)尾斋配。字符串的其余部分將被忽略。
將前面步驟讀入的這些數(shù)字轉(zhuǎn)換為整數(shù)（即及刻，"123" -> 123竞阐， "0032" -> 32）缴饭。如果沒有讀入數(shù)字，則整數(shù)為 0 馁菜。必要時更改符號（從步驟 2 開始）茴扁。
如果整數(shù)數(shù)超過 32 位有符號整數(shù)范圍 [?231, 231 ? 1] ，需要截斷這個整數(shù)汪疮，使其保持在這個范圍內(nèi)峭火。具體來說毁习，小于 ?231 的整數(shù)應(yīng)該被固定為 ?231 ，大于 231 ? 1 的整數(shù)應(yīng)該被固定為 231 ? 1 卖丸。
返回整數(shù)作為最終結(jié)果纺且。
注意：
本題中的空白字符只包括空格字符 ' ' 。
除前導(dǎo)空格或數(shù)字后的其余字符串外稍浆，請勿忽略 任何其他字符载碌。

示例 1：
輸入：s = "42"
輸出：42
解釋：加粗的字符串為已經(jīng)讀入的字符，插入符號是當(dāng)前讀取的字符衅枫。
第 1 步："42"（當(dāng)前沒有讀入字符嫁艇，因為沒有前導(dǎo)空格）
第 2 步："42"（當(dāng)前沒有讀入字符，因為這里不存在 '-' 或者 '+'）
第 3 步："42"（讀入 "42"）
解析得到整數(shù) 42 弦撩。
由于 "42" 在范圍 [-231, 231 - 1] 內(nèi)步咪，最終結(jié)果為 42 。

示例 2：
輸入：s = "   -42"
輸出：-42
解釋：
第 1 步："   -42"（讀入前導(dǎo)空格益楼，但忽視掉）
第 2 步："   -42"（讀入 '-' 字符猾漫，所以結(jié)果應(yīng)該是負(fù)數(shù)）
第 3 步："   -42"（讀入 "42"）
解析得到整數(shù) -42 。
由于 "-42" 在范圍 [-231, 231 - 1] 內(nèi)感凤，最終結(jié)果為 -42 悯周。

示例 3：
輸入：s = "4193 with words"
輸出：4193
解釋：
第 1 步："4193 with words"（當(dāng)前沒有讀入字符，因為沒有前導(dǎo)空格）
第 2 步："4193 with words"（當(dāng)前沒有讀入字符陪竿，因為這里不存在 '-' 或者 '+'）
第 3 步："4193 with words"（讀入 "4193"禽翼；由于下一個字符不是一個數(shù)字，所以讀入停止）
解析得到整數(shù) 4193 萨惑。
由于 "4193" 在范圍 [-231, 231 - 1] 內(nèi)捐康，最終結(jié)果為 4193 仇矾。

示例代碼

+ (int)hy_myAtoi:(NSString *)s {
    if (!s || s.length == 0) {
        return 0;
    }
    
    NSInteger i = 0;
    NSInteger sign = 1;
    NSInteger result = 0;
    
    // 移除前導(dǎo)空格
    while (i < s.length && [s characterAtIndex:i] == ' ') {
        i++;
    }
    
    // 處理正負(fù)號
    if (i < s.length && ([s characterAtIndex:i] == '+' || [s characterAtIndex:i] == '-')) {
        sign = [s characterAtIndex:i] == '-' ? -1 : 1;
        i++;
    }
    
    // 處理數(shù)字字符
    while (i < s.length && [s characterAtIndex:i] >= '0' && [s characterAtIndex:i] <= '9') {
        int digit = [s characterAtIndex:i] - '0';
        if (result > INT_MAX / 10 || (result == INT_MAX / 10 && digit > INT_MAX % 10)) {
            return sign == -1 ? INT_MIN : INT_MAX;
        }
        result = result * 10 + digit;
        i++;
    }
    
    return (int)(sign * result);
}

該算法首先移除前導(dǎo)空格庸蔼，并處理正負(fù)號。然后它逐個字符地讀取數(shù)字字符贮匕，并將其轉(zhuǎn)換為整數(shù)姐仅。如果整數(shù)超出了 32 位有符號整數(shù)范圍，則會截斷該整數(shù)以使其保持在此范圍內(nèi)刻盐。
要使用該函數(shù)掏膏，請調(diào)用 myAtoi 方法，并將要轉(zhuǎn)換的字符串作為參數(shù)傳遞給它敦锌。

無重復(fù)字符的最長子串

給定一個字符串 s 馒疹，請你找出其中不含有重復(fù)字符的 最長子串 的長度。

示例 1:
輸入: s = "abcabcbb"
輸出: 3 
解釋: 因為無重復(fù)字符的最長子串是 "abc"乙墙，所以其長度為 3颖变。
示例 2:
輸入: s = "bbbbb"
輸出: 1
解釋: 因為無重復(fù)字符的最長子串是 "b"生均，所以其長度為 1。

示例 3:
輸入: s = "pwwkew"
輸出: 3
解釋: 因為無重復(fù)字符的最長子串是 "wke"腥刹，所以其長度為 3马胧。
     請注意，你的答案必須是 子串 的長度衔峰，"pwke" 是一個子序列佩脊，不是子串。

示例代碼

- (NSInteger)hy_lengthOfLongestSubstring:(NSString *)s {
    if (s.length == 0) {
        return 0;
    }
    
    NSInteger maxLength = 0;
    NSInteger left = 0, right = 0;
    NSMutableDictionary *charDict = [NSMutableDictionary dictionary];
    
    while (right < s.length) {
        NSString *currentChar = [s substringWithRange:NSMakeRange(right, 1)];
        if ([charDict objectForKey:currentChar]) {
            NSNumber *prevIndex = [charDict objectForKey:currentChar];
            left = MAX(left, prevIndex.integerValue + 1);
        }
        
        [charDict setObject:@(right) forKey:currentChar];
        maxLength = MAX(maxLength, right - left + 1);
        right++;
    }
    
    return maxLength;
}

這個算法的基本思想是使用滑動窗口來維護(hù)最長不重復(fù)子串垫卤。我們使用兩個指針 left 和 right 來表示當(dāng)前窗口的左右邊界威彰。我們還使用一個字典來存儲每個字符在字符串中出現(xiàn)的最后位置（即上一次出現(xiàn)的位置）。
當(dāng)我們移動 right 指針時穴肘，我們檢查當(dāng)前字符是否已經(jīng)在窗口中出現(xiàn)抱冷。如果是，則更新 left 指針以跳過前面的所有重復(fù)字符梢褐，并且將當(dāng)前字符的位置添加到字典中旺遮。同時，我們還需要更新最長不重復(fù)子串的長度盈咳。
要找到字符串中的最長不重復(fù)子串長度耿眉，只需調(diào)用 lengthOfLongestSubstring 方法，并將要計算的字符串作為參數(shù)傳遞給它即可鱼响。

正則表達(dá)式匹配-提取字符串中的數(shù)字

給你一個字符串 s 和一個字符規(guī)律 p鸣剪，請你來實(shí)現(xiàn)一個支持 '.' 和 '*' 的正則表達(dá)式匹配。
'.' 匹配任意單個字符
'*' 匹配零個或多個前面的那一個元素
所謂匹配丈积，是要涵蓋 整個 字符串 s的筐骇，而不是部分字符串。

示例 1：
輸入：s = "aa", p = "a"
輸出：false
解釋："a" 無法匹配 "aa" 整個字符串江滨。

示例 2:
輸入：s = "aa", p = "a*"
輸出：true
解釋：因為 '*' 代表可以匹配零個或多個前面的那一個元素, 在這里前面的元素就是 'a'铛纬。因此，字符串 "aa" 可被視為 'a' 重復(fù)了一次唬滑。

示例 3：
輸入：s = "ab", p = ".*"
輸出：true
解釋：".*" 表示可匹配零個或多個（'*'）任意字符（'.'）告唆。

Code

+ (BOOL)hy_isMatch:(NSString *)s withPattern:(NSString *)p {
    if (!p || p.length == 0) {
        return !s || s.length == 0;
    }
    
    BOOL firstMatch = s && s.length > 0 && ([p characterAtIndex:0] == [s characterAtIndex:0] || [p characterAtIndex:0] == '.');
    
    if (p.length >= 2 && [p characterAtIndex:1] == '*') {
        return [self hy_isMatch:s withPattern:[p substringFromIndex:2]] || (firstMatch && [self hy_isMatch:[s substringFromIndex:1] withPattern:p]);
    } else {
        return firstMatch && [self hy_isMatch:[s substringFromIndex:1] withPattern:[p substringFromIndex:1]];
    }
}

該算法使用遞歸來實(shí)現(xiàn)正則表達(dá)式匹配。它首先檢查字符規(guī)律是否為空晶密。如果是擒悬，則返回 true 如果要匹配的字符串為空；否則稻艰，如果要匹配的字符串不為空懂牧，則返回 false。
然后尊勿，算法檢查模式的第一個字符是否與字符串的第一個字符匹配僧凤。如果相匹配用狱，則算法將繼續(xù)對剩余的字符串和模式進(jìn)行匹配。如果模式的下一個字符是 '*'拼弃，則算法可以選擇跳過該字符或重復(fù)前一個字符夏伊，并在兩種情況下繼續(xù)遞歸搜索。
最后吻氧，如果整個字符串都已匹配溺忧，并且整個模式也已處理完畢，則返回 true盯孙；否則鲁森，如果字符串沒有全部匹配或者模式仍然存在未處理的字符，則返回 false振惰。

有效數(shù)字

有效數(shù)字（按順序）可以分成以下幾個部分：
一個 小數(shù) 或者 整數(shù)
（可選）一個 'e' 或 'E' 歌溉，后面跟著一個 整數(shù)
小數(shù)（按順序）可以分成以下幾個部分：
（可選）一個符號字符（'+' 或 '-'）
下述格式之一：
至少一位數(shù)字，后面跟著一個點(diǎn) '.'
至少一位數(shù)字骑晶，后面跟著一個點(diǎn) '.' 痛垛，后面再跟著至少一位數(shù)字
一個點(diǎn) '.' ，后面跟著至少一位數(shù)字
整數(shù)（按順序）可以分成以下幾個部分：
（可選）一個符號字符（'+' 或 '-'）
至少一位數(shù)字
部分有效數(shù)字列舉如下：["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"]
部分無效數(shù)字列舉如下：["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"]
給你一個字符串 s 桶蛔，如果 s 是一個 有效數(shù)字 匙头，請返回 true 。

示例 1：

輸入：s = "0"
輸出：true
示例 2：

輸入：s = "e"
輸出：false
示例 3：

輸入：s = "."
輸出：false

typedef NS_ENUM(NSInteger, HYNumberState) {
    STATE_INITIAL,              // 初始狀態(tài)
    STATE_INT_SIGN,             // 整數(shù)符號狀態(tài)
    STATE_INTEGER,              // 整數(shù)狀態(tài)
    STATE_POINT,                // 小數(shù)點(diǎn)狀態(tài)
    STATE_POINT_WITHOUT_INT,    // 前面無整數(shù)小數(shù)點(diǎn)狀態(tài)
    STATE_FRACTION,             // 小數(shù)狀態(tài)
    STATE_EXP,                  // 指數(shù)字符狀態(tài)
    STATE_EXP_SIGN,             // 指數(shù)符號狀態(tài)
    STATE_EXP_NUMBER,           // 指數(shù)數(shù)字狀態(tài)
    STATE_END                   // 結(jié)束狀態(tài)
};

typedef NS_ENUM(NSInteger, HYNumberCharType) {
    CHAR_NUMBER,                // 數(shù)字類型
    CHAR_EXP,                   // 指數(shù)字符類型
    CHAR_POINT,                 // 小數(shù)點(diǎn)類型
    CHAR_SIGN,                  // 符號類型
    CHAR_ILLEGAL                // 非法字符類型
};


+ (BOOL)hy_isNumber:(NSString *)s {
    // 定義狀態(tài)轉(zhuǎn)移規(guī)則字典
       NSDictionary *stateMap = @{
           @(STATE_INITIAL): @{
               @(CHAR_NUMBER): @(STATE_INTEGER),
               @(CHAR_POINT): @(STATE_POINT_WITHOUT_INT),
               @(CHAR_SIGN): @(STATE_INT_SIGN)
           },
           @(STATE_INT_SIGN): @{
               @(CHAR_NUMBER): @(STATE_INTEGER),
               @(CHAR_POINT): @(STATE_POINT_WITHOUT_INT)
           },
           @(STATE_INTEGER): @{
               @(CHAR_NUMBER): @(STATE_INTEGER),
               @(CHAR_EXP): @(STATE_EXP),
               @(CHAR_POINT): @(STATE_POINT)
           },
           @(STATE_POINT): @{
               @(CHAR_NUMBER): @(STATE_FRACTION),
               @(CHAR_EXP): @(STATE_EXP)
           },
           @(STATE_POINT_WITHOUT_INT): @{
               @(CHAR_NUMBER): @(STATE_FRACTION)
           },
           @(STATE_FRACTION): @{
               @(CHAR_NUMBER): @(STATE_FRACTION),
               @(CHAR_EXP): @(STATE_EXP)
           },
           @(STATE_EXP): @{
               @(CHAR_NUMBER): @(STATE_EXP_NUMBER),
               @(CHAR_SIGN): @(STATE_EXP_SIGN)
           },
           @(STATE_EXP_SIGN): @{
               @(CHAR_NUMBER): @(STATE_EXP_NUMBER)
           },
           @(STATE_EXP_NUMBER): @{
               @(CHAR_NUMBER): @(STATE_EXP_NUMBER)
           }
       };
       
    HYNumberState state = STATE_INITIAL;            // 初始狀態(tài)為 STATE_INITIAL
    NSUInteger length = [s length];         // 輸入字符串的長度
       
    for (NSUInteger i = 0; i < length; i++) {
        HYNumberCharType type = [self toCharType:[s characterAtIndex:i]];   // 將當(dāng)前字符轉(zhuǎn)換成字符類型
        if (![stateMap[@(state)] objectForKey:@(type)]) {          // 如果當(dāng)前狀態(tài)不能接受該類型的字符
            return NO;                                              // 直接返回 NO仔雷，說明輸入的字符串不是一個有效數(shù)字
        } else {
            state = [[stateMap[@(state)] objectForKey:@(type)] integerValue];   // 根據(jù)狀態(tài)轉(zhuǎn)移規(guī)則將狀態(tài)轉(zhuǎn)移到下一個狀態(tài)
        }
    }
    
    return state == STATE_INTEGER || state == STATE_POINT || state == STATE_FRACTION || state == STATE_EXP_NUMBER || state == STATE_END;  // 最終狀態(tài)必須為有效數(shù)字的結(jié)束狀態(tài)之一
}

+(HYNumberCharType)toCharType:(unichar)ch {
    if (ch >= '0' && ch <= '9') {           // 如果當(dāng)前字符是數(shù)字
        return CHAR_NUMBER;
    } else if (ch == 'e' || ch == 'E') {    // 如果當(dāng)前字符是指數(shù)字符
        return CHAR_EXP;
    } else if (ch == '.') {                 // 如果當(dāng)前字符是小數(shù)點(diǎn)
        return CHAR_POINT;
    } else if (ch == '+' || ch == '-') {   // 如果當(dāng)前字符是符號
        return CHAR_SIGN;
    } else {
        return CHAR_ILLEGAL;                // 否則為非法字符類型
    }
}

該實(shí)現(xiàn)首先定義了一個有限狀態(tài)機(jī)蹂析，其中每個狀態(tài)都是一個對象，其屬性表示在該狀態(tài)下接受的字符類型以及轉(zhuǎn)移后的狀態(tài)碟婆。具體而言电抚，有以下幾種字符類型：空格、符號（+/-）竖共、數(shù)字蝙叛、小數(shù)點(diǎn)、e/E和無效字符肘迎。其中甥温，狀態(tài)0表示起始狀態(tài)锻煌，在該狀態(tài)下可以接受的字符類型有空格妓布、符號、數(shù)字和小數(shù)點(diǎn)宋梧；狀態(tài)3匣沼、4、5捂龄、8和9分別表示不同的有效數(shù)字結(jié)束狀態(tài)释涛，如果最終狀態(tài)為這些狀態(tài)之一加叁，則說明輸入的字符串是一個有效數(shù)字。

接下來唇撬，使用一個循環(huán)遍歷輸入字符串中的每個字符它匕。在循環(huán)體中，首先判斷當(dāng)前字符屬于哪種類型窖认；然后豫柬，查找當(dāng)前狀態(tài)能否接受該類型的字符，如果不能扑浸，則說明輸入的字符串不是一個有效數(shù)字烧给，可以直接返回false；否則喝噪，將狀態(tài)轉(zhuǎn)移為下一個狀態(tài)础嫡。最后，檢查最終狀態(tài)是否為有效數(shù)字的結(jié)束狀態(tài)之一酝惧，如果是榴鼎，則返回true，否則返回false晚唇。