LeetCode 第29題：兩數相除

題目描述

給你兩個整數，被除數dividend和除數divisor。將兩數相除，要求不使用乘法、除法和取余運算。整數除法應該向零截斷，也就是截去其小數部分。例如，8.345將被截斷為8，-2.7335將被截斷為-2，返回被除數除以除數得到的商。

注意：假設環境只能存儲32位有符號整數，其數值范圍是[-2^31，2^31-1]。本題中如果商大于2^31-1，則返回2^31-1;如果商小于-2^31，則返回-2^31。

難度：中等
題目鏈接：29. 兩數相除 - 力扣（LeetCode）

示例1：

輸入：dividend = 10, divisor = 3
輸出：3
解釋：10/3 = 3.33333... ，向零截斷后得到 3

?示例2：

輸入：dividend = 7, divisor = -3
輸出：-2
解釋：7/-3 = -2.33333... ，向零截斷后得到 -2

提示：

• -2^31<=dividend,divisor<=2^31-1
• divisor!=0

解題思路

方法：優化的位運算
使用位運算和減法來實現除法，通過將除法轉換為減法并使用位移來優化性能。

• ?處理特殊情況

1. 處理除數為±1的情況
2. 處理最小值除以-1的溢出

• 將問題轉化為負數處理：

1. 記錄結果符號
2. 轉換為負數避免溢出

• 使用位移和減法計算商：

1. 找到最大的移位次數
2. 累加商的結果

• 根據符號返回最終結果
• 時間復雜度：O(log n)
• 空間復雜度：O（1）

public class Solution
{public int Divide(int dividend,int divisor){//處理特殊情況if(dividend == int.MinValue && divisor==-1)  return int.MaxValue;if(divisor==1)  return dividend;if(divisor==-1)  return -dividend;//記錄符號并轉換為負數處理（避免溢出）bool isnegative  = (dividend>0) ^ (divisor>0);int a= dividend>0 ? -dividend : dividend;int b= divisor>0 ? -divisor:divisor;//計算int result=0;while(a<=b){int temp=b;int multiple = -1;//找到最大的移位次數while(temp>=(int.MinValue>>1) && a<=(temp<<1)){temp<<=1;multiple<<=1;}a=a-temp;result= result+multiple;}return isnegative ? result:-result;}
}

LeetCode 第30題：串聯所有單詞的子串

題目描述

給定一個字符串s和一個字符串數組words。words中所有字符串長度相同。

s中的串聯子串是指一個包含words中所有words中所有字符串以任意順序排列連接起來的子串。

例如，如果words = ["ab"，“cd”，“ef”]，那么“abcdef""，“”abefcd“，”cdabef“，”cdefab“，”efabcd“，”efcdab“都是串聯子串。”acdbef“不是串聯子串，因為他不是任何words排列的連接。返回所有串聯子串在s中的開始索引。你可以以任意順序返回答案。

難度：困難

題目鏈接：30. 串聯所有單詞的子串 - 力扣（LeetCode）

示例1：

輸入：s = "barfoothefoobarman", words = ["foo","bar"]
輸出：[0,9]
解釋：串聯子串的起始位置為：
- 0："barfoo" 是 ["bar","foo"] 的串聯
- 9："foobar" 是 ["foo","bar"] 的串聯

?示例2：
?

輸入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
輸出：[]
解釋：不存在串聯子串

提示：

• 1<=s.length<=104
• 1<=words.length<=5000
• 1<=words[i].length<=30
• words[i]和s由小寫英文字母組成

解題思路：滑動窗口+哈希表

關鍵點：

• 所有單詞長度相同，這是一個重要的條件。
• 需要考慮所有可能的起始位置
• 使用哈希表記錄單詞出現次數

具體步驟：

• 預處理：統計words中每個單詞的出現次數
• 滑動窗口：遍歷所有可能的起始位置
• 驗證過程：檢查當前窗口中的單詞是否符合要求

public calss Solution
{public IList<int> FindSubstring(string s,string[] words){List<int> result = new List<int>();if(string.IsNullOrEmpty(s) || words ==null || words.Length==0)  return result;Dictionary<string,int> wordCount = new Dictionary<string,int>();foreach(string word in words){if(!wordCount.ContainsKey(word))   wordCount[word]=0;wordCount[word]++;}int wordLength = words[0].Length;int totalLength = wordLength * words.Length;for(int i=0;i<=s.Length - totalLength;i++){Dictionary<string,int> seenWords = new Dictionary<string,int>();int j;for(j=0;j<words.Length;j++){int startPos = i+j*wordLength;string currentWord = s.Substring(startPos,wordLength);if(!wordCount.ContainsKey(currentWord))  break;if(!seenWords.ContainsKey(currentWord)) seenWord[currentWord]=0;seenWords[currentWord]++;if(seenWords[currentWord]>wordCount[currentWord])  break;}}if(j==words.Length)  result.Add(i);return result;}}