https://leetcode.com/problems/unique-paths-ii/ Unique Paths II Total Accepted: 47668 Total Submissions: 169510 Difficulty: Medium Follow up for “Unique Paths”: Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and empty space is marked as 1 and 0 respectively in the grid. For example, There is one obstacle …
Author Archives: czxttkl
Leetcode 62: Unique Paths
https://leetcode.com/problems/unique-paths/ Unique Paths Total Accepted: 62277 Total Submissions: 185422 Difficulty: Medium A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of …
Leetcode 153: Find Minimum in Rotated Sorted Array
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/ Find Minimum in Rotated Sorted Array Total Accepted: 63536 Total Submissions: 186885 Difficulty: Medium Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). Find the minimum element. You may assume no duplicate exists …
Continue reading “Leetcode 153: Find Minimum in Rotated Sorted Array”
Leetcode 281: Zigzag Iterator
https://leetcode.com/problems/zigzag-iterator/ Zigzag Iterator Total Accepted: 1714 Total Submissions: 4685 Difficulty: Medium 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 173: Binary Search Tree Iterator
https://leetcode.com/problems/binary-search-tree-iterator/ Binary Search Tree Iterator Total Accepted: 29015 Total Submissions: 95018 Difficulty: Medium Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST. Calling next() will return the next smallest number in the BST. Note: next() and hasNext() should run in average O(1) time …
Continue reading “Leetcode 173: Binary Search Tree Iterator”
Leetcode 57: Insert Interval
https://leetcode.com/problems/insert-interval/ Insert Interval Total Accepted: 43188 Total Submissions: 196069 Difficulty: Hard Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times. Example 1:Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9]. Example 2:Given [1,2],[3,5],[6,7],[8,10],[12,16], …
Leetcode 159: Longest Substring with At Most Two Distinct Characters
https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/ Longest Substring with At Most Two Distinct Characters Total Accepted: 4982 Total Submissions: 16108 Difficulty: Hard Given a string, find the length of the longest substring T that contains at most 2 distinct characters. For example, Given s = “eceba”, T is “ece” which its length is 3. Code class Solution(object): def lengthOfLongestSubstringTwoDistinct(self, s): …
Continue reading “Leetcode 159: Longest Substring with At Most Two Distinct Characters”
Leetcode 230: Kth Smallest Element
https://leetcode.com/problems/kth-smallest-element-in-a-bst/ Kth Smallest Element in a BST Total Accepted: 20098 Total Submissions: 63388 Difficulty: Medium Given a binary search tree, write a function kthSmallest to find the kth smallest element in it. Note: You may assume k is always valid, 1 ≤ k ≤ BST’s total elements. Follow up:What if the BST is modified (insert/delete …
Leetcode 56: Merge Interval
https://leetcode.com/problems/merge-intervals/ Merge Intervals Total Accepted: 47467 Total Submissions: 206089 Difficulty: Hard Given a collection of intervals, merge all overlapping intervals. For example,Given [1,3],[2,6],[8,10],[15,18],return [1,6],[8,10],[15,18]. Code # Definition for an interval. # class Interval(object): # def __init__(self, s=0, e=0): # self.start = s # self.end = e class Solution(object): def merge(self, intervals): “”” :type intervals: List[Interval] …
Heapsort basic idea
Just recap the basic idea of heapsort (return an ascending order): first you build max heap right on the original array. You don’t need to create an additional O(N) space. Instead, just make sure child node index i is always less than parent node (i – 1)/2 by necessary swaps between index i and index (i-1)/2. …