Youngsam
BAN USERJava Code
public static void main(String[] args){
String s="4+2*a/b-3";
double a=3;
double b=4;
evaluate(s,a,b);
}
static void evaluate(String s,double a,double b){
s=s.replaceAll("a",String.valueOf(a));
s=s.replaceAll("b",String.valueOf(b));
ArrayList<String> ar= new ArrayList<String>();
//split into arraylist by number or operator
String tmp="";
for(int i=0;i<s.length();i++){
if(Character.isDigit(s.charAt(i)) || s.charAt(i)=='.' ){
tmp=tmp+s.charAt(i);
}else{
ar.add(tmp);
ar.add(String.valueOf(s.charAt(i)));
tmp="";
}
if(i==s.length()-1){
ar.add(tmp);
tmp="";
}
}
ArrayList<String> r1=operate(ar,"*");
ArrayList<String> r2=operate(r1,"/");
ArrayList<String> r3=operate(r2,"+");
ArrayList<String> r4=operate(r3,"-");
System.out.println(r4.get(0));
}
static ArrayList<String> operate(ArrayList<String> source,String operator){
ArrayList<String> result=new ArrayList<String>();
boolean flag=false;
for(int i=0;i<source.size();i++){
String temp=source.get(i);
if(temp.equals(operator)){
double c=Double.valueOf(source.get(i-1));
double d=Double.valueOf(source.get(i+1));
result.remove(i-1);
if(operator.equals("*"))
{result.add(String.valueOf(c*d));flag=true;}
else if(operator.equals("/"))
{result.add(String.valueOf(c/d));flag=true;}
else if(operator.equals("+"))
{result.add(String.valueOf(c+d));flag=true;}
else{
result.add(String.valueOf(c-d));flag=true;}
}
else{
if(flag){
flag=false;
continue;
}
else
result.add(temp);
}
}
return result;
}
public static void main(String[] args){
int[][] a={
{11,12,13,14},
{21,22,23,24},
{31,32,33,34},
{41,42,43,44}
};
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("\r\n");
}
System.out.println("\r\n");
System.out.println("---------------------------------");
rotate(a);
}
static void rotate(int[][] a){
int rowlength=a.length;
int[][] r=new int[rowlength][];
for(int i=0;i<rowlength;i++){
r[i]=new int[a[i].length];
}
for(int j=0;j<a.length;j++){
for(int k=0;k<a[j].length;k++){
r[k][rowlength-j-1]=a[j][k];
}
}
for(int i=0;i<r.length;i++){
for(int j=0;j<r[i].length;j++){
System.out.print(r[i][j] +" ,");
}
System.out.println("\r\n");
}
}
public static void main(String[] args){
int[] a={8,2,4,7,1,0,3,6};
solve(a);
}
static void solve(int[] a){
ArrayList<Integer> r=new ArrayList<>();
System.out.println("increment order start");
for(int i=0;i<a.length;i++){
int tmp=a[i];
r.add(tmp);
tmp++;
for(int j=i+1;j<a.length;j++){
if(tmp==a[j]){
r.add(tmp);
tmp++;
}
}
if(r.size()>=2){
for(int k:r){
System.out.print(k + " , ");
}
}
System.out.println("\r\n");
r.clear();
}
System.out.println("increment order end");
System.out.println("decrement order start");
for(int i=0;i<a.length;i++){
int tmp=a[i];
r.add(tmp);
tmp--;
for(int j=i+1;j<a.length;j++){
if(tmp==a[j]){
r.add(tmp);
tmp--;
}
}
if(r.size()>=2){
for(int k:r){
System.out.print(k + " , ");
}
}
r.clear();
System.out.println("\r\n");
}
System.out.println("decrement order end");
}
Minimum O(N) not O(1) , question itself is wrong or it's not asking coding problem
O(N) java code for your reference
public static void main(String[] args){
int[] a1={1,2,3,4,5,6,7,8};
int[] a2={2,9,0,1,34,7,8};
merge(a1,a2);
}
static void merge(int[] a1,int[] a2){
ArrayList<Integer> arr=new ArrayList<>();
for(int i=0;i<a1.length;i++){
arr.add(a1[i]);
}
for(int i=0;i<a2.length;i++){
if(arr.contains(a2[i]))
continue;
else
arr.add(a2[i]);
}
for(int i:arr){
System.out.println(i);
}
}
Java Code
public static void main(String[] args){
SLinkedList sl=new SLinkedList();
sl.insertFirst(1);
sl.insertFirst(2);
sl.insertFirst(3);
sl.insertBefore(4, 2);
sl.insertAfter(5,4);
/*sl.reverse();*/
sl.recursiveReverse(sl.root);
sl.display();
}
}
class Node{
int data;
Node next;
public Node(int d){
this.data=d;
}
}
class SLinkedList{
Node root;
public SLinkedList(){
}
public void reverse(){
if(root==null || root.next==null)
return;
else if(root!=null && root.next!=null && root.next.next==null){
Node curr=root;
Node next=root.next;
next.next=curr;
root=next;
}
else{
Node curr=root;
Node next=curr.next;
Node prev=null;
while(curr.next!=null){
next=curr.next;
curr.next=prev;
prev=curr;
curr=next;
}
curr.next=prev;
root=curr;
}
}
public void recursiveReverse(Node n){
Node curr=n;
if(curr==null)
return;
if(curr.next==null){
root=curr;
return;
}
recursiveReverse(n.next);
curr.next.next=curr;
curr.next=null;
}
public void insertFirst(int d){
Node n=new Node(d);
if(root==null)
root=n;
else{
n.next=root;
root=n;
}
}
public void insertBefore(int v,int d){
if(root==null)
return;
else{
Node n= new Node(v);
Node curr=root;
Node prev=null;
while(curr.data!=d){
prev=curr;
curr=curr.next;
if(curr==null)
return;
}
prev.next=n;
n.next=curr;
}
}
public void insertAfter(int v,int d){
if(root==null)
return;
else{
Node n=new Node(v);
Node curr=root;
Node next=null;
while(curr.data!=d){
curr=curr.next;
next=curr.next;
if(curr==null)
return;
}
curr.next=n;
n.next=next;
}
}
public void remove(int d){
if(root==null)
return;
else{
Node curr=root;
Node prev=null;
while(curr.data!=d){
prev=curr;
curr=curr.next;
if(curr==null)
return;
}
prev.next=curr.next;
curr=null;
}
}
public void display(){
if(root==null)
return;
else{
Node curr=root;
while(curr!=null){
System.out.print(curr.data + " ---> ");
curr=curr.next;
}
}
}
Java code
public static void main(String[] args){
String s="abcdaabbcdefghk";
String r=dedupe(s);
System.out.println(r);
}
static String dedupe(String s){
char[] c=s.toCharArray();
for(int i=0;i<c.length;i++){
char tmp=c[i];
for(int j=0;j<c.length;j++){
if(i==j)
continue;
else
if(tmp==c[j])
c[j]=' ';
}
}
String result=String.valueOf(c);
return result.replaceAll("\\s", "");
}
public static void main(String[] args){
int[] a={2,3,1,4};
solve(a,0);
}
static void solve(int[] a,int index){
//result array
int[] r = new int[a.length];
int t=1;
//multiple from left
for(int i=0;i<a.length;i++){
r[i]=t;
t=t*a[i];
}
t=1;
//multiple from right
for(int i=(a.length-1);i>=0;i--){
r[i]=t*r[i];
t=t*a[i];
}
//complete
for(int i=0;i<a.length;i++){
System.out.println(r[i]);
}
Java code
public static void main(String[] args){
String x = "1..5,8,11..14,18,20,26..29";
String y = "1,2,3,4,5,8,11,12,13,14,18,20,26,27,28,29";
extend(x,y);
}
static void extend(String x,String y){
String[] target=y.split(",");
ArrayList<Integer> source=new ArrayList<>();
String[] tmp=x.split("\\.\\.");
for(int i=0;i<tmp.length;i++){
String[] tmp2=tmp[i].split(",");
for(int j=0;j<tmp2.length;j++){
source.add(Integer.valueOf(tmp2[j]));
}
}
for(String s:target){
if(!source.contains(Integer.valueOf(s)))
source.add(Integer.valueOf(s));
}
Collections.sort(source);
for(Integer i:source){
System.out.print(i+",");
}
}
public static void main(String[] args){
String ap="/usr/bin/mail";
String rp="../../../etc/xyz/../abc";
pwd(ap, rp);
}
static void pwd(String ap,String rp){
String result="";
String[] a=ap.split("/");
String[] r=rp.split("/");
Stack<String> s=new Stack<String>();
for(int i=0;i<a.length;i++){
s.push(a[i]);
}
for(int j=0;j<r.length;j++){
if(r[j].equals("."))
continue;
else if(r[j].equals(".."))
s.pop();
else
s.push(r[j]);
}
while(!s.isEmpty()){
result=s.pop()+"/"+result;
}
System.out.println(result);
}
static HashMap<Integer, char[]> dictionary;
public static void main(String[] args){
dictionary = new HashMap<>();
char[] tmp0={'0','1','2'};
char[] tmp1={'a','b','c'};
char[] tmp2={'d','e','f'};
char[] tmp3={'h','i','j'};
char[] tmp4={'k','l','m'};
char[] tmp5={'o','p','q'};
char[] tmp6={'r','s','t'};
char[] tmp7={'u','v','w'};
char[] tmp8={'x','y','z'};
dictionary.put(1,tmp0);
dictionary.put(2,tmp1);
dictionary.put(3,tmp2);
dictionary.put(4,tmp3);
dictionary.put(5,tmp4);
dictionary.put(6,tmp5);
dictionary.put(7,tmp6);
dictionary.put(8,tmp7);
dictionary.put(9,tmp8);
int[] number={9,1,8,9,8,3,8,4};
solve(null,number);
}
static void solve(String[] c,int[] number){
if(number==null)
return;
else{
char[] c2=dictionary.get(number[0]);
String[] c3;
if(c!=null)
c3=new String[c.length*c2.length];
else
c3=new String[1*c2.length];
int count=0;
if(c!=null){
for(int i=0;i<c.length;i++){
for(int j=0;j<c2.length;j++){
c3[count++]=String.valueOf(c[i])+String.valueOf(c2[j]);
}
}
}else{
for(int j=0;j<c2.length;j++){
c3[count++]=String.valueOf(c2[j]);
}
}
int[] next=new int[number.length-1];
for(int i=1;i<number.length;i++){
next[i-1]=number[i];
}
if(next.length<1){
for(int i=0;i<c3.length;i++){
System.out.println(c3[i]);
}
}
else
solve(c3,next);
}
}
public static void main(String[] args){
String[] s={"bak","bag","tab"};
System.out.println(solve(s));
}
static boolean solve(String[] s){
for(int i=0;i<s.length;i++){
String tmp=new StringBuilder(s[i]).reverse().toString();
for(int j=0;j<s.length;j++){
if(i==j)
continue;
if(tmp.equals(s[j]))
return true;
else
continue;
}
}
return false;
}
public static void main(String[] args){
String a="cat";
String b="aata";
System.out.println(OneEditApart(a,b));
}
static boolean OneEditApart(String a,String b){
char[] arr = b.toCharArray();
int index=0;
int count=0;
if(Math.abs(a.length()-b.length())>1)
return false;
for(int i=0;i<a.length();i++){
index=b.indexOf(a.charAt(i));
if(index>=0){
arr[index]='\u0000';
}
else
count++;
if(count>1)
return false;
}
String result=String.valueOf(arr).trim();
if(result.length()<=1)
return true;
else
return false;
}
To put it simply , I ve used Binary Search Tree (didn't add up the balancing -rotation)
bottom line here is to traverse to capture all the value of the nodes
here's java code
public static void main(String[] args){
BinaryTree bt = new BinaryTree();
bt.insert(11);
bt.insert(5);
bt.insert(6);
bt.insert(9);
bt.insert(10);
bt.insert(15);
bt.insert(3);
bt.display();
bt.storeValue(bt.root);
System.out.println(bt.findMedian());
}
public class BinaryTree {
ArrayList<Integer> ar;
class Node{
int data;
Node leftChild;
Node rightChild;
public Node(int d){
this.data=d;
ar=new ArrayList<Integer>();
}
}
Node root;
public void insert(int d){
Node n=new Node(d);
if(root==null){
root=n;
}
else{
Node curr=root;
Node parr=null;
while(true){
parr=curr;
if(d<curr.data){
curr=curr.leftChild;
if(curr==null){
parr.leftChild=n;
return;
}
}
else{
curr=curr.rightChild;
if(curr==null){
parr.rightChild=n;
return;
}
}
}
}
}
public int getMaxDepth(Node n){
Node curr=n;
int count=0;
if(curr!=null){
count++;
if(curr.leftChild!=null && curr.rightChild==null)
return count+getMaxDepth(curr.leftChild);
else if(curr.leftChild==null && curr.rightChild!=null)
return count+getMaxDepth(curr.rightChild);
else {
if(getMaxDepth(curr.leftChild)>getMaxDepth(curr.rightChild))
return count+getMaxDepth(curr.leftChild);
else
return count+getMaxDepth(curr.rightChild);
}
}
else
return count;
}
public void display(){
Stack<Node> parr = new Stack<Node>();
Stack<Node> curr = new Stack<Node>();
boolean isEmptyRow=false;
parr.push(root);
while(isEmptyRow==false){
isEmptyRow=true;
while(parr.isEmpty()==false){
Node n=(Node)parr.pop();
if(n!=null){
System.out.print(" "+n.data+" ");
curr.push(n.leftChild);
curr.push(n.rightChild);
if(n.leftChild!=null || n.rightChild!=null)
isEmptyRow=false;
}
else{
System.out.print(" ** ");
curr.push(null);
curr.push(null);
}
}
while(curr.isEmpty()==false){
parr.push(curr.pop());
}
System.out.println("\r\n");
}
}
public void storeValue(Node n){
if(n!=null){
ar.add(n.data);
if(n.leftChild!=null && n.rightChild==null)
storeValue(n.leftChild);
else if(n.leftChild==null && n.rightChild!=null)
storeValue(n.rightChild);
else if (n.leftChild!=null && n.rightChild!=null){
storeValue(n.leftChild);
storeValue(n.rightChild);
}
}
}
public Integer findMedian(){
Collections.sort(ar);
if(ar.size()%2==1)
return ar.get(((ar.size())+1)/2 - 1);
else
return (ar.get((ar.size()/2) -1 ) + ar.get(((ar.size()/2) + 1)) -1 )/2;
}
Hello Rocky
I forgot the last case
Here's java code again
thx
public static void main(String[] args){
String a="12345a";
System.out.println(solve(a));
}
static boolean solve(String a){
char[] arr = a.toCharArray();
int tmp=0;
for( int i=0;i<arr.length;i++){
char c=arr[i];
tmp=(int)(c-'0');
if(i!=arr.length-1){
if(tmp>0 && tmp<10)
continue;
else
return false;
}{
if(c==' ' || (tmp>0 && tmp<10))
continue;
else
return false;
}
}
return true;
}
public static void main(String[] args){
String[] s={"cat","dog","fish","cat"};
solve(s);
}
static void solve(String[] s){
ArrayList<String> ar =new ArrayList<>();
for(int i=0;i<s.length;i++){
if(!ar.contains(s[i]))
ar.add(s[i]);
}
Object[] o=ar.toArray();
for(Object c:o){
System.out.println((String)c);
}
}
public static void main(String[] args){
String s="the boy ran";
solve(s);
}
static void solve(String _s){
String[] s=_s.split(" ");
StringBuilder r=new StringBuilder();
for(int i=0;i<s.length;i++){
for(int j=s[i].length()-1;j>=0;j--){
r.append(s[i].charAt(j));
}
r.append(" ");
}
System.out.println(r);
public static void main(String[] args){
int[] a={1,2,0,0,0,3,0,6,7,4,0,3,7,0};
solve(a);
}
static void solve(int[] a){
int tmp=0;
int tmp2=0;
for(int i=0;i<a.length;i++){
tmp=a[i];
if(tmp==0){
for(int j=i+1;j<a.length;j++){
if(a[j]!=0){
tmp2=a[j];
a[j]=tmp;
a[i]=tmp2;
}
}
}
}
for(int i:a){
System.out.print(i+", ");
}
}
public static void main(String[] args){
Object[][] a={{'a',1,5},{'b',2,4},{'c',7,8}};
solve(a);
}
static void solve(Object[][] a){
int len=a.length*2;
Object[][] o=new Object[len][2];
char tmpc=' ';
int tmpi=0;
int count=0;
for(int i=0;i<a.length;i++){
for(int j=0;j<a[i].length;j++){
if(j==0){
tmpc=(char)a[i][j];
o[count][0]=tmpc;
}
else if (j==1){
tmpi=(int)a[i][j];
o[count][1]=(int)tmpi;
count++;
}else {
tmpc=(char)a[i][0];
tmpi=(int)a[i][j];
o[count][0]=tmpc;
o[count][1]=(int)tmpi;
count++;
}
}
}
for(int i=0;i<o.length;i++){
System.out.println(o[i][0] + " ," + o[i][1]);
}
}
public static void main(String[] args){
String a="1234a56";
System.out.println(solve(a));
}
static boolean solve(String a){
char[] arr = a.toCharArray();
int tmp=0;
for(char c:arr){
tmp=(int)(c-'0');
if(tmp>0 && tmp<10)
continue;
else
return false;
}
return true;
}
public static void main(String[] args){
int[] a = new int[]{9,3,1,2,3,4,5,7,8,9,9};
solve(a);
}
static void solve(int[] a){
ArrayList<Integer> ar= new ArrayList<>();
for(int i=0;i<a.length;i++){
ar.add(a[i]);
}
Collections.sort(ar);
System.out.println(ar.get(ar.size()-1));
}
Java code , here you go
key is to compare the node which has both child
public class CMain {
public static void main(String[] args){
BinaryTree bt = new BinaryTree();
bt.insert(11);
bt.insert(5);
bt.insert(6);
bt.insert(9);
bt.insert(10);
bt.insert(15);
bt.insert(3);
bt.display();
int max=bt.getMaxDepth(bt.root);
System.out.println(max);
}
}
public class BinaryTree {
class Node{
int data;
Node leftChild;
Node rightChild;
public Node(int d){
this.data=d;
}
}
Node root;
public void insert(int d){
Node n=new Node(d);
if(root==null){
root=n;
}
else{
Node curr=root;
Node parr=null;
while(true){
parr=curr;
if(d<curr.data){
curr=curr.leftChild;
if(curr==null){
parr.leftChild=n;
return;
}
}
else{
curr=curr.rightChild;
if(curr==null){
parr.rightChild=n;
return;
}
}
}
}
}
public int getMaxDepth(Node n){
Node curr=n;
int count=0;
if(curr!=null){
count++;
if(curr.leftChild!=null && curr.rightChild==null)
return count+getMaxDepth(curr.leftChild);
else if(curr.leftChild==null && curr.rightChild!=null)
return count+getMaxDepth(curr.rightChild);
else {
if(getMaxDepth(curr.leftChild)>getMaxDepth(curr.rightChild))
return count+getMaxDepth(curr.leftChild);
else
return count+getMaxDepth(curr.rightChild);
}
}
else
return count;
}
public void display(){
Stack<Node> parr = new Stack<Node>();
Stack<Node> curr = new Stack<Node>();
boolean isEmptyRow=false;
parr.push(root);
while(isEmptyRow==false){
isEmptyRow=true;
while(parr.isEmpty()==false){
Node n=(Node)parr.pop();
if(n!=null){
System.out.print(" "+n.data+" ");
curr.push(n.leftChild);
curr.push(n.rightChild);
if(n.leftChild!=null || n.rightChild!=null)
isEmptyRow=false;
}
else{
System.out.print(" ** ");
curr.push(null);
curr.push(null);
}
}
while(curr.isEmpty()==false){
parr.push(curr.pop());
}
System.out.println("\r\n");
}
}
}
public static void main(String[] args){
String x="12786";
int r=solve(x);
System.out.println(r);
}
public static int solve(String x){
int sum = 0;
int i =1;
if (x.length()>0 && Integer.parseInt(x) < 27){
sum = 1;
}
while (i < x.length()){
sum = sum + solve(x.substring(i,x.length()));
i++;
}
return sum;
}
4 times correct
public static void main(String[] args){
int _s1=10;
int _s2=6;
int[] _A={0,2,3};
int _c=0;
int max=solve(_s1,_s2,_A,_c);
System.out.println(max);
}
public static int solve(int s1, int s2, int[] A, int c)
{
if(s1==0 && s2==0) return c;
else if (s1<0 || s2<0 ) return -1;
int max=-1;
for(int i=0;i<A.length;i++){
for(int j=0;j<A.length;j++){
int sc1=A[i];
int sc2=A[j];
if(sc1==0 && sc2==0) continue;
boolean change=false;
if(
(s1>s2 && (s1-sc1 <s2-sc2) &&s1-sc1>0 && s2-sc2>0 && (s1-sc1!=1) && (s2-sc2!=1) )
||
(s1<s2 && (s1-sc1 >s2-sc2) &&s1-sc1>0 && s2-sc2>0 && (s1-sc1!=1) && (s2-sc2!=1))
){
change=true;
System.out.println("(+"+sc1 +")----> " +s1 +" : " +s2 + "<---(+" + sc2 +")");
}
int x=solve(s1-sc1,s2-sc2,A,c+(change==true?1:0));
if(x>max) max=x;
}
}
return max;
}
(+3)----> 6 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+2)----> 5 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+3)----> 5 : 4<---(+0)
(+2)----> 5 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+3)----> 5 : 4<---(+0)
(+2)----> 4 : 3<---(+0)
(+3)----> 5 : 3<---(+0)
(+3)----> 5 : 3<---(+0)
(+2)----> 4 : 3<---(+0)
(+3)----> 6 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+2)----> 5 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+3)----> 5 : 4<---(+0)
(+2)----> 4 : 3<---(+0)
(+3)----> 5 : 3<---(+0)
(+3)----> 6 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+2)----> 4 : 3<---(+0)
(+0)----> 4 : 6<---(+3)
(+2)----> 4 : 3<---(+0)
(+2)----> 4 : 3<---(+0)
(+0)----> 3 : 4<---(+2)
(+0)----> 3 : 4<---(+2)
(+3)----> 6 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+2)----> 4 : 3<---(+0)
(+3)----> 8 : 6<---(+0)
(+0)----> 5 : 6<---(+2)
(+2)----> 5 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+3)----> 5 : 4<---(+0)
(+0)----> 5 : 6<---(+3)
(+3)----> 5 : 3<---(+0)
(+0)----> 3 : 4<---(+2)
(+0)----> 3 : 4<---(+2)
(+2)----> 5 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+3)----> 5 : 4<---(+0)
(+3)----> 5 : 3<---(+0)
(+3)----> 6 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+2)----> 5 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+3)----> 5 : 4<---(+0)
(+2)----> 4 : 3<---(+0)
(+3)----> 5 : 3<---(+0)
(+2)----> 5 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+3)----> 5 : 4<---(+0)
(+3)----> 5 : 3<---(+0)
(+2)----> 4 : 3<---(+0)
(+2)----> 7 : 6<---(+0)
(+0)----> 5 : 6<---(+2)
(+2)----> 5 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+3)----> 5 : 4<---(+0)
(+0)----> 5 : 6<---(+3)
(+3)----> 5 : 3<---(+0)
(+0)----> 3 : 4<---(+2)
(+0)----> 3 : 4<---(+2)
(+2)----> 5 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+3)----> 5 : 4<---(+0)
(+3)----> 5 : 3<---(+0)
(+3)----> 7 : 6<---(+0)
(+0)----> 4 : 6<---(+3)
(+2)----> 4 : 3<---(+0)
(+2)----> 4 : 3<---(+0)
(+2)----> 5 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+3)----> 5 : 4<---(+0)
(+3)----> 5 : 3<---(+0)
(+2)----> 4 : 3<---(+0)
4
Here is java code
key is you have to minus from final score ,
minus options are 0,2,3
e.g: 10-3 vs 6-0 --> 7-2 vs 6-0 (lead change)
public static void main(String[] args){
int _s1=10;
int _s2=6;
int[] _A={0,2,3};
int _c=0;
int max=solve(_s1,_s2,_A,_c);
System.out.println(max);
}
public static int solve(int s1, int s2, int[] A, int c)
{
if (s1 == 0 && s2 == 0) return c;
else if (s1 < 0 || s2 < 0) return -1;
int max = -1;
for (int i = 0; i < A.length; i++)
{
for (int j = 0; j < A.length; j++)
{
int sc1 = A[i];
int sc2 = A[j];
if (sc1 == 0 && sc2 == 0) continue;
boolean change = (s1 > s2 && s1 - sc1 < s2 - sc2 ||
(s1 < s2 && s1 - sc1 > s2 - sc2 ));
int x = solve(s1-sc1, s2-sc2, A, c + (change ? 1 : 0));
if (x > max) max = x;
}
}
return max;
}
public class CMain {
public static void main(String[] args){
Trie t = new Trie();
t.insert("cat");
t.insert("cot");
t.insert("cut");
t.insert("cit");
t.search2("c.t",t.root);
/*t.insert("aseton");*/
}
}
public class Trie {
Node root;
public Trie(){
root= new Node(' ');
}
public void insert(String s){
Node curr=root;
if(s.length()==0)
curr.marker=true;
for(int i=0;i<s.length();i++){
Node n=curr.getNode(s.charAt(i));
if(n!=null)
curr=n;
else{
curr.children.add(new Node(s.charAt(i)));
curr=curr.getNode(s.charAt(i));
}
if(i==s.length()-1)
curr.marker=true;
}
}
public void search2(String s, Node n){
Node curr=n;
while(curr!=null){
for(int i=0;i<s.length();i++){
if(curr.getNode(s.charAt(i))==null && s.charAt(i)!='.')
return;
else if(curr.getNode(s.charAt(i))!=null && s.charAt(i)!='.'){
curr=curr.getNode(s.charAt(i));
System.out.print(curr.data);
}
else //if(curr.getNode(s.charAt(i))==null && s.charAt(i)=='.')
{
System.out.println("\r\n");
for(Node tmp:curr.children){
System.out.print(tmp.data);
}
System.out.println("\r\n");
for(Node tmp:curr.children){
search2(s.substring(i+1,s.length()),tmp);
}
}
}
if(curr.marker==true){
return;
}
}
}
}
public class Node {
char data;
boolean marker;
Collection<Node> children;
public Node(char c){
children=new LinkedList<Node>();
data=c;
marker=false;
}
public Node getNode(char c){
if(children!=null){
for(Node n:children){
if(n.data==c)
return n;
}
}
return null;
}
}
public class CMain {
public static void main(String[] args){
Point p = new Point(0, 0);
p.findPath(new Point(0,0), new Point(5,5), p, new char[10][10]);
}
}
public class Point {
int x;
int y;
public Point(int _x,int _y){
this.x=_x;
this.y=_y;
}
public boolean findPath(Point start,Point end,Point current,char[][] map){
if(
current.x<0 || current.y<0 ||
current.x >= (map[current.y].length -1 ) ||
current.y >= (map.length-1) ||
map[current.y][current.x]=='X'
)
return false;
if(current.x==end.x && current.y==end.y){
System.out.println(current.x +" , "+ current.y);
return true;
}
if(current.x<end.x ){
System.out.println(current.x +" , "+ current.y);
return findPath(start,end,new Point(current.x+1,current.y),map);
}
else if(current.x>end.x ){
System.out.println(current.x +" , "+ current.y);
return findPath(start,end,new Point(current.x-1,current.y),map);
}
else if (current.y<end.y){
System.out.println(current.x +" , "+ current.y);
return findPath(start,end,new Point(current.x,current.y+1),map);
}
else if (current.y>end.y){
System.out.println(current.x +" , "+ current.y);
return findPath(start,end,new Point(current.x,current.y-1),map);
}
else
return false;
}
}
public class CMain {
public static void main(String[] args){
Point p = new Point(0, 0);
p.findPath(new Point(0,0), new Point(5,5), p, new char[10][10]);
}
}
public class Point {
int x;
int y;
public Point(int _x,int _y){
this.x=_x;
this.y=_y;
}
public boolean findPath(Point start,Point end,Point current,char[][] map){
if(
current.x<0 || current.y<0 ||
current.x >= (map[current.y].length -1 ) ||
current.y >= (map.length-1) ||
map[current.y][current.x]=='X'
)
return false;
if(current.x==end.x && current.y==end.y){
System.out.println(current.x +" , "+ current.y);
return true;
}
if(current.x<end.x ){
System.out.println(current.x +" , "+ current.y);
return findPath(start,end,new Point(current.x+1,current.y),map);
}
else if(current.x>end.x ){
System.out.println(current.x +" , "+ current.y);
return findPath(start,end,new Point(current.x-1,current.y),map);
}
else if (current.y<end.y){
System.out.println(current.x +" , "+ current.y);
return findPath(start,end,new Point(current.x,current.y+1),map);
}
else if (current.y>end.y){
System.out.println(current.x +" , "+ current.y);
return findPath(start,end,new Point(current.x,current.y-1),map);
}
else
return false;
}
}
Java Code
- Youngsam September 19, 2014