我太菜了

喜欢写Hello World的未来程序员.

127.WordLadder

你快乐吗？

127. Word Ladder C++，bfs，差不多200ms。思路如下： 首先用unordered_set构造单词列表，因为unordered_set底层用hash实现，搜索速度比vector快得多，一个O(1)，一个O(n)； 用unordered_map作为记录层数的表，beginWord肯定就是第一层； 首先要确定endWord在列表里，不然就返回0； ...

Posted by bbkgl on September 26, 2019

120.Triangle

你快乐吗？

120. Triangle C++，动态规划。其实就是经典的dp题数塔问题，从下到上找最优解。 从下底层到最顶层，走到当前点的最短路劲都只和左下邻点以及右下邻点有关，所以得到本题的状态转移方程就是： dp[i][j] = dp[i][j] + min(dp[i+1][j], dp[i+1][j+1]) 代码如下： class Solution { public: int ...

Posted by bbkgl on September 26, 2019

117.PopulatingNextRightPointersinEachNodeII

你快乐吗？

117. Populating Next Right Pointers in Each Node II C++。应该是更新测点了，使得时间变长了。。。 讲一下思路。 dfs，深搜，和上一题的区别是这不是完全二叉树了，所以要注意几个点： 可能有右子树，但没有左子树； 要用node->next指向堂兄弟时，可能堂兄弟不是左子结点，而可能是右子结点； 需要先找到右边的堂...

Posted by bbkgl on September 26, 2019

116.PopulatingNextRightPointersinEachNode

你快乐吗？

116. Populating Next Right Pointers in Each Node C++，dfs深搜解决。 题意看了好久才看懂，其实就是将每一层的点都连接起来。每个结点的next指针都指向右边的结点，这样分两种情况： 如果右边结点是亲兄弟结点，则在遍历到父节点的时候就root->left->next = root->right;； 如果右边结...

Posted by bbkgl on September 26, 2019

114.FlattenBinaryTreetoLinkedList

你快乐吗？

114. Flatten Binary Tree to Linked List C++，数据量不大的情况下，时间没什么意义，看运气都。。。复杂度O(n)，思路如下： 题目的意思是让把前序遍历的结果串成链表，要求不创建新结点，即原地串成链表。 遍历每个节点的时候，完成三个操作： 将右子树入栈（全局栈） 将左子树的遍历结果赋值给右子树指针 返回当前节点 这时候就有个...

Posted by bbkgl on September 26, 2019

113.PathSumII

你快乐吗？

113. Path Sum II C++。dfs，回溯，不剪枝。没有说是正整数就不要剪枝了。。。 typedef TreeNode* TNP; class Solution { public: vector<vector<int>> pathSum(TreeNode* root, int sum) { vector<vector...

Posted by bbkgl on September 26, 2019

109.ConvertSortedListtoBinarySearchTree

你快乐吗？

109. Convert Sorted List to Binary Search Tree C++，代码很简短。。。本来可以真的去构造AVL树，但是给的序列已经是有序的了，就没必要了。不然AVL写下来至少也得七八十行。。。 思路就是利用分治的思想，将中间结点作为分割点，分成左子树和右子树。 首先链表元素可以先用vector存一下，因为后面如果用链表再去找中间结点的话，很影响效率...

Posted by bbkgl on September 26, 2019

106.ConstructBinaryTreefromInorderandPostorderTraversal

你快乐吗？

106. Construct Binary Tree from Inorder and Postorder Traversal 106. Construct Binary Tree from Inorder and Postorder Traversal 以下思路参考柳婼文章：已知后序与中序输出前序（先序） C++。首先要知道一个结论，前序/后序+中序序列可以唯一确定一棵...

Posted by bbkgl on September 26, 2019

105.ConstructBinaryTreefromPreorderandInorderTraversal

你快乐吗？

105. Construct Binary Tree from Preorder and Inorder Traversal 105. Construct Binary Tree from Preorder and Inorder Traversal 这道题剑指offer已经做过了，见重建二叉树 直接复制思路： C++。首先要知道一个结论，前序/后序+中序序列可以唯一确定...

Posted by bbkgl on September 26, 2019

103.BinaryTreeZigzagLevelOrderTraversal

你快乐吗？

103. Binary Tree Zigzag Level Order Traversal 103. Binary Tree Zigzag Level Order Traversal 102题解–102. Binary Tree Level Order Traversal 上一题递归做的，这题也可以递归做，同样也是线性复杂度，但是递归的效率肯定比较低，所以这次也提供用队...

Posted by bbkgl on September 26, 2019

FEATURED TAGS
Blog leetcode C++ 剑指offer http Raft Linux Hadoop 设计模式 CV 链表 动态规划 图 拓扑排序 快排 二叉树 leveldb 数学 数组 二分 dfs profile hash表 字符串 贪心 01背包 最小堆 单调栈 luajit 计算机网络 操作系统 共享内存 linux 原地哈希 双指针 滑动窗口 UE4 编译原理
ABOUT ME

写过Hello World, 下过矿。

✉️ zoujiakun@zju.edu.cn

FRIENDS