Posts

Showing posts from April, 2016

Topcoder SRM 689 NonDeterministicSubstring

this problem is about


Problem Statement You are given two Strings: A and B. Each character in A is either '0' or '1'. Each character in B is '0', '1', or '?'.


A string C matches B if we can change B into C by changing each '?' in B either to '0' or to '1'. Different occurrences of '?' may be changed to different digits. For example, C = "0101" matches B = "01??". Note that each character in C must be either '0' or '1', there cannot be any '?' remaining.


Consider all possible strings that match B. How many of these strings occur as a (contiguous) substring in A? Compute and return their number. Note that we only count each good string once, even if it has multiple occurrences in A. Definition …

how can we know this array is sorted in java

this is easy example

int o = a[0] < a[1] ? 0 :1; for (int i = 1; i < a.length-1; i++) if( 0!= (a[i] < a[i+1]?0:1) ) return"not sorted"; return o ==0?"ascending" : "descending";

Project Euler problem 303

My effort to solve it
1. make 3digit generator and divide with n 2. 9999 is never solved in time. 3. find 9, 99, 999, 9999 in pattern. 4. finally solve it in 9s

find the ways to make specific number with dice

this problem is about hexanacci number

long a = 0,b= 0,c= 0,d= 0,e= 0,f=1, t = 0; for (int i = 1; i <= n; i++) { t = a+b+c+d+e+f; a=b; b=c; c=d; d=e; e=f; f=t; } return t+"";Hexanacci numbers: a(n+1) = a(n)+...+a(n-5) with a(0)=...=a(4)=0, a(5)=1.

huffman coding ( encoding and decoding) algorithm in python

this is short code written by python.
Huffmanencoding and decoding

I studied using this site and write code  http://www.geeksforgeeks.org/greedy-algorithms-set-3-huffman-coding/




import random dic = {} class MinHeapNode: def setNode(self, left, right, freq, char): self.left = left self.right = right self.freq = freq self.char = char return selfdef huffmanCoding(arr, freq): heapArr = [] for i in range(len(arr)): heapArr.append(MinHeapNode().setNode(None, None , freq[i], arr[i])) print(heapArr[i].freq, heapArr[i].char) while(len(heapArr)>1): left = heapArr.pop(0) right = heapArr.pop(0) insertionSort(heapArr, MinHeapNode().setNode(left, right, left.freq+right.freq, left.char + right.char)) rootheap= heapArr.pop() return rootheap def printHeap(heap, str): if heap.left != None: printHeap(heap.left, str + '0') if heap.right !=None: printHeap(heap.right,…