I wrote a post before talking about sum-product algorithm: http://maider.blog.sohu.com/307377602.html At that time, I had fresh memory on how graph model works. However, today when I read the post again, I am lost again. Therefore, I want to recap the basic motivations of graph models. This post can serve as an intro to the old post. …
Monthly Archives: October 2015
Use PDB to check variables before crashes
1. Use `python -i your_script.py` to execute your program with interactive mode. This means, after your program finishes executing, or your program crashes in the midway, you will enter a python shell. 2. Suppose your script has a bug so that you enter the python shell after it crashes. Now you can play with pdb …
Continue reading “Use PDB to check variables before crashes”
Leetcode 209: Minimum Size Subarray Sum
https://leetcode.com/problems/minimum-size-subarray-sum/ Minimum Size Subarray Sum Total Accepted: 20591 Total Submissions: 84896 Difficulty: Medium Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn’t one, return 0 instead. For example, given the array [2,3,1,2,4,3] and s = 7,the …
Leetcode 208: Implement Trie (Prefix Tree)
https://leetcode.com/problems/implement-trie-prefix-tree/ Implement Trie (Prefix Tree) Total Accepted: 18703 Total Submissions: 75061 Difficulty: Medium Implement a trie with insert, search, and startsWith methods. Note:You may assume that all inputs are consist of lowercase letters a-z. Code class TrieNode(object): def __init__(self): “”” Initialize your data structure here. “”” self.nodes = dict() self.is_word = False class Trie(object): …
Continue reading “Leetcode 208: Implement Trie (Prefix Tree)”
Leetcode 220: Contains Duplicate III
https://leetcode.com/problems/contains-duplicate-iii/ Contains Duplicate III Total Accepted: 15083 Total Submissions: 90517 Difficulty: Medium Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k. Code …
Leetcode 261: Graph Valid Tree
https://leetcode.com/problems/graph-valid-tree/ Graph Valid Tree Total Accepted: 2794 Total Submissions: 10778 Difficulty: Medium 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 and …
Leetcode 99: Validate Binary Search Tree
https://leetcode.com/problems/validate-binary-search-tree/ Validate Binary Search Tree Total Accepted: 65929 Total Submissions: 326515 Difficulty: Medium Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node’s key. The right subtree of a …
leetcode 61: Rotate List
https://leetcode.com/problems/rotate-list/ Rotate List Total Accepted: 50875 Total Submissions: 233034 Difficulty: Medium Given a list, rotate the list to the right by k places, where k is non-negative. For example:Given 1->2->3->4->5->NULL and k = 2,return 4->5->1->2->3->NULL. Code # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next …
Leetcode 26: Remove Duplicates from Sorted Array
https://leetcode.com/problems/remove-duplicates-from-sorted-array/ Remove Duplicates from Sorted Array Total Accepted: 87967 Total Submissions: 280545 Difficulty: Easy Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this in place with constant memory. For example,Given input …
Continue reading “Leetcode 26: Remove Duplicates from Sorted Array”
Leetcode 53: Maximum Subarray
https://leetcode.com/problems/maximum-subarray/ Maximum Subarray Total Accepted: 79595 Total Submissions: 227725 Difficulty: Medium Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array [−2,1,−3,4,−1,2,1,−5,4],the contiguous subarray [4,−1,2,1] has the largest sum = 6. click to show more practice. More practice: If you have figured out …