滴滴秋储笔试(2022年06月11日)
编程题
1) 给定一个数组,可以将任意一个数字标记为红色或者蓝色,使得所有红色数字递增,蓝色数字递减;
判断是否可以将所有数字都染色
例子:
输入:
7 4 1 3 2 5 6输出
Yes解释
7 4 3 标记为蓝色 为降序 1 2 5 6 标记为红色 为升序代码
boolean isIllegal(int[] values) {
// 让第一个数字为降序或者升序的一部分，进行dfs搜索
return dfs(values, 1, values[0], Integer.MAX_VALUE) || dfs(values, 1, Integer.MIN_VALUE, values[0]);
}
/**
* @param values
* @param index 当前搜索的数字
* @param preLower 升序序列的末尾
* @param preHigher 降序序列的末尾
* @return
*/
boolean dfs(int[] values, int index, int preLower, int preHigher) {
if (index >= values.length) return true;
// values[index] 作为升序序列的一部分
if (values[index] > preLower && dfs(values, index + 1, values[index], preHigher)) {
return true;
}
// values[index] 作为降序序列的一部分
if (values[index] < preHigher && dfs(values, index + 1, preLower, values[index])) {
return true;
}
// 都不行，返回false
return false;
} 
饿了么成长空间 132人发布
