leetcode解题思路分析（三十五）284—290题

蔚落 2023-03-03 08:57 17阅读 0赞

1.  顶端迭代器  
    给定一个迭代器类的接口，接口包含两个方法： next() 和 hasNext()。设计并实现一个支持 peek() 操作的顶端迭代器 – 其本质就是把原本应由 next() 方法返回的元素 peek() 出来。

**很无聊的一道题，无非是考一个提前量而已**

/* * Below is the interface for Iterator, which is already defined for you. * **DO NOT** modify the interface for Iterator. * * class Iterator { * struct Data; * Data* data; * Iterator(const vector<int>& nums); * Iterator(const Iterator& iter); * * // Returns the next element in the iteration. * int next(); * * // Returns true if the iteration has more elements. * bool hasNext() const; * }; */
    
    class PeekingIterator : public Iterator { 
        int nCurr;
        bool bEnd;
    public:
    
    	PeekingIterator(const vector<int>& nums) : Iterator(nums) 
        { 
    	    // Initialize any member here.
    	    // **DO NOT** save a copy of nums and manipulate it directly.
    	    // You should only use the Iterator interface methods.
    	    bEnd = false;
            if (Iterator::hasNext()) 
            { 
                nCurr = Iterator::next();
            } 
            else 
            { 
                bEnd = true;
            }
    	}
    
        // Returns the next element in the iteration without advancing the iterator.
    	int peek() 
        { 
            return nCurr;
    	}
    
    	// hasNext() and next() should behave the same as in the Iterator interface.
    	// Override them if needed.
    	int next() 
        { 
            if (bEnd) 
            { 
                return -1;
            }
            int res = nCurr;
    	    if (Iterator::hasNext()) 
            { 
                nCurr = Iterator::next();
            } 
            else 
            { 
                bEnd = true;
            }
            return res;
    	}
    
    	bool hasNext() const 
        { 
    	    return !bEnd;
    	}
    };

1.  寻找重复数  
    给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

**本题可以通过二分查找或者二进制位操作进行，但是最佳做法是类似于142题的快慢指针求解。这里有三个关键点：1. 我们以数组值作为下一个索引项，以此构建了一个图。由于有重复值，所以该图一定有环路 2. 因为索引从0开始而数值从1开始，因此快慢指针不可能在开始循环的时候陷入原地死循环。 3. 找到数之后再次循环，相遇的位置即为环的接入点，即重复元素值**

class Solution { 
    public:
        int findDuplicate(vector<int>& nums) { 
            int slow = 0, fast = 0;
            do { 
                slow = nums[slow];
                fast = nums[nums[fast]];
            } while (slow != fast);
            slow = 0;
            while (slow != fast) { 
                slow = nums[slow];
                fast = nums[fast];
            }
            return slow;
        }
    };

1.  生命游戏  
    根据当前状态，写一个函数来计算面板上所有细胞的下一个（一次更新后的）状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。

**本题有一个陷阱就是已修改的可能对未修改的产生影响，不适用额外空间的话比较好的办法是使用额外的标记，如0表示死亡，1表示活着，增加2表示从死亡活过来，-1表示从活变成死亡即可完美解决**

class Solution { 
    public:
        void gameOfLife(vector<vector<int>>& board) { 
            int neighbors[3] = { 0, 1, -1};
    
            int rows = board.size();
            int cols = board[0].size();
    
            // 遍历面板每一个格子里的细胞
            for (int row = 0; row < rows; row++) { 
                for (int col = 0; col < cols; col++) { 
    
                    // 对于每一个细胞统计其八个相邻位置里的活细胞数量
                    int liveNeighbors = 0;
    
                    for (int i = 0; i < 3; i++) { 
                        for (int j = 0; j < 3; j++) { 
    
                            if (!(neighbors[i] == 0 && neighbors[j] == 0)) { 
                                // 相邻位置的坐标
                                int r = (row + neighbors[i]);
                                int c = (col + neighbors[j]);
    
                                // 查看相邻的细胞是否是活细胞
                                if ((r < rows && r >= 0) && (c < cols && c >= 0) && (abs(board[r][c]) == 1)) { 
                                    liveNeighbors += 1;
                                }
                            }
                        }
                    }
    
                    // 规则 1 或规则 3 
                    if ((board[row][col] == 1) && (liveNeighbors < 2 || liveNeighbors > 3)) { 
                        // -1 代表这个细胞过去是活的现在死了
                        board[row][col] = -1;
                    }
                    // 规则 4
                    if (board[row][col] == 0 && liveNeighbors == 3) { 
                        // 2 代表这个细胞过去是死的现在活了
                        board[row][col] = 2;
                    }
                }
            }
    
            // 遍历 board 得到一次更新后的状态
            for (int row = 0; row < rows; row++) { 
                for (int col = 0; col < cols; col++) { 
                    if (board[row][col] > 0) { 
                        board[row][col] = 1;
                    } else { 
                        board[row][col] = 0;
                    }
                }
            }
        }
    };

1.  单词规律  
    给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。

**1.定义两个map，为何定义两个呢？ 防止\[aaaa\]与\[cat dog dog cat\]、\[abba\]与\[cat cat cat cat\]时输出true  
2.用stringstream可以自动输出词组  
3.判断：!(ss >> s)判断pattern长度是否大于str长度，且将ss容器中字符串赋值给s  
4.判断：(map.count© == 1 && map\[c\] != s) || (rmap.count(s) == 1 && rmap\[s\] != c)) 来判断是否匹配  
5.判断：(ss >> s) ? false : true 判断str长度是否大于pattern长度**

class Solution { 
    public:
        bool wordPattern(string pattern, string str) 
        { 
            unordered_map<char, string> map;
            unordered_map<string, char> rmap;
            stringstream ss(str); string s;
            for(char c : pattern) 
            { 
                if(!(ss >> s) || (map.count(c) == 1 && map[c] != s) 
                    || (rmap.count(s) == 1 && rmap[s] != c)) 
                    return false;
                map[c] = s; 
                rmap[s] = c;
            }
            return (ss >> s) ? false : true;
        }
    };

1.  Nim游戏  
    你和你的朋友，两个人一起玩 Nim 游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。  
    你们是聪明人，每一步都是最优解。 编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。

**当i个必败的情况下，i + 1, i + 2, i + 3必胜，因此i 为4的倍数则必败，否则必胜**

class Solution { 
    public:
        bool canWinNim(int n) { 
            if (n <= 3)
                return true;
            return !(n % 4 == 0);
        }
    };

1.  数据流的中位数  
    设计一个支持以下两种操作的数据结构：  
    void addNum(int num) - 从数据流中添加一个整数到数据结构中。  
    double findMedian() - 返回目前所有元素的中位数。

**最简单的做法就是用动态数组保存，然后每次查询的时候先排序再取中间数。优化版的方法是每次保存均插入在排序的位置上，即查询的时候不需要排序。更好的方法是采取两个堆：一个最小堆一个最大堆，由此两个堆的堆顶即是中位数。该做法需要做到两个堆的平衡，但是总体复杂度较容器低。除此之外还可以采取自平衡树，也有类似的效果。**

class MedianFinder { 
        priority_queue<int> lo;                              // max heap
        priority_queue<int, vector<int>, greater<int>> hi;   // min heap
    
    public:
        // Adds a number into the data structure.
        void addNum(int num)
        { 
            lo.push(num);                                    // Add to max heap
    
            hi.push(lo.top());                               // balancing step
            lo.pop();
    
            if (lo.size() < hi.size()) {                      // maintain size property
                lo.push(hi.top());
                hi.pop();
            }
        }
    
        // Returns the median of current data stream
        double findMedian()
        { 
            return lo.size() > hi.size() ? (double) lo.top() : (lo.top() + hi.top()) * 0.5;
        }
    };
    
    
    /** * Your MedianFinder object will be instantiated and called as such: * MedianFinder* obj = new MedianFinder(); * obj->addNum(num); * double param_2 = obj->findMedian(); */

class MedianFinder { 
        multiset<int> data;
        multiset<int>::iterator mid;
    
    public:
        MedianFinder()
            : mid(data.end())
        { 
        }
    
        void addNum(int num)
        { 
            const int n = data.size();
            data.insert(num);
    
            if (!n)                                 // first element inserted
                mid = data.begin();
            else if (num < *mid)                    // median is decreased
                mid = (n & 1 ? mid : prev(mid));
            else                                    // median is increased
                mid = (n & 1 ? next(mid) : mid);
        }
    
        double findMedian()
        { 
            const int n = data.size();
            return (*mid + *next(mid, n % 2 - 1)) * 0.5;
        }
    };

1.  二叉树的序列化和反序列化  
    序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。  
    请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

**采用递归或者堆栈均可，说白了就是二叉树的前中后序遍历加一个字符串处理而已，没有难度**

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Codec {
    public:
    
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
            string res;
            dfs_s(root, res);
            return res;
        }
    
        // 前序遍历序列转化为字符串
        void dfs_s(TreeNode* root, string& res) {
            if (!root) {
                res += "null ";
                return;
            }
            res += to_string(root->val) + ' ';
            dfs_s(root->left, res);
            dfs_s(root->right, res);
        }
    
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            // 开始遍历索引
            int u = 0;
            return dfs_d(data, u);
        }
    
        TreeNode* dfs_d(string& data, int& u) {
            if (u >= data.size()) return NULL;
            if (data[u] == 'n') {
                u = u + 5;
                return NULL;
            }
            int val = 0, sign = 1;
            if (data[u] == '-') sign = -1, u ++ ;
            while(data[u] != ' '){val = val * 10 + data[u] - '0'; u++;}
            val *= sign;
            u = u + 1 ;
    
            auto root = new TreeNode(val);
            root->left = dfs_d(data, u);
            root->right = dfs_d(data, u);
    
            return root;
        }
    };
    
    
    // Your Codec object will be instantiated and called as such:
    // Codec codec;
    // codec.deserialize(codec.serialize(root));