Skip to content

Instantly share code, notes, and snippets.

@bdunovska

bdunovska/Change.java

Last active September 24, 2015 23:04
Show Gist options
  • Save bdunovska/1d700a0f0c3316df81ae to your computer and use it in GitHub Desktop.
Save bdunovska/1d700a0f0c3316df81ae to your computer and use it in GitHub Desktop.
Download ZIP
CodeU Final Exercises.
Raw
Change.java
/**
* Created by belladunovska on 09/09/15.
*/
public class Change {
/**
* Helper method to compute the ways to make a change using recursion.
*
* @param n cents
* @param coins possible values
* @param acc intermediate holder value
* @return the number of ways to make a change.
*/
public int makeChange(int n, int[] coins, int acc) {
if (n == 0) {
return 1;
} else if (n < 0 || coins.length == acc) {
return 0;
} else {
int withFirstCoin = makeChange(n - coins[acc], coins, acc);
int withoutFirstCoin = makeChange(n, coins, acc + 1);
return withFirstCoin + withoutFirstCoin;
}
}
public int makeChange(int n, int[] coins) {
return makeChange(n, coins, 0);
}
Raw
Palindrome.java
/**
* Created by belladunovska on 08/09/15.
*/
public class Palindrome {
/***
* Method to find the kth palindrome binary representation.
* @param k
* @return the integer with the corresponding binary palindrome.
*/
public int palinrome(int k) {
int counter = 0;
int largestPalindrome = 0;
while (k >= 0) {
if (isPalindrome(binaryRepresentation(counter))) {
k--;
largestPalindrome = counter;
}
counter++;
}
return largestPalindrome;
}
/**
* Method to check if a string is a palindrome
*
* @param sequence the string to be checked
* @return true if it is, false otherwise
*/
public boolean isPalindrome(String sequence) {
boolean isPalindrom = true;
for (int i = 0; i < sequence.length(); i++) {
if (sequence.charAt(i) != sequence.charAt(sequence.length() - 1 - i)) {
isPalindrom = false;
}
}
return isPalindrom;
}
/**
* Method to return the binary representation of an integer.
*
* @param n the integer
* @return a binary string representation of the integer
*/
public String binaryRepresentation(int n) {
return Integer.toBinaryString(n);
}
Raw
PalindromeString.java
/**
* Created by belladunovska on 08/09/15.
*/
public class PalStirng {
/**
* Helper method to find a palindrome starting from its middle or two middle elemnets.
*
* @param s the sequence of characters
* @param left the index to start from and continue to the left
* @param right the index to start from and continue to the right
* @return the length of the palindrome found with this middle
*/
public int intermediatePalindromeLength(String s, int left, int right) {
if (left > right) return 0;
while (left >= 0 && right < s.length()
&& s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return (right - 1) - left;
}
/**
* Method that returns the wanted values by finding the palindrome.
*
* @param s the sequence of string that we search through for the longest palindrome.
* @return a pair of index and length
*/
public Pair<Integer, Integer> longestPalindromeString(String s) {
if (s == null || s.length() == 0) return null;
int longestLength = 1;
int position = 0;
for (int i = 0; i < s.length() - 1; i++) {
int palindromeLength = intermediatePalindromeLength(s, i, i);
if (palindromeLength > longestLength) {
longestLength = palindromeLength;
position = i;
}
palindromeLength = intermediatePalindromeLength(s, i, i + 1);
if (palindromeLength > longestLength) {
longestLength = palindromeLength;
position = i;
}
}
return new Pair<Integer, Integer>(position - longestLength / 2, longestLength);
}
Raw
SplitString.java
/**
* Created by belladunovska on 09/09/15.
*/
public class SplitString {
private ArrayList<String> sentence = new ArrayList<String>();
private String dictionary[] = {
"alpha", "beta", "cupcake", "donut", "eclair", "froyo",
"gingerbread", "honeycomb", "ice", "cream", "sandwich",
"jelly", "bean", "kitkat", "lollipop", "marshmellow"};
/**
* Helper method to check if a word is present in our dictionary
* @param: word
* the word that we need to check in the dictionary
* @return true if the word is in the dictionary,
* false if it is not.
*/
public boolean isInDictionary(String word) {
for (String s : dictionary) {
if (s.equals(word))
return true;
}
return false;
}
/**
* Method that fills an array list with words if they are proper words.
* @param: word
* the word to be broken in a sentence
*/
public void splitWord(String word) {
if (word.length() == 0) return;
for (int i = 1; i <= word.length(); i++) {
if (isInDictionary(word.substring(0, i))) {
sentence.add(word.substring(0, i));
splitWord(word.substring(i));
return;
}
}
}
/**
* Method to print the sentence.
* @param: string
* the string that we want to print as a sentence, if it is appropriate against our dictioanry.
*/
public void printSentence(String string) {
splitWord(string);
if (sentence.size() == 2) {
for (String word : sentence) {
System.out.print(word + " ");
}
} else {
System.out.print("Sorry, no match ");
}
}
Raw
UglyNumbers.java
/**
* Created by belladunovska on 08/09/15.
*/
public class UglyNumbers {
/**
* Method to print the kth number in the sequence of all ugly numbers.
* @param k
*/
public void printKthUgly(int k) {
String result = "";
if (k > 0) {
int[] uglies = new int[k];
uglies[0] = 1;
int nextIndex = 1;
int positionWithTwo = 0;
int positionWithThree = 0;
int positionWithFive = 0;
while (nextIndex < k) {
uglies[nextIndex] = Math.min(Math.min(uglies[positionWithTwo] * 2, uglies[positionWithThree] * 3), uglies[positionWithFive] * 5);
while (uglies[positionWithTwo] * 2 <= uglies[nextIndex])
++positionWithTwo;
while (uglies[positionWithThree] * 3 <= uglies[nextIndex])
++positionWithThree;
while (uglies[positionWithFive] * 5 <= uglies[nextIndex])
++positionWithFive;
nextIndex++;
}
result = String.valueOf(uglies[k - 1]);
}
System.out.print(result);
}
@tiziano88
Copy link

Hey it seems it's not possible to comment on individual lines on a Gist, any chance you could turn this into a normal Git repository? If not, let me know and I'll fork it or figure out something else, thanks!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment