转化为全0矩阵的最少反转次数
转化为全0矩阵最少反转次数
BFS
class Solution {
public int minFlips(int[][] mat){
//BFS
int n=mat.length;int m=mat[0].length;
Queue<Integer> queue=new LinkedList<Integer>();
Set<Integer> set=new HashSet<Integer>();
int res=0;
int start=encode(mat);
if (start == 0) {
return res;
}
queue.offer(start);
set.add(start);
while (!queue.isEmpty()) {
int size=queue.size();
for(int k=0;k<size;k++){
int node=queue.poll();
if(node==0){
return res;
}
int[][] status=decode(node,n,m);
//当前状态所有位进行翻转
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){//每一次只翻转一位,需要恢复状态
flip(status,i,j,n,m);
int cur_state=encode(status);
if(!set.contains(cur_state)){
set.add(cur_state);
queue.offer(cur_state);
}
flip(status,i,j,n,m);
}
}
}
res++;
}
return -1;
}
int[] dx={0,1,0,-1,0};
int[] dy={1,0,-1,0,0};
public void flip(int[][] matrix,int x,int y,int n,int m){
for(int k=0;k<5;k++){
int a=x+dx[k];
int b=y+dy[k];
if(a<0||a>=n||b<0||b>=m){
continue;
}
matrix[a][b]^=1;
}
}
public int[][] decode(int state,int n,int m){
int[][] matrix=new int[n][m];
for(int i=n-1;i>=0;i--){
for(int j=m-1;j>=0;j--){
matrix[i][j]=(state&1);
state>>=1;
}
}
return matrix;
}
//定义编码矩阵映射
public int encode(int[][] matrix){
int res=0;
for(int i=0;i<matrix.length;i++){
for(int j=0;j<matrix[0].length;j++){
res=res*2+matrix[i][j];
}
}
return res;
}
}
方式二:通过递归的方式进行搜索
dfs递归过程中如果有状态改变,需要将对应的状态恢复
class Solution {
int res=Integer.MAX_VALUE;
public int minFlips(int[][] mat){
int n=mat.length;int m=mat[0].length;
dfs(mat,0,0);
return res==Integer.MAX_VALUE? -1:res;
}
public void dfs(int[][] matrix,int steps,int cnt){
int n=matrix.length;int m=matrix[0].length;
if (steps == matrix.length * matrix[0].length) {
//判断是否全零
boolean flag=true;
for(int i=0;i<matrix.length;i++){
for(int j=0;j<matrix[0].length;j++){
if(matrix[i][j]!=0){
flag=false;
}
}
}
if(flag){
res=Math.min(res,cnt);
}
return;
}
int row=steps/m;int col=steps%m;
dfs(matrix,steps+1,cnt);
//翻转
convert(matrix,row,col);
dfs(matrix,steps+1,cnt+1);
convert(matrix,row,col);
}
int[] dx={0,1,0,-1,0};
int[] dy={1,0,-1,0,0};
public void convert(int[][] matrix,int i,int j){
int n=matrix.length;int m=matrix[0].length;
for(int k=0;k<5;k++){
int a=i+dx[k];
int b=j+dy[k];
if(a>=0&&a<n&&b>=0&&b<m){
matrix[a][b]^=1;
}
}
}
}
由于第一行状态如果确定,下面所有的行是否反转也就确定了
dfs+剪枝
class Solution {
int res=Integer.MAX_VALUE;
public int minFlips(int[][] mat){
int n=mat.length;int m=mat[0].length;
dfs(mat,0,0);
return res==Integer.MAX_VALUE? -1:res;
}
public void dfs(int[][] matrix,int steps,int cnt){
int n=matrix.length;int m=matrix[0].length;
if(steps==m*n){
boolean flag=true;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(matrix[i][j]!=0){
flag=false;
}
}
}
if(flag){
res=Math.min(res,cnt);
}
return;
}
int row=steps/m;int col=steps%m;
if(row==0){
dfs(matrix,steps+1,cnt);
convert(matrix,row,col);
dfs(matrix,steps+1,cnt+1);
convert(matrix,row,col);
}else{
if(matrix[row-1][col]==0){
dfs(matrix,steps+1,cnt);
}else{
convert(matrix,row,col);
dfs(matrix,steps+1,cnt+1);
convert(matrix,row,col);
}
}
}
int[] dx={0,1,0,-1,0};
int[] dy={1,0,-1,0,0};
public void convert(int[][] matrix,int i,int j){
int n=matrix.length;int m=matrix[0].length;
for(int k=0;k<5;k++){
int a=i+dx[k];
int b=j+dy[k];
if(a>=0&&a<n&&b>=0&&b<m){
matrix[a][b]^=1;
}
}
}
}
能从盒子获得最大糖果数
能从盒子获得最大糖果数
创建对应的标记数组记录对应的能够进行打开的所有的盒子
通过标记数组记录没有使用的盒子
以及拥有的盒子
初始化将所有的能够打开的所有的盒子放入队列进行初始化搜索
class Solution {
public int maxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) {
int n=status.length;
boolean[] can_open=new boolean[n];
boolean[] has_box=new boolean[n];
boolean[] used=new boolean[n];
for(int i=0;i<n;i++){
can_open[i]=status[i]==1? true:false;
}
Queue<Integer> queue=new LinkedList<Integer>();
//将所有的能打开的盒子放入队列
int res=0;
for(int i=0;i<initialBoxes.length;i++){
has_box[initialBoxes[i]]=true;
if(can_open[initialBoxes[i]]){
res+=candies[initialBoxes[i]];
used[initialBoxes[i]]=true;
queue.offer(initialBoxes[i]);
}
}
while (!queue.isEmpty()) {
int node=queue.poll();
for (int key : keys[node]) {
//能打开的盒子
can_open[key]=true;
if(!used[key]&&has_box[key]){
res+=candies[key];
queue.offer(key);
used[key]=true;
}
}
//有的盒子
for (int box : containedBoxes[node]) {
has_box[box]=true;
if(!used[box]&&can_open[box]){
res+=candies[box];
queue.offer(box);
used[box]=true;
}
}
}
return res;
}
}
获取所有的钥匙的最短路径
class Solution {
int[][][] dist=new int[31][31][1<<6];
public int shortestPathAllKeys(String[] grid) {
//通过dist[i][j][s]表示从起点到grid[i][j]位置钥匙数为s,通过BFS更新dist[][][]
int n=grid.length;int m=grid[0].length();
int S=0;
Queue<Node> queue=new LinkedList<Node>();
//初始化
for(int i=0;i<dist.length;i++){
for(int j=0;j<dist[0].length;j++){
Arrays.fill(dist[i][j],0x3f3f3f);
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(grid[i].charAt(j)=='@'){
dist[i][j][0]=0;
queue.offer(new Node(i,j,0));
}else if(grid[i].charAt(j)>='a'&&grid[i].charAt(j)<='z'){
S++;
}
}
}
int[] dx={0,1,0,-1};
int[] dy={1,0,-1,0};
while (!queue.isEmpty()) {
Node node=queue.poll();
int d=dist[node.x][node.y][node.s];
for(int k=0;k<4;k++){
int a=node.x+dx[k];int b=node.y+dy[k];int s=node.s;
//新状态扩展
if(a<0||a>=n||b<0||b>=m||grid[a].charAt(b)=='#'){
continue;
}
char ch=grid[a].charAt(b);
if(ch>='a'&&ch<='z'){
s|=(1<<(ch-'a'));
if (dist[a][b][s] > d + 1) {
dist[a][b][s]=d+1;
if(s==((1<<S)-1)){
return dist[a][b][s];
}
queue.offer(new Node(a,b,s));
}
}else if(ch>='A'&&ch<='Z'){
if ((s & (1 << (ch - 'a'))) != 0) {
if (dist[a][b][s] > d + 1) {
dist[a][b][s]=d+1;
queue.offer(new Node(a,b,s));
}
}
}else{
if (dist[a][b][s] > d + 1) {
dist[a][b][s]=d+1;
queue.offer(new Node(a,b,s));
}
}
}
}
return -1;
}
}
class Node{
int x,y,s;
public Node(int x,int y,int s){
this.x=x;
this.y=y;
this.s=s;
}
}
赛车
赛车
+ 到达终点target一定是加速
+ 起始一定是加速,如果是转向,一定可以转化为先进性加速
+ 最后的指令序列一定是 A^k1RA^k2.....
+ 搜索状态范围一定是[0,target*2],所以加速之后的位置可以进行特判
class Solution {
public int racecar(int target){
int[][][] dist=new int[20010][15][2];
for(int i=0;i<dist.length;i++){
for(int j=0;j<dist[0].length;j++){
Arrays.fill(dist[i][j],0x3f3f3f);
}
}
Queue<Node> queue=new LinkedList<Node>();
dist[0][0][1]=0;
queue.offer(new Node(0,0,1));
while (!queue.isEmpty()) {
Node node=queue.poll();
int d=dist[node.x][node.k][node.d];
//如果当前位置为[0,target*2]可以进行加速
//加速
int x=node.x+(1<<node.k)*(2*node.d-1);
if (x >= 0 && x <= target * 2) {//下一个位置需要在[0,target*2]
if (dist[x][node.k + 1][node.d] > d + 1) {
dist[x][node.k+1][node.d]=d+1;
if(x==target){
return dist[x][node.k+1][node.d];
}
queue.offer(new Node(x,node.k+1,node.d));
}
}
//转向,下一个状态为dist[node.x][0][node.d^1];
if (dist[node.x][0][node.d ^ 1] > d + 1) {
dist[node.x][0][node.d^1]=d+1;
//下一个状态加入队列
queue.offer(new Node(node.x,0,node.d^1));
}
}
return -1;
}
}
class Node{
int x,k,d;
public Node(int x,int k,int d){
this.x=x;
this.k=k;
this.d=d;
}
}
公交路线
公交路线
将每一条环线看成一个点进行BFS扩展
由于BFS扩展,第一次进行扩展就可以将所有的环线进行扩展,第一次进行扩展就已经是最优的
所以对于每一个点进行扩展,就可以将该点删除,
对于每一个点扩展该点经过的环线
class Solution {
public int numBusesToDestination(int[][] routes, int source, int target) {
if(source==target){
return 0;
}
//通过维护倒排索引,每一个点上经过的环线
Map<Integer,List<Integer>> map=new HashMap<Integer, List<Integer>>();
int n=routes.length;
int[] dist=new int[n];//每一个环线对应的一个点
Arrays.fill(dist,0x3f3f3f);
Queue<Integer> queue=new LinkedList<Integer>();
for(int i=0;i<n;i++){
for(int j=0;j<routes[i].length;j++){
if(routes[i][j]==source){
dist[i]=1;
queue.offer(i);
}
//维护倒排索引表
List<Integer> list = map.getOrDefault(routes[i][j], new ArrayList<>());
list.add(i);
map.put(routes[i][j],list);
}
}
while (!queue.isEmpty()) {
Integer node=queue.poll();
//当前环线所有点进行扩展
for (int cur_node : routes[node]) {
if(cur_node==target){
return dist[node];
}
//当前点上的所有的环线
if(map.get(cur_node)!=null) {
for (Integer line : map.get(cur_node)) {
if (dist[line] > dist[node] + 1) {
dist[line] = dist[node] + 1;
queue.offer(line);
}
}
//将当前点删除
map.remove(cur_node);
}
}
}
return -1;
}
}
吃掉n个橘子的最少天数
吃掉n个橘子的最少天数
要是操作次数最少,需要在进行/2操作之前,需要将所有的操作减为最接近2的偶数然后除2
三种操作:(1)将橘子数减一(2)将橘子数减半/2 如果橘子数为偶数(3)将橘子数减为/3,如果橘子树%3==0
- 在任意一次操作2之前最多只会有1次操作1
- 在任意一次操作3之前最多只会有2次操作1
- 除了最后一次操作1之外,其余连续操作1之后都会有操作2或3
class Solution {
//通过dijkstra搜索
PriorityQueue<int[]> queue=new PriorityQueue<int[]>((a,b)->a[0]!=b[0]? a[0]-b[0]:a[1]-b[1]);
public int minDays(int n){
Set<Integer> vis=new HashSet<Integer>();
queue.offer(new int[]{0,n});//分别表示距离和位置
while (!queue.isEmpty()) {
int[] node=queue.poll();
int d=node[0];int x=node[1];
if(vis.contains(x)){
continue;
}
//标记
vis.add(x);
//更新距离
if(x==1){
return d+1;
}
queue.offer(new int[]{d+x%2+1,x/2});
queue.offer(new int[]{d+x%3+1,x/3});
}
return -1;
}
}
方式二:记忆化搜索
//记忆化搜索
Map<Integer,Integer> memo=new HashMap<Integer,Integer>();
public int minDays01(int n){
if(n<=1){
return n;
}
if(memo.containsKey(n)){
return memo.get(n);
}
memo.put(n,Math.min(n%2+1+minDays01(n/2),n%3+1+minDays01(n/3)));
return memo.get(n);
}