讨论/题目交流/🏆 迎国庆,力扣第 156 场周赛 🇨🇳/
🏆 迎国庆,力扣第 156 场周赛 🇨🇳

祖国 image.png 周年盛世华诞,这是国庆前的一场激烈竞赛,欢迎小伙伴们在这里交流分享你的参赛心得以及体验,祝大家国庆假期快乐。

image.png前往竞赛本周周赛题目:

独一无二的出现次数
尽可能使字符串相等
删除字符串中的所有相邻重复项 II
穿过迷宫的最少移动次数 —— 小蛇移动

展开讨论

后两题题解(基于java):
删除字符串中的所有相邻重复项 II:
用栈模拟即可。
代码:

class Solution {
	class node
	{
		char val;
		int num;
		public node(char val,int num)
		{
			this.val=val;
			this.num=num;
		}
	}
    public String removeDuplicates(String s, int k) {
        Stack<node> st=new Stack();
        for(int i=0;i<s.length();i++)
        {
        	int tmp=0;
        	if(!st.isEmpty() && s.charAt(i)==st.peek().val)
        		tmp=st.peek().num+1;
        	else
        		tmp=1;
        	if(tmp==k)
        	{
        		int num=k-1;
        		while(num>0)
        		{
        			st.pop();
        			num--;
        		}
        	}
        	else
        		st.add(new node(s.charAt(i),tmp));
        }
        
        StringBuilder str1=new StringBuilder();
        StringBuilder str2=new StringBuilder();
        
        while(!st.isEmpty()) str1.append(st.pop().val);
        for(int i=str1.length()-1;i>=0;i--)
        	str2.append(str1.charAt(i));
        
        return str2.toString();
    }
}
  1. 穿过迷宫的最少移动次数:
    bfs搞一搞就好了
class Solution {
	
	class node
	{
		int x1,x2,y1,y2,state,step;
		public node(int x1,int y1,int x2,int y2,int state,int step)
		{
			this.x1=x1;
			this.y1=y1;
			this.x2=x2;
			this.y2=y2;
			this.state=state;
			this.step=step;
		}
	}
	
	boolean[][][] flag=new boolean[105][105][2];
	
    public int minimumMoves(int[][] grid) {
    	int n=grid.length;
        node start=new node(0,0,0,1,0,0); flag[0][0][0]=true;
        node end=new node(n-1,n-2,n-1,n-1,0,0);
        Queue<node> q=new LinkedList();
        q.add(start);
        while(!q.isEmpty())
        {
        	 node now=q.poll();
        	 if(isOk(now,end))
        		 return now.step;
        	 int dx1,dy1,dx2,dy2;
        	 if(now.state==0)
        	 {
            	  dx1=now.x1;dy1=now.y1+1;
            	  dx2=now.x2;dy2=now.y2+1;
	        	 if(dy1<n && dy2<n && !flag[dx1][dy1][0] &&	grid[dx2][dy2]==0)
	        	 {
	        		 flag[dx1][dy1][0]=true;
	        		 q.add(new node(dx1,dy1,dx2,dy2,0,now.step+1));
	        	 }
	        	 if(dx1+1<n && grid[dx1+1][now.y1]==0 && grid[dx1+1][now.y2]==0)
	        	 {
	        		 if(!flag[dx1+1][now.y1][0])
	        		 {
	        			 flag[dx1+1][now.y1][0]=true;
	        			 q.add(new node(dx1+1,now.y1,dx2+1,now.y2,0,now.step+1));
	        		 }
	        		 if(!flag[dx1][now.y1][1])
	        		 {
	        			 flag[dx1][now.y1][1]=true;
	        			 q.add(new node(dx1,now.y1,dx1+1,now.y1,1,now.step+1));
	        		 }
	        	 }
        	 }
        	 else
        	 {
        		 dx1=now.x1+1;dy1=now.y1;
        		 dx2=now.x2+1;dy2=now.y2;
        		 if(dx1<n && dx2<n && grid[dx2][dy2]==0 && !flag[dx1][dy1][1])
        		 {
        			 flag[dx1][dy1][1]=true;
        			 q.add(new node(dx1,dy1,dx2,dy2,1,now.step+1));
        		 }
        		 if(dy1+1<n && grid[now.x1][now.y1+1]==0 && grid[now.x2][now.y2+1]==0)
        		 {
        			 if(!flag[now.x1][now.y1+1][1])
        			 {
	        			 flag[now.x1][now.y1+1][1]=true;
	        			 q.add(new node(now.x1,now.y1+1,now.x2,now.y2+1,1,now.step+1));
        			 }
        			 if(!flag[now.x1][now.y1][0])
        			 {
        				 flag[now.x1][now.y1][0]=true;
        				 q.add(new node(now.x1,now.y1,now.x1,now.y1+1,0,now.step+1));
        			 }
        		 }
        		 
        	 }
        }      
        return -1;
    }
    
    private boolean isOk(node a,node b)
    {
    	if(a.x1==b.x1 && a.x2==b.x2 && a.y1==b.y1 && a.y2==b.y2)
    		return true;
    	return false;
    }
}
展开全部 21 讨论