单调递增的数组.
中等题,738的测试用例不是很完善,我四个月前提交的代码是错误的也能过用例,如277777,方法1返回的是269999,实际需要返回277777,方法2是正确的。思路就是贪心,两个指针,一个指针卡着第一个不是严格递增的位置,另外一个指针设置在for循环结束时候的前一个位置。也就是end位置合法,end+1不合法,如果end来到了终点位置,整个串都是单调递增的,返回原数。如果不是,回到第一个不是严格递增的位置,把后面的位置补0,把这个数减一,就是答案,如27777775,先变成27000000,减去1,变成26999999。代码如下
public int monotoneIncreasingDigits1(int N) {
char[] res = String.valueOf(N).toCharArray();
//把N变成了数组
int p = 0;
//记录第一个不是递增的位置
for(int i=1;i<res.length;i++){
if(res[i]>res[i-1]){
p=i;
}else if(res[i]<res[i-1]){
break;
}
}
if(p+1==res.length) return Integer.valueOf(new String(res));
while(++p!=res.length){
res[p] = '0';
}
return Integer.valueOf(new String(res))-1;
}
public int monotoneIncreasingDigits2(int N) {
String a = String.valueOf(N);
char[] b = a.toCharArray();
int p = 0, end = 0;
for(int i = 1; i < b.length; i++) {
if(b[i] > b[i-1]) p = i;
else if(b[i] < b[i-1]) {
break;
}
end = i;
}
if(end == b.length - 1) return Integer.valueOf(new String(b));
for(int i = p + 1; i <= b.length - 1; i++) b[i] = '0';
return Integer.valueOf(new String(b)) - 1;
}
单词规律.
简单题,用到哈希表。关键是利用map建立一个一一映射关系,一个map是不够的,还需要记录以及被加入到map里面的字符。
public boolean wordPattern(String pattern, String s) {
String[] b = s.split(" ");
char[] a = pattern.toCharArray();
if(a.length != b.length) return false;
HashMap<Character, String> map = new HashMap<>();
HashSet<String> set = new HashSet<>();
for(int i = 0; i < b.length; i++) {
if(!map.containsKey(a[i]) && !set.contains(b[i])) {
map.put(a[i], b[i]);
set.add(b[i]);
}else if(!map.containsKey(a[i]) && set.contains(b[i])) {
return false;
}else {
if(!map.get(a[i]).equals(b[i])) return false;
}
}
return true;
}