【前端js】算法全歸納（四）對象與class：對象常用操作總結

文章目錄

• 一、建立對象
• • 1.根據包名，在指定空間中建立對象
• 二、借助對象/Map對象
• • 1.字元串中的第一個唯一字元（leetcode 387. First Unique Character in a String）
  • • • 方法一：`indexOf`和`lastIndexOf`比較（性能較差）
      • 方法二：借助對象比較（性能較好）
  • 2.字元流中第一個不重複的字元（牛客網：劍指 offer字元串專題）
  • 3.兩數之和（leetcode：1. Two Sum）
  • 3.數組中第一個重複的數字（牛客網：劍指 offer數組專題）

題目來源于牛客網前端專題：

https://www.nowcoder.com/ta/front-end?page=1

https://www.nowcoder.com/ta/js-assessment

一、建立對象

周遊對象+判斷對象類型+指針引用嵌套的對象空間

1.根據包名，在指定空間中建立對象

題目描述

根據包名，在指定空間中建立對象

輸入描述:

namespace({a: {test: 1, b: 2}}, ‘a.b.c.d’)

輸出描述:

{a: {test: 1, b: {c: {d: {}}}}}

原題：https://www.nowcoder.com/practice/a82e035501504cedbe881d08c824a381?tpId=2&tqId=10854&tPage=1&rp=1&ru=/ta/front-end&qru=/ta/front-end/question-ranking

function namespace(oNamespace, sPackage) {
  var arr = sPackage.split(".");//按順序儲存屬性值
  var obj = oNamespace;//建立指針指向對象
  for (var i = 0; i < arr.length; i++) {//周遊屬性值
    //對象中沒有該屬性，或者對象中該屬性是一個基礎資料結構
    if (!obj.hasOwnProperty(arr[i]) || !(obj[arr[i]] instanceof Object)) {
      obj[arr[i]] = {};//給該屬性指派空對象
    }

    //将指針指向這個内部對象
    obj = obj[arr[i]];
  }
  return oNamespace;//因為obj隻是對原對象的引用，原對象已被修改，最後傳回原對象的值
}
namespace({ a: { test: 1, b: 2 } }, "a.b.c.d");
           

二、借助對象/Map對象

建立對象+周遊輸入值，将key和頻率插入對象+周遊對象擷取需要的key進行操作

1.字元串中的第一個唯一字元（leetcode 387. First Unique Character in a String）

題目描述，點選檢視原題

Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.

方法一：

indexOf

和

lastIndexOf

比較（性能較差）

思路：

• 周遊字元串
• 條件一：如果字元串

  indexOf

  和

  lastIndexOf

  相等代表字元唯一，
• 條件二：不為-1代表字元存在，

• &&

  連接配接兩個條件。滿足條件傳回索引值：

var firstUniqChar = function(s) {
    for(let i in s){
    //index和lastIndex
        if(s.indexOf(s[i]) === s.lastIndexOf(s[i])&&s.indexOf(s[i])!== -1){
            return i;
        }
    }
    return -1;
};
           

方法二：借助對象比較（性能較好）

思路：

• 建立對象map，
• 周遊輸入值，将key和頻率插入對象。
• 周遊對象擷取需要的value進行操作

注意：

• 要尋找非重複字元串，就是要尋找

  頻率為1的key

  ，必須要先周遊數組/字元串，把所有的元素和頻率都插入對象了以後，再周遊對象取value=1的key；
• 但是尋找重複字元串，就是要尋找

  對象裡已經插入的key

  ，可以一邊周遊數組/字元串，一遍查詢對象中是否有對應的key，

  obj[key]不為空

  ，則代表該元素重複。

var firstUniqChar = function(s) {
    //存放頻率
     map = {};
    //周遊字元串，向map插入頻率
  for (let char of s) {
    if (map[char]) {
      map[char]++;
    } else {
      map[char] = 1;
    }
  }
 //周遊對象
  for (var key of Object.keys(map)) {
    if (map[key] === 1) {
      return s.indexOf(key);
    }
  }
  return "-1";
};
           

2.字元流中第一個不重複的字元（牛客網：劍指 offer字元串專題）

[題目描述，點選檢視原題](https://www.nowcoder.com/practice/00de97733b8e4f97a3fb5c680ee10720?tpId=13&tqId=11207&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)

請實作一個函數用來找出字元流中第一個隻出現一次的字元。例如，當從字元流中隻讀出前兩個字元"go"時，第一個隻出現一次的字元是"g"。當從該字元流中讀出前六個字元“google"時，第一個隻出現一次的字元是"l"。如果目前字元流沒有存在出現一次的字元，傳回#字元。

思路： 同上，按照要求拆分成三個方法：

//Init module if you need
var map = {};
function Init()
{
    map = {};
    // write code here
}
//Insert one char from stringstream
function Insert(ch)
{
    if(map[ch]){
        map[ch]++;
    }else{
        map[ch]=1;
    }
     
    // write code here
}
//return the first appearence once char in current stringstream
function FirstAppearingOnce()
{
    // write code here
   
for (var char of ch) {
    if (map[char] === 1) {
      return char;
    }
  }
  return "#";
}
           

3.兩數之和（leetcode：1. Two Sum）

題目描述，點選檢視原題

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

思路：

• 特殊情況： 數組長度小于1直接傳回
• 先建立 map對象，Map是一組鍵值對的結構，具有極快的查找速度。
• 然後

  forEach

  周遊數組，向map插入

  元素和索引

  。
• 最後周遊數組，查找map對象是否有

  key===內插補點

  ，擷取對應

  value（索引）j

• 如果

  j && j !== i

  ，j存在，且j不能為自身索引i（自己+自己不允許），傳回

  [i, j]

Object和Map：

1. 一個Object的key隻能是

   字元串

   或者

   Symbols

   ，但一個 Map 的鍵可以是任意值，包括函數、對象、基本類型。
2. Object中的key的順序是

   無序

   的，Map 中的鍵值是

   有序

   的，而。是以，當對它進行周遊時，Map 對象是按插入的順序傳回鍵值。
3. Object 的鍵值對個數隻能

   手動計算

   ，Map 可以通過

   size

   屬性直接擷取鍵值對個數。
4. Map 可直接進行

   for of

   疊代，而 Object 的疊代需要先

   Object.keys(obj)

   擷取它的鍵數組，然後再進行

   for of

   疊代。

MDN文檔 https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Map

var twoSum = function(nums, target) {
//建立map對象存放數組元素和索引
 let map = new Map();
 //數組長度小于1直接傳回
  if(nums.lenght<=1){
      return [];
  }
  //周遊數組，向map插入元素和索引
  nums.forEach((e, i) => map.set(e, i));
//周遊數組，查找map對象是否有key===內插補點
  for (let i = 0; i < nums.length; i++) {
    let j = map.get(target - nums[i]);
    //j存在，且j不能為自身索引i（自己+自己不允許）
    if (j && j !== i) {
      return [i, j];
    }
  }
  return [];
};
           

性能很好：

3.數組中第一個重複的數字（牛客網：劍指 offer數組專題）

題目描述，點選檢視原題

在一個長度為n的數組裡的所有數字都在0到n-1的範圍内。 數組中某些數字是重複的，但不知道有幾個數字是重複的。也不知道每個數字重複幾次。請找出數組中任意一個重複的數字。 例如，如果輸入長度為7的數組{2,3,1,0,2,5,3}，那麼對應的輸出是第一個重複的數字2。

思路：

• 特殊情況： 數組長度小于等于1直接傳回
• 先建立 map對象，Map是一組鍵值對的結構，具有極快的查找速度。
• 然後一邊

  for of

  周遊數組，一邊查詢map中是否有

  item的鍵值

  。
• 如果有，代表item是重複元素，return
• 如果沒有，代表第一次周遊item，

  map.set(item, 1)

  向map插入元素和頻率1
• 周遊結束也沒有查找到重複元素，return

function duplicate(numbers, duplication) {
  // write code here
  //這裡要特别注意~找到任意重複的一個值并指派到duplication[0]
  //函數傳回True/False
 if (numbers.lenght <= 1) {
    return false;
  }
  var map = new Map();
  for (let item of numbers) {
    if (map.has(item)) {
      duplication[0] = item;
      return true;
    }
    map.set(item, 1);
  }
  return false;
}