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], …
Author Archives: czxttkl
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. …
Leetcode 228: Summary Ranges
https://leetcode.com/problems/summary-ranges/ Summary Ranges Total Accepted: 22806 Total Submissions: 114600 Difficulty: Easy Given a sorted integer array without duplicates, return the summary of its ranges. For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"]. Code class Solution(object): def summaryRanges(self, nums): “”” :type nums: List[int] :rtype: List[str] “”” res = [] s = “” for i, v in enumerate(nums): if …
Leetcode 288: Unique Word Abbreviation
https://leetcode.com/problems/unique-word-abbreviation/ Unique Word Abbreviation Total Accepted: 984 Total Submissions: 5829 Difficulty: Easy An abbreviation of a word follows the form <first letter><number><last letter>. Below are some examples of word abbreviations: a) it –> it (no abbreviation) 1 b) d|o|g –> d1g 1 1 1 1—5—-0—-5–8 c) i|nternationalizatio|n –> i18n 1 1—5—-0 d) l|ocalizatio|n –> l10n …
Leetcode 20: Valid Parenthesis
https://leetcode.com/problems/valid-parentheses/ Valid Parentheses Total Accepted: 72044 Total Submissions: 267703 Difficulty: Easy Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not. My code: …
Leetcode 140: Word Break II
https://leetcode.com/problems/word-break-ii/ Word Break II Total Accepted: 41843 Total Submissions: 232195 Difficulty: Hard Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences. For example, given s = "catsanddog", dict = ["cat", "cats", "and", "sand", …
Leetcode 139: WordBreak
https://leetcode.com/problems/word-break/ Word Break Total Accepted: 65299 Total Submissions: 278950 Difficulty: Medium Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words. For example, givens = "leetcode",dict = ["leet", "code"]. Return true because "leetcode" can be segmented as "leet code". …