leetcode刷题记录08（2023-05-03）【只出现一次的数字(异或运算) | 单词拆分 | 环形链表 II(快慢指针/哈希) | 二叉树的序列化与反序列化(前序遍历建树)】

素颜马尾好姑娘i 2024-03-22 11:39 7阅读 0赞

## 136. 只出现一次的数字 ##

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：  
输入：nums = \[2,2,1\]  
输出：1

示例 2 ：  
输入：nums = \[4,1,2,1,2\]  
输出：4

示例 3 ：  
输入：nums = \[1\]  
输出：1

提示：  
 1 < = n u m s . l e n g t h < = 3 ∗ 1 0 4 1 <= nums.length <= 3 \* 10^4 1<=nums.length<=3∗104  
 − 3 ∗ 1 0 4 < = n u m s \[ i \] < = 3 ∗ 1 0 4 -3 \* 10^4 <= nums\[i\] <= 3 \* 10^4 −3∗104<=nums\[i\]<=3∗104  
除了某个元素只出现一次以外，其余每个元素均出现两次。

进行异或运算，多个数，一起进行异或运算，相同的都会归0，不同的位为1。思路很巧妙，代码如下：

// 代码：
    #include<iostream>
    #include<vector>
    using namespace std;
    
    class Solution {
        	
    	public:
    		int singleNumber(vector<int>& nums) {
        
    		int ans = 0;
    		for (auto num : nums) {
        
    			ans ^= num;
    		}
    		return ans;
    	}
    };
    
    int main() {
        
    	Solution sol;
    	vector<int> vec = {
         4,1,2,1,2 };
    	int res = sol.singleNumber(vec);
    	cout<< res << endl;
    }

## 139. 单词拆分 ##

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：  
输入: s = “leetcode”, wordDict = \[“leet”, “code”\]  
输出: true  
解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。

示例 2：  
输入: s = “applepenapple”, wordDict = \[“apple”, “pen”\]  
输出: true  
解释: 返回 true 因为 “applepenapple” 可以由 “apple” “pen” “apple” 拼接成。  
注意，你可以重复使用字典中的单词。

示例 3：  
输入: s = “catsandog”, wordDict = \[“cats”, “dog”, “sand”, “and”, “cat”\]  
输出: false

提示：  
 1 < = s . l e n g t h < = 300 1 <= s.length <= 300 1<=s.length<=300  
 1 < = w o r d D i c t . l e n g t h < = 1000 1 <= wordDict.length <= 1000 1<=wordDict.length<=1000  
 1 < = w o r d D i c t \[ i \] . l e n g t h < = 20 1 <= wordDict\[i\].length <= 20 1<=wordDict\[i\].length<=20  
s 和 wordDict\[i\] 仅有小写英文字母组成  
wordDict 中的所有字符串 互不相同

采用一维动态规划来实现。当前长度是否满足条件，取决于他前面的前缀串是否满足，以及除了前缀串之外的子串是否满足。

代码如下：

#include<iostream>
    #include<vector>
    #include<unordered_set>
    #include<iostream>
    using namespace std;
    
    class Solution {
        
    public:
        bool wordBreak(string s, vector<string>& wordDict) {
        
            unordered_set<string> st = unordered_set<string>();
            for (int i = 0; i < wordDict.size(); i++) {
        
                st.insert(wordDict[i]);
            }
            vector<bool> dp = vector<bool>(s.size() + 1, false);
            dp[0] = true;
            for (int i = 1; i < s.size() + 1; i++) {
        
                for (int j = 0; j < i; j++) {
        
                    string tmp = s.substr(j, i - j);
                    if (dp[j] && st.find(tmp) != st.end()) {
        
                        dp[i] = true;
                        break;
                    }
                }
            }
            return dp[s.size()];
        }
    };
    
    int main() {
        
        string s = "leetcode";
        vector<string> wordDict = {
         "leet", "code" };
        Solution sol;
        bool is = sol.wordBreak(s, wordDict);
        cout << is;
    }

## 142. 环形链表 II ##

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

![在这里插入图片描述][8b846848dab14bdfad87a6e43e960f14.png]

输入：head = \[3,2,0,-4\], pos = 1  
输出：返回索引为 1 的链表节点  
解释：链表中有一个环，其尾部连接到第二个节点。  
示例 2：

![在这里插入图片描述][2d828ea2f6224450ae92e2609580b69f.png]

输入：head = \[1,2\], pos = 0  
输出：返回索引为 0 的链表节点  
解释：链表中有一个环，其尾部连接到第一个节点。  
示例 3：

![在这里插入图片描述][f7f05f45cb2b49859f4e47b59942553e.png]

输入：head = \[1\], pos = -1  
输出：返回 null  
解释：链表中没有环。

提示：

链表中节点的数目范围在范围 \[0, 104\] 内  
 − 1 0 5 < = N o d e . v a l < = 1 0 5 -10^5 <= Node.val <= 10^5 −105<=Node.val<=105  
pos 的值为 -1 或者链表中的一个有效索引

进阶：你是否可以使用 O(1) 空间解决此题？

第一种方法就是采用哈希，记录当前点是否出现过，如果出现过，则证明找到了入口点，返回。

#include<unordered_map>
    #include<iostream>
    using namespace std;
    
    // Definition for singly-linked list.
    struct ListNode {
        
        int val;
        ListNode* next;
        ListNode(int x) : val(x), next(nullptr) {
        }
    };
     
    class Solution {
        
    public:
        ListNode* detectCycle(ListNode* head) {
        
            ListNode* cur = head;
            unordered_map<ListNode*, int> mp = unordered_map<ListNode*, int>();
            while (cur != nullptr) {
        
                if (mp.find(cur) != mp.end()) {
        
    				return cur;
    			}
    			mp[cur] = 1;
    			cur = cur->next;
    		}
            return nullptr;
        }
    };

这种方法的空间复杂度是O(n)，时间复杂度因为遍历了一遍数组，因此也是O(n)。

这道题有点数学题的意思，如下：

这里注意，fast指针速度是slow指针的2倍，因此无论如何，fast指针都可以在slow指针走一圈之内追上slow。

![在这里插入图片描述][69b3f93c0ba74e2791c7b0e7d76852b3.png_pic_center_x_16]  
slow走过的距离的2倍 = fast走过的距离：  
 2 × ( a + b ) = a + b + n × ( b + c ) 2\\times(a+b) = a+b+n\\times(b+c) 2×(a\+b)=a\+b\+n×(b\+c)  
假设，fast比slow多走了n圈，n肯定为整数，至少为1.

化简可以得到：

a = ( n − 1 ) b + n c = ( n − 1 ) ( b + c ) + c a=(n-1)b+nc=(n-1)(b+c)+c a=(n−1)b\+nc=(n−1)(b\+c)\+c

从上式可以看出，a的长度等于c加上n个整圈，因此，可以从头再搞一个指针，当它与slow相遇的时候，就是入口点。

具体的思路见：[https://leetcode.cn/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/][https_leetcode.cn_problems_linked-list-cycle-ii_solution_huan-xing-lian-biao-ii-by-leetcode-solution]

代码如下：

class Solution {
        
    public:
        ListNode* detectCycle(ListNode* head) {
        
            ListNode* slow = head;
            ListNode* fast = head;
            ListNode* meet = head;
            while (fast != nullptr) {
        
    			slow = slow->next;
    			if (fast->next == nullptr) {
        
    				return nullptr;
    			}
    			fast = fast->next->next;
                if (fast == slow) {
        
    				while (meet != slow) {
        
    					meet=meet->next;
    					slow=slow->next;
    				}
    				return meet;
    			}
    		}
            return nullptr;
        }
    };

空间复杂度O(1)

时间复杂度O(n)

## 297. 二叉树的序列化与反序列化 ##

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

示例 1：

![在这里插入图片描述][dd54e41521f341cc9f91a4e0ca0bad05.png]

输入：root = \[1,2,3,null,null,4,5\]  
输出：\[1,2,3,null,null,4,5\]

示例 2：

输入：root = \[\]  
输出：\[\]

示例 3：

输入：root = \[1\]  
输出：\[1\]

示例 4：

输入：root = \[1,2\]  
输出：\[1,2\]

提示：

树中结点数在范围  \[ 0 , 1 0 4 \] \[0, 10^4\] \[0,104\] 内  
\-1000 <= Node.val <= 1000

一次通过！

![在这里插入图片描述][59dac29aff3e48b4b2a9a2b3102f0a77.png]

主要思路就是利用前序遍历建树，对空节点编码为 `nullptr`。

#include<string>
    #include<vector>
    
    using namespace std;
    
    // Definition for a binary tree node.
    struct TreeNode {
        
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode(int x) : val(x), left(nullptr), right(NULL) {
        }
    };
    
    class Codec {
        
    private:
        void visitTree(TreeNode* root, string& res) {
        
            if (root == nullptr) {
        
                res += "nullptr";
                res += " ";
                return;
            }
            res += to_string(root->val);
            res += " ";
            visitTree(root->left, res);
            visitTree(root->right, res);
        }
    
        TreeNode* buildTree(vector<string>& vec, int& index) {
        
            if (vec[index] == "nullptr") {
        
                return nullptr;
            }
            else {
        
                TreeNode* node = new TreeNode(atoi(vec[index].c_str()));
                index++;
                node->left = buildTree(vec, index);
                index++;
                node->right = buildTree(vec, index);
                return node;
            }
        }
    
    public:
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
        
            // 用来对数进行编码
            string res = "";
            visitTree(root, res);
            
            return res;
        }
    
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
        
            vector<string> strs;
            string curStr = "";
            for (int i = 0; i < data.size(); i++) {
        
                if (data[i] != ' ') {
        
                    curStr += data[i];
                }
                else {
        
                    strs.push_back(curStr);
                    curStr = "";
                }
            }
    
            // 进行一个递归建树
            int index = 0;
            TreeNode* node = buildTree(strs, index);
            return node;  
        }
    };

[8b846848dab14bdfad87a6e43e960f14.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/bcfe5ebab9b042b7a49d76fa1ed48024.png
[2d828ea2f6224450ae92e2609580b69f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/9c94cc0bd8ab4743af66d736589c099e.png
[f7f05f45cb2b49859f4e47b59942553e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/3a9038a6a4bb493b916602979e69e264.png
[69b3f93c0ba74e2791c7b0e7d76852b3.png_pic_center_x_16]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/b686ff0028184b7f9e412dfc9faa4568.png
[https_leetcode.cn_problems_linked-list-cycle-ii_solution_huan-xing-lian-biao-ii-by-leetcode-solution]: https://leetcode.cn/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/
[dd54e41521f341cc9f91a4e0ca0bad05.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/4b7c9226e1134c0a80925dde90c1f10f.png
[59dac29aff3e48b4b2a9a2b3102f0a77.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/dac9c3b646ea4d369073afb68d90b5af.png