前端程式員學好演算法系列(二)數組

来源:https://www.cnblogs.com/kbnet/archive/2020/07/26/13380576.html
-Advertisement-
Play Games

我們今天繼續研究數組在演算法中的應用 167. 兩數之和 II - 輸入有序數組 給定一個已按照升序排列 的有序數組,找到兩個數使得它們相加之和等於目標數。 函數應該返回這兩個下標值 index1 和 index2,其中 index1 必須小於 index2。 說明: 返回的下標值(index1 和 ...


我們今天繼續研究數組在演算法中的應用

167. 兩數之和 II - 輸入有序數組

給定一個已按照升序排列 的有序數組,找到兩個數使得它們相加之和等於目標數。

函數應該返回這兩個下標值 index1 和 index2,其中 index1 必須小於 index2。

說明:

返回的下標值(index1 和 index2)不是從零開始的。
你可以假設每個輸入只對應唯一的答案,而且你不可以重覆使用相同的元素。
示例:

輸入: numbers = [2, 7, 11, 15], target = 9
輸出: [1,2]
解釋: 27 之和等於目標數 9 。因此 index1 = 1, index2 = 2

我們這裡直接用滑動視窗進行解題:


1.定義左指針 l為0
2.定義右指針為numbers.length - 1
3.如果左指針的值和右指針的值相加等於target直接返回索引加1的值,否則大於時r-- 小於時l++

var twoSum = function(numbers, target) {
      let l = 0
      let r = numbers.length - 1
      while(l<r){
          if(numbers[l]+numbers[r]==target){  
              return [l+1,r+1]
          }
          if(numbers[l]+numbers[r]>target){
              r--
          }else{
              l++
          }    
      }
      return []
};

209. 長度最小的子數組
給定一個含有 n 個正整數的數組和一個正整數 s ,找出該數組中滿足其和 ≥ s 的長度最小的 連續 子數組,並返回其長度。如果不存在符合條件的子數組,返回 0。

示例:

輸入:s = 7, nums = [2,3,1,2,4,3]
輸出:2
解釋:子數組 [4,3] 是該條件下的長度最小的子數組。

解題:
1.設置[l,r] 左閉右閉的區間內取值,r區間預設為-1就是沒有任何元素,res初始為數組的長度加1因為我們是取最小值,數組滿足條件的值不可能大於數組長度加1
2.我們在l和r的區間內重覆取值,當區間內的值相加滿足大於s時減掉最左邊的一個元素,sum<s時讓r++同時sum加上r的值。
3.為保證數組不越界在r++前需要保證r+1< nums.length
4.每次有解時計算區間內的元素數量為 r - l +1 ,+1是因為索引是從0開始的,取有正確答案時的最小元素個數
5.當計算結果的長度為nums.length +1 時說明我們沒有找到正確的解直接返回0

var minSubArrayLen = function(s, nums) {
    let l = 0, r = -1 // [l, r], 左閉右閉
    let sum = 0  //初始化總和的值
    let res = nums.length + 1   //初始化可能的最大值加1
    while(l < nums.length){
        if((r+ 1 <nums.length) && sum < s){
            r++
            sum += nums[r]
        } else {
            sum -= nums[l]
            l++
        }
        if(sum >= s ){
            res = Math.min(res,r-l+1)
        }
        
    }
    if(res === nums.length + 1){
        return 0
    }
    return res
}

3. 無重覆字元的最長子串
給定一個字元串,請你找出其中不含有重覆字元的 最長子串 的長度。

示例 1:

輸入: "abcabcbb"
輸出: 3 
解釋: 因為無重覆字元的最長子串是 "abc",所以其長度為 3

示例 2:

輸入: "bbbbb"
輸出: 1
解釋: 因為無重覆字元的最長子串是 "b",所以其長度為 1

解題:

1.滑動視窗問題 我們在 [ans,rk]區間內取值,初始化ans為0 ,rk為-1 ,-1是為了保證滑動視窗中沒有值
2.我們創建一個set結構判斷我的的視窗中是否出現了重覆的元素,當occ.has(s.charAt(rk + 1))不存在當前字元時右區間rk++,

3.rk+1時保證數組不越界

var lengthOfLongestSubstring = function(s) {
    // 哈希集合,記錄每個字元是否出現過
    const occ = new Set();
    const n = s.length;
    // 右指針,初始值為 -1,相當於我們在字元串的左邊界的左側,還沒有開始移動
    let rk = -1, ans = 0;
    for (let i = 0; i < n; ++i) {
        if (i != 0) {
            // 左指針向右移動一格,移除一個字元
            occ.delete(s.charAt(i - 1));
        }
        while (rk + 1 < n && !occ.has(s.charAt(rk + 1))) {
            // 不斷地移動右指針
            occ.add(s.charAt(rk + 1));
            ++rk;
        }
        // 第 i 到 rk 個字元是一個極長的無重覆字元子串
        ans = Math.max(ans, rk - i + 1);
    }
    return ans;
};

 


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

-Advertisement-
Play Games
更多相關文章
  • 參考:https://juejin.im/entry/58b93af3ac502e006c0820c9 1.常見的加密方式:Base64、MD5、AES、EDS、RSA HTTPS 以及SSL/TSL 什麼是SSL?SSL(Secure Sockets Layer, 安全套接字層),因為原先互聯網上 ...
  • 1.棧的基礎使用,js中數組直接可以作為棧使用,棧遵循先進後出的原則,即js可以使用push()和pop() 比較容易的實現一個棧 20. 有效的括弧給定一個只包括 '(',')','{','}','[',']' 的字元串,判斷字元串是否有效。 有效字元串需滿足: 左括弧必須用相同類型的右括弧閉合。 ...
  • (一)單一 |【1】屬性選擇器 | | | | | | | |p[alt]|選擇具有att屬性的 |p元素 | |p[alt="val"] |選擇att屬性值 |等於val的p | |p[alt^="val"] |匹配att屬性值 |以val開頭的p | |p[alt$="val"] |匹配att屬 ...
  • 美拍短視頻按作者批量下載,去水印的方法教程,很多做自媒體搬運或者要下載美拍短視頻上面的素材,都需要批量下載美拍無水印短視頻。這裡教大家如何按作者批量下載美拍無水印短視頻,並自動修改MD5消重。此文分享的是一個線上的網站工具,不需要下載任何軟體,直接在瀏覽器里打開工具網址就可以使用的。 其實不僅僅是支 ...
  • 24. 兩兩交換鏈表中的節點給定一個鏈表,兩兩交換其中相鄰的節點,並返回交換後的鏈表。 你不能只是單純的改變節點內部的值,而是需要實際的進行節點交換。 示例: 給定 1->2->3->4, 你應該返回 2->1->4->3. 解題:我們定義4個指針如上進行節點交換,1.給head添加一個虛擬頭節點t ...
  • 原型與原型鏈 所有函數都有一個特別的屬性: prototype : 顯式原型屬性 所有實例對象都有一個特別的屬性: __proto__ : 隱式原型屬性 顯式原型與隱式原型的關係 函數的prototype: 定義函數時被自動賦值, 值預設為, 即用為原型對象 實例對象的__proto__: 在創建實 ...
  • 1.瀏覽器內核及首碼 在CSS中新的屬性標準尚未明確的情況下,各瀏覽器廠商對新屬性的支持情況也不相同,這個階段會對屬性加廠商首碼進行區分。 根據不同的瀏覽器內核,CSS首碼有所不同,最基本的瀏覽器內核有四種,其他內核都是基於此四種進行再研發的。 ① Gecko內核,首碼為“-moz-”,火狐瀏覽器 ...
  • 接下來我們來看鏈表題 206. 反轉鏈表反轉一個單鏈表。 示例: 輸入: 1->2->3->4->5->NULL 輸出: 5->4->3->2->1->NULL 解題:鏈表題需要我們設立更多的指針來保存我們當前操作的細節;1.我們需要定義3個指針 pre,cur ,next,pre為當前鏈表的前一個 ...
一周排行
    -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版本說明 機器同時安裝了 ...