前言
之前对算法方面看的太少了，现在补补课。
Mumbling
This time no story, no theory. The examples below show you how to write function accum:
Examples:
Accumul.accum(“abcd”); // “A-Bb-Ccc-Dddd” Accumul.accum(“RqaEzty”); // “R-Qq-Aaa-Eeee-Zzzzz-Tttttt-Yyyyyyy” Accumul.accum(“cwAt”); // “C-Ww-Aaa-Tttt” The parameter of accum is a string which includes only letters from a..z and A..Z.
best
public class Accumul {
public static String accum(String s) {
StringBuilder bldr = new StringBuilder();
int i = 0;
for(char c : s.toCharArray()) {
if(i > 0) bldr.append('-');
bldr.append(Character.toUpperCase(c));
for(int j = 0; j < i; j++) bldr.append(Character.toLowerCase(c));
i++;
}
return bldr.toString();
}
}
my
public class Accumul {
public static String accum(String s) {
char[] a = s.toUpperCase().toCharArray();
StringBuffer sum = new StringBuffer();
for (int i = 0; i < a.length; i++) {
char c = a[i];
sum.append(c);
for (int j = 0; j < i; j++) {
sum.append(Character.toLowerCase(c));
}
sum.append("-");
}
String str = sum.toString();
return str.substring(0,str.length()-1);
}
}
Descending Order
Your task is to make a function that can take any non-negative integer as a argument and return it with its digits in descending order. Essentially, rearrange the digits to create the highest possible number.
Examples: Input: 21445 Output: 54421
Input: 145263 Output: 654321
Input: 1254859723 Output: 9875543221
best
import java.util.Arrays;
import java.util.Collections;
public class DescendingOrder {
public static int sortDesc(final int num) {
String[] array = String.valueOf(num).split("");
Arrays.sort(array, Collections.reverseOrder());
return Integer.valueOf(String.join("", array));
}
}
my
public class DescendingOrder {
public static int sortDesc(final int num) {
String temp = Integer.toString(num);
int[] a = new int[temp.length()];
for (int i = 0; i < temp.length(); i++) {
a[i] = temp.charAt(i) - '0';
}
for (int i = 0; i < a.length; i++) {
for (int j = i+1; j < a.length; j++) {
if (a[i] < a[j]) {
a[i] += a[j];
a[j] = a[i]-a[j];
a[i] = a[i]-a[j];
}
}
}
StringBuffer strbuff = new StringBuffer();
for (int i : a) {
strbuff.append(i);
}
return new Integer(strbuff.toString()).intValue();
}
}
Decode the Morse code
In this kata you have to write a simple Morse code decoder. While the Morse code is now mostly superceded by voice and digital data communication channels, it still has its use in some applications around the world. The Morse code encodes every character as a sequence of “dots” and “dashes”. For example, the letter A is coded as ·−, letter Q is coded as −−·−, and digit 1 is coded as ·−−−. The Morse code is case-insensitive, traditionally capital letters are used. When the message is written in Morse code, a single space is used to separate the character codes and 3 spaces are used to separate words. For example, the message HEY JUDE in Morse code is ···· · −·−− ·−−− ··− −·· ·.
NOTE: Extra spaces before or after the code have no meaning and should be ignored.
In addition to letters, digits and some punctuation, there are some special service codes, the most notorious of those is the international distress signal SOS (that was first issued by Titanic), that is coded as ···−−−···. These special codes are treated as single special characters, and usually are transmitted as separate words.
Your task is to implement a function that would take the morse code as input and return a decoded human-readable string.
For example:
MorseCodeDecoder.decode(“…. . -.– .— ..- -.. .”) //should return “HEY JUDE” The Morse code table is preloaded for you as a dictionary, feel free to use it. In CoffeeScript, C++, Go, JavaScript, PHP, Python, Ruby and TypeScript, the table can be accessed like this: MORSE_CODE[’.–’], in Java it is MorseCode.get(‘.–’), in C# it is MorseCode.Get(‘.–’), in Haskell the codes are in a Map String String and can be accessed like this: morseCodes ! “.–”, in Elixir it is morse_codes variable.
All the test strings would contain valid Morse code, so you may skip checking for errors and exceptions. In C#, tests will fail if the solution code throws an exception, please keep that in mind. This is mostly because otherwise the engine would simply ignore the tests, resulting in a “valid” solution.
Good luck!
After you complete this kata, you may try yourself at Decode the Morse code, advanced.
best
public class MorseCodeDecoder {
public static String decode(String morseCode) {
String result = "";
for(String word : morseCode.trim().split(" ")) {
for(String letter : word.split("\\s+")) {
result += MorseCode.get(letter);
}
result += ' ';
}
return result.trim();
}
}
my
public class MorseCodeDecoder {
public static String decode(String morseCode) {
// your brilliant code here, remember that you can access the preloaded Morse code table through MorseCode.get(code)
String a[] = morseCode.trim().split(" ");
StringBuffer c = new StringBuffer();
for (int i = 0; i < a.length; i++) {
a[i] = MorseCode.get(a[i]);
if(a[i]==null){
c.append(" ");
} else {
c.append(a[i]);
}
}
return c.toString().replace(" ", " ");
}
}
Highest and Lowest
In this little assignment you are given a string of space separated numbers, and have to return the highest and lowest number.
Example:
HighAndLow(“1 2 3 4 5”) // return “5 1” HighAndLow(“1 2 -3 4 5”) // return “5 -3” HighAndLow(“1 9 3 4 -5”) // return “9 -5” Notes:
All numbers are valid Int32, no need to validate them. There will always be at least one number in the input string. Output string must be two numbers separated by a single space, and highest number is first.
best
import java.util.Arrays;
public class Kata {
public static String HighAndLow(String numbers) {
int min = Arrays.stream(numbers.split(" "))
.mapToInt(i -> Integer.parseInt(i))
.min()
.getAsInt();
int max = Arrays.stream(numbers.split(" "))
.mapToInt(i -> Integer.parseInt(i))
.max()
.getAsInt();
return String.format("%d %d", max, min);
}
}
my
public class Kata {
public static String HighAndLow(String numbers) {
String[] temp = numbers.split(" ");
int[] a = new int[temp.length];
for (int i = 0; i < a.length; i++) {
a[i] = Integer.valueOf(temp[i]);
}
for (int i = 0; i < a.length; i++) {
for (int j = i+1; j < a.length; j++) {
if (a[i] < a[j]) {
a[i] += a[j];
a[j] = a[i]-a[j];
a[i] = a[i]-a[j];
}
}
}
return (a[0]+" "+a[temp.length-1]);
}
}
Complementary DNA
Deoxyribonucleic acid (DNA) is a chemical found in the nucleus of cells and carries the “instructions” for the development and functioning of living organisms.
If you want to know more http://en.wikipedia.org/wiki/DNA
In DNA strings, symbols “A” and “T” are complements of each other, as “C” and “G”. You have function with one side of the DNA (string, except for Haskell); you need to get the other complementary side. DNA strand is never empty or there is no DNA at all (again, except for Haskell).
DnaStrand.makeComplement(“ATTGC”) // return “TAACG”
DnaStrand.makeComplement(“GTAT”) // return “CATA”
best
public class DnaStrand {
public static String makeComplement(String dna) {
dna = dna.replaceAll("A","Z");
dna = dna.replaceAll("T","A");
dna = dna.replaceAll("Z","T");
dna = dna.replaceAll("C","Z");
dna = dna.replaceAll("G","C");
dna = dna.replaceAll("Z","G");
return dna;
}
}
my
public class DnaStrand {
public static String makeComplement(String dna) {
String temp[] = dna.toUpperCase().split("");
StringBuilder retStr = new StringBuilder();
for (int i = 0; i < temp.length; i++) {
switch (temp[i]) {
case "A":
temp[i] = "T";
break;
case "T":
temp[i] = "A";
break;
case "C":
temp[i] = "G";
break;
case "G":
temp[i] = "C";
break;
default:
break;
}
retStr.append(temp[i]);
}
return retStr.toString();
}
}
You’re a square!
A square of squares You like building blocks. You especially like building blocks that are squares. And what you even like more, is to arrange them into a square of square building blocks!
However, sometimes, you can’t arrange them into a square. Instead, you end up with an ordinary rectangle! Those blasted things! If you just had a way to know, whether you’re currently working in vain… Wait! That’s it! You just have to check if your number of building blocks is a perfect square.
Task Given an integral number, determine if it’s a square number:
In mathematics, a square number or perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself.
The tests will always use some integral number, so don’t worry about that in dynamic typed languages.
Examples Square.isSquare(-1) // =false Square.isSquare( 3) // =false Square.isSquare( 4) // =true Square.isSquare(25) // =true Square.isSquare(26) // =false
best
import static java.lang.Math.*;
public class Square {
public static boolean isSquare(int n) {
return Math.sqrt(n) % 1 == 0;
}
}
my
public class Square {
public static boolean isSquare(int n) {
int d=1;//d=1,3,5...
int count=0;
while(n>0){
n-=d;
d+=2;
count++;
if(n==0){
return true;
}
}
return false; // fix me!
}
}
Square Every Digit
Welcome. In this kata, you are asked to square every digit of a number.
For example, if we run 9119 through the function, 811181 will come out, because 92 is 81 and 12 is 1.
Note: The function accepts an integer and returns an integer
best
public class SquareDigit {
public int squareDigits(int n) {
String result = "";
while (n != 0) {
int digit = n % 10 ;
result = digit*digit + result ;
n /= 10 ;
}
return Integer.parseInt(result) ;
}
}
my
public class SquareDigit {
public int squareDigits(int n) {
char[] b = Integer.toString(n).toCharArray();
StringBuilder d = new StringBuilder();
for (char c : b) {
int a = Integer.valueOf(String.valueOf(c));
d.append(a*a);
}
return new Integer(d.toString());
}
}
Sum of Digits / Digital Root
In this kata, you must create a digital root function.
A digital root is the recursive sum of all the digits in a number. Given n, take the sum of the digits of n. If that value has two digits, continue reducing in this way until a single-digit number is produced. This is only applicable to the natural numbers.
Here’s how it works (Ruby example given):
digital_root(16) =1 + 6 =7
digital_root(942) =9 + 4 + 2 =15 … =1 + 5 =6
digital_root(132189) =1 + 3 + 2 + 1 + 8 + 9 =24 … =2 + 4 =6
digital_root(493193) =4 + 9 + 3 + 1 + 9 + 3 =29 … =2 + 9 =11 … =1 + 1 =2
best
public class DRoot {
public static int digital_root(int n) {
return (n != 0 && n%9 == 0) ? 9 : n % 9;
}
}
my
public class DRoot {
public static int digital_root(int n) {
if (n < 10) {
return n;
} else {
int sum = 0;
int temp = 0;
while (n / 10 != 0) {
sum += n % 10;
n /= 10;
}
sum += n % 10;
return digital_root(sum);
}
}
}
Simple Encryption #1 - Alternating Split
For building the encrypted string: Take every 2nd char from the string, then the other chars, that are not every 2nd char, and concat them as new String. Do this n times!
Examples:
“This is a test!”, 1 -“hsi etTi sats!” “This is a test!”, 2 -“hsi etTi sats!” -“s eT ashi tist!” Write two methods:
String encrypt(final String text, final int n) String decrypt(final String encryptedText, final int n) For both methods: If the input-string is null or empty return exactly this value! If n is <= 0 then return the input text.
This kata is part of the Simple Encryption Series: Simple Encryption #1 - Alternating Split Simple Encryption #2 - Index-Difference Simple Encryption #3 - Turn The Bits Around Simple Encryption #4 - Qwerty
Have fun coding it and please don’t forget to vote and rank this kata! :-)
best
public class Kata {
public static String encrypt(final String text, int n) {
if (n <= 0 || text == null || text.isEmpty()) {
return text;
}
StringBuilder firstPart = new StringBuilder();
StringBuilder secondPart = new StringBuilder();
for (int i = 0; i < text.length(); i++) {
char aChar = text.charAt(i);
if (i % 2 == 1) {
firstPart.append(aChar);
} else {
secondPart.append(aChar);
}
}
return encrypt(firstPart.append(secondPart).toString(), --n);
}
public static String decrypt(final String encryptedText, int n) {
if (n <= 0 || encryptedText == null || encryptedText.isEmpty()) {
return encryptedText;
}
StringBuilder text = new StringBuilder();
final int half = encryptedText.length() / 2;
for (int i = 0; i < half; i++) {
text.append(encryptedText.charAt(half + i)).append(encryptedText.charAt(i));
}
if (encryptedText.length() % 2 == 1) {
text.append(encryptedText.charAt(encryptedText.length() - 1));
}
return decrypt(text.toString(), --n);
}
}
my
public class Kata {
public static String encrypt(final String text, final int n) {
if(text == null) {
return null;
}
if(text == "") {
return "";
}
char[] temp = text.toCharArray();
for (int i = 0; i < n; i++) {
String a = "", b = "";
for (int j = 0; j < temp.length; j++) {
if (j % 2 != 0) {
a += temp[j];
} else {
b += temp[j];
}
}
temp = (a + b).toCharArray();
}
return new String(temp);
}
public static String decrypt(final String encryptedText, final int n) {
if(encryptedText == null) {
return null;
}
if(encryptedText == "") {
return "";
}
char[] temp = encryptedText.toCharArray();
for (int i = 0; i < n; i++) {
char[] temp1 = new String(temp).substring(0, encryptedText.length()/2).toCharArray();
char[] temp2 = new String(temp).substring(encryptedText.length()/2).toCharArray();
for (int j = 0; j < temp.length; j++) {
if(j%2 == 0){
temp[j] = temp2[j/2];
} else {
temp[j] = temp1[j/2];
}
}
}
return new String(temp);
}
}
Human Readable Time
Write a function, which takes a non-negative integer (seconds) as input and returns the time in a human-readable format (HH:MM:SS)
HH = hours, padded to 2 digits, range: 00 - 99 MM = minutes, padded to 2 digits, range: 00 - 59 SS = seconds, padded to 2 digits, range: 00 - 59 The maximum time never exceeds 359999 (99:59:59)
You can find some examples in the test fixtures.
best
public class HumanReadableTime {
public static String makeReadable(int seconds) {
return String.format("%02d:%02d:%02d", seconds / 3600, (seconds / 60) % 60, seconds % 60);
}
}
my
public class HumanReadableTime {
public static String makeReadable(int seconds) {
String timeStr = null;
int hour = 0;
int minute = 0;
int second = 0;
if (seconds <= 0){
return "00:00:00";
}
else {
minute = seconds / 60;
if (minute < 60) {
second = seconds % 60;
timeStr = "00:"+unitFormat(minute) + ":" + unitFormat(second);
} else {
hour = minute / 60;
if (hour > 99)
return "99:59:59";
minute = minute % 60;
second = seconds - hour * 3600 - minute * 60;
timeStr = unitFormat(hour) + ":" + unitFormat(minute) + ":"
+ unitFormat(second);
}
}
return timeStr;
}
public static String unitFormat(int i) {
String retStr = null;
if (i >= 0 && i < 10)
retStr = "0" + Integer.toString(i);
else
retStr = "" + i;
return retStr;
}
}
Maximum subarray sum
The maximum sum subarray problem consists in finding the maximum sum of a contiguous subsequence in an array or list of integers:
Max.sequence(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}); // should be 6: {4, -1, 2, 1} Easy case is when the list is made up of only positive numbers and the maximum sum is the sum of the whole array. If the list is made up of only negative numbers, return 0 instead.
Empty list is considered to have zero greatest sum. Note that the empty list or array is also a valid sublist/subarray.
best
public class Max {
public static int sequence(int[] arr) {
int m = 0, a = 0, s = 0;
for(int e : arr) {
s += e;
m = Math.min(s, m);
a = Math.max(a, s - m);
}
return a;
}
}
my
public class Max {
public static int sequence(int[] arr) {
int curSum = 0;
int maxSum = 0;
int len = arr.length;
if (arr == null || len == 0) {
return 0;
}
for (int i = 0; i < len; i++) {
curSum += arr[i];
if (curSum < 0) {
curSum = 0;
}
if (curSum > maxSum) {
maxSum = curSum;
}
}
// all data are negative
if (maxSum == 0) {
for (int i = 0; i < len; i++) {
if (i == 0) {
maxSum = arr[i];
}
if (arr[i] > maxSum) {
maxSum = arr[i];
}
}
}
return maxSum;
}
}
