LeetCode - Michael's Blog

Binary Tree Preorder Traversal

144. Binary Tree Preorder Traversal [https://leetcode.com/problems/binary-tree-preorder-traversal/?tab=Description] 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? class

LeetCode

Kth Smallest Element in a Sorted Matrix

378. Kth Smallest Element in a Sorted Matrix [https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/description/] Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix. Note that it is the kth smallest element in the

LeetCode

Binary Tree Inorder Traversal

94. Binary Tree Inorder Traversal [http://www.lintcode.com/en/problem/binary-tree-inorder-traversal] Given a binary tree, return the inorder traversal of its nodes' values. For example: Given binary tree [1,null,2,3], 1 \ 2 / 3 return [1,3,2]. Note: Recursive solution is trivial, could you do it iteratively?

LeetCode

Minimum Window Substring

76. Minimum Window Substring [https://leetcode.com/problems/minimum-window-substring/] LintCode-32.Minimum Window Substring [http://www.lintcode.com/en/problem/minimum-window-substring/] Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). For example, S = "ADOBECODEBANC"

LeetCode

First Bad Version

278. First Bad Version [https://leetcode.com/problems/first-bad-version/] You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a

LeetCode

Implement Trie (Prefix Tree)

208. Implement Trie (Prefix Tree) [https://leetcode.com/problems/implement-trie-prefix-tree/] LintCode-442.Implement Trie [http://www.lintcode.com/en/problem/implement-trie/] Implement a trie with insert, search, and startsWith methods. Note: You may assume that all inputs are consist of lowercase letters a-z. class TrieNode { private var children: [TrieNode?] = [] public var

LeetCode

Word Search

79. Word Search [https://leetcode.com/problems/word-search/] LintCode-123.Word Search [http://www.lintcode.com/en/problem/word-search/] Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally

LeetCode

Basic Calculator

224. Basic Calculator [https://leetcode.com/problems/basic-calculator/] Implement a basic calculator to evaluate a simple expression string. The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces . You may assume that the given expression is always valid. Some examples:

LeetCode

Brick Wall

554. Brick Wall [https://leetcode.com/problems/brick-wall/] There is a brick wall in front of you. The wall is rectangular and has several rows of bricks. The bricks have the same height but different width. You want to draw a vertical line from the top to the bottom and

LeetCode

Sort Colors

75. Sort Colors [https://leetcode.com/problems/sort-colors/] LintCode-148.Sort Colors [http://www.lintcode.com/en/problem/sort-colors/] Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

LeetCode

Add and Search Word

211. Add and Search Word - Data structure design [https://leetcode.com/problems/add-and-search-word-data-structure-design/] LintCode-473.Add and Search Word [http://www.lintcode.com/en/problem/add-and-search-word/] Design a data structure that supports the following two operations: void addWord(word) bool search(word) search(word) can search a literal word or

LeetCode

Missing Ranges

163. Missing Ranges [https://leetcode.com/problems/missing-ranges/] Given a sorted integer array where the range of elements are in the inclusive range [lower, upper], return its missing ranges. For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99, return ["2", "4->49", "51->74", "76->99"

LeetCode

Moving Average from Data Stream

346. Moving Average from Data Stream [https://leetcode.com/problems/moving-average-from-data-stream/] Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window. For example, MovingAverage m = new MovingAverage(3); m.next(1) = 1 m.next(10) = (1 + 10) / 2 m.next(

LeetCode

Strobogrammatic Number

246. Strobogrammatic Number [https://leetcode.com/problems/strobogrammatic-number/description/] A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Write a function to determine if a number is strobogrammatic. The number is represented as a string. For example, the numbers "69", "88"

LeetCode

Zigzag Iterator

281. Zigzag Iterator [https://leetcode.com/problems/zigzag-iterator/] Given two 1d vectors, implement an iterator to return their elements alternately. For example, given two 1d vectors: v1 = [1, 2] v2 = [3, 4, 5, 6] By calling next repeatedly until hasNext returns false, the order of elements returned by next should

LeetCode

Plus One

66. Plus One [https://leetcode.com/problems/plus-one/] Given a non-negative integer represented as a non-empty array of digits, plus one to the integer. You may assume the integer do not contain any leading zero, except the number 0 itself. The digits are stored such that the most significant digit

LeetCode

Decode String

394. Decode String [https://leetcode.com/problems/decode-string/description/] Given an encoded string, return it's decoded string. The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer. You may

LeetCode

License Key Formatting

482. License Key Formatting [https://leetcode.com/problems/license-key-formatting/] Now you are given a string S, which represents a software license key which we would like to format. The string S is composed of alphanumerical characters and dashes. The dashes split the alphanumerical characters within the string into groups. (i.

LeetCode

Strobogrammatic Number II

247. Strobogrammatic Number II [https://leetcode.com/problems/strobogrammatic-number-ii] A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Find all strobogrammatic numbers that are of length = n. For example, Given n = 2, return ["11","69","88","96"]. n = 0: none n

LeetCode

Intersection of Two Linked Lists

160. Intersection of Two Linked Lists [https://leetcode.com/problems/intersection-of-two-linked-lists/] LintCode-380.Intersection of Two Linked Lists [http://www.lintcode.com/en/problem/intersection-of-two-linked-lists/] Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists: A: a1

LeetCode

Combination Sum IV

377. Combination Sum IV [https://leetcode.com/problems/combination-sum-iv/] Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target. Example: nums = [1, 2, 3] target = 4 The possible combination ways are: (1, 1, 1, 1)

LeetCode

Combination Sum III

216. Combination Sum III [https://leetcode.com/problems/combination-sum-iii/] Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers. Example 1: Input: k = 3, n

LeetCode

Rearrange String k Distance Apart

358. Rearrange String k Distance Apart [https://leetcode.com/problems/rearrange-string-k-distance-apart/] Given a non-empty string s and an integer k, rearrange the string such that the same characters are at least distance k from each other. All input strings are given in lowercase letters. If it is not possible to

LeetCode

Split Array Largest Sum

410. Split Array Largest Sum [https://leetcode.com/problems/split-array-largest-sum/] Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays. Note: If n is the length

LeetCode

Graph Valid Tree

261. Graph Valid Tree [https://leetcode.com/problems/graph-valid-tree] Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree. For example: Given n = 5