您当前所在分类目录: leetcode

[leetcode题解]215.Kth Largest Element in an Array(数组中找第k大数)

leetcode,215,Kth Largest Element in an Array,给定一个包括若干元素的数组以及一个k,要求在数组中找出第k大的数。 通常的思路是排序,然后可以快速找到第k大的数,时间复杂度o(nlogn)。比较好的方法是借助快排的思想,一次轴分,可以以o(n)的时间复杂度找到第k大数。 c++代码: class Solution { public: //author:凌风 …

Continue reading

[leetcode题解]143. Reorder List(链表重排序)

leetcode第143题,recorder list,属于linked-list相关的题目。 题目给定一个单链表,然后要求按给定的顺序重新排列所有元素,要求在原地做,而且不能修改节点中的值,只能修改节点的插入顺序。重排序的规则如下示例: L:a0->a1->a2->a3…..->an 将其修改为L:a0->an->a1->an-1->& …

Continue reading

[leetcode题解]2.Add Two Numbers

leetcode,2,Add Two Numbers,给定两个单链表,将两个单链表从左到右进行相加,题目中已知不会出现前导0。本题可以直接对两单链表同时进行遍历相加即可,保留一个进位,检测最后是否要进行正确进位,python和c++两种语言写,代码如下: python代码 class Solution(object): def addTwoNumbers(self, l1, l2): “”” :t …

Continue reading

[leetcode题解]19.Remove Nth Node From End of List(删除倒数N个元素)

leetcode,19,Remove Nth Node From End of List,给定一个单链表,删除倒数第N个元素,要求进行一遍遍历即可。思路是利用两个指针,一个提前走N步,然后另一个指针指向开头,两个指针同时走,当前面的指针到尾部时,后面的指针正好位于要删除的元素位置。为了得到要删除位置的前一个位置,可以加入一个预头,然后,前面的指针从头开始,后面的指针从预头开始。 c++代码: cl …

Continue reading

[leetcode题解]21.Merge two Sorted Lists(两排序链表合并)

leetcode,21,Merge Two Sorted Lists,单链表合并问题,合并两个已排序链表为一个完整的已排序链表。 直接使用两个指针依次比较其中值大小即可,小的插入,并且指针后移,最后不要忘记把剩下的非空链表加入链尾。 此题的升级版本为leetcode,23,Merge K Sorted Lists.  c++代码: class Solution { public: Lis …

Continue reading

[leetcode题解]23.Merge K Sorted Lists(多链表合并)

leetcode,23题,Merge K Sorted Lists,多排序链表合并为一个有序链表问题。可以直接使用priority_queue或者heap。 多个链表以vector形式组织,vector中可能含有空链表,所以建堆或者初始化优先队列之前先对vector进行过滤,将空链表过滤掉。 注意优先队列的写法,类型,底层容器,以及要用到的比较器,比较器是一个重载了括号操作符的普通类。 c++题解 …

Continue reading

[leetcode题解]24.Swap Nodes in Pairs(节点交换)

leetcode 第24题,将链表中相邻元素位置颠倒,题目要求不能改变元素节点中元素的值,只能改动节点位置。也就是要求在链表中删除插入。 python代码如下: # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = No …

Continue reading

[leetcode题解]25.Reverse Nodes in k-Group(链表每k个元素逆置)

这个题很有意思,虽然标的难度为hard,但是其实就是链表相关知识点的一个小综合,比如尾插法,段遍历,双指针操作等。题目给定一个单链表和一个k值,要求将链表中的元素从表头开始每k个元素组成一个组,然后组内的元素进行逆置操作,如果最后一组不满k个元素,则该组中的元素顺序保持不变。特别的,题目中说操作过程中不能改变元素节点的值,只能对整个节点进行操作,这就要求我们要通过链表指针的操作来完成上述过程。 总 …

Continue reading

[leetcode题解]82.Remove Duplicates from Sorted List-II(排序链表保留唯一)

上一篇论文中写了一个排序链表去重的题目解法,那个题目要求对于重复的元素只保留一个,而本题给定一个排序链表,要求把重复的元素全部删除,所以与上个题目有点差异,但是解法可以基本一致,这里对每个元素,判断其是否唯一,如果不唯一就直接删除,如果唯一,那么就将这个唯一的元素拿出来插入新的链表中,最后将新的链表返回去即可。 题意演示 Given 1->2->3->3->4->4- …

Continue reading

[leetcode题解]61. Rotate List(链表旋转)

题目中给定一个单链表和一个数字k,要求将链表循环右移k次,每次将最右边的元素移动到最左边。最简单的思路先找到最后的k个元素的起始位置,然后把这k个元素直接搬到链表最前面并插入即可(可以使用尾插法,当然也可以把最后一个元素记录下来,然后直接将整段插入)。但是这里k的值可能非常大,是链表长度的好几倍,我们要先处理下k值,我们需要的k值是对链表长度取余得到的值,所以这里先写一个方法求得链表的长度,然后k …

Continue reading

[leetcode题解]83.Remove Duplicates from Sorted List(排序链表去重)

题目给定一个单链表,该单链表已排序,要求删除所有重复值的节点。因为链表已排序,所以相同的值的节点都相邻,所以本题是相邻节点去重问题,可以直接两个指针操作即可。比较简单的排序链表去重问题。一种逐个去重,一种把所有重复的找出来,直接去除所有重复元素,两种方法分别是python实现和c++实现。 python代码: class Solution(object): def deleteDuplicates …

Continue reading

[leetcode题解]86.Partition List(链表分割)

leetcode第86题,partition-list,是一个关于链表分割的题目。题目给定一个单链表和一个数x,要求链表中节点val小于x的节点全部在左边,而大于等于x的节点全部在右边,而且左右两边中的元素分别保持在原链表中的相对位置。总体来说就类似于快排中的partition部分。所以这个的实现可以直接使用快排的中partition方法直接在单链表上更换节点的值就好。 这里使用最原始的思路,就是 …

Continue reading

[leetcode题解]92.Reverse Linked List II(链表部分逆置)

leetcode第92题,reverse-linked-list-ii,题目是一个单链表的题目,给定一个单链表,然后告诉一个区间[n,m],然后要求将链表中第n到m个节点逆序,这里保证n和m是合法的,即1 <= n <= m <= 链表长度,链表的节点id从1开始计数。 思路比较简单,设定两个指针,以前以后,首先数n个节点,然后将后面的m – n个节点进行头插(逆序插 …

Continue reading

[leetcode题解]109.Convert sorted list to binary search tree

leetcode 109,convert sorted list to binary search tree,给定一个已排好序的单链表,将其转换为一棵平衡二叉查找树,平衡二叉查找树要求左右子树的高度差小于等于1,而且左子树上的节点都小于等于当前根节点,有子树上的节点都大于当前根节点。 由于单链表本身就已经排好序了,所以,只要保证左右子树高度满足即可,可以以链表的中心节点为界,将链表一分为二,这样左 …

Continue reading

[leetcode题解]138.Copy List with Random Pointer(linked-list)

leetcode,138.copy list with random pointer. 正常的单链表中只有一个next的指针指向下一个元素的地址,本题给定一个链表,这个链表比较特殊,不仅有指向下一个元素的next指针,还有一个指向链表中随机元素的一个random指针(random pointer)。 题目要求对该链表进行拷贝,在新的拷贝中,元素的链接关系不变,注意这里的拷贝要求的是深拷贝。 由于r …

Continue reading

[leetcode题解]142.Linked List Cycle II(python + c++)

leetcode第142题,linked list cycle ii,前面有道题目是判断单链表是否有环。 本题就是将上个题目进行改进,首先判断是否有环,如果有环则返回环的入口节点,如果没有环的话返回NULL。 本题的解法首先按照上篇文章中提到的快慢指针法来判断环,并返回快慢指针相遇的节点。 然后,将一个指针从头开始,另一个指针从相遇节点开始,一步一步走下去,直到两者相遇的点就是环的入口节点。 直接 …

Continue reading

[leetcode题解]141.Linked List Cycle(链表环问题)

leetcode题解141.Linked list cycle,给定一个单链表,判断该单链表是否有环问题,这个问题蛮简单的,但是在面试中也是经常被问到的,所以要注意一下。解决这道题的思路就是使用两个指针,一个一次走两步,一个一次走一步,如果有环两者必定在某个位置处相遇,只要快的走到了NULL节点,则说明此链表无环。这就是快慢指针找环法,是比较经典的问题。 c++代码如下: class Soluti …

Continue reading

[leetcode题解]147.Insertion Sort List

对单链表的排序,前几天写过一篇文章使用o(nlog(n))的时间复杂度进行排序,当时说可选的方法是利用归并或者快排对单链表进行排序,这个题目同样给定一个单链表,只不过这里要求用插入排序对其进行排序。在数组中我们使用插入排序的时候通常在寻找插入位置的时候是从后向前,这样可以同时查找并把较大的元素后移一位,然后腾出要插入的位置,但是在单链表中就不行了,首先,单链表不能逆向遍历,第二,单链表无需移动,可 …

Continue reading

[leetcode题解]148.sort list

leetcode第148题,sort list,题目给定一个单链表,要求用o(nlogn)的时间复杂度对链表进行排序,其实对于单链表的排序可以使用快排,也可以使用归并排序,对于已排序链表的合并由于比较简单,所以这里就使用归并排序实现一下。 设计了一个找链表中间节点的方法halfList,找到中间节点后将链表一分为二,左右各进行归并排序就好了,最后一个合并两个已排序链表的操作就可以了。 下面使用c+ …

Continue reading

[leetcode题解]160.Intersection of Two Linked Lists

leetcode第160题,给定两个链表的头节点,求两个链表是否相交,如果相交则返回相交的首节点,否则返回NULL。 思路是两个指针分别从头开始走,直到一个指针为NULL,这说明另一个链表比较长,而且长的这个链表剩下的节点个数正好是长度超出的节点数。这个时候把长的从头开始走,走的步数为整下的节点个数,这样短的节点从头开始,就能保证两者要走的节点数相同,也就是如果相交,那么两者分别走下去一定会在交点 …

Continue reading

[leetcode题解]203.Remove Linked List Elements

leetcode第203题,remove linked list elements,题目给定一个单链表和一个值,要求将该单链表中所有val与该给定值相等的节点删除,结果返回删除后的链表,原链表中的元素相对位置不变。 例如: Given: 1 –> 2 –> 6 –> 3 –> 4 –> 5 –> 6, val = 6 Return: 1 –> 2 –> 3 –> 4 –> 5 …

Continue reading

[leetcode题解]206-Reverse-Linked-List

简单链表逆置,这个在面试中多次要求被写,是在搞不懂这么简单的问题为什么要放在面试中,直接用头插法就可以了,下面是c++和python代码 c++代码: class Solution { public: ListNode* reverseList(ListNode* head) { ListNode *pre = new ListNode(-1); ListNode *p = head; while …

Continue reading

[leetcode题解]234.Palindrome-Linked-list

leetcode第234题,简单链表操作的题目,题目要求判断给定的单链表是否是回文的,是返回true,否则返回false。 题目比较简单,直接暴力解,通过快慢指针找到中点,然后把前半部分逆置一下,最后把前后向部分判断元素是否依次相等即可,全相等则回文,否则就不是回文。下面用了c++和python同时实现,两者的思路是完全一样的。 c++代码: class Solution { public: bo …

Continue reading

[leetcode题解]237.Delete a node in a linked list-python+c++

leetcode第237题,题目要求写一个函数实现删除链表中的一个节点,该节点以指针给出。一般链表中删除某个节点的时候我们通常是找到要删除节点的前一个节点,然后把当前节点删除掉,但是这里直接给了要删除节点的指针,题目中也说了,该节点不会是尾节点,这样我们就可以把当前节点的内容与当前节点的下一个节点的内容交换,然后删掉下一个节点就可以了。 所以代码比较简单,可以用不同的方法,以下是python和c+ …

Continue reading

[leetcode题解]328 Odd Even Linked List(python+c++)

题目给定一个包含数字的链表,要求把链表进行修改,保证奇数位置的元素按顺序排在前面,然后是偶数位置的元素一次排在后面。返回修改后的链表即可。 简单的思路就是把所有奇数位的元素摘出来按原有顺序组成一个链表even然后把所有偶数位置的元素摘出来组成一个新的链表odd,然后把odd链表链在even链表之后就可以了。这样能保证空间复杂度o(1),时间复杂度o(n)。如下为c++和python两个版本的代码。 …

Continue reading

[leetcode题解]96. Unique Binary Search Trees

如果把示例数据的顺序改一下,就可以看出规律了。 1 1 2 3 3 \ \ / \ / / 3 2 1 3 2 1 / \ / \ 2 3 1 2 比如,以 1 为根的树的个数,等于左子树的个数乘以右子树的个数,左子树是 0 个元素的树, 右子树是 2 个元素的树。以 2 为根的树的个数,等于左子树的个数乘以右子树的个数,左子树是 1 个元素的树,右子树也是 1 个元素的树。依此类推。 当数组为 …

Continue reading