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

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

我們今天繼續研究數組在演算法中的應用 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;
};

 


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

更多相關文章
  • 參考: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為當前鏈表的前一個 ...
一周排行
  • 比如要拆分“呵呵呵90909086676喝喝999”,下麵當type=0返回的是中文字元串“呵呵呵,喝喝”,type=1返回的是數字字元串“90909086676,999”, private string GetStrings(string str,int type=0) { IList<strin ...
  • Swagger一個優秀的Api介面文檔生成工具。Swagger可以可以動態生成Api介面文檔,有效的降低前後端人員關於Api介面的溝通成本,促進項目高效開發。 1、使用NuGet安裝最新的包:Swashbuckle.AspNetCore。 2、編輯項目文件(NetCoreTemplate.Web.c ...
  • 2020 年 7 月 30 日, 由.NET基金會和微軟 將舉辦一個線上和為期一天的活動,包括 微軟 .NET 團隊的演講者以及社區的演講者。本次線上大會 專註.NET框架構建微服務,演講者分享構建和部署雲原生應用程式的最佳實踐、模式、提示和技巧。有關更多信息和隨時瞭解情況:https://focu... ...
  • #abp框架Excel導出——基於vue #1.技術棧 ##1.1 前端採用vue,官方提供 UI套件用的是iview ##1.2 後臺是abp——aspnetboilerplate 即abp v1,https://github.com/aspnetboilerplate/aspnetboilerp ...
  • 前言 本文的文字及圖片來源於網路,僅供學習、交流使用,不具有任何商業用途,版權歸原作者所有,如有問題請及時聯繫我們以作處理。 作者:碧茂大數據 PS:如有需要Python學習資料的小伙伴可以加下方的群去找免費管理員領取 input()輸入 Python提供了 input() 內置函數從標準輸入讀入一 ...
  • 從12年到20年,python以肉眼可見的趨勢超過了java,成為了當今It界人人皆知的編程語言。 python為什麼這麼火? 網路編程語言搜索指數 適合初學者 Python具有語法簡單、語句清晰的特點,這就讓初學者在學習階段可以把精力集中在編程對象和思維方法上。 大佬都在用 Google,YouT ...
  • 在社會上存在一種普遍的對培訓機構的學生一種歧視的現象,具體表現在,比如:當你去公司面試的時候,一旦你說了你是培訓機構出來的,那麼基本上你就涼了,那麼你瞞著不說,然後又通過了面試成功入職,但是以後一旦在公司被髮現有培訓經歷,可能會面臨被降薪,甚至被辭退,培訓機構出來的學生,在用人單位眼裡就是能力低下的 ...
  • from typing import List# 這道題看了大佬寫的代碼,經過自己的理解寫出來了。# 從最外圍的四周找有沒有為O的,如果有的話就進入深搜函數,然後深搜遍歷# 判斷上下左右的位置是否為Oclass Solution: def solve(self, board: List[List[s ...
  • import requests; import re; import os; # 1.請求網頁 header = { "user-agent":'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537.36 (KHTML, li ...
  • import requests; import re; import os; import parsel; 1.請求網頁 header = { "user-agent":'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537. ...