java - Java - Google Foobar 挑战 2:“请传递编码消息”
问题描述
我很好奇为什么我的代码除了第四个测试用例之外都通过了。
如果您参与过 Google 的 Foobar 挑战,您可能会知道测试用例是隐藏的,您从终端收到的唯一响应是“通过”或“失败”。到目前为止,尽管 Java 不是我的首选,但这个挑战一直是个大问题。
该算法是接收一个整数数组(范围为 0-9)并输出一个密码。我已经确定解决方案代码是通过按降序对数组进行排序、将其转换为字符串并从该数字(从右到左)中删除尽可能少的数字以使其可被 3 整除来获得的。
给出的测试用例:
//input:
int[] l = { 3, 1, 4, 1 };
//output:
int solution = 4311;
//input:
int[] l = { 3, 1, 4, 1, 5, 9 };
//output:
int solution = 94311;
这是我的代码:
//Foobar gives you this static class and no external dependencies.
//The driver code looks like "Solution.solution({input int array});", which must return Integer type.
public class Solution {
public static int solution(int[] l) {
//reverse sort and get value as both String and int (to take advantage of String manipulation options).
quickSort(l, 0, l.length-1);
String str = arrayToStringReverse(l);
//Handle as long datatype to retain the ability to return up to Integer.MAX_VALUE.
long num = Long.parseLong(str);
num = (num % 3 == 0) ? num : makeDivisibleByThree(str);
//Handle solutions exceeding Integer.MAX_VALUE.
return((num > Integer.MAX_VALUE) ? 0 : ((int)num));
}
public static long makeDivisibleByThree(String str) {
int pass = 1;
int size = str.length() - 1;
//If the number of digits cannot be removed, return early with 0.
if(str.length() == pass) return(0);
StringBuilder stb = new StringBuilder();
int index = size;
//crawl from right to left
for(int i = size; i >= 0; i--) {
//start with a new copy of the original string each itr.
stb.replace(0, size, str);
//remove n=pass digits.
for(int x = 0; x < pass; x++) {
stb.deleteCharAt(index - x);
}
//check if divisible by 3. if not, increment the index right.
if(Long.parseLong(stb.toString()) % 3 == 0) {
return(Long.parseLong(stb.toString()));
}else {
index--;
}
//if current pass completed without success, reset increment variables and continue for consecutive pass (iteratively removing an extra digit).
if(i == 0) {
pass++;
//Return early if number of digits to be removed exceeds number of digits of the string being operated on.
if(str.length() == pass) return(0);
index = size;
i = size;
continue;
}
}
return(0);
}
//I've minified these functions, as they are generic and work fine.
public static String arrayToStringReverse(int[] arr){String rs="";for(int i=arr.length-1;i>=0;i--){rs+=arr[i];}return(rs);}
public static void quickSort(int arr[],int begin,int end){if(begin<end){int partitionIndex=partition(arr,begin,end);quickSort(arr,begin,partitionIndex-1);quickSort(arr,partitionIndex+1,end);}}
public static int partition(int arr[],int begin,int end){int pivot=arr[end];int i=(begin-1);for(int j=begin;j<end;j++){if(arr[j]<=pivot){i++;int swapTemp=arr[i];arr[i]=arr[j];arr[j]=swapTemp;}}int swapTemp=arr[i+1];arr[i+1]=arr[end];arr[end]=swapTemp;return i+1;}
}
/*
I've also found that test case 5 should return 0, for whatever that's worth.
My code is currently passing all but case #4.
*/
任何人都可以给我一些建议或建议我可能忽略的任何事情吗?
解决方案
推荐阅读
- javascript - 如何在 JavaScript 中使用 CDK 将资源策略添加到现有 S3 存储桶?
- c# - WPF 中的井字游戏 GUI
- jquery - Jquery - 查找包含具有给定文本值的特定类的类的 div
- angular - 取消订阅 location.onUrlChange()
- c++ - C++ 结构冒泡排序
- sas - SAS:数据集合并并打印出完整的变量列表,但找不到供将来使用的变量
- sql - SQL 子查询:显示购买了两件商品的 Customer_ID
- mysql - 在sql中合并具有不同行数的2个不同列后,如何使重复值变为null?
- r - 在 R Markdown 中,如何使用超链接创建对引用的引用?
- javascript - 如何检查作为字符串带来的变量是否是 Javascript 中的数字或字母?