LeetCode 第29题、30题
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的溢出
- 将问题转化为负数处理：
- 记录结果符号
- 转换为负数避免溢出
- 使用位移和减法计算商：
- 找到最大的移位次数
- 累加商的结果
- 根据符号返回最终结果
- 时间复杂度：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;}}