C/C++

《数据结构与算法之美》06～10笔记

2019-09-23  本文已影响0人  太阳骑士索拉尔

关于我的仓库

前言

06讲链表(上):如何实现LRU缓存淘汰算法

实现LRU缓存淘汰算法

课后题：如何判断一个字符串是否是回文字符串的问题，我想你应该听过，我们今天的思题目就是基于这个问题的改造版本。如果字符串是通过单链表来存储的，那该如何来判断是一个回文串呢?你有什么好的解决思路呢?相应的时间空间复杂度又是多少呢?【LeetCode 234 回文链表】

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (head == NULL || head->next == NULL) {
      return true;
    }

    ListNode *prev = NULL;
    ListNode *slow = head;
    ListNode *fast = head;

    while (fast != NULL && fast->next != NULL) {
      //pre：前一个
      //slow：慢指针&&后一段链表的开头
      //fast：快指针，边界工具人
      //操作就是要把慢指针经过的逆置过来，所以让pre作为前一个，slow作为当前工具人，使用next去记录下一个，就是slow的下一位
      //变换时，先把前面的逆过来，slow再往下走
      fast = fast->next->next;
      ListNode *next = slow->next;
      slow->next = prev;
      prev = slow;
      slow = next;
    }

    if (fast != NULL) {
      //！=NULL的这个情况就是奇数的情况，此时，slow工具人站在中间，pre就位，因此要让slow往前一个
      slow = slow->next;
    }

    while (slow != NULL) {
      if (slow->val != prev->val) {
        return false;
      }
      slow = slow->next;
      prev = prev->next;
    }

    return true;
    }
};

07讲链表(下):如何轻松写出正确的链表代码

链表六技

技巧一：理解指针或引用的含义

技巧二：警惕指针丢失和内存泄漏

技巧三：利用哨兵简化实现难度

// 正常人写的代码
// 在数组a中，查找key，返回key所在的位置 // 其中，n表示数组a的⻓度
int find(char* a, int n, char key) {
// 边界条件处理，如果a为空，或者n<=0，说明数组中没有数据，就不用while循环比较了 
  if(a == null || n <= 0) {
        return -1;
  }
    int i = 0;
// 这里有两个比较操作:i<n和a[i]==key. 
  while (i < n) {
    if (a[i] == key) {
        return i;
        }
        ++i;
    }
    return -1;
}

// 憨憨哨兵代码
// 在数组a中，查找key，返回key所在的位置
// 其中，n表示数组a的⻓度
// 我举2个例子，你可以拿例子走一下代码 //a={4,2,3,5,9,6} n=6key=7 //a={4,2,3,5,9,6} n=6key=6 
int find(char* a, int n, char key) {
    if(a == null || n <= 0) { 
    return -1;
    }
// 这里因为要将a[n-1]的值替换成key，所以要特殊处理这个值 
  if (a[n-1] == key) {
        return n-1;
  }
// 把a[n-1]的值临时保存在变量tmp中，以便之后恢复。tmp=6。 
// 之所以这样做的目的是:希望find()代码不要改变a数组中的内容 char tmp = a[n-1];
// 把key的值放到a[n-1]中，此时a = {4, 2, 3, 5, 9, 7} 
  a[n-1] = key;
    int i = 0;
// while 循环比起代码一，少了i<n这个比较操作 
  while (a[i] != key) {
        ++i;
  }
// 恢复a[n-1]原来的值,此时a= {4, 2, 3, 5, 9, 6} 
  a[n-1] = tmp;
    if (i == n-1) {
// 如果i == n-1说明，在0...n-2之间都没有key，所以返回-1 
    return -1;
    } else {
// 否则，返回i，就是等于key值的元素的下标 
    return i;
    } 
}

技巧四：重点留意边界条件处理

技巧五：举例画图，辅助思考

page7image39834288.jpg

技巧六：多写多练，没有捷径

单链表反转【LeetCode 206 反转链表】

参考文章
题解
我的题解
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        
        ListNode *pre = NULL;
        ListNode *next = NULL;
        ListNode *pNode = head;
        
        while (pNode != NULL) {
            next = pNode->next;
            pNode->next = pre;
            pre = pNode;
            pNode = next;
        }
        
        return pre;
    }
};
参考题解
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        
       if (head == NULL || head->next == NULL) return head;
        ListNode *p = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return p;
    }
};
反思

链表中环的检测【LeetCode 141 环形链表】

参考文章
题解
我的题解
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == NULL || head->next == NULL) {
            return false;
        }
        ListNode *slow = head;
        ListNode *fast = head;
        while (fast->next != NULL && fast->next->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow->val == fast->val) {
                return true;
            }
        }
        return false;
    }
};
参考题解
public boolean hasCycle(ListNode head) {
    Set<ListNode> nodesSeen = new HashSet<>();
    while (head != null) {
        if (nodesSeen.contains(head)) {
            return true;
        } else {
            nodesSeen.add(head);
        }
        head = head.next;
    }
    return false;
}
反思

两个有序的链表合并【LeetCode 21 合并两个有序链表】

参考文章
题解
我的题解
//这谁会呢
参考题解
//递归
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == NULL) {
            //这一步不仅是一开始的判空，更是后面当一个链表已经遍历到结束了
            //就一直使用另一个里面的节点
            return l2;
        } 
        else if (l2 == NULL) {
            return l1;
        }
        else if (l1->val < l2->val) {
            //由于从小到大，因此
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
        else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

//迭代
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        //这等于就是添加哨兵的思想，使得不用考虑开头的数字，妙啊
        ListNode *prehead = new ListNode(-1);

      
        ListNode *prev = prehead;
        while (l1 != NULL && l2 != NULL) {
            if (l1->val <= l2->val) {
                //把l1连上
                prev->next = l1;
                //接下来要做的仅仅是把l1指针指向下一个
                l1 = l1->next;
            } else {
                prev->next = l2;
                l2 = l2->next;
            }
            prev = prev->next;
        }
        prev->next = l1 == NULL ? l2 :l1;

        return prehead->next;
    }
};
反思

删除链表倒数第n个结点【LeetCode 19 删除链表的倒数第N个节点】

参考文章
题解
我的题解
//这谁会呢
参考题解
//两次遍历算法
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        int length  = 0;
        ListNode *first = head;
        while (first != NULL) {
            length++;
            first = first->next;
        }
        length -= n;
        first = dummy;
        while (length > 0) {
            length--;
            first = first->next;
        }
        first->next = first->next->next;
        return dummy->next;
    }
};

//一次遍历法
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        ListNode *first = dummy;
        ListNode *second = dummy;
        for (int i = 1; i <= n + 1; i++) {
            first = first->next;
        }
        while (first != NULL) {
            first = first->next;
            second = second->next;
        }
        second->next = second->next->next;
        return dummy->next;
    }
};
反思

求链表的中间结点【LeetCode 876 链表的中间结点】

参考文章
题解
我的题解
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode *slowNode = head;
        ListNode *fastNode = head;
        while (fastNode->next != NULL && fastNode->next->next != NULL) {
            fastNode = fastNode->next->next;
            slowNode = slowNode->next;
        }
        if (fastNode->next != NULL) {
            slowNode = slowNode->next;
        }
        return slowNode;
    }
};
参考题解
//这要啥参考题解呢
反思

课后题：今天我们讲到用哨兵来简化编码实现，你是否还能够想到其他场景，利用哨兵可以大大地简化编码难度?

08讲栈：如何实现浏览器的前进和后退功能

顺序栈的基本实现

EF09A73A-1691-4D2F-9818-FEBADC0B04A9

支持动态扩容的顺序栈

page4image7848160.png page5image7775648.png

典型使用

栈在函数调用中的应用【函数调用栈】

//
//  main.cpp
//  stack-Test
//
//  Created by Kevin.J on 2019/9/11.
//  Copyright © 2019 姜凯文. All rights reserved.
//

#include <iostream>

int add(int x, int y) {
    int sum = 0;
    sum = x + y;
    return sum;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    std::cout << "Hello, World!\n";
    
    int a = 1;
    int ret = 0;
    int res = 0;
    ret = add(3, 5);
    res = a + ret;
    printf("%d", res);
    return 0;
}

//输入 thread backtrace
* thread #1, queue = 'com.apple.main-thread', stop reason = breakpoint 2.1
  * frame #0: 0x00000001000011d1 stack-Test`add(x=3, y=5) at main.cpp:13:11
    frame #1: 0x0000000100001234 stack-Test`main(argc=1, argv=0x00007ffeefbff5f0) at main.cpp:24:11
    frame #2: 0x00007fff6bf9f3d5 libdyld.dylib`start + 1
//当前顶上的就是add
page6image7649056.png

栈在表达式求值中的应用

page7image8074704.png 0301B223-3494-44BE-B268-394991C9125E

栈在括号匹配中的应用

通过栈实现浏览器的前进和后退

page8image7821888.png page8image7823680.png page9image7397920.png

课后题

我们在讲栈的应用时，讲到用函数调用栈来保存临时变量，为什么函数调用要用“栈”来保存临时变量呢?用其他数据结构 不行吗?

我们都知道，JVM内存管理中有个“堆栈”的概念。栈内存用来存储局部变量和方法调用，堆内存用来存储Java中的对象。 那JVM里面的“栈”跟我们这里说的“栈”是不是一回事呢?如果不是，那它为什么又叫作“栈”呢?

作业

09讲队列：队列在线程池等有限资源池中的应用

如何理解“队列”？

img

顺序队列和链式队列

顺序队列

// 顺序队列的实现
// 用数组实现的队列
public class ArrayQueue {
  // 数组：items，数组大小：n
  private String[] items;
  private int n = 0;
  // head表示队头下标，tail表示队尾下标
  private int head = 0;
  private int tail = 0;

  // 申请一个大小为capacity的数组
  public ArrayQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }

  // 入队
  public boolean enqueue(String item) {
    // 如果tail == n 表示队列已经满了
    if (tail == n) return false;
    items[tail] = item;
    ++tail;
    return true;
  }

  // 出队
  public String dequeue() {
    // 如果head == tail 表示队列为空
    if (head == tail) return null;
    // 为了让其他语言的同学看的更加明确，把--操作放到单独一行来写了
    String ret = items[head];
    ++head;
    return ret;
  }
}
img img 
 // 入队操作，将item放入队尾
  public boolean enqueue(String item) {
    // tail == n表示队列末尾没有空间了
    if (tail == n) {
      // tail ==n && head==0，表示整个队列都占满了
      if (head == 0) return false;
      // 数据搬移
      for (int i = head; i < tail; ++i) {
        items[i-head] = items[i];
      }
      // 搬移完之后重新更新head和tail
      tail -= head;
      head = 0;
    }
    
    items[tail] = item;
    ++tail;
    return true;
  }
img

链式队列

img

循环队列

img img img 
public class CircularQueue {
  // 数组：items，数组大小：n
  private String[] items;
  private int n = 0;
  // head表示队头下标，tail表示队尾下标
  private int head = 0;
  private int tail = 0;

  // 申请一个大小为capacity的数组
  public CircularQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }

  // 入队
  public boolean enqueue(String item) {
    // 队列满了
    if ((tail + 1) % n == head) return false;
    items[tail] = item;
    tail = (tail + 1) % n;
    return true;
  }

  // 出队
  public String dequeue() {
    // 如果head == tail 表示队列为空
    if (head == tail) return null;
    String ret = items[head];
    head = (head + 1) % n;
    return ret;
  }
}

阻塞队列和并发队列

img img

线程池没有空闲线程时，新的任务请求线程资源时，线程池该如何处理？各种处理策略又是如何实现的呢？

课后题

除了线程池这种池结构会用到队列排队请求，你还知道有哪些类似的池结构或者场景中会用到队列的排队请求呢?

今天讲到并发队列，关于如何实现无锁并发队列，网上有非常多的讨论。对这个问题，你怎么看呢?

作业：循环队列【LeetCode 622. 设计循环队列】

class MyCircularQueue {
public:
    /** Initialize your data structure here. Set the size of the queue to be k. */
    MyCircularQueue(int k) {
        size = k;
        head = 0;
        tail = 0;
        data.resize(k);
    }
    
    /** Insert an element into the circular queue. Return true if the operation is successful. */
    bool enQueue(int value) {
        if ((tail + 1) % size == head) {
            return false;
        }
        data[tail] = value;
        tail = (tail + 1) % size;
        return true;
    }
    
    /** Delete an element from the circular queue. Return true if the operation is successful. */
    bool deQueue() {
        if (head == tail) {
            return false;    
        }
        head = (head + 1) % size;
        return true;
    }
    
    /** Get the front item from the queue. */
    int Front() {
        if (head == tail) {
            return -1;    
        }
        return data[head];
    }
    
    /** Get the last item from the queue. */
    int Rear() {
        if (head == tail) {
            return -1;    
        }
        return data[(tail - 1 + size) % size];
    }
    
    /** Checks whether the circular queue is empty or not. */
    bool isEmpty() {
        if (head == tail) {
            return true;    
        }
        return false;
    }
    
    /** Checks whether the circular queue is full or not. */
    bool isFull() {
        if ((tail + 1) % size == head) {
            return true;
        }
        return false;
    }
    
private:
    vector<int> data;
    int size, head, tail;
};

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue* obj = new MyCircularQueue(k);
 * bool param_1 = obj->enQueue(value);
 * bool param_2 = obj->deQueue();
 * int param_3 = obj->Front();
 * int param_4 = obj->Rear();
 * bool param_5 = obj->isEmpty();
 * bool param_6 = obj->isFull();
 */

10讲递归：如何用三行代码找到“最终推荐人”

如何理解“递归”？

递归需要满足的三个条件

Leetcode 687. 最长同值路径

给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。

注意：两个节点之间的路径长度由它们之间的边数表示。

示例 1:

输入:

          5
         / \
        4   5
       / \   \
      1   1   5

输出:

2
示例 2:

输入:

          1
         / \
        4   5
       / \   \
      4   4   5

输出:

2
注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。

分析：

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int ans;
    int longestUnivaluePath(TreeNode* root) {
        ans = 0;
        arrowLength(root);
        return ans;
    }
    int arrowLength(TreeNode* node) {
        if (node == NULL) {
            return 0;
        }
        int left = arrowLength(node->left);
        int right = arrowLength(node->right);
        int arrowLeft = 0, arrowRight = 0;
        if (node->left != NULL && node->left->val == node->val) {
            arrowLeft += left + 1;
        }
        if (node->right != NULL && node->right->val == node->val) {
            arrowRight += right + 1;
        }
        ans = max(ans, arrowLeft + arrowRight);
        return max(arrowLeft, arrowRight);
    }
};

递归心法

警惕栈溢出

递归代码警惕重复计算

img

迭代法与递归相互转化

开篇解答：如何找到“最终推荐人”？

img 
long findRootReferrerId(long actorId) {
  Long referrerId = select referrer_id from [table] where actor_id = actorId;
  if (referrerId == null) return actorId;
  return findRootReferrerId(referrerId);
}

课后题：我们平时调试代码喜欢使用IDE的单步跟踪功能，像规模比较大、递归层次很深的递归代码，几乎无法使用这种调试方式。对于递归代码，你有什么好的调试方法呢？

上一篇 下一篇

猜你喜欢

热点阅读