📂
LeetCode Note
  • Introduction
  • Tools
    • Clean Code
    • 英文小辭典
    • JS Reference
    • 常見 Edge Case
    • Array Method
    • Object Method
    • Function
    • Hashing
    • Prototype
    • 處理 Array 小撇步
    • String Method
    • Math / Date
    • loop
    • JSON.xx / localStorage
    • Date
    • Regex
    • Memorization
    • reduce condition
    • 命名
  • 筆記 Note
    • Promise
    • Walking the DOM
    • Element size and scrolling
    • CSS
  • Leetcode todo
    • ToDo
  • Array
    • # Select random poker without duplicates
    • # 最少替換達成不連續字串
    • # 724 Find Pivot Index
    • # 747. Largest Number At Least Twice of Others
    • # 01 getMaxProfit
    • # maxOfBiggestVal
    • # findSecondLargest
    • # 41 First Missing Positive
    • # 134 Gas Station (有圖)
    • # 202 Happy Number
    • # 344 Reverse String
    • # 412 Fizz Buzz
    • # 561 Array Partition I
    • # 804 Unique Morse Code Words
    • # 905 Sort Array By Parity
    • # 121. Best Time to Buy and Sell Stock.js
    • # 122 Best Time to Buy and Sell Stock II
    • # 189 Rotate Array
    • # 229 Majority Element II
    • # 268 Missing Number.
    • # 299 Bulls and Cows (有圖)
    • # 896 Monotonic Array
    • # 1002 Find Common Characters
    • # 1051 Height Checker
    • # 1185 Day of the Week
    • # 169 Majority Element
    • # 605. Can Place Flowers
    • # 350 Intersection of Two Arrays II (有圖)
    • # 482. License Key Formatting
  • Set / Map
    • # GetLengthOfLongestSubstring
    • #1 Two Sum
    • # 217 Contains Duplicate
    • # 1122 Relative Sort Array
    • # 1160 Find Words That Can Be Formed by Characters
    • #811 Subdomain Visit Count
    • # 349 Intersection of Two Arrays
    • # 819 Most Common Word
  • Two Pointer
    • #704. Binary Search
    • #26 Remove Duplicates from Sorted Array (有圖)
    • #27 Remove Element
    • # 66 Plus One
    • # 80 Remove Duplicates from Sorted Array II (有圖)
    • # 88 Merge Sorted Array (有圖)
    • # 125 Valid Palindrome
    • #167 Two Sum II - Input array is sorted (有圖)
    • # 283 Move Zeroes (有圖)
    • # 38 Count and Say
    • # 557. Reverse Words in a String III
    • #977 Squares of a Sorted Array
    • #209 Minimum Size Subarray Sum
  • String
    • # 13 Roman to Integer (有圖)
    • # 771 Jewels and Stones
    • # 937 Reorder Data in Log Files
    • # 929 Unique Email Addresses
    • # 1108 Defanging an IP Address
    • #14 Longest Common Prefix
    • # 387 First Unique Character in a String (有圖)
    • #193 Valid Phone Numbers
    • # 28 Implement strStr()
    • #383 Ransom Note
  • Stack
    • # 20 Valid Parentheses (有圖)
    • # 155 Min Stack
    • BF 165. remove characters
    • #1047 Remove All Adjacent Duplicates In String
  • Binary Search
    • # 1064 Fixed Point (有圖)
    • # 852 Peak Index in a Mountain Array
  • Recursion 遞迴
    • #2625. Flatten Deeply Nested Array
  • Math
    • # 7 Reverse Integer
    • # 9 Palindrome Number (有圖)
    • #53 Maximum Subarray (有圖)
    • # 1085 Sum of Digits in the Minimum Number.
    • # 136 Single Number
    • # 204 Count Primes (有圖)
    • #243 Shortest Word Distance
  • Dynamic Programing
    • # 322 Coin Change
    • # 509 Fibonacci Number (有圖)
    • # 70 Climbing Stairs
    • # 198 House Robber
    • # 168. Excel Sheet Column Title
  • Others
    • # 205. Isomorphic Strings
    • Implement js Array method
    • Flatten Array/Object
  • Matrix
    • 867. Transpose Matrix
  • Queue
    • DOM tree with queue
  • 排序
    • Different Sort
Powered by GitBook
On this page
  • 如何解
  • 改善
  • 學到什麼

Was this helpful?

  1. String

# 387 First Unique Character in a String (有圖)

應用桶子排序 / 建立桶子 lookup = new Array(26); lookup.fill(0)

Previous#14 Longest Common PrefixNext#193 Valid Phone Numbers

Last updated 5 years ago

Was this helpful?

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

input: 給一字串
output: 找出第一個沒有重覆的字元
Examples:

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.
Note: You may assume the string contain only lowercase letters.

/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function(s) {
    
};

如何解

丟入 Map 然後抓第一個 length = 1 的值 (Map 有順序性)

var firstUniqChar = function(s) {

  let myMap = new Map();
  for(let i = 0; i < s.length; i++){
    if(myMap.has(s[i])){
      myMap.set(s[i], myMap.get(s[i]) + 1)
    }else{
      myMap.set(s[i], 1)
    }
  }
  for(let item of myMap){
    if(item[1] == 1){
      return s.indexOf(item[0])
    }
  }
  return -1;

};
// // faster than 14.00% of JavaScript online submissions

結果速度只有 14% 好慘

改善

這題應用到桶子排序,桶子排序就是抓取速度超快,但容易浪費記憶體.不過這邊因為要存字母,字母也才 26 個數字而已

let lookup = new Array(26); // 26 個英文字母桶子
// 先全部填 0 代表裡面沒東西,
// 不然預設會是 "" 空字串, "" + 數字會變 String
lookup.fill(0);

遍歷一次 s 然後把字母放到桶子

for(let i=0; i<len;i++){
    // a 就是 97,所以就是有那個字,代表那個字的桶子數字就 + 1
    lookup[ s.charCodeAt(i) - 97 ]++; 
}
var firstUniqChar = function(s) {
  let len = s.length;
  let lookup = new Array(26); // 26 個英文字母桶子
  // 先全部填 0 代表裡面沒東西,不然預設會是 undefined, undefined + 數字會變 NaN
  lookup.fill(0);

  for(let i=0; i<len;i++){
      // a 就是 97,所以就是有那個字,代表那個字的桶子數字就 + 1
      lookup[ s.charCodeAt(i) - 97 ]++; 
  }
  for(let i=0;i<len;i++){
      if( lookup[ s.charCodeAt(i) - 97 ] === 1 ){
          return i;
      }
  }
    return -1;

};
console.log(firstUniqChar("cc"))
// faster than 80.40% of JavaScript online submissions

學到什麼

這題學到蠻多,多一個新的解題方式了就是應用桶子排序解,主要就是可以先把桶子建立起來再存相對應數量進去

let lookup = new Array(26); // 26 個英文字母桶子
// 先全部填 0 代表裡面沒東西,
// 不然預設會是 undefined, undefined + 數字會變 NaN
lookup.fill(0);

LeetCode