2.7
如果字符串中不含有任何 'aaa','bbb' 或 'ccc' 这样的字符串作为子串,那么该字符串就是一个「快乐字符串」。
给你三个整数 a,b ,c,请你返回 任意一个 满足下列全部条件的字符串 s:
s 是一个尽可能长的快乐字符串。
s 中 最多 有a 个字母 'a'、b 个字母 'b'、c 个字母 'c' 。
s 中只含有 'a'、'b' 、'c' 三种字母。
如果不存在这样的字符串 s ,请返回一个空字符串 ""。
方法:贪心,思路比较简单,每次选取当前剩余数量最多的字母,如果连续两个了,就在剩下的两个里面选数量最多的,直到有两个剩余数量为零,则无法再扩展下去,返回答案即可。
方法一:使用数组维护当前剩余数量最多/次多的字母数
class Solution {
public String longestDiverseString(int a, int b, int c) {
// 构造一个数组来记录每个字母的剩余数量
//注意数组是int,保存的是char对应的ASCII码
int[][] pairs = {
{'a', a}, {'b', b}, {'c', c}};
//容量最大为a+b+c,不够也没关系
StringBuilder sb = new StringBuilder(a + b + c);
while (true) {
// 按数量从大到小排序
Arrays.sort(pairs,(x,y)->y[1]-x[1]);
int len=sb.length();
//如果最大的也为零,无法再拼接了
if(pairs[0][1]==0)break;
//数量最多的已经连用两次了,不能再用了
if(len>=2&&sb.charAt(len-1)==pairs[0][0]&&sb.charAt(len-2)==pairs[0][0]){
if(pairs[1][1]==0)break;
sb.append((char)pairs[1][0]);
pairs[1][1]--;
}//数量最多的还没用到两次,还能再用
else{
sb.append((char)pairs[0][0]);
pairs[0][1]--;
}
}
return sb.toString();
}
}
方法二:使用优先队列维护,实际上相当于队列里存了三个数组,也就是用来代替pairs的
一个不同之处:如果取出来的数组[1]==0,则不再入列,这样可以减小维护成本
class Solution {
public String longestDiverseString(int a, int b, int c) {
// 大顶堆,数量多的在最上面
PriorityQueue<int[]> heap = new PriorityQueue<>((x, y) -> y[1] - x[1]);
// 初始化入堆,初始数量为零就不用了
if (a > 0) {
heap.offer(new int[] {'a', a});
}
if (b > 0) {
heap.offer(new int[] {'b', b});
}
if (c > 0) {
heap.offer(new int[] {'c', c});
}
StringBuilder sb = new StringBuilder(a + b + c);
while (!heap.isEmpty()) {
//大根堆,出来的是当前剩余数量最多的字母
int[]max=heap.poll();
int len=sb.length();
//最大值用了两次,不能再用
if(len>=2&&sb.charAt(len-1)==max[0]&&sb.charAt(len-2)==max[0]){
//首先要确保有次大值还在
if(!heap.isEmpty()){
//取次大值
int[]mid=heap.poll();
sb.append((char)mid[0]);
mid[1]--;
if(mid[1]>0){
heap.offer(mid);
}
//容易遗漏的是,即使用的是次大值,也要将最大值加入堆中
heap.offer(max);
}else{
//若不在直接返回
break;
}
}else{
sb.append((char)max[0]);
max[1]--;
if(max[1]>0){
heap.offer(max);
}
}
}
return sb.toString();
}
}
2.8
在大小为 n x n 的网格 grid 上,每个单元格都有一盏灯,最初灯都处于 关闭 状态。
给你一个由灯的位置组成的二维数组 lamps ,其中 lamps[i] = [rowi, coli] 表示 打开 位于 grid[rowi][coli] 的灯。即便同一盏灯可能在 lamps 中多次列出,不会影响这盏灯处于 打开 状态。
当一盏灯处于打开状态,它将会照亮 自身所在单元格 以及同一 行 、同一 列 和两条 对角线 上的 所有其他单元格 。
另给你一个二维数组 queries ,其中 queries[j] = [rowj, colj] 。对于第 j 个查询,如果单元格 [rowj, colj] 是被照亮的,则查询结果为 1 ,否则为 0 。在第 j 次查询之后 [按照查询的顺序] ,关闭 位于单元格 grid[rowj][colj] 上及相邻 8 个方向上(与单元格 grid[rowi][coli] 共享角或边)的任何灯。
返回一个整数数组 ans 作为答案, ans[j] 应等于第 j 次查询 queries[j] 的结果,1 表示照亮,0 表示未照亮。
网格大小n*n,n可以取到10^9,显然会TLE,因此我们用哈希表记录每一盏灯照亮的行列斜,并用集合记录所有灯的位置,为了节省空间,还要讲点的坐标二维转一维(即哈希变换)
class Solution {
int N;
public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
N=n;
int[][] dirs = new int[][]{
{0,0},{0,-1},{0,1},{-1,0},{-1,-1},{-1,1},{1,0},{1,-1},{1,1}};
Map<Integer,Integer>row=new HashMap<>(),col=new HashMap<>(),
left=new HashMap<>(),right=new HashMap<>();
Set<Long>set=new HashSet<>();
//记录所有亮着的灯和格子
for(int[]l:lamps){
int x=l[0],y=l[1];
int a=x+y,b=x-y;
if(set.contains(hash(x, y)))continue;
//亮灯数据更新
set.add(hash(x, y));
add(row, x);
add(col, y);
add(left, a);
add(right, b);
}
int m=queries.length;
int[]ans=new int[m];
//处理查询
for(int i=0;i<m;i++){
int[]q=queries[i];
int x=q[0],y=q[1];
int a=x+y,b=x-y;
//五种点亮方式
if(set.contains(hash(x, y))||row.containsKey(x)||col.containsKey(y)||left.containsKey(a)||right.containsKey(b)){
ans[i]=1;
}
//九宫格内如果有灯就熄灯
for(int[]dir:dirs){
int dx=x+dir[0],dy=y+dir[1];
if (dx < 0 || dx >= n || dy < 0 || dy >= n) continue;
//如果找到了灯,则灭灯并消除影响
if(set.contains(hash(dx, dy))){
set.remove(hash(dx, dy));
minus(row, dx);
minus(col, dy);
minus(left, dx+dy);
minus(right, dx-dy);
}
}
}
return ans;
}
//二维转一维,将所有点用一个Long型数据表示并存储
long hash(int x,int y){
return x*N+y;
}
//哈希表数据++
void add(Map<Integer,Integer>map,int key){
map.put(key, map.getOrDefault(key, 0)+1);
}
//灭灯,哈希表数据--
//注意其实我们的运算过程保证了不会出现default这个情况,但是为了安全还要有
void minus(Map<Integer,Integer>map,int key){
if (map.getOrDefault(key,0) == 1) map.remove(key);
else map.put(key, map.getOrDefault(key,0) - 1);
}
}
2.9
给你一个整数数组 nums 和一个整数 k ,请你返回数对 (i, j) 的数目,满足 i < j 且 |nums[i] - nums[j]| == k 。
|x| 的值定义为:
如果 x >= 0 ,那么值为 x 。
如果 x < 0 ,那么值为 -x 。
这题和第一题两数之和极像,方式自然也有两种了!
方法一:双重遍历
class Solution {
public int countKDifference(int[] nums, int k) {
int ans=0,n=nums.length;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(Math.abs(nums[i]-nums[j])==k)ans++;
}
}
return ans;
}
}
方法二:哈希表
class Solution {
public int countKDifference(int[] nums, int k) {
int ans=0,n=nums.length;
HashMap<Integer,Integer>map=new HashMap<>();
for(int i=0;i<n;i++){
map.put(nums[i],map.getOrDefault(nums[i],0)+1);
ans+=map.getOrDefault(nums[i]-k,0)+map.getOrDefault(nums[i]+k,0);
}
return ans;
}
}
文章评论