ehsan
BAN USER90 degree clockwise rotation of n*m array means
row i of input array should copy to column n-1-i output array
and column j of input array should copy to row j of output array
int [][] rotate(int [][] input){
int n =input.length();
int m = input[0].length();
int [][] output = new int [m][n];
for (int i=0; i<n; i++)
for (int j=0;j<m; j++)
output [j][n-1-i] = input[i][j];
return output;
}
assume that we are searching for president of U.S. and the community has 3 persons. you , me and the president of U.S.
p[0] is you
p[1] is president of U.S.
p[2] is me
you don't know me. and I don't know you. but both of us know the president.
in your code at first loop i =0 and j=2 ( p[0] is you and p[2] is me)
if(you know me)
i++; // it does not run because you do not know me.
if(I know you)
j++; // it does not run because I don't know you
then while loop runs again and again , it means there is an infinite loop
I did my best to simplify the problem and explain that your code does not work!
dear Bigphatkdawg,
If you have the graph for this community you can find the mayor in O(n) but you don't have community graph. you should create it then use it to find the possible mayor.
the creation time is O(n2) because you have to check all possible edges. It does not matter how many edges the community has. for creation you need two nested loop to check who knows who.
if P[i] does not know any one return P[i]
else check P[i++]
it takes O(n2)
boolean isMayor = true;
for(int i=0; i< P.size; i++){
isMayor = true;
for(int j=0;j<i; j++)
if(P[i].knows(P[j])){
isMayor = false;
break;
}
if(isMayor){
for(int j=i+1;j<P.size; j++)
if(P[i].knows(P[j]))
isMayor = false;
break;
}
if(isMayor)
return P[i];
}
return null;
start from 0 and find first black index
start from n-1 and find first red index
then swap these black and red.
continue till these two index meet each other.
public static void sort(String [] st){
int n = st.length;
int b=0;//black Index
int r=n-1;//red Index
while(b<r){
while(b<n-1 && !st[b].equalsIgnoreCase("B"))
b++;
while(r>0 && !st[r].equalsIgnoreCase("R"))
r--;
if(b<r){
String temp = st[b];
st[b] = st[r];
st[r] = temp;
}
}
}
public static String missedNumber(String string) {
int missedNo = -1;
int n = string.length();
int next, temp, len, missedIndex = 0;
for (int l = 1; l <= n / 2; l++) {
next = Integer.valueOf(string.substring(0, l)) + 1;
len = l;
for (int i = l; i < n;) {
if (next / Math.pow(10, l) >= 1 && (next - 1) / Math.pow(10, l) < 1)
len++;
if (i + len <= n)
temp = Integer.valueOf(string.substring(i, i + len));
else
break;
if (temp == next) {
next++;
} else if (temp == next + 1 && missedNo == -1) {
missedNo = next;
missedIndex = i;
next++;
} else if ((next + 1) / Math.pow(10, l) == 1) {
temp = Integer.valueOf(string.substring(i, i + len + 1));
if (temp == next + 1 && missedNo == -1) {
missedNo = next;
missedIndex = i;
len++;
next += 2;
} else
break;
} else {
missedNo = -1;
break;
}
i += len;
}
if (missedNo != -1) {
break;
}
}
if (missedNo != -1) {
String before = string.substring(0, missedIndex);
String missed = String.valueOf(missedNo);
String after = string.substring(missedIndex, n);
return before.concat(missed).concat(after);
} else
return null;
}
It looks like powerset problem!
for each element of input :
If it is visited for the first time, just add it to all sets that has been added to powerset.
else check hashmap to find number of this element that has been visited, then add new element to set(s) that has exactly this number of duplication.
public static void powerSet(ArrayList<Integer> input) {
ArrayList<ArrayList<Integer>> powerSet = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> set = new ArrayList<Integer>();
powerSet.add(set);
HashMap<Integer, Integer> hm = new HashMap<>();
int focoused;
int counter=0,dupCounter;
if (input.isEmpty())
System.out.println("null");
else {
while (!input.isEmpty()) {
focoused = input.remove(0);
int psize = powerSet.size();
counter=0;
dupCounter=0;
{
if(hm.containsKey(focoused))
{
hm.put(focoused, hm.get(focoused)+1);
dupCounter = hm.get(focoused);
for (int i = 0; i < psize; i++) {
for(Integer ii : powerSet.get(i))
if(ii==focoused)
counter++;
if(counter==dupCounter-1)
{
powerSet.get(i).contains(focoused);
set = (ArrayList<Integer>) powerSet.get(i).clone();
set.add(focoused);
powerSet.add(set);
}
counter=0;
}
}
else{
hm.put(focoused, 1);
for (int i = 0; i < psize; i++) {
set = (ArrayList<Integer>) powerSet.get(i).clone();
set.add(focoused);
powerSet.add(set);
}
}
}
}
System.out.println(powerSet.toString());
}
}
It does not need to check all positions.
Check char at position 2 then 4 then 8 and so on until caught exception.
then call recursive method which returns the position of last char.
- ehsan October 17, 2013