建设旅游景点的网站的好处,外贸公司系统管理软件,怎么搜索关键词,企业公示信息查询系统浙江前言
本题解Go语言部分基于 LeetCode-Go 其他部分基于本人实践学习 个人题解GitHub连接#xff1a;LeetCode-Go-Python-Java-C Go-Python-Java-C-LeetCode高分解法-第一周合集 Go-Python-Java-C-LeetCode高分解法-第二周合集 Go-Python-Java-C-LeetCode高分解法-第三周合集 G…前言
本题解Go语言部分基于 LeetCode-Go 其他部分基于本人实践学习 个人题解GitHub连接LeetCode-Go-Python-Java-C Go-Python-Java-C-LeetCode高分解法-第一周合集 Go-Python-Java-C-LeetCode高分解法-第二周合集 Go-Python-Java-C-LeetCode高分解法-第三周合集 Go-Python-Java-C-LeetCode高分解法-第四周合集 本文部分内容来自网上搜集与个人实践。如果任何信息存在错误,欢迎读者批评指正。本文仅用于学习交流,不用作任何商业用途。
29. Divide Two Integers
题目
Given two integersdividendanddivisor, divide two integers without using multiplication, division and mod operator.
Return the quotient after dividingdividendbydivisor.
The integer division should truncate toward zero.
Example 1:
Input: dividend 10, divisor 3
Output: 3Example 2:
Input: dividend 7, divisor -3
Output: -2Note:
Both dividend and divisor will be 32-bit signed integers.The divisor will never be 0.Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. For the purpose of this problem, assume that your function returns 2^31 − 1 when the division result overflows.
题目大意
给定两个整数被除数 dividend 和除数 divisor。将两数相除要求不使用乘法、除法和 mod 运算符。返回被除数 dividend 除以除数 divisor 得到的商。
说明:
被除数和除数均为 32 位有符号整数。除数不为 0。假设我们的环境只能存储 32 位有符号整数其数值范围是 [−2^31, 2^31 − 1]。本题中如果除法结果溢出则返回 2^31 − 1。
解题思路
给出除数和被除数要求计算除法运算以后的商。注意值的取值范围在 [−2^31, 2^31 − 1] 之中。超过范围的都按边界计算。这一题可以用二分搜索来做。要求除法运算之后的商把商作为要搜索的目标。商的取值范围是 [0, dividend]所以从 0 到被除数之间搜索。利用二分找到(商 1 ) * 除数 被除数并且 商 * 除数 ≤ 被除数 或者 (商1)* 除数 ≥ 被除数并且商 * 除数 被除数的时候就算找到了商其余情况继续二分即可。最后还要注意符号和题目规定的 Int32 取值范围。二分的写法常写错的 3 点 low ≤ high (注意二分循环退出的条件是小于等于)mid low (high-low)1 (防止溢出)low mid 1 ; high mid - 1 (注意更新 low 和 high 的值如果更新不对就会死循环) 以下是每个版本的解题思路的详细介绍
Go 版本
Go 版本的解题思路如下 首先处理特殊情况包括被除数dividend等于 0除数divisor等于 1以及避免溢出的情况例如被除数为math.MinInt32除数为-1。 确定最终结果的符号正数或负数并将被除数和除数都转换为正数以便进行位运算。 使用二分搜索来找到商。二分搜索的目标是找到一个整数 x使得 (x 1) * divisor dividend 且 x * divisor ≤ dividend或者 (x 1) * divisor ≥ dividend 且 x * divisor dividend。这个 x 就是我们要找的商。 在二分搜索的过程中确保更新搜索的范围和值同时处理可能的溢出情况。 最后根据符号和边界情况返回最终的商。
Python 版本
Python 版本的解题思路如下 处理特殊情况包括被除数等于 0除数等于 1以及避免溢出的情况例如被除数为-2^31除数为-1。 确定最终结果的符号正数或负数并将被除数和除数都转换为正数以便进行位运算。 使用递归的二分搜索方法来找到商。递归函数的目标是找到一个整数 x使得 (x 1) * divisor dividend 且 x * divisor ≤ dividend或者 (x 1) * divisor ≥ dividend 且 x * divisor dividend。这个 x 就是我们要找的商。 在递归的过程中确保更新搜索的范围和值同时处理可能的溢出情况。 最后根据符号和边界情况返回最终的商。
Java 版本
Java 版本的解题思路如下 处理特殊情况包括被除数等于 0除数等于 1以及避免溢出的情况例如被除数为Integer.MIN_VALUE除数为-1。 确定最终结果的符号正数或负数并将被除数和除数都转换为正数以便进行位运算。 使用递归的二分搜索方法来找到商。递归函数的目标是找到一个整数 x使得 (x 1) * divisor dividend 且 x * divisor ≤ dividend或者 (x 1) * divisor ≥ dividend 且 x * divisor dividend。这个 x 就是我们要找的商。 在递归的过程中确保更新搜索的范围和值同时处理可能的溢出情况。 最后根据符号和边界情况返回最终的商。
C 版本
C 版本的解题思路如下 处理特殊情况包括被除数等于 0除数等于 1以及避免溢出的情况例如被除数为INT_MIN除数为-1。 确定最终结果的符号正数或负数并将被除数和除数都转换为正数以便进行位运算。 使用递归的二分搜索方法来找到商。递归函数的目标是找到一个整数 x使得 (x 1) * divisor dividend 且 x * divisor ≤ dividend或者 (x 1) * divisor ≥ dividend 且 x * divisor dividend。这个 x 就是我们要找的商。 在递归的过程中确保更新搜索的范围和值同时处理可能的溢出情况。 最后根据符号和边界情况返回最终的商。
总之这些解决方案的核心思想都是使用二分搜索来找到商同时处理特殊情况和溢出情况以确保最终的计算结果正确。递归函数在实现中被广泛用于搜索过程。
代码
Go
func abs(x int) int {if x 0 {return -x}return x
}// 解法一 递归版的二分搜索
func divide(dividend int, divisor int) int {sign, res : -1, 0// low, high : 0, abs(dividend)if dividend 0 {return 0}if divisor 1 {return dividend}if dividend math.MinInt32 divisor -1 {return math.MaxInt32}if dividend 0 divisor 0 || dividend 0 divisor 0 {sign 1}if dividend math.MaxInt32 {dividend math.MaxInt32}// 调用二分搜索函数计算商res binarySearchQuotient(0, abs(dividend), abs(divisor), abs(dividend))// 处理溢出情况if res math.MaxInt32 {return sign * math.MaxInt32}if res math.MinInt32 {return sign * math.MinInt32}return sign * res
}// 二分搜索函数用于计算商
func binarySearchQuotient(low, high, val, dividend int) int {quotient : low (high-low)1if ((quotient1)*val dividend quotient*val dividend) || ((quotient1)*val dividend quotient*val dividend) {if (quotient1)*val dividend {return quotient 1}return quotient}if (quotient1)*val dividend quotient*val dividend {return binarySearchQuotient(low, quotient-1, val, dividend)}if (quotient1)*val dividend quotient*val dividend {return binarySearchQuotient(quotient1, high, val, dividend)}return 0
}func abs(x int) int {if x 0 {return -x}return x
}// 解法二 非递归版的二分搜索
func divide(dividend int, divisor int) int {if dividend math.MinInt32 divisor -1 {return math.MaxInt32}result : 0sign : -1if dividend 0 divisor 0 || dividend 0 divisor 0 {sign 1}dividendAbs, divisorAbs : abs(dividend), abs(divisor)for dividendAbs divisorAbs {temp : divisorAbsmultiplier : 1for temp1 dividendAbs {temp 1multiplier 1}dividendAbs - tempresult multiplier}return sign * result
}Python
class Solution:def divide(self, dividend: int, divisor: int) - int:# 递归版def recursive_divide(dividend, divisor):if dividend divisor:return 0quotient 1div divisorwhile (div div) dividend:div divquotient quotientreturn quotient recursive_divide(dividend - div, divisor)if dividend 0:return 0if dividend -2 ** 31 and divisor -1:return 2 ** 31 - 1sign 1 if (dividend 0) (divisor 0) else -1dividend, divisor abs(dividend), abs(divisor)result recursive_divide(dividend, divisor)return sign * resultclass Solution:# 非递归版def divide(self, dividend: int, divisor: int) - int:if dividend 0:return 0if dividend -2 ** 31 and divisor -1:return 2 ** 31 - 1sign 1 if (dividend 0) (divisor 0) else -1dividend, divisor abs(dividend), abs(divisor)result 0while dividend divisor:temp, m divisor, 1while dividend (temp 1):temp 1m 1dividend - tempresult mreturn sign * resultJava
class Solution {public int divide(int dividend, int divisor) {// 递归版if (dividend 0) {return 0;}if (dividend Integer.MIN_VALUE divisor -1) {return Integer.MAX_VALUE;}int sign (dividend 0) (divisor 0) ? 1 : -1;long dvd Math.abs((long) dividend);long dvs Math.abs((long) divisor);int result recursiveDivide(dvd, dvs);return sign * result;}private int recursiveDivide(long dividend, long divisor) {if (dividend divisor) {return 0;}int quotient 1;long div divisor;while ((div div) dividend) {div div;quotient quotient;}return quotient recursiveDivide(dividend - div, divisor);}}
class Solution {// 非递归版public int divide(int dividend, int divisor) {if (dividend 0) {return 0;}if (dividend Integer.MIN_VALUE divisor -1) {return Integer.MAX_VALUE;}int sign (dividend 0) (divisor 0) ? 1 : -1;long dvd Math.abs((long) dividend);long dvs Math.abs((long) divisor);int result 0;while (dvd dvs) {long temp dvs;int m 1;while (dvd (temp 1)) {temp 1;m 1;}dvd - temp;result m;}return sign * result;}
}Cpp
class Solution {
public:int divide(int dividend, int divisor) {// 处理特殊情况if (dividend 0) {return 0;}if (divisor 1) {return dividend;}if (dividend INT_MIN divisor -1) {return INT_MAX;}int sign (dividend 0 divisor 0) || (dividend 0 divisor 0) ? 1 : -1;// 处理溢出情况if (dividend INT_MAX) {dividend INT_MAX;}return sign * binarySearchQuotient(0, abs((long)dividend), abs((long)divisor), abs((long)dividend));}private:int binarySearchQuotient(long low, long high, long val, long dividend) {long quotient low (high - low) / 2;if (((quotient 1) * val dividend quotient * val dividend) || ((quotient 1) * val dividend quotient * val dividend)) {if ((quotient 1) * val dividend) {return quotient 1;}return quotient;}if ((quotient 1) * val dividend quotient * val dividend) {return binarySearchQuotient(low, quotient - 1, val, dividend);}if ((quotient 1) * val dividend quotient * val dividend) {return binarySearchQuotient(quotient 1, high, val, dividend);}return 0;}
};class Solution {
public:int divide(int dividend, int divisor) {// 处理特殊情况if (dividend INT_MIN divisor -1) {return INT_MAX;}int result 0;int sign (dividend 0 divisor 0) || (dividend 0 divisor 0) ? 1 : -1;long dvd abs((long)dividend);long dvs abs((long)divisor);while (dvd dvs) {long temp dvs;long m 1;while (temp 1 dvd) {temp 1;m 1;}dvd - temp;// 处理溢出情况if (result INT_MAX - m) {return sign 1 ? INT_MAX : INT_MIN;}result m;}return sign * result;}
};
当讨论每个版本的解决方案时我将分开介绍所需的详细基础知识。
Go 版本 Go 语言基础: 在理解 Go 版本的解决方案之前您需要熟悉 Go 语言的基础知识包括变量、函数、条件语句、循环等。 递归: Go 版本的解决方案中使用了递归来实现二分搜索因此需要了解递归的概念和用法。 位运算: Go 版本中使用位运算来处理细节如符号、边界情况等。因此您需要了解 Go 中的位运算操作符如、和位运算的基本原理。 边界情况处理: 了解如何处理边界情况是解决这个问题的关键之一因为输入和输出受到了限制。需要考虑最小和最大的 32 位有符号整数。
Python 版本 Python 语言基础: 您需要熟悉 Python 语言的基础知识包括变量、函数、条件语句、循环以及整数溢出处理。 递归: Python 版本中的递归解决方案使用了递归函数来实现二分搜索。您需要了解如何编写递归函数以及递归的工作原理。 位运算: 位运算在 Python 版本中也被用于处理符号和边界情况。了解 Python 中的位运算操作符如、和位运算的基本原理将有助于理解解决方案。
Java 版本 Java 语言基础: 在理解 Java 版本的解决方案之前您需要熟悉 Java 语言的基础知识包括类、方法、条件语句、循环以及整数溢出处理。 递归: Java 版本的解决方案使用了递归函数来实现二分搜索。您需要了解如何编写递归函数以及递归的工作原理。 位运算: 位运算在 Java 版本中用于处理符号和边界情况。了解 Java 中的位运算操作符如、和位运算的基本原理将有助于理解解决方案。 整数溢出处理: Java 版本考虑了整数溢出情况并采取了措施来防止溢出。您需要了解 Java 中整数溢出的特点以及如何处理它。
C 版本 C 语言基础: 在理解 C 版本的解决方案之前您需要熟悉 C 语言的基础知识包括类、函数、条件语句、循环以及整数溢出处理。 递归: C 版本的解决方案使用了递归函数来实现二分搜索。您需要了解如何编写递归函数以及递归的工作原理。 位运算: 位运算在 C 版本中用于处理符号和边界情况。了解 C 中的位运算操作符如、和位运算的基本原理将有助于理解解决方案。 整数溢出处理: C 版本考虑了整数溢出情况并采取了措施来防止溢出。您需要了解 C 中整数溢出的特点以及如何处理它。
总之理解每个版本的解决方案需要对编程语言的基础知识、递归、位运算和整数溢出处理有一定的了解。此外了解问题的特殊要求和边界情况也是解决这个问题的关键。
30. Substring with Concatenation of All Words
题目
You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
Example 1:
Input:s barfoothefoobarman,words [foo,bar]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are barfoor and foobar respectively.
The output order does not matter, returning [9,0] is fine too.Example 2:
Input:s wordgoodgoodgoodbestword,words [word,good,best,word]
Output: []题目大意
给定一个源字符串 s再给一个字符串数组要求在源字符串中找到由字符串数组各种组合组成的连续串的起始下标如果存在多个在结果中都需要输出。
解题思路
这一题看似很难但是有 2 个限定条件也导致这题不是特别难。1. 字符串数组里面的字符串长度都是一样的。2. 要求字符串数组中的字符串都要连续连在一起的前后顺序可以是任意排列组合。
解题思路先将字符串数组里面的所有字符串都存到 map 中并累计出现的次数。然后从源字符串从头开始扫每次判断字符串数组里面的字符串时候全部都用完了(计数是否为 0) 如果全部都用完了并且长度正好是字符串数组任意排列组合的总长度就记录下这个组合的起始下标。如果不符合就继续考察源字符串的下一个字符直到扫完整个源字符串。 下面我将分别介绍每个版本的解题思路
Go 版本 初始化变量 获取输入字符串 s 的长度 ls单词数组 words 的长度 m以及单词的长度 n。初始化一个空的整数切片 ans 用于存储结果。 主循环 从字符串 s 的前 n 个字符开始循环遍历起始位置。创建一个映射 differ 用于跟踪当前窗口内每个单词的出现次数。 遍历单词列表 words 对于单词列表中的每个单词在 differ 中增加其出现次数。如果出现次数增加后变为 0从 differ 中删除该单词。 主循环 从当前起始位置开始每次移动一个单词的长度 n检查子串是否包含所有单词。如果不包含继续移动窗口。如果 differ 中不包含任何单词说明子串包含了所有单词将当前起始位置添加到结果中。 返回结果返回存储结果的切片 ans。
Python 版本 初始化变量 初始化一个空列表 ans 用于存储结果。计算单词的长度 word_len单词数组的长度 total_words单词数组的元素计数 word_count以及输入字符串 s 的长度 s_len。 循环遍历单词的起始位置 外层循环迭代单词的起始位置从 0 到 word_len-1。内部维护两个指针 left 和 j以及一个计数器 count 和一个单词计数器 current_count。 遍历字符串 s 内部循环遍历字符串 s 从当前起始位置开始每次移动一个单词的长度 word_len。在内部循环中检查当前子串是否是单词数组的一个有效组合。如果是有效组合将起始位置 left 添加到结果列表中。 返回结果返回存储结果的列表 ans。
Java 版本 初始化变量 初始化一个空列表 res 用于存储结果。创建一个映射 map 用于存储单词以及它们的出现次数。获取单词数组的长度 m。 循环遍历可能的单词起始位置 外层循环迭代单词的起始位置从 0 到 len(words[0])-1。 遍历字符串 s 内部循环遍历字符串 s从当前起始位置开始每次移动一个单词的长度。在内部循环中检查当前子串是否是单词数组的一个有效组合。如果是有效组合将起始位置添加到结果列表 res 中。 返回结果返回存储结果的列表 res。
C 版本 初始化变量 初始化一个空向量 ans 用于存储结果。获取单词数组的长度 m 和单词的长度 wordsize。创建一个映射 mp 用于存储单词以及它们的出现次数。获取输入字符串 s 的长度 n。 循环遍历可能的单词起始位置 外层循环迭代单词的起始位置从 0 到 wordsize-1。 遍历字符串 s 内部循环遍历字符串 s从当前起始位置开始每次移动一个单词的长度。在内部循环中检查当前子串是否是单词数组的一个有效组合。如果是有效组合将起始位置添加到结果向量 ans 中。 返回结果返回存储结果的向量 ans。
这些是每个版本的基本解题思路。它们都采用了滑动窗口技巧从不同的起始位置开始逐步移动窗口并检查子串是否满足条件。同时它们还利用了数据结构如映射或计数器来统计单词的出现次数以进行比较。不同的编程语言在实现细节上有所不同但整体思路是一致的。
代码
Go
func findSubstring(s string, words []string) (ans []int) {// 获取输入字符串 s 的长度ls, m, n : len(s), len(words), len(words[0])// 遍历字符串 s 的前 n 个字符for i : 0; i n im*n ls; i {// 使用 map differ 来跟踪子串中每个单词的出现次数differ : map[string]int{}// 遍历单词列表 wordsfor j : 0; j m; j {// 将子串中的每个单词加入到 differ 中并统计出现次数differ[s[ij*n:i(j1)*n]]}// 遍历单词列表 wordsfor _, word : range words {// 减少 differ 中对应单词的出现次数differ[word]--// 如果出现次数减少到 0从 differ 中删除这个单词if differ[word] 0 {delete(differ, word)}}// 从当前位置 i 开始每次移动一个单词长度 n检查子串是否包含所有单词for start : i; start ls-m*n1; start n {if start ! i {// 更新 differ增加新单词的出现次数减少旧单词的出现次数word : s[start(m-1)*n : startm*n]differ[word]if differ[word] 0 {delete(differ, word)}word s[start-n : start]differ[word]--if differ[word] 0 {delete(differ, word)}}// 如果 differ 中不包含任何单词说明子串包含了所有单词if len(differ) 0 {ans append(ans, start)}}}return
}
Python
from collections import Counterclass Solution:def findSubstring(self, s: str, words: List[str]) - List[int]:if not s or not words:return []ans []word_len len(words[0])total_words len(words)word_count Counter(words)s_len len(s)for i in range(word_len):left icount 0current_count Counter()for j in range(i, s_len - word_len 1, word_len):word s[j:j word_len]if word in word_count:current_count[word] 1count 1while current_count[word] word_count[word]:left_word s[left:left word_len]current_count[left_word] - 1count - 1left word_lenif count total_words:ans.append(left)else:current_count.clear()count 0left j word_lenreturn ans
Java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;public class Solution {public ListInteger findSubstring(String s, String[] words) {MapString, Integer map new HashMap();// 将单词数组中的单词以及它们的出现次数存储在 map 中for (String str : words) {map.put(str, map.getOrDefault(str, 0) 1);}int len words[0].length(); // 单词的长度ListInteger res new ArrayList(); // 存储结果的列表// 遍历字符串 s 中每个可能的起始位置for (int i 0; i len; i) {MapString, Integer newmap new HashMap(); // 存储当前窗口内的单词出现次数int count 0; // 记录窗口内匹配的单词数量for (int j i; j s.length() - len;) {String cur s.substring(j, j len); // 当前窗口内的单词// 如果当前单词在单词数组中且未超出其出现次数限制if (map.containsKey(cur) (!newmap.containsKey(cur) || newmap.get(cur) map.get(cur))) {newmap.put(cur, newmap.getOrDefault(cur, 0) 1); // 更新窗口内单词出现次数count; // 增加匹配的单词数量// 如果窗口内匹配的单词数量等于单词数组的长度表示找到一个满足条件的子串if (count words.length) {res.add(j - len * (words.length - 1)); // 记录子串的起始位置count--;String pre s.substring(j - len * (words.length - 1), j - len * (words.length - 2));newmap.put(pre, newmap.get(pre) - 1); // 更新窗口内单词出现次数}j len; // 移动窗口} // 如果当前单词不在单词数组中else if (!map.containsKey(cur)) {count 0;newmap.clear(); // 清空窗口内的单词记录j len;} // 如果当前单词在单词数组中但超出其出现次数限制else {String pre s.substring(j - len * count, j - len * (count - 1));newmap.put(pre, newmap.get(pre) - 1); // 更新窗口内单词出现次数count--; // 减少匹配的单词数量}}}return res; // 返回结果列表}
}
Cpp
class Solution {
public:vectorint findSubstring(string s, vectorstring words) {const int n s.length(); // 输入字符串的长度const int m words.size(); // 单词数组的大小const int wordsize words.front().length(); // 单词的长度unordered_mapstring, int mp; // 用于存储单词以及它们的出现次数for (auto word : words)mp[word];vectorint ans; // 存储结果的向量for (int i 0; i wordsize; i) { // 对于每个可能的起始位置unordered_mapstring, int cnt; // 用于存储当前窗口内的单词出现次数int start i; // 记录符合条件的字符串的起始位置for (int j i; j n; j wordsize) { // 遍历字符串 s 中所有单词string word s.substr(j, wordsize);if (!mp.count(word)) { // 如果遇到不在单词数组中的单词直接清空前面所有的计数cnt.clear();start j wordsize;} else {cnt[word] 1;while (cnt[word] mp[word]) { // 某个单词的计数超过了在单词数组中的出现次数从左边减cnt[s.substr(start, wordsize)]--;start wordsize;}if (j - start (m - 1) * wordsize) // 如果窗口内匹配的单词数量等于单词数组的长度表示找到一个满足条件的子串ans.push_back(start);}}}return ans;}
};
每个版本的代码中所需要掌握的基础知识。
Go 版本 Go 语言基础: 了解 Go 语言的基本语法包括变量、循环、条件语句、函数等。 字符串处理: 了解如何使用字符串切片和字符串拼接操作来处理字符串。理解字符串长度的计算方法。 映射map: 了解 Go 中的映射数据结构即 map以及如何向映射中添加、删除和检索元素。熟悉如何使用映射来实现单词计数和比较。 循环和条件语句: 了解如何使用 for 循环和 if 条件语句来实现迭代和条件判断。 切片操作: 了解如何使用切片来操作数组或字符串的子集。理解如何通过切片进行迭代。
Python 版本 Python 语言基础: 熟悉 Python 语言的基本语法包括变量、循环、条件语句、函数等。 字符串处理: 了解如何使用字符串切片和字符串拼接操作来处理字符串。知道如何获取字符串的长度。 Counter 类: 了解 Python 中的 collections.Counter 类用于统计元素出现的次数。知道如何使用 Counter 对象来进行单词计数。 循环和条件语句: 理解如何使用 for 循环和 if 条件语句来实现迭代和条件判断。 列表List: 熟悉 Python 中的列表数据结构以及如何使用列表来存储和操作数据。
Java 版本 Java 语言基础: 熟悉 Java 语言的基本语法包括变量、循环、条件语句、函数等。 字符串处理: 了解如何使用字符串切片和字符串拼接操作来处理字符串。知道如何获取字符串的长度。 Map映射: 理解 Java 中的 java.util.Map 接口以及如何使用 HashMap 实现映射。知道如何向映射中添加、删除和检索元素。 循环和条件语句: 了解如何使用 for 循环和 if 条件语句来实现迭代和条件判断。 列表List: 熟悉 Java 中的列表数据结构即 java.util.List以及如何使用列表来存储和操作数据。
C 版本 C 语言基础: 理解 C 语言的基本语法包括变量、循环、条件语句、函数等。 字符串处理: 了解如何使用字符串切片和字符串拼接操作来处理字符串。知道如何获取字符串的长度。 STL标准模板库: 理解 C STL 中的 std::unordered_map用于实现映射。知道如何向映射中添加、删除和检索元素。 循环和条件语句: 了解如何使用 for 循环和 if 条件语句来实现迭代和条件判断。 向量Vector: 熟悉 C 中的向量数据结构即 std::vector以及如何使用向量来存储和操作数据。
这些是理解和编写提供的不同语言版本的代码所需的基本知识。每个版本都使用了相似的算法和数据结构但具体的语法和库函数可能会有所不同。
31. Next Permutation
题目
Implementnext permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).
The replacement must be**in place**and use only constant extra memory.
Example 1:
Input: nums [1,2,3]
Output: [1,3,2]Example 2:
Input: nums [3,2,1]
Output: [1,2,3]Example 3:
Input: nums [1,1,5]
Output: [1,5,1]Example 4:
Input: nums [1]
Output: [1]Constraints:
1 nums.length 1000 nums[i] 100
题目大意
实现获取 下一个排列 的函数算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列则将数字重新排列成最小的排列即升序排列。必须 原地 修改只允许使用额外常数空间。
解题思路
Go 版本解题思路 寻找下一个排列首先我们要找到下一个排列即重新排列给定数字序列使其成为字典序中的下一个更大的排列。 寻找较小数的位置从右往左遍历整数切片 nums寻找第一个满足 nums[i] nums[i1] 的下标 i。这个位置代表了较小数的位置。 寻找较大数的位置如果找到了 i则在下降区间 [i1, n) 中从右往左找到第一个满足 nums[i] nums[j] 的下标 j这个位置代表了较大数的位置。 交换较小数和较大数交换 nums[i] 和 nums[j]这一步完成后区间 [i1, n) 一定是一个降序区间。 翻转子数组对 [i1, n) 区间内的元素进行原地翻转使其变为升序这样才能生成下一个排列。
Python 版本解题思路
Python 版本的解题思路与 Go 版本相似只是使用了 Python 的列表和对象。 寻找下一个排列与 Go 版本相同我们首先要找到下一个排列即重新排列给定数字序列使其成为字典序中的下一个更大的排列。 寻找较小数的位置从右往左遍历整数列表 nums寻找第一个满足 nums[i] nums[i1] 的下标 i代表了较小数的位置。 寻找较大数的位置如果找到了 i则在下降区间 [i1, n) 中从右往左找到第一个满足 nums[i] nums[j] 的下标 j代表了较大数的位置。 交换较小数和较大数交换 nums[i] 和 nums[j]这一步完成后区间 [i1, n) 一定是一个降序区间。 翻转子数组对 [i1, n) 区间内的元素进行原地翻转使其变为升序这样才能生成下一个排列。
Java 版本解题思路
Java 版本的解题思路与 Go 和 Python 版本相似只是使用了 Java 的数组和类。 寻找下一个排列与其他版本相同首先要找到下一个排列即重新排列给定数字序列使其成为字典序中的下一个更大的排列。 寻找较小数的位置从右往左遍历整数数组 nums寻找第一个满足 nums[i] nums[i1] 的下标 i代表了较小数的位置。 寻找较大数的位置如果找到了 i则在下降区间 [i1, n) 中从右往左找到第一个满足 nums[i] nums[j] 的下标 j代表了较大数的位置。 交换较小数和较大数交换 nums[i] 和 nums[j]这一步完成后区间 [i1, n) 一定是一个降序区间。 翻转子数组对 [i1, n) 区间内的元素进行原地翻转使其变为升序这样才能生成下一个排列。
C 版本解题思路
C 版本的解题思路与 Go、Python 和 Java 版本相似只是使用了 C 的数组和类。 寻找下一个排列与其他版本相同首先要找到下一个排列即重新排列给定数字序列使其成为字典序中的下一个更大的排列。 寻找较小数的位置从右往左遍历整数数组 nums寻找第一个满足 nums[i] nums[i1] 的下标 i代表了较小数的位置。 寻找较大数的位置如果找到了 i则在下降区间 [i1, n) 中从右往左找到第一个满足 nums[i] nums[j] 的下标 j代表了较大数的位置。 交换较小数和较大数交换 nums[i] 和 nums[j]这一步完成后区间 [i1, n) 一定是一个降序区间。 翻转子数组对 [i1, n) 区间内的元素进行原地翻转使其变为升序这样才能生成下一个排列。
代码
Go
// 解法一
// 定义一个函数 nextPermutation用于生成下一个排列
func nextPermutation(nums []int) {// 定义两个变量 i 和 j并初始化为 0i, j : 0, 0// 从倒数第二个元素开始向前遍历整数切片 nums寻找第一个满足 nums[i] nums[i1] 的 ifor i len(nums) - 2; i 0; i-- {if nums[i] nums[i1] {break}}// 如果找到了 i表示存在下一个排列if i 0 {// 从最后一个元素开始向前遍历整数切片 nums寻找第一个满足 nums[j] nums[i] 的 jfor j len(nums) - 1; j i; j-- {if nums[j] nums[i] {break}}// 交换 nums[i] 和 nums[j]swap(nums, i, j)}// 对从 i1 到末尾的部分进行翻转以获得下一个排列reverse(nums, i1, len(nums)-1)
}// 定义一个函数 reverse用于翻转整数切片 nums 中从位置 i 到 j 的元素
func reverse(nums *[]int, i, j int) {// 使用双指针将元素从两端向中间逐个交换for i j {swap(nums, i, j)ij--}
}// 定义一个函数 swap用于交换整数切片 nums 中位置 i 和 j 的元素
func swap(nums *[]int, i, j int) {// 使用指针访问和交换切片中的元素值(*nums)[i], (*nums)[j] (*nums)[j], (*nums)[i]
}
Python
class Solution:def nextPermutation(self, nums: List[int]) - None:Do not return anything, modify nums in-place instead.# Step 1: Find the first decreasing element from right to left (i)i len(nums) - 2while i 0 and nums[i] nums[i 1]:i - 1# Step 2: Find the first element larger than nums[i] from right to left (j)if i 0:j len(nums) - 1while j i and nums[j] nums[i]:j - 1# Step 3: Swap nums[i] and nums[j]nums[i], nums[j] nums[j], nums[i]# Step 4: Reverse the subarray to the right of ileft, right i 1, len(nums) - 1while left right:nums[left], nums[right] nums[right], nums[left]left 1right - 1
Java
class Solution {public void nextPermutation(int[] nums) {// Step 1: Find the first decreasing element from right to left (i)int i nums.length - 2;while (i 0 nums[i] nums[i 1]) {i--;}// Step 2: Find the first element larger than nums[i] from right to left (j)if (i 0) {int j nums.length - 1;while (j i nums[j] nums[i]) {j--;}// Step 3: Swap nums[i] and nums[j]int temp nums[i];nums[i] nums[j];nums[j] temp;}// Step 4: Reverse the subarray to the right of iint left i 1, right nums.length - 1;while (left right) {int temp nums[left];nums[left] nums[right];nums[right] temp;left;right--;}}
}
Cpp
class Solution {
public:void nextPermutation(vectorint nums) {// Step 1: Find the first decreasing element from right to left (i)int i nums.size() - 2;while (i 0 nums[i] nums[i 1]) {i--;}// Step 2: Find the first element larger than nums[i] from right to left (j)if (i 0) {int j nums.size() - 1;while (j i nums[j] nums[i]) {j--;}// Step 3: Swap nums[i] and nums[j]swap(nums[i], nums[j]);}// Step 4: Reverse the subarray to the right of iint left i 1, right nums.size() - 1;while (left right) {swap(nums[left], nums[right]);left;right--;}}
};
基础知识
Go 版本 Go 语言基础: 了解 Go 语言的基本语法、数据类型、函数定义和使用、切片slice等相关知识。 指针: 了解指针的概念以及如何在 Go 中使用指针。 函数: 理解如何定义和调用函数以及函数的参数和返回值。 数组切片: 了解 Go 中的切片概念和切片操作包括切片的创建和修改。
Python 版本 Python 基础: 了解 Python 的基本语法、列表list、条件语句和循环。 类和对象: 理解如何定义类和创建对象在 Python 类中定义方法。 列表操作: 了解如何操作列表包括索引、切片、迭代和修改列表元素。
Java 版本 Java 基础: 熟悉 Java 的基本语法、数组、循环和条件语句。 类和方法: 了解如何定义类和方法并且如何在类中使用成员变量和方法。 数组操作: 熟悉 Java 中数组的创建、遍历和修改操作。
C 版本 C 基础: 了解 C 的基本语法、数组、循环和条件语句。 函数: 理解如何定义和调用函数以及函数的参数和返回值。 数组操作: 了解如何操作数组包括索引、遍历和修改数组元素。
32. Longest Valid Parentheses
题目
Given a string containing just the characters(and), find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: s (()
Output: 2
Explanation: The longest valid parentheses substring is ().Example 2:
Input: s )()())
Output: 4
Explanation: The longest valid parentheses substring is ()().Example 3:
Input: s
Output: 0Constraints:
0 s.length 3 * 104s[i]is(, or).
题目大意
给你一个只包含 ‘(’ 和 ‘)’ 的字符串找出最长有效格式正确且连续括号子串的长度。
解题思路
以下是每个版本的解题思路的详细介绍
Go 版本解题思路
Go 版本的解题思路是利用栈来处理括号匹配问题并采用了双指针的方法来计算最长有效括号子串的长度。主要步骤如下 定义一个辅助函数 max(a, b int) int 用于返回两个整数中的较大值。 初始化 left、right 和 maxLength 变量它们分别用于记录左括号数量、右括号数量和最长有效括号子串的长度初始值都为 0。 遍历输入字符串 s从左到右 如果当前字符是 ‘(’, 则增加 left 计数器。如果当前字符是 ‘)’, 则增加 right 计数器。如果 left 和 right 计数器相等说明找到了一个有效的括号子串计算当前有效括号子串的长度并更新 maxLength。如果 right 大于 left则重置 left 和 right 计数器为 0因为当前的括号串无法匹配。 重置 left、right 和 maxLength 变量为 0再进行一次从右到左的遍历处理右括号数量多于左括号数量的情况。 返回 maxLength它表示最长有效括号子串的长度。
Python 版本解题思路
Python 版本的解题思路与 Go 版本相似也是利用栈来处理括号匹配问题并采用了双指针的方法来计算最长有效括号子串的长度。主要步骤如下 定义一个辅助函数 max(a, b) 用于返回两个数中的较大值。 初始化 left、right 和 maxLength 变量它们分别用于记录左括号数量、右括号数量和最长有效括号子串的长度初始值都为 0。 遍历输入字符串 s从左到右 如果当前字符是 ‘(’, 则增加 left 计数器。如果当前字符是 ‘)’, 则增加 right 计数器。如果 left 和 right 计数器相等说明找到了一个有效的括号子串计算当前有效括号子串的长度并更新 maxLength。如果 right 大于 left则重置 left 和 right 计数器为 0因为当前的括号串无法匹配。 重置 left、right 和 maxLength 变量为 0再进行一次从右到左的遍历处理右括号数量多于左括号数量的情况。 返回 maxLength它表示最长有效括号子串的长度。
Java 版本解题思路
Java 版本的解题思路与 Go 和 Python 版本相似也是利用栈来处理括号匹配问题并采用了双指针的方法来计算最长有效括号子串的长度。主要步骤如下 初始化 left、right 和 maxLength 变量它们分别用于记录左括号数量、右括号数量和最长有效括号子串的长度初始值都为 0。 遍历输入字符串 s从左到右 如果当前字符是 ‘(’, 则增加 left 计数器。如果当前字符是 ‘)’, 则增加 right 计数器。如果 left 和 right 计数器相等说明找到了一个有效的括号子串计算当前有效括号子串的长度并更新 maxLength。如果 right 大于 left则重置 left 和 right 计数器为 0因为当前的括号串无法匹配。 重置 left、right 和 maxLength 变量为 0再进行一次从右到左的遍历处理右括号数量多于左括号数量的情况。 返回 maxLength它表示最长有效括号子串的长度。
C 版本解题思路
C 版本的解题思路与 Go、Python 和 Java 版本相似也是利用栈来处理括号匹配问题并采用了双指针的方法来计算最长有效括号子串的长度。主要步骤如下 初始化 left、right 和 maxLength 变量它们分别用于记录左括号数量、右括号数量和最长有效括号子串的长度初始值都为 0。 遍历输入字符串 s从左到右 如果当前字符是 ‘(’, 则增加 left 计数器。如果当前字符是 ‘)’, 则增加 right 计数器。如果 left 和 right 计数器相等说明找到了一个有效的括号子串计算当前有效括号子串的长度并更新 maxLength。如果 right 大于 left则重置 left 和 right 计数器为 0因为当前的括号串无法匹配。 重置 left、right 和 maxLength 变量为 0再进行一次从右到左的遍历处理右括号数量多于左括号数量的情况。 返回 maxLength它表示最长有效括号子串的长度。
代码
Go
func max(a, b int) int {// 返回两个整数中的较大值if a b {return a}return b
}// 解法二 双指针
func longestValidParentheses(s string) int {// 初始化左右指针和最大有效括号子串长度left, right, maxLength : 0, 0, 0for i : 0; i len(s); i {// 如果当前字符是左括号 (增加左括号计数if s[i] ( {left} else {// 如果当前字符是右括号 )增加右括号计数right}// 如果左右括号计数相等说明找到了一个有效的括号子串if left right {// 计算当前有效括号子串的长度并更新最大长度maxLength max(maxLength, 2*right)} else if right left {// 如果右括号计数大于左括号计数重置左右指针left, right 0, 0}}// 重置左右指针left, right 0, 0for i : len(s) - 1; i 0; i-- {// 从右向左遍历字符串处理与上面相同的逻辑if s[i] ( {left} else {right}if left right {maxLength max(maxLength, 2*left)} else if left right {left, right 0, 0}}// 返回最大有效括号子串的长度return maxLength
}
Python
class Solution:def longestValidParentheses(self, s: str) - int:def max(a, b):return a if a b else bleft, right, maxLength 0, 0, 0# 从左向右遍历字符串for char in s:if char (:left 1else:right 1if left right:maxLength max(maxLength, 2 * right)elif right left:left, right 0, 0left, right 0, 0# 从右向左遍历字符串for i in range(len(s) - 1, -1, -1):char s[i]if char (:left 1else:right 1if left right:maxLength max(maxLength, 2 * left)elif left right:left, right 0, 0return maxLength
Java
class Solution {public int longestValidParentheses(String s) {int left 0, right 0, maxLength 0;// 从左向右遍历字符串for (char c : s.toCharArray()) {if (c () {left;} else {right;}if (left right) {maxLength Math.max(maxLength, 2 * right);} else if (right left) {left 0;right 0;}}left 0;right 0;// 从右向左遍历字符串for (int i s.length() - 1; i 0; i--) {char c s.charAt(i);if (c () {left;} else {right;}if (left right) {maxLength Math.max(maxLength, 2 * left);} else if (left right) {left 0;right 0;}}return maxLength;}
}
Cpp
class Solution {
public:int longestValidParentheses(string s) {int left 0, right 0, maxLength 0;// 从左向右遍历字符串for (char c : s) {if (c () {left;} else {right;}if (left right) {maxLength max(maxLength, 2 * right);} else if (right left) {left 0;right 0;}}left 0;right 0;// 从右向左遍历字符串for (int i s.length() - 1; i 0; i--) {char c s[i];if (c () {left;} else {right;}if (left right) {maxLength max(maxLength, 2 * left);} else if (left right) {left 0;right 0;}}return maxLength;}
};
Go 版本 Go 语言基础 变量声明和初始化循环for 循环条件语句if-else函数声明和调用数组和切片slices的基本操作 栈的概念 Go 中可以使用切片slices来模拟栈的行为
Python 版本 Python 语言基础 变量声明和初始化循环for 循环条件语句if-else函数声明和调用字符串的基本操作 栈的概念 Python 中可以使用列表list来模拟栈的行为
Java 版本 Java 语言基础 类和对象的概念方法声明和调用循环for 循环条件语句if-else字符串的基本操作 栈的概念 Java 中可以使用集合类如 ArrayList 或 LinkedList来模拟栈的行为
C 版本 C 语言基础 变量声明和初始化函数声明和调用循环for 循环条件语句if-else字符串的基本操作 栈的概念 C 中可以使用标准库中的容器如 std::vector 或 std::deque来模拟栈的行为
33. Search in Rotated Sorted Array
题目
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Your algorithm’s runtime complexity must be in the order of O(log n).
Example 1:
Input: nums [4,5,6,7,0,1,2], target 0
Output: 4Example 2:
Input: nums [4,5,6,7,0,1,2], target 3
Output: -1题目大意
假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。搜索一个给定的目标值如果数组中存在这个目标值则返回它的索引否则返回 -1 。你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
解题思路
下面将分别介绍每个版本的解题思路
Go 版本解题思路
初始化两个指针 low 和 high分别指向数组的开头和结尾。使用二分查找的循环来搜索目标值。在每次迭代中计算中间元素的索引 mid。检查中间元素与目标值的关系 如果中间元素等于目标值则直接返回中间元素的索引。如果中间元素大于最左边的元素说明左半段是有序的则比较目标值与中间元素的大小关系 如果目标值大于中间元素且小于等于最右边的元素说明目标值在右半段有序部分更新 low mid 1。否则目标值在左半段无序部分更新 high mid - 1。 如果中间元素小于等于最右边的元素说明右半段是有序的则比较目标值与中间元素的大小关系 如果目标值大于中间元素且小于等于最右边的元素说明目标值在右半段有序部分更新 low mid 1。否则目标值在左半段无序部分更新 high mid - 1。 如果中间元素与最左边的元素相等说明可能存在重复元素可以将最左边的指针 low 向右移动一位。如果中间元素与最右边的元素相等说明可能存在重复元素可以将最右边的指针 high 向左移动一位。 重复步骤 3 和步骤 4直到 low 大于 high此时未找到目标值返回 -1。
Python 版本解题思路
初始化两个指针 low 和 high分别指向数组的开头和结尾。使用二分查找的循环来搜索目标值。在每次迭代中计算中间元素的索引 mid。检查中间元素与目标值的关系 如果中间元素等于目标值则直接返回中间元素的索引。如果中间元素大于最左边的元素说明左半段是有序的则比较目标值与中间元素的大小关系 如果目标值大于中间元素且小于等于最右边的元素说明目标值在右半段有序部分更新 low mid 1。否则目标值在左半段无序部分更新 high mid - 1。 如果中间元素小于等于最右边的元素说明右半段是有序的则比较目标值与中间元素的大小关系 如果目标值大于中间元素且小于等于最右边的元素说明目标值在右半段有序部分更新 low mid 1。否则目标值在左半段无序部分更新 high mid - 1。 如果中间元素与最左边的元素相等说明可能存在重复元素可以将最左边的指针 low 向右移动一位。如果中间元素与最右边的元素相等说明可能存在重复元素可以将最右边的指针 high 向左移动一位。 重复步骤 3 和步骤 4直到 low 大于 high此时未找到目标值返回 -1。
Java 版本解题思路
初始化两个指针 low 和 high分别指向数组的开头和结尾。使用二分查找的循环来搜索目标值。在每次迭代中计算中间元素的索引 mid。检查中间元素与目标值的关系 如果中间元素等于目标值则直接返回中间元素的索引。如果中间元素大于最左边的元素说明左半段是有序的则比较目标值与中间元素的大小关系 如果目标值大于中间元素且小于等于最右边的元素说明目标值在右半段有序部分更新 low mid 1。否则目标值在左半段无序部分更新 high mid - 1。 如果中间元素小于等于最右边的元素说明右半段是有序的则比较目标值与中间元素的大小关系 如果目标值大于中间元素且小于等于最右边的元素说明目标值在右半段有序部分更新 low mid 1。否则目标值在左半段无序部分更新 high mid - 1。 如果中间元素与最左边的元素相等说明可能存在重复元素可以将最左边的指针 low 向右移动一位。如果中间元素与最右边的元素相等说明可能存在重复元素可以将最右边的指针 high 向左移动一位。 重复步骤 3 和步骤 4直到 low 大于 high此时未找到目标值返回 -1。
C 版本解题思路
初始化两个指针 low 和 high分别指向数组的开头和结尾。使用二分查找的循环来搜索目标值。在每次迭代中计算中间元素的索引 mid。检查中间元素与目标值的关系 如果中间元素等于目标值则直接返回中间元素的索引。如果中间元素大于最左边的元素说明左半段是有序的则比较目标值与中间元素的大小关系 如果目标值大于中间元素且小于等于最右边的元素说明目标值在右半段有序部分更新 low mid 1。否则目标值在左半段无序部分更新 high mid - 1。 如果中间元素小于等于最右边的元素说明右半段是有序的则比较目标值与中间元素的大小关系 如果目标值大于中间元素且小于等于最右边的元素说明目标值在右半段有序部分更新 low mid 1。否则目标值在左半段无序部分更新 high mid - 1。 如果中间元素与最左边的元素相等说明可能存在重复元素可以将最左边的指针 low 向右移动一位。如果中间元素与最右边的元素相等说明可能存在重复元素可以将最右边的指针 high 向左移动一位。 重复步骤 3 和步骤 4直到 low 大于 high此时未找到目标值返回 -1。
这四个版本的解题思路基本一致都是使用二分查找的变种来在旋转有序数组中搜索目标值关键是正确处理不同情况下指针的更新以及边界条件的处理。算法的时间复杂度是 O(log n)因为每次迭代都将搜索范围减半。不同版本的代码实现方式有所不同但核心逻辑相似。
代码
Go
func search(nums []int, target int) int {// 检查数组是否为空如果是空数组则直接返回-1if len(nums) 0 {return -1}// 初始化两个指针分别指向数组的开头和结尾low, high : 0, len(nums)-1// 使用二分查找的循环来搜索目标值for low high {// 计算中间元素的索引mid : low (high-low)1// 如果中间元素等于目标值则直接返回中间元素的索引if nums[mid] target {return mid} else if nums[mid] nums[low] { // 如果中间元素在数值大的一部分区间里// 检查目标值是否在左半部分区间内如果是则更新高指针if nums[low] target target nums[mid] {high mid - 1} else {// 否则更新低指针low mid 1}} else if nums[mid] nums[high] { // 如果中间元素在数值小的一部分区间里// 检查目标值是否在右半部分区间内如果是则更新低指针if nums[mid] target target nums[high] {low mid 1} else {// 否则更新高指针high mid - 1}} else {// 处理中间元素等于边界元素的情况移动边界指针以去除重复元素if nums[low] nums[mid] {low}if nums[high] nums[mid] {high--}}}// 如果未找到目标值则返回-1return -1
}
Python
class Solution:def search(self, nums, target: int):# 如果数组为空直接返回-1if len(nums) 0:return -1# 如果数组只有一个元素分两种情况判断elif len(nums) 1:if nums[0] ! target:return -1else:return 0# 找到旋转点的位置for i in range(len(nums) - 1):if nums[i] nums[i 1]:flag i 1break# 在旋转点左边进行二分查找left self.binary_search(nums, target, 0, flag - 1)if left ! -1:return leftelse:# 如果左边没有找到就在旋转点右边进行二分查找right self.binary_search(nums, target, flag, len(nums) - 1)if right -1:return -1else:return rightdef binary_search(self, nums, target, left, right):l, r left, rightwhile l r:mid l (r - l) // 2if nums[mid] target:return midelif nums[mid] target:l mid 1else:r mid - 1return -1
Java
class Solution {public int search(int[] nums, int target) {if (nums null || nums.length 0) {return -1;}int low 0, high nums.length - 1;while (low high) {int mid low (high - low) / 2;if (nums[mid] target) {return mid;} else if (nums[mid] nums[low]) {if (nums[low] target target nums[mid]) {high mid - 1;} else {low mid 1;}} else if (nums[mid] nums[high]) {if (nums[mid] target target nums[high]) {low mid 1;} else {high mid - 1;}} else {if (nums[low] nums[mid]) {low;}if (nums[high] nums[mid]) {high--;}}}return -1;}
}
Cpp
class Solution {
public:int search(vectorint nums, int target) {if (nums.empty()) {return -1;}int low 0, high nums.size() - 1;while (low high) {int mid low (high - low) / 2;if (nums[mid] target) {return mid;} else if (nums[mid] nums[low]) {if (nums[low] target target nums[mid]) {high mid - 1;} else {low mid 1;}} else if (nums[mid] nums[high]) {if (nums[mid] target target nums[high]) {low mid 1;} else {high mid - 1;}} else {if (nums[low] nums[mid]) {low;}if (nums[high] nums[mid]) {high--;}}}return -1;}
};
当用不同编程语言实现算法时需要掌握以下基础知识
Go 版本 函数定义与调用了解如何定义和调用函数包括函数的参数和返回值。 数组与切片Go 中没有传统的数组而是使用切片来处理动态数组。需要了解如何声明、初始化和操作切片。 循环与条件语句了解如何使用 for 和 if 语句来实现循环和条件判断。 二分查找理解二分查找的原理和实现方法包括如何计算中间元素的索引和更新指针。 算法复杂度理解算法复杂度的概念包括时间复杂度和空间复杂度并了解如何分析算法的性能。
Python 版本 类和方法了解如何定义类和类方法并如何创建类的实例。 列表Python 中的列表类似于动态数组需要了解如何声明、初始化和操作列表。 循环与条件语句了解如何使用 for 和 if 语句来实现循环和条件判断。 二分查找理解二分查找的原理和实现方法包括如何计算中间元素的索引和更新指针。 函数递归理解函数递归的概念以及如何在递归中解决问题。
Java 版本 类和方法了解如何定义类和类方法并如何创建类的实例。 数组Java 中有静态数组需要了解如何声明、初始化和操作数组。 循环与条件语句了解如何使用 for 和 if 语句来实现循环和条件判断。 二分查找理解二分查找的原理和实现方法包括如何计算中间元素的索引和更新指针。 算法复杂度理解算法复杂度的概念包括时间复杂度和空间复杂度并了解如何分析算法的性能。
C 版本 类和方法了解如何定义类和类方法并如何创建类的实例。 向量C 中的向量类似于动态数组需要了解如何声明、初始化和操作向量。 循环与条件语句了解如何使用 for 和 if 语句来实现循环和条件判断。 二分查找理解二分查找的原理和实现方法包括如何计算中间元素的索引和更新指针。 算法复杂度理解算法复杂度的概念包括时间复杂度和空间复杂度并了解如何分析算法的性能。
以上是实现搜索旋转排序数组算法所需要掌握的基础知识包括语言特性、数据结构操作、循环和条件判断、二分查找算法和算法复杂度分析等方面的知识。不同编程语言有不同的语法和库函数但核心的算法思想和逻辑都是相似的。
34. Find First and Last Position of Element in Sorted Array
题目
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm’s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
Example 1:
Input: nums [5,7,7,8,8,10], target 8
Output: [3,4]Example 2:
Input: nums [5,7,7,8,8,10], target 6
Output: [-1,-1]题目大意
给定一个按照升序排列的整数数组 nums和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。你的算法时间复杂度必须是 O(log n) 级别。如果数组中不存在目标值返回 [-1, -1]。
解题思路
Go 版本的解题思路 首先初始化两个指针 l_ptr 和 r_ptr它们分别指向数组的起始位置和结束位置。 初始化一个整数切片 ans用于存储目标值的范围初始值为 [-1, -1]。 使用二分搜索的思想在循环中不断缩小搜索范围直到找到目标值的范围或确定目标值不存在。 在每次迭代中计算中间位置的索引 mid。 如果中间位置的元素等于目标值则更新 ans[0] 和 ans[1] 为 mid。然后通过循环向左和向右扩展找到目标值的第一个和最后一个位置。 如果中间位置的元素大于目标值则将右指针 r_ptr 移动到 mid - 1以缩小搜索范围到左半部分。 如果中间位置的元素小于目标值则将左指针 l_ptr 移动到 mid 1以缩小搜索范围到右半部分。 最终返回包含目标值范围的 ans 数组。
Python 版本的解题思路
Python 版本的解题思路与 Go 版本类似但使用了函数和模块的结构来组织代码 首先定义了两个辅助函数 find_left 和 find_right它们分别用于查找目标值的左边界和右边界。 在主函数 searchRange 中初始化两个整数用于存储目标值的左边界和右边界。这些值是通过调用辅助函数来找到的。 辅助函数 find_left 和 find_right 采用二分搜索的思想不断缩小搜索范围直到找到目标值的边界或确定目标值不存在。 当找到左边界时继续向右搜索找到右边界。 最终返回包含目标值范围的结果列表。
Java 版本的解题思路
Java 版本的解题思路与 Go 版本类似但使用了类和方法的结构来组织代码 在 Solution 类中定义了一个方法 searchRange 来解决问题。 在 searchRange 方法中初始化两个整数用于存储目标值的左边界和右边界。 使用 while 循环在循环中不断缩小搜索范围直到找到目标值的范围或确定目标值不存在。 在每次迭代中计算中间位置的索引 mid。 如果中间位置的元素等于目标值则更新左边界和右边界然后通过循环向左和向右扩展找到目标值的第一个和最后一个位置。 如果中间位置的元素大于目标值则缩小搜索范围到左半部分将右指针 r_ptr 移动到 mid - 1。 如果中间位置的元素小于目标值则缩小搜索范围到右半部分将左指针 l_ptr 移动到 mid 1。 最终返回包含目标值范围的整数数组。
C 版本的解题思路
C 版本的解题思路与 Java 版本类似但使用了类和方法的结构来组织代码 在 Solution 类中定义了一个方法 searchRange 来解决问题。 在 searchRange 方法中初始化两个整数用于存储目标值的左边界和右边界。 使用 while 循环在循环中不断缩小搜索范围直到找到目标值的范围或确定目标值不存在。 在每次迭代中计算中间位置的索引 mid。 如果中间位置的元素等于目标值则更新左边界和右边界然后通过循环向左和向右扩展找到目标值的第一个和最后一个位置。 如果中间位置的元素大于目标值则缩小搜索范围到左半部分将右指针 r_ptr 移动到 mid - 1。 如果中间位置的元素小于目标值则缩小搜索范围到右半部分将左指针 l_ptr 移动到 mid。 最终返回包含目标值范围的整数数组。
这些是每个版本的解题思路的详细说明希望这能帮助您更好地理解每个解决方案的工作原理。如果您有任何进一步的问题请随时提问。
代码
Go
func searchRange(nums []int, target int) []int {// 获取数组的长度n : len(nums)// 初始化左指针为 0l_prt : 0// 初始化右指针为数组长度减一r_prt : n - 1// 初始化答案数组用于存储目标值的范围ans : []int{-1, -1} // 在左指针小于等于右指针的条件下进行循环for l_prt r_prt {// 计算中间位置的索引mid : ((r_prt - l_prt) 1) l_prt// 如果中间位置的元素等于目标值if nums[mid] target {// 更新答案的左边界和右边界为中间位置ans[0] midans[1] mid// 从中间位置向左扩展找到目标值的第一个位置for ans[0] 0 nums[ans[0]-1] target {ans[0]--}// 从中间位置向右扩展找到目标值的最后一个位置for ans[1] n - 1 nums[ans[1] 1] target {ans[1]}// 跳出循环因为已经找到了目标值的范围break} else if nums[mid] target {// 如果中间位置的元素大于目标值缩小搜索范围到左半部分r_prt mid - 1} else {// 如果中间位置的元素小于目标值缩小搜索范围到右半部分l_prt mid 1}}// 返回包含目标值范围的答案数组return ans
}
Python
class Solution:def searchRange(self, nums: List[int], target: int) - List[int]:# 辅助函数查找目标值的左边界def find_left():start, end 0, len(nums) - 1res -1 # 初始化结果为-1表示未找到while start end:mid (start end) // 2 # 计算中间位置的索引if nums[mid] target:start mid 1 # 如果中间值小于目标值缩小搜索范围到右半部分elif nums[mid] target:end mid - 1 # 如果中间值大于目标值缩小搜索范围到左半部分else:res mid # 找到目标值更新结果为当前位置end mid - 1 # 继续向左搜索更左边的位置return res# 辅助函数查找目标值的右边界def find_right():start, end 0, len(nums) - 1res -1 # 初始化结果为-1表示未找到while start end:mid (start end) // 2 # 计算中间位置的索引if nums[mid] target:start mid 1 # 如果中间值小于目标值缩小搜索范围到右半部分elif nums[mid] target:end mid - 1 # 如果中间值大于目标值缩小搜索范围到左半部分else:res mid # 找到目标值更新结果为当前位置start mid 1 # 继续向右搜索更右边的位置return res# 返回包含目标值范围的结果数组左边界和右边界分别由辅助函数找到return [find_left(), find_right()]
Java
class Solution {public int[] searchRange(int[] nums, int target) {// 获取数组的长度int n nums.length;// 初始化左指针为0int l_ptr 0;// 初始化右指针为数组长度减一int r_ptr n - 1;// 初始化答案数组用于存储目标值的范围int[] ans {-1, -1};// 在左指针小于等于右指针的条件下进行循环while (l_ptr r_ptr) {// 计算中间位置的索引int mid (r_ptr - l_ptr) / 2 l_ptr;// 如果中间位置的元素等于目标值if (nums[mid] target) {// 更新答案的左边界和右边界为中间位置ans[0] mid;ans[1] mid;// 从中间位置向左扩展找到目标值的第一个位置while (ans[0] 0 nums[ans[0] - 1] target) {ans[0]--;}// 从中间位置向右扩展找到目标值的最后一个位置while (ans[1] n - 1 nums[ans[1] 1] target) {ans[1];}// 跳出循环因为已经找到了目标值的范围break;} else if (nums[mid] target) {// 如果中间位置的元素大于目标值缩小搜索范围到左半部分r_ptr mid - 1;} else {// 如果中间位置的元素小于目标值缩小搜索范围到右半部分l_ptr mid 1;}}// 返回包含目标值范围的答案数组return ans;}
}
Cpp
class Solution {
public:vectorint searchRange(vectorint nums, int target) {int ret; // 用于存储目标值的起始位置int l 0, r nums.size() - 1; // 初始化左右指针表示搜索范围// 第一个循环查找目标值的起始位置while (l r) {int mid (l r) / 2; // 计算中间位置的索引if (nums[mid] target) {l mid 1; // 如果中间值小于目标值缩小搜索范围到右半部分} else {r mid; // 否则缩小搜索范围到左半部分}}// 如果找到的位置超出数组范围或者该位置的值不等于目标值返回{-1, -1}if (l nums.size() || nums[l] ! target) {return {-1, -1};}ret l; // 记录目标值的起始位置l 0;r nums.size() - 1;// 第二个循环查找目标值的结束位置while (l r) {int mid (l r 1) / 2; // 计算中间位置的索引if (nums[mid] target) {r mid - 1; // 如果中间值大于目标值缩小搜索范围到左半部分} else {l mid; // 否则缩小搜索范围到右半部分}}// 返回包含目标值范围的结果数组包括起始位置和结束位置return {ret, l};}
};
每个版本的所需基础知识
Go 版本的基础知识 切片SlicesGo 语言中的切片是动态数组非常常用于处理数组数据。在这个解决方案中nums 是一个整数切片而 ans 也是一个整数切片用于存储目标值的范围。 循环和条件语句解决方案中使用了 for 循环和 if 条件语句来实现逻辑控制例如在二分搜索中不断缩小搜索范围。 二分搜索这个问题的关键是使用二分搜索算法。需要了解二分搜索的基本原理即通过比较中间元素与目标值的大小将搜索范围缩小一半直到找到目标或确定目标不存在。
Python 版本的基础知识 列表ListsPython 中的列表类似于数组用于存储一组元素。在这个解决方案中nums 是一个整数列表而 ans 也是一个整数列表用于存储目标值的范围。 函数和模块解决方案中定义了两个辅助函数 find_left 和 find_right并使用了函数来组织代码。还需要了解 Python 模块的概念例如 List 类型在 typing 模块中的导入。 循环和条件语句与 Go 版本一样Python 版本也使用了 for 循环和 if 条件语句来实现逻辑控制。 二分搜索同样需要了解二分搜索的基本原理和实现方式。
Java 版本的基础知识 数组Java 使用数组来存储一组元素。在这个解决方案中nums 是一个整数数组而 ans 也是一个整数数组用于存储目标值的范围。 类和方法Java 版本使用了一个类 Solution其中包含一个方法 searchRange 来解决问题。需要了解如何定义类和方法并调用它们。 循环和条件语句与其他版本一样Java 版本也使用了 while 循环和 if 条件语句来实现逻辑控制。 二分搜索了解二分搜索的基本原理和实现方式。
C 版本的基础知识 向量VectorsC 中的向量类似于动态数组用于存储一组元素。在这个解决方案中nums 是一个整数向量而 ans 也是一个整数向量用于存储目标值的范围。 类和方法与 Java 版本一样C 版本也使用了一个类 Solution其中包含一个方法 searchRange 来解决问题。需要了解如何定义类和方法并调用它们。 循环和条件语句与其他版本一样C 版本也使用了 while 循环和 if 条件语句来实现逻辑控制。 二分搜索了解二分搜索的基本原理和实现方式。
35. Search Insert Position
题目
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Example 1:
Input: [1,3,5,6], 5
Output: 2Example 2:
Input: [1,3,5,6], 2
Output: 1Example 3:
Input: [1,3,5,6], 7
Output: 4Example 4:
Input: [1,3,5,6], 0
Output: 0题目大意
给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
解题思路
以下是每个版本的解题思路
Go 版本解题思路 定义两个指针 low 和 high它们分别指向数组的起始位置和末尾位置。 使用循环执行二分查找 计算中间元素的索引 mid使用 (low (high - low) 1) 计算。如果中间元素 nums[mid] 大于或等于目标值 target将 high 指针移动到 mid - 1表示在左半部分继续搜索。否则如果中间元素小于目标值 target 检查中间元素的下一个元素是否大于等于目标值 target 或者是否已经到达数组末尾。如果是说明目标值应该插入到当前位置的后面返回 mid 1 作为插入位置的索引。否则将 low 指针移动到 mid 1表示在右半部分继续搜索。 如果循环结束仍然没有找到合适的位置说明目标值应该插入到数组的开头返回 0。
Python 版本解题思路 定义两个指针 low 和 high它们分别指向数组的起始位置和末尾位置。 使用 while 循环执行二分查找 计算中间元素的索引 mid使用 (low (high - low) // 2) 计算。如果中间元素 nums[mid] 大于或等于目标值 target将 high 指针移动到 mid - 1表示在左半部分继续搜索。否则如果中间元素小于目标值 target 检查中间元素的下一个元素是否大于等于目标值 target 或者是否已经到达数组末尾。如果是说明目标值应该插入到当前位置的后面返回 mid 1 作为插入位置的索引。否则将 low 指针移动到 mid 1表示在右半部分继续搜索。 如果循环结束仍然没有找到合适的位置说明目标值应该插入到数组的开头返回 0。
Java 版本解题思路 定义两个指针 low 和 high它们分别指向数组的起始位置和末尾位置。 使用 while 循环执行二分查找 计算中间元素的索引 mid使用 (low (high - low) / 2) 计算。如果中间元素 nums[mid] 大于或等于目标值 target将 high 指针移动到 mid - 1表示在左半部分继续搜索。否则如果中间元素小于目标值 target 检查中间元素的下一个元素是否大于等于目标值 target 或者是否已经到达数组末尾。如果是说明目标值应该插入到当前位置的后面返回 mid 1 作为插入位置的索引。否则将 low 指针移动到 mid 1表示在右半部分继续搜索。 如果循环结束仍然没有找到合适的位置说明目标值应该插入到数组的开头返回 0。
C 版本解题思路 定义两个指针 low 和 high它们分别指向向量动态数组的起始位置和末尾位置。 使用 while 循环执行二分查找 计算中间元素的索引 mid使用 (low (high - low) / 2) 计算。如果中间元素 nums[mid] 大于或等于目标值 target将 high 指针移动到 mid - 1表示在左半部分继续搜索。否则如果中间元素小于目标值 target 检查中间元素的下一个元素是否大于等于目标值 target 或者是否已经到达向量末尾。如果是说明目标值应该插入到当前位置的后面返回 mid 1 作为插入位置的索引。否则将 low 指针移动到 mid 1表示在右半部分继续搜索。 如果循环结束仍然没有找到合适的位置说明目标值应该插入到向量的开头返回 0。
总的来说每个版本的解题思路都是基于二分查找算法的变种通过不断更新 low 和 high 指针来逼近目标值的插入位置。根据不同的编程语言语法和数据结构的细节会有所不同但基本思路保持一致。
代码
Go
func searchInsert(nums []int, target int) int {// 定义两个指针low 指向数组的起始位置high 指向数组的末尾位置low, high : 0, len(nums)-1// 使用循环执行二分查找for low high {// 计算中间元素的索引mid : low (high-low)1// 如果中间元素大于等于目标值if nums[mid] target {// 将 high 指针移动到中间元素的前一个位置high mid - 1} else {// 如果中间元素小于目标值// 检查中间元素的下一个元素是否大于等于目标值或者是否已经到达数组末尾if (mid len(nums)-1) || (nums[mid1] target) {// 如果是说明目标值应该插入到当前位置的后面返回当前位置的下一个索引return mid 1}// 否则将 low 指针移动到中间元素的下一个位置low mid 1}}// 如果循环结束仍然没有找到合适的位置说明目标值应该插入到数组的开头返回0return 0
}
Python
class Solution:def searchInsert(self, nums: List[int], target: int) - int:# 定义两个指针low指向数组的起始位置high指向数组的末尾位置low, high 0, len(nums) - 1# 使用循环执行二分查找while low high:# 计算中间元素的索引mid low (high - low) // 2# 如果中间元素大于等于目标值if nums[mid] target:# 将high指针移动到中间元素的前一个位置high mid - 1else:# 如果中间元素小于目标值# 检查中间元素的下一个元素是否大于等于目标值或者是否已经到达数组末尾if mid len(nums) - 1 or nums[mid 1] target:# 如果是说明目标值应该插入到当前位置的后面返回当前位置的下一个索引return mid 1# 否则将low指针移动到中间元素的下一个位置low mid 1# 如果循环结束仍然没有找到合适的位置说明目标值应该插入到数组的开头返回0return 0
Java
class Solution {public int searchInsert(int[] nums, int target) {// 定义两个指针low指向数组的起始位置high指向数组的末尾位置int low 0, high nums.length - 1;// 使用循环执行二分查找while (low high) {// 计算中间元素的索引int mid low (high - low) / 2;// 如果中间元素大于等于目标值if (nums[mid] target) {// 将high指针移动到中间元素的前一个位置high mid - 1;} else {// 如果中间元素小于目标值// 检查中间元素的下一个元素是否大于等于目标值或者是否已经到达数组末尾if (mid nums.length - 1 || nums[mid 1] target) {// 如果是说明目标值应该插入到当前位置的后面返回当前位置的下一个索引return mid 1;}// 否则将low指针移动到中间元素的下一个位置low mid 1;}}// 如果循环结束仍然没有找到合适的位置说明目标值应该插入到数组的开头返回0return 0;}
}
Cpp
class Solution {
public:int searchInsert(vectorint nums, int target) {// 定义两个指针low指向数组的起始位置high指向数组的末尾位置int low 0, high nums.size() - 1;// 使用循环执行二分查找while (low high) {// 计算中间元素的索引int mid low (high - low) / 2;// 如果中间元素大于等于目标值if (nums[mid] target) {// 将high指针移动到中间元素的前一个位置high mid - 1;} else {// 如果中间元素小于目标值// 检查中间元素的下一个元素是否大于等于目标值或者是否已经到达数组末尾if (mid nums.size() - 1 || nums[mid 1] target) {// 如果是说明目标值应该插入到当前位置的后面返回当前位置的下一个索引return mid 1;}// 否则将low指针移动到中间元素的下一个位置low mid 1;}}// 如果循环结束仍然没有找到合适的位置说明目标值应该插入到数组的开头返回0return 0;}
};
当理解和编写每个版本的代码时你需要掌握以下基础知识
Go 版本
切片 (Slices)Go 中的数组和切片是非常重要的数据结构。切片是动态数组用于存储一系列相同类型的元素。循环和条件语句你需要了解 Go 中的 for 循环和 if 条件语句的用法以便编写代码中的循环和条件判断。函数你需要了解如何定义和调用函数以及函数的参数和返回值。二分查找算法理解二分查找算法的工作原理对于理解此代码非常重要。
Python 版本
列表 (Lists)Python 中的列表是有序的数据结构可以存储多种数据类型。在此问题中列表用于存储整数元素。循环和条件语句你需要了解 Python 中的 while 循环和 if 条件语句的使用方法以便编写代码中的循环和条件判断。类和方法Python 中的 class 和方法定义方式。在这个版本中代码被封装在一个类中。二分查找算法理解二分查找算法的工作原理对于理解此代码非常重要。
Java 版本
数组Java 中的数组是一种静态数据结构你需要了解如何声明、初始化和访问数组元素。循环和条件语句你需要了解 Java 中的 while 循环和 if 条件语句的使用方法以便编写代码中的循环和条件判断。类和方法Java 中的类和方法的定义方式。在这个版本中代码被封装在一个类中。二分查找算法理解二分查找算法的工作原理对于理解此代码非常重要。
C 版本
向量 (Vectors)C 中的向量是一种动态数组类似于 Python 中的列表或 Go 中的切片。循环和条件语句你需要了解 C 中的 while 循环和 if 条件语句的使用方法以便编写代码中的循环和条件判断。类和方法C 中的类和方法的定义方式。在这个版本中代码被封装在一个类中。二分查找算法理解二分查找算法的工作原理对于理解此代码非常重要。
总的来说无论选择哪种编程语言的版本都需要熟悉数组、循环、条件语句和二分查找算法。此外了解特定编程语言的语法和标准库函数也是非常重要的以便能够正确地编写和理解代码。如果你不熟悉某种特定语言建议先学习该语言的基础知识然后再尝试理解和编写相应版本的代码。
