实现一个 LRU 缓存淘汰算法:

import java.util.HashMap;
import java.util.Iterator;

public class LRU<K,V> {
    
    private Node head;
    private Node tail;
    private HashMap<K, Node> map;
    private int maxSize;

    private class Node {
        Node pre;
        Node next;
        K k;
        V v;
        public Node(K k, V v) {
            this.k = k;
            this.v = v;
        }
    }

    public LRU(int maxSize) {
        this.maxSize = maxSize;
        this.map = new HashMap<>(maxSize * 4 / 3);
        head = new Node(null, null);
        tail = new Node(null, null);
        head.next = tail;
        tail.pre = head;
    }

    public V get(K key) {
        if (!map.containsKey(key)) {
            return null;
        }
        Node node = map.get(key);
        unlink(node);
        appendToHead(node);
        return node.v;
    }
    public void put(K key, V value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            unlink(node);
        }
        Node node = new Node(key, value);
        appendToHead(node);
        map.put(key, node);
        if (map.size() > maxSize) {
            Node toRemove = removeTail();
            map.remove(toRemove.k);
        }
    }
    private Node removeTail() {
        Node node = tail.pre;
        Node pre = node.pre;
        tail.pre = pre;
        pre.next = tail;
        node.next = null;
        node.pre = null;
        return node;
    }
    private void appendToHead(Node node) {
        Node next = head.next;
        node.next = next;
        node.pre = head;
    next.pre = node;
        head.next = node;
    }
    private void unlink(Node node) {
        Node pre = node.pre;
        Node next = node.next;
        pre.next = next;
        next.pre = pre;
        node.pre = null;
        node.next = null;
    }
    
}

#朴素字符串匹配算法
def nmatching(t, p):
# t代表主串，p代表模式串
    i = 0
    j = 0
    n = len(t)
    m = len(p)
    while i < n and j < m:
        if t[i] == p[j]:
            i = i+1
            j = j+1
        else:
            i = i-j+1
            j = 0 #i-j+1是关键，遇字符不等时将模式串t右移一个字符
    if j == m:
        return i-j #找到一个匹配，返回索引值
    return -1 #未找到，返回-1

王争老师，新年的第四天快乐，已经很晚了，祝您好梦！
关于基于链表法解决冲突的散列表，就是使用一个数组，将值散列到数组下标上，但数组的每个值又是一个链表的头结点，当遇到冲突时就遍历该头结点后链表。其实java中hashmap底层的实现原理就是一个基于链表解决冲突的动态扩容的数组。大家有兴趣可以自己实现一下hashmap的底层数据结构，还是很有收获的。
今天leetcode上的三题都是关于字符串的，下面是我的解题思路和代码
1. Reverse String （反转字符串）
解题思路：这一题要求使用O(1)的空间将字符串进行反转，就是原地反转字符串，对字符串s[0…n-1]来说当i<n/2;将i与n-1-i位置的字符进行互换就行.
代码： https://github.com/yyxd/leetcode/blob/master/src/leetcode/strings/Problem344_ReverseString.java
2. Reverse Words in a String （翻转字符串里的单词）
解题思路：这一题我用的是java中的StringBuilder处理字符串，先用split函数将字符串按空格分开，但是当有多个连续空格时，一定要注意这种不能当做单词处理，要检查一下。
代码： https://github.com/yyxd/leetcode/blob/master/src/leetcode/strings/Problem151_ReverseWordsInString.java
3. String to Integer (atoi) 字符串转换整数 (atoi)）
解题思路：将字符串转化为整数,首先是对数字前面的+/-进行处理，遍历字符串，如果不是数字字符就break，自己不懂得地方在于如何将大于INT.MAX 的值转化为 INT.MAX,将INT.MIN的值化为 INT.MIN，我自己想到的解法是用更高精度的long去保存，然后转化成int类型的值
代码： https://github.com/yyxd/leetcode/blob/master/src/leetcode/strings/Problem8_atoi.java

#字符串转整数
class Solution:
    def myAtoi(self, str: str) :
        pattern = r"[\s]*[+-]?[\d]+"
        match = re.match(pattern, str)
        if match:
            res = int(match.group(0))
            if res > 2 ** 31 - 1:
                res = 2 ** 31 -1
            if res < - 2 ** 31:
                res = - 2 ** 31
        else:
            res = 0
        return res

#反转字符串
class Solution:
    def reverseString(self, s):
        low = 0
        high = len(s)-1
        while low <= high:
            s[low] , s[high] = s[high] , s[low]
            low+=1
            high-=1
        return s

字符串转换整数python实现：
import math

class Solution:
    def myAtoi(self, str: 'str') -> 'int':
        result = 0

        i, N, former = 0, len(str), 1

        while i < N:
            if str[i] != ' ':
                break
            i += 1
            
        if i < N and (str[i] == '-' or str[i] == '+'):
            former = -1 if str[i] == '-' else 1
            i += 1
            
        while i < N:
            if str[i].isdigit():
                result = result * 10 + int(str[i])
                i += 1
            else:
                break

        result = result * former
        if result > (math.pow(2, 31) * -1) and result < (math.pow(2,31) - 1):
            return result
        elif former > 0 :
            return int(math.pow(2,31) - 1)
        else:
            return int(math.pow(2,31) * -1)

1.从两端向中间两两对调，时间复杂度O（n）。

2.先去空格，O（n^2）。从两端向中间查找单词，找到一对单词s、t（s在前t在后），保存这两个单词，如果s长t短，把它们之间的字符串整体左移长度差个字符，反之整体右移长度差个字符，再把s和t按调整后位置向原数组赋值，O（n^2）。

3.如果字符串全为空、全为空格、首个非空格字符非法，则返回0。若首个合法字符位“-”则记录。int num=0；逐个读取数字部分字符a，若a合法，则num*=10，然后num+=a-‘0’，直到读取结束或者读到非法字符，此时如果记录的首个合法字符为“-”返回num*（-1），否则返回num。不知int型运算过程中结果值溢出，是否自动将值设置为边界值。如果不能就要在每次乘10的时候结合“-”考察一下是否越界。

反转字符串python实现：
class Solution:
    def reverseString(self, s: 'List[str]') -> 'None':
        """
        Do not return anything, modify s in-place instead.
        """
        i, N = 0, len(s)
        while i < N//2:
            s[i], s[N-1-i] = s[N-1-i], s[i]
            i += 1
            
        print(s)

反转字符串
class Solution {
public:
    string reverseString(string s) {
        int length = s.length();
        if (length < 2) {
            return s;
        }
        int i = 0, j = length - 1;
        char temp;
        while (i < j) {
            temp = s[i];
            s[i] = s[j];
            s[j] = temp;
            i++;
            j--;
        }
        return s;
    }
};

itoa

public class Solution {
    public int myAtoi(String str) {
        if (str.isEmpty())
            return 0;
        str = str.trim();
        int i = 0, ans = 0, sign = 1, len = str.length();
        if (str.charAt(i) == '-' || str.charAt(i) == '+')
            sign = str.charAt(i++) == '+' ? 1 : -1;
        for (; i < len; ++i) {
            int tmp = str.charAt(i) - '0';
            if (tmp < 0 || tmp > 9)
                break;
            if (ans > Integer.MAX_VALUE / 10
                    || (ans == Integer.MAX_VALUE / 10 && Integer.MAX_VALUE % 10 < tmp))
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            else
                ans = ans * 10 + tmp;
        }
        return sign * ans;
    }
}

反转字符串 go 语言实现
package main

import "fmt"

func reverseString(s []byte) {
    length := len(s)
    for i := 0; i < length/2; i++ {
        s[i], s[length-i-1] = s[length-i-1], s[i]
    }
}

func main() {
    testString := []byte{'h', 'e', 'l', 'l', 'o'}
    fmt.Println(string(testString[:]))
    reverseString(testString)
    fmt.Println(string(testString[:]))
}

LRU缓存淘汰算法
    private class Node{
        private Node prev;
        private Node next;
        private int key;
        private int value;

        Node(int key,int value){
            this.key = key;
            this.value = value;
        }
    }

    private Node head;// 最近最少使用，类似列队的头，出队
    private Node tail;// 最近最多使用，类似队列的尾，入队
    private Map<Integer,Node> cache;
    private int capacity;

    public LRUCache(int capacity) {
        this.cache = new HashMap<>();
        this.capacity = capacity;
    }

    public int get(int key) {
        Node node = cache.get(key);
        if(node == null){
            return -1;
        }else{
            moveNode(node);
            return node.value;
        }
    }

    public void put(int key, int value) {
        Node node = cache.get(key);
        if (node != null){
            node.value = value;
            moveNode(node);
        }else {
            removeHead();
            addNode(new Node(key,value));
        }
        cache.put(key,node);
    }

    private void removeHead(){
        if (cache.size() == capacity){
            Node tempNode = head;
            cache.remove(head.key);
            head = head.next;
            tempNode.next = null;
            if (head != null)
                head.prev = null;
        }
    }

    private void addNode(Node node){
        if (head == null)
            head = tail = node;
        else
            addNodeToTail(node);
    }

    private void addNodeToTail(Node node){
        node.prev = tail;
        tail.next = node;
        tail = node;
    }

    private void moveNode(Node node){
        if(head == node && node != tail){
            head = node.next;
            head.prev = null;
            node.next = null;
            addNodeToTail(node);
        }else if (tail == node){
        }else {
            node.prev.next = node.next;
            node.next.prev = node.prev;
            node.next = null;
            addNodeToTail(node);
        }
    }
}

反转字符串
class Solution {
    public void reverseString(char[] s) {
        int start = 0;
        int end = s.length - 1;
        while(start < end){
            swap(s,start,end);
            start++;
            end--;
        }
    }
    
    public void swap(char[] array,int a,int b){
        char tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }
    
    
}

//字符串转换整数
package com.jxyang.test.geek.day4.Solution;

class Solution2 {
    public int myAtoi(String str) {
        if(str==null){
            return 0;
        }
        char[] arr= str.toCharArray();
        boolean flag = false;
        boolean numBegin = false;
        int result = 0;
        for(int i =0;i<arr.length;i++){
            if(numBegin && (arr[i]=='-'||arr[i]=='+'||arr[i]==' ')){
                break;
            }else if(arr[i]==' ') {
                continue;
            }else if(arr[i]=='+'){
                numBegin = true;
                continue;
            }else if(arr[i]=='-'){
                flag = true;
                numBegin = true;
                continue;
            }else if(arr[i]>='0'&&arr[i]<='9'){
                numBegin = true;
                if(result==0){
                    result = flag?('0'-arr[i]):(arr[i]-'0');
                }else{
                    try{
                        result = Math.multiplyExact(result,10);
                        result = Math.addExact(result,flag?('0'-arr[i]):(arr[i]-'0'));
                    }catch (Exception e){
                        if(flag){
                            return Integer.MIN_VALUE;
                        }else{
                            return Integer.MAX_VALUE;
                        }
                    }
                }
            }else{
                break;
            }
        }
        return result;
    }
    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();
        System.out.println(solution2.myAtoi("42"));
        System.out.println(solution2.myAtoi(" +0 123"));//期望123
        System.out.println(solution2.myAtoi(" -42"));
        System.out.println(solution2.myAtoi("4193 with words"));
        System.out.println(solution2.myAtoi("words and 987"));
        System.out.println(solution2.myAtoi("-91283472332"));//期望-2147483648
        System.out.println(solution2.myAtoi("+1"));//期望-2147483648
    }
}

class Solution {
//反转字符串
    public void reverseString(char[] s) {
        if(s==null||s.length<2){
            return;
        }
        int l=0;
        int r=s.length-1;
        while (l<r){
            char tmp = s[l];
            s[l] = s[r];
            s[r] = tmp;
            l++;
            r--;
        }
    }
}

Reverse Words in a String

public class Solution {
    public String reverseWords(String s) {
        final List<String> words = new ArrayList<>();
        final char[] charArray = s.toCharArray();
        
        int start = 0;
        int end = 0;
        while (end < s.length()) {
            if (' ' == charArray[end]) {
                if (start != end) {
                    words.add(getWord(charArray, start, end));
                    start = end;
                }
                start++;
                end++;
            } else {
                end++;
            }
        }
        
        if (start != end) {
            words.add(getWord(charArray, start, end));
        }
        
        Collections.reverse(words);
        return String.join(" ", words);
    }
    
    private String getWord(final char[] charArray, final int start, final int end) {
        char[] tmp = new char[end - start];
        int pos = 0;
        for(int i = start; i < end; i++) {
            tmp[pos++] = charArray[i];
        }
        return new String(tmp);
    }
}