shmilyaw
BAN USERsimiliar solutions. 1. go through the list 2. for each string in the list, change it to char array. 3. sort the char array. Put the sorted char array as key, the original string as value, to a HashMap. 4. compare each sorted string with the HashMap. 5. go through the hashmap to print all the result.
import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
public class RearrangeWords {
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list.add("star");
list.add("rats");
list.add("ice");
list.add("cie");
list.add("arts");
Map<String, List<String>> map = storeStrings(list);
printMap(map);
}
public static void printMap(Map<String, List<String>> map) {
for(String key : map.keySet()) {
for(String item : map.get(key)) {
System.out.print(item + " ");
}
System.out.println();
}
}
public static Map<String, List<String>> storeStrings(List<String> list) {
Map<String, List<String>> map = new HashMap<String, List<String>>();
for(String str : list) {
char[] chars = str.toCharArray();
sort(chars, 0, chars.length - 1);
String sortedStr = new String(chars);
if(map.containsKey(sortedStr)) {
map.get(sortedStr).add(str);
} else {
List<String> array = new ArrayList<String>();
array.add(str);
map.put(sortedStr, array);
}
}
return map;
}
public static void sort(char[] charlist, int l, int r) {
if(l < r) {
int p = partition(charlist, l, r);
sort(charlist, l, p - 1);
sort(charlist, p + 1, r);
}
}
public static int partition(char[] charlist, int l, int r) {
char val = charlist[r];
int j = l - 1;
for(int i = l; i < r; i++) {
if(charlist[i] < val) {
j++;
swap(charlist, i, j);
}
}
swap(charlist, j + 1, r);
return j + 1;
}
public static void swap(char[] charlist, int i, int j) {
char temp = charlist[i];
charlist[i] = charlist[j];
charlist[j] = temp;
}
One idea about the solution: 1. Calculate the distances of all points, they will get stored in an array. 2. The question can be attributed to the question to find the smallest k items in an array. To solve this question, we can use several ways, including sorting and find the kth, quicksort like way to partition the array to parts, that all based on the items are not that big enough, they can be loaded into memory.
The following part is sample code to find the Kth number:
public class FindKth {
public static int findKth(int[] a, int l, int r, int k) {
int n = partition(l, r);
int i = n - l + 1;
if(i > k) {
return findKth(a, l, n - 1, k);
} else if(i < k) {
return findKth(a, n + 1, r, k - i);
} else
return n;
}
public static int partition(int[] a, int l, int r) {
int value = a[r];
int j = l - 1;
for(int i = l; i < r; i++) {
if(a[i] < value) {
j++;
swap(a, i, j);
}
}
swap(a, j + 1, r);
return j + 1;
}
public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
Just fix a small issue in my previous code.
boolean isBST(TreeNode node) {
if(node == null)
return true;
if(node.left == null || node.right == null) {
if(node.left != null)
return (node.value > node.left.value) && isBST(node.left);
else if(node.right != null)
return (node.value < node.right.value) && isBST(node.right);
else
return true;
}
return (isBST(node.left) && node.value > node.left.value) &&
(isBST(node.right) && node.value < node.right.value);
}
public class MissingFinder {
public static int findMissing(int[] list) {
int length = list.length;
long sum = (length + 1) * (list[0] + list[length - 1]) / 2;
for(int i = 0; i < length; i++) {
sum -= list[i];
}
return (int)sum;
}
public static void main(String[] args) {
int[] list = {1, 3, 7, 9, 11, 13};
System.out.println(findMissing(list));
}
}
One way to solve it in java: 1. go through all the items in the list. 2. Check if the item is in a hashmap or set, if it's true, ignore it. Otherwise, put the item to the map and append it to an ArrayList
import java.util.List;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
public class Duplicator {
public static List<Integer> uniqueArray(int[] list) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
List<Integer> array = new ArrayList<Integer>();
for(int i = 0; i < list.length; i++) {
if(!map.containsKey(list[i])) {
map.put(list[i], 0);
array.add(list[i]);
}
}
return array;
}
public static void main(String[] args) {
int[] list = {1, 2, 3, 2, 3, 5, 4, 1};
List<Integer> array = uniqueArray(list);
for(Integer item: array) {
System.out.print(item + " ");
}
}
}
Based on the previous discussion, we can change the question to judge the number of moves to compact the number so at last all the number 1 get stay together, like '11111'. So in order to calculate the total number of moves, we can go through the following ways. First, find the first occurrence of 0 in the sequence. Then find the number 1 just behind this first 0. Then the moves for this round should be the subtract of both first 0 and 1 after it. Then we swap these two numbers in the array.
We keep on the process until we cannot find number 1 after the so called first 0. Then the total number of moves will be the judge base. Let it as count. If count is odd, then that means player 1 wins. Otherwise player 2 wins. The code are attached below, I just print the total move number:
- shmilyaw November 09, 2013