IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 二、leetbook栈 -> 正文阅读

[数据结构与算法]二、leetbook栈

一、实现栈

class MyStack {
	private List<Integer> data;
	public MyStack{
		data = new ArrayList<>();
	
	public void push(int x){
		data.add(x);
	}
	public boolean isEmpty(){
		return data.isEmpty();
	}
	public int top(){
		return data.get(data.size()-1);
	}
	public boolean pop(){
		if (isEmpty()){
			return false;
		}
		data.remove(data.size()-1)
		return true
	}

public class Main{
	public static void main(String[] args){
		Mystack s = new MyStack();
		s.push(1)
		s.push(2)
		s.push(3)
		for (int i = 0;i<4;i++){
			if (!s.isEmpty(){
				System.out.println(s.top());
			}
			System.out.println(s.pop());
		}
	}
}

二、栈的用法

public class Main{
	public static void main(String[] args){
		Stack<Integer> s = new Stack<>();
		s.push(5);
		s.push(13);
		s.push(8);
		s.push(6);
		if (s.empty() == true){
			System.out.println("Stack is empty!");
			return}
		s.pop();
		System.out.println("The top element is: " + s.peek());
		System.out.println("The size is: "+s.size());
	}
}
		

三、例题

1. 最小栈

https://leetcode-cn.com/leetbook/read/queue-stack/g5l7d/

class MinStack:

    def __init__(self):
        self.stList = []
               

    def push(self, val: int) -> None:
        self.stList.append(val)           

    def pop(self) -> None:
        self.stList.pop(-1)


    def top(self) -> int:
        return self.stList[-1]

    def getMin(self) -> int:
        #if self.stList == []:
            #return None
        min =self.stList[0] 
        for i in range(1, len(self.stList)):
            if self.stList[i]<min:
                min = self.stList[i]
        return min
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

结果:
在这里插入图片描述
改进:
为了缩减用时,新建一个最小栈list,用于存储每轮入栈时的最小栈,并在每次出栈时也pop掉该list的最后一个值。这样保证了min随着出栈而改变。

class MinStack:

    def __init__(self):
        self.stList = []
        self.minList = []
               

    def push(self, val: int) -> None:
        self.stList.append(val) 
        if self.minList == []:
            self.minList.append(val)
        elif val < self.minList[-1]:
            self.minList.append(val)
        else:
            self.minList.append(self.minList[-1])

    def pop(self) -> None:
        self.stList.pop(-1)
        self.minList.pop(-1)


    def top(self) -> int:
        return self.stList[-1]

    def getMin(self) -> int:
        #if self.stList == []:
            #return None
        return self.minList[-1]
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

结果:
在这里插入图片描述

改进:
当栈进出大的元素时,对minList是没有影响的,所以改进算法:==>当新入栈的元素大于min时,minlist不改动;当出栈的元素大于min时,minlist不改动。只有小于或等于min时,minlist才变化。
这样可以减少内存。

(改动为注释处。)
(注意:self.stList.pop() == self.getMin() 尽管为判断语句,pop()依然是执行了的)

class MinStack:

    def __init__(self):
        self.stList = []
        self.minList = []
               

    def push(self, val: int) -> None:
        self.stList.append(val) 
        if self.minList == []:
            self.minList.append(val)
        #elif val < self.minList[-1]:
        elif val <= self.minList[-1]:
            self.minList.append(val)
        #else:
            #self.minList.append(self.minList[-1])

    def pop(self) -> None:
        if self.stList.pop() == self.getMin():
            self.minList.pop()
        #self.stList.pop()
        #self.minList.pop(-1)


    def top(self) -> int:
        return self.stList[-1]

    def getMin(self) -> int:
        return self.minList[-1]



# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

结果:
在这里插入图片描述

2. 有效的括号

https://leetcode-cn.com/leetbook/read/queue-stack/g9d0h/
思路:当出现左括号,入栈对应右括号,即可保证正确的顺序;若之后出现的右括号不符合出栈的符号时,或无出栈元素/多了元素,则为false

class Solution:
    def isValid(self, s: str) -> bool:
        strList = list(s)
        theStack = []
        if len(strList) == 0:
            return False
        for element in strList:
            print(element)
            if element == '(':
                theStack.append(')')
                print(theStack)

            elif element == '[':
                theStack.append(']')
            elif element == '{':
                theStack.append('}')
            elif (len(theStack)==0) or (element != theStack.pop()) :
                print(theStack)
                return False
        if len(theStack)!=0:
            return False
        return True

在这里插入图片描述
优化:
优化最后三行,直接改为返回一个判断的结果

class Solution:
    def isValid(self, s: str) -> bool:
        strList = list(s)
        theStack = []
        if len(strList) == 0:
            return False
        for element in strList:
            if element == '(':
                theStack.append(')')
            elif element == '[':
                theStack.append(']')
            elif element == '{':
                theStack.append('}')
            elif (len(theStack)==0) or (element != theStack.pop()) :
                return False
        
        return len(theStack)==0

结果:
提升了速度
在这里插入图片描述

3. 每日温度

https://leetcode-cn.com/leetbook/read/queue-stack/genw3/
1)用暴力法,可以通过简短的案例;但测试案例不通过,案例非常长,严重超时,

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        outcome = []
        for i in range(0,n-1):
            for j in range(i+1, n):
                #print("i: %d j: %d"%(i,j))
                if temperatures[i]<temperatures[j]:
                    outcome.append(j-i)
                    break
                elif j == n-1:
                    outcome.append(0)
        outcome.append(0)
        return outcome            

在这里插入图片描述
2)用栈解法

思路:考虑用栈记录每个元素下标,存放尚未找到更大元素的元素下标。当新元素比前元素大时,出栈前元素下标,记录下标差,入栈新元素下标;当新元素比前元素小时,入栈新元素下标,等待更大的元素入栈。

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        theStack = []
        n = len(temperatures)
        outcome = [0]*n
        for i in range(0,n):
            while (len(theStack)!= 0) and (temperatures[i]>temperatures[theStack[-1]]):
                index = theStack.pop()
                outcome[index] = i - index
            theStack.append(i)
        return outcome

结果:
在这里插入图片描述

3)最后,原网页从后往前找的方法,i从后往前,j从i+1开始与i元素比较大小,不服条件就跳res[j]格再比较:

public int[] dailyTemperatures(int[] T) {
        int[] res = new int[T.length];
        //从后面开始查找
        for (int i = res.length - 1; i >= 0; i--) {
            int j = i + 1;
            while (j < res.length) {
                if (T[j] > T[i]) {
                    //如果找到就停止while循环
                    res[i] = j - i;
                    break;
                } else if (res[j] == 0) {
                    //如果没找到,并且res[j]==0。说明第j个元素后面没有
                    //比第j个元素大的值,因为这一步是第i个元素大于第j个元素的值,
                    //那么很明显这后面就更没有大于第i个元素的值。直接终止while循环。
                    break;
                } else {
                    //如果没找到,并且res[j]!=0说明第j个元素后面有比第j个元素大的值,
                    //然后我们让j往后挪res[j]个单位,找到那个值,再和第i个元素比较
                    j += res[j];
                }
            }
        }
        return res;
    }

作者:数据结构和算法
链接:https://leetcode-cn.com/leetbook/read/queue-stack/genw3/?discussion=OGBxRQ
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

此方法较快:
在这里插入图片描述

4. 逆波兰表达式求值

https://leetcode-cn.com/leetbook/read/queue-stack/gomvm/

算法已给出:在这里插入图片描述

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        theStack = []
        for element in tokens:
            if element not in ["+","-","*","/"]:
                theStack.append(element)
            else:
                num2 = theStack.pop()
                num1 = theStack.pop()
                expression = num1+ element + num2
                tempResult = int(eval(expression))
                theStack.append(str(tempResult))
        return int(theStack.pop())

结果:
在这里插入图片描述
其他方法:
对于运算符,直接分类讨论,执行用时会减少

四、栈与深度优先搜索

-dfs的访问方式适合用栈:从最后访问的节点一直延伸(入栈),没有可访问的就出栈,然后继续

1. 实现DFS-模板1:递归

https://leetcode-cn.com/leetbook/read/queue-stack/gp5a7/

boolean DFS(Node cur, Node target, Set<Node> visited){
	return true if cur is target:
	for (next: each neighbor of cur){
		if (next is not in visited){
			add next to visited;
			return true  if DFS(next, target, visited) == true;
		}
	}
	return false;
}

2. 习题

1. 克隆图

https://leetcode-cn.com/leetbook/read/queue-stack/gmcr6/

错误做法:直接clone node.neighbors——在neighbor的newNode未创建前,是无法添加进curNewNode.neighbors。

"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        stack = []
        nodeList = []
        visited = set()
        created = set()
        createdNei = set()

        stack.append(node)
        visited.add(node.val)
        

        while len(stack)!= 0:
            cur = stack.pop()
            newNode = Node(cur.val,[])
            created.add(node.val)
           
            print(newNode.val)
            
            if newNode.val == 1:
                result = newNode
            for neighbor in cur.neighbors:
                if neighbor.val not in visited:
                    
                    stack.append(neighbor)                    
                    visited.add(neighbor.val)
                    if cur.val not in createdNei:
                        newNei = Node(neighbor.val,[]) 
                        newNode.neighbors.append(newNei) 
            createdNei.add(cur.val)

        return newNode

正确解法(参照原网页):

dfs递归,建立newNode,然后用val标记各个newNode,存入字典。在给newNode添加neighbor时,dfs进行递归:未clone的(不在字典里的)neighbor先clone,已clone的直接返回新节点。

"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        visited = {}
        return self.dfsClone(node, visited)
    
    def dfsClone(self, node, visited:{}):
        # if the new node has been created, return it
        if node == None:
            return None
        if node.val in visited.keys():
            return visited.get(node.val)
        else:
            #if the new node hasn't been created, create it 
            newNode = Node(node.val, [])
            #add the new node to the visited, use val as the key
            visited[node.val] = newNode

        for neighbor in node.neighbors:
            newNode.neighbors.append(self.dfsClone(neighbor, visited))
        
        return newNode

①neighbor作为属性,在递归时进行clone会造成嵌套的循环吗?
——No.[].append操作在内部dfs返回值之前,不执行;当最深的neighbor的新节点都创建完,一步步会返回值,因此不会有循环。
②什么时候完成.append()操作?newNode.neighbors时候变化?
——当有return完成时(有返回值时),neighbor有增加。

以三点为例,计算过程和对应newNode.neighbor的状态:
以三点为例,new node邻居属性的状态
结果:
在这里插入图片描述

2. 目标和

https://leetcode-cn.com/leetbook/read/queue-stack/ga4o2/

错误一:一开始,在dfs方法中使用count作为一个变量,但这样每次调用dfs,count都从0开始计算,return后方法结束,对外部的count并没有产生影响。为了将其作为全局变量,使用global限定,依旧出错(python变量名解析遵循LEGB法则)。

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        count = 0
        return self.dfsCalculate(nums,0,target,count,0)

    def dfsCalculate(self,nums: List[int],tempRes:int, target: int,count,i):
        if i == len(nums):           
            if  tempRes == target:               
                count+=1                
                return

        if i<len(nums):            
            addRes = tempRes + nums[i]
            subRes = tempRes - nums[i]
            print("i: %d addRes: %d subRes: %d tempRes: %d"%(i,addRes,subRes,tempRes))
            self.dfsCalculate(nums,addRes,target,count,i+1)
            self.dfsCalculate(nums,subRes,target,count,i-1)
        
        return count

修正:参考https://www.pythonheidong.com/blog/article/519926/d1050cf106431680133b/ 在目标函数设置self.count=0变量,self.count可在被调用的dfs中被直接修改,不是作为参数传导。最后在目标函数中返回self.count。
修改后解决了问题。

可通过部分测试。但长的案例超时,不通过

class Solution:   

    def dfsCalculate(self,nums: List[int],tempRes:int, target: int,i):
        if i == len(nums):
            if  tempRes == target:
                self.count+=1
        return self.count        
            
        addRes = tempRes + nums[i]
        subRes = tempRes - nums[i]
        #print("i: %d addRes: %d subRes: %d tempRes: %d"%(i,addRes,subRes,tempRes))
        self.dfsCalculate(nums,addRes,target,i+1)
        self.dfsCalculate(nums,subRes,target,i+1)
        
        return self.count
    
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        self.count = 0
        self.dfsCalculate(nums,0,target,0)
        return self.count
        

结果:
在这里插入图片描述
将dfsCalculate的return self.count 都换成只return,多通过3个案例,之后的案例还是超时。

由讨论区,本题使用动态规划可解决超时问题(留待dp专项再做)。
另,原方法使用JAVA可通过:

class Solution {
    private int count = 0;
    public int findTargetSumWays(int[] nums, int target) {
        dfsCalculate(nums, 0, target, 0);
        return count;

    }

    public void dfsCalculate(int[] nums, int temptSum, int target, int i){
        if (i == nums.length){
            if (temptSum == target){
                count ++;             
            }
            return; 
        }
        int addSum = temptSum + nums[i];
        int mnsSum = temptSum - nums[i];
        
        dfsCalculate(nums, addSum, target, i+1);
        dfsCalculate(nums, mnsSum, target, i+1);

        return;
    }
}

结果:
在这里插入图片描述

3. 实现DFS-模板2:显式栈

https://leetcode-cn.com/leetbook/read/queue-stack/g2g9c/
递归方法缺点:深度过大时,堆栈溢出
使用显式栈:

/*
*Return true if there is a path from cur to target
*/
boolean DFS(int root, int target){
	Set<Node> visited;
	Stack<Node> s;
	add root to s;
	while (s is not empty){
		Node cur = the top element in s;
		return true if cur is target;
		for (Node next: the neightbors of cur){
			if (next is not in visited){
			add next to s;
			add next to visited;
			}
		}
		remove cur from s;
	}
	return false;	
}

4. 习题

1. 二叉树的中序遍历

https://leetcode-cn.com/leetbook/read/queue-stack/gnq5i/
题目要求用迭代算法,思路:
中序遍历遵循左-中-右的访问顺序,因此先找到最左的节点(一路找.left直到.left=None,并将一路的节点都存入stack),pop出该最左节点,记录其val,然后看是否有右子树:若有,再搜寻右子树的最左节点,重复上一步骤;若无,再pop出一个节点,记录val,查看右子树。直到stack为空。

简单来说,对于节点,都是先确认.left为None/已被访问过,然后记录val,再然后查看有无.right,有right再查看.left,无right再pop,记录,看right

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        
        theStack = []
        theList = []

        cur = root
        while (cur!=None) or (len(theStack)!=0):
            while cur!=None:
                theStack.append(cur)
                cur = cur.left
        
            cur = theStack.pop()
            theList.append(cur.val)
            cur = cur.right
        
        return theList

结果:
在这里插入图片描述

五、 小结

1. 用栈实现队列

https://leetcode-cn.com/leetbook/read/queue-stack/gvtxe/
思路:建立两个栈,第一个栈存储queue,第二个栈翻转第一个栈的数据,从而实现queue。
注意:在第二个栈中的元素未全部pop出去时,不添入第一个栈的元素,否则pop()顺序会被打乱。

class MyQueue:

    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def push(self, x: int) -> None:
        self.stack1.append(x)
        
    def pop(self) -> int:
        # use 2 stacks to realize the pop order of a queue
        # to ensure the right order, before appending new elements to stack2, the stack2 should pop
        # out all existing elements; if there are elements in stack2, pop them first
        if len(self.stack2)== 0:
            while len(self.stack1)!=0:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()


    def peek(self) -> int:
        if len(self.stack2)== 0:
            while len(self.stack1)!=0:
                self.stack2.append(self.stack1.pop())
        return self.stack2[-1]


    def empty(self) -> bool:
        if len(self.stack2)==0 and len(self.stack1)==0:
            return True
        else:
            return False


# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

在这里插入图片描述

2. 用队列实现栈

https://leetcode-cn.com/leetbook/read/queue-stack/gw7fg/
1)用单个队列实现栈
思路:每次向队列添加新元素后,都把前面的元素依次pop出并添加到队列后面==>保留的队列本身是翻转的数据

class MyStack:

    def __init__(self):
        self.q = []

    def push(self, x: int) -> None:
        n = len(self.q)
        self.q.append(x)
        for i in range(n):
            self.q.append(self.q.pop(0))

    def pop(self) -> int:
        return self.q.pop(0)

    def top(self) -> int:
        return self.q[0]

    def empty(self) -> bool:
        return len(self.q)==0

# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

在这里插入图片描述
2) 两个队列实现栈
思路:一个队列append数据,当遇到pop或top时,将这个队列除了最后一个元素,都pop并存到另一个队列,然后–pop():返回pop(最后一个元素),–top():复制最后一个元素,将其pop存到另一个元素后,返回复制的值

class MyStack:

    def __init__(self):
        self.q1 = []
        self.q2 = []

    def push(self, x: int) -> None:
        if len(self.q2) == 0:
            self.q1.append(x)
        else:
            self.q2.append(x)

    def pop(self) -> int:
        if len(self.q1)!= 0:
            n = len(self.q1)
            for i in range(n-1):
                self.q2.append(self.q1.pop(0))
            return self.q1.pop()
        if len(self.q2)!= 0:
            n = len(self.q2)
            for i in range(n-1):
                self.q1.append(self.q2.pop(0))
            return self.q2.pop()

    def top(self) -> int:
        if len(self.q1)!= 0:
            n = len(self.q1)
            for i in range(n-1):
                self.q2.append(self.q1.pop(0))
            x = self.q1[0]
            self.q2.append(self.q1.pop(0))
            return x
        if len(self.q2)!= 0:
            n = len(self.q2)
            for i in range(n-1):
                self.q1.append(self.q2.pop(0))
            x = self.q2[0]
            self.q1.append(self.q2.pop(0))
            return x

    def empty(self) -> bool:
        if len(self.q1)==0 and len(self.q2) == 0:
            return True
        else:
            return False

# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

在这里插入图片描述

3. 字符串解码

解法参考:https://leetcode-cn.com/leetbook/read/queue-stack/gdwjv/?discussion=A8wST0

  1. 遇数字用num = num * 10 + d来解决多位数字的字符串转数字问题
  2. 遇[:将之前的字母串入栈,数字入栈; 遇]:将数字出栈,并乘以[后的字符,然后在前面加上出栈的字母串。
class Solution:
    def decodeString(self, s: str) -> str:
        
        numStack = []
        alphaStack = []
        alphaFrag = ''
        num = 0
        
        for i in range(len(s)):
            if s[i].isalpha():
                alphaFrag += s[i] 
            elif s[i].isdigit():
                d = int(s[i])
                num = num *10 + d
            elif s[i] == '[':
                alphaStack.append(alphaFrag)
                alphaFrag = ''
                numStack.append(num)
                num = 0
            elif s[i] == ']':
                times = numStack.pop()
                alphaFrag = alphaFrag * times

                alpha = alphaStack.pop()
                alphaFrag = alpha + alphaFrag
        
        return alphaFrag

在这里插入图片描述

4. 图像渲染

类似小岛问题
注意:1)需要visited避免递归次数超出限制 2)dfs中return的条件可以简化

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        k = image[sr][sc]
        visited = set()
        return self.dfsColor(image, sr, sc, newColor, k, visited)

    def dfsColor(self, image, i, j, newColor, k, visited):
        if (image[i][j] == k) and ((i,j) not in visited):
            image[i][j] = newColor
            visited.add((i,j))
            
            if (j-1>=0):
                self.dfsColor(image,i,j-1,newColor,k,visited)
            if (j+1<len(image[0])):
                self.dfsColor(image,i,j+1,newColor,k,visited)
            if (i-1>=0):
                self.dfsColor(image,i-1,j,newColor,k,visited)
            if (i+1<len(image)):
                self.dfsColor(image,i+1,j,newColor,k,visited)
        else:
            return
        
        return image

在这里插入图片描述
dfs中return的条件可简化,但是效率可能下降。

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        k = image[sr][sc]
        visited = set()
        return self.dfsColor(image, sr, sc, newColor, k, visited)

    def dfsColor(self, image, i, j, newColor, k, visited):
        if (i<0) or (i>= len(image)) or (j<0) or (j>=len(image[0])) or ((i,j) in visited):
            return

        if (image[i][j] == k):
            image[i][j] = newColor
            visited.add((i,j))

            self.dfsColor(image,i,j-1,newColor,k,visited)
            self.dfsColor(image,i,j+1,newColor,k,visited)
            self.dfsColor(image,i-1,j,newColor,k,visited)
            self.dfsColor(image,i+1,j,newColor,k,visited)
            
        return image


在这里插入图片描述

5. 0-1矩阵

https://leetcode-cn.com/leetbook/read/queue-stack/g7pyt/

思路:目标函数扫描每个格子,对于非1 的格子,调用bfs查找0。bfs使用队列模板。
结果:通过大部分测试,最长的测试通不过,chao

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        m = len(mat)
        n = len(mat[0])
        distMat = [[0 for x in range(n)]for y in range(m)]
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 0:
                    distMat[i][j] = 0
                else:
                    distMat[i][j] = self.bfs( mat, i, j)
        return distMat
    
    def bfs(self, mat, a, b) -> int:
        m = len(mat)
        n = len(mat[0])
        depth = -1
        q = []
        q.append((a,b))
        visited = set()
        visited.add((m,n))
        while(len(q)!=0):
            depth+=1
            size = len(q)
            for each in range(size):
                pos = q.pop(0)
                i = pos[0]
                j = pos[1]
                if mat[i][j] == 0:
                    return depth

                if (j-1>=0) and ((i,j-1) not in visited):
                    q.append((i,j-1))
                    visited.add((i,j-1))
                if j+1<n and ((i,j+1) not in visited):
                    q.append((i,j+1))
                    visited.add((i,j+1))
                if (i-1>=0) and ((i-1,j) not in visited):
                    q.append((i-1,j))
                    visited.add((i-1,j))
                if (i+1<m) and ((i+1,j) not in visited):
                    q.append((i+1,j))
                    visited.add((i+1,j))
        return -1

在这里插入图片描述

6. 钥匙和房间

https://leetcode-cn.com/leetbook/read/queue-stack/gle1r/

思路

对每个房间依次设为目标房间,每一轮查看目标房间是否能到达。从room[0]开始,用stack存储能到达、待查看的房间,然后pop出进行查看这个房间的钥匙是否为目标钥匙。

一个要点:visited的set存储的是什么、或什么是否把点存入visited——它是出现过的key?查看过的房间?因这题相当于有环有向图,从之前的单项节点图直观思考不一样。那我们可以从前面的思路的stack来看:visited是避免单个节点重复入栈,那我们直接把房间0和append入栈的节点放入visited,每次append前进行不在visited的判断,即可。

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        roomSize = len(rooms)
        for target in range(1, roomSize):
            if self.dfs(rooms, target) == False:
                return False
        return True
                
    
    def dfs(self, rooms, target):
        stack = []
        visited = set()
        visited.add(0)

        for key in rooms[0]:
            if key == target:
                return True
            else:
                stack.append(key)
                visited.add(key)
                    
        while len(stack) != 0:
            roomNum = stack.pop()
            for key in rooms[roomNum]:
                if key == target:
                    return True
                else:
                    if key not in visited:
                        stack.append(key)
                        visited.add(key)
        
        return False

在这里插入图片描述

改进1

1)测试使用in能否更快。即查询target是否在某房间的所有钥匙中,而不是每个钥匙依次查是否为target
在这里插入图片描述
结果:更慢了
在这里插入图片描述
不存储到keys比上面更慢。

☆ 改进2

2)题目探究从房间0进入,是否能进入所有房间,那么我们可对这一步能进入的房间进行标记,并递归下一步能进入的所有房间。如果最后仍然有房间不能进入,则返回False,否则返回True

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        roomSize = len(rooms)
        self.noted = [0]*roomSize
        self.dfsNote(rooms, 0)
        if 0 in self.noted:
            return False
        else:
            return True

    def dfsNote(self, rooms, i):
        if self.noted[i] == 1:
            return 
        if self.noted[i] == 0:
            self.noted[i] =1
            for key in rooms[i]:
                self.dfsNote(rooms, key)

效果不错
在这里插入图片描述

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-12-05 12:17:23  更:2021-12-05 12:19:30 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 14:48:29-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码