精华内容
下载资源
问答
  • 对于“访问单向链表倒数第k个结点”,比较成熟的算法是快慢指针,即定义两个指针,一个指针先走k个结点,之后两个指针再一起走,从而拿到倒数第k个结点。 快慢指针算法如下: LinkNode* findNode(LinkNode* ...
      对于“访问单向链表倒数第k个结点”,比较成熟的算法是快慢指针,即定义两个指针,一个指针先走k个结点,之后两个指针再一起走,从而拿到倒数第k个结点。
    快慢指针算法如下:
    LinkNode* findNode(LinkNode* head){//找到单向链表倒数第2个结点,快慢指针
    LinkNode* temp = head->next->next;
    LinkNode* result = head;
    while (temp != NULL){
    result = result->next;
    temp = temp->next;
    }
    return result;
    }

    普通算法,需要循环两次
    LinkNode* findNode2(LinkNode* head){//找到单向链表倒数第2个结点,循环两次
    int len = 0;
    LinkNode* result = head;
    while (result != NULL){
    result = result->next;
    len++;
    }

    result = head;
    while (len-- > 2){
    result = result->next;
    }
    return result;
    }

    刚开始接触快慢指针的时候,觉得这种算法很巧妙,四两拨千斤,只需要循环一次即可解决问题。但后来仔细分析之后发现了点问题,就是快慢指针中虽然只有一个循环,但循环体中却有两个访问语句,这样算起来的话,它的整体访问次数也并没有减少啊,以上面问题为例,两种算法最终都是访问了2n次结点啊。这样想来,快慢指针是不是没有提高运行效率呢?

      实验是检验一切问题的标尺
    我们只需要简单的做个实验即可:


    从上面可以看到,在大数量级下,快慢指针确实效率更高,并且接近一倍。

    这说明快慢指针还是依旧的牛逼,那刚开始的怀疑应该怎么解释呢?
    这是就需要仔细分析for循环执行过程中的耗时在哪里,有两个一方,一是for循环中的每次循环切换,二是循环体中的语句耗时。
    我们可以大胆猜测一下上面的例子中主要的耗时是在每次的循环切换,循环体本身耗时不多,所以两个for循环要比一个for循环慢。

    为了验证这个猜测,我们可以再做一个实验:
    //对两个数组中的元素进行赋值操作
    void change(int* array,int* array2,int n){
    int i = 0;
    for (int i = 0; i < n; i++){
    array[i] = rand();//因为使用了随机树,所以相对耗时
    array2[i] = rand();
    }
    }

    void change2(int* array, int* array2, int n){
    for (int i = 0; i < n; i++){
    array[i] = rand();
    }
    for (int i = 0; i < n; i++){
    array2[i] = rand();
    }
    }

    我们来看一下测试结果


    这时我们再看一下发现,把两条语句一起写到一个循环体中已经体现不出来优势了。大致上佐证了刚才的猜测,循环体本身是耗时操作,这样循环本身的切换耗时就不是关键了。

    但是对于普通的不是很耗时的操作,把两条写在一块还是能提高效率的,比如快慢指针访问倒数第k个结点。


    展开全文
  • 文章目录题目要求解题思路代码复杂度分析工作之余刷刷题写写题解...链表题中看到 O(n)O(n)O(n) 时间复杂度且 O(1)O(1)O(1) 空间复杂度可以考虑快慢指针就相当于数组题看到 O(n)O(n)O(n) 时间复杂度且 O(1)O(1)O(1) 空间

    题目要求

    判断一个链表是否为回文链表。

    解题思路

    不限制时间复杂度的情况下是非常简单的题目,可以有多种方法完成本题。

    如果限制了O(n)O(n) 时间复杂度且 O(1)O(1) 空间复杂度那么可以按照以下思路。

    链表题中看到 O(n)O(n) 时间复杂度且 O(1)O(1) 空间复杂度可以考虑快慢指针就相当于数组题看到 O(n)O(n) 时间复杂度且 O(1)O(1) 空间复杂度可以考虑双指针一样。

    那么从快慢指针开始思考。我们知道,快慢指针可以找链表的中点。回文链表只需要对链表中点两边进行比较就可以知道结果,因此先用快慢指针找到链表的中点。

    找到中点以后需要令前半部分末尾等于 NoneNone,因此为了方便起见,前半部分找到中点左边的一个点,就停止。假设中间节点是 medianmedian,我们希望 slowslow 停留在 medianmedian 的左边第一个节点,这样我们只要令 slow.next=Noneslow.next = None 就可以得到左半部分链表。

    此时右半部分链表只需要令 cur=slow.nextcur = slow.next,这样 curcur 就是右半链表。

    利用双指针反转链表的方式,反转链表之后进行比较节点的值就可以得到结果。在比较的时候,我们之前这样处理以后,右半部分一定不大于左半部分的长度,因此遍历右半部分,这样如果链表长度是奇数的时候,不需要考虑中间节点。

    以下用多张图具体说明这个过程:

    • 链表长度是奇数

    ppt1.jpg2.ppt2.jpg3.ppt3.jpg4.ppt4.jpg5.ppt5.jpg6.ppt6.jpg7.ppt7.jpg8.ppt8.jpg9.ppt9.jpg10.ppt10.jpg11.ppt11.jpg12.ppt12.jpg13.ppt13.jpg

    • 链表长度是偶数时,可以尝试用同样的方式处理

    代码

    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def isPalindrome(self, head: ListNode) -> bool:
            if not head:
                return True
            fast = slow = head
            while fast.next and fast.next.next:
                fast = fast.next.next
                slow = slow.next
            pre = None
            cur = slow.next
            slow.next = None
            while cur:
                tmp = cur.next
                cur.next = pre
                pre = cur
                cur = tmp
            while pre:
                if head.val != pre.val:
                    return False
                head = head.next
                pre = pre.next
            return True
    

    复杂度分析

    时间复杂度 O(n)O(n) 其中 nn 是链表的长度
    空间复杂度 O(1)O(1) 没有使用额外空间

    工作之余刷刷题写写题解,我的Leetcode主页

    https://leetcode-cn.com/u/airesearcherjhm/

    展开全文
  • 一般时间复杂度为O(n),空间复杂度O(1). 双指针用途广泛,熟悉的归并快排,二分查找就是用的双指针。下面就总结一下双指针这个算法技巧。 本文双指针的内容有: 双指针的各种类型。 双指针的应用。 第一部分: 我...

    双指针,就是用两个变量在数组中经过某种形式的移动得到结果的操作。一般时间复杂度为O(n),空间复杂度O(1). 双指针用途广泛,熟悉的归并快排,二分查找就是用的双指针。下面就总结一下双指针这个算法技巧。

    本文双指针的内容有:

    1. 双指针的各种类型。
    2. 双指针的应用。

    第一部分:

    我认为双指针一般有两种类型:前后指针,左右指针。
    **前后指针:**也可以称为快慢指针。假设有两个指针 l 和 r ,l为慢指针,r为快指针 。一开始l和r在同一位置, r 往后遍历,探寻一下后面的内容,达到某种条件之后 l 指针跟上。这样往复直到遍历完数组。
    **左右指针:**l 和 r 在数组的两端,经过某种条件的判定决定 l 向右还是 r 向左,直到 l > r.

    第二部分:

    1. 前后指针

    前后指针最常见的应用就是“尺取法”,又称“滑动窗口”。
    尺取法,经常用在求子区间的问题上,是一个很巧妙的方法,时间复杂度通常在O(n).
    **运用尺取法的情况:**经常用在求子区间的问题上。比如说,给你一个区间[1,n],让你求最大/小子区间使得该区间满足条件xxx.
    常规操作:
    假设让你在区间[1,n]中求子区间使得该区间满足条件a.

    1. 设两个指针 l = r = 0,ans记录区间 [l,r] 的信息,index记录最终结果的下标,len记录最终结果的长度。
    2. r 先往后遍历,同时更新ans,直到ans不满足条件a,即区间 [l,r] 不满足条件a.
    3. l 开始往后遍历,同时更新ans,直到ans重新满足条件a.
    4. 如此反复,直到 r >= n结束。

    在这个过程中index, len根据题目所要求的子区间来更新。下面举一个实际例子来详细解释吧。

    给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s
    的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。

    示例:

    输入: s = 7, nums = [2,3,1,2,4,3]
    输出: 2
    解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/minimum-size-subarray-sum

    题目要求的是一个最小子区间的长度,条件为区间和>=s. 那么来分析一下如何用尺取法完成这道题。

    1. 初始化:l = r = 0, sum = nums[0], ans = 0.
    2. r 先往后遍历,sum += nums[r]. 可以发现 r = 3 时 sum = 8 > 7,当前区间 [l,r] 不满足条件。
    3. l 往后遍历,sum -= nums[l]. 可以发现 l = 1 时 sum = 6 < 7,当前区间满足条件,更新ans = r-l+1=3. 因为区间满足条件了, r 再继续往后遍历直到区间条件再一次不满足。
    4. 按照这样的规律一直下去,就可以得到ans最小值。

    以上就是这道题的大致解法。如果用常规方法,就是枚举所有的区间,时间复杂度O(n^2);而用尺取法,时间复杂度为O(n). 快了许多。当然,可能你会想为什么尺取法不用枚举完所有的区间就可以得到这个正确答案。下面对这个问题解释一下。
    首先,我们枚举区间是[2],[2,3],[2,3,1],[2,3,1,2],[2,3,1,2,4],[2,3,1,2,4,3],[3]…
    你发现了吗?当区间在[2,3,1]往后,其实就没必要枚举了。因为每个数都是正整数,后面的区间只会比[2,3,1]大。也就是说,只有[2],[2,3],[2,3,1]是枚举的有效区间。而尺取法里的 r 就是起到这样的效果。在第一次发现区间不满足条件时停下来,让 l 跟上。l 一旦走到满足条件的位置之后立马停下来,r继续走。这样就保证了 [l,r] 始终控制在有效区间左右,在O(n)的时间内枚举了所有有效区间。

    这道题的代码在此:https://blog.csdn.net/Skyed_blue/article/details/103056163

    相信经过这一道题你已经对尺取法这种朴实无华的技巧心生赞叹了。看着以前面对这种题目只会写TLE的自己,是时候开始变强了!下面推几道滑动窗口的题练练!

    poj2566
    题意:给定一个数组和一个值t,求一个子区间使得其和的绝对值与t的差值最小,如果存在多个,任意解都可行。
    基本算是模板题,自己熟悉一下。

    leetcode 统计「优美子数组」
    有一点点难,除了尺取还需要其他的一些思想。不过还是很容易想到从尺取法开始构思。

    leetcode 最小覆盖子串
    leetcode的hard题,尺取思想很明显,不过中间有各种各样隐藏的细节需要考虑到并且处理好,比较繁琐的题。

    leetcode 替换后的最长重复字符
    看题意可以大致判断与尺取思想有关,不过对于区间的条件比较隐晦,没有前几道那么直白,需要自己琢磨一下。

    蓝桥杯 日志统计
    如果不是对尺取法的应用很熟悉,其实还是不容易想到用尺取法的。因为题目信息太多了,想的构思就有许多。这道题没找到哪个oj平台有,放出来见识一下尺取法在一些竞赛题目中的巧妙运用。

    当然了,前后指针还有其他的用法。

    leetcode 删除排序数组中的重复项 II
    先用 r 指针探寻,再让 l 跟进。其实也有点尺取的意思。

    题目先更新到这,之后看到好的题目也会更新博客。

    2. 左右指针

    左右指针也巧妙,不过不像尺取法那么有章可循。左右指针局限性比较强,在某些特定题目下才有其一席之地。也可能是我对左右指针理解不深。
    下面上两道左右指针有“奇效”的特定题目。
    leetcode 盛最多水的容器
    leetcode 接雨水
    这两道题目算是对左右指针比较“偏心”的题目了。反正我是想不来。

    下面尽量讲一下左右指针的一些比较常见的应用吧。
    排好序的Two Sum问题:
    给定一个有序数组,在里面找两个数使其和为x. 比如说有这么一个数组:[2,7,11,15],x = 9.
    对于“有序”的问题,比较敏感的可以想到二分吧?这道题确实可以用二分做,i 枚举数组,在 i 后面二分查找 x-a[i] 是否存在即可。时间复杂度O(nlgn).
    不过这道题运用双指针,可以把时间复杂度降到O(n). 我们将 l 和 r 放在数组两端,如果 a[l]+a[r] > x,r 向左逼近;a[l] + a[r] < x,l 向右逼近。直到a[l]+a[r] == x. 若 l > r,则不存在两个数其和为x.
    其实这种方法也和尺取法原理差不多,就是减少不必要的枚举。
    如果该数组元素的位置不是固定的,也可以先排序然后再考虑二分或者双指针。
    leetcode 三数之和
    左右指针经典例子,和上面那道类似。

    左右指针就当作一个技巧。想一道题目的时候看看数组左右两端向中间逼近能否贪心就是左右指针的运用了。

    双指针,时间复杂度O(n),空间复杂度O(1),这是两个指针的跳动所带来的奇妙!关于双指针的妙处还有很多,不过大部分都挺难想到,这里就不表了。

    展开全文
  • 时间复杂度 O(n) 空间复杂度 O(1) 在数组开头设置一个指针,末尾设置一个指针。 当前指针指向的元素是奇数,则向后移动,直到指向元素是偶数(前指针在尾指正前) 当尾指针指向的元素是偶数,则向前移动,直到指向...

    调整数组顺序使奇数位于偶数前面

    个人博客

    输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。

    题解

    • 快慢指针

      • 时间复杂度 O(n) 空间复杂度 O(1)
      • 在数组开头设置一个指针,末尾设置一个指针。
      • 当前指针指向的元素是奇数,则向后移动,直到指向元素是偶数(前指针在尾指正前)
      • 当尾指针指向的元素是偶数,则向前移动,直到指向元素是奇数(前指针在尾指正前)
      class Solution {
          public int[] exchange(int[] nums) {
              int front = 0;
              int behind = nums.length - 1;
      
              while(front<behind){
                  while((nums[front]&1) == 1 && front < behind){
                      front++;
                  }
                  while((nums[behind]&1) == 0 && behind > front){
                      behind--;
                  }
                  if(front < behind){
                      int temp = nums[front];
                      nums[front] = nums[behind];
                      nums[behind] = temp;
                  }
              }
              return nums;
      
          }
      }
      

      L7qITS

    总结

    • 可以用位运算优化取模

    • 需要判断元素指向的位置,防止数组越界

    展开全文
  • 双指针算法引言1、对撞指针2、快慢指针3、滑动窗口 引言 什么是双指针? \quad \quad严格的来说,双指针只能说是是算法中的一种技巧。双指针指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两...
  • 快慢指针

    2019-09-20 10:46:22
    快慢指针 快慢指针中的快慢指的是移动的步长,即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2,慢指针每次向前移动1次。 快慢指针的应用 (1)判断单链表是否存在环 如果链表存在环,就好像操场...
  • 使用快慢指针,可以在 O(n) 的时间复杂度 O(1) 的空间复杂度完成答题 题型 对于线性表类型的题目,如果要求中间某个特定位置的结点值,我们就可以用到快慢指针 关键字 要求线性表中某个结点的结点值 解题步骤 若题型...
  • 快慢指针应用总结

    2019-09-12 14:04:07
    快慢指针 快慢指针中的快慢指的是移动的步长,即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2,慢指针每次向前移动1次。 快慢指针的应用 (1)判断单链表是否存在环 如果链表存在环,就好像操场...
  • 快慢指针&双指针

    2021-03-11 11:27:25
    快慢指针在算法中的应用 天下武功, 无坚不破, 唯快不破 ——— 某功夫大佬 本文为我,leetcode easy player,algorithm小xuo生在刷题过程中对快慢指针的应用的总结 ps: 向leetcode里耐心写解题, 特别是画图解题的...
  • 快慢指针应用

    2019-02-08 21:16:36
    快慢指针 快慢指针中的快慢指的是移动的步长,即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2,慢指针每次向前移动1次。 快慢指针的应用 (1)判断单链表是否存在环 如果链表存在环,就好像操场的...
  • 时间复杂度O(n) 空间复杂度O(1) 快慢指针 快慢指针非常适合这种有中点的问题,并且在移动快慢指针的过程,将原有的链表拆成了两部分(注意:对原链表进行了操作,若为工程不该这么做,但是题目要求空间复杂度O(1)),...
  • 快慢指针的做法比较有趣,只需要一个 for 循环即可解决,时间复杂度为 O(n) ,总体思路就是有两个指针,前面一个后面一个,前面的用于搜索需要删除的值,当遇到需要删除的值时,前指针直接跳过,后面的指针不动,当...
  • [寻找环链表入口点] 快慢指针数学原理剖析

    千次阅读 多人点赞 2018-12-02 14:25:25
    想必大家都知道这个问题应该使用快慢指针去求解,因为它具有最优的时间复杂度O(n)。但是大家可能对快慢指针的数学原理不是很清楚,为啥它能达到最优。详细读了这篇文章,大家必定豁然开朗,掌握快慢指针背后的数学...
  • 快慢指针(思想)

    千次阅读 2018-02-03 00:11:16
    所谓「快慢指针」是指设定两个指针,其中快的指针的移动速度是慢的指针的移动速度的两倍;“快慢指针”方法主要用来解决两类问题,即“判断一个链表是否为循环链表”以及“寻找一个有序链表的中位数” 针对该算法...
  • 链表常用套路:快慢指针

    千次阅读 2019-04-17 18:30:04
    使用多个指针是解决链表问题的常用套路(诸如反转链表需要三个指针前中后、默认在head节点前添加一个pre空节点等),其中有两个比较特殊的指针分别是slow指针和fast指针,也叫快慢指针。由于在很久以前初识这个套路...
  • 时间复杂度O(N) 额外空间复杂度O(1)的解 N:链表长度(问题的规模) 通过快慢指针找到中点节点 遍历N 反转中点右边节点的指向 遍历0.5N 判断是否回文 遍历0.5N 恢复中点右边的节点的指向 0.5N 总的需要遍历链表2.5N次...
  • 链表快慢指针       快慢指针中的快慢指的是指针沿链表移动的步长,即每次向前移动速度的快慢。快指针每次沿链表向前移动...用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题。 示例 1:输入: 1->2 ;输出: false...
  • 刚开始只想到了哈希表 看了题解才想到快慢指针 快指针每次走2 慢指针每次走1 如果存在环 则一定会相遇 至于快指针为什么是走2 而不是3,4,5…因为正常遍历是O(n) 快指针的遍历是O(kn) k得2时复杂度最低 public ...
  • 快慢指针的应用

    2019-02-04 12:18:48
    https://blog.csdn.net/qq_21815981/article/details/79833976 快慢指针&amp;amp;...快慢指针中的快慢指的是移动的步长,即每次向前移动速度的快慢。...快慢指针的应用...
  • 快慢指针的应用总结

    2020-03-24 21:38:33
    快慢指针 快慢指针中的快慢指的是移动的步长,即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2,慢指针每次向前移动1次。 快慢指针的应用 (1)判断单链表是否存在环 如果链表存在环,就好像操场...
  • 用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题 示例 示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: true 思路 首先使用快慢指针找到链表中点,然后翻转后半部分链表,再与前半部分...
  • 环形链表(快慢指针判断是否有环,不需要找环的起点)思路1:map存放链表节点 (空间复杂度O(N))思路2:双指针法(空间复杂度为O(1))142. 环形链表 II (寻找找出环的入口节点)思路1:快慢指针(找环)+同步指针...
  • 环形链表(快慢指针

    千次阅读 2019-09-06 17:19:23
    文章目录环形链表(快慢指针)题目思路代码leetcode展示 环形链表(快慢指针) 题目 在leetcode上有两道关于环形链表的题,...我的第一反应是哈希表,这样的时间复杂度可以控制在O(n),但是空间复杂度也是O(n)。 ...
  • C++快慢指针的应用

    2019-09-10 10:40:52
    快慢指针 快慢指针中的快慢指的是移动的步长,即每次向前移动的快慢,例如每次可以让快指针沿链表向前移动2,慢指针向前移动1次。 快慢指针的应用 (1)判断单链表是否存在环   如果链表是一个环,就好像...
  • 文章目录引言一、对撞指针二、快慢指针三、LeetCode—167其他用到对撞指针的问题四、LeetCode—142 引言   双指针算法在数组问题中极为常用。双指针主要用于遍历数组,两个指针指向不同的元素,从而协同完成任务。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,964
精华内容 2,785
关键字:

快慢指针时间复杂度