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

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

前端程式員怎麼才能學好演算法呢?目前演算法優秀的視頻集中在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
    }
};

 

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







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

-Advertisement-
Play Games
更多相關文章
  • 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 和 ...
一周排行
    -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版本說明 機器同時安裝了 ...