菜鸡的博客 | WTCL

94.BinaryTreeInorderTraversal

你快乐吗？

94. Binary Tree Inorder Traversal C++，二叉树的中序遍历，这个没什么好说的2333。 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * T...

Posted by bbkgl on September 26, 2019

93.RestoreIPAddresses

你快乐吗？

93. Restore IP Addresses dfs，回溯+剪枝。。。就我觉得中等题做到后面，完成一道题花的时间越来越长吗？下面说下思路用left和right变量控制ip地址每段的范围，其中： left作为每段起始点，且在每次函数调用中向后递进，即dfs(ans, s, depth + 1, right + 1, temp + ts + ".");； ...

Posted by bbkgl on September 26, 2019

92.ReverseLinkedListII

你快乐吗？

92. Reverse Linked List II 做没有头结点的链表题，先造个头结点贼方便，屡试不爽。 class Solution { public: ListNode* reverseBetween(ListNode* head, int m, int n) { if (m == n) return head; ListNode *p =...

Posted by bbkgl on September 26, 2019

91.Decode_Ways

你快乐吗？

91. Decode Ways 题目整体思路就是dp，就是找当前位编码数和前一位编码数的关系以及前两位编码数的关系。要分好几种情况来分析：如果当前位为0：如果前一位不是1或2，则这个0无法和任何数组成字母，代表整个串无法构成编码如果前一位是1或者2，则说明前一位和当前位能组成字母，这时候能构成的编码数目是和前前位相同的，即：dp[i] = d...

Posted by bbkgl on September 26, 2019

90.SubsetsII

你快乐吗？

90. Subsets II 这种数据量不大的情况下，时间多少纯粹碰运气，所以看时间意义不大。这道题相比上一道题多了去重的步骤，所以在看懂上一道题的情况下，这道题就是如何理解去重了。上一道题的解题介绍（78. Subsets）,下面讲解思路。以下思路基于元素列已经被排序。为什么会出现重复子列？该解法生成子列是在之前已经生成的所有子列上依次加上新的...

Posted by bbkgl on September 26, 2019

89.格雷编码

你快乐吗？

89. 格雷编码就感觉这道题不是用一般的方法来做，果然是位运算（异或）。公式：G(i) = i ^ (i/2); class Solution { public: vector<int> grayCode(int n) { vector<int> ans; for (int i = 0; i < (1 <<...

Posted by bbkgl on September 26, 2019

86.分隔链表

你快乐吗？

86. 分隔链表其实这个题多少ms已经没关系了，因为大家都是O(n)的时间复杂度。当然空间复杂度得是O(1)才更好，也就是不能生成新的链表作为答案，就用原链表返回。 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * Lis...

Posted by bbkgl on September 26, 2019

82. Remove Duplicates from Sorted List II

你快乐吗？

82. Remove Duplicates from Sorted List II 已经是线性复杂度了，不知道为什么还是%16，可能和运行有关吧。评论里很多方法其实跑了不止一趟的，下面介绍只跑一趟的方法。思路就是：指针right向前移动，每移动一次都和left指针对比，看两个值是否一样，如果一样，则计数加一，表示存在一个重复；如果两个值不一样，将left移动到right一样的位置，舍弃...

Posted by bbkgl on September 26, 2019

81. Search in Rotated Sorted Array II

你快乐吗？

81. Search in Rotated Sorted Array II 参考大佬题解，如果大家有兴趣的话可以看看，博客里说的很清楚，放上链接，渣渣我就不做过多解释了。以下是大佬博文链接：Search in Rotated Sorted Array II – LeetCode 最后放上渣渣我写的代码，供参考： class Solution { public: bool sea...

Posted by bbkgl on September 26, 2019

80.Remove Duplicates from Sorted Array II

你快乐吗？

80.Remove Duplicates from Sorted Array II 98.65%，参考了评论区大佬的解法，在这里给解释一下各个步骤和变量的含义： len表示的是删除重复元素后新序列的长度，同时也表示新元素进入新序列的索引； i就是循环变量，用于遍历整个旧序列； if (len < 2) nums[len++] = nums[i];的意思就是如果新序...

Posted by bbkgl on September 26, 2019

我太菜了

94.BinaryTreeInorderTraversal

你快乐吗？

93.RestoreIPAddresses

你快乐吗？

92.ReverseLinkedListII

你快乐吗？

91.Decode_Ways

你快乐吗？

90.SubsetsII

你快乐吗？

89.格雷编码

你快乐吗？

86.分隔链表

你快乐吗？

82. Remove Duplicates from Sorted List II

你快乐吗？

81. Search in Rotated Sorted Array II

你快乐吗？

80.Remove Duplicates from Sorted Array II

你快乐吗？

FEATURED TAGS

ABOUT ME

FRIENDS