高強度學習訓練第九天總結:5道劍指offer的題目

来源:https://www.cnblogs.com/godoforange/archive/2019/09/23/11575258.html
-Advertisement-
Play Games

實在不想看JVM了。刷幾道劍指Offer的題,今天就水一水吧,腦子迷糊。 1.二維數組中的查找 在一個二維數組中(每個一維數組的長度相同),每一行都按照從左到右遞增的順序排序,每一列都按照從上到下遞增的順序排序。請完成一個函數,輸入這樣的一個二維數組和一個整數,判斷數組中是否含有該整數。 解題思路: ...


實在不想看JVM了。刷幾道劍指Offer的題,今天就水一水吧,腦子迷糊。

1.二維數組中的查找

在一個二維數組中(每個一維數組的長度相同),每一行都按照從左到右遞增的順序排序,每一列都按照從上到下遞增的順序排序。請完成一個函數,輸入這樣的一個二維數組和一個整數,判斷數組中是否含有該整數。

解題思路:從右上角開始搜索,從上到下為遞增,從右到左為遞減。根據這個思路來進行搜索,演算法複雜度n+m

public class Solution {
    public boolean Find(int target, int [][] array) {
        int x=0,y=array[0].length-1;
        while(x<array.length&&y>-1){
            if(array[x][y]>target){
                y--;
            }else if(array[x][y]<target){
                x++;
            }else{
                return true;
            }
        }
        return false;
    }
}

2.替換空格

請實現一個函數,將一個字元串中的每個空格替換成“%20”。例如,當字元串為We Are Happy.則經過替換之後的字元串為We%20Are%20Happy。

解題思路:不能一個一個插入,複雜度太高,要用空間來換取時間。一個一個賦值比較好。

public class Solution {
    public String replaceSpace(StringBuffer str) {
        StringBuffer sb = new StringBuffer();
        for(int i=0;i<str.length();i++) {
            if(str.charAt(i)==' ') {
                sb.append("%20");
            }else {
                sb.append(str.charAt(i));
            }
        }
        return sb.toString();
    }
}

3.從尾到頭列印鏈表

輸入一個鏈表,按鏈表從尾到頭的順序返回一個ArrayList。

解題思路:這題用C++的話可以直接把指針反轉,不過Java傳進來的是一個集合類。就算了吧。用傻瓜式解法。

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> al = new ArrayList<Integer>();
        while(listNode!=null) {
            al.add(0,listNode.val);
            listNode = listNode.next;
        }
        return al;
    }
}

4.重建二叉樹

輸入某二叉樹的前序遍歷和中序遍歷的結果,請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重覆的數字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6},則重建二叉樹並返回。

解題思路:遞歸建樹。基礎題。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre.length==0) return null;
        TreeNode trn = new TreeNode(pre[0]);
        if(pre.length==1) return trn;
        else for(int i=0;i<in.length;i++) {
            if(in[i]==pre[0]) {
                int [] preleft = new int[i];
                int [] preright = new int[in.length-i-1];
                int [] inleft = new int[i];
                int [] inright = new int[in.length-i-1];
                System.arraycopy(pre,1,preleft,0,i);
                System.arraycopy(pre,i+1,preright,0,in.length-i-1);
                System.arraycopy(in,0, inleft, 0, i);
                System.arraycopy(in,i+1, inright, 0, in.length-i-1);
                trn.left = reConstructBinaryTree(preleft, inleft);
                trn.right = reConstructBinaryTree(preright,inright);
                return trn;
            }
        }
        return trn;
    }
}

5.用兩個棧實現隊列

用兩個棧來實現一個隊列,完成隊列的Push和Pop操作。 隊列中的元素為int類型。

解題思路:對先進後出和先進先出的基礎理解即可想明白。

import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
     public void push(int node) {
        stack1.push(node);
    }
    
    public int pop() {
        if(!stack2.empty()) {
            return stack2.pop();
        }
        else{
            while(!stack1.empty()) {
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }
    }
}

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

-Advertisement-
Play Games
更多相關文章
  • # 1.在伺服器上 tomcat 的 bin目錄下找到並打開 catalina.sh 在文件中搜索: ``` JPDA_ADDRESS= ``` 找一個伺服器上沒有被使用的埠,填入,如50005,保存並退出。 > 如何知道某埠有沒有被占用? > 命令: > ``` > lsof -i:50005 ...
  • idea搭建spring源碼閱讀環境 安裝gradle Github下載Spring源碼 新建學習spring源碼的項目 idea搭建spring源碼閱讀環境 安裝gradle Github下載Spring源碼 新建學習spring源碼的項目 安裝gradle Github下載Spring源碼 新建 ...
  • 2019-09-23-23:48:00 今日所學的內容有: ...
  • 一、預設配置文件 二、指定配置文件 三、使用profile指定配置 ...
  • 在上篇文章: "SpringBoot源碼解析:創建SpringApplication對象實例" 中,我們詳細描述了SpringApplication對象實例的創建過程,本篇文章繼續看 方法的執行邏輯吧 1. 第一行使用了 來記錄開始時間 2. 設置了 環境變數,在網上瞭解了一下這個變數的相關信息 H ...
  • [TOC] 1. 數組操作符重載 數組操作符重載 通過重載數組操作符,可以使類的對象支持數組的下標訪問 數組操作符只能重載為類的成員函數 重載函數能且僅能使用一個參數,也就是數組下標 可以定義不同參數的多個重載函數 在重載數組操作符時,要記得數組操作符的原生語義——數組訪問和指針運算。 cpp / ...
  • 從今天起,我會在這裡記錄一下學習深度學習所留下的足跡,目的也很簡單,手頭有近3w個已經標記好正確值得驗證碼,想要從頭訓練出一個可以使用的模型, 雖然我也知道網上的相關模型和demo很多,但是還是非常希望自己可以親手搞一個能用的出來,學習書籍主要是:李金洪老師的《深度學習之Tensorflow 入門、 ...
  • 在做數據分析的過程中,經常會遇到文件的讀取。我想很多人都在這個環節遇到過問題,所以就把自己掌握的一些文件讀取方法記錄下來,以及過程中遇到的一些狀況和解決方法列出來,以便交流。 open open() 函數用於創建或打開指定文件,該函數的語法格式如下: 參數說明: file:表示要創建的文件對象。 f ...
一周排行
    -Advertisement-
    Play Games
  • Timer是什麼 Timer 是一種用於創建定期粒度行為的機制。 與標準的 .NET System.Threading.Timer 類相似,Orleans 的 Timer 允許在一段時間後執行特定的操作,或者在特定的時間間隔內重覆執行操作。 它在分散式系統中具有重要作用,特別是在處理需要周期性執行的 ...
  • 前言 相信很多做WPF開發的小伙伴都遇到過表格類的需求,雖然現有的Grid控制項也能實現,但是使用起來的體驗感並不好,比如要實現一個Excel中的表格效果,估計你能想到的第一個方法就是套Border控制項,用這種方法你需要控制每個Border的邊框,並且在一堆Bordr中找到Grid.Row,Grid. ...
  • .NET C#程式啟動閃退,目錄導致的問題 這是第2次踩這個坑了,很小的編程細節,容易忽略,所以寫個博客,分享給大家。 1.第一次坑:是windows 系統把程式運行成服務,找不到配置文件,原因是以服務運行它的工作目錄是在C:\Windows\System32 2.本次坑:WPF桌面程式通過註冊表設 ...
  • 在分散式系統中,數據的持久化是至關重要的一環。 Orleans 7 引入了強大的持久化功能,使得在分散式環境下管理數據變得更加輕鬆和可靠。 本文將介紹什麼是 Orleans 7 的持久化,如何設置它以及相應的代碼示例。 什麼是 Orleans 7 的持久化? Orleans 7 的持久化是指將 Or ...
  • 前言 .NET Feature Management 是一個用於管理應用程式功能的庫,它可以幫助開發人員在應用程式中輕鬆地添加、移除和管理功能。使用 Feature Management,開發人員可以根據不同用戶、環境或其他條件來動態地控制應用程式中的功能。這使得開發人員可以更靈活地管理應用程式的功 ...
  • 在 WPF 應用程式中,拖放操作是實現用戶交互的重要組成部分。通過拖放操作,用戶可以輕鬆地將數據從一個位置移動到另一個位置,或者將控制項從一個容器移動到另一個容器。然而,WPF 中預設的拖放操作可能並不是那麼好用。為瞭解決這個問題,我們可以自定義一個 Panel 來實現更簡單的拖拽操作。 自定義 Pa ...
  • 在實際使用中,由於涉及到不同編程語言之間互相調用,導致C++ 中的OpenCV與C#中的OpenCvSharp 圖像數據在不同編程語言之間難以有效傳遞。在本文中我們將結合OpenCvSharp源碼實現原理,探究兩種數據之間的通信方式。 ...
  • 一、前言 這是一篇搭建許可權管理系統的系列文章。 隨著網路的發展,信息安全對應任何企業來說都越發的重要,而本系列文章將和大家一起一步一步搭建一個全新的許可權管理系統。 說明:由於搭建一個全新的項目過於繁瑣,所有作者將挑選核心代碼和核心思路進行分享。 二、技術選擇 三、開始設計 1、自主搭建vue前端和. ...
  • Csharper中的表達式樹 這節課來瞭解一下表示式樹是什麼? 在C#中,表達式樹是一種數據結構,它可以表示一些代碼塊,如Lambda表達式或查詢表達式。表達式樹使你能夠查看和操作數據,就像你可以查看和操作代碼一樣。它們通常用於創建動態查詢和解析表達式。 一、認識表達式樹 為什麼要這樣說?它和委托有 ...
  • 在使用Django等框架來操作MySQL時,實際上底層還是通過Python來操作的,首先需要安裝一個驅動程式,在Python3中,驅動程式有多種選擇,比如有pymysql以及mysqlclient等。使用pip命令安裝mysqlclient失敗應如何解決? 安裝的python版本說明 機器同時安裝了 ...