每日演算法之矩陣中的路徑

来源:https://www.cnblogs.com/loongnuts/archive/2022/11/28/16932046.html
-Advertisement-
Play Games

JZ12 矩陣中的路徑 描述 請設計一個函數,用來判斷在一個n乘m的矩陣中是否存在一條包含某長度為len的字元串所有字元的路徑。路徑可以從矩陣中的任意一個格子開始,每一步可以在矩陣中向左,向右,向上,向下移動一個格子。如果一條路徑經過了矩陣中的某一個格子,則該路徑不能再進入該格子。 思路 我們看到他 ...


JZ12 矩陣中的路徑

描述

請設計一個函數,用來判斷在一個n乘m的矩陣中是否存在一條包含某長度為len的字元串所有字元的路徑。路徑可以從矩陣中的任意一個格子開始,每一步可以在矩陣中向左,向右,向上,向下移動一個格子。如果一條路徑經過了矩陣中的某一個格子,則該路徑不能再進入該格子。

思路

我們看到他是從矩形中的一個點開始往他的上下左右四個方向查找,這個點可以是矩形中的任何一個點,所以代碼的大致輪廓我們應該能寫出來,就是遍歷矩形所有的點,然後從這個點開始往他的4個方向走,因為是二維數組,所以有兩個for迴圈,代碼如下
public boolean hasPath (char[][] matrix, String word) {
    char[] words = word.toCharArray();
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
            //從[i,j]這個坐標開始查找
            if (dfs(matrix, words, i, j, 0))
                return true;
        }
    }
    return false;
}
這裡關鍵代碼是dfs這個函數,因為每一個點我們都可以往他的4個方向查找,所以我們可以把它想象為一棵4叉樹,就是每個節點有4個子節點,而樹的遍歷我們最容易想到的就是遞歸,我們來大概看一下

boolean dfs(char[][] board, char[] word, int i, int j, int index) {
    if (邊界條件的判斷) {
        return;
    }
 
    一些邏輯處理
 
    boolean res;
    //往右
    res = dfs(board, word, i + 1, j, index + 1)
    //往左
    res |= dfs(board, word, i - 1, j, index + 1)
    //往下
    res |= dfs(board, word, i, j + 1, index + 1)
    //往上
    res |= dfs(board, word, i, j - 1, index + 1)
    //上面4個方向,只要有一個能查找到,就返回true;
    return res;
}

代碼

package mid.JZ12矩陣中的路徑;

import java.util.*;


public class Solution {
    /**
     * 代碼中的類名、方法名、參數名已經指定,請勿修改,直接返回方法規定的值即可
     *
     * 
     * @param matrix char字元型二維數組 
     * @param word string字元串 
     * @return bool布爾型
     */
    public boolean hasPath (char[][] matrix, String word) {
        // write code here
        char[] words = word.toCharArray();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (dfs(matrix, words, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] matrix,char[] word, int i, int j, int index) {
        //行
        int n = matrix.length;
        //列
        int m = matrix[0].length;
        if (i >= n || i < 0 || j >= m || j < 0 || matrix[i][j] != word[index]) {
            return false;
        }
        if (index == word.length - 1) return true;

        //記錄當前坐標的值保存下來,防止重覆使用
        char tmp = matrix[i][j];
        matrix[i][j] = '.';

        //走遞歸
        boolean res = (dfs(matrix, word, i + 1, j, index + 1) ||
                dfs(matrix, word, i, j + 1, index + 1) ||
                dfs(matrix, word, i - 1, j, index + 1) ||
                dfs(matrix, word, i, j - 1, index + 1));

        //當前值複原
        matrix[i][j] = tmp;
        return res;
    }
}

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 巨集在 C 語言中非常重要,但在 C++ 中卻無甚大用,普遍的共識:儘量避免使用巨集 C++ 之父 Bjarne 在《C++ Programming Language》中寫到 Avoid macros 《Effective C++》 條款 2 Prefer const, enum, and inline ...
  • 目錄 一.OpenGL 圖像色階 1.原始圖片 2.效果演示 二.OpenGL 圖像色階源碼下載 三.猜你喜歡 零基礎 OpenGL ES 學習路線推薦 : OpenGL ES 學習目錄 >> OpenGL ES 基礎 零基礎 OpenGL ES 學習路線推薦 : OpenGL ES 學習目錄 >> ...
  • 目標:爬取xx二手房樓市信息自己分析形勢 目的:記錄重溫爬蟲歷程 1、引用包requests,random,time,pandas,bs4 2、查詢:bs4使用方法,re。comple,以及他山之石。 3、思路:簡單應用,直接寫死不用def,class, -url 列表,初始列表後,append添加 ...
  • 併發編程Bug的源頭:可見性、原子性和有序性問題。 「CPU、記憶體、磁碟之間的速度差異」 - 為了能同時執行多個任務,CPU 發展出時間片輪轉、多核等 - CPU 要從記憶體中讀數據太慢了,所以給自己設置了緩存 - CPU 讀磁碟更慢了,所以可以讓該線程阻塞 ...
  • GCC struct 記憶體對齊規則 結構體起始地址需要被其中成員類型最大的大小所整除; 每個成員起始地址需要被其類型大小所整除,如int32_t類型成員記憶體對齊到4B; 如果成員有子結構體,則該子結構體成員起始地址要被其內部成員類型最大的所整除。如struct a里存有struct b,b 里有 c ...
  • 理解多態 多種多樣的形態(靜態多態,動態多態) 靜態多態(編譯時期) 1:函數重載 bool comparet(int ,int); bool compare(double,double); compare(100,100)->compare_int_int(); compare(1.0,2.0)- ...
  • 打包下載成.zip文件 項目背景 公司使用vue + SpringBoot實現批量下載功能 今天在調試批量下載這個功能。打包成.zip文件時,在返回給前端瀏覽器出現報錯信息: 後端報錯: ERROR c.c.p.c.e.BusinessExceptionHandler - java.io.IOExc ...
  • 抽象類和普通類有什麼區別? 抽象類一般不用作抽象實體類型 一般把上面類設計為抽象類? 基類 定義抽象類的唯一目的, 就是去建立派生類. 我們在抽象類基礎上要定義出功能各異的派生類, 再用這些派生類去建立對象. 凡是包含純虛函數的類都是抽象類. 純虛函數不用實現, 故不能被調用, 抽象類無法建立對象. ...
一周排行
    -Advertisement-
    Play Games
  • 前言 當別人做大數據用Java、Python的時候,我使用.NET做大數據、數據挖掘,這確實是值得一說的事。 寫的並不全面,但都是實際工作中的內容。 .NET在大數據項目中,可以做什麼? 寫腳本(使用控制台程式+頂級語句) 寫工具(使用Winform) 寫介面、寫服務 使用C#寫代碼的優點是什麼? ...
  • 前言 本文寫給想學C#的朋友,目的是以儘快的速度入門 C#好學嗎? 對於這個問題,我以前的回答是:好學!但仔細想想,不是這麼回事,對於新手來說,C#沒有那麼好學。 反而學Java還要容易一些,學Java Web就行了,就是SpringBoot那一套。 但是C#方向比較多,你是學控制台程式、WebAP ...
  • 某一日晚上上線,測試同學在回歸項目黃金流程時,有一個工單項目介面報JSF序列化錯誤,馬上升級對應的client包版本,編譯部署後錯誤消失。 線上問題是解決了,但是作為程式員要瞭解問題發生的原因和本質。但這都是為什麼呢? ...
  • 本文介紹基於Python語言中TensorFlow的Keras介面,實現深度神經網路回歸的方法。 1 寫在前面 前期一篇文章Python TensorFlow深度學習回歸代碼:DNNRegressor詳細介紹了基於TensorFlow tf.estimator介面的深度學習網路;而在TensorFl ...
  • 前段時間因業務需要完成了一個工作流組件的編碼工作。藉著這個機會跟大家分享一下整個創作過程,希望大家喜歡,組件暫且命名為"easyFlowable"。 接下來的文章我將從什麼是工作流、為什麼要自研這個工作流組件、架構設計三個維度跟大家來做個整體介紹。 ...
  • 1 簡介 我們之前使用了dapr的本地托管模式,但在生產中我們一般使用Kubernetes托管,本文介紹如何在GKE(GCP Kubernetes)安裝dapr。 相關文章: dapr本地托管的服務調用體驗與Java SDK的Spring Boot整合 dapr入門與本地托管模式嘗試 2 安裝GKE ...
  • 摘要:在jvm中有很多的參數可以進行設置,這樣可以讓jvm在各種環境中都能夠高效的運行。絕大部分的參數保持預設即可。 本文分享自華為雲社區《為什麼需要對jvm進行優化,jvm運行參數之標準參數》,作者:共飲一杯無。 我們為什麼要對jvm做優化? 在本地開發環境中我們很少會遇到需要對jvm進行優化的需 ...
  • 背景 我們的業務共使用11台(阿裡雲)伺服器,使用SpringcloudAlibaba構建微服務集群,共計60個微服務,全部註冊在同一個Nacos集群 流量轉發路徑: nginx->spring-gateway->業務微服務 使用的版本如下: spring-boot.version:2.2.5.RE ...
  • 基於php+webuploader的大文件分片上傳,帶進度條,支持斷點續傳(刷新、關閉頁面、重新上傳、網路中斷等情況)。文件上傳前先檢測該文件是否已上傳,如果已上傳提示“文件已存在”,如果未上傳則直接上傳。視頻上傳時會根據設定的參數(分片大小、分片數量)進行上傳,上傳過程中會在目標文件夾中生成一個臨 ...
  • 基於php大文件分片上傳至七牛雲,使用的是七牛雲js-sdk V2版本,引入js文件,配置簡單,可以暫停,暫停後支持斷點續傳(刷新、關閉頁面、重新上傳、網路中斷等情況),可以配置分片大小和分片數量,官方文檔https://developer.qiniu.com/kodo/6889/javascrip ...