littlefinger
BAN USERf(n,k,is_previous_vowel)= {if yes then 21*f(n-1,k,false)+4*f(n-1,k,true)+1*f(n-1,k-1,true), if no then 25*f(n-1,k,false)+f(n-1,k,true)}
- littlefinger October 24, 2017go over all the 26^n strings and count
- littlefinger October 24, 20171- do topology sort
// 2- go over the list
// 2.1 - mark as visited
// 2.2 - if has one neighbour then
// 2.2.1 - update beforeMe to be the node population
// 2.2.2 - update max to be total_population - my population
// 2.3 - else:
// 2.3.1 - update beforeMe to be the sum of all the beforeMe of the visited neighbours
// 2.3.2 - update the max to be the maximum between the neighbours' beforeMe and (the total_population - visitorsUntilNow) since it is topological sort and we have another neighbour to visit
the code becomes as follows:
package training;
import java.util.ArrayList;
public class BaseballCity{
public static int id = 1;
public static int totalPopulation = 0;
public boolean isCalculating = false;
public int cityId;
public int population;
public int beforeMe = -1;
public int max = -1;
public ArrayList<BaseballCity> neighbours;
public BaseballCity(int population){
this.population = population;
cityId = id;
id++;
totalPopulation+=population;
neighbours = new ArrayList<>();
}
public void addNeighbour(BaseballCity n){
if(!neighbours.contains(n))
neighbours.add(n);
if(!n.neighbours.contains(n))
n.neighbours.add(this);
}
public ArrayList<BaseballCity> runTopologySort(BaseballCity n, boolean[] visited){
ArrayList<BaseballCity> res = new ArrayList<>();
visited[n.cityId] = true;
for(BaseballCity b : n.neighbours){
if(!visited[b.cityId]){
res.addAll(runTopologySort(b,visited));
}
}
res.add(n);
return res;
}
public void calcVisitors(){
// 1- do topology sort
// 2- go over the list
// 2.1 - mark as visited
// 2.2 - if has one neighbour then
// 2.2.1 - update beforeMe to be the node population
// 2.2.2 - update max to be total_population - my population
// 2.3 - else:
// 2.3.1 - update beforeMe to be the sum of all the beforeMe of the visited neighbours
// 2.3.2 - update the max to be the maximum between the neighbours' beforeMe and (the total_population - visitorsUntilNow) since it is topological sort and we have another neighbour to visit
boolean[] visited = new boolean[id];
ArrayList<BaseballCity> tsorted = runTopologySort(this, visited);
for(BaseballCity b : tsorted){
if(b.neighbours.size() == 1){
b.beforeMe = b.population;
b.max = totalPopulation - b.population;
}else{
int max = 0;
b.beforeMe = b.population;
for(BaseballCity i : b.neighbours){
if(i.beforeMe != -1){
if(i.beforeMe > max){
max = i.beforeMe;
}
b.beforeMe += i.beforeMe;
}
}
int flowFromOtherNodes = totalPopulation -b.beforeMe;
b.max = max > flowFromOtherNodes? max: flowFromOtherNodes;
}
}
}
@Override
public boolean equals(Object o){
return ((BaseballCity)o).cityId == cityId;
}
@Override
public String toString(){
return "city " +cityId + " : " + max;
}
public static void main(String[] args){
BaseballCity b1 = new BaseballCity(7);
BaseballCity b2 = new BaseballCity(2);
BaseballCity b3 = new BaseballCity(15);
BaseballCity b4 = new BaseballCity(1);
BaseballCity b5 = new BaseballCity(5);
BaseballCity b6 = new BaseballCity(3);
BaseballCity b7 = new BaseballCity(7);
BaseballCity b8 = new BaseballCity(4);
BaseballCity b9 = new BaseballCity(3);
//BaseballCity b = new BaseballCity();
b1.addNeighbour(b2);
b2.addNeighbour(b3);
b2.addNeighbour(b5);
b5.addNeighbour(b4);
b5.addNeighbour(b6);
b5.addNeighbour(b8);
b8.addNeighbour(b7);
b8.addNeighbour(b9);
b1.calcVisitors();
boolean[] visited = new boolean[id];
ArrayList<BaseballCity> tsorted = b1.runTopologySort(b1, visited);
for(BaseballCity b : tsorted)
System.out.println(b.toString());
}
}
what i did is: a recursion that is called on each expression between parenthesis. the result is put into queue. in the end, i will have a queue with operation and numbers.
package helloworld;
import java.util.LinkedList;
import java.util.Queue;
public class CalcExp {
String exp;
public CalcExp(String exp) {
this.exp = exp;
}
public Integer calc() throws Exception{
Queue<String> q = new LinkedList<String>();
int i =0;
for(String str : exp.split(" ")){
i += str.length()+1; // plus one for the space
if(str.equals("(")){
exp = exp.substring(i);
i=0;
q.add(calc().toString());
if(exp.equals("")){
break;
}
continue;
}
if(str.equals("*") ||str.equals("/") ||str.equals("+") ||str.equals("-") ){
q.add(str);
continue;
}
if(str.equals(" ")){
continue;
}
if(str.equals(")")){
exp = exp.substring(i-1);
i=0;
return calcStack(q);
}
// if we reached here then we have a digit.
q.add(str);
}
return calcStack(q);
}
private int calculate(String op, int op1, int op2) throws Exception {
if (op.equals("*")) {
return op1 * op2;
}
if (op.equals("/")) {
return op1 / op2;
}
if (op.equals("-")) {
return op1 - op2;
}
if (op.equals("+")) {
return op1 + op2;
}
throw new Exception("Operation " + op + " is not familiar");
}
private int calcStack(Queue<String> q) throws Exception {
int op1;
int op2;
int result = 0;
String currOp = null;
while (! q.isEmpty()) {
String str = q.poll();
if (str.equals("*") || str.equals("/") || str.equals("+") || str.equals("-")) {
currOp = new String(str);
op1 = Integer.parseInt(q.poll());
op2 = Integer.parseInt(q.poll());
result = calculate(currOp, op1, op2);
}else{
op2 = Integer.parseInt(str);
result = calculate(currOp, result, op2);
}
}
return result;
}
public static void main(String[] args) throws Exception {
String exp = "* 8 ( + 7 5 )";
System.out.println(exp + " equals: " + new CalcExp(exp).calc());
exp = "+ 7 5";
System.out.println(exp + " equals: " + new CalcExp(exp).calc());
}
}
my solution is as follows:
Start from the middle and compare the substring on the right and on the left
if equal then count 1 otherwise take a shorter string on the left and a shorter string on the right. by shorter i mean, drop the last char on each substring. keeps doing it until you reach two equal strings. then drop them from the main string, count them as 1 and solve the same problem for a shorter string. here is the code:
package helloworld;
import java.util.ArrayList;
import java.util.HashMap;
public class LongestPalindrom{
public Integer countPalindroms(String str){
//System.out.println("Solving for " + str);
if(str.length() <=1){
return str.length();
}
if(str.length() == 2 && str.charAt(0) == str.charAt(1)){
return 2;
}else{
if(str.length() == 2 && str.charAt(0) != str.charAt(1))
return 1;
}
int middle = (str.length())/2;
for(int i=0;i<middle; i++){
//System.out.println("comparing:" + str.substring(0,middle - i) + " and:"+str.substring(middle + i+1) + " middle=" + middle + " str=" + str );
if(str.substring(0,middle - i).equals(str.substring(middle + i+1))){
return 1 + countPalindroms(str.substring(middle - i , str.length() - (middle-i)));
}
}
return 1;
}
public static void main(String[] args){
String pal1 = "VOLVO";
System.out.printf("The pals for %s is:%d. expected 2%n",pal1,new LongestPalindrom().countPalindroms(pal1));
pal1 = "abZLkZLab";
System.out.printf("The pals for %s is:%d. expected 3%n",pal1,new LongestPalindrom().countPalindroms(pal1));
pal1 = "abZLffkjhffZLab";
System.out.printf("The pals for %s is:%d. expected 4%n",pal1,new LongestPalindrom().countPalindroms(pal1));
pal1 = "LLaZOkaLL";
System.out.printf("The pals for %s is:%d. expected 3%n",pal1,new LongestPalindrom().countPalindroms(pal1));
pal1 = "abZLfkjhfZLab";
System.out.printf("The pals for %s is:%d. expected 4%n",pal1,new LongestPalindrom().countPalindroms(pal1));
pal1 = "abaaolk";
System.out.printf("The pals for %s is:%d. expected 1%n",pal1,new LongestPalindrom().countPalindroms(pal1));
pal1 = "antaprezatpezapreanta";
System.out.printf("The pals for %s is:%d. expected 4%n",pal1,new LongestPalindrom().countPalindroms(pal1));
}
}
package helloworld;
import java.util.HashMap;
public class TopTrip{
private static int TOTAL_WEEKS = 4 - 1; // start counting from zero
private int getLongestVacationAtWeek(HashMap<Integer, Integer[]> vacations, int startWeek){
int maxVac = -1;
for(Integer currcity : vacations.keySet()){
int currCityVal = getCityVacationAtWeek(vacations, startWeek, currcity);
if(currCityVal > maxVac){
maxVac = currCityVal;
}
}
return maxVac;
}
private int getCityVacationAtWeek(HashMap<Integer, Integer[]> vacations, int startWeek, int city){
Integer[] cityVacs = vacations.get(city);
return cityVacs[startWeek];
}
private int calculateBestPath(HashMap<Integer, Integer[]> vacations, int startWeek, Integer[] visitedCities){
if(startWeek == TOTAL_WEEKS){
Integer city = new Integer(-1);
Integer longest = getLongestVacationAtWeek(vacations, startWeek);
int maxVac = -1;
for(Integer currcity : vacations.keySet()){
int currCityVal = getCityVacationAtWeek(vacations, startWeek, currcity);
if(currCityVal > maxVac){
maxVac = currCityVal;
city = currcity;
}
}
visitedCities[startWeek] = city;
return longest;
}
int longestTripInTotal = 0;
for(int city : vacations.keySet()){
int cityVacationAtWeek = getCityVacationAtWeek(vacations, startWeek, city);
int longestVacationFromCity = cityVacationAtWeek + calculateBestPath(vacations, startWeek+1,visitedCities);
if(longestVacationFromCity > longestTripInTotal){
visitedCities[startWeek] = city;
longestTripInTotal = longestVacationFromCity;
}
}
return longestTripInTotal;
}
public Integer[] getTopTrip(HashMap<Integer, Integer[]> vacations){
Integer[] result = null;
if(vacations == null){
return result;
}
if(vacations.keySet().size() == 0){
return result;
}
result = new Integer[TOTAL_WEEKS+1];
int longestPath = calculateBestPath(vacations, 0, result);
System.out.println("The longest trip is:" + longestPath);
return result;
}
public static void main(String[] args){
TopTrip tv = new TopTrip();
Integer[] city0 = {1,1,2,11};
Integer[] city1 = {5,1,3,7};
Integer[] city2 = {1,1,4,13};
HashMap<Integer, Integer[]> v = new HashMap<Integer, Integer[]>();
v.put(0,city0);
v.put(1,city1);
v.put(2,city2);
Integer[] path = tv.getTopTrip(v);
for(Integer i : path){
System.out.print(i + "->");
}
}
}
use Dijkstra
- littlefinger October 28, 2017