Claim In this post, I am using the same notation as in the video below and the wiki page (https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm) Our problem is given a matrix costs in which costs[i][j] is the traveling cost going from node i to node j, we are asked to return the minimum cost for traveling from node 0 and visit …
Continue reading “Solve Travelling Salesman Problem using DP”
https://leetcode.com/problems/binary-tree-upside-down/ Binary Tree Upside Down Total Accepted: 4861 Total Submissions: 13934 Difficulty: Medium Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes …
https://leetcode.com/problems/binary-tree-postorder-traversal/ Binary Tree Postorder Traversal Total Accepted: 76404 Total Submissions: 229965 Difficulty: Hard Given a binary tree, return the postorder traversal of its nodes’ values. For example:Given binary tree {1,#,2,3}, 1 \ 2 / 3 return [3,2,1]. Note: Recursive solution is trivial, could you do it iteratively? Idea: This problem is similar to a …
Continue reading “Leetcode 145: Binary Tree Postorder Traversal”
https://leetcode.com/discuss/23326/very-simple-iterative-python-solution Binary Tree Preorder Traversal Total Accepted: 89130 Total Submissions: 240451 Difficulty: Medium Given a binary tree, return the preorder traversal of its nodes’ values. For example:Given binary tree {1,#,2,3}, 1 \ 2 / 3 return [1,2,3]. Note: Recursive solution is trivial, could you do it iteratively? Code # Definition for a binary tree …
Continue reading “Leetcode 144: Binary Tree Preorder Traversal”
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/ Lowest Common Ancestor of a Binary Search Tree Total Accepted: 30832 Total Submissions: 81197 Difficulty: Easy Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and …
Continue reading “Leetcode 235: Lowest Common Ancestor of a Binary Search Tree (BST)”
https://leetcode.com/problems/shortest-word-distance-iii/ Shortest Word Distance III Total Accepted: 1824 Total Submissions: 4282 Difficulty: Medium This is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2. Given a list of words and two words word1 and word2, return the shortest distance between these two words in the …
https://leetcode.com/problems/shortest-word-distance-ii/ Shortest Word Distance II Total Accepted: 1811 Total Submissions: 5300 Difficulty: Medium This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it? Design a class which …
https://leetcode.com/problems/shortest-word-distance/ Shortest Word Distance Total Accepted: 2492 Total Submissions: 5946 Difficulty: Easy Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list. For example,Assume that words = ["practice", "makes", "perfect", "coding", "makes"]. Given word1 = “coding”, word2 = “practice”, return 3.Given word1 = …
https://leetcode.com/problems/different-ways-to-add-parentheses/ Different Ways to Add Parentheses Total Accepted: 9627 Total Submissions: 34073 Difficulty: Medium Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +,- and *. Example 1 Input: "2-1-1". ((2-1)-1) = 0 (2-(1-1)) = 2 Output: …
Continue reading “Leetcode 241: Different Ways to Add Parenthesis”
https://leetcode.com/problems/generate-parentheses/ Generate Parentheses Total Accepted: 62423 Total Submissions: 186597 Difficulty: Medium Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: "((()))", "(()())", "(())()", "()(())", "()()()" Code class Solution(object): def generateParenthesis(self, n): “”” :type n: int :rtype: List[str] “”” res …