文章 217
评论 6
浏览 143928
Trie - 212. Word Search II

Trie - 212. Word Search II

212. Word Search II Given a 2D board and a list of words from the dictionary, find all words in the board. Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.   Example: Input: board = [ ['o','a','a','n'], ['e','t','a','e'], ['i','h','k','r'], ['i','f','l','v'] ] words = ["oath","pea","eat","rain"] Output: ["eat","oath"] Not....

Trie - 211. Add and Search Word - Data structure design

Trie - 211. Add and Search Word - Data structure design

211. Add and Search Word - Data structure design Design a data structure that supports the following two operations: void addWord(word) bool search(word) search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter. Example: addWord("bad") addWord("dad") addWord("mad") search("pad") -> false search("bad") -> true search(".ad") -> true search("b..") -> true Note: You ma....

Trie - 208. Implement Trie (Prefix Tree)

Trie - 208. Implement Trie (Prefix Tree)

208. Implement Trie (Prefix Tree) Implement a trie with insert, search, and startsWith methods. Example: Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // returns true trie.search("app"); // returns false trie.startsWith("app"); // returns true trie.insert("app"); trie.search("app"); // returns true Note: You may assume that all inputs are consist of lowercase letters a-z. All inputs are guaranteed to be non-empty strings. 思路: 题目意思很明确,就是实现一下....

Tree - 337. House Robber III

Tree - 337. House Robber III

337. House Robber III The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night. Determine the maximum amount of money the thief can rob tonight without alerting the p....

Tree - 250. Count Univalue Subtrees

Tree - 250. Count Univalue Subtrees

250. Count Univalue Subtrees Given a binary tree, count the number of uni-value subtrees. A Uni-value subtree means all nodes of the subtree have the same value. Example Example1 Input: root = {5,1,5,5,5,#,5} Output: 4 Explanation: 5 / \ 1 5 / \ \ 5 5 5 Example2 Input: root = {1,3,2,4,5,#,6} Output: 3 Explanation: 1 / \ 3 2 / \ \ 4 5 6 思路: 题目意思是找出一棵树中以树中某节点为根节点的子树中所有元素都相同,很明显,叶子结点肯定是一个uni的子树,回到问题本身,判断以一个节点为根节点的子树是否为uni-value,只需要满足左子树是uni-value,右子树是uni-value,并且判断当前节点和左右孩子节点值,就能求解。所以,递归后序遍....

Tree - 124. Binary Tree Maximum Path Sum

Tree - 124. Binary Tree Maximum Path Sum

124. Binary Tree Maximum Path Sum Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root. Example 1: Input: [1,2,3] 1 / \ 2 3 Output: 6 Example 2: Input: [-10,9,20,null,null,15,7]   -10    / \   9  20     / &nb....

Tree - 110. Balanced Binary Tree

Tree - 110. Balanced Binary Tree

110. Balanced Binary Tree Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as: a binary tree in which the depth of the two subtrees of every node never differ by more than 1. Example 1: Given the following tree [3,9,20,null,null,15,7]: 3 / \ 9 20 / \ 15 7 Return true. Example 2: Given the following tree [1,2,2,3,3,null,null,4,4]: 1 / \ 2 2 / \ 3 3 / \ 4 4 Return false. 思路: 题目意思是判断一棵二叉树是否是平衡二叉树。而平衡二....

Tree - 104. Maximum Depth of Binary Tree

Tree - 104. Maximum Depth of Binary Tree

104. Maximum Depth of Binary Tree Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Note: A leaf is a node with no children. Example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its depth = 3. 思路: 一棵空树的深度为零,也就是可以看做叶子节点的孩子节点的深度为零,叶子节点的深度为1,而一个树的深度和高度相同,所以求一个树的深度其实就是左右子树的深度的最大值加一。递归求解就可以。 代码: go: /** * Definition for a binary tree node. * type T....

Tree - 298. Binary Tree Longest Consecutive Sequence

Tree - 298. Binary Tree Longest Consecutive Sequence

298 . Binary Tree Longest Consecutive Sequence Description Given a binary tree, find the length of the longest consecutive sequence path. The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse). Example 1: Input: 1 \ 3 / \ 2 4 \ 5 Output:3 Explanation: Longest consecutive sequence path is 3-4-5, so return 3. 思路: 找出根到叶子节点的路径中的最长递增序列,做法就是由根节点向叶....

Tree - 111. Minimum Depth of Binary Tree

Tree - 111. Minimum Depth of Binary Tree

111. Minimum Depth of Binary Tree Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. Note: A leaf is a node with no children. Example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its minimum depth = 2. 思路: 求二叉树的最小深度,可以采用深度优先搜索递归求解。 代码: go: /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right ....

Tree - 129. Sum Root to Leaf Numbers

Tree - 129. Sum Root to Leaf Numbers

129. Sum Root to Leaf Numbers Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. An example is the root-to-leaf path 1->2->3 which represents the number 123. Find the total sum of all root-to-leaf numbers. Note: A leaf is a node with no children. Example: Input: [1,2,3] 1 / \ 2 3 Output: 25 Explanation: The root-to-leaf path 1->2 represents the number 12. The root-to-leaf path 1->3 represents the nu....

Tree - 113. Path Sum II

Tree - 113. Path Sum II

113. Path Sum II Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum. Note: A leaf is a node with no children. Example: Given the below binary tree and sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 Return: [ [5,4,11,2], [5,8,4,5] ] 思路: 题目意思是求出所有根节点到叶子结点路径和为sum的结果。递归求解,找到叶子节点比较sum就可以 代码: go: /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func pathSum(roo....

Tree - 112. Path Sum

Tree - 112. Path Sum

112. Path Sum Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Note: A leaf is a node with no children. Example: Given the below binary tree and sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1 return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22. 思路: 题目意思是问根节点叶子节点的路径有没有求和之后等于sum,很简单的题目,和257题类似,递归求解。 代码: go: /** * Definition for a binary tr....

Tree - 257. Binary Tree Paths

Tree - 257. Binary Tree Paths

257. Binary Tree Paths Given a binary tree, return all root-to-leaf paths. Note: A leaf is a node with no children. Example: Input: 1 / \ 2 3 \ 5 Output: ["1->2->5", "1->3"] Explanation: All root-to-leaf paths are: 1->2->5, 1->3 思路: 题目意思是从root节点走到叶子节点一共有多少路径,采用递归求解,和先序遍历类似,找到叶子节点就把路径保存下来。 代码: go: /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func binaryTreePaths(root *TreeNode) []string { var r....

Tree - 226. Invert Binary Tree

Tree - 226. Invert Binary Tree

226. Invert Binary Tree Invert a binary tree. Example: Input: 4 / \ 2 7 / \ / \ 1 3 6 9 Output: 4 / \ 7 2 / \ / \ 9 6 3 1 思路: 递归求解翻转每个不为nil的节点 代码: go: /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func invertTree(root *TreeNode) *TreeNode { if root == nil { return root } root.Left, root.Right = root.Right, root.Left invertTree(root.Left) invertTree(root.Right) return root }

Tree - 101. Symmetric Tree

Tree - 101. Symmetric Tree

101. Symmetric Tree Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree [1,2,2,3,4,4,3] is symmetric: 1 / \ 2 2 / \ / \ 3 4 4 3 But the following [1,2,2,null,3,null,3] is not: 1 / \ 2 2 \ \ 3 3 Note: Bonus points if you could solve it both recursively and iteratively. 思路: 题目意思是判断一棵树是不是对称的,可以用迭代或者递归来做 代码: go: /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *Tr....

Tree - 100. Same Tree

Tree - 100. Same Tree

100. Same Tree Given two binary trees, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical and the nodes have the same value. Example 1: Input: 1 1 / \ / \ 2 3 2 3 [1,2,3], [1,2,3] Output: true 思路: 题目很简单,判断两个树是否相同,只要随便使用一种方式遍历一次树就可以,这里使用先序遍历来做。 代码: go: /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ //recursive func isSameTree(p *TreeNode, q....

Tree - 102. Binary Tree Level Order Traversal

Tree - 102. Binary Tree Level Order Traversal

102. Binary Tree Level Order Traversal Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level). For example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its level order traversal as: [ [3], [9,20], [15,7] ] 思路: 层序遍历二叉树,这一题和637题很像,637是求每一层的平均值,这一题只让打印出来,可以用bfs做,也可以使用dfs做,这里用bfs做,有递归写法和非递归写法,非递归写法使用了队列在存储下一层要遍历的节点。 代码: go: /** * Definition for a binary tree node. * type TreeNode struct {....

Dynamic Programming - 91. Decode Ways

Dynamic Programming - 91. Decode Ways

91. Decode Ways A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given a non-empty string containing only digits, determine the total number of ways to decode it. Example 1: Input: “12” Output: 2 Explanation: It could be decoded as “AB” (1 2) or “L” (12). Example 2: Input: “226” Output: 3 Explanation: It could be decoded as “BZ” (2 26), “VF” (22 6), or “BBF” (2 2 6). 思路:....

Dynamic Programming - 213. House Robber II

Dynamic Programming - 213. House Robber II

213. House Robber II You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given a list of non-negative integers representing the amount of mo....

Nothing just happens, it's all part of a plan.