[数据结构与算法]LeetCode 热题 HOT 100 第十天

Leetcode136. 只出现一次的数字

思路：位运算

异或的性质：

1. 符合交换律、结合律、分配律
2. 两个相同的数异或为0：$x^x=0$
3. 两个不同的数异或为1：$x^y=1$

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (auto& t : nums) res ^= t;
        return res;
    }
};

Leetcode139. 单词拆分

思路：字符串哈希+动态规划

扫描一遍字典，存储每一个字典中的字串哈希值，枚举每一个位置，在上一个可以拆分的位置后查找可能的拆分的位置

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        typedef unsigned long long ULL;
        const int P = 131;
        unordered_set<ULL> S;
        for (auto& word : wordDict) {
            ULL h = 0;
            for (auto& c : word) h = h * P + c;
            S.insert(h);
        }

        int n = s.size();
        vector<bool> f(n + 1);
        s = ' ' + s;
        f[0] = true;
        for (int i = 0; i < n; i ++ ) {
            if (f[i]) {
                ULL h = 0;
                for (int j = i + 1; j <= n; j ++ ) {
                    h = h * P + s[j];
                    if (S.count(h)) f[j] = true;
                }
            }
        }
        return f[n];
    }
};

Leetcode142. 环形链表

思路一：哈希表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode*> S;
        while (head) {
            if (S.count(head)) return head;
            S.insert(head);
            head = head->next;
        }
        return NULL;
    }
};

思路二：快慢指针

/**
 * 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) {
        auto l = head, f = head;
        while (f) {
            l = l->next;
            f = f->next;
            if (!f) return NULL;
            f = f->next;
            if (f == l) return f;
        }
        return NULL;
    }
};

Leetcode142. 环形链表2

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        auto f = head, l = head;
        while (f) {
            l = l->next;
            f = f->next;
            if (!f) return NULL;
            f = f->next;
            if (l == f) {
                f = head;
                while (f != l) f = f->next, l = l->next;
                return f;
            }
        }
        return NULL;
    }
};

Leetcode146. LRU缓存机制

class LRUCache {
public:
    struct Node
    {
        int val, key;
        Node *left, *right;
        Node() : key(0), val(0), left(NULL), right(NULL) {}
    };
    Node *hu, *tu; // hu: head_used, tu: tail_used; head在左侧，tail在右侧
    Node *hr, *tr; // hr: head_remains, tr: tail_remains; head在左侧，tail在右侧
    int n;
    unordered_map<int, Node*> hash;

    void delete_node(Node *p)
    {
        p->left->right = p->right, p->right->left = p->left;
    }

    void insert_node(Node *h, Node *p)
    {
        p->right = h->right, h->right = p;
        p->left = h, p->right->left = p;
    }

    LRUCache(int capacity) {
        n = capacity;
        hu = new Node(), tu = new Node();
        hr = new Node(), tr = new Node();
        hu->right = tu, tu->left = hu;
        hr->right = tr, tr->left = hr;

        for (int i = 0; i < n; i ++ )
        {
            Node *p = new Node();
            insert_node(hr, p);
        }
    }

    int get(int key) {
        if (hash[key])
        {
            Node *p = hash[key];
            delete_node(p);
            insert_node(hu, p);
            return p->val;
        }
        return -1;
    }

    void put(int key, int value) {
        if (hash[key])
        {
            Node *p = hash[key];
            delete_node(p);
            insert_node(hu, p);
            p->val = value;
            return;
        }

        if (!n)
        {
            n ++ ;
            Node *p = tu->left;
            hash[p->key] = 0;
            delete_node(p);
            insert_node(hr, p);
        }

        n -- ;
        Node *p = hr->right;
        p->key = key, p->val = value, hash[key] = p;
        delete_node(p);
        insert_node(hu, p);
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */