等式方程的可满足性
class Solution {
int[] father;
public boolean equationsPossible(String[] equations) {
//初始化,所有的变量都是单变量
init();
for(int i=0;i<equations.length;i++){
String s=equations[i];
int a=find(s.charAt(0)-'a');
int b=find(s.charAt(3)-'a');
if(s.charAt(1)=='='){
//直接合并
father[a]=b;
}
}
//先要将所有的相等关系进行维护
for(int i=0;i<equations.length;i++){
String s=equations[i];
int a=find(s.charAt(0)-'a');
int b=find(s.charAt(3)-'a');
if(s.charAt(1)=='!'&&a==b){
return false;
}
}
return true;
}
public void init(){
father=new int[26];
for(int i=0;i<=25;i++){
father[i]=i;
}
}
public int find(int x){
if(x!=father[x]){
father[x]=find(father[x]);
}
return father[x];
}
}
统计不开心的朋友
统计不开心的朋友
通过预处理order[i][j]通过人获得对应的下标,正常情况对于preferences[i][j]通过下标获得人
class Solution {
public int unhappyFriends(int n,int[][] preferences,int[][] pairs){
//创建数组order[i][j]表示朋友j在i亲密程度的下标
int[][] order=new int[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n-1;j++){
order[i][preferences[i][j]]=j;
}
}
//将所有的配对关系映射到数组,对于所有的配对的人都需要进行检查
int[] match=new int[n];
for (int[] pair : pairs) {
int start=pair[0];int end=pair[1];
match[start]=end;match[end]=start;
}
int res=0;
for(int i=0;i<n;i++){
int x=i;int y=match[i];
//对x进行检查
int ord=order[x][y];
for(int j=0;j<ord;j++){
//对于亲密程度更高的preferences[i][j]
int c=preferences[i][j];int d=match[c];
if(order[c][d]>order[c][x]){
res++;
break;//如果当前元素x是不开心的,则直接对下一个人进行检查
}
}
}
return res;
}
}
对于从网格图上的某一个格子,进行十字遍历
int start,end;
for(int k=0;k<4;k++){
//对于下一个格子
int a=start+dx[k];
int b=end+dy[k];
//如果对应的[a][b]没有越界,一条路走下去
while(a>=0&&a<m&&b>=0&&b<n){
a=a+dx[k];
b=b+dy[k];
}
}
统计网格图中没有被保护的格子数
class Solution {
public int countUnguarded(int m, int n, int[][] guards, int[][] walls) {
int[] dx={0,1,0,-1};
int[] dy={1,0,-1,0};
int[][] grid=new int[m][n];
for(int[] node:guards){
grid[node[0]][node[1]]=1;
}
for(int[] node:walls){
grid[node[0]][node[1]]=2;
}
//从警卫处开始扩展,将所有可以保护的地方标记为3
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]==1){
for(int k=0;k<4;k++){
int a=i+dx[k];
int b=j+dy[k];
while(a>=0&&a<m&&b>=0&&b<n){
//如果合法位置
grid[a][b]=3;
a=a+dy[k];
b=b+dy[k];
}
}
}
}
}
int res=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]==0){
res++;
}
}
}
return res;
}
}
球的下落位置
球的下落位置
对于球的下一个位置 通过next=c+grid[r][c];
判断是否会卡住,通过grid[r][c]!=grid[r][next]进行判断
class Solution {
int[][] grid;
public int[] findBall(int[][] grid) {
this.grid=grid;
int n=grid.length;int m=grid[0].length;
int[] res=new int[m];
//对于每一列的小球
for(int i=0;i<m;i++){
res[i]=getValue(i);
}
return res;
}
public int getValue(int x){
int r=0,c=x;
int n=grid.length;int m=grid[0].length;
while(r<n){
int next=c+grid[r][c];
if(next<0||next>=m){
return -1;
}
//对于同一样的下一个next
if(grid[r][next]!=grid[r][c]){
return -1;
}
c=next;
r++;
}
return c;
}
}
最大网络秩
最大网络秩
通过计数所有的节点的度,通过O(n)时间判断两个点是否直接相连,将多余计算的一次去除
class Solution {
public int maximalNetworkRank(int n, int[][] roads) {
//统计每一个点的度
int[] deg=new int[n];
for (int[] road : roads) {
int start=road[0];int end=road[1];
deg[start]++;deg[end]++;
}
int ans=Integer.MIN_VALUE;
int res=0;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
res=deg[i]+deg[j];
// System.out.println("deg[i]"+deg[i]+"==="+"deg[j]"+deg[j]);
if(check(roads,i,j)){
res-=1;
}
ans=Math.max(ans,res);
}
}
return ans;
}
public boolean check(int[][] roads,int start,int end){
for (int[] road : roads) {
int i=road[0];int j=road[1];
if((i==start&&j==end)||(i==end&&j==start)){
return true;
}
}
return false;
}
}