Another Humble Programmer
BAN USERJust go through every node to see if its value is between min and max.
- Another Humble Programmer October 29, 2012Sure. Basically there are several rules that were described by those if and else if's.
(1) if i hasn't been initialized --> set i to the current number
(2) if j hasn't been initialized --> set it to the first number that is larger than a[i]
(3) when j hasn't been initialized, when a smaller number (i.e. a[n]) is found, update i.
(4) if i and j have been found; n represents the new number, if a[n] > a[i] and a[n]>a[j], update j; since a[j] is smaller, it is more likely to find a k.
(5) if i and j have been found, if a[n] > a[j] we find k!! Since we have found i<j<k and a[i]<a[j]<a[k] at this time, the loop can be terminated.
(6) if temp hasn't been initialized, if a[n] < a[i], we found a potentially smaller i, store the i in temp, temp = i
(7) if a number that is smaller than a[j] but larger than a[i] has been found, and temp is initialized, we update i and j at the same time. either, senario one, i=temp, j=the new number or, senario two, i=the new number, j=temp, depending on the relative maginitue of a[temp] and a[n];we reset temp to -1 after this.
This one works too.
It simulates the rotation. Though it's O(n^2).
1 2 3 4 5
0 5 6 7 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
------------
0,0 --> 0,4
0,4 --> 4,4
4,4 --> 4,0
4,0 --> 0,0
***
0,1 --> 1,4
1,4 --> 4,3
4,3 --> 3,0
3,0 --> 0,1
***
0,2 --> 2,4
2,4 --> 4,2
4,2 --> 2,0
2,0 --> 0,2
***
0,3 --> 3,4
3,4 --> 4,1
4,1 --> 1,0
1,0 --> 0,3
***
1,1 --> 1,3
1,3 --> 3,3
3,3 --> 3,1
3,1 --> 1,1
***
1,2 --> 2,3
2,3 --> 3,2
3,2 --> 2,1
2,1 --> 1,2
***
0 0 0 0 1
0 0 0 5 2
0 0 0 6 3
0 0 0 7 4
0 0 0 0 5
package Rotate;
public class RotateClean {
public static void main(String args[]) {
int[][] a = { { 1, 2, 3, 4, 5 }, { 0, 5, 6, 7, 0 }, { 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 } };
rotate(a);
}
static void rotate(int[][] a) {
int temp0, temp1;
int n = a.length;
int m = n / 2;
print(a);
System.out.println("------------");
for (int j = 0; j < m; j++) {
for (int i = j; i < n - j - 1; i++) {
temp0 = a[i][n - 1 - j];
a[i][n - 1 - j] = a[j][i];
temp1 = a[n - 1 - j][n - 1 - j - (i - j)];
a[n - 1 - j][n - 1 - j - (i - j)] = temp0;
temp0 = a[n - 1 - j - (i - j)][j];
a[n - 1 - j - (i - j)][j] = temp1;
a[j][i] = temp0;
}
}
print(a);
}
static void print(int[][] a) {
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[i].length; j++) {
System.out.print(a[i][j] + " ");
}
System.out.println("");
}
}
}
It does not work given int[] a = { 9, 7, 5, 1, 9, 8, 9, 6, 10 };
- Another Humble Programmer October 28, 2012This does not work with input 9, 7, 5, 1, 3, 8, 9, 6, 2; there is 1<3<8
- Another Humble Programmer October 28, 2012I got a solution of O(n) time and O(1) space. It doesn't need to finish going through the array.
The idea:
Go through the list from left to right. If k hasn't been found, I want to find i and j to be some numbers as small as possible. I use variable temp to store a potential smaller i. i and j will be updated at the same time when a smaller j has been found.
Use 4, 7, 5, 1, 3, 8, 9, 6, 2 as an example:
i, j, k, temp
----------
0,-1,-1,-1 // a[0] = 4
0, 1,-1,-1 // a[0] = 4, a[1] = 7
0, 2,-1,-1 // a[0] = 4, a[2] = 5
0, 2,-1, 3 // temp = 3
3, 4,-1,-1 // a[3] = 1, a[4] = 3
3, 4, 5,-1 // a[3] = 1, a[4] = 3, a[5] = 8
i<j<k: 3<4<5
a[i]<a[j]<a[k]: 1<3<8
class Ijk {
public static void main(String[] args) {
Integer[] a = { 4, 7, 5, 1, 3, 8, 9, 6, 2 };
Integer temp = -1, i = -1, j = -1, k = -1;
for (int n = 0; n < a.length; n++) {
if (i != -1) {
if (j != -1) {
if (a[n] > a[i] && a[n] < a[j]) {
j = n;
} else if (a[n] > a[j]) {
k = n;
break;
}
if (temp != -1) {
if (a[temp] < a[i] && a[n] < a[j] && a[n] > a[temp]) {
i = temp;
j = n;
temp = -1;
}
else if (a[temp] < a[i] && a[n] < a[j]
&& a[n] < a[temp]) {
i = n;
j = temp;
temp = -1;
}
} else {
if (a[n] < a[i]) {
temp = n;
}
}
} else {
if (a[n] > a[i]) {
j = n;
}else if (a[n] < a[i]) {
i = n;
}
}
} else {
i = n;
}
}
System.out.println(i + "<" + j + "<" + k);
System.out.println(a[i] + "<" + a[j] + "<" + a[k]);
}
}
@juando.martin Yes. I think you are right :-) Good idea. Thank you so much. What I implemented is what alphayoung suggests.
- Another Humble Programmer October 27, 2012I have implemented the idea in Java. It looks good.
import java.util.HashMap;
class Node {
Integer first;
Integer last;
Node(Integer first_int, Integer last_int) {
this.first = first_int;
this.last = last_int;
}
}
public class ConsecutiveString {
public static void main(String[] args) {
Integer max_length = 0;
String max_string = "";
HashMap<Integer, Node> table = new HashMap<Integer, Node>();
Integer[] numbers = { 101, 2, 3, 104, 5, 103, 9, 102 };
for (Integer number : numbers) {
if (table.containsKey(number)) {
continue;
} else {
Integer first = number;
Integer last = number;
if (table.containsKey(number - 1)) {
first = table.get(number - 1).first;
}
if (table.containsKey(number + 1)) {
last = table.get(number + 1).last;
}
// update all consecutive nodes
String consecutive = number.toString();
int i = 1;
while (table.containsKey(number - i)) {
table.get(number - i).first = first;
table.get(number - i).last = last;
consecutive = ((Integer) (number - i)).toString() + ","
+ consecutive;
i++;
}
i = 1;
while (table.containsKey(number + i)) {
table.get(number + i).first = first;
table.get(number + i).last = last;
consecutive = consecutive + ","
+ ((Integer) (number + i)).toString();
i++;
}
Node new_node = new Node(first, last);
table.put(number, new_node);
int length = last - first + 1;
if (length > max_length) {
max_length = length;
max_string = consecutive;
}
}
}
System.out.println(max_string);
}
}
Reppamulapaya2, Area Sales Manager at Alcatel Lucent
Jorie , a Customer services manager with more than 6 years' experience working is responsible for managing the relationships between an ...
Reprizzafilher, Java Developer at Achieve Internet
Sorter with 3+ years of experience , performs duties in a safe manner in compliance with all local, state, and federal ...
RepNaomiAdams, abc at 8x8
Passionate educator for nearly 5 years with a strong desire to help students recognize the connection between learning and experience ...
RepNirvedPerez, abc at 8x8
To make sure a thorough investigation is done if discrepancies occur. Execute the Brand Customer Service standards to meet or ...
Repaleasebkern, Personnel
Plant operators manage all things in an industrial plant or a power plant . They are supervising all the work . For ...
Repgiannanewhart, Cloud Support Associate at ABC TECH SUPPORT
I am Clinical managers, a type of medical and health services manager, and work as managers in both administrative areas ...
Repdevlinadevid, CAD Designer at FeatureCAM
Experienced CAD drafter seeking an advanced architectural position. Interested in culinary arts and currently in a course for making sushi ...
RepZoeyUhl, abc at 247quickbookshelp
With a highly experienced law clerk, well respected and writing proficient, detail oriented and proficient in preparing legal memos of ...
Repamritatorr, Paramedic at Capital Medical Billing
By profession, I am a paramedic in Chicago. I want to know about Indian ayurvedic treatment. I like to explore ...
Repjj2234971, Applications Developer at ABC TECH SUPPORT
My role for teaching students in a particular subject area. I specialize in a variety of subjects and fields. such ...
Repbungayasorya, Accountant at BrowserStack
An archeologist is an expert on history who gains expertise through experience with historical documents and artifacts. The archaeological record ...
This is my solution. You can create a InsertZeros.java to take a look. It uses dynamic programming.
- Another Humble Programmer October 29, 2012