Kolpino
BAN USERpackage google.task;
public class CostToCost {
static int NX = 3;
static int NY = 3;
static Cell cells[][] = new Cell[NX][NY];
public static void main(String[] args) {
for (int i = 0; i < NX; i++) {
for (int j = 0; j < NY; j++) {
cells[i][j] = new CostToCost.Cell();
cells[i][j].value=-i;
}
}
cells[1][1].value = -10;
cells[0][0].hasPathDown = true;
visitDown(NX - 1, NY - 1);
for (int i = 0; i < NX; i++) {
for (int j = 0; j < NY; j++) {
System.out.println(" i=" + i + " j=" + j + " hasPathDwn="
+ cells[i][j].hasPathDown + " isVisitedDown="
+ cells[i][j].isVisitedDown + " value="
+ cells[i][j].value);
}
}
System.out.println("=================");
cells[NX-1][NY-1].hasPathUp = true;
visitUp(0, 0);
for (int i = 0; i < NX; i++) {
for (int j = 0; j < NY; j++) {
System.out.println(" i=" + i + " j=" + j + " hasPathUp="
+ cells[i][j].hasPathUp + " isVisitedUp="
+ cells[i][j].isVisitedUp + " value="
+ cells[i][j].value);
}
}
System.out.println("=================");
cells[NX-1][NY-1].hasPathUp = true;
visitUp(0, 0);
for (int i = 0; i < NX; i++) {
for (int j = 0; j < NY; j++) {
if (cells[i][j].hasPathUp && cells[i][j].hasPathDown)
System.out.println("Has path down and up i=" + i + " j=" + j );
}
}
}
static class Cell {
boolean isVisitedDown = false;
boolean hasPathDown = false;
int value;
boolean isVisitedUp = false;
boolean hasPathUp = false;
}
static void visitDown(int i, int j) {
if (i < 0 || i > (NX - 1) || j < 0 || j > (NY - 1))
return;
if (cells[i][j].isVisitedDown == true)
return;
int newI = i - 1;
if (newI >= 0) {
visitDown(newI, j);
if (cells[newI][j].value <= cells[i][j].value
&& cells[newI][j].hasPathDown) {
cells[i][j].hasPathDown = true;
}
}
int newJ = j - 1;
if (newJ >= 0) {
visitDown(i, newJ);
if (cells[i][newJ].value <= cells[i][j].value
&& cells[i][newJ].hasPathDown) {
cells[i][j].hasPathDown = true;
}
}
cells[i][j].isVisitedDown = true;
}
static void visitUp(int i, int j) {
if (i < 0 || i > (NX - 1) || j < 0 || j > (NY - 1))
return;
if (cells[i][j].isVisitedUp == true)
return;
int newI = i + 1;
if (newI < NX) {
visitUp(newI, j);
if (cells[newI][j].value <= cells[i][j].value
&& cells[newI][j].hasPathUp) {
cells[i][j].hasPathUp = true;
}
}
int newJ = j + 1;
if (newJ < NY) {
visitUp(i, newJ);
if (cells[i][newJ].value <= cells[i][j].value
&& cells[i][newJ].hasPathUp) {
cells[i][j].hasPathUp = true;
}
}
cells[i][j].isVisitedUp = true;
}
}
package google.task;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
public class UniqSubstr {
public static void main(String[] args) {
fun(string, subString);
}
final static int m = 2;
static List<Character> string = new LinkedList<>();
static List<Character> subString = new LinkedList<>();
static {
string.add('a');
string.add('b');
string.add('c');
string.add('c');
string.add('c');
string.add('c');
string.add('z');
string.add('c');
}
public static void fun(List<Character> string, List<Character> subString) {
for (int i = 0; i < string.size() - subString.size(); i++) {
List<Character> cand = string.subList(i, i + subString.size() + 1);
if ((new HashSet<Character>(cand)).size() <= m) {
subString = cand;
System.out.println("subString="+subString);
fun(string,subString);
break;
}
}
}
}
Simple Solution - create new List and pack into it with proper order:
- Kolpino April 23, 2015