菜鸡的博客 | WTCL

142. Linked List Cycle II

你快乐吗？

142. Linked List Cycle II C++，链表，数学题。链表的操作我们就不说了，这道题其实是一道数学题。解法如下：首先分别定义两个指针，一个一次走两步，一个走一步，分别为fast，slow，记录下快指针经过的结点数（不包括头结点）为lf，慢指针为ls，必有lf = 2ls；假设有环链表的长度为l，环的长度为c，从头结点到环入口的距离为a；一个...

Posted by bbkgl on September 26, 2019

139. Word Break

你快乐吗？

139. Word Break C++，动态规划。dfs也是可以的，但是一定得存储之前搜索的结果，本质还是动态规划。其实就是三个步骤：在字符串s中从前往后找到第一个单词，记录下这个单词已经完整找到了，反应在代码中就是dp[i] = true；继续找第二个单词，找到第二个单词并且确定之前已经有完整的单词；重复上述过程，直到从头到尾找出s中所有单词。返回true...

Posted by bbkgl on September 26, 2019

138. Copy List with Random Pointer

你快乐吗？

138. Copy List with Random Pointer C++，hash，链表。看到的都是没用哈希表的版本，我就写一个用了好几个表的版本。如何在深拷贝的情况下，记录random指针指向的地址其实是一件难事。。。深拷贝要求重新生成结点，而不是单纯地复制指针 “原表中每个结点的random指向”，这个信息复制到新表需要通过两个映射第i个节...

Posted by bbkgl on September 26, 2019

137.SingleNumberII

你快乐吗？

137. Single Number II C++，位运算。讲一个更容易理解的解法吧，复杂度是32 * O(n)，也是符合题目要求的。热评大佬的解法我暂时没看懂。只要是在int范围内，每个整数都是用32位二进制表示的。如果我们将nums中所有数都转成32位的二进制，并用一个size为32的数组bits表示每个位中1的个数，就能发现一件很巧妙的事情。有一些位的值，是3的倍数 ...

Posted by bbkgl on September 26, 2019

136.Single Number

你快乐吗？

136. Single Number C++，位运算，按位异或。 int a = 0, b = 5; a = a ^ b; // a = 5 a = a ^ b; // a = 0 根据上述规律，即一个数b与初始为0的数a按位异或两次，a就会变成0。同理，本题中数组nums中所有出现两次的数与初始为0的数a按位异或两次，a都会变成0。所以最后a就会变成只与a按位异或一次的...

Posted by bbkgl on September 26, 2019

134.Gas Station

你快乐吗？

134. Gas Station C++，模拟题大概？？？参考热评大佬，然后说下自己的理解和思路。有解的话要满足两个条件：所有站点的油量和要大于跑一整圈的耗油量的和绕圈的途中，在任何一个站点加完油后，都要能到达下一个站点假设起始站点为0，一旦遇到在k站无法到达k+1站的情况，则说明起始站一定不在k及k之前，原因如下（假设油箱中剩余油量为rest）：首先确...

Posted by bbkgl on September 26, 2019

133. Clone Graph

你快乐吗？

133. Clone Graph C++，dfs，深拷贝。。。其实就是深拷贝的一个实现，深拷贝就是对于所有的指针成员，不能仅仅是赋值，还要重新分配空间。深拷贝反应在本题中就是，所有的结点需要重新new出来，而不是直接赋值。整体的思路依然是dfs，跑遍原图中每个结点，然后根据原结点生成新结点。要注意的地方就是，因为图存在环，所以要标记访问过的结点，避免重复形成死循环...

Posted by bbkgl on September 26, 2019

131.PalindromePartitioning

你快乐吗？

131. Palindrome Partitioning C++，dfs，回溯剪枝。这种从前往后都是同一个规律的题，就要想到递归了。对于字符串S的当前子串[left, right]，要找到其中所有的回文串组合，要完成如下工作：定义变量i从left到right进行分割，得到子串S[left, i]；如果子串S[left, i]是...

Posted by bbkgl on September 26, 2019

130.SurroundedRegions

你快乐吗？

130. Surrounded Regions C++，dfs，反向。题意就是找出被‘X’完全包围的‘O’的区域，填充为‘X’。解决思路就是反向找出没有完全被‘X’完全包围的‘O’的区域，标记一下，然后没有标记的就是要被填充的。思路就是绕着矩阵的最外圈转一圈，碰到‘O’，说明这里可以往里进行深搜；将深搜经过的所有‘O’都标记成‘Y’；外圈深搜完...

Posted by bbkgl on September 26, 2019

129.SumRoottoLeafNumbers

你快乐吗？

129. Sum Root to Leaf Numbers C++, dfs。 void dfs(TreeNode *root, string temp, int &ans)；看函数参数就知道了，对于当前结点，如果是叶节点，就把和加入ans。如果不是叶节点，就带着当前结点的数字往左右儿子继续递归。代码如下： class Solution { public: ...

Posted by bbkgl on September 26, 2019

我太菜了

142. Linked List Cycle II

你快乐吗？

139. Word Break

你快乐吗？

138. Copy List with Random Pointer

你快乐吗？

137.SingleNumberII

你快乐吗？

136.Single Number

你快乐吗？

134.Gas Station

你快乐吗？

133. Clone Graph

你快乐吗？

131.PalindromePartitioning

你快乐吗？

130.SurroundedRegions

你快乐吗？

129.SumRoottoLeafNumbers

你快乐吗？

FEATURED TAGS

ABOUT ME

FRIENDS