力扣题解(哈希表)

1. 两数之和

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 如果列表中有相同元素，后面元素的索引会覆盖前面元素的索引
        unordered_map<int, int> m;
        vector<int> res;
        for (int i = 0; i < nums.size(); i++) {
            m[nums[i]] = i;
        }
        for (int i = 0; i < nums.size(); i++ ) {
            int t = target - nums[i];
            if(m.count(t) && m[t] != i) {
                res.push_back(i);
                res.push_back(m[t]);
                break;
            }
        }
        return res;
    }
};

3. 无重复字符的最长子串

参考

图片来源网络，见参考

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int max = 0;
        map<char, int> m;  // 记录当前子串中各个字符出现的次数
        for (int left = 0, right = 0; right < s.size(); right ++) {
            m[s[right]] ++;
            while(m[s[right]] > 1) {  // 存在重复(按照这种遍历方式出现重复一定是首尾重复)
                m[s[left]] --;  // 更新哈西表
                left ++;  // 左指针右移
            }
            max = right - left + 1 > max ? right - left + 1 : max;
        }
        return max;
    }
};

136. 只出现一次的数字

异或运算的性质：

1. 交换律：a ^ b ^ c <=> a ^ c ^ b
2. 任何数与0异或为其自身：0 ^ n => n
3. 相同的数异或为0：n ^ n => 0

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        // 最开始的思路：哈希表统计每个字符出现的次数，时间复杂度 O(n)，空间复杂度 O(n)
        // 思路二：异或运算的数学性质
        int res = 0;
        for (auto num : nums) {
            res = res ^ num;
        }
        return res;
    }
};

138. 复制带随机指针的链表

参考

1. 拷贝原链表的每一个节点，将其接在原链表相应节点的后面（拷贝的节点的所有 random 指针都置空）。

   
   拷贝节点

2. 设定random指针。由于新节点就在原节点的后面，因此，依次检测给定链表中的每个节点，若random不为空，则将它的下一个节点（对应新节点）的random指针指向原节点random指针所指节点的下一个节点。

   
   image.png
3. 拆分链表

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head)
            return nullptr;
        Node *iter = head;
        while(iter) {
            Node *node = new Node(iter->val, iter->next, nullptr);
            iter->next = node;
            iter = iter->next->next;
        }
        iter = head;
        while(iter) {
            if(iter->random)
                iter->next->random = iter->random->next;
            iter = iter->next->next;
        }
        iter = head;
        Node *ret = iter->next;  // 要返回的链表头
        while(iter->next) {
            Node *tmp = iter->next;
            iter->next = iter->next->next;
            iter = tmp;
        }
        return ret;
    }
};

面试题 16.20. T9键盘

class Solution {
public:
    vector<string> getValidT9Words(string num, vector<string>& words) {
        // 构建 hashmap，遍历单词，暴力匹配
        unordered_map<char, bool> hp[10];
        vector<string> res;
        // 不会出现 0, 1 两个数字
        hp[2]['a'] = hp[2]['b'] = hp[2]['c'] = true;
        hp[3]['d'] = hp[3]['e'] = hp[3]['f'] = true;
        hp[4]['g'] = hp[4]['h'] = hp[4]['i'] = true;
        hp[5]['j'] = hp[5]['k'] = hp[5]['l'] = true;
        hp[6]['m'] = hp[6]['n'] = hp[6]['o'] = true;
        hp[7]['p'] = hp[7]['q'] = hp[7]['r'] = hp[7]['s'] = true;
        hp[8]['t'] = hp[8]['u'] = hp[8]['v'] = true;
        hp[9]['w'] = hp[9]['x'] = hp[9]['y'] = hp[9]['z'] = true;
        int num_size = num.size();
        for (string word : words) {
            int word_size = word.size();
            if (word_size == num_size) {
                int j = 0;
                for (j = 0; j < num_size; j++) {
                    if (!hp[num[j] - '0'][word[j]]) break;
                }
                if (j >= num_size) {
                    res.push_back(word);
                }
            }
        }
        return res;
    }
};