ttoommbb@126.com
BAN USERpackage gao.zone.study;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import static org.junit.Assert.assertArrayEquals;
public class DecodeNumsToChars {
public static void main(String[] args) {
String[] rst = transform("123");
String[] expected = {"abc","lc","aw"};
System.out.println(Arrays.toString(rst));
Arrays.sort(rst);
Arrays.sort(expected);
assertArrayEquals(expected, rst);
}
private static String[] transform(String nums) {
List<String> set = new ArrayList<String>();
transform(nums, set, new StringBuilder(), 0);
return set.toArray(new String[0]);
}
private static void transform(String nums, List<String> list,
StringBuilder prefix, int index) {
if (index >= nums.length()) {
list.add(prefix.toString());
return;
}
int bitNum = readNum(nums, index);
if (bitNum > 3 || index + 1 >= nums.length()) {// 3x,4x,...,9x or last
// bit.
transform(nums, list, prefix.append(numToWordChar(bitNum)),
index + 1);
} else {
// 1x,2x
int nextBitNum = readNum(nums, index + 1);
int combineBitNum = bitNum * 10 + nextBitNum;
if(nextBitNum != 0) {
//1x, 2x, except 10,20.
transform(nums, list, new StringBuilder(prefix).append(numToWordChar(bitNum)), index+1);
}
if (combineBitNum <= 26) {
transform(nums, list, prefix.append(numToWordChar(combineBitNum)), index+2);
}
}
}
private static int readNum(String string, int index) {
return string.charAt(index) - '0';
}
private static char numToWordChar(int num) {
return (char) (num-1 +'a');
}
}
int end = arr.length;
arr[end] may throw IndexOutOfBoundsException
package gao.zone.study;
import static org.junit.Assert.*;
import java.util.Arrays;
/**
* On a very large rotated sorted array with one or more duplicates, find the
* index of a particular number: 20,30,30,45,60,60,5,17,17,19
* */
public class SearchInRotatedSortedArray {
public static void main(String[] args) {
int[] nums = { 20, 30, 30, 45, 60, 60, 5, 17, 17, 19 };
for (int n : nums) {
int index = findIndex(nums, n);
assertTrue(index >= 0);
assertEquals(n, nums[index]);
}
assertTrue(findIndex(nums, 15) < 0);
assertTrue(findIndex(nums, 25) < 0);
assertTrue(findIndex(nums, 35) < 0);
assertTrue(findIndex(nums, 55) < 0);
assertTrue(findIndex(nums, 65) < 0);
}
private static int findIndex(int[] arr, int key) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
if (arr[low] <= arr[mid]) {
// left part continues.
if (arr[low] <= key && arr[mid] >= key) {
// key in range low~mid.
return Arrays.binarySearch(arr, low, mid + 1, key);
}
// key in range mid~high.
low = mid + 1;
continue;
}
if (arr[mid] <= arr[high]) {
// right part continues.
if (arr[mid] <= key && arr[high] >= key) {
// key in range mid~high
return Arrays.binarySearch(arr, mid, high + 1, key);
}
// key in range low~high.
high = mid - 1;
}
}
return -(low + 1);
}
}
It's said "... and store it in a separate array ..."
- ttoommbb@126.com September 05, 2014package gao.zone.study;
import java.lang.reflect.Array;
import java.util.Arrays;
public class SplitArr2 {
public static void main(String[] args) {
Integer[] arr = new Integer[88];// or use 0,1,19,20,21,999,1001
for (int i = 0; i < arr.length; i++) {
arr[i] = i;
}
Integer[][] splits = split(arr, 20);
for (Integer[] sub : splits) {
System.out.println(Arrays.toString(sub));
}
}
/**
* Split.
*
* @param <T> the generic type
* @param arr the array, not null
* @param gap the gap distance, must be positive.
* @return the splitted arrays.
*/
@SuppressWarnings("unchecked")
public static <T> T[][] split(T[] arr, int gap) {
T[][] arrs = (T[][]) Array.newInstance(arr.getClass(),
Math.min(gap, arr.length));
int shortLength = arr.length / gap;
int reminder = arr.length % gap;
for (int i = 0; i < arrs.length; i++) {
int partLength = i < reminder ? (1 + shortLength) : shortLength;
arrs[i] = (T[]) Array.newInstance(arr.getClass().getComponentType(), partLength);
for (int j = i, k = 0; j < arr.length; j += gap, k++) {
arrs[i][k] = arr[j];
}
}
return arrs;
}
}
Even the easiest questions can show your coding fundamentals.
If you don't agree, you can try to answer the question then compare with others'.
I believe you can learn from it more or less.
package gao.zone.study;
import java.util.Arrays;
public class PosNegSortArray {
public static void main(String[] args) {
int[] input = { 2, -1, -3, -7, -8, 9, 5, -5, -7 };
int[] expected = { 2, -1, 9, -3, 5, -7, -8, -5, -7 };
sort(input);
System.out.println(Arrays.toString(input));
System.out.println(Arrays.equals(input, expected));
}
private static void sort(int[] arr) {
next_i: for (int i = 0; i < arr.length; i++) {
boolean shouldBeNegative = (i & 1) != 0;
if (arr[i] > 0 ^ shouldBeNegative) {
// 0,2,4,...-> positive. 1,3,5,...->negative.
// condition satisfied.
continue;
}
// arr[i] not correct.
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] > 0 ^ shouldBeNegative) {
// first index j satisfied position for index i.
reInsert(arr, i, j);
continue next_i;
}
}
// not found suitable index j.
return;
}
}
private static void reInsert(int[] arr, int target, int pos) {
int t = arr[pos];
System.arraycopy(arr, target, arr, target+1, pos-target);
arr[target] = t;
}
}
package gao.zone.study;
import java.util.Arrays;
public class ThreeNumFromThreeArr {
private static class Combine {
private final int[] nums;
public Combine(int a, int b, int c) {
nums = new int[] {a,b,c};
}
public int getValue() {
int biggest = nums[0];
int smallest = nums[0];
for(int i = 1; i < nums.length ; i++) {
if(nums[1]> biggest) {
biggest = nums[i];
}
if(nums[i] < smallest) {
smallest = nums[i];
}
}
return biggest-smallest <<1;
}
public int[] toArray() {
return nums;
}
}
public static void main(String[] args) {
int[] arr1 = { 1, 2, 3, 30, 5 };
int[] arr2 = { 2, 4, 6, 8, 10 };
int[] arr3 = { 1, 4, 8, 9 };
int[] rst = findThreeNumber(arr1, arr2, arr3);
// 4,4,4.
System.out.println(Arrays.toString(rst));
}
public static int[] findThreeNumber(int[] arr1, int[] arr2, int[] arr3) {
Combine combine = null;
for (int n1 : arr1) {
int[] nearest = narrow(arr2, n1);
int[] nearest2 = narrow(arr3, n1);
Combine next = findBestCombine(n1, nearest, nearest2);
combine = getBetterCombine(combine, next);
}
return combine.toArray();
}
private static Combine findBestCombine(int n1, int[] nearest, int[] nearest2) {
Combine best = new Combine(n1, nearest[0], nearest2[0]);
for (int n2 : nearest) {
for (int n3 : nearest2) {
Combine next = new Combine(n1, n2, n3);
best = getBetterCombine(best, next);
}
}
return best;
}
private static Combine getBetterCombine(Combine c1, Combine c2) {
if(c1 == null) {
return c2;
}
if(c2 == null) {
return c1;
}
if(c1.getValue() < c2.getValue()) {
return c1;
}
return c2;
}
/**
* Find nearest two value to num. One is bigger than num, one is smaller
* than num. Or one only one result if have equals to num or no
* bigger/smaller than num.
*
* @param arr
* the arr
* @param num
* the num
* @return the int[]
*/
private static int[] narrow(int[] arr, int num) {
int positiveNear = num;// invalid value
int negativeNear = num;// invalid value
for (int n : arr) {
int offset = n - num;
if (offset == 0) {
return new int[] { num };
}
if (offset > 0) {
if (positiveNear == num || positiveNear > n) {
positiveNear = n;
}
continue;
}
if (offset < 0) {
if (positiveNear == num || negativeNear < n) {
negativeNear = n;
}
}
}
if (positiveNear == num) {
return new int[] { negativeNear };
}
if (negativeNear == num) {
return new int[] { positiveNear };
}
return new int[] { positiveNear, negativeNear };
}
}
package gao.zone.study;
import java.util.Arrays;
public class AnagramsSort {
public static void main(String[] args) {
String[] input = { "god", "dog", "abc", "cab", "man"};
String[] expected = {"abc", "cab", "dog", "god", "man"};
sort(input);
System.out.println(Arrays.toString(input));
if(!Arrays.equals(input, expected)) {
throw new AssertionError();
}
}
private static void sort(String[] input) {
for (int i = 0; i < input.length - 1; i++) {
// put correct value to index i
for (int j = i + 1; j < input.length; j++) {
if (input[i].compareTo(input[j]) > 0) {
swap(input, i, j);
}
}
// place anagrams follow index i
int anagramCount = 0;
char[] anagramKey = toAnagramKey(input[i]);
for (int j = i + 1; j < input.length; j++) {
if (isAnagram(anagramKey, input[j])) {
anagramCount++;
swap(input, i + anagramCount, j);
}
}
if (anagramCount > 0) {
Arrays.sort(input, i + 1, i + anagramCount + 1);
i += anagramCount;
}
}
}
private static boolean isAnagram(char[] anagramKey, String string) {
if (string.length() != anagramKey.length) {
return false;
}
return Arrays.equals(toAnagramKey(string), anagramKey);
}
private static char[] toAnagramKey(String string) {
char[] arr = string.toCharArray();
Arrays.sort(arr);
return arr;
}
private static void swap(String[] input, int i, int j) {
String temp = input[i];
input[i] = input[j];
input[j] = temp;
}
}
package gao.zone.study;
import java.util.StringTokenizer;
public class FindLatestVersion {
public static void main(String[] args) {
String[] versions = { "3.1", "3.2" ,"3.2.gao","3.2.zone"};
String v = latest(versions);
System.out.println(v);
}
private static String latest(String[] versions) {
if (versions.length == 0) {
return null;
}
String v = versions[0];
for (int i = 1; i < versions.length; i++) {
v = latest(v, versions[i]);
}
return v;
}
private static String latest(String version1, String version2) {
StringTokenizer st1 = new StringTokenizer(version1, ".");
StringTokenizer st2 = new StringTokenizer(version2, ".");
while (true) {
// the longer, the later.
if (!st1.hasMoreTokens()) {
return version2;
}
if (!st2.hasMoreTokens()) {
return version1;
}
String p1 = st1.nextToken();
String p2 = st2.nextToken();
int compare = comparePart(p1, p2);
if (compare > 0) {
return version1;
}
if (compare < 0) {
return version2;
}
}
}
private static int comparePart(String p1, String p2) {
// number bigger than string.
Integer num1 = null, num2 = null;
try {
num1 = Integer.parseInt(p1);
num2 = Integer.parseInt(p2);
} catch (NumberFormatException e) {
}
if (num1 == null) {
if (num2 == null) {
// compare as string
return p1.compareTo(p2);
}
assert num1 == null && num2 != null;
return -1;
}
assert num1 != null;
if(num2 == null) {
return 1;
}
assert num1 != null && num2 != null;
return Integer.compare(num1, num2);
}
}
package gao.zone.study;
import java.util.Arrays;
public class PrintAsteriskTraingle {
public static void main(String[] args) {
print(1, 4, 1);
}
private static void print(int min, int max, int step) {
for (int i = min; i <= max; i += step) {
printLine(i);
}
}
private static void printLine(int length) {
char[] chars = new char[length];
Arrays.fill(chars, '*');
System.out.println(String.valueOf(chars));
}
}
Open Close Principle
Software entities like classes, modules and functions should be open for extension but closed for modifications.
Dependency Inversion Principle
High-level modules should not depend on low-level modules. Both should depend on abstractions.
Abstractions should not depend on details. Details should depend on abstractions.
Interface Segregation Principle
Clients should not be forced to depend upon interfaces that they don't use.
Single Responsibility Principle
A class should have only one reason to change.
Liskov's Substitution Principle
Derived types must be completely substitutable for their base types.
For "short" and "long" , IMO they are similar, both per JVM.
If need scale limitation, you can change public to default.
Or register a SecurityManager to limit specific invoking case.
Below is a Singleton example, you can also use Enum or Interface(java1.8+)
package gao.zone.study;
public class MySingleton {
private final static class Holder{
private final static MySingleton INSTANCE = new MySingleton();
}
private MySingleton(){}
public final static MySingleton getInstance() {
return Holder.INSTANCE;
}
public void foo() { }
public <T> T bar() {return null;}
}
For 2. I think a private static class is enough.
- ttoommbb@126.com August 25, 2014public class MergeArray{
/**
@Param arr1 sorted arr
@Param arr2 sorted arr
*/
public static <T extends Comparable<? super T>> T[] merge(T[] arr1, T[] arr2){
@SuppressWarnings("unchecked")
T[] merged = (T[])(Array.newInstance(arr1.getClass().getComponentType(), arr1.length+arr2.length));
int index1 = 0;
int index2 = 0;
for(int i = 0; i < merged.length ; i++){
if(index1 == arr1.length){
System.arraycopy(arr2, index2, merged, i, merged.length - i);
break;
}
if(index2 == arr2.length){
System.arraycopy(arr1, index1, merged, i, merged.length - i);
break;
}
T t1 = arr1[index1];
T t2 = arr2[index2];
if(t1.compareTo(t2) <= 0){
merged[i] = t1;
index1++;
}else{
merged[i] = t2;
index2++;
}
}
return merged ;
}
public static void main(String[] args){
Integer [] a = {1,3,4, 5,6,7,8};
Integer [] b={4,6,7,8,9,10,11,12,13,14,15};
Integer [] merged = MergeArray.merge(a, b);
System.out.println(Arrays.toString(merged));
}
}
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;
interface Member {
public double getMonthlySales();
Collection<Member> getRecruitedMembers();
}
public class MemberPayoutUtil {
public static double calculatePayout(Member member) {
// Implement me!
final class TotalSalesTask extends RecursiveTask<Double> {
private final Member m;
TotalSalesTask(Member m) {
this.m = m;
}
@Override
public Double compute() {
List<TotalSalesTask> subTasks = new ArrayList<>();
for (Member sub : m.getRecruitedMembers()) {
TotalSalesTask subTask = new TotalSalesTask(sub);
subTask.fork();
subTasks.add(subTask);
}
double sum = m.getMonthlySales();
for (TotalSalesTask subTask : subTasks) {
try {
sum += subTask.get();
} catch (InterruptedException | ExecutionException e) {
e.printStackTrace();
}
}
return sum;
}
}
ForkJoinPool forkJoinPool = new ForkJoinPool();
Double allSales = forkJoinPool.invoke(new TotalSalesTask(member));
return allSales * 0.04 + member.getMonthlySales() * 0.06;
}
public static void main(String[] args) {
class MockMember implements Member {
private final double sales;
private final Collection<Member> members;
MockMember(double sales, Collection<Member> members) {
this.sales = sales;
this.members = members;
}
MockMember(double sales, int subs, double subSales) {
this.sales = sales;
members = new ArrayList<>(subs);
for (int i = 0; i < subs; i++) {
Member sub = new MockMember(subSales, null);
members.add(sub);
}
}
@Override
public Collection<Member> getRecruitedMembers() {
if (members == null) {
return Collections.emptyList();
}
return members;
}
@Override
public double getMonthlySales() {
return sales;
}
}
List<Member> members = new ArrayList<>();
for (int i = 0; i < 10; i++) {
Member m = new MockMember(100, 10, 100);
members.add(m);
}
Member member = new MockMember(100, members);
// member with 110 subs, each member sales equals 100.
// thus 100*110*0.04 + 100*0.1 = 450
System.out.println(MemberPayoutUtil.calculatePayout(member));
}
}
public class ArrayIntersectioner{
public static <E> Collection<E> intersection(E[] arr1,E[] arr2){
Map<E, Integer> countMap1 = getCountMap(arr1);
Map<E, Integer> countMap2 = getCountMap(arr2);
List<E> list = new ArrayList<E>(countMap1.size());
for(Entry<E,Integer> e1 : countMap1.entrySet()){
E item = e1.getKey();
Integer count2 = countMap2.get(item);
if(count2 == null){
continue;
}
Integer count1 = e1.getValue();
int minCount = Math.min(count1, count2);
for(int i = 0; i< minCount; i++){
list.add(item);
}
}
return list;
}
private static <E> Map<E, Integer> getCountMap(E[] arr){
Map<E, Integer> map = new HashMap<>();
for(E e : arr){
Integer count = map.get(e);
map.put(e, count == null ? 1 : ++count);
}
return map;
}
public static void main(String[] args){
String a[]={"a","b","c","d"};
String b[]={"b","c"};
Collection<String> commons = ArrayIntersectioner.intersection(a, b);
System.out.println(commons);
}
}
import java.util.Arrays;
import java.util.Iterator;
public class FlattedIterator<E> implements Iterator<E> {
private final Iterator<? extends Iterator<? extends E>> nested;
private Iterator<? extends E> cur;
public FlattedIterator(Iterator<? extends Iterator<? extends E>> nested) {
this.nested = nested;
cur = nested.next();
}
public static <E> Iterator<E> flattern(Iterator<? extends Iterator<? extends E>> nested) {
return new FlattedIterator<E>(nested);
}
@Override
public E next() {
if (!hasNext()) {
return null;
}
return cur.next();
}
@Override
public boolean hasNext() {
while (cur != null) {
if (cur.hasNext()) {
return true;
}
if (nested.hasNext()) {
cur = nested.next();
} else {
return false;
}
}
return false;
}
@Override
public void remove() {
if (cur.hasNext()) {
cur.remove();
}
}
public static void main(String[] args) {
Iterator<Integer> a = Arrays.asList(1, 2, 3).iterator();
Iterator<Double> b = Arrays.asList(4.0, 5.0, 6.0).iterator();
Iterator<Long> c = Arrays.asList(7L, 8L, 9L).iterator();
Iterator<? extends Iterator<? extends Number>> list = Arrays.asList(a, b, c).iterator();
Iterator<Number> itr = flattern(list);
while (itr.hasNext()) {
Number num = itr.next();
System.out.println(num);
}
}
}
Similar to algolearner's answer. But use layer deep first. Also skipped circles.
- ttoommbb@126.com September 05, 2014