快手笔试工程A卷，前三道AC，第四题看不懂
第一题，求前面比他高的距离
public static int[] DistanceToHigher (int[] height) {
// write code here
int n = height.length;
int[] dp = new int[n];
for(int i=1;i<n;i++){
if(height[i]<height[i-1]){
dp[i] = 1;
}else{
int j = i-1;
while (j>0 && height[j] <= height[i]){
if(dp[j] == 0){
dp[i] = 0;
break;
}
j -= dp[j];
}
dp[i] = height[j] > height[i] ? i-j : 0 ;
}
}
return dp;
} 第二题，如果当前数左边有唯一一个比它大的数，输出当前数的下标，我用一个优先队列存最大值和第二大值，如果当前数大于等于第二大值，并且小于最大值，保存当前数下标，并更新优先队列
private static String findHelper(int[] nums) {
if(nums == null || nums.length < 2){
return "-1";
}
if(nums.length == 2){
return nums[1] < nums[0] ? "1" :"-1";
}
//用优先队列放最大的两个值
PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.add(nums[0]);
queue.add(nums[1]);
List<Integer> res = new ArrayList<>();
if(nums[0] > nums[1]){
res.add(1);
}
for(int i=2;i<nums.length;i++){
if(nums[i] >= queue.peek()){
queue.poll();
if(nums[i] < queue.peek()){
res.add(i);
}
queue.add(nums[i]);
}
}
String ans = res.size() == 0 ? "-1" : "";
for(int i=0;i<res.size();i++){
if(i == res.size()-1){
ans += res.get(i);
}else {
ans += res.get(i) + " ";
}
}
return ans;
} 第三题：靓号，这个比较暴力，写了一百多行……不建议看，大致思路是自定义个比较器，遍历当前号码判断是不是一个靓号，是的话就扔到集合里排序
static class Node{
int index;
int value;
//为顺子还是豹子 豹子为1 顺子0
int shunOrBao;
String phone;
public Node(int index,int value,int shunOrBao,String phone){
this.index = index;
this.value = value;
this.shunOrBao = shunOrBao;
this.phone = phone;
}
}
static class MyComparator implements Comparator<Node>{
@Override
public int compare(Node o1, Node o2) {
//先按价值大小
if(o1.value != o2.value){
return o2.value - o1.value;
}
//再按豹子顺子
if(o1.shunOrBao != o2.shunOrBao){
return o2.shunOrBao - o1.shunOrBao;
}
//最后是下标
return o1.index - o2.index;
}
}
private static String findHelper(String[] phones) {
PriorityQueue<Node> queue = new PriorityQueue<>(new MyComparator());
for(int j=0;j<phones.length;j++){
char[] cs = phones[j].toCharArray();
boolean isShun = false;
boolean isBao = false;
boolean isUp = false;
boolean isLess = false;
int count = 1;
int curMax = 1;
Node curPhone = null;
for(int i=4;i<cs.length;i++){
if(cs[i] == cs[i-1]){
//豹子
isBao = true;
if(isShun){
isShun = false;
count = 1;
}
count++;
}else if(cs[i] == cs[i-1]+1){
//上升的顺子
isShun = true;
if(isBao || isLess){
isBao = false;
isLess = false;
count = 1;
}
isUp = true;
count++;
}else if(cs[i] == cs[i-1]-1){
//下降的顺子
isShun = true;
if(isBao || isUp){
isBao = false;
isUp = false;
count = 1;
}
isLess= true;
count++;
}else{
isBao = false;
isShun = false;
isUp = false;
isLess = false;
count = 1;
}
if(count >= curMax && count >= 3){
if(curPhone == null){
curPhone = new Node(j,count,isBao ? 1 : 0,phones[j]);
}else if(count == curMax){
if(curPhone.shunOrBao == 0 && isBao){
curPhone.shunOrBao = 1;
}
}else if(count > curMax){
curPhone.shunOrBao = isBao ? 1 : 0;
curPhone.value = count;
}
curMax = count;
}
}
if(curPhone != null){
queue.add(curPhone);
}
}
if(queue.isEmpty()){
return "null";
}
StringBuilder res = new StringBuilder();
while (!queue.isEmpty()){
Node node = queue.poll();
if(queue.isEmpty()){
res.append(node.phone);
}else {
res.append(node.phone).append(",");
}
}
return res.toString();
} 
联想公司福利 1503人发布