- 1446. 连续字符">1446. 连续字符
- 506. 相对名次">506. 相对名次
- 1005. K 次取反后最大化的数组和">1005. K 次取反后最大化的数组和
- 383. 赎金信">383. 赎金信
- 372. 超级次方">372. 超级次方
- 1816. 截断句子">1816. 截断句子
- 1034. 边界着色">1034. 边界着色
- 794. 有效的井字游戏">794. 有效的井字游戏
- 748. 最短补全词">748. 最短补全词
- 911. 在线选举">911. 在线选举
- 709. 转换成小写字母">709. 转换成小写字母
- 807. 保持城市天际线">807. 保持城市天际线
- 630. 课程表 III">630. 课程表 III
- 851. 喧闹和富有">851. 喧闹和富有
- 1518. 换酒问题">1518. 换酒问题
- 419. 甲板上的战舰">419. 甲板上的战舰
- 997. 找到小镇的法官">997. 找到小镇的法官
- 475. 供暖器">475. 供暖器
- 1154. 一年中的第几天">1154. 一年中的第几天
- 686. 重复叠加字符串匹配">686. 重复叠加字符串匹配
- 1705. 吃苹果的最大数目">1705. 吃苹果的最大数目
- 1609. 奇偶树">1609. 奇偶树
- 1078. Bigram 分词">1078. Bigram 分词
- 825. 适龄的朋友">825. 适龄的朋友
- 1995. 统计特殊四元组">1995. 统计特殊四元组
- 846. 一手顺子">846. 一手顺子
- 507. 完美数">507. 完美数
1446. 连续字符
class Solution {public:int maxPower(string s) {if(s.size()==1)return 1;int maxLen=1,cnt=1;//初始化最大长度以及计数值都为1for(int i=0;i<s.size()-1;i++){if(s[i]==s[i+1]){cnt++;//遇到相同字符计数+1maxLen=max(maxLen,cnt);//更新最大长度}elsecnt=1;//遇到不同的字符 计数重新开始}return maxLen;}};//O(n)//O(1)
506. 相对名次
用一个map记录对应分数和下标，然后再对分数进行排序，最后根据排序后的分数获取下标给对应的位置存放答案即可
class Solution {public String[] findRelativeRanks(int[] score) {String []ans=new String[score.length];HashMap<Integer,Integer> map=new HashMap<>();for(int i=0;i<score.length;i++){map.put(score[i],i);//记录分数和对应的下标}Arrays.sort(score);for(int i=score.length-1;i>=0;i--){int index=map.get(score[i]);if(i==score.length-1)ans[index]="Gold Medal";else if(i==score.length-2)ans[index]="Silver Medal";else if(i==score.length-3)ans[index]="Bronze Medal";elseans[index]=String.valueOf(score.length-i);}return ans;}}//O(nlogn)//O(n)
1005. K 次取反后最大化的数组和
记cnt为数组中负数出现的次数 flag表示数组中是否有0出现 id表示数组元素中绝对值最小的元素的下标
- cnt>=k 此时将数组在所有的负数取反即可
- cnt<k 先将数组中的cnt个负数取反 此时还需要取反k-cnt次 k=k-cnt
2.1 若剩余的k是偶数或者有0出现 最终的结果不变 2.2 若剩余的k是计数并且有0出现 则需要将数组中绝对值最小的元素取反
class Solution {public int largestSumAfterKNegations(int[] nums, int k) {int ans=0;int id=0;//记录绝对值最小的元素的下标boolean flag=false;//表示数组中是否出现0//q中存放的是数组下标 根据数组元素升序来排列的下标PriorityQueue<Integer> q=new PriorityQueue<>((a,b)->nums[a]-nums[b]);for(int i=0;i<nums.length;i++){if(nums[i]<0)q.offer(i);if(nums[i]==0)flag=true;if(Math.abs(nums[i])<Math.abs(nums[id]))id=i;}if(k<=q.size())//负数个数>=k{for(int i=0;i<k;i++){nums[q.peek()]=-nums[q.peek()];q.poll();}}else//负数个数<k{//先将所有的负数取反while(!q.isEmpty()){nums[q.peek()]=-nums[q.peek()];q.poll();k--;}//剩下的k次是奇数if(!flag&&k%2==1)nums[id]=-nums[id];}for(int num:nums)ans+=num;return ans;}}//O(nlogn)//O(n)
先对数组的负数进行取反并求和，最后判断剩余的k是不是奇数，如果是奇数就对数组中绝对值最小的元素取反，由于前面求和加的是绝对值，这里取反之后相当于和减去2倍的绝对值
class Solution {
public int largestSumAfterKNegations(int[] nums, int k) {
Arrays.sort(nums);
int ans=0,minVal=Integer.MAX_VALUE;
for(int i=0;i<nums.length;i++)
{
if(nums[i]<0&&k>0)
{
nums[i]=-nums[i];
k--;
}
ans+=nums[i];
minVal=Math.min(minVal,nums[i]);
}
if(k%2!=0)
ans-=2*minVal;
return ans;
}
}
//O(nlogn)
//(n)
383. 赎金信
先遍历一遍magazine字符串，记录下该字符串中各个字符出现的次数，由于只有小写字母，因此可以使用一个大小为26的整型数组；之后再遍历ransomNote字符串时，每次对相应的字符个数进行减减操作，如果发现个数<0，则返回false
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int count[]=new int[26];
for(int i=0;i<magazine.length();i++)
count[magazine.charAt(i)-'a']++;
for(int i=0;i<ransomNote.length();i++)
{
if(--count[ransomNote.charAt(i)-'a']<0)
return false;
}
return true;
}
}
//O(max(m,n) m n分别是ransomNote字符串 magazine字符串的长度
//O(1)
372. 超级次方
通过上述形式的数学公式，不断的对ab进行分解，对分解后的部分单独取余，最后将结果乘在一起
class Solution {
public int superPow(int a, int[] b) {
return dfs(a,b,b.length-1);
}
public int dfs(int a,int []b,int x)
{
if(x==-1)
return 1;
return pow(dfs(a,b,x-1),10)*pow(a,b[x])%1337;
}
public int pow(int a,int x)
{
int ans=1;
a=a%1337;
while(x-->0)
{
ans=ans*a%1337;
}
return ans;
}
}
//O(n*10) 调用n次pow函数 每次pow中循环执行10次
//O(n) 递归的空间消耗
1816. 截断句子
思路1：直接使用字符传的split函数获得一个字符串数组，然后用StringBuiler逐个连接即可
class Solution {
public String truncateSentence(String s, int k) {
String words[]=s.split(" ");
StringBuilder sb=new StringBuilder();
for(int i=0;i<k;i++)
{
sb.append(words[i]);
if(i!=k-1)
sb.append(" ");
}
return sb.toString();
}
}
//O(k)
//O(len) len是k个单词的总长度
思路2：直接用一个index记录下k个单词加上k-1个空格的长度 然后s.substring(0,index) 即可
class Solution {
public String truncateSentence(String s, int k) {
int index=0;
while(index<s.length())
{
if(s.charAt(index)==' ')
k--;
if(k==0)
break;
index++;
}
return s.substring(0,index);
}
}
//O(n)
//O(1)
1034. 边界着色
题目大意： 给定一个网格，将这个网格所在的连通分量的边界着色 连通分量的边界判断：对于一个网格grid[x][y], 在上下左右四个方向如果都有同一个连通分量的网格与之相连则grid[x][y]不是边界，否则是边界 因此可以采用dfs或bfs的办法，不要直接修改原来的数组grid, 因为在计算中需要使用grid原始的数值进行判断，因此可以创建一个新的数组ans来保存染色的值，最后再将未染色的值赋值进ans数组，使用一个标记数组visited,由于各个解答只需要访问一次，因此访问标记不需要还原
class Solution {
int ans[][];
int grid[][];
int dirs[][]=new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
int m,n,color;
boolean visited[][];
public int[][] colorBorder(int[][] grid, int row, int col, int color) {
this.grid=grid;
this.m=grid.length;
this.n=grid[0].length;
this.color=color;
this.ans=new int[m][n];
visited=new boolean[m][n];
dfs(row,col);
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
if(ans[i][j]==0)
ans[i][j]=grid[i][j];
}
return ans;
}
public void dfs(int x,int y)
{
int cnt=0;
visited[x][y]=true;
for(int dir[]:dirs)
{
int nx=x+dir[0],ny=y+dir[1];
if(nx<0||nx>=m||ny<0||ny>=n)
continue;
if(grid[x][y]!=grid[nx][ny])
continue;
else
cnt++;
if(visited[nx][ny]==true)
continue;
visited[nx][ny]=true;
dfs(nx,ny);
}
ans[x][y]=cnt==4?grid[x][y]:color;//染色+还原标记
}
}
//O(m*n)
//O(m*n)
class Solution {
public int[][] colorBorder(int[][] grid, int row, int col, int color) {
int dirs[][]=new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
int m=grid.length,n=grid[0].length;
int ans[][]=new int[m][n];
boolean visited[][]=new boolean[m][n];
Queue<int[]> q=new LinkedList<>();
q.offer(new int[]{row,col});
while(!q.isEmpty())
{
int p[]=q.poll();
int x=p[0],y=p[1];
int cnt=0;
visited[x][y]=true;
for(int dir[]:dirs)
{
int nx=x+dir[0],ny=y+dir[1];
if(nx<0||nx>=m||ny<0||ny>=n)
continue;
if(grid[x][y]!=grid[nx][ny])
continue;
else
cnt++;
if(visited[nx][ny]==true)
continue;
q.offer(new int[]{nx,ny});
}
ans[x][y]=cnt==4?grid[x][y]:color;
}
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
if(ans[i][j]==0)
ans[i][j]=grid[i][j];
}
return ans;
}
}
//O(m*n)
//O(m*n)
794. 有效的井字游戏
记录游戏板中的X和O出现的次数，并且判断板子中的X和O是否可以连接成功 记：countX为游戏板中X的出现次数，countO为游戏板中O出现的次数，isX为true表示X可以连接成功，isO表示O可以连接成功，则分为以下几种情况：
- countO>countX —->false O的个数不能大于X的个数
- countX-countO>1—->false X的个数不能比O的个数多超于1个
- isX&&countO>=countX—->false X连接成功时，O的个数只可能小于X的个数
- isO&&countO!=countX——>false O连接成功时，O的个数只能等于X的个数
class Solution {
public boolean validTicTacToe(String[] board) {
int countX=0,countO=0;
boolean isX,isO;
char b[][]=new char[3][3];
for(int i=0;i<board.length;i++)
{
String s=board[i];
for(int j=0;j<s.length();j++)
{
if(s.charAt(j)=='X')
countX++;
if(s.charAt(j)=='O')
countO++;
}
}
isX=judge(board,'X');
isO=judge(board,'O');
if(countO>countX||countX-countO>1)
return false;
else if(isX&&countO>=countX)
return false;
else if(isO&&countX!=countO)
return false;
return true;
}
public boolean judge(String[] board,char c)
{
for(int i=0;i<3;i++)
{
if(board[i].charAt(0)==c&&board[i].charAt(1)==c&&board[i].charAt(2)==c)
return true;
if(board[0].charAt(i)==c&&board[1].charAt(i)==c&&board[2].charAt(i)==c)
return true;
}
boolean a1=board[0].charAt(0)==c&&board[1].charAt(1)==c&&board[2].charAt(2)==c;
boolean a2=board[0].charAt(2)==c&&board[1].charAt(1)==c&&board[2].charAt(0)==c;
return a1||a2;
}
}
//O(C) 常数C=9
//O(1)
748. 最短补全词
先使用一个大小为26的int数组记录licensePlate中字母出现的次数，然后逐个计算words中每个单词中字母出现的次数，words中的单词如果满足补全词，则单词中对应字符的出现次数应该比licensePlate中字母出现的次数多或相等
class Solution {
public String shortestCompletingWord(String licensePlate, String[] words) {
int[] count=new int[26];
int minLen=1001;
int index=0;
for(int i=0;i<licensePlate.length();i++)
{
char c=licensePlate.charAt(i);
if(Character.isLetter(c))
{
char lowerC=Character.toLowerCase(c);
count[lowerC-'a']++;
}
}
for(int i=0;i<words.length;i++)
{
boolean stop=false;
int len=words[i].length();
int[] tmp= new int[26];
for(int j=0;j<len;j++)
{
tmp[words[i].charAt(j)-'a']++;//记录单词中字母出现的个数
}
for(int j=0;j<26;j++)
{
if(tmp[j]<count[j])//如果单词中的字母比lincensePlate中的少 则结束比较 并且后面的步骤跳过
{
stop=true;
break;
}
}
if(stop)
continue;
if(len<minLen)//满足条件且长度更短
{
minLen=len;
index=i;
}
}
return words[index];
}
}
911. 在线选举
对数据进行预处理，使用一个list保存各个时刻对应的获胜选举人，然后对查询的时刻进行二分查找，返回list对应的结果即可
class TopVotedCandidate {
ArrayList<Integer> tops=new ArrayList<>();
HashMap<Integer,Integer> map=new HashMap<>();
int times[];
public TopVotedCandidate(int[] persons, int[] times) {
this.times=times;
int top=-1;
map.put(-1,-1);
map.get(top);
for(int i=0;i<times.length;i++)
{
int p=persons[i];
map.put(p, map.getOrDefault(p, 0) + 1);
if(map.get(p)>=map.get(top))//等于的时候也需要更新 因为最新获得选票的人获胜
{
top=p;
}
tops.add(top);
}
}
//查找第一个小于等于t的数
public int q(int t) {
int left=0,right=times.length-1;
while(left<=right)
{
int mid=left+(right-left)/2;
if(times[mid]<t)
left=mid+1;
else if(times[mid]>t)
right=mid-1;
else if(times[mid]==t)
return tops.get(mid);
}
return tops.get(left-1);
}
}
709. 转换成小写字母
将ASCII码值在65-90的字符的码值加32，操作方法有两种
- 直接加32
- 由于65*-90的二进制的表示“32”的二进制位都是0，因此可以与32进行异或操作来完成加32的需求
class Solution {
public String toLowerCase(String s) {
StringBuilder sb=new StringBuilder();
for(int i=0;i<s.length();i++)
{
char ch=s.charAt(i);
if(ch>=65&&ch<=90)
ch+=32;//ch|=32
sb.append(ch);
}
return sb.toString();
}
}
//O(n)
//O(1) 不考虑返回值的空间占用
807. 保持城市天际线
先使用两个一维数组记录下各行的最大值以及各列的最大值，然后遍历grid,对于某一个位置(i，j)而言，它应该增加的值取决于min(所在行的最大值，所在列的最大值)-grid[i][j]
class Solution {
public int maxIncreaseKeepingSkyline(int[][] grid) {
int n=grid.length;
int col[]=new int[n];
int row[]=new int[n];
int sum=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
row[i]=Math.max(row[i],grid[i][j]);
col[i]=Math.max(col[i],grid[j][i]);
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
int minVal=Math.min(row[i],col[j]);
sum+=minVal-grid[i][j];
}
}
return sum;
}
}
//O(n^2)
//O(n)
630. 课程表 III
贪心：
- 优先选择截至时间早的课程
- 当遇到当前课程course时间超出时，比较当前couser的学习时长和heap堆顶的course的学习时长，如果当前course的学习时间较短，则换出堆顶的课程，选择当前的课程
class Solution {
public int scheduleCourse(int[][] courses) {
Arrays.sort(courses,(a,b)->a[1]-b[1]);//按截至日期升序
PriorityQueue<int[]> heap=new PriorityQueue<>((a,b)->b[0]-a[0]);//按学习时长降序
int totalTime=0;
for(int[] course:courses)
{
if(totalTime+course[0]<=course[1])
{
totalTime+=course[0];
heap.offer(course);
}
else if(!heap.isEmpty()&&heap.peek()[0]>course[0])
{
totalTime=totalTime-heap.poll()[0]+course[0];
heap.offer(course);
}
}
return heap.size();
}
}
//O(nlogn) 排序：nlogn 入堆出堆：logn n个元素 nlogn
//O(n) 最坏情况下所有元素都入队
851. 喧闹和富有
建立一张图，图中的节点关系：有钱的指向没钱的，这样一样对于某个节点，沿着箭头往下走，则路径上的节点都比它有钱，先设置当前的ans[x]=x,然后拓展x的相邻节点，同时对相邻节点也需要再拓展，由于可能存在重复运算，因此当ans[x]!=-1时直接返回即可
class Solution {
public int[] loudAndRich(int[][] richer, int[] quiet) {
int n=quiet.length;
ArrayList<Integer> [] graph=new ArrayList[n];
int[] ans=new int[n];
Arrays.fill(ans,-1);
for(int i=0;i<n;i++)
graph[i]=new ArrayList<>();
for(int[] r:richer)
{
graph[r[1]].add(r[0]);//有钱的指向没钱的
}
for(int i=0;i<n;i++)
{
dfs(i,graph,quiet,ans);
}
return ans;
}
public void dfs(int x,ArrayList<Integer>[] graph,int[] quiet,int[] ans)
{
if(ans[x]!=-1)
return;
ans[x]=x;
for(int y:graph[x])
{
dfs(y,graph,quiet,ans);
if(quiet[ans[y]]<quiet[ans[x]])
ans[x]=ans[y];
}
}
}
//O(m+n) m=richer.length n=quiet.length 建立图和DFS的时间复杂度均为O(m+n)
//O(m+n) 存储图的空间是m+n
1518. 换酒问题
思路1：模拟
class Solution {
public int numWaterBottles(int numBottles, int numExchange) {
int ans=numBottles;
int empty=numBottles;
while(empty>=numExchange)
{
int add=empty/numExchange;//当前兑换的酒数量
ans+=add;
empty-=add*numExchange;//减去当前兑换酒消耗的空瓶子
empty+=add;//加上喝完当前兑换的酒的瓶子
}
return ans;
}
}
//O(n/(m-1)) n=numBottles m=numExchange
//O(1)
思路2：数学 交换一瓶酒损失m个瓶子，喝完这瓶酒又可以得到1个新瓶子，相当于损失了m-1个瓶子，所有对于初始有n瓶酒，即有n个瓶子时，可以交换n/(m-1)次（向下取整） 注意点：当n是m-1的倍数时，最后一次交换不了，因此需要-1
class Solution {
public int numWaterBottles(int numBottles, int numExchange) {
int ans=numBottles;
int swapTimes=numBottles/(numExchange-1),mod=numBottles%(numExchange-1);
ans+=mod==0?swapTimes-1:swapTimes;
return ans;
}
}
//O(1) n=numBottles m=numExchange
//O(1)
419. 甲板上的战舰
找出一个战舰的开始位置，所谓的开始位置（i,j）,这个位置的上面没有X，左边没有X，但是第0行和第0列除外，第0行没有上面，第0列没有左边
class Solution {
public int countBattleships(char[][] board) {
int m=board.length,n=board[0].length;
int ans=0;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(i>0&&board[i-1][j]=='X')
continue;
if(j>0&&board[i][j-1]=='X')
continue;
if(board[i][j]=='X')
ans++;
}
}
return ans;
}
}
//O(m*n)
//O(1)
997. 找到小镇的法官
统计每个节点的入度和出度，法官节点：入度为n-1,出度为0，如下面的图中的节点3就是法官节点
class Solution {
public int findJudge(int n, int[][] trust) {
int inDegree[]=new int[n+1];
int outDegree[]=new int[n+1];
for(int p[]:trust)
{
inDegree[p[1]]++;
outDegree[p[0]]++;
}
for(int i=1;i<=n;i++)
{
if(inDegree[i]==n-1&&outDegree[i]==0)
return i;
}
return -1;
}
}
//O(n)
//O(n)
475. 供暖器
对于某个房子house，最小的加热半径应该取决于离它最近的加热器，因此可以先通过二分查找找到heaters中最后一个小于等于house的加热器（最左靠近），记该加热器的位置是i, 则i+1是最右靠近house的加热器，比较这两个加热器和house的距离，取较小值，然后对所有的房子都求出最小半径，最后的结果是这些半径中的最大值
class Solution {
public int findRadius(int[] houses, int[] heaters) {
int ans=0;
Arrays.sort(heaters);
for(int house:houses)
{
int i=binary_search(house,heaters);//heaters[i]<=house
int j=i+1;//heaters[j]>house
int leftDistance=i<0?Integer.MAX_VALUE:house-heaters[i];//i<0: houser左边无heater
int rightDistance=j>=heaters.length?Integer.MAX_VALUE:heaters[j]-house;//j==n: house右边无heater
int distance=Math.min(leftDistance,rightDistance);
ans=Math.max(ans,distance);
}
return ans;
}
//找到指定house的左边最靠近它的heater(相当于在heaters数组中查找最后一个<=house的数)
public int binary_search(int house,int[] heaters)
{
int left=0,right=heaters.length-1;
while(left<=right)
{
int mid=left+(right-left)/2;
if(heaters[mid]<=house)
{
if(mid==heaters.length-1||heaters[mid+1]>house)
return mid;
else
left=mid+1;
}
else
{
right=mid-1;
}
}
return -1;//heaters中的所有元素都比house大 即house左边没有heater
}
}
//O(mlogn+nlogn) n:heaters.length m:houses.length 排序：nlogn 二分查找：mlogn
//O(logn) 排序的空间消耗
1154. 一年中的第几天
class Solution {
public int dayOfYear(String date) {
int monthDays[]={31,28,31,30,31,30,31,31,30,31,30,31};
int days=0;
String s[]=date.split("-");
int year=Integer.parseInt(s[0]);
int month=Integer.parseInt(s[1]);
int day=Integer.parseInt(s[2]);
for(int i=0;i<month-1;i++)
days+=monthDays[i];
days+=day;
if(month>2)
if((year%400==0)||(year%4==0&&year%100!=0))
days+=1;
return days;
}
}
//O(1) 月份的循环是一个常数
//O(1)
686. 重复叠加字符串匹配
a重复之后有2种情况会包含b, 第1种是a重复若干次的长度和b一样时包含b,另外一种是长度刚好比b长的的时候包含b(重复n次比b长，重复n-1次比b短)，判断是否包含可以使用字符串的indexOf方法，更好的做法是使用KMP算法
class Solution {
public int repeatedStringMatch(String a, String b) {
StringBuilder sb=new StringBuilder();
int times=0;
while(sb.length()<b.length())
{
sb.append(a);
times++;
}
String aa=sb.toString();
if(aa.indexOf(b)!=-1)
return times;
sb.append(a);
times++;
aa=sb.toString();
if(aa.indexOf(b)!=-1)
return times;
return -1;
}
}
1705. 吃苹果的最大数目
class Solution {
public int eatenApples(int[] apples, int[] days) {
//pq队列根据苹果的腐烂日期进行升序
PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->(a[1]-b[1]));
int ans=0;
int n=apples.length;
for(int i=0;i<apples.length;i++)
{
//pq.peek()[0]: 苹果的数量
//pq.peek()[1]: 苹果的腐烂日期
if(apples[i]>0)//苹果数量大于0才加入堆
pq.offer(new int[]{apples[i],days[i]+i});
//找到当前堆中没有腐烂且腐烂日期最近的
while(!pq.isEmpty()&&pq.peek()[1]<=i)
{
pq.poll();
}
//当前的堆顶元素要保证苹果还没被吃完
if(!pq.isEmpty())
{
ans++;
if(pq.peek()[0]==1)//就剩一个 吃完将其从堆中删除
pq.poll();
else
pq.peek()[0]=pq.peek()[0]-1;//苹果数量-1
}
}
while(!pq.isEmpty())//n天之后的情况
{
while(!pq.isEmpty()&&pq.peek()[1]<=n)
pq.poll();
if(!pq.isEmpty())
{
ans++;
if(pq.peek()[0]==1)
pq.poll();
else
pq.peek()[0]=pq.peek()[0]-1;
}
n++;//日期+1
}
return ans;
}
}
//O(nlogn) 每个元素最多进入堆1次
//O(n) 堆中的元素不会超过n个
1609. 奇偶树
BFS层次遍历进行判断
class Solution {
public boolean isEvenOddTree(TreeNode root) {
LinkedList<TreeNode> q=new LinkedList<>();
boolean isEven=true;
q.offer(root);
while(!q.isEmpty())
{
int sz=q.size();
TreeNode node1=q.poll();//先拿出该层节点中的第1个节点
if(isEven)//判断节点数值的奇偶性是否满足
{
if(node1.val%2==0)
return false;
}
else
{
if(node1.val%2==1)
return false;
}
if(node1.left!=null)//加入第1个节点的左右子节点
q.offer(node1.left);
if(node1.right!=null)
q.offer(node1.right);
for(int i=1;i<sz;i++)//判断剩下的节点
{
TreeNode node2=q.poll();
if(isEven)
{
//偶数层节点值为奇数&递增
if(node1.val>=node2.val||node1.val%2==0||node2.val%2==0)
return false;
}
else
{
//ji TreeNode node2=q.poll();
if(isEven)
{
//偶数层节点值为奇数&递增
if(node1.val>=node2.val||node1.val%2==0||node2.val%2==0)
return false;
}
else
{
//奇数层节点值为偶数&递减
if(node1.val<=node2.val||node1.val%2==1||node2.val%2==1)
return false;
}
if(node2.left!=null)
q.offer(node2.left);
if(node2.right!=null)
q.offer(node2.right);
node1=node2;//node1指向当前节点
}
isEven=!isEven;
}
return true;
}
}
//O(n)
//O(n)
1078. Bigram 分词
先找到第1个单词，然后判断第3个单词的下标是否在范围内&第2个单词是否能在第1个单词后面紧跟着
class Solution {
public String[] findOcurrences(String text, String first, String second) {
String words[]=text.split(" ");
ArrayList<String> list=new ArrayList<>();
int i=0;
while(i<words.length)
{
if(words[i].equals(first))
{
if(i+2<words.length&&words[i+1].equals(second))
list.add(words[i+2]);
}
i++;
}
return list.toArray(new String[list.size()]);
}
}
//O(n)
//O(n)
825. 适龄的朋友
对于x，它可以发送的范围是y=<x<2(y-7) 使用两个指针left,right, left指向x可以发送范围区间内的第1个元素，right指向区间内的最后1个满足条件的元素，区间内的满足条件的元素个数为区间长度-1，因为不包括自己
class Solution {
public int numFriendRequests(int[] ages) {
int ans=0,n=ages.length;
Arrays.sort(ages);
int left=0,right=0;
for(int i=0;i<n;i++)
{
while(left<i&&!check(ages,i,left))
left++;//找到满足条件的第1个元素
if(right<i)//right指针如果在i的左边 则指向i
right=i;//ages[i]和ages[i]肯定满足条件
while(right+1<n&&check(ages,i,right+1))//right+1指向的元素不满足条件
right++;//找到满足条件的最后1个元素
//[left,right]区间内的元素是对于ages[i]可以发送请求的人
if(right>left)
ans+=(right-left);//(right-left+1)-1 区间长度-1 不包括自己
}
return ans;
}
boolean check(int ages[],int x,int y)
{
if(ages[y]<=0.5*ages[x]+7)
return false;
if(ages[y]>ages[x])
return false;
if(ages[y]>100&&ages[x]<100)
return false;
return true;
}
}
//O(nlogn) 排序：nlogn 双指针遍历：n
//O(logn)
1995. 统计特殊四元组
暴力枚举
class Solution {
public int countQuadruplets(int[] nums) {
int ans=0,n=nums.length;
for(int i=0;i<n-3;i++)
{
for(int j=i+1;j<n-2;j++)
{
for(int k=j+1;k<n-1;k++)
{
for(int h=k+1;h<n;h++)
{
if(nums[i]+nums[j]+nums[k]==nums[h])
{
ans++;
//System.out.println(nums[i]+" "+nums[j]+" "+nums[k]+" "+nums[h]);
}
}
}
}
}
return ans;
}
}
//O(n^4)
//O(1)
哈希表 nums[a]+nums[b]=nums[c]+nums[d]等价于nums[a]+numa[b]=nums[d]-nums[c] 对b进行逆序遍历，在逆序遍历的同时记录每一个b可能产生的nums[d]-nums[c]和nums[a]+nums[b]，然后判断二者是否有相等的情况
class Solution {
public int countQuadruplets(int[] nums) {
int ans=0,n=nums.length;
HashMap<Integer,Integer> map=new HashMap<>();
for(int b=n-3;b>=1;b--)
{
for(int d=b+2;d<n;d++)
{
int c=b+1;
//b每减小1 c的选择就多了一个 且多出来的是b+1 比如n=6 b=3 此时c可以为4 b=2时 c可以为3、4
//当c=4在前一次循环中已经保存了nums[d]-nums[c]的值 因此本次循环只需要记录c=3
map.put(nums[d]-nums[c],map.getOrDefault(nums[d]-nums[c],0)+1);
}
for(int a=0;a<b;a++)//枚举a
{
ans+=map.getOrDefault(nums[a]+nums[b],0);
}
}
return ans;
}
}
846. 一手顺子
先将hand数组排序后用map记录数组中各个元素出现的次数，然后按顺序处理数组元素，假设当前遍历道的元素是x,如果x在map中的val是0则跳过本次循环（x可能已经全部被归类），否则进行处理，判断[x,x+groupSize]区间的元素是否在map中存在，不存在则返回false,存在则将对应元素在map中的个数-1
class Solution {
public boolean isNStraightHand(int[] hand, int groupSize) {
int n=hand.length;
if(n%groupSize!=0)
return false;
Arrays.sort(hand);
HashMap<Integer,Integer> map=new HashMap<>();
for(int num:hand)
{
map.put(num,map.getOrDefault(num,0)+1);
}
for(int num:hand)
{
if(map.get(num)==0)
continue;
for(int j=0;j<groupSize;j++)
{
int x=num+j;
if(!map.containsKey(x))
return false;
map.put(x,map.get(x)-1);
}
}
return true;
}
}
//O(nlogn)
//O(n)
507. 完美数
枚举从[2,sqrt(num)]范围内的因数，如果有1个因数在[2,sqrt(num)]范围内，则必有另外一个因数num/i在[sqrt(num),num]内,需要注意当num是一个完全平方数时，i==num/i,要避免重复累加i
class Solution {
public boolean checkPerfectNumber(int num) {
if(num==1)
return false;
int sum=1;
for(int i=2;i*i<=num;i++)
{
if(num%i==0)
{
sum+=i;
if(i*i<num)//避免i*i==num 这种情况将i重复计算
sum+=num/i;
}
}
return sum==num;
}
}
//O(sqrt(num))
//O(1)
若有收获，就点个赞吧
0 人点赞
