缓存、链表形式的缓存、数组形式的缓存、回文的判定

什么是缓存？

缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非广泛的应用，比如常见的CPU缓存、数据库缓存、浏览器缓存等等。

为什么使用缓存？即缓存的特点

缓存的大小是有限的，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？就需要用到缓存淘汰策略。

什么是缓存淘汰策略？

指的是当缓存被用满时清理数据的优先顺序。

有哪些缓存淘汰策略？

常见的3种包括先进先出策略FIFO（First In，First Out）、最少使用策略LFU（Least Frenquently Used）、最近最少使用策略LRU（Least Recently Used）。

链表实现LRU缓存淘汰策略

当访问的数据没有存储在缓存的链表中时，直接将数据插入链表表头，时间复杂度为O(1)；当访问的数据存在于存储的链表中时，将该数据对应的节点，插入到链表表头,时间复杂度为O(n)。如果缓存被占满，则从链表尾部的数据开始清理，时间复杂度为O(1)。

数组实现LRU缓存淘汰策略

方式一：首位置保存最新访问数据，末尾位置优先清理

当访问的数据未存在于缓存的数组中时，直接将数据插入数组第一个元素位置，此时数组所有元素需要向后移动1个位置，时间复杂度为O(n)；当访问的数据存在于缓存的数组中时，查找到数据并将其插入数组的第一个位置，此时亦需移动数组元素，时间复杂度为O(n)。缓存用满时，则清理掉末尾的数据，时间复杂度为O(1)。

方式二：首位置优先清理，末尾位置保存最新访问数据

当访问的数据未存在于缓存的数组中时，直接将数据添加进数组作为当前最有一个元素时间复杂度为O(1)；当访问的数据存在于缓存的数组中时，查找到数据并将其插入当前数组最后一个元素的位置，此时亦需移动数组元素，时间复杂度为O(n)。缓存用满时，则清理掉数组首位置的元素，且剩余数组元素需整体前移一位，时间复杂度为O(n)。（优化：清理的时候可以考虑一次性清理一定数量，从而降低清理次数，提高性能。）

如何通过单链表实现“判断某个字符串是否为水仙花字符串”？

（比如上海自来水来自海上, ABCBA）

核心思想是用两个快慢指针，快指针是慢指针移动速度的两倍，当快指针到末尾的时候，慢指正正好到中点位置；
创建一个指针A，每次移动的时候，都把慢指针访问过的节点翻转。
遍历创建节点和慢节点，看其访问的value是否一致。（此时创建的指针A从中间访问到链表头，而慢节点是从中间访问到链表尾部）

附录：判断一个链表是否是回文的代码

`
/**

Implement a function to check if a linked list is a palindrome don’t forget import statements!
判断一个链表是否是一个回文（回文指的是正着读，倒着读都是一样的文字）
*/
public class IsPalindrome {

/**
- 这个方法是把所有的数据取出来放入到一个栈中。然后在遍历栈看是否与之前遍历的数据一致。
- 时间 O（n）
- 空间 O（n）
  */
  public static boolean isPalindrome(LinkedListNode head) {
  Stack stack = new Stack();
  StringBuilder sb = new StringBuilder();
  while (head != null) {
```
stack.add(head.getValue());
head = head.getPost();
sb.append(head.getValue());
```
  }
  
  StringBuilder sb2 = new StringBuilder();
  while (!stack.empty()) {
```
sb2.append(stack.pop());
```
  }
  
  return sb.toString().equals(sb2.toString());
  }
  
  /**
- 递归版本
- 时间 O(n)
- 空间 O(1)
  */
  LinkedListNode left;
  
  public boolean isPalindrome2(LinkedListNode head) {
  left = head;
  boolean result = helper(head);
  return result;
  
  }
  
  public boolean helper(LinkedListNode right) {
  if (right == null) {
```
return true;
```
  }
  
  boolean x = helper(right.getPost());
  if (!x) {
```
return false;
```
  }
  
  boolean y = (left.getValue() == right.getValue());
  
  left = left.getPost();
  return y;
  
  }
  
  /**
- 使用快慢两个指针找到链表中点，慢指针每次前进一步，快指针每次前进两步。
- 在慢指针前进的过程中，同时修改其 next 指针，使得链表前半部分反序。最后比较中点两侧的链表是否相等。
- 时间 O(n)
- 空间 O(1)
  *
- @return true or false
  */
  public boolean isPalindrome3(LinkedListNode head) {
  if (head == null || head.getPost() == null) {
```
return true;
```
  }
  
  LinkedListNode pre = null;
  LinkedListNode fast = head;
  LinkedListNode slow = head;
  
  while (fast != null && fast.getPost() != null) {
```
fast = fast.getPost().getPost();
LinkedListNode next = slow.getPost();
slow.setPost(pre);
pre = slow;
slow = next;
```
  }
  if (fast != null) {
```
slow = slow.getPost();
```
  }
  
  while (slow != null) {
```
if (slow.getValue() != pre.getValue()) {
    return false;
}

slow = slow.getPost();
pre = pre.getPost();
```
  }
  return true;
  }

`/**

Implement a function to check if a linked list is a palindrome don’t forget import statements!
判断一个链表是否是一个回文（回文指的是正着读，倒着读都是一样的文字）
*/
public class IsPalindrome {

/**
- 这个方法是把所有的数据取出来放入到一个栈中。然后在遍历栈看是否与之前遍历的数据一致。
- 时间 O（n）
- 空间 O（n）
  */
  public static boolean isPalindrome(LinkedListNode head) {
  Stack stack = new Stack();
  StringBuilder sb = new StringBuilder();
  while (head != null) {
```
stack.add(head.getValue());
head = head.getPost();
sb.append(head.getValue());
```
  }
  
  StringBuilder sb2 = new StringBuilder();
  while (!stack.empty()) {
```
sb2.append(stack.pop());
```
  }
  
  return sb.toString().equals(sb2.toString());
  }
  
  /**
- 递归版本
- 时间 O(n)
- 空间 O(1)
  */
  LinkedListNode left;
  
  public boolean isPalindrome2(LinkedListNode head) {
  left = head;
  boolean result = helper(head);
  return result;
  
  }
  
  public boolean helper(LinkedListNode right) {
  if (right == null) {
```
return true;
```
  }
  
  boolean x = helper(right.getPost());
  if (!x) {
```
return false;
```
  }
  
  boolean y = (left.getValue() == right.getValue());
  
  left = left.getPost();
  return y;
  
  }
  
  /**
- 使用快慢两个指针找到链表中点，慢指针每次前进一步，快指针每次前进两步。
- 在慢指针前进的过程中，同时修改其 next 指针，使得链表前半部分反序。最后比较中点两侧的链表是否相等。
- 时间 O(n)
- 空间 O(1)
  *
- @return true or false
  */
  public boolean isPalindrome3(LinkedListNode head) {
  if (head == null || head.getPost() == null) {
```
return true;
```
  }
  
  LinkedListNode pre = null;
  LinkedListNode fast = head;
  LinkedListNode slow = head;
  
  while (fast != null && fast.getPost() != null) {
```
fast = fast.getPost().getPost();
LinkedListNode next = slow.getPost();
slow.setPost(pre);
pre = slow;
slow = next;
```
  }
  if (fast != null) {
```
slow = slow.getPost();
```
  }
  
  while (slow != null) {
```
if (slow.getValue() != pre.getValue()) {
    return false;
}

slow = slow.getPost();
pre = pre.getPost();
```
  }
  return true;
  }