第一题是判断中位数和平均数哪个大
平均数直接求。
中位数可以加速一点，利用快速排序是思想。
/**
*
* @param arr int整型一维数组
* @return int整型
*/
public int Answerofjudge (int[] arr) {
// write code here
//先求平均数
double count = 0;
for (int i = 0; i < arr.length; i++) {
count = count + arr[i];
}
double avg = count/arr.length;
double mid = 0;
BigDecimal b1 = new BigDecimal(Double.toString(avg));
if (arr.length%2 != 0) {//中位数直接取的情况
mid = quickSortFind(arr, 0, arr.length-1, arr.length/2);
}else {//中位数需要除以2的情况（可以优化为一次快排，略）
double m1 = quickSortFind(arr, 0, arr.length-1, arr.length/2);
double m2 = quickSortFind(arr, 0, arr.length-1, arr.length/2-1);
mid = (m1+m2)/2;
}
BigDecimal b2 = new BigDecimal(Double.toString(mid));
//浮点数的比较，需要注意
return b2.compareTo(b1);
}
/**
*
* @param arr
* @param low
* @param high
* @param target 第n大数字的索引
* @return 第n大数字
*/
private static int quickSortFind(int[] arr, int low, int high,int target) {
int i = low;
int j = high;
int temp;
while (i < j) {
while (arr[j] >= arr[low] && i < j) {
j--;
}
while (arr[i] <= arr[low] && i < j) {
i++;
}
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
temp = arr[low];
arr[low] = arr[j];
arr[j] = temp;
if (target == j) {
return arr[j];
} else if (target < j) {
return quickSortFind(arr, low, j-1, target);
} else {
return quickSortFind(arr, j+1, high, target);
}
}
第二题有点类似leetcode的“买卖股票的最佳时机”
我这里也是使用的一次遍历法
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 返回符合题意的最长的子串长度
* @param x string字符串
* @return int整型
*/
public int Maximumlength (String x) {
// write code here
int ans = 0;
int count = 0;//当前最大符合题意子串
char[] chars = x.toCharArray();
int n = -1;//n出现的索引
int p = -1;//p出现的索引
int y = -1;//y出现的索引
for (int i = 0; i < chars.length; i++) {
//分情况记录
if (chars[i] == 'n') {
n = i;
} else if (chars[i] == 'p'){
p = i;
}else if (chars[i] == 'y'){
y = i;
}
//npy同时出现，把最小的index（i）替换，重置count
if (n != -1&& p!= -1 &&y!=-1) {
int min = -1;
if (n<p&&n<y) {
min =n;
n = -1;
}else if (p<y&&p<n) {
min = p;
p = -1;
}else {
min =y;
y = -1;
}
ans = Math.max(ans,count );
count = i-min;
} else {
count ++;
ans = Math.max(ans,count );
}
}
return ans;
} 第三题 其实就是利用栈 /**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 给定一个后缀表达式，返回它的结果
* @param str string字符串
* @return long长整型
*/
public long solve (String str) {
Stack<Long> stack = new Stack<>();
String num = "";
long x1,x2;
for(int i = 0;i < str.length();++i)
{
char c = str.charAt(i);
if(c == '#')
continue;
if(c == '+')
{
x1 = stack.pop();
x2 = stack.pop();
stack.push(x1 + x2);
}
else if(c == '-')
{
x1 = stack.pop();
x2 = stack.pop();
stack.push(x2 - x1);
}
else if(c == '*')
{
x1 = stack.pop();
x2 = stack.pop();
stack.push(x1 * x2);
}
else
{
num = "";
while(c != '#')
{
num += c;
i++;
c = str.charAt(i);
}
stack.push(Long.parseLong(num));
}
}
return stack.pop();
} 
全部评论
(0) 回帖