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

来源:https://www.cnblogs.com/kbnet/archive/2020/07/25/13378754.html

前端程式員怎麼才能學好演算法呢?目前演算法優秀的視頻集中在c++,java,python,本人通過幾個月專心看c++的視頻掌握了演算法的基本思路,都翻譯成前端代碼一一寫出來,從真題到思維全面提升演算法思維面對演算法面試,不畏懼 二分查找法O(logn)尋找數組中的最大/最小值O(N)歸併排序演算法 O(nlog ...


前端程式員怎麼才能學好演算法呢?目前演算法優秀的視頻集中在c++,java,python,本人通過幾個月專心看c++的視頻掌握了演算法的基本思路,都翻譯成前端代碼一一寫出來,從真題到思維全面提升演算法思維
面對演算法面試,不畏懼

二分查找法O(logn)
尋找數組中的最大/最小值O(N)
歸併排序演算法 O(nlogn)
選擇排序演算法O(n^2)

第一題.數組 704.二分查找法

給定一個 n 個元素有序的(升序)整型數組 nums 和一個目標值 target  ,寫一個函數搜索 nums 中的 target,如果目標值存在返回下標,否則返回 -1。
示例 1:

輸入: nums = [-1,0,3,5,9,12], target = 9
輸出: 4
解釋: 9 出現在 nums 中並且下標為 4

解題:

1.在左邊界0 和右邊界arr.length -1 中進行尋找,

2.每次取最中間的元素mid,如果當前尋找的元素就是當前元素直接返回,

3.否則當前元素小於target左邊界等於mid+1 否則右邊界等於mid -1,如果沒有找到返回-1

 function binarySearch(arr,target) {
       let l = 0
       let r = arr.length - 1
       let mid
       while(l<=r){
          // mid = Math.floor((l + r)/2) 
          // 下麵的代碼解決l+r 整數溢出的問題
          mid = Math.floor(l + (r-l)/2) 
          
          if(arr[mid]===target){
             return mid
          }
          if(arr[mid] < target){
            l = mid + 1
          } else {
            r = mid - 1
          }
       }
       return -1
     }

第二題283. 移動零

給定一個數組 nums,編寫一個函數將所有 0 移動到數組的末尾,同時保持非零元素的相對順序。
示例:

輸入: [0,1,0,3,12]
輸出: [1,3,12,0,0]

說明:

必須在原數組上操作,不能拷貝額外的數組。
儘量減少操作次數。

解題:

1.我們定義一個k指針預設為0
2.迴圈數組當數組值為0時交換數組k和當前索引的值k++
3.如果 i!=k 這步針對特殊用力優化

var moveZeroes = function(nums) {
        let k = 0
        for(let i =0;i<nums.length;i++){
          if(nums[i]){
            if(i!=k){
              swap(nums,k,i)
              k++
            } else {
              k++
            }
          }
        }
        function swap(arr,i,j){
          let tmp = arr[i]
          arr[i] = arr[j]
          arr[j] = tmp
        }
};

第三題 27.移動元素

給你一個數組 nums 和一個值 val,你需要 原地 移除所有數值等於 val 的元素,並返回移除後數組的新長度。

不要使用額外的數組空間,你必須僅使用 O(1) 額外空間並 原地 修改輸入數組。

元素的順序可以改變。你不需要考慮數組中超出新長度後面的元素。

示例 1:

給定 nums = [3,2,2,3], val = 3,

函數應該返回新的長度 2, 並且 nums 中的前兩個元素均為 2。

你不需要考慮數組中超出新長度後面的元素。

解題:此題原理與上題相同

var removeElement = function(nums, val) {
    let j = 0
    let arr =[]
     for(let i =0,len=nums.length;i<len;i++){
         if(nums[i]!==val){ 
             nums[j] = nums[i]
             j++
         } 
     }
     return j
};

第四題 75. 顏色分類

給定一個包含紅色、白色和藍色,一共 n 個元素的數組,原地對它們進行排序,使得相同顏色的元素相鄰,並按照紅色、白色、藍色順序排列。

此題中,我們使用整數 0、 1 和 2 分別表示紅色、白色和藍色。

註意:
不能使用代碼庫中的排序函數來解決這道題。

示例:

輸入: [2,0,2,1,1,0]
輸出: [0,0,1,1,2,2]

解題一
暴力解法:
1.本題只有三種顏色所以我們可以給統計每個元素出現的次數保存起來然後在按數量值依次排列,代碼如下

var sortColors = function(nums) {
    let obj = {}
    for(let i =0;i<nums.length;i++){
        if(!obj[nums[i]]){
            obj[nums[i]] = 1
        } else {
            obj[nums[i]] = obj[nums[i]] + 1
        }
    }
    let index = 0
    for(let i=0;i<obj[0];i++){
        nums[index++] = 0
    }
    for(let i=0;i<obj[1];i++){
        nums[index++] = 1
    }
    for(let i=0;i<obj[2];i++){
        nums[index++] = 2
    }
};

 


解法二

三路快排

1.定義前邊界zero為-1,因為預設左邊界中沒有任何一個元素,左邊界記憶體放所有為0的元素
2. 定義右邊界tow後面的元素都是2,tow中預設也不存在任何元素
3.我們這裡for迴圈時沒有i++ 因為我們需要處理一種不需要i++的情況,噹噹前願隨num[i] ==2時我們把 tow-- 然後tow和i交換位置,此時i位置的元素為tow位置交換過去的元素,還為訪問,所以i不需要++


var sortColors = function(nums) {
     let zero = -1     // nums[0...zero] ==0
     let tow = nums.length // nums[tow..n-1] ==2
     for(let i =0;i<tow;){
         if(nums[i]===1){
             i++
         } else if(nums[i] ==2){
             --tow
            swap(nums,i,tow)
         } else {
            zero++
            swap(nums,i,zero)
            i++
         }
     }
    function swap(arr,i,j){
        let tmp =arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
    }
};

 

演算法數組入門暫時就先寫到這裡







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

更多相關文章
  • 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為當前鏈表的前一個 ...
  • 我們今天繼續研究數組在演算法中的應用 167. 兩數之和 II - 輸入有序數組 給定一個已按照升序排列 的有序數組,找到兩個數使得它們相加之和等於目標數。 函數應該返回這兩個下標值 index1 和 index2,其中 index1 必須小於 index2。 說明: 返回的下標值(index1 和 ...
一周排行
  • 比如要拆分“呵呵呵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. ...