xiang.zh
BAN USERIf we want to do it in place, then we have to shift the elements,And my solution's time complexity is O(n*n)
public class sortArray {
public static void main(String[] args){
int array[] = {1,-2,3,-4,-5,-6,-7,8,9,4,10,11,12};
for(int i : array){
System.out.print(i + " ");
}
System.out.println();
sortMethod(array);
for(int i : array){
System.out.print(i + " ");
}
}
public static void sortMethod(int array[]){
if(array == null){
return;
}
int positiveIndex = 0;
int negativeIndex = 0;
while(positiveIndex < array.length && negativeIndex < array.length){
positiveIndex = findNextOddPositive(array, positiveIndex);
if(positiveIndex == -1){
break;
}
negativeIndex = findNextNegatveEven(array, negativeIndex);
if(negativeIndex == -1){
break;
}
if(positiveIndex > negativeIndex){
int firstPostive = findFirstPostive(array, negativeIndex);
if(firstPostive == -1){
break;
}
shiftArray(array, negativeIndex, firstPostive);
}
else{
int firstNegative = findFirstNegative(array, positiveIndex);
if(firstNegative == -1){
break;
}
shiftArray(array, positiveIndex, firstNegative);
}
}
return ;
}
public static int findFirstPostive(int array[], int index){
while(index < array.length){
if(array[index] >= 0){
return index;
}
index++;
}
return -1;
}
public static int findFirstNegative(int array[], int index){
while(index < array.length){
if(array[index] < 0){
return index;
}
index++;
}
return -1;
}
public static void shiftArray(int array[], int start, int end){
if(start > end || array == null){
return;
}
int temp = array[end];
for(int i = end; i > start; i--){
array[i] = array[i - 1];
}
array[start] = temp;
}
public static int findNextOddPositive(int array[], int index){
if(array == null){
return -1;
}
while(index >= 0 && index < array.length){
if(array[index] < 0 || (array[index] >= 0 && (index % 2) == 0)){
index++;
}
else{
return index;
}
}
return -1;
}
public static int findNextNegatveEven(int array[], int index){
if(array == null){
return -1;
}
while(index >= 0 && index < array.length){
if(array[index] >= 0 || (array[index] < 0 && (index % 2) == 1)){
index++;
}
else{
return index;
}
}
return -1;
}
}
public static int findMinumumJump(int array[]){
if(array == null){
return -1;
}
if(array.length == 1){
return 0;
}
int jumps[] = new int[array.length];
for(int i = array.length - 2; i >= 0 ; i--){
if(array[i] == 0){
jumps[i] = Integer.MAX_VALUE;
continue;
}
if((array[i] + i) >= array.length - 1){
jumps[i] = 1;
}
else{
int minumnNumber = Integer.MAX_VALUE;
for(int j = i + 1; (j < array.length - 1) && (j <= array[i] + i); j++){
if(jumps[j] < minumnNumber){
minumnNumber = jumps[j];
}
}
jumps[i] = minumnNumber + 1;
}
}
return jumps[0];
}
import java.util.*;
import java.lang.*;
public class Excel {
public static void main(String[] args){
changeToString(702);
}
public static void changeToString(int number){
if(number <= 0){
return;
}
Stack<Integer> array = new Stack<Integer>();
int temp = number;
while(temp > 26){
int remain = temp % 26;
if(remain == 0){
remain = 26;
}
array.add(remain);
temp = temp - remain;
temp = temp / 26;
}
if(temp != 0){
array.add(temp);
}
String s = convertToString(array);
System.out.println(s);
}
public static String convertToString(Stack<Integer> array){
StringBuilder sb = new StringBuilder();
while(array.size() != 0){
int number = array.pop();
sb.append(numberToChar(number));
}
return sb.toString();
}
public static char numberToChar(int number){
if(number > 26 || number < 0){
return '\0';
}
char c = (char) ('A' + (number - 1));
return c;
}
}
public static void printLeftNode(TreeNode pNode, HashMap<Integer, Boolean> map, int currenDepth){
if(pNode == null){
return;
}
if(!map.containsKey(currenDepth)){
System.out.print(pNode.data + " ");
map.put(currenDepth, true);
}
printLeftNode(pNode.pLeft, map, currenDepth + 1);
printLeftNode(pNode.pRight, map, currenDepth + 1);
}
import java.lang.*;
public class face {
public static void main(String[] args){
int result = countNumber("bcd");
System.out.print(result);
}
public static int countNumber(String s){
if(s == null || s.equals("")){
return 0;
}
int result = countNumberCore(s, 0, s.length() - 1, 0, false);
return result;
}
public static int countNumberCore(String s, int start, int end, int sum, boolean sameChar){
if(sameChar == true){
return sum;
}
if(start == end){
return sum + (s.charAt(start) - 'a');
}
char before = '\0';
if(start != 0){
before = s.charAt(start - 1);
}
if(before == '\0' || s.charAt(start) < before){
int difference = s.charAt(start) - 'a';
sum = countSubfunction(difference, start, end, sum);
}
else if(s.charAt(start) > before) {
int difference = s.charAt(start) - 'a' - 1;
sum = countSubfunction(difference, start, end, sum);
}
else{
sameChar = true;
int difference = s.charAt(start) - 'a';
sum = countSubfunction(difference, start, end, sum);
}
return countNumberCore(s, start + 1, end, sum, sameChar);
}
public static int countSubfunction(int difference, int start, int end, int sum){
for(int i = difference; i > 0; i--){
int tempSum = 1;
for(int j = start + 1; j <= end; j++){
tempSum = (tempSum * 25) % 1009;
}
sum += tempSum;
}
return sum % 1009;
}
}
import java.lang.*;
public class face {
public static void main(String[] args){
int result = countNumber("bcd");
System.out.print(result);
}
public static int countNumber(String s){
if(s == null || s.equals("")){
return 0;
}
int result = countNumberCore(s, 0, s.length() - 1, 0, false);
return result;
}
public static int countNumberCore(String s, int start, int end, int sum, boolean sameChar){
if(sameChar == true){
return sum;
}
if(start == end){
return sum + (s.charAt(start) - 'a');
}
char before = '\0';
if(start != 0){
before = s.charAt(start - 1);
}
if(before == '\0' || s.charAt(start) < before){
int difference = s.charAt(start) - 'a';
sum = countSubfunction(difference, start, end, sum);
}
else if(s.charAt(start) > before) {
int difference = s.charAt(start) - 'a' - 1;
sum = countSubfunction(difference, start, end, sum);
}
else{
sameChar = true;
int difference = s.charAt(start) - 'a';
sum = countSubfunction(difference, start, end, sum);
}
return countNumberCore(s, start + 1, end, sum, sameChar);
}
public static int countSubfunction(int difference, int start, int end, int sum){
for(int i = difference; i > 0; i--){
int tempSum = 1;
for(int j = start + 1; j <= end; j++){
tempSum = (tempSum * 25) % 1009;
}
sum += tempSum;
}
return sum % 1009;
}
}
I used the BFS method by deleting one digit in each level to get the result.
And also use a Map to filter the duplicate node.
For example:
level 0: 8761
level 1: 876 871 861 761
level 2: 87 86 76 .....
- xiang.zh September 27, 2014