【D26】二維數(shù)組&從前序與中序遍歷序列構(gòu)造二叉樹(LC 240&105)

240. 搜索二維矩陣 II

問題描述

編寫一個高效的算法來搜索 m x n 矩陣 matrix 中的一個目標(biāo)值 target 。該矩陣具有以下特性:
每行的元素從左到右升序排列。
每列的元素從上到下升序排列啥么。

解題思路1-二分查找行

遍歷每一行的首元素,如果首元素小于target菲驴,代表target有可能存在該行;再針對每一行進(jìn)行二分查找骑冗。

代碼實現(xiàn)1-二分查找行

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        //求行數(shù)n
        int n = matrix.length;

        for(int i = 0; i < n; i++){
            if(matrix[i].length != 0 && matrix[i][0] > target){
                continue;
            }
            if(binarySearch(matrix[i],target) != -1){
                return true;
            }
        }
        return false;
       
    }

    //二分查找法赊瞬,返回target在行中索引,若不存在返回-1
    public int binarySearch(int[] row, int target){
        int left = 0, right = row.length - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(row[mid] < target){
                left = mid + 1;
            }else if(row[mid] > target){
                right = mid - 1;
            }else{
                return mid;
            }
        }
        return -1;
        
    }
}
  • 時間復(fù)雜度為O(nlogn)

解題思路2-雙指針遍歷

利用數(shù)組中右下角的元素一定最大的思想
每次都可以按行/列對搜索空間進(jìn)行縮減

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        //求行數(shù)n贼涩,列數(shù)m
        int n = matrix.length, m = matrix[0].length;
        
        int row = n - 1, col = 0;
        while(row >= 0 && col < m){
            if(matrix[row][col] > target){
                row--;
            }else if (matrix[row][col] < target){
                col++;
            }else{
                return true;
            }
        }
        return false; 
    }
}
  • 時間復(fù)雜度O(m + n)

105. 從前序與中序遍歷序列構(gòu)造二叉樹

問題描述

根據(jù)一棵樹的前序遍歷與中序遍歷構(gòu)造二叉樹巧涧。
注意:你可以假設(shè)樹中沒有重復(fù)的元素。

解題思路

dfs遞歸構(gòu)建遥倦。

  • 可以利用hashMap減少每次定位根節(jié)點在中序數(shù)組中的位置所花費的時間

代碼實現(xiàn)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    //key為數(shù)組中元素的值谤绳,value為對應(yīng)的索引
    private HashMap<Integer, Integer> mapInorder = new HashMap<>();
    //將數(shù)組轉(zhuǎn)為全局變量,節(jié)省空間
    int[] pre;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int len = preorder.length;
        if(len == 0 || len != inorder.length){
            return null;
        }
        pre = preorder;
        for(int i = 0 ; i < len; i++){
            mapInorder.put(inorder[i], i);
        }
        return getTree(0, len - 1,  0, len - 1);
    }

    // preStart,preEnd表示前序遍歷數(shù)組在preorder中的開始位置袒哥、結(jié)束位置
   // inStart, int inEnd表示中序遍歷數(shù)組在inorder中的開始位置缩筛、結(jié)束位置
    public TreeNode getTree(int preStart, int preEnd, int inStart, int inEnd){
        //根節(jié)點為前序遍歷數(shù)組的首元素
        int rootVal = pre[preStart];
        TreeNode root = new TreeNode(rootVal);

        if(preStart == preEnd){
            //若樹只有一個節(jié)點,則直接返回
            return root;
        }

        //root節(jié)點在中序數(shù)組中的索引
        int rootIn = mapInorder.get(rootVal);
       
        //【構(gòu)建左子樹】
        //左子樹節(jié)點的數(shù)量
        int leftNodes = rootIn - inStart;
        if(leftNodes > 0){
            root.left = getTree(preStart + 1, preStart + leftNodes, inStart, rootIn - 1);
        }
        
        //【構(gòu)建右子樹】
        //右子樹節(jié)點的數(shù)量
        int rightNodes = inEnd - rootIn;
        if(rightNodes > 0){
            root.right = getTree(preStart + leftNodes + 1, preStart + leftNodes + rightNodes , rootIn + 1,  inEnd);
        }

        return root;
    }
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末堡称,一起剝皮案震驚了整個濱河市瞎抛,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌却紧,老刑警劉巖婿失,帶你破解...
    沈念sama閱讀 216,591評論 6 501
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異啄寡,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)哩照,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,448評論 3 392
  • 文/潘曉璐 我一進(jìn)店門挺物,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人飘弧,你說我怎么就攤上這事识藤⊙庵” “怎么了?”我有些...
    開封第一講書人閱讀 162,823評論 0 353
  • 文/不壞的土叔 我叫張陵痴昧,是天一觀的道長稽穆。 經(jīng)常有香客問我辉懒,道長登颓,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 58,204評論 1 292
  • 正文 為了忘掉前任拄查,我火速辦了婚禮豪娜,結(jié)果婚禮上餐胀,老公的妹妹穿的比我還像新娘。我一直安慰自己瘤载,他們只是感情好否灾,可當(dāng)我...
    茶點故事閱讀 67,228評論 6 388
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著鸣奔,像睡著了一般墨技。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上挎狸,一...
    開封第一講書人閱讀 51,190評論 1 299
  • 那天扣汪,我揣著相機(jī)與錄音,去河邊找鬼伟叛。 笑死私痹,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的统刮。 我是一名探鬼主播紊遵,決...
    沈念sama閱讀 40,078評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼侥蒙!你這毒婦竟也來了暗膜?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 38,923評論 0 274
  • 序言:老撾萬榮一對情侶失蹤鞭衩,失蹤者是張志新(化名)和其女友劉穎学搜,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體论衍,經(jīng)...
    沈念sama閱讀 45,334評論 1 310
  • 正文 獨居荒郊野嶺守林人離奇死亡瑞佩,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,550評論 2 333
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了坯台。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片炬丸。...
    茶點故事閱讀 39,727評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖蜒蕾,靈堂內(nèi)的尸體忽然破棺而出稠炬,到底是詐尸還是另有隱情焕阿,我是刑警寧澤,帶...
    沈念sama閱讀 35,428評論 5 343
  • 正文 年R本政府宣布首启,位于F島的核電站暮屡,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏毅桃。R本人自食惡果不足惜褒纲,卻給世界環(huán)境...
    茶點故事閱讀 41,022評論 3 326
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望疾嗅。 院中可真熱鬧外厂,春花似錦、人聲如沸代承。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,672評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽论悴。三九已至掖棉,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間膀估,已是汗流浹背幔亥。 一陣腳步聲響...
    開封第一講書人閱讀 32,826評論 1 269
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點兒被人妖公主榨干…… 1. 我叫王不留察纯,地道東北人帕棉。 一個月前我還...
    沈念sama閱讀 47,734評論 2 368
  • 正文 我出身青樓,卻偏偏與公主長得像饼记,于是被迫代替她去往敵國和親香伴。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 44,619評論 2 354

推薦閱讀更多精彩內(nèi)容