You Might Need This
Jump to navigation
Jump to search
Roman Numerals
The first time i needed this in a contest, I thought about it, and ended up hardcoding the roman numerals from 1 to 50 by hand.....got "40" wrong, and missed out on winning an SRM because of it (D2). Figured i'd never need it...and then it came up AGAIN...so finally I wrote some concise code to do it
/**
* converts an integer to a roman numeral
* @param n the number
* @return a string of the roman numeral
*/
public String i2rn(int n) {
String[] rn={"I","V","X","L","C","D","M"};
String out="";
while(n>1000){
n-=1000;
out+=rn[6];
}
for(int i=2;i>=0;i--){
int temp=n/(int)Math.pow(10, i);
n%=(int)Math.pow(10, i);
if(temp%5==4){
out+=rn[2*i];
temp++;
}
if(temp>9){
out+=rn[2*i+2];
temp-=10;
}
if(temp>4)out+=rn[2*i+1];
for(int j=0;j<temp%5;j++)out+=rn[2*i];
}
return out;
}
/**
* converts a roman numeral string to an integer
* @param n the input string
* @return the integer
*/
public int rn2i(String n) {
//2x0 100 500 4x0 1 2x0 50 1000 8x0 5 0 10
int[] nr={0,0,100,500,0,0,0,0,1,0,0,50,1000,0,0,0,0,0,0,0,0,5,0,10};
int ans=0;
int[] t=new int[n.length()+1];
for(int i=0;i<n.length();i++)t[i]=nr[n.charAt(i)-'A'];
for(int i=0;i<n.length();i++){
if(t[i+1]>t[i])ans-=t[i];
else ans+=t[i];
}
return ans;
}
Random Notes
/* other stuff
* *******************************************************
* MATH
perp has form -Bx+Ay=D, find d by plugging in any point
to reflect, find perp through one point, double the vector two the intersection
to rotate x' = xcos(0)-ysin(0) y'=xsin(0)+ycos(0)
dot product A.x*B.x+A.y*B.y+A.z*B.z = |A|*|B|*cos(theta)
cross product={A.y*B.z-A.z*B.y, A.z*B.x-A.x*B.z, A.x*B.y-A.y*B.x}
|A x B|=|A|*|B|*sin(theta)
can be used to determine what side of a line a point is on, or what direction a line turns (whether the z coordinate is positive or not)
euclidean distance =((x1-x2)^2+(y1-y2)^2+(z1-z)^2+....)^.5
law of sines sin(A)/a=sin(B)/b=sin(C)/c
law of consines c^2=a^2+b^2-s*a*b*cos(C)
area of triangle =1/2*b*h = 1/2*a*b*sin(C) = 1/2*c^2*sin(A)*sin(B)/sin(C)
area of a triangle based on 3 points A=1/2*(A.x*B.y+B.x*C.y+C.x*A.y-A.x*C.y-B.x*A.y-C.x-B.y)
area of triangle based on 3 side lengths A=sqrt(s*(s-a)*(s-b)*(s-c)) where s=1/2*(a+b+c)
triangle incircle is centered at intersection of angle bisectors
triangle outcircle is centered at intersection of perpendicular bisectors
least common denominator= a*b/gcd(a,b)
sum of first n numbers= n/2*(n+1)
sum of first n squares= n*(n+1)*(2n+1)/6
sum of first n cubes= (n/2*(n+1))^2
lcm(a,b)*gcd(a,b)=a*b
cramer's rule A=array of coefficients, x=det(A_x)/det(A) y=det(A_y)/det(A),
where A_? means replace the column representing that variable with the column of constants
************************************************************
PRINTF EXAMPLES
printf ("Characters: %c %c \n", 'a', 65);
printf ("Decimals: %d %ld\n", 1977, 650000L);
printf ("Preceding with blanks: %10d \n", 1977);
printf ("Preceding with zeros: %010d \n", 1977);
printf ("Some different radixes: %d %x %o %#x %#o \n", 100, 100, 100, 100, 100);
printf ("floats: %4.2f %+.0e %E \n", 3.1416, 3.1416, 3.1416);
printf ("Width trick: %*d \n", 5, 10);
printf ("%s \n", "A string");
Characters: a A
Decimals: 1977 650000
Preceding with blanks: 1977
Preceding with zeros: 0000001977
Some different radixes: 100 64 144 0x64 0144
floats: 3.14 +3e+000 3.141600E+000
Width trick: 10
A string
new DecimalFormat("#,###,##0.00").format(Math.min(1000000, b))
************************************************************
regex stuff:
Matcher m=Pattern.compile(regex).matcher(string);
JAVA OBJECTS AND METHODS
Native types:
int: 32 bytes from -2 billion to +2 billion
string->int Integer.parseInt(string,base)
int->string Integer.toString(int) Integer.toHexString,toBinaryString...etc
other methods
Integer .bitCount(i) number of 1's in the binary representation
.highest/lowestOneBit(i)
.numberOfLeading/TrailingZeros(i)
long: 64 bytes from -2^63 to 2^63
double: decimal number up to 2^128
char: character, useful to know you can subtract 'A' from chars to get index in the alphabet
String: just convert it to soemthing else
Containers:
Array:
must be created with a length int[] j=new int[25];
length can't change
methods:
Arrays .sort
.binarySearch --array must be sorted before hand...negative result indicates object not found
.copyOfRange --copies part of an array to a new array
.fill --fill an array with a value
.length
Collections:
Collection<T> j=new COllection<T>(oldCollection); creates j with all the elements of oldCollection
methods
COllections .binarySearch --list must be sorted
.copy --copies a list to a new list
.fill
.max
.min
.replaceAll --replaces all occurances of one thing with another
.reverse
.swap
.sort --use custome comparator or Colletions.reverseOrder() to sort backwards
List:
just a list of stuff
List .add/addAll
.contains/containsAll
.isEmpty
.indexOf
.remove/removeAll
.toArray
.size
ArrayList<T> j=new ArrayList<T>();
length can change, o(1) lookup/insert from back, o(n) insert/delete (from front)
LinkedList<T> j=new LinkedList<T>();
o(n) lookup, o(1) insert/delete at front/back
Set:
a container which only contains 1 of a given element
Set .add/addAll
.contains/containsAll
.isEmpty
.remove/RemoveAll
.size
.toArray
HashSet: o(1) for all operations
TreeSet: o(log(n)) for all operations, is sorted inherently
Treeset .ceiling --returns first object higher than the given object
.first
.floor --opposite of ceiling
.headset --returns a treeset of items lower than the given one
.last
.subSet --set between two given objects
.tailset --opposite of headset
Map:
maps a key to a value
Map .clear
.containsKey
.keySet
.put
.get
.remove
HashMap: only one you'll ever use, commonly HashMap<ArrayList<Integer>>
OTHER COllections:
Stack: can only get back the things you added in reverse order
stack .push --add something to the stack
.pop --get and remove the item at the top of the stack
.peek --check the item on top of the stack without removing
Queue: can only get back the oldest item in the list, must be a linked list Queue j=new LinkedList();
Queue .offer --add something to the queue
.poll --get and remove the front of the queue
.peek --check the front but dont remove
Priority Queue: sorted list that returns the lowest value thing, must instantiate with a size and a comparator
o(log(n)) add, o(log(n)) remove from front o(n) arbitrary remove
AWT objects:
Point: an x,y integer pair, often used to represent edges
Point .x/y the two values of the point
.translate move the point by the offsets given
.distance distance between two points
Point2D.Double: same as a point, but uses doubles instead of ints...useful sometimes
Line2D.Double: contains 2 points that define the line
.getBounds --returns a Rectangle defined by the box
.intersectsLine
.ptLineDist
.ptSegDist
Shape/Rectangle, I've never used, but useful for testing if a point is inside a given shape, taking intersections/etc
****************************************
dumb things to not do
corner cases
divide by zero error
xproduct=0
copying lines...double check EVERY change
exit condition
changes you made for simplicity breaking corner cases
correct mini-maxes
what's inside nested loops
initial doesn't work check
accidental overflow (including temporary from multiply before division)
double/integer division
multiple solutions to problem when you might not get right one(aka for dijkstras)
explicitly calculating number of times through loop instead of while()
lost bits off the front converting ints to strings (especially binary)
extra bits off the front converting strings to ints (negative numbers)
substrings off the end
number of integer partitions is SMALL
recursion base cases
mods with doubles
structs that get saved across test cases
looping over changing data (missing something)
treesets with common elements
rounding doubles without adding/subtracting an epison
comparing doubles without checking delta from one another
long+=double
1L before left shifting >32
extra teadline when switching what you're reading
don't compare arrays for equality without a custom comparator
make comparators consistent
print out your damn code
== instead of .equals
*/