syl20j
BAN USERWe have to care about two things :
- computing the right coefficient (order of points)
- what if line is vertical ? Above has no meaning here
I think of something like this :
public class Line {
private float coef;
private float offset;
public Line(float x1,float y1, float x2, float y2){
if( x1 == x2){
throw new RuntimeException("can't create vertical lines");
}
// swap points if they aren't ordered on x axis
if( x1 >= x2 ){
float tmp = x1;
x1 = x2;
x2 = tmp;
tmp = y1;
y1 = y2;
y2 = tmp;
}
coef = (y2-y1)/(x2-x1);
offset = x1 - (coef*x1);
}
public boolean isAbove(float x, float y){
return (x*coef+offset)>y;
}
}
1) use a recursive function that provides sublist tail as result (and updates head as side-effect)
2) use two references to adjacent nodes (current and previous), chain current.next to previous
public class ReverseLinkedList {
private class Node {
private int value;
private Node next;
public Node(int value){
this.value = value;
}
public int getValue(){ return value;}
public Node getNext(){ return next;}
public void setNext(Node next){ this.next = next;}
}
private Node head;
public ReverseLinkedList(){
}
public void add(int v){
Node n = new Node(v);
n.setNext(head);
head = n;
}
public int remove(){
if( null == head){
throw new IllegalStateException("can't remove from empty list");
}
int v = head.getValue();
head = head.getNext();
return v;
}
public void reverse(){
if( null != head ){
Node newTail = reverseSubList(head);
newTail.setNext(null);
}
}
public void reverse2(){
if( null != head ){
Node previous = head;
Node n = head.getNext();
head.setNext(null);
while( null != n ){
Node oldNext = n.getNext();
n.setNext(previous);
previous = n;
n = oldNext;
}
head = previous;
}
}
public void print(){
Node n = head;
while( null != n ){
System.out.print(n.getValue());
System.out.print(" -> ");
n = n.getNext();
}
System.out.print("null");
}
// n is sublist head
// return sublist tail once reversed
// updates head reference when needed
private Node reverseSubList(Node n){
if( null == n.getNext()){
head = n;
} else {
Node subListTail = reverseSubList(n.getNext());
subListTail.setNext(n);
}
return n;
}
public static void main(String[] args){
ReverseLinkedList list = new ReverseLinkedList();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.print();
list.reverse();
list.print();
list.reverse2();
list.print();
}
}
Create a stack that keeps a reference to the min element.
Each node in stack have a reference to the "previous min" prior to its insertion.
When we remove the min, we update the min with its "previous min" and voila...
Should look like this :
public class MinStack {
private static class Node {
private final Integer v;
private final Node next;
private final Node previousMin;
public Node(Integer v, Node next, Node previousMin){
this.v = v;
this.next = next;
this.previousMin = previousMin;
}
public Integer getValue(){ return v;}
public Node getNext(){ return next;}
public Node getPreviousMin(){ return previousMin;}
}
private Node min = null;
private Node head = null;
public void push(Integer v){
Node n = new Node(v, head, min);
if( null == head){
head = n;
}
if( null == min || n.getValue() < min.getValue() ){
min = n;
}
}
public Integer pop(){
if( null == head ){
throw new RuntimeException("stack is empty");
}
Integer result = head.getValue();
if( head == min ){
min = head.getPreviousMin();
}
head = head.getNext();
return result;
}
public Integer getMin(){
if( null == min ){
throw new RuntimeException("can't get min from an empty stack");
}
return min.getValue();
}
}
observations :
- A prints a single A, other keys don't print anything unless in a sequence
- a sequence of Ctrl^A, Ctrl^C, Ctrl+V costs 3 keystrokes, but allows to multiply current amount of A by a factor of 2.
For less or equal to 6, typing only As is the bese solution, thus we return n.
Starting from 7, typing four A then a "copy sequence" allows to make 8 A.
we have to maximize the amount of sequences, and make sure we type at least one A.
- syl20j January 09, 2011