leetcode解题思路分析（五十三）454 - 461 题

旧城等待， 2022-12-27 11:02 159阅读 0赞

1.  四数相加  
    给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A\[i\] + B\[j\] + C\[k\] + D\[l\] = 0。

**将AB视为统一的元素，将和存在哈希表中，然后C和D双重循环，依次求解**

class Solution { 
    public:
        int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) { 
            unordered_map<int, int> countAB;
            for (int u: A) { 
                for (int v: B) { 
                    ++countAB[u + v];
                }
            }
            int ans = 0;
            for (int u: C) { 
                for (int v: D) { 
                    if (countAB.count(-u - v)) { 
                        ans += countAB[-u - v];
                    }
                }
            }
            return ans;
        }
    };

1.  分发饼干  
    假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。  
    对每个孩子 i，都有一个胃口值 g\[i\]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s\[j\] 。如果 s\[j\] >= g\[i\]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

**贪心算法基础题，可以从最大开始匹配，也可以从最小开始匹配**

class Solution { 
    public:
        int findContentChildren(vector<int>& g, vector<int>& s) { 
            int gPos = 0, sPos = 0, ret = 0;
            sort(g.begin(), g.end());
            sort(s.begin(), s.end());
            while (gPos < g.size() && sPos < s.size())
            { 
                if (s[sPos] >= g[gPos])
                { 
                    ++ret;
                    ++gPos;
                }
                ++sPos;
            }
            return ret;
        }
    };

1.  132模式  
    给定一个整数序列：a1, a2, …, an，一个132模式的子序列 ai, aj, ak 被定义为：当 i < j < k 时，ai < ak < aj。设计一个算法，当给定有 n 个数字的序列时，验证这个序列中是否含有132模式的子序列。

**目标是找到132，倒序找则找到23再找到1即可所以先保存第一个数，然后依次遍历，如果比第一个数大，则保存为two。如果有更大的，则更新two。如果找到比two小的了，直接返回。**

class Solution { 
    public:
        bool find132pattern(vector<int>& nums) 
        { 
            if (nums.size() <= 2) return false;
            int two = INT_MIN;
            stack<int> m_stack;
            for (int i = nums.size() - 1; i >= 0; i--)
            { 
                if (nums[i] < two) return true; 
                while (!m_stack.empty() && m_stack.top() < nums[i])
                { 
                    two = m_stack.top(); 
                    m_stack.pop();
                }
                m_stack.push(nums[i]);
            }
            return false;
        }
    };

1.  环形数组循环  
    给定一个含有正整数和负整数的环形数组 nums。 如果某个索引中的数 k 为正数，则向前移动 k 个索引。相反，如果是负数 (-k)，则向后移动 k 个索引。因为数组是环形的，所以可以假设最后一个元素的下一个元素是第一个元素，而第一个元素的前一个元素是最后一个元素。  
    确定 nums 中是否存在循环（或周期）。循环必须在相同的索引处开始和结束并且循环长度 > 1。此外，一个循环中的所有运动都必须沿着同一方向进行。换句话说，一个循环中不能同时包括向前的运动和向后的运动。

**设计思路为递归，如果不符合条件则点至0，正在检索中则置为最大值，如果方向不符合则返回false，如果遇到正在检索中的点则出现了闭环，为true。闭环为1则跳过。**

class Solution 
    { 
        int m_size;
    public:
        bool dfs(vector<int>& nums, int pos, int dir) 
        { 
            // 遇到不符合条件的点，返回false
            if (nums[pos] == 0) return false;
            // 遇到在考察中的点，说明形成了闭环，返回true
            if (nums[pos] == INT_MAX) return true;
    
            if (nums[pos] * dir > 0) 
            { 
                int next = (m_size + (nums[pos] + pos) % m_size) % m_size;
    
                // 将pos处的值设为INT_MAX，标志pos点在考察中
                nums[pos] = INT_MAX;
                if (next != pos && dfs(nums, next, dir)) 
                { 
                    return true;
                } 
                else 
                { 
                    // pos点不符合条件，赋值为0
                    nums[pos] = 0;
                    return false;
                }
            }
            return false;
        }
    
        bool circularArrayLoop(vector<int>& nums) 
        { 
            m_size = nums.size();
            for (int i = 0; i < m_size; ++i) 
            { 
                if (nums[i] == 0) continue;
                int dir = nums[i] > 0 ? 1 : -1;
                if (dfs(nums, i, dir)) 
                { 
                    return true;
                }
            }
            return false;
        }
    };

1.  可怜的小猪  
    有 buckets 桶液体，其中 正好 有一桶含有毒药，其余装的都是水。它们从外观看起来都一样。为了弄清楚哪只水桶含有毒药，你可以喂一些猪喝，通过观察猪是否会死进行判断。不幸的是，你只有 minutesToTest 分钟时间来确定哪桶液体是有毒的。  
    喂猪的规则如下：  
    选择若干活猪进行喂养  
    可以允许小猪同时饮用任意数量的桶中的水，并且该过程不需要时间。  
    小猪喝完水后，必须有 minutesToDie 分钟的冷却时间。在这段时间里，你只能观察，而不允许继续喂猪。  
    过了 minutesToDie 分钟后，所有喝到毒药的猪都会死去，其他所有猪都会活下来。  
    重复这一过程，直到时间用完。  
    给你桶的数目 buckets ，minutesToDie 和 minutesToTest ，返回在规定时间内判断哪个桶有毒所需的 最小 猪数。

**只能喝一次水则有死和活两种状态，如果能喝两次，则有活，第一次喝了死和第二次喝了死三种状态，以此类推。所以status作为底，数量为指数，只要指数的结果大于bucket即可。**

class Solution { 
    public:
        int poorPigs(int buckets, int minutesToDie, int minutesToTest) { 
            int states = minutesToTest / minutesToDie + 1;
            return ceil(log(buckets) / log(states));
        }
    };

1.  重复的子字符串  
    给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

**原理是如果s由多个重复子串构成，则两个s拼接以后，从第二个字符开始找一个s，一定会在第二个s结束前就找到**

class Solution { 
    public:
        bool repeatedSubstringPattern(string s) { 
            return (s + s).find(s, 1) != s.size();
        }
    };

1.  LFU缓存

**双哈希表可以实现O(1)时间复杂度，相当于空间换时间。第一个哈希表为key， iterator。指向第二个哈希表。第二个哈希表为frequency, val。其中解决第二个哈希冲突采取链表解决**

// 缓存的节点信息
    struct Node { 
        int key, val, freq;
        Node(int _key,int _val,int _freq): key(_key), val(_val), freq(_freq){ }
    };
    class LFUCache { 
        int minfreq, capacity;
        unordered_map<int, list<Node>::iterator> key_table;
        unordered_map<int, list<Node>> freq_table;
    public:
        LFUCache(int _capacity) { 
            minfreq = 0;
            capacity = _capacity;
            key_table.clear();
            freq_table.clear();
        }
        
        int get(int key) { 
            if (capacity == 0) return -1;
            auto it = key_table.find(key);
            if (it == key_table.end()) return -1;
            list<Node>::iterator node = it -> second;
            int val = node -> val, freq = node -> freq;
            freq_table[freq].erase(node);
            // 如果当前链表为空，我们需要在哈希表中删除，且更新minFreq
            if (freq_table[freq].size() == 0) { 
                freq_table.erase(freq);
                if (minfreq == freq) minfreq += 1;
            }
            // 插入到 freq + 1 中
            freq_table[freq + 1].push_front(Node(key, val, freq + 1));
            key_table[key] = freq_table[freq + 1].begin();
            return val;
        }
        
        void put(int key, int value) { 
            if (capacity == 0) return;
            auto it = key_table.find(key);
            if (it == key_table.end()) { 
                // 缓存已满，需要进行删除操作
                if (key_table.size() == capacity) { 
                    // 通过 minFreq 拿到 freq_table[minFreq] 链表的末尾节点
                    auto it2 = freq_table[minfreq].back();
                    key_table.erase(it2.key);
                    freq_table[minfreq].pop_back();
                    if (freq_table[minfreq].size() == 0) { 
                        freq_table.erase(minfreq);
                    }
                } 
                freq_table[1].push_front(Node(key, value, 1));
                key_table[key] = freq_table[1].begin();
                minfreq = 1;
            } else { 
                // 与 get 操作基本一致，除了需要更新缓存的值
                list<Node>::iterator node = it -> second;
                int freq = node -> freq;
                freq_table[freq].erase(node);
                if (freq_table[freq].size() == 0) { 
                    freq_table.erase(freq);
                    if (minfreq == freq) minfreq += 1;
                }
                freq_table[freq + 1].push_front(Node(key, value, freq + 1));
                key_table[key] = freq_table[freq + 1].begin();
            }
        }
    };

1.  汉明距离  
    两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给出两个整数 x 和 y，计算它们之间的汉明距离。

**异或后逐位与即可**

class Solution { 
    public:
        int hammingDistance(int x, int y) { 
            x = x ^ y;
            int cnt = 0;
    
            //将每一个元素与然后右移
            while ( x > 0)
            { 
                cnt += x & 1;
                x >>= 1;
            }
    
            return cnt;
        }
    };