链表反转

解题思路

采用链表原地逆置的思想，设立两个指针pre和cur，初始时pre=nil, cur=head。每次循环时，都使cur和pre向后移动的同时，使得cur.Next指向pre
采用头插法的思想，设立一个头节点，将原链表中的各节点依次插入到头节点后
借助辅助栈实现，从前向后遍历链表并压入栈中，遍历完成后依次将栈中元素弹出构建新链表（空间辅助度达O(n)）

解题代码

链表原地逆置

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var pre , cur  *ListNode	// pre指向cur的前驱
    pre = nil
    cur = head

    for cur != nil {
        // cur指向下一个节点
        // cur的Next指向前驱pre
        // pre指向cur
        cur, cur.Next, pre = cur.Next, pre, cur
    }

    return pre

}

头插法

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    cur := head
    var newHead ListNode   // 设立新的头节点

    for cur != nil {
        // 将cur头插到newHead后
        newHead.Next, cur , cur.Next = cur, cur.Next, newHead.Next
    }

    return newHead.Next //返回结果不需要头节点
}

LRU缓存

解题思路

因为需要用到key-value对，所以考虑使用hash map来保存k-v对。用双向链表来模拟实现LRU算法，每一次访问命中或在cache中加入新数据，则将对应的节点移动到链表头部；而链表尾部则是最久未被访问到的数据，每次替换都将链表尾部的节点替换出去
函数get：在map中查找key，若不存在则直接返回-1；若存在则将对应节点移动到双向链表的头部
函数put：在map中查找key，若不存在则插入该数据，根据实际占用的容量与总容量的关系，选择直接插入或是将链表尾部的数据块替换出去，插入完成后将节点移动到链表头部；若存在则更新value并将对应节点移动到链表头部

解题代码

type DLNode struct {    // 双向链表节点
    key, value int  
    pre, next *DLNode   // 前后指针
}


type LRUCache struct {
    capacity int    // 总容量
    size int    // 实际占用的容量
    hashmap map[int]*DLNode // hash表，用于存储key和对应的链表节点
    head, tail *DLNode  // 双向链表的头尾指针
}


func DLNodeInit(key, value int) (*DLNode) {
    return &DLNode{
        key: key,
        value: value,
    }
}


func Constructor(capacity int) LRUCache {
    cache := LRUCache{
        capacity: capacity,
        hashmap: map[int]*DLNode{},
        head: DLNodeInit(0, 0),
        tail: DLNodeInit(0, 0),
    }
    cache.head.next = cache.tail
    cache.tail.pre = cache.head
    
    return cache
}


func (this *LRUCache) Get(key int) int {
    if _, ok := this.hashmap[key]; ok { // 关键字key在cache中存在
        // 将对应节点取下来,放到链表头部
        node := this.hashmap[key]
        this.removeToHead(node)
        // 返回value
        return node.value
    } else {    // 关键字不存在，返回-1
        return -1
    }
}


func (this *LRUCache) Put(key int, value int)  {
    if _, ok := this.hashmap[key]; !ok {    // 若key不存在
        if this.size < this.capacity {  // cache缓存未被放满
            node := DLNodeInit(key, value)
            // 插入到head之后
            this.head.next, node.pre, node.next, this.head.next.pre = node, this.head, this.head.next, node
            // 写hash表
            this.hashmap[key] = node
            // 增加实际占用的空间
            this.size++
        } else {    // 将链表最后一个元素替换出去
            node := this.tail.pre
            // 在hash表中删除链表的最后一个元素
            delete(this.hashmap, node.key)
            // 写入新数据
            node.key = key
            node.value = value
            // 将最后一个节点取下来，插入到head之后
            this.removeToHead(node)
            // 新key写入hash表
            this.hashmap[key] = node
        }
    } else {    //key存在，更新value值
        // 将对应节点取下来，插入到head之后
        node := this.hashmap[key]
        this.removeToHead(node)
        // 更新vale
        node.value = value
    }
}

func (this *LRUCache) removeToHead(node *DLNode) {
    // 将对应节点取下来
    node.pre.next, node.next.pre = node.next, node.pre
    // 插入到head之后
    this.head.next, node.pre, node.next, this.head.next.pre = node, this.head, this.head.next, node
}

无重复字符的最长子串

解题思路

采用滑动窗口的思想，从前向后遍历字符串，利用map记录每个字符的出现位置。
若当前遍历字符为s[i]，那么如果s[i]已经出现并且在窗口的起始位置之后，则更新窗口起始位置，将窗口起始位置更新为上次出现的位置+1。接着在map更新s[i]的最新出现位置。若窗口长度大于当前无重复子串最大长度，则将之更新为窗口长度。

解题代码

func lengthOfLongestSubstring(s string) int {
    n := len(s)	// 字符串长度
    var maxLen, start int	// 无重复子串最大长度，滑动窗口的起始位置
    subsring := map[byte]int{}

    for i := 0; i < n; i++ {
        if _, ok := subsring[s[i]]; ok && subsring[s[i]] >= start{
            // 若s[i]已经出现且在窗口的起始位置及以后，则更新窗口的起始位置
			start = subsring[s[i]] + 1
        }
        subsring[s[i]] = i	// 更新s[i]的最新位置
        if i-start+1 > maxLen {	// i-start+1为窗口长度，窗口长度>maxLen，则更新
            maxLen = i-start+1
        }
    }

    return maxLen
}

Dawn's Blogs

算法刷题笔记 (1) 链表反转 LRU缓存无重复字符的最长子串

链表反转

解题思路

解题代码

LRU缓存

解题思路

解题代码

无重复字符的最长子串

解题思路

解题代码