# 面試作業 1
- https://leetcode.com/problems/merge-nodes-in-between-zeros/
- https://zxi.mytechroad.com/blog/list/leetcode-2181-merge-nodes-in-between-zeros/

- 🧍：盤同學妳好 歡迎參加我們這次的面試 接下來我們會給你一份考券 總共會有三題 待會麻煩您準備好後 我們就開始吧
------------------------------- [第一題](https://leetcode.com/problems/shuffle-string/) -------------------
- 🧍：ＯＫ 那我先來跟你解釋一下第一題 這題會給妳兩個資訊 一個是字串資訊 一個長度相同的整數 array 且此 array 代表的是前一個字串打亂的位置，請你幫我用相對快的方式出答案 並告訴我為什麼這樣做
- 🙂： 請問有甚麼限制嗎
- 🧍：沒關西 你可以先跟我說說你有甚麼想法
- 🙂： 好的 目前看到這款題目，如在不考慮記憶體用量的作法的話，應該會使用直接搜尋的方法，先見另一個儲存答案的陣列，之後利用FOR會圈依照後面的indeX陣列的位置放入到新的答案陣列中

class Solution {
public:
    string restoreString(string s, vector<int>& indices) {// 首先先建立一個function
        string ans;
        char strTemp[s.size()]={0};//如在不考慮記憶體用量的作法的話，直接先宣告一個所需長度的自串
        for (int i =0 ;i<indices.size();i++)//接下來建立一個for迴圈
        {
            strTemp[indices[i]]=s.at(i);依照他給的填寫index 填入到新的strTemp中
        }
        ans = strTemp;
        return ans;//之後在將答案回傳
    }
};

- 🧍：了解，那請問你知道這樣的寫法的時間複雜度是多少呢
- 🙂：以這個解法來說的話 應該是 O (n) 因為他會直接走完完整的array 一次
- 🧍:了解 那你可以實作看看嗎
- 🧍：ok 那你剛剛有說 在不考慮記憶體的情況 可以這樣做 那如果考慮記憶體呢？
- 🙂：對的 剛剛那個作法的空間複雜度是 Ｏ(n) 如果今天在記憶體有限的情快下 可以用以下作法變成 O(1)
-

class Solution {
public:
    string restoreString(string s, vector<int>& indices) {
        int n = s.size();
        //差別在可以不用宣告一個相同大小的陣列 減少一個陣列的記憶體空間
        for(int i = 0;i < n;i++)
        {
            while(indices[i] != i)//使用while 來確認陣列是否已結束
            {
                swap(s[i],s[indices[i]]);//先將目前指到的s資料 移動到由index指定的位置中 
                swap(indices[i],indices[indices[i]]);//接下來再來更改index的位置，卻寶index資料對應不變
            }
        }
        
        return s;
    }
};

- 🙂：以上方法可以省去那記憶體，但 複雜度變成O(n^2)因為他使用swap 因此這部分可以 case by case 來選擇撰寫方式
- 🧍：了解 這題你解的不錯 還從不同角度下手

------------------------------- [第二題](https://leetcode.com/problems/decode-the-message/) -------------------

- 🧍：那我們接下來來看第二題 第二題的要求是請你解密這個加密訊息，會給你一個字串的 key 與 message，分別代表密碼的key 與加密訊息，請你回傳加密訊息的原文，使用 key 中 26 個英文小寫字母第一次出現的順序作為替換表中的字母 順序。比如我給你的 key 是 happy boy，則這就代表 ('h' -> 'a', 'a' -> 'b', 'p' -> 'c', 'y' -> 'd', 'b' -> 'e', 'o' -> 'f'，之後再請你用這個密碼表來對message做解密。
- 🙂：了解 那請問是否每個字母都會出現過呢？還是會有缺少的例外事件呢？ 並請問遇到空白是會跳過嗎？
- 🧍：不會的，此題遇到空白時直接跳過保持不變，並 key 中每個字母一定會至少出現一次。
- 🙂：那我了解題目了，以目前的想法來看，應該可以分兩部來完成，第一步首先是先生成加密對找表格，可以利用 Array 等結構，也可以 Map 來完成。
- 🙂：第二步就可以利用對照表來解開訊息了。
- 。
- 🧍：ok 這看起來是沒問題 可以請你告訴我這解法的時間複雜度嗎。
- 🙂：是 O(m+n)
- 🧍：好 那請問還有其他種的解法嗎 如果不使用 array 作為對照表 有其他的的解法嗎？
- 🙂：如果使用 unordered_map 也可以完成，並執行速度應該會更快。

class Solution {
public:
    string decodeMessage(string key, string message) {
        unordered_map<char, char> d;
        d[' '] = ' ';
        int i = 0;
        string lowcase = "abcdefghijklmnopqrstuvwxyz";
        for (char c : key) {
            if (d.count(c)) continue;
            d[c] = lowcase[i++];
        }
        string ans;
        for (char c : message) ans.push_back(d[c]);
        return ans;
    }
};

- 🧍：ok ,做得很好，這種做法之後在大量資料中，搜尋也會快蠻多的，那接下來就進入第三題摟
-

------------------------------- [第三題](https://leetcode.com/problems/merge-nodes-in-between-zeros/) -------------------
- 🧍： ok.then we going to the final problem,in this problem
- 🧍： You are given the head of a linked list, which contains a series of integers separated by 0's. The beginning and end of the linked list will have Node.val == zero.
- 🧍： For every two consecutive zeros, merge all the nodes that are between them into one node whose value is the sum of all the merged nodes. The modified list should not contain any zeros. Returns the head of the modified list.
-
- 🙂： ok, got it, so i just caculate the sum of all the nodes's value between the beginning and end of the linked list have val is zero right?
- 🧍： yes ,just merge the node and return the ans list
- 🙂： and will there be two consecutive nodes with val equal to 0?
- 🧍： will not happen There are no two consecutive nodes with Node.val is 0.
- 🙂：ok , and final question , Is the Node.val at the beginning and end of the linked list both 0? Or are there other exceptions that need to be handled.
- 🧍： unnecessary The beginning and end ndoes velue is 0 of the linked list .
- 🙂： got it ,i think in this case , just need to determine the current value is 0 or not . If it is 0, then the sum of the numbers between the last 0 is stored in a modified link ; if it is not 0, then the current value is added to the sum and we go on from there.
- 🧍：ok,sound good , can you finish the code ?
- 🙂： sure

class Solution {
public:
  ListNode* mergeNodes(ListNode* head) {
    ListNode nodes;    
    head = head->next;
    for (ListNode* prev = &nodes; head; head = head->next) {
      int sum = 0;
      while (head->val != 0) {
        sum += head->val;
        head = head->next;
      }
      prev->next = head;
      head->val = sum;
      prev = head;      
    }
    return nodes.next;
  }
};

- 🧍：Well done , can you tell me what the complexity is for this problem?
- 🙂： I think Time complexity is O(n) and Space complexity is O(1)