100100001000 One[i]: 1XXXXXXXXXXXXX Zero[i]: 1XXXXXXXXXXXXX Zero[i] = zero[i + 1] + one[i + 1]; One[i] = zero[i] One[i] is the number of combination without continuous 11, with MSB 1 Zero[i] is the number of combination without continuous 11, with MSB 0 Then go over from MSB to LSB. If at any position, it has XX00YY,… Read More »
leetcode 368. Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0. If there are multiple solutions, return any subset is fine. Example 1: nums: [1,2,3] Result: [1,2] (of course, [1,3]… Read More »
https://leetcode.com/problems/integer-break/ Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get. For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3… Read More »
Problem: There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color. The cost of painting each house with… Read More »
Problem source: https://leetcode.com/problems/burst-balloons/ Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i.… Read More »
‘.’ Matches any single character. ‘*’ Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). The function prototype should be: bool isMatch(const char *s, const char *p) Some examples: isMatch(“aa”,”a”) → false isMatch(“aa”,”aa”) → true isMatch(“aaa”,”aa”) → false isMatch(“aa”, “a*”) → true isMatch(“aa”, “.*”) → true… Read More »
This is from leetcode: ‘.’ Matches any single character. ‘*’ Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). The function prototype should be: bool isMatch(const char *s, const char *p) Some examples: isMatch(“aa”,”a”) → false isMatch(“aa”,”aa”) → true isMatch(“aaa”,”aa”) → false isMatch(“aa”, “a*”) → true… Read More »
Given a dictionary, and a string, find is string can be broke down by words in dictionary. For example, dict = [cat, cats, and, dog, sand], str=’catsanddog’ Should return ‘cat sand dog’, ‘cats and dog’ Naive way is from-top-to-bottom. For example, if we want to check [c1, c2, c3, c4, c5] is breakable, we check… Read More »
Given a set of coins and a bill value, use minimum number of coins to consist of number. For example, coin = {1, 2, 5}, bill=11. the minimum coins is 5+5+1=11, 3 coins coin = {1, 2, 5}, bill=11, the minimum coins is 1+1+1+1+1+1+1+1+1+1+1=11, 11 coins coin = {2, 5, 7}, bill=11, there is no… Read More »
This is from leetcode: link. Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions. The solution is to maintain 2 array, maxLeft[], maxRight[]. maxLeft[i] maintains the max profit from price[0],…,price[i] by one transaction. maxRight[i] maintains from price[i],…,price[length-1] by… Read More »