凡科自助建站平台,杭seo网站建设排名,山东网站制作策划,优惠活动推广文案前言
本题解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高分解法-第三周合集 本…前言
本题解Go语言部分基于 LeetCode-Go 其他部分基于本人实践学习 个人题解GitHub连接LeetCode-Go-Python-Java-C Go-Python-Java-C-LeetCode高分解法-第一周合集 Go-Python-Java-C-LeetCode高分解法-第二周合集 Go-Python-Java-C-LeetCode高分解法-第三周合集 本文部分内容来自网上搜集与个人实践。如果任何信息存在错误,欢迎读者批评指正。本文仅用于学习交流,不用作任何商业用途。
22. Generate Parentheses
题目
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n 3, a solution set is:
[((())),(()()),(())(),()(()),()()()
]题目大意
给出 n 代表生成括号的对数请你写出一个函数使其能够生成所有可能的并且有效的括号组合。
解题思路
这道题乍一看需要判断括号是否匹配的问题如果真的判断了那时间复杂度就到 O(n * 2^n)了虽然也可以 AC但是时间复杂度巨高。这道题实际上不需要判断括号是否匹配的问题。因为在 DFS 回溯的过程中会让 ( 和 ) 成对的匹配上的。 当然请继续阅读我会为你分别介绍每个版本的解题思路。
Go 版本解题思路
这个解题思路使用了深度优先搜索DFS的方法来生成有效的括号组合。主要的步骤如下 定义 generateParenthesis 函数接收括号对数目 n 作为参数返回有效的括号组合列表。 如果 n 为 0直接返回一个空的字符串列表因为没有括号需要生成。 初始化一个空的结果列表 res用于存储有效的括号组合。 调用辅助函数 findGenerateParenthesis 来递归生成括号组合。传入当前剩余左右括号数目、当前生成的字符串和结果列表的指针。 在 findGenerateParenthesis 函数中当左右括号剩余数目都为 0 时将当前生成的字符串添加到结果列表中。 如果剩余的左括号数目大于 0可以在当前字符串后添加一个左括号然后递归生成。 如果剩余的右括号数目大于 0并且剩余的右括号数目严格大于剩余的左括号数目以保证有效性可以在当前字符串后添加一个右括号然后递归生成。 返回最终的有效括号组合列表 res。
Python 版本解题思路
这个解题思路同样使用了深度优先搜索DFS的方法来生成有效的括号组合。主要的步骤如下 定义一个 Solution 类其中有一个 generateParenthesis 方法接收括号对数目 n 作为参数返回有效的括号组合列表。 初始化一个空的结果列表 res用于存储有效的括号组合。 调用递归函数 generate 来生成括号组合。传入当前剩余左右括号数目、当前生成的字符串和结果列表。 在 generate 函数中有两个基准情况 如果剩余的左右括号数目都为 0将当前生成的字符串添加到结果列表中。如果剩余的左括号数目大于 0可以在当前字符串后添加一个左括号然后递归生成。 如果剩余的右括号数目大于 0并且剩余的右括号数目严格大于剩余的左括号数目以保证有效性可以在当前字符串后添加一个右括号然后递归生成。 最后generateParenthesis 方法返回最终的有效括号组合列表 res。
Java 版本解题思路
这个解题思路与前两个版本类似同样使用深度优先搜索DFS的方法来生成有效的括号组合。主要的步骤如下 定义一个 Solution 类其中有一个 generateParenthesis 方法接收括号对数目 n 作为参数返回有效的括号组合列表。 初始化一个空的结果列表 res用于存储有效的括号组合。 调用递归函数 generate 来生成括号组合。传入当前剩余左右括号数目、当前生成的字符串和结果列表。 在 generate 函数中同样有两个基准情况 如果剩余的左右括号数目都为 0将当前生成的字符串添加到结果列表中。如果剩余的左括号数目大于 0可以在当前字符串后添加一个左括号然后递归生成。 如果剩余的右括号数目大于 0并且剩余的右括号数目严格大于剩余的左括号数目以保证有效性可以在当前字符串后添加一个右括号然后递归生成。 最后generateParenthesis 方法返回最终的有效括号组合列表 res。
C 版本解题思路
这个解题思路与其他版本相似同样使用深度优先搜索DFS的方法来生成有效的括号组合。主要的步骤如下 定义一个 Solution 类其中有一个 generateParenthesis 方法接收括号对数目 n 作为参数返回有效的括号组合列表。 初始化一个空的结果列表 res用于存储有效的括号组合。 调用递归函数 generate 来生成括号组合。传入当前剩余左右括号数目、当前生成的字符串和结果列表。 在 generate 函数中同样有两个基准情况 如果剩余的左右括号数目都为 0将当前生成的字符串添加到结果列表中。如果剩余的左括号数目大于 0可以在当前字符串后添加一个左括号然后递归生成。 如果剩余的右括号数目大于 0并且剩余的右括号数目严格大于剩余的左括号数目以保证有效性可以在当前字符串后添加一个右括号然后递归生成。 最后generateParenthesis 方法返回最终的有效括号组合列表 res。
代码
Go
// 定义一个函数 generateParenthesis输入参数 n 表示括号对数目返回有效的括号组合列表。
func generateParenthesis(n int) []string {// 如果括号对数目为 0直接返回一个空的字符串列表。if n 0 {return []string{}}// 初始化一个结果列表用于存储有效的括号组合。res : []string{}// 调用辅助函数 findGenerateParenthesis 生成括号组合传入当前左右括号剩余数目、当前生成的字符串和结果列表的指针。findGenerateParenthesis(n, n, , res)// 返回最终的有效括号组合列表。return res
}// 定义辅助函数 findGenerateParenthesis用于递归生成有效的括号组合。
func findGenerateParenthesis(lindex, rindex int, str string, res *[]string) {// 当左右括号剩余数目都为 0 时说明已经生成了一个有效的括号组合将其添加到结果列表中。if lindex 0 rindex 0 {*res append(*res, str)return}// 如果左括号剩余数目大于 0可以在当前字符串后添加一个左括号继续递归生成。if lindex 0 {findGenerateParenthesis(lindex-1, rindex, str(, res)}// 如果右括号剩余数目大于 0并且剩余的右括号数目严格大于剩余的左括号数目// 则可以在当前字符串后添加一个右括号继续递归生成。if rindex 0 lindex rindex {findGenerateParenthesis(lindex, rindex-1, str), res)}
}
Python
class Solution:def generateParenthesis(self, n: int) - List[str]:res [] # 存储最终的有效括号组合列表self.generate(n, n, , res) # 调用递归函数生成括号组合return res# 递归生成括号组合的辅助函数def generate(self, left: int, right: int, current: str, res: List[str]):# 当左右括号剩余数目都为 0 时说明已经生成了一个有效的括号组合将其添加到结果列表中。if left 0 and right 0:res.append(current)return# 如果左括号剩余数目大于 0可以在当前字符串后添加一个左括号继续递归生成。if left 0:self.generate(left - 1, right, current (, res)# 如果右括号剩余数目大于 0并且剩余的右括号数目严格大于剩余的左括号数目# 则可以在当前字符串后添加一个右括号继续递归生成。if right 0 and left right:self.generate(left, right - 1, current ), res)
Java
import java.util.ArrayList;
import java.util.List;class Solution {public ListString generateParenthesis(int n) {ListString res new ArrayList(); // 存储最终的有效括号组合列表generate(n, n, , res); // 调用递归函数生成括号组合return res;}// 递归生成括号组合的辅助函数private void generate(int left, int right, String current, ListString res) {// 当左右括号剩余数目都为 0 时说明已经生成了一个有效的括号组合将其添加到结果列表中。if (left 0 right 0) {res.add(current);return;}// 如果左括号剩余数目大于 0可以在当前字符串后添加一个左括号继续递归生成。if (left 0) {generate(left - 1, right, current (, res);}// 如果右括号剩余数目大于 0并且剩余的右括号数目严格大于剩余的左括号数目// 则可以在当前字符串后添加一个右括号继续递归生成。if (right 0 left right) {generate(left, right - 1, current ), res);}}public static void main(String[] args) {Solution solution new Solution();int n 3; // 设置括号对数目ListString result solution.generateParenthesis(n); // 调用生成函数for (String str : result) {System.out.println(str); // 输出生成的括号组合}}
}
Cpp
#include iostream
#include vector
using namespace std;class Solution {
public:vectorstring generateParenthesis(int n) {vectorstring res; // 存储最终的有效括号组合列表generate(n, n, , res); // 调用递归函数生成括号组合return res;}// 递归生成括号组合的辅助函数void generate(int left, int right, string current, vectorstring res) {// 当左右括号剩余数目都为 0 时说明已经生成了一个有效的括号组合将其添加到结果列表中。if (left 0 right 0) {res.push_back(current);return;}// 如果左括号剩余数目大于 0可以在当前字符串后添加一个左括号继续递归生成。if (left 0) {generate(left - 1, right, current (, res);}// 如果右括号剩余数目大于 0并且剩余的右括号数目严格大于剩余的左括号数目// 则可以在当前字符串后添加一个右括号继续递归生成。if (right 0 left right) {generate(left, right - 1, current ), res);}}
};
每个版本代码所需要的基础知识。
Go 版本基础知识 函数声明与调用 了解如何声明和调用函数Go 使用 func 关键字来定义函数。 条件语句 了解 if 条件语句的用法以及如何使用条件判断。 切片Slices 切片是 Go 中灵活的数据结构类似于动态数组。了解如何声明、初始化和操作切片。 递归 了解递归的概念以及如何在函数中调用自身。 指针与引用 了解 Go 中的指针和引用因为函数中需要通过引用传递结果列表。
Python 版本基础知识 函数定义与调用 理解如何定义和调用函数Python 使用 def 关键字来声明函数。 条件语句 理解 if 条件语句的语法以及如何使用条件判断。 列表Lists 列表是 Python 中常用的数据结构类似于动态数组。了解如何创建、修改和操作列表。 递归 理解递归的概念以及如何在函数中调用自身。
Java 版本基础知识 函数声明与调用 了解如何声明和调用函数Java 使用方法methods来定义函数。 条件语句 了解 if 条件语句的语法以及如何进行条件判断。 列表Lists 在 Java 中可以使用 ArrayList 类作为动态数组。了解如何创建、修改和操作 ArrayList。 递归 了解递归的概念以及如何在方法中调用自身。 类与对象 Java 是面向对象的编程语言理解类和对象的概念以及如何定义和使用它们。
C 版本基础知识 函数声明与调用 了解如何声明和调用函数C 使用函数functions来定义函数。 条件语句 理解 if 条件语句的语法以及如何进行条件判断。 向量Vectors 在 C 中可以使用 vector 类作为动态数组。了解如何创建、修改和操作向量。 递归 理解递归的概念以及如何在函数中调用自身。 类与对象 C 也是面向对象的编程语言理解类和对象的概念以及如何定义和使用它们。
23. Merge k Sorted Lists
题目
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example :
Input:
[1-4-5,1-3-4,2-6
]
Output: 1-1-2-3-4-4-5-6
题目大意
合并 K 个有序链表
解题思路
Go 版本解法
这个解法使用了分治的思想来合并 k 个有序链表。首先判断输入的链表数组的长度
如果长度为 0返回 nil。如果长度为 1直接返回该链表。
对于长度大于 1 的情况将链表数组分成两半然后递归地合并左半部分和右半部分最后将两部分合并。合并的过程是通过一个辅助函数来实现的比较两个链表的当前节点值选择较小的节点连接到合并后的链表。
Python 版本解法
这个解法使用了优先队列堆来合并 k 个有序链表。首先将每个链表的头节点及其值和索引放入优先队列中。然后循环从优先队列中弹出最小值的节点将其连接到合并链表的末尾。如果弹出的节点还有下一个节点将下一个节点入队。
这样通过不断弹出最小节点不断将下一个节点入队就能够逐步构建合并后的链表。
Java 版本解法
这个解法也是使用了优先队列堆来合并 k 个有序链表。与 Python 版本类似首先将每个链表的头节点及其值和索引放入优先队列中。然后循环从优先队列中弹出最小值的节点将其连接到合并链表的末尾。如果弹出的节点还有下一个节点将下一个节点入队。
这个过程会不断弹出最小节点不断将下一个节点入队从而构建合并后的链表。
C 版本解法
这个解法使用了分治的思想来合并 k 个有序链表。首先定义了一个辅助函数 merge用来合并两个有序链表。然后使用递归的分治方法将 k 个链表分成两半递归地合并左半部分和右半部分最后将两部分合并。
在合并的过程中辅助函数 merge 会比较两个链表的当前节点值选择较小的节点连接到合并后的链表。
以上就是各个版本的解题思路它们都是通过合并有序链表来实现的但采用了不同的数据结构和算法来达到相同的目标。## 代码
Go
/*** 定义单链表节点结构* type ListNode struct {* Val int // 当前节点的值* Next *ListNode // 指向下一个节点的指针* }*/
func mergeKLists(lists []*ListNode) *ListNode {// 获取输入链表数组的长度len : len(lists)// 根据不同情况进行合并操作switch len {case 0:return nil // 如果没有链表返回 nilcase 1:return lists[0] // 如果只有一个链表直接返回这个链表default:mid : len / 2 // 将链表数组分成两半left : mergeKLists(lists[:mid]) // 递归地合并左半部分right : mergeKLists(lists[mid:]) // 递归地合并右半部分return merge(left, right) // 合并左右两部分链表}
}func merge(list1 *ListNode, list2 *ListNode) *ListNode {dummy : ListNode{} // 创建一个哑节点作为合并后的链表的起始节点cur : dummy // 创建一个当前节点指针初始指向哑节点// 比较两个链表的节点值逐个选择较小的节点连接到合并后的链表for list1 ! nil list2 ! nil {if list1.Val list2.Val {cur.Next list1list1 list1.Next} else {cur.Next list2list2 list2.Next}cur cur.Next}// 将剩余的 list1 链接到合并后的链表for list1 ! nil {cur.Next list1list1 list1.Nextcur cur.Next}// 将剩余的 list2 链接到合并后的链表for list2 ! nil {cur.Next list2list2 list2.Nextcur cur.Next}return dummy.Next // 返回合并后链表的起始节点
}
Python
import heapq
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def mergeKLists(self, lists: List[Optional[ListNode]]) - Optional[ListNode]:heap [] # 使用一个最小堆来存储当前每个链表的头节点for i, node in enumerate(lists):if node:heapq.heappush(heap, (node.val, i, node)) # 将链表头节点的值、链表索引和链表头节点元组入堆dummy ListNode() # 创建哑节点作为合并后链表的起始节点cur dummy # 创建一个当前节点指针初始指向哑节点while heap:val, idx, node heapq.heappop(heap) # 弹出堆顶元素即最小值的节点cur.next node # 将最小节点接到合并链表的末尾cur cur.nextif node.next:heapq.heappush(heap, (node.next.val, idx, node.next)) # 将下一个节点入堆保持堆的有序性return dummy.next # 返回合并后链表的起始节点
Java
import java.util.*;
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode mergeKLists(ListNode[] lists) {// 创建一个最小堆并根据节点值进行比较PriorityQueueListNode minHeap new PriorityQueue((a, b) - a.val - b.val);// 将所有链表的头节点加入堆for (ListNode node : lists) {if (node ! null) {minHeap.offer(node);}}ListNode dummy new ListNode(); // 创建哑节点作为合并后链表的起始节点ListNode cur dummy; // 创建一个当前节点指针初始指向哑节点while (!minHeap.isEmpty()) {ListNode minNode minHeap.poll(); // 弹出堆顶元素即最小值的节点cur.next minNode; // 将最小节点接到合并链表的末尾cur cur.next;if (minNode.next ! null) {minHeap.offer(minNode.next); // 将下一个节点加入堆保持堆的有序性}}return dummy.next; // 返回合并后链表的起始节点}
}
Cpp
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:// 递归合并两个有序链表ListNode* merge(ListNode* list1, ListNode* list2) {if (!list1) return list2;if (!list2) return list1;if (list1-val list2-val) {list1-next merge(list1-next, list2);return list1;} else {list2-next merge(list1, list2-next);return list2;}}// 使用分治法逐步合并 K 个链表ListNode* quick(vectorListNode* lists, int l, int r) {if (l r) return nullptr;if (l r) return lists[l];int mid (l r) 1;return merge(quick(lists, l, mid), quick(lists, mid 1, r));}// 主函数合并 K 个有序链表ListNode* mergeKLists(vectorListNode* lists) {return quick(lists, 0, lists.size() - 1);}
};
每个版本的详细基础知识。
Go 版本解法 链表数据结构 你需要理解 ListNode 结构的定义它是一个表示链表节点的结构体包括一个整数值 Val 和指向下一个节点的指针 Next。 递归 这个解法使用了递归来实现分治合并。你需要了解递归的工作原理即一个函数调用自身以解决更小规模的问题。 切片Slices Go 中的切片是动态数组用于存储多个相同类型的元素。解法中用切片进行了链表的分割和合并。
Python 版本解法 优先队列堆 heapq 是 Python 中的堆操作库它提供了优先队列的实现。你需要了解如何使用堆来维护最小元素以及堆的基本操作。 链表数据结构 你需要理解 ListNode 结构的定义类似于 Go 版本的链表数据结构。 类和对象 Python 是面向对象的语言解法中使用了类来定义 Solution 类以及链表节点的构造。 循环 解法中使用了循环来遍历链表、优先队列等。
Java 版本解法 优先队列堆 Java 中的优先队列也是通过堆实现的你需要了解如何使用 PriorityQueue 类来创建和操作优先队列。 链表数据结构 你需要理解 ListNode 结构的定义与其他版本类似。 类和对象 Java 也是面向对象的语言你需要理解类的定义和使用。 循环 解法中使用了循环来遍历链表、优先队列等。
C 版本解法 优先队列堆 C 中的 priority_queue 类用于实现优先队列你需要了解如何使用它来维护最小元素。 链表数据结构 你需要理解 ListNode 结构的定义与其他版本类似。 递归 解法中使用了递归来实现分治合并你需要理解递归的概念和用法。 类和对象 C 是面向对象的语言解法中使用了类来定义 Solution 类和链表节点。
24. Swap Nodes in Pairs
题目
Given a linked list, swap every two adjacent nodes and return its head.
You may not modify the values in the list’s nodes, only nodes itself may be changed.
Example:
Given 1-2-3-4, you should return the list as 2-1-4-3.题目大意
两两相邻的元素翻转链表
解题思路
Go版本
创建一个虚拟节点dummy将其指向原链表的头节点。使用一个指针pt来遍历链表直到没有足够的相邻节点可以交换。在每一轮循环中获取需要交换的相邻节点node1和node2。进行节点交换即将pt的next指向node2node1的next指向node2的nextnode2的next指向node1。更新指针pt的位置继续下一轮交换。返回交换相邻节点后的链表头节点。
Python版本
创建一个虚拟节点dummy将其指向原链表的头节点。使用一个指针pt来遍历链表直到没有足够的相邻节点可以交换。在每一轮循环中获取需要交换的相邻节点node1和node2。进行节点交换即将pt的next指向node2node1的next指向node2的nextnode2的next指向node1。更新指针pt的位置继续下一轮交换。返回交换相邻节点后的链表头节点。
Java版本
创建一个虚拟节点dummy将其指向原链表的头节点。使用一个指针pt来遍历链表直到没有足够的相邻节点可以交换。在每一轮循环中获取需要交换的相邻节点node1和node2。进行节点交换即将pt的next指向node2node1的next指向node2的nextnode2的next指向node1。更新指针pt的位置继续下一轮交换。返回交换相邻节点后的链表头节点。
C版本
如果链表为空直接返回原链表头节点。创建一个虚拟节点virNode将其指向原链表的头节点。使用三个指针p1、p2和p3来进行节点交换。创建一个指针ago用于记录上一组交换节点的末尾节点。循环遍历链表直到没有足够的相邻节点可以交换。获取p2的下一个节点。将p2的next指针置为空然后将p2的next指向p1将p1的next指向p3将ago的next指向p2。更新指针ago为p1指针p1为p3指针p2为p1的下一个节点。返回交换相邻节点后的链表头节点。## 代码
Go
/*** Definition for singly-linked list.* type ListNode struct {* Val int* Next *ListNode* }*/// 定义一个函数用于交换链表中相邻节点的位置
func swapPairs(head *ListNode) *ListNode {// 创建一个虚拟节点指向原链表的头节点dummy : ListNode{Next: head}// 循环遍历链表直到没有足够的相邻节点可以交换for pt : dummy; pt ! nil pt.Next ! nil pt.Next.Next ! nil; {// 使用多重赋值的方式交换相邻节点的位置pt, pt.Next, pt.Next.Next, pt.Next.Next.Next pt.Next, pt.Next.Next, pt.Next.Next.Next, pt.Next}// 返回交换相邻节点后的链表头节点的指针return dummy.Next
}
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def swapPairs(self, head: Optional[ListNode]) - Optional[ListNode]:# 创建一个虚拟节点指向原链表的头节点dummy ListNode(0)dummy.next head# 使用一个指针pt来遍历链表pt dummy# 循环遍历链表直到没有足够的相邻节点可以交换while pt.next and pt.next.next:# 获取需要交换的相邻节点node1 pt.nextnode2 pt.next.next# 进行节点交换pt.next node2node1.next node2.nextnode2.next node1# 更新指针pt的位置继续下一轮交换pt node1# 返回交换相邻节点后的链表头节点return dummy.nextJava
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode swapPairs(ListNode head) {// 创建一个虚拟节点指向原链表的头节点ListNode dummy new ListNode(0);dummy.next head;// 使用一个指针pt来遍历链表ListNode pt dummy;// 循环遍历链表直到没有足够的相邻节点可以交换while (pt.next ! null pt.next.next ! null) {// 获取需要交换的相邻节点ListNode node1 pt.next;ListNode node2 pt.next.next;// 进行节点交换pt.next node2;node1.next node2.next;node2.next node1;// 更新指针pt的位置继续下一轮交换pt node1;}// 返回交换相邻节点后的链表头节点return dummy.next;}
}
Cpp
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* swapPairs(ListNode* head) {// 如果链表为空直接返回原链表头节点if (!head) return head;// 创建一个虚拟节点指向原链表的头节点ListNode* virNode new ListNode(-1);virNode-next head;// 使用三个指针p1、p2和p3来进行节点交换ListNode* p1 head;ListNode* p2 p1-next;ListNode* p3;// 创建一个指针ago用于记录上一组交换节点的末尾节点ListNode* ago virNode;// 循环遍历链表直到没有足够的相邻节点可以交换while (p2) {// 获取p2的下一个节点p3 p2-next;// 将p2的next指针置为空然后将p2的next指向p1将p1的next指向p3将ago的next指向p2p2-next nullptr;p2-next p1;p1-next p3;ago-next p2;// 更新指针ago为p1指针p1为p3指针p2为p1的下一个节点ago p1;p1 p3;if (!p1) {break;} else {p2 p1-next;}}// 返回交换相邻节点后的链表头节点return virNode-next;}
};
Go 版本:
掌握 Go 中的结构体(struct)的定义方法,ListNode 表示节点。理解指针概念,p 用于遍历指向每个节点。了解 for 循环的语法,通过判断指针是否为 nil 来结束。知道如何访问结构体成员,通过指针 p.Next。了解 Make 函数来分配结构体的方法,dummy : ListNode{0, head}
C 版本:
掌握 C 中的结构体(struct)的定义和使用。本题中用结构体 ListNode 表示链表节点。了解 C 中指针的概念。p 是表示当前节点的指针,通过 p-next 访问后继节点。知道 while 循环的写法,循环条件是判断指针是否为空。理解引用传递, ListNode* 表示传递的是指针的引用。知道如何动态创建结构体对象,这里用 ListNode dummy(0) 创建一个虚拟头节点。
Java 版本:
掌握 Java 中的类(class)和对象的概念。ListNode 类表示节点对象。理解 Java 中引用传递,ListNode 类型表示对象引用。知道 Java 的 while 循环写法,循环条件是判断引用是否为 null。能够通过引用访问对象的成员,如 n1.next。掌握创建对象的语法,new ListNode(0) 创建一个节点对象。
Python 版本:
了解 Python 中的类(class)的概念,ListNode 类表示节点。掌握 Python 的 while 循环语法,通过判断变量是否为 None 来结束循环。理解 Python 中的对象引用,p 和 n1 等都是对对象的引用。能使用 . 属性访问对象成员,如 p.next。知道如何创建类的实例,dummy ListNode(0) 来创建对象。
25. Reverse Nodes in k-Group
题目
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
Example:
Given this linked list: 1-2-3-4-5For k 2, you should return: 2-1-4-3-5For k 3, you should return: 3-2-1-4-5Note:
Only constant extra memory is allowed.You may not alter the values in the list’s nodes, only nodes itself may be changed.
题目大意
按照每 K 个元素翻转的方式翻转链表。如果不满足 K 个元素的就不翻转。
解题思路
这一题是 problem 24 的加强版problem 24 是两两相邻的元素翻转链表。而 problem 25 要求的是 k 个相邻的元素翻转链表problem 相当于是 k 2 的特殊情况。
Go 版本解题思路 创建一个 reverseKGroup 函数该函数接收一个头节点和一个整数 k用于翻转每 k 个节点。 在 reverseKGroup 函数中使用一个循环来判断是否剩余 k 个节点。 在循环中调用 reverse 函数来翻转当前的 k 个节点。 将当前节点组的头节点连接到下一个节点组的头节点然后递归处理下一个节点组。 最终返回整个链表翻转后的头节点。 reverse 函数用于翻转从 first 到 last 之间的节点它使用指针操作来实现翻转。
Python 版本解题思路 创建一个 reverseKGroup 方法该方法接收一个头节点和一个整数 k用于翻转每 k 个节点。 在 reverseKGroup 方法中使用递归来处理每个节点组。 在递归中调用 reverse 方法来翻转当前的 k 个节点。 将当前节点组的头节点连接到下一个节点组的头节点然后递归处理下一个节点组。 最终返回整个链表翻转后的头节点。 reverse 方法用于翻转从 first 到 last 之间的节点它使用指针操作来实现翻转。
Java 版本解题思路 创建一个 reverseKGroup 方法该方法接收一个头节点和一个整数 k用于翻转每 k 个节点。 在 reverseKGroup 方法中使用递归来处理每个节点组。 在递归中调用 reverse 方法来翻转当前的 k 个节点。 将当前节点组的头节点连接到下一个节点组的头节点然后递归处理下一个节点组。 最终返回整个链表翻转后的头节点。 reverse 方法用于翻转从 first 到 last 之间的节点它使用指针操作来实现翻转。
C 版本解题思路 创建一个 reverseKGroup 方法该方法接收一个头节点和一个整数 k用于翻转每 k 个节点。 在 reverseKGroup 方法中使用循环来处理每个节点组。 在循环中调用 reverse 方法来翻转当前的 k 个节点。 将当前节点组的头节点连接到下一个节点组的头节点然后继续循环处理下一个节点组。 最终返回整个链表翻转后的头节点。 reverse 方法用于翻转从 target 节点开始的 k 个节点它使用指针操作来实现翻转。
代码
Go
/*** 单链表节点的定义。* type ListNode struct {* Val int* Next *ListNode* }*/// reverseKGroup 函数接收一个头节点和一个整数 k将链表中每 k 个节点进行翻转操作。
func reverseKGroup(head *ListNode, k int) *ListNode {node : head // 保存头节点的引用用于后面返回for i : 0; i k; i {if node nil {return head // 如果剩余节点不足 k 个不进行翻转直接返回头节点}node node.Next // 移动节点指针到下一个节点}newHead : reverse(head, node) // 调用 reverse 函数翻转当前的 k 个节点head.Next reverseKGroup(node, k) // 递归处理剩余节点并将返回的头节点连接到当前节点组的末尾return newHead // 返回翻转后的头节点
}// reverse 函数用于将从 first 到 last 之间的节点进行翻转返回翻转后的头节点。
func reverse(first *ListNode, last *ListNode) *ListNode {prev : last // prev 指向翻转后的链表末尾初始为 lastfor first ! last {tmp : first.Next // 保存下一个节点的引用first.Next prev // 将当前节点的 Next 指向 prev实现翻转prev first // 更新 prev 为当前节点以便下一轮循环使用first tmp // 更新 first 为下一个节点以便下一轮循环使用}return prev // 返回翻转后的头节点
}
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next nextclass Solution:def reverseKGroup(self, head: Optional[ListNode], k: int) - Optional[ListNode]:node head # 保存头节点的引用用于后面返回for i in range(k):if not node:return head # 如果剩余节点不足 k 个不进行翻转直接返回头节点node node.next # 移动节点指针到下一个节点new_head self.reverse(head, node) # 调用 reverse 函数翻转当前的 k 个节点head.next self.reverseKGroup(node, k) # 递归处理剩余节点并将返回的头节点连接到当前节点组的末尾return new_head # 返回翻转后的头节点# reverse 函数用于将从 first 到 last 之间的节点进行翻转返回翻转后的头节点。def reverse(self, first: Optional[ListNode], last: Optional[ListNode]) - Optional[ListNode]:prev last # prev 指向翻转后的链表末尾初始为 lastwhile first ! last:tmp first.next # 保存下一个节点的引用first.next prev # 将当前节点的 next 指向 prev实现翻转prev first # 更新 prev 为当前节点以便下一轮循环使用first tmp # 更新 first 为下一个节点以便下一轮循环使用return prev # 返回翻转后的头节点
Java
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode reverseKGroup(ListNode head, int k) {ListNode node head; // 保存头节点的引用用于后面返回for (int i 0; i k; i) {if (node null) {return head; // 如果剩余节点不足 k 个不进行翻转直接返回头节点}node node.next; // 移动节点指针到下一个节点}ListNode newHead reverse(head, node); // 调用 reverse 函数翻转当前的 k 个节点head.next reverseKGroup(node, k); // 递归处理剩余节点并将返回的头节点连接到当前节点组的末尾return newHead; // 返回翻转后的头节点}// reverse 函数用于将从 first 到 last 之间的节点进行翻转返回翻转后的头节点。private ListNode reverse(ListNode first, ListNode last) {ListNode prev last; // prev 指向翻转后的链表末尾初始为 lastwhile (first ! last) {ListNode tmp first.next; // 保存下一个节点的引用first.next prev; // 将当前节点的 next 指向 prev实现翻转prev first; // 更新 prev 为当前节点以便下一轮循环使用first tmp; // 更新 first 为下一个节点以便下一轮循环使用}return prev; // 返回翻转后的头节点}
}
Cpp
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:// 主函数翻转每 k 个节点的组ListNode* reverseKGroup(ListNode* head, int k) {auto cur head; // 当前组的头节点ListNode* prev_tail nullptr; // 上一组的尾节点ListNode *cur_head nullptr; // 当前组的头节点ListNode *cur_tail nullptr; // 当前组的尾节点ListNode *next_cur nullptr; // 下一个组的头节点ListNode *ans nullptr; // 最终翻转后的链表的头节点// 循环处理每个组do {// 调用 reverse 函数翻转当前的 k 个节点next_cur reverse(cur, cur_head, cur_tail, k);if(!ans) {ans cur_head; // 如果 ans 为空将当前组的头节点作为答案的头节点}if(prev_tail) {prev_tail-next cur_head; // 将上一组的尾节点与当前组的头节点相连}prev_tail cur_tail; // 更新 prev_tail 为当前组的尾节点cur next_cur; // 将 cur 更新为下一个组的头节点} while(next_cur);cur_tail-next next_cur; // 将最后一个组的尾节点与下一个组的头节点相连return ans; // 返回整个翻转后的链表头节点}// 辅助函数翻转从 target 节点开始的 k 个节点ListNode* reverse(ListNode *target, ListNode *(ret_head), ListNode *(ret_tail), int k) {if(!target-next) {ret_head target;ret_tail target;return nullptr; // 如果 target 节点后面没有节点了返回空表明不需要翻转}int cnt 1;ListNode *tmp target;for(; tmp-next ! nullptr; tmptmp-next) {if(cnt k ) {break;}cnt;}if(cnt k) {ret_head target;ret_tail tmp;return nullptr; // 如果剩余节点数量不足 k返回空表明不需要翻转}ret_tail target; // 更新当前组的尾节点为 targetauto cur target;auto next target-next;cnt 1;while(next cnt k) {auto next_next next-next;next-next cur;cur next;next next_next;cnt;}ret_head cur; // 更新当前组的头节点为 curret_tail-next nullptr; // 将当前组的尾节点的 next 指向空表示该组翻转后的尾节点return next; // 返回下一个组的头节点}
};
Go 版本代码
结构体与指针 Go 使用结构体表示链表节点这是一种自定义的数据结构。代码中的 ListNode 结构体有一个整数字段 Val 和一个指向下一个节点的指针字段 Next。head 是指向链表头节点的指针。
递归 reverseKGroup 函数使用递归来处理每一组节点的翻转。递归是一种重要的编程技巧它可以在解决问题时将问题拆分成更小的相同子问题。
Python 版本代码
类与方法 Python 使用类来定义链表节点代码中的 ListNode 类包含整数字段 val 和指向下一个节点的引用字段 next。Solution 类定义了处理问题的方法。
递归 与 Go 版本相同Python 版本也使用递归来处理每一组节点的翻转。
Java 版本代码
类与方法 Java 也使用类来定义链表节点代码中的 ListNode 类有一个整数字段 val 和一个指向下一个节点的引用字段 next。Solution 类定义了处理问题的方法。
递归 与 Go 和 Python 版本类似Java 版本也使用递归来处理每一组节点的翻转。
C 版本代码
类与指针 C 使用 struct 结构体来定义链表节点代码中的 ListNode 结构体有一个整数字段 val 和一个指向下一个节点的指针字段 next。Solution 类定义了处理问题的方法。
递归 与其他版本一样C 版本也使用递归来处理每一组节点的翻转。
指针操作 C 版本中涉及指针的操作如节点的指针赋值、遍历等。理解指针的基本概念和操作对于理解这些代码是很重要的。
26. Remove Duplicates from Sorted Array
题目
Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
Example 1:
Given nums [1,1,2],Your function should return length 2, with the first two elements of nums being 1 and 2 respectively.It doesnt matter what you leave beyond the returned length.Example 2:
Given nums [0,0,1,1,1,2,2,3,3,4],Your function should return length 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.It doesnt matter what values are set beyond the returned length.Clarification:
Confused why the returned value is an integer but your answer is an array?
Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.
Internally you can think of this:
// nums is passed in by reference. (i.e., without making a copy)
int len removeElement(nums, val);// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i 0; i len; i) {print(nums[i]);
}题目大意
给定一个有序数组 nums对数组中的元素进行去重使得原数组中的每个元素只有一个。最后返回去重以后数组的长度值。
解题思路
Go 版本解题思路
初始化一个指针 i用于指向当前不重复元素的位置。使用两个指针i 和 j其中 i 指向当前不重复元素的位置而 j 用于遍历数组。从数组的第二个元素开始遍历数组。比较当前元素和前一个元素是否相等。如果当前元素不等于前一个元素说明找到了一个新的不重复元素将指针 i 向前移动一位然后将当前不重复的元素放置在指针 i 的位置。重复步骤 3 和 4直到遍历完整个数组。返回不重复元素的数量长度需要加 1因为数组下标从 0 开始。
Python 版本解题思路
初始化一个指针 i用于指向当前不重复元素的位置。使用两个指针i 和 j其中 i 指向当前不重复元素的位置而 j 用于遍历列表。从列表的第二个元素开始遍历列表。比较当前元素和前一个元素是否相等。如果当前元素不等于前一个元素说明找到了一个新的不重复元素将指针 i 向前移动一位然后将当前不重复的元素放置在指针 i 的位置。重复步骤 3 和 4直到遍历完整个列表。返回不重复元素的数量长度需要加 1因为列表下标从 0 开始。
Java 版本解题思路
初始化一个指针 i用于指向当前不重复元素的位置。使用两个指针i 和 j其中 i 指向当前不重复元素的位置而 j 用于遍历数组。从数组的第二个元素开始遍历数组。比较当前元素和前一个元素是否相等。如果当前元素不等于前一个元素说明找到了一个新的不重复元素将指针 i 向前移动一位然后将当前不重复的元素放置在指针 i 的位置。重复步骤 3 和 4直到遍历完整个数组。返回不重复元素的数量长度需要加 1因为数组下标从 0 开始。
C 版本解题思路
初始化一个指针 i用于指向当前不重复元素的位置。使用两个指针i 和 j其中 i 指向当前不重复元素的位置而 j 用于遍历向量。从向量的第二个元素开始遍历向量。比较当前元素和前一个元素是否相等。如果当前元素不等于前一个元素说明找到了一个新的不重复元素将指针 i 向前移动一位然后将当前不重复的元素放置在指针 i 的位置。重复步骤 3 和 4直到遍历完整个向量。返回不重复元素的数量长度需要加 1因为向量下标从
代码
Go
// 定义一个函数用于从排序后的整数数组中去除重复元素并返回新数组的长度
func removeDuplicates(nums []int) int {// 如果数组为空直接返回0if len(nums) 0 {return 0}// 初始化一个指针i用于指向当前不重复元素的位置i : 0// 遍历数组从第二个元素开始for j : 1; j len(nums); j {// 如果当前元素不等于前一个元素说明找到了一个新的不重复元素if nums[i] ! nums[j] {// 将指针i向前移动一位i// 将当前不重复的元素放置在指针i的位置nums[i] nums[j]}}// 返回不重复元素的数量长度需要加1因为数组下标从0开始return i 1
}
Python
class Solution:def removeDuplicates(self, nums: List[int]) - int:# 如果数组为空直接返回0if not nums:return 0# 初始化一个指针i用于指向当前不重复元素的位置i 0# 遍历数组从第二个元素开始for j in range(1, len(nums)):# 如果当前元素不等于前一个元素说明找到了一个新的不重复元素if nums[i] ! nums[j]:# 将指针i向前移动一位i 1# 将当前不重复的元素放置在指针i的位置nums[i] nums[j]# 返回不重复元素的数量长度需要加1因为数组下标从0开始return i 1Java
class Solution {public int removeDuplicates(int[] nums) {// 如果数组为空直接返回0if (nums.length 0) {return 0;}// 初始化一个指针i用于指向当前不重复元素的位置int i 0;// 遍历数组从第二个元素开始for (int j 1; j nums.length; j) {// 如果当前元素不等于前一个元素说明找到了一个新的不重复元素if (nums[i] ! nums[j]) {// 将指针i向前移动一位i;// 将当前不重复的元素放置在指针i的位置nums[i] nums[j];}}// 返回不重复元素的数量长度需要加1因为数组下标从0开始return i 1;}
}
Cpp
#include vectorclass Solution {
public:int removeDuplicates(std::vectorint nums) {// 如果数组为空直接返回0if (nums.empty()) {return 0;}// 初始化一个指针i用于指向当前不重复元素的位置int i 0;// 遍历数组从第二个元素开始for (int j 1; j nums.size(); j) {// 如果当前元素不等于前一个元素说明找到了一个新的不重复元素if (nums[i] ! nums[j]) {// 将指针i向前移动一位i;// 将当前不重复的元素放置在指针i的位置nums[i] nums[j];}}// 返回不重复元素的数量长度需要加1因为数组下标从0开始return i 1;}
};
Go 版本解法所需基础知识
切片Slices和数组Arrays Go 中的切片是动态数组可以根据需要动态调整大小。在本题中我们使用切片来操作数组。循环和迭代 你需要理解 for 循环和如何迭代数组的元素。指针 i 是一个指向数组元素的指针你需要了解指针的概念和如何使用它来修改数组元素。
Python 版本解法所需基础知识
列表Lists Python 中的列表类似于数组可以包含多个元素。在本题中我们使用列表来操作数组。循环和迭代 你需要理解 for 循环和如何迭代列表的元素。索引和切片 你需要了解如何使用索引来访问列表元素以及如何使用切片来修改和操作列表。
Java 版本解法所需基础知识
数组 Java 中的数组是一组相同类型的元素的集合。在本题中我们使用数组来存储和操作元素。循环和迭代 你需要理解 for 循环和如何迭代数组的元素。数组索引 你需要了解如何使用索引来访问数组元素并理解数组索引从 0 开始的概念。
C 版本解法所需基础知识
向量Vectors C 中的向量类似于数组是一种动态数组容器。在本题中我们使用向量来存储和操作元素。循环和迭代 你需要理解 for 循环和如何迭代向量的元素。数组索引 你需要了解如何使用索引来访问向量元素并理解数组索引从 0 开始的概念。
27. Remove Element
题目
Given an array nums and a value val, remove all instances of that value in-place and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
The order of elements can be changed. It doesn’t matter what you leave beyond the new length.
Example 1:
Given nums [3,2,2,3], val 3,Your function should return length 2, with the first two elements of nums being 2.It doesnt matter what you leave beyond the returned length.Example 2:
Given nums [0,1,2,2,3,0,4,2], val 2,Your function should return length 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.Note that the order of those five elements can be arbitrary.It doesnt matter what values are set beyond the returned length.Clarification:
Confused why the returned value is an integer but your answer is an array?
Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.
Internally you can think of this:
// nums is passed in by reference. (i.e., without making a copy)
int len removeElement(nums, val);// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i 0; i len; i) {print(nums[i]);
}题目大意
给定一个数组 nums 和一个数值 val将数组中所有等于 val 的元素删除并返回剩余的元素个数。
解题思路
以下是每个版本的解题思路的详细介绍
Go 版本解题思路 使用两个指针 left 和 right 分别初始化为 0 和切片 nums 的长度。left 指向数组的起始位置right 指向数组的结束位置。 使用一个循环条件是 left 小于 right表示只要 left 还在 right 的左边就继续执行循环。 在循环中检查 nums[left] 是否等于目标值 val。如果相等说明需要将这个元素删除。 如果相等将 nums[left] 的值替换为 nums[right-1] 的值同时将 right 减 1相当于将目标值移到数组的末尾。这一步不需要真正删除元素只是覆盖了数组中的值。 如果 nums[left] 不等于目标值 val将 left 向右移动一位继续检查下一个元素。 循环结束后返回 left 的值即新数组的长度因为所有等于目标值 val 的元素都被移到数组末尾而剩余元素的个数就是 left 的值。
Python 版本解题思路 初始化两个指针 fast 和 slow初始都为 0。 使用一个循环遍历数组 nums条件是 fast 小于数组的长度。 如果 nums[slow] 不等于目标值 val将 slow 指针向后移动一位以保留当前元素。 如果 nums[slow] 等于目标值 val需要删除该元素。使用另一个循环将后面的元素逐个左移覆盖掉当前元素直到将目标值 val 移除。 每次循环结束后将 fast 指针向后移动一位以继续遍历下一个元素。 循环结束后slow 的值表示新数组的长度返回 slow。
Java 版本解题思路 初始化两个指针 left 和 right其中 left 指向数组的起始位置right 指向数组的结束位置。 使用一个循环条件是 left 小于 right表示只要 left 还在 right 的左边就继续执行循环。 在循环中检查 nums[left] 是否等于目标值 val。如果相等说明需要将这个元素删除。 如果相等将 nums[left] 的值替换为 nums[right-1] 的值同时将 right 减 1相当于将目标值移到数组的末尾。这一步不需要真正删除元素只是覆盖了数组中的值。 如果 nums[left] 不等于目标值 val将 left 向右移动一位继续检查下一个元素。 循环结束后返回 left 的值即新数组的长度因为所有等于目标值 val 的元素都被移到数组末尾而剩余元素的个数就是 left 的值。
C 版本解题思路 初始化两个指针 left 和 right其中 left 指向向量的起始位置right 指向向量的结束位置。 使用一个循环条件是 left 小于 right表示只要 left 还在 right 的左边就继续执行循环。 在循环中检查 nums[left] 是否等于目标值 val。如果相等说明需要将这个元素删除。 如果相等将 nums[left] 的值替换为 nums[right-1] 的值同时将 right 减 1相当于将目标值移到数组的末尾。这一步不需要真正删除元素只是覆盖了数组中的值。 如果 nums[left] 不等于目标值 val将 left 向右移动一位继续检查下一个元素。 循环结束后返回 left 的值即新向量的长度因为所有等于目标值 val 的元素都被移到向量末尾而剩余元素的个数就是 left 的值。
代码
Go
func removeElement(nums []int, val int) int {// 定义左右两个指针初始位置分别为切片的起始位置和结束位置left, right : 0, len(nums)// 使用循环当左指针小于右指针时继续执行操作for left right {// 如果左指针指向的元素等于目标值 valif nums[left] val {// 将左指针指向的元素替换为右指针指向的元素// 同时将右指针向左移动一位nums[left] nums[right - 1]right--} else {// 如果左指针指向的元素不等于目标值 val// 则将左指针向右移动一位继续检查下一个元素left}}// 循环结束后左指针的位置就是新切片的长度return left
}
Python
class Solution:def removeElement(self, nums: List[int], val: int) - int:# 初始化两个指针 fast 和 slow表示快慢指针fast, slow 0, 0# 使用 while 循环遍历列表while fast len(nums):# 如果慢指针指向的元素不等于目标值 valif nums[slow] ! val:slow 1else:# 如果慢指针指向的元素等于目标值 val需要删除该元素i slowwhile i len(nums) - 1:nums[i] nums[i 1]i 1# 快指针向右移动一位fast 1# 返回慢指针的位置即新列表的长度return slow
Java
class Solution {public int removeElement(int[] nums, int val) {// 初始化左右两个指针left指向切片的起始位置right指向切片的结束位置int left 0;int right nums.length;// 遍历数组当left小于right时继续执行while (left right) {// 如果当前元素等于目标值valif (nums[left] val) {// 将当前元素替换为右指针指向的元素// 同时将右指针向左移动一位nums[left] nums[right - 1];right--;} else {// 如果当前元素不等于目标值val// 则将左指针向右移动一位继续检查下一个元素left;}}// 循环结束后左指针的位置就是新数组的长度return left;}
}
Cpp
class Solution {
public:int removeElement(vectorint nums, int val) {// 初始化左右两个指针left指向向量的起始位置right指向向量的结束位置int left 0;int right nums.size();// 遍历向量当left小于right时继续执行while (left right) {// 如果当前元素等于目标值valif (nums[left] val) {// 将当前元素替换为右指针指向的元素// 同时将右指针向左移动一位nums[left] nums[right - 1];right--;} else {// 如果当前元素不等于目标值val// 则将左指针向右移动一位继续检查下一个元素left;}}// 循环结束后left的位置就是新向量的长度return left;}
};
当讨论这些不同编程语言版本的解决方案时需要了解以下基本知识
Go 版本
Go 是一种静态类型的编程语言具有内存管理和并发支持。在 Go 中切片是动态数组是一种引用类型可以动态扩展。在 Go 中数组和切片的下标从0开始。了解 for 循环以及条件语句如 if 语句。掌握指针的概念因为解决方案使用了两个指针即 left 和 right。Go 使用零值初始化变量因此需要确保变量的初始状态正确。
Python 版本
Python 是一种高级的解释型编程语言具有动态类型。Python 中的列表List是一种动态数组可以包含不同类型的元素。理解 while 循环以及条件语句如 if 语句。掌握列表的基本操作如访问、修改和删除元素。了解 Python 的索引规则列表的索引也是从0开始。
Java 版本
Java 是一种静态类型的编程语言具有强类型检查和垃圾回收。在 Java 中数组是一种固定大小的数据结构不能动态扩展。因此需要使用新的数组来实现元素的删除操作。掌握类和方法的定义以及循环结构如 while 循环。了解数组的基本操作包括访问和修改元素。
C 版本
C 是一种静态类型的编程语言具有高性能和低级内存控制。在 C 中使用标准库容器 vector 来表示动态数组也可以使用数组。掌握类和方法的定义以及循环结构如 while 循环。了解数组或 vector 的基本操作包括访问和修改元素。
28. Find the Index of the First Occurrence in a String
题目
Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack hello, needle ll
Output: 2Example 2:
Input: haystack aaaaa, needle bba
Output: -1Clarification:
What should we return when needle is an empty string? This is a great question to ask during an interview.
For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().
题目大意
实现一个查找 substring 的函数。如果在母串中找到了子串返回子串在母串中出现的下标如果没有找到返回 -1如果子串是空串则返回 0 。
解题思路
Go 版本
解法一
使用两个嵌套的循环在主字符串 haystack 中迭代每个字符外循环从 i 开始内循环从 j 开始。在内循环中比较 haystack[ij] 和 needle[j]如果不相等则跳出内循环继续外循环。如果内循环完成即 j 等于 needle 的长度则表示找到了匹配的子串返回 i即匹配子串在 haystack 中的起始索引。如果外循环完成即 ij 等于 haystack 的长度仍未找到匹配返回 -1。
解法二
使用 Go 标准库中的 strings.Index 函数该函数会在主字符串 haystack 中查找子串 needle 的第一次出现并返回其索引。如果找到匹配的子串则返回索引值如果未找到则返回 -1。
Python 版本
解法一
使用两个嵌套的循环在主字符串 haystack 中迭代每个字符外循环从 i 开始内循环从 j 开始。在内循环中比较 haystack[ij] 和 needle[j]如果不相等则跳出内循环继续外循环。如果内循环完成即 j 等于 needle 的长度则表示找到了匹配的子串返回 i即匹配子串在 haystack 中的起始索引。如果外循环完成即 ij 等于 haystack 的长度仍未找到匹配返回 -1。
解法二
使用 Python 字符串的内置方法 str.find(needle)该方法会在主字符串 haystack 中查找子串 needle 的第一次出现并返回其索引。如果找到匹配的子串则返回索引值如果未找到则返回 -1。
Java 版本
解法一
使用两个嵌套的循环在主字符串 haystack 中迭代每个字符外循环从 i 开始内循环从 j 开始。在内循环中比较 haystack.charAt(ij) 和 needle.charAt(j)如果不相等则跳出内循环继续外循环。如果内循环完成即 j 等于 needle 的长度则表示找到了匹配的子串返回 i即匹配子串在 haystack 中的起始索引。如果外循环完成即 ij 等于 haystack 的长度仍未找到匹配返回 -1。
解法二
使用 Java 字符串的内置方法 haystack.indexOf(needle)该方法会在主字符串 haystack 中查找子串 needle 的第一次出现并返回其索引。如果找到匹配的子串则返回索引值如果未找到则返回 -1。
C 版本
解法一
使用两个嵌套的循环在主字符串 haystack 中迭代每个字符外循环从 i 开始内循环从 j 开始。在内循环中比较 haystack[ij] 和 needle[j]如果不相等则跳出内循环继续外循环。如果内循环完成即 j 等于 needle 的长度则表示找到了匹配的子串返回 i即匹配子串在 haystack 中的起始索引。如果外循环完成即 ij 等于 haystack 的长度仍未找到匹配返回 -1。
解法二
使用 C 字符串的内置方法 haystack.find(needle)该方法会在主字符串 haystack 中查找子串 needle 的第一次出现并返回其索引。如果找到匹配的子串则返回索引值如果未找到则返回 -1。
这些解题思路详细描述了每个版本的代码是如何逐步寻找匹配子串的过程并在找到匹配时返回相应的索引或在未找到匹配时返回 -1。
代码
Go
import strings// 解法一
func strStr(haystack string, needle string) int {// 外层循环遍历haystack中的每个字符for i : 0; ; i {// 内层循环遍历needle中的每个字符for j : 0; ; j {// 如果j等于needle的长度说明needle中的所有字符都已经在haystack中匹配成功if j len(needle) {return i // 返回匹配成功的起始索引位置i}// 如果ij等于haystack的长度说明已经遍历完haystack但仍未找到匹配if ij len(haystack) {return -1 // 返回-1表示未找到匹配}// 如果当前needle中的字符与当前haystack中的字符不相等跳出内层循环if needle[j] ! haystack[ij] {break}}}
}// 解法二
func strStr1(haystack string, needle string) int {// 使用标准库strings的Index函数来查找needle在haystack中的位置// 如果找到返回第一次出现的索引位置如果未找到返回-1return strings.Index(haystack, needle)
}
Python
class Solution:def strStr(self, haystack: str, needle: str) - int:# 解法一自己实现的字符串匹配算法for i in range(len(haystack) 1):for j in range(len(needle) 1):if j len(needle):return iif i j len(haystack):return -1if needle[j] ! haystack[i j]:breakclass Solution:def strStr(self, haystack: str, needle: str) - int:# 解法二使用Python内置函数indexreturn haystack.find(needle)
Java
class Solution {public int strStr(String haystack, String needle) {// 解法一自己实现的字符串匹配算法for (int i 0; ; i) {for (int j 0; ; j) {if (j needle.length()) {return i;}if (i j haystack.length()) {return -1;}if (needle.charAt(j) ! haystack.charAt(i j)) {break;}}}}
}
class Solution {public int strStr(String haystack, String needle) {// 解法二使用Java内置函数indexOfreturn haystack.indexOf(needle);}
}
Cpp
class Solution {
public:int strStr(string haystack, string needle) {// 解法一自己实现的字符串匹配算法for (int i 0; ; i) {for (int j 0; ; j) {if (j needle.length()) {return i;}if (i j haystack.length()) {return -1;}if (needle[j] ! haystack[i j]) {break;}}}}
};
class Solution {
public:int strStr(string haystack, string needle) {// 解法二使用C内置函数findsize_t index haystack.find(needle);return index ! string::npos ? index : -1;}
};
Go 版本
解法一
字符串操作需要了解如何访问字符串的字符字符串的长度等。循环需要熟悉 for 循环以便在字符串中进行遍历操作。条件语句使用条件语句来检查是否匹配子串以及何时返回结果。索引和切片可以通过索引访问字符串的单个字符并使用切片来获取子串。
解法二
字符串操作需要了解 Go 标准库中字符串处理函数的用法例如 strings.Index。
Python 版本
解法一
字符串操作需要了解如何访问字符串的字符字符串的长度等。循环需要熟悉 for 循环以便在字符串中进行遍历操作。条件语句使用条件语句来检查是否匹配子串以及何时返回结果。
解法二
字符串操作需要了解 Python 字符串的一些内置方法如 str.find。
Java 版本
解法一
字符串操作需要了解如何访问字符串的字符字符串的长度等。循环需要熟悉 for 循环以便在字符串中进行遍历操作。条件语句使用条件语句来检查是否匹配子串以及何时返回结果。
解法二
字符串操作需要了解 Java 字符串的一些内置方法如 indexOf。
C 版本
解法一
字符串操作需要了解如何访问字符串的字符字符串的长度等。循环需要熟悉 for 循环以便在字符串中进行遍历操作。条件语句使用条件语句来检查是否匹配子串以及何时返回结果。
解法二
字符串操作需要了解 C 字符串的一些内置方法如 find。数据类型转换使用 static_cast 进行数据类型转换因为 find 返回的是 size_t 类型而我们需要返回 int 类型的结果。
