algorithm
共 34 篇文章
[leetcode] Decode ways
http://leetcode.com/onlinejudge#question_91 Decode WaysJun 25 '121292 / 5011 A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given an encoded message containing digits, determine the total number of ways to decode it. Fo…
2013-05-02 21:47 · algorithm
[leetcode] Balanced Binary Tree
Check if a binary tree is balanced or not. This solution is from the discuss board. Much better than mine. /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public boolean isBalanced…
[leetcode] find median of two sorted arrays
http://leetcode.com/onlinejudge#question_4 Solution: a little ugly. public class Solution { public double findMedianSortedArrays(int A[], int B[]) { // Start typing your Java solution below // DO NOT write main() function int len1 = A.length; int len2 = B.length; int i = 0; int j = 0; int k = 0; do…
[leetcode] word ladder
Q: Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that: Only one letter can be changed at a time Each intermediate word must exist in the dictionary For example, Given: start = "hit" end = "cog" dict = As one shortest t…
[leetcode] sqrt(x)
I have talked about this question in my previous posts. http://leetcode.com/onlinejudge#question_69 Q: Implement int sqrt(int x). Compute and return the square root of x. Solution: public class Solution { public int sqrt(int x) { // Start typing your Java solution below // DO NOT write main() funct…
2013-04-15 07:44 · algorithm
[leetcode] word ladder II
http://leetcode.com/onlinejudge#question_126 Q: Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that: Only one letter can be changed at a time Each intermediate word must exist in the dictionary For example, Given: start = "hit…
[leetcode] Count and Say
http://leetcode.com/onlinejudge#question_38 Question: The count-and-say sequence is the sequence of integers beginning as follows: 1, 11, 21, 1211, 111221, ... 1 is read off as "one 1" or 11. 11 is read off as "two 1s" or 21. 21 is read off as "one 2, then one 1" or 1211. Given an integer n, genera…
[leetcode] Palindrome Partition
http://leetcode.com/onlinejudge#question_131 Question: Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. For example, given s = "aab", Return , ] Solution: This is also a DP. I like DP :D import java.util.Arra…
[leetcode] Palindrome Partitioning II
http://leetcode.com/onlinejudge#question_132 Question: Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s. For example, given s = "aab", Return 1 since the palindrome partitioning could be produ…
怎么不开根号算平方根?
写一个函数,不用开根号算平方根。 这是网上一个题目,一开始一筹莫展,看了答案恍然大悟,就是用二分法去逼近。 const double error = 0.000000001f; double findSqrt(double t){ double high = t; double low = 0; while(high-low >= error){ double mid = (high+low)/2; if(mid*mid > t){ high = mid; }else { low = mid; } } return low; }
2012-12-24 22:55 · algorithm
stack with min operation
How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time. public class StackWithMin extends Stack<NodeWithMin> { public void push(int value) { int newMin = Math.min(value, min()); su…
Rotation of String
Problem: Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring (i.e., “waterbottle” is a rotation of “erbottlewat”). 这个问题的trick就是将两个原字符串拼起来,然后检测。。。
算法:去除字符串中的重复字母
问题:去除字符串中的重复字符,不能使用额外空间(1或者2个变量除外)。 很简单的练手题,但是发现很难写正确。 public class DuplicateChar { //return length of the final string public static int removeDuplicateChar(char []str){ int len = str.length; if(len < 2) return len; for(int i=0;i<len-1;i++){ char ch = str[i]; int index = i+1; for(int j=i+1;j<=len-…
找零钱问题
假设有25美分,10美分,5美分,1美分的硬币足够多,假设有N美分钱,问你怎么用这些硬币表示? 用perl重新做这个问题,前面用 java 做过 use strict; use warnings; my $count = 0; sub changes { my ($coins_ref, $factors_ref, $value) = @_; my @coins = @$coins_ref; if($value == 0){ $count++; print "Result $count\n"; foreach my $key (keys %$factors_ref){ print "coin:…
怎样生成全排列?
我前面写过一种方法生成全排列,现在看用DP的方法解决。 参考 How to generate permutations 看前面的那种解法。 DP的思路就是生成N个数的全排列,先考虑生成前面N-1个数字的全排列,然后把最后一个数字插入上一步每个结果的每个缝隙中,形成最后的结果。用perl比较好操纵数组,写起来的程序比较简单。(可惜这个博客不支持perl语法高亮啊) use strict; use warnings; sub permutation { my (@array) = @_; my $length = scalar @array; if($length == 1){ #如果数组就一个…
Print all binary search trees
Problem: Given numbers 1,2,3...N, print all binary search trees that can be constructed with these N numbers. Solution: package alg; import java.util.ArrayList; import java.util.Collections; import java.util.List; public class AllBST { class Node<T extends Comparable<?>> { Node<T> left, right; T da…
Little-Known Awesome Algorithms: Fenwick Trees – Rapidly Find Cumulative Frequen
http://www.swageroo.com/wordpress/little-known-awesome-algorithms-fenwick-range-trees-rapidly-find-cumulative-frequency-sums/ This is to solve range query problems. Questions can be like below Imagine that we are creating an analytics tool for a financials brokerage, where orders are coming in all …
2012-09-28 17:28 · algorithm
Lock Free Stack
This example is copied from book "Java Concurrency in Practice". From this example we can learn that the lock free queue code is not correct for MPMC (multi-producer-multi-consumer) in my previous post. Actually, lock free means you should guarantee the atomicity of updating a pointer. When you add…
2012-09-06 15:31 · algorithm
Lock Free Queue Implementation
One consumer, one producer problem: Lock Free Queue Basically add one a separator in a list then nodes between separator and last is owned by consumer, the node between first and separator should be collected by producer and producer only append new nodes to the last. This problem is also described…
2012-09-05 16:29 · algorithm
8-Queen Problem
Problem: Write an algorithm to print all ways of arranging eight queens on a chess board so that none of them share the same row, column or diagonal. My Code: package alg; import java.util.Stack; public class EightQueens { public static final int N = 8; static class Queen { public int x, y; Queen(i…
2012-09-03 14:54 · algorithm