Leetcode No.696 Count Binary Substrings 📒

題號：No.696

類型：字串 String

難度：簡單

使用語言：JavaScript

¶題目

Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0’s and 1’s, and all the 0’s and all the 1’s in these substrings are grouped consecutively.

Substrings that occur multiple times are counted the number of times they occur.

¶Example 1:

Input: “00110011”
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1’s and 0’s: “0011”, “01”, “1100”, “10”, “0011”, and “01”.

Notice that some of these substrings repeat and are counted the number of times they occur.

Also, “00110011” is not a valid substring because all the 0’s (and 1’s) are not grouped together.

¶Example 2:

Input: “10101”
Output: 4
Explanation: There are 4 substrings: “10”, “01”, “10”, “01” that have equal number of consecutive 1’s and 0’s.

¶Note:

• s.length will be between 1 and 50,000.
• s will only consist of “0” or “1” characters.

---

¶解題切入的知識點

• string.prototype.sort
• 正規表達式 /g
  • 對於表達式對象的 exec 方法，不加入 g，則只返回第一個匹配，無論執行多少次均是如此，如果加入 g，則第一次執行也返回第一個匹配，再執行返回第二個匹配，依次類推。
• 數組常用操作方法: https://juejin.im/post/59f848026fb9a0450167420a

---

1. 使用頭部或尾部的陣列刪除方法
   • 數組尾部删除 pop（）：方法用於删除並且返回陣列最後一個元素。用法：arrayObject.pop()

push()、pop()、unshift()、shift() 

btn[3].onclick =
function
(){	var arr = [1,2,3,4,5]	
arr.pop()	
alert(arr) //1,2,3,4
}//尾部删除一個

2. 數組頭部添加 unshift() 方法可向數组的開頭增加一個或更多元素，並返回新的長度。語法：JavaScript arrayObject.unshift(newelement1,newelement2,....,newelementX)

btn[5].onclick =
function
(){	var arr = [1,2,3,4,5]	
arr.shift()	
alert(arr)//2,3,4,5
}//頭部删除一個

¶解法

思考邏輯：

1. 先將數字對應的英文字母列出
2. 將數字分割，EX: 234 ⇒ [2,3,4]
3. 組出一個新的陣列，也就是數字所對應英文字母的陣列
4. 先讓23兩個數字進行組合，再跟下一個數字進行組合

¶注意點

1. 在把數字對應的字母塞回陣列的時候，要記得判斷如果該數字有字母再塞回去
2. 跑 for 迴圈長度想得太困難，！arr[0] 代表的意思是說，比如先拿 2,3 兩兩去循環組合，2 = ‘abc’, 所以循環的長度就是 3
3. 要把一剛開始的 2,3 數字替換掉
4. 記得返回取得的數組
5. 最後面要返回 function

export default (str) => {
        //建立數字對應字母
        let map =['',1, 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tux', 'wxyz']
        //把輸入字串按照單字分隔，234=>2,3,4
        let num = str.split('');
        // 保存鍵盤映射的字母內容，23=>[abc, def]
        let code = []
        num.forEach(item => {
            if(map[item]){
                code.push(map[item])
            }       
        });
        console.log(code);
    
        let comb = (arr) => {
            //臨時變量，用來保存前兩個組合的結果
           let temp = []; 
           // 最外層的循環式是跑遍第一個元素，第二個循環是跑遍第二個元素
           let il = arr[0].length;
           let jl = arr[1].length; 
           for (let i = 0; i < il ; i++) {     
               for (let j = 0; j < jl; j++) {
                   temp.push(`${arr[0][i]}${arr[1][j]}`)
               }
           } 
    				//替換掉一開始組合的2,3，準備跟下一個繼續尬for迴圈
           arr.splice(0, 2, temp);
    				//如果還有長度繼續尬
           if(arr.length > 1 ){
               comb(arr)
           } else {
    				//沒有就把陣列返回就好
               return temp;
           }
           //最後是要返回陣列的第一個組合
           return arr[0];
             
        }
        return comb(code);
    }