存档

‘LeetCode’ 分类的存档

LeetCode面试题之删除单链表节点

2016年7月16日 583 人阅读 没有评论

1.限制于要求

只给要删除的数据节点的指针,指针不会指向链表尾。

2.思考

正常删除一个链表中的节点我们先要获取要删除节点的前驱节点的指针pre,然后执行pre->next = pre->next->next来把要删除的节点从链表中剔除。其实这里我们可以转换一下思维方式不一定要通过删除节点的方式来删除数据,我们可以通过复制要删除节点的下一个节点的数据到当前要删除的节点中,然后再把要删除节点的下一个节点给删除,就能达到删除指定节点上数据的要求。

3.算法图解

分类: c/c++, LeetCode, 面试 标签:

LeetCode面试题之回文单链表

2016年7月15日 452 人阅读 没有评论

1.限制与要求

  • 时间复杂度O(n),空间复杂度O(1)

2.思考

回文最初的概念是应用在字符串上的,比如”abccba”和“abcdcba”都是回文字符串。判断是否是回文字符串的算法也很简单,使用两个下标i、j,i从头开始向后遍历,j从尾开始向前遍历,只要i < j就一直遍历,在遍历过程中如果i和j位置上的字符不相同,则该字符串必然不是回文的并立即停止遍历,如果遍历结束后都没遇到不相同的字符,则该字符串是回文的。

  • 单链表回文难点
    • 我们无法像遍历连续空间那样,直接从尾部向前遍历。
    • 即使解决了逆向遍历的问题,那么如何判断结束遍历也同样是个问题。
  • 一个巧妙的解法
    • 第一个问题:我们把单链表逆序然后再遍历就可以实现从尾部(逆序前的单链表)向前遍历了。
    • 第二个问题:把链表先拆分成left和right两部分,然后只对right部分进行逆序。
    • 最后我们从left头节点和逆序后的right头节点开始遍历,一直往后遍历直到链表尾。
    • 遍历过程中出现不相同的数据则不是回文的单链表,否则就是回文的单链表。

3.算法图解

分类: c/c++, LeetCode, 面试 标签:

LeetCode面试题之删除单链表中倒数第n个节点

2016年7月15日 447 人阅读 没有评论

1. 限制于要求

  • 空间复杂度O(1),时间复杂度度O(n)

2.思考

可以使用两个指针来实现,一个cur指针先从链表头往后遍历n个节点,然后一个pre指针(初始为NULL)和cur指针一起在链表中往后遍历直到cur指向NULL,而此时pre指向的就是要被删除的倒数第n个节点的前驱,如果pre为空,则说明要删除的是链表头节点,否则更新一下pre的next指针即可,即pre->next = pre->next->next。

2.1删除链表尾节点

分类: c/c++, LeetCode, 面试 标签:

LeetCode面试题之单链表是否有环

2016年7月13日 403 人阅读 没有评论

1.限制与要求

  • 不允许修改链表结构。
  • 时间复杂度O(n),空间复杂度O(1)。

2.思考

2.1判断是否有环

如果链表有环,那么在遍历链表时则会陷入死循环,利用这个特征,我们可以设计这样的算法。

  • 使用一个slow指针,一个fast指针。
  • slow指针一次往后遍历以1个节点,fast指针一次往后遍历2个节点,一直做这样的操作。

    阅读全文…
分类: c/c++, LeetCode, 面试 标签:

LeetCode面试题之两个单链表相交

2016年7月13日 447 人阅读 没有评论

1.限制和要求

  • 如果两个链表没有交叉返回NULL,有相交返回相交的点。
  • 两个链表的原始结构不能被修改。
  • 两个链表中都没有环。
  • 算法的时间复杂度要求是O(n),空间复杂度是O(1)。

2.思考

  • 算法1
    • 分别遍历两个链表,记录遍历的节点。
    • 出现重复的节点,就说明两条链表相交。
    • 第一个重复出现的节点就是交点。
  • 算法2
    算法1不能满足空间复杂为O(1)的要求,因为你需要记录遍历过的节点,认真分析后发现如果两个链表有相交那么它们的尾节点必定是相同的。

    • 分别遍历两个链表,记录遍历的尾节点和链表长度,如果两个链表的尾节点相同则说明链表相交。
    • 在两边相交的情况下,如果两个链表的长度不一致,则较长的链表先从链表头遍历n步,n为两个链表的长度差。
    • 长度短的链表从链表头往后遍历,长度长的链表继续往后遍历,直到遍历到相同的节点,而这个节点就是这两个链表的交点。

3.算法图解

分类: c/c++, LeetCode, 面试 标签:

LeetCode面试题之单链表逆序

2016年7月12日 662 人阅读 没有评论

1.算法概述

遍历链表,并在遍历的过程中修改当前节点cur的next指针,使当前节点cur的next指针指向当前节点的前驱节点pre,遍历完之后pre指针就是逆序后链表的头指针。

2.图解

分类: c/c++, LeetCode, 算法, 面试 标签:

LeetCode面试题之LRU

2016年7月2日 337 人阅读 没有评论

1.问题

在刷LeetCode时遇到了一道这样的题目

1.1LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

  class LRUCache{
  public:
      LRUCache(int capacity) {
          
      }
      
      int get(int key) {
          
      }
      
      void set(int key, int value) {
          
      }
  };
  

阅读全文…

分类: c/c++, LeetCode, 算法, 通用概念, 面试 标签: