2023年11月8日 星期三

FastAIoT config 欄位

"name": Service 名稱

"central_broker" & "app_broker": port 與 IP 的設定

    "host"

    "management_port"

    "connection_port"

"input": DataName_DataFormat (ex: png_image, acc_nparray)

"output": DataName_DataFormat (ex: fall_text, speech_text)

"topology": "source" & "destination" pair

    "type": "input", "output", "server"

    "queue"

            if type == "input" or "output": DataName_DataFormat 

            else: ModelName_<input/output>_DataFormat

            (ex: "HumanDetector_output_image", "FallDetectorLSTM_input_nparray")

(ex:

    "source":

            "type": "input",

            "queue": "png_image"      

     "destination":

             "type": "server",

            "queue": "FallDetectorGCN_input_image")

FastAIoT 平台,自建 service

 不用 central broker 版本:

import pika, sys, os

import numpy as np

import cv2

import torch

from torch import nn

import torchvision


os.environ["KMP_DUPLICATE_LIB_OK"]="TRUE"


# load the COCO dataset category names

# we will use the same list for this notebook

COCO_INSTANCE_CATEGORY_NAMES = [

    '__background__', 'person', 'bicycle', 'car', 'motorcycle', 'airplane', 'bus',

    'train', 'truck', 'boat', 'traffic light', 'fire hydrant', 'N/A', 'stop sign',

    'parking meter', 'bench', 'bird', 'cat', 'dog', 'horse', 'sheep', 'cow',

    'elephant', 'bear', 'zebra', 'giraffe', 'N/A', 'backpack', 'umbrella', 'N/A', 'N/A',

    'handbag', 'tie', 'suitcase', 'frisbee', 'skis', 'snowboard', 'sports ball',

    'kite', 'baseball bat', 'baseball glove', 'skateboard', 'surfboard', 'tennis racket',

    'bottle', 'N/A', 'wine glass', 'cup', 'fork', 'knife', 'spoon', 'bowl',

    'banana', 'apple', 'sandwich', 'orange', 'broccoli', 'carrot', 'hot dog', 'pizza',

    'donut', 'cake', 'chair', 'couch', 'potted plant', 'bed', 'N/A', 'dining table',

    'N/A', 'N/A', 'toilet', 'N/A', 'tv', 'laptop', 'mouse', 'remote', 'keyboard', 'cell phone',

    'microwave', 'oven', 'toaster', 'sink', 'refrigerator', 'N/A', 'book',

    'clock', 'vase', 'scissors', 'teddy bear', 'hair drier', 'toothbrush'

]


model = torchvision.models.detection.fasterrcnn_resnet50_fpn(pretrained=True)

model.eval()

class PersonDetector():

    def __init__(self) -> None:

        self.connection = pika.BlockingConnection(pika.ConnectionParameters(host='192.168.56.1', port=5672))

        self.channel = self.connection.channel()


        self.channel.exchange_declare(exchange="PersonDetector", exchange_type="topic", auto_delete=True, arguments={"output":["PersonDetector_output_text"]})

        self.channel.queue_declare(queue='PersonDetector_input_image', exclusive=True)

        self.channel.queue_bind(queue="PersonDetector_input_image", exchange="PersonDetector", routing_key=f"*.*.*.image")

        

        # load model

        print("Start loading model")

        #model = torchvision.models.detection.fasterrcnn_resnet50_fpn(pretrained=True)

        #model.eval()

        print("Load model successfully")


    

    def __callback(self, ch, method, properties, body):

        if "PersonDetector" in method.routing_key:

            pass

        else:

            routing_key_tokens = method.routing_key.split(".")

            app_name = routing_key_tokens[0]

            client_id = routing_key_tokens[1]

            

            # preprocessing

            img_bytes = np.frombuffer(body, dtype=np.uint8)

            img = cv2.imdecode(img_bytes, 1)

            cv2.cvtColor(img, cv2.COLOR_BGR2RGB)

            img = img.astype(np.float32) / 255.0

            img = torch.tensor(img)

            img = img.permute(2, 0, 1)

            


            # detect

            pred = model([img])

            pred_class = [COCO_INSTANCE_CATEGORY_NAMES[i] for i in list(pred[0]['labels'].numpy())]

            pred_boxes = [[(i[0], i[1]), (i[2], i[3])] for i in list(pred[0]['boxes'].detach().numpy())]

            pred_score = list(pred[0]['scores'].detach().numpy())

            pred_t = [pred_score.index(x) for x in pred_score if x>0.7][-1]

            pred_boxes = pred_boxes[:pred_t+1]

            pred_class = pred_class[:pred_t+1]

            for cls in pred_class:

                if cls == "person":

                    print(f"person detect!!!")


                

    def run(self):

        self.channel.basic_consume(queue='PersonDetector_input_image', on_message_callback=self.__callback, auto_ack=True)


        print(' [*] Waiting for messages. To exit press CTRL+C')

        self.channel.start_consuming()

        

        

if __name__ == '__main__':

    try:

        detector = PersonDetector()

        detector.run()

    except KeyboardInterrupt:

        print('Interrupted')

        try:

            sys.exit(0)

        except SystemExit:

            os._exit(0)


==========

import pika

import pandas as pd

import numpy as np


connection = pika.BlockingConnection(pika.ConnectionParameters(host='192.168.56.1', port=5672))

channel = connection.channel()



with open(f"C:\\Users\\Cherry\\Downloads\\image.jpg", "rb") as f:

    data = f.read()

channel.basic_publish(exchange='PersonDetector',

                        routing_key=f'PersonDetection.client0.null.image',

                        body=data)

connection.close()

print("finish")

2023年9月26日 星期二

啟動 FastAIoT 平台

Conda

啟動 conda 環境: conda activate aiot


Central broker

打開 docker console ,找到 rabbitmq 點選 start

回到程式資料夾底下,啟動 central broker


Config 

刪除或新增"APP"的UI介面,上傳 config

啟動:

python main.py

上傳:

POST -> try it out -> 選擇檔案 -> execute

查看 Responses -> Code,如果有成功會寫: Build App successfully



Server

到 application 的資料夾底下,啟動 server

python server.py


Client

到 application 的資料夾底下,用 client.py 送資料

python client.py --audio <filename>.wav



Build container from a dockerfile

docker build -t <name> .

docker run --rm <name>

2023年9月15日 星期五

Multi Camera Multi Target Python* Demo (openvino) (fail)

git clone https://github.com/openvinotoolkit/open_model_zoo.git

cd open_model_zoo\demos

cd multi_camera_multi_target_tracking_demo\python

conda create --name openvino python=3.7

conda activate openvino

pip install openvino

cd ..\..

pip install -r requirements.txt

cd multi_camera_multi_target_tracking_demo\python

pip install openvino-dev

pip install --upgrade pip

pip install .

omz_downloader --list models.lst

omz_converter --list models.lst

python multi_camera_multi_target_tracking_demo.py -i "\cam1.mp4" "\cam4.mp4" --m_detector "\open_model_zoo\demos\multi_camera_multi_target_tracking_demo\python\intel\person-detection-retail-0013\FP16\person-detection-retail-0013.xml" --m_reid "\open_model_zoo\demos\multi_camera_multi_target_tracking_demo\python\intel\person-reidentification-retail-0277\FP16\person-reidentification-retail-0277.xml" --config configs\person.py --output_video outout.avi


有執行結果,但完全不準 = W =


ref:

https://github.com/openvinotoolkit/open_model_zoo/tree/master/demos/multi_camera_multi_target_tracking_demo/python

安裝 Torchreid (fail)

git clone https://github.com/KaiyangZhou/deep-person-reid.git

cd deep-person-reid/

conda create --name torchreid python=3.7

conda activate torchreid

pip install -r requirements.txt

pip install torch==1.12.0+cu113 torchvision==0.13.0+cu113 torchaudio==0.12.0 --extra-index-url https://download.pytorch.org/whl/cu113

python setup.py develop

python scripts/main.py --config-file configs/im_osnet_x1_0_softmax_256x128_amsgrad_cosine.yaml --transforms random_flip random_erase --root ./dataset data.save_dir log/osnet_x1_0_dukemtmcreid_softmax_cosinelr # train不起來




dataset: 
https://drive.google.com/file/d/0B8-rUzbwVRk0c054eEozWG9COHM/view

安裝 CMU Object Detection & Tracking for Surveillance Video Activity Detection (fail)

# method 1

conda create --name cmuOD python=3.7

conda activate cmuOD

pip install -r requirements.txt

conda install tensorflow-gpu==1.15

python obj_detect_tracking.py --model_path obj_v3_model --version 3 --video_dir v1-val_testvideos --video_lst_file v1-val_testvideos.lst --frame_gap 1 --get_tracking --tracking_dir test_track_out # can't successfully execute yet

(ref: 最簡單的python Tensorflow-gpu安裝方法)


# method 2

conda create --name cmuOD python=3.7  

conda activate cmuOD

conda install -c conda-forge cudatoolkit=10.0 cudnn=7.6.5

pip install -r requirements.txt

pip install tensorflow-gpu==1.15




# test tensorflow with GPU

from tensorflow.python.client import device_lib

print(device_lib.list_local_devices())


# requirements.txt

numpy==1.19

scipy

scikit-learn

opencv-python

matplotlib

pycocotools

tqdm

protobuf==3.20.*

psutil

pyyaml

2023年9月7日 星期四

安裝 MC-MOT

link: https://github.com/daedalus-tech/mc-mot



conda create -n mc-mot python=3.10

conda activate mc-mot

pip install torch==1.12.0+cu113 torchvision==0.13.0+cu113 torchaudio==0.12.0 --extra-index-url https://download.pytorch.org/whl/cu113

pip install opencv-python

pip install pandas

pip install psutil

pip install pyyaml

pip install tqdm

pip install ultralytics

pip install filterpy 

python calibrate.py --video1 .\cam1.mp4 --video2 .\cam4.mp4 --homography-pth .\homography

python main.py --video1 .\cam1.mp4 --video2 .\cam4.mp4 --homography .\homography.npy

安裝 Simple-HRNet

git clone https://github.com/stefanopini/simple-HRNet.git

cd simple-HRNet

conda env remove -n hrnet

conda create -n hrnet python=3.9

conda activate hrnet

pip install -r requirements.txt

pip install torch==1.12.0+cu113 torchvision==0.13.0+cu113 torchaudio==0.12.0 --extra-index-url https://download.pytorch.org/whl/cu113



# demo

python scripts/live-demo.py --camera_id 0 --single_person --device cuda


python scripts/live-demo.py --filename video.mp4 --single_person --disable_vidgear --save_video

2023年9月5日 星期二

ASUS Vivobook 連接耳機後麥克風無法收音的問題排除

1. 先檢查麥克風熱鍵(F9)是否開啟

2. 如開啟後仍無聲音,檢查麥克風設定。如:Google Meet 中,設定 > 音訊 > 麥克風 要選擇 Microphone Array 而不是預設的 Microphone;Skype 同理也可解決


不知為何預設的音訊來源不能用,記得不管是哪個軟體或程式,把麥克風音訊的來源裝置設定一下即可。


2023年9月4日 星期一

docker 指令筆記

# 用特定路徑底下的 dockerfile build image

docker build -t welcome-to-docker .


#  多個 container 組在一起啟動

docker compose up -d


# 查看有哪些 images

docker images

2023年8月26日 星期六

[label studio] Import pre-annotated data

 先講心得:超麻煩。可能是我沒看清楚文件,加上 label-studio 在上傳標記資料集的功能沒設計很好,來來回回搞很久才成功。

[label studio] The number of files exceeded settings.DATA_UPLOAD_MAX_NUMBER_FILES

 照著圖片中的方法:



由於我是用 anaconda ,所以檔案的路徑是:

C:\Users\<username>\anaconda3\envs\<envname>\Lib\site-packages\label_studio\core\settings\base.py


在最上方找地方加上 DATA_UPLOAD_MAX_NUMBER_FILES = None


就 ok 了。


ref: https://github.com/HumanSignal/label-studio/issues/4556

2023年8月2日 星期三

安裝 mmtracking

conda create -n mmtrack python=3.8 pip numpy -y

conda activate mmtrack

pip install torch==1.12.0+cu113 torchvision==0.13.0+cu113 torchaudio==0.12.0 --extra-index-url https://download.pytorch.org/whl/cu113

pip install mmcv-full -f https://download.openmmlab.com/mmcv/dist/cu113/torch1.12.0/index.html

pip install mmdet==2.28.0

pip install opencv-python

git clone https://github.com/open-mmlab/mmtracking.git

cd mmtracking

pip install -r requirements/build.txt

pip install -v -e .


驗證套件有被正確安裝:

import torch, mmcv, mmdet

print(torch.__version__)

print(mmcv.__version__)

print(mmdet.__version__)



demo

python demo/demo_mot_vis.py configs/mot/deepsort/sort_faster-rcnn_fpn_4e_mot17-private.py --input demo/demo.mp4 --output mot.mp4




官方的下載說明根本裝不起來,試了好幾個小時才弄好。避免繞路,把能成功安裝的指令記錄下來。

2023年7月5日 星期三

在 anaconda 上面跑使用 cuda

1. 進入網站 https://pytorch.org/get-started/locally/

2. 依據需求選擇選項,記得選conda

3. 複製指令,貼到 anaconda prompt 上

4. done


測試:




or

pip install https://download.pytorch.org/whl/ + 網址中的指定檔案連結

cp 指的是 python 版本

2023年6月23日 星期五

Conda 指令筆記

建創環境

conda create -n my_env python=3.7 numpy Keras


啟動環境

# For  conda 4.6 and later versions on Linux/macOS/Windows, use

conda activate my_env

#For conda versions prior to 4.6 on Linux/macOS, use 

source activate my_env

#For conda versions prior to 4.6 on Windows, use 

activate my_env


列出套件

# If the environment is not activated

conda list -n env_name

# If the environment is activated

conda list

# To see if a specific package, say `scipy` is installed in an environment

conda list -n env_name scipy


關閉環境

# For  conda 4.6 and later versions on Linux/macOS/Windows, use

conda deactivate

#For conda versions prior to 4.6 on Linux/macOS, use 

source deactivate

#For conda versions prior to 4.6 on Windows, use 

deactivate


移除環境

conda env remove -n env_name



其他

pip freeze > requirements.txt

pip install -r requirements.txt



2023年6月21日 星期三

[Python] Command Line arguments 使用範例

get_input_args.py

import argparse

def get_input_args():

    # Create Parse using ArgumentParser
    parser = argparse.ArgumentParser()

    # Create 3 command line arguments as mentioned above using add_argument() from ArguementParser method
    parser.add_argument('--dir', type = str, default = 'pet_images/', 
                    help = 'path to the folder of pet images') 
    parser.add_argument('--arch', type = str, default = 'vgg',
                        help = 'which CNN Model Architecture')
    parser.add_argument('--dogfile', type = str, default = 'dognames.txt',
                        help = 'Text File with Dog Names')
    
    # Replace None with parser.parse_args() parsed argument collection that 
    # you created with this function 
    return parser.parse_args()


main.py

in_arg = get_input_args()

print(in_arg.dir)

2023年6月18日 星期日

在 pythonanywhere 上部署 Flask web + install package

雖然有內建先在環境裝好常見的套件,但仍有些要手動安裝。


1. Dashboard > new console

2. Create a virtualenv

ex:

mkvirtualenv myvirtualenv --python=/usr/bin/python3.10

3. install packages

ex:

pip install -r requirements.txt

4. update Configuration 

要讓 web app 知道要在我們指定的環境上運行。

Web > Virtualenv > "your path"

ex:

/home/myusername/.virtualenvs/myvirtualenv

5. Reload


如果無法順利打開,可以看 Log。


ref

https://help.pythonanywhere.com/pages/Virtualenvs/

2023年6月17日 星期六

VirtualBox Ubuntu 全螢幕時黑屏 ( black screen when full screen)

Take the VRAM to the max of 128 MB (VM Settings » Display » Screen).

機器關機時,回到 virtual box

設定 > 顯示 > 視訊記憶體 調到  128 MB。


ref

https://forums.virtualbox.org/viewtopic.php?t=91084

2023年6月16日 星期五

Unity 專案上傳至 GitHub

整包專案全部上傳太大,用 gitignore 選擇只將需要的 push 上去。

參考下方連結內的 .gitignore。

https://douduck08.wordpress.com/2017/01/01/gitignore-setting-for-unity/

安裝 Unity Recorder

 新版本的 Unity 無法直接安裝 Unity Recorder。


方法:

1. Open Project Manager

2.  clicking  "+" > "Add package by name..."

3.  type "com.unity.recorder"


等待一段時間後即可。


ref

https://forum.unity.com/threads/cant-find-unity-recorder.908690/

在 VirtualBox 上安裝 Ubuntu 與共享資料夾、調整螢幕大小、雙向剪貼簿

簡易步驟:

1. 裝 VirtualBox

2. 下載 Ubuntu iso 檔

3. 新增虛擬機與設定


共享資料夾:

1.  把資料夾加入共用 (記得選取「自動掛載」)

2.  試試看打開資料夾


https://ubuntu.com/tutorials/how-to-run-ubuntu-desktop-on-a-virtual-machine-using-virtualbox#2-create-a-new-virtual-machine

設定與在 virtualbox 的 ubuntu 共享資料夾所遇問題 " You do not have the permissions necessary to view the contents of "

打開 terminal,輸入

sudo adduser $USER vboxsf

後重啟即可解決。


ref

https://askubuntu.com/questions/890729/this-location-could-not-be-displayed-you-do-not-have-the-permissions-necessary

2023年6月8日 星期四

1351. Count Negative Numbers in a Sorted Matrix

解題思路

先以單一個 row 來看,要怎麼找有幾個負數?

根據題目說明的特性,只要找到從哪裡開始都是負數的位置就好。那可以用 binary search。

譬如:[4,3,2,-1],最後 left 會停在 -1 的位置,那就可以算有幾個負數。

另外,因為下面的 row 肯定負數/正數的邊界只會越靠左,所以可以先存這邊以加快速度。

程式碼

class Solution {
public:
    int helper(vector<vector<int>>& grid, int& right, int row)
    {
        int left = 0;
        while(left <= right)
        {
            int mid = (left + right) / 2;
            if(grid[row][mid] >= 0)
                left++;
            else
                right--;
        }
        right = min(right, left);
        return grid[row].size() - left;
    }
    int countNegatives(vector<vector<int>>& grid) {
        int ans = 0, right = grid[0].size() - 1;
        for(int i=0; i<grid.size(); i++)
        {
            ans += helper(grid, right, i);
        }
        return ans;
    }
};

2023年6月7日 星期三

1318. Minimum Flips to Make a OR b Equal to c

解題思路

每次都把 a, b, c 的LSB 抓出來看,如果 a, b 的 bit OR 不等於 c,就要進一步檢查。

如果 c 是 0,代表 a,b 一定要都是0,所以算 a, b是1的數量。

如果 c 是 1,那就只需要改一個bit,直接加一就好。


程式碼

class Solution {
public:
    int minFlips(int a, int b, int c) {
        int ans = 0;
        while(a != 0 || b!= 0 || c != 0)
        {
            int m1 = a % 2, m2 = b % 2, m3 = c % 2;
            if((m1 | m2) != m3)
            {
                if(m3 == 0)
                    ans += (m1 == 1) + (m2 == 1);
                else
                    ans += 1;
            }
            a /= 2;
            b /= 2;
            c /= 2;
        }
        return ans;
    }
};

2023年5月30日 星期二

705. Design HashSet

解題思路

昨天的 leetcode daily 也是 hash map ,但已經偷懶用 single array 來解了,今天不能再偷懶下去,不然就失去解題意義(其實是看到discussion裡面有人說:「你確定你會在面試時用這種解法嗎?」)


hash 通常會搭配 linked-list,而 list 這個 stl 容器就是用 double-linked list 實現的。

另外 vector 的 resize 可以用來動態改變大小。


至於 prime 數字大小怎麼選擇暫時沒想到,這裡的數字是抄別人的。

程式碼

class MyHashSet {
public:
    int size;
    vector<list<int>> table;
    MyHashSet() {
        size = 10007;
        table.resize(size);
    }
    
    void add(int key) {
        int hash = key % size;
        table[hash].push_back(key);
    }
    
    void remove(int key) {
        int hash = key % size;
        table[hash].remove(key);
    }
    
    bool contains(int key) {
        int hash = key % size;
        return find(table[hash].begin(), table[hash].end(), key) != table[hash].end();
    }
};

2023年5月24日 星期三

2542. Maximum Subsequence Score

解題思路

解法參考其他大神,沒指望自己能想出來,只是順手紀錄幾個部分。

pair sorting 是預設 sort first element。

以及

sort(rbegin(), rend()) 是由大排序到小。

程式碼

class Solution {
public:
    long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<pair<int, int>> v;
        for(int i=0; i<nums1.size(); i++)
            v.push_back({nums2[i], nums1[i]});
        sort(rbegin(v), rend(v));

        long long ans = 0, currentSum = 0;
        priority_queue<int, vector<int>, greater<int>> pq;
        for(auto [second, first] : v)
        {
            pq.emplace(first);
            currentSum += first;

            if(pq.size() > k)
            {
                currentSum -= pq.top();
                pq.pop();
            }
            if(pq.size() == k)
                ans = max(ans, currentSum * second);
        }
        return ans;
    }
};

2023年5月23日 星期二

2563. Count the Number of Fair Pairs

解題思路

先假設 sort 好的 input = [0, 1, 4, 4, 5, 7]。很明顯不可能把 array  中任兩個數字的 pair 都檢查一次,這樣時間複雜度太高。

要簡化,直覺想到要調整 boundary,至少某些數字超過 upper 想也知道要排除掉。

用這個邏輯往下繼續想,其實可以用兩個 pointer 構成的boundary,找出當下有幾個符合的 pair。

譬如說當 left = 0, right = 4 時,代表數字 0 跟 1、4、4、5 都是可以選擇的組合,共有四個。

用這個方法找出所有 < upper 的 pair,在減掉其中 < lower 的組合即可。

程式碼

class Solution {
public:
    long long helper(vector<int>& nums, int bound)
    {
        long long ans = 0;
        int left = 0, right = nums.size() - 1;
        while(left < right)
        {
            while(left < right && nums[left] + nums[right] > bound)
                right--;
            ans += right - left;
            left++;
        }
        return ans;
    }
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        sort(nums.begin(), nums.end());
        return helper(nums, upper) - helper(nums, lower - 1);
    }
};

2023年5月17日 星期三

2130. Maximum Twin Sum of a Linked List

解題思路

題目要求兩兩對應點和的最大值。要能找到一個點的對應點,就要能找到中間在哪。

在 linked list 中找中間,可以用 two pointer。

再來觀察 two pointer,當 linked list 是偶數長度時,slow pointer 會一一走訪左半部的 node,停在中間靠右的 node。

所以可以在找中間點的同時,用 stack 紀錄點的數值。當找到中間點時,一個個 pop 出來跟當前的 node value 相加,看看是不是最大值。

程式碼

class Solution {
public:
    int pairSum(ListNode* head) {
        ListNode *slow, *fast;
        fast = slow = head;

        stack<int> st;
        int maxSum = 0;
        while(fast && fast->next)
        {
            st.push(slow->val);
            slow = slow->next;
            fast = fast->next->next;
        }
        while(slow)
        {     
            maxSum = max(maxSum, slow->val + st.top());
            st.pop();
            slow = slow->next;
        }
        return maxSum;
    }
};

2023年5月14日 星期日

2095. Delete the Middle Node of a Linked List

解題思路

看到找 linked list 中間節點,就知道是使用 fast-slow pointer。

程式碼

class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {
        if(head->next == nullptr)
            return nullptr;
        ListNode *fast, *slow, *prev;
        fast = slow = head;

        while(fast && fast->next)
        {
            prev = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        prev->next = slow->next;
        return head;
    }
};

2023年5月13日 星期六

2466. Count Ways To Build Good Strings

解題心得

推導後會發現這是爬樓梯問題的變化版。

程式碼

class Solution {
public:
    int countGoodStrings(int low, int high, int zero, int one) {
        vector<int> dp(high + 1, 0);
        dp[0] = 1;

        int count = 0, mod = 1e9 + 7;
        for(int i=1; i<=high; i++)
        {
            dp[i] = (i >= zero ? dp[i-zero] : 0) + (i >= one ? dp[i-one] : 0);
            dp[i] %= mod;
            if(low <= i && i <= high)
                count = (count + dp[i]) % mod;
        }
        return count;
    }
};

2023年4月24日 星期一

1047. Remove All Adjacent Duplicates In String

解題思路

看題目敘述就知道是用 stack 的概念。

原本是先用 stack 存字元,最後再從 stack 裡面把剩下的組合還原成答案。但這樣會 TLE。

改成不用 stack,直接在字串上操作。

程式碼

class Solution {
public:
    string removeDuplicates(string s) {
        string ans = "";
        for(int i=0; i<s.size(); i++)
        {
            if(ans.back() == s[i])
                ans.pop_back();
            else
                ans += s[i];
        }
        return ans;
    }
};

2023年4月19日 星期三

1372. Longest ZigZag Path in a Binary Tree

解題思路

遍歷整棵樹,然後不斷更新當下的 zigzag 長度與整棵樹最常 zigzag 長度。

程式碼

原本的程式
class Solution {
public:
    void helper(TreeNode* root, bool lastIsLeft, int currentL, int& maxL)
    {
        if(root == nullptr)
            return;

        maxL = max(maxL, currentL);
        if(lastIsLeft)
        {
            helper(root->left, true, 1, maxL);
            helper(root->right, false, currentL + 1, maxL);
        }
        else
        {
            helper(root->left, true, currentL + 1, maxL);
            helper(root->right, false, 1, maxL);
        }

    }
    int longestZigZag(TreeNode* root) {
        int maxL = 0;
        helper(root->left, true, 1, maxL);
        helper(root->right, false, 1, maxL);
        return maxL;
    }
};
chatGPT 改進後的程式
class Solution {
public:
    void helper(TreeNode* root, int leftLen, int rightLen, int& maxLen) {
        if (root == nullptr) {
            return;
        }
        maxLen = max(maxLen, max(leftLen, rightLen));
        helper(root->left, rightLen + 1, 0, maxLen);
        helper(root->right, 0, leftLen + 1, maxLen);
    }

    int longestZigZag(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        int maxLen = 0;
        helper(root, 0, 0, maxLen);
        return maxLen;
    }
};

2023年4月18日 星期二

2645. Minimum Additions to Make Valid String

解題思路

我是轉換成類似 finite state 的概念。假設當下預計要看到 a,但是字串當下指到的不是 a,就代表要多加一個字元;如果指到的是 a,則代表可以指到字串下一個位置繼續比對。

然後整個字串看完,還是要把檢查當下的 state。只有 stateA 是走完了,stateB 跟 stateC 要額外加上字元。

程式碼
class Solution {
public:
    int addMinimum(string word) {
        bool stateA = true, stateB = false, stateC = false;
        int count = 0, i=0;
        while(i < word.size())
        {
            if(stateA)
            {
                if(word[i] != 'a') count++;
                else i++;
                stateA = false;
                stateB = true;
            }
            else if(stateB)
            {
                if(word[i] != 'b') count++;
                else i++;
                stateB = false;
                stateC = true;
            }
            else if(stateC)
            {
                if(word[i] != 'c') count++;
                else i++;
                stateC = false;
                stateA = true;
            }
        }
        if(stateB) count += 2;
        else if(stateC) count += 1;
        return count;
    }
};

2023年4月3日 星期一

743. Network Delay Time

解題心得

Dijkstra 演算法實作。

1. emplace_back 會把該筆資料放到最末端;emplace 是放入任意位置。

2. 用 minHeap,是因為在演算法中,要取出當下 cost 最小的路徑來做更新。

3. 用 max(),是因為找出傳到所有 node 最少需要的時間,又最遠 node 要得最久。

4. 如果無法每個 node 都拜訪,則回傳 -1。

程式碼

typedef pair<int, int> edge; // target node, weight;

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<edge>> graph(n+1);
        for(int i=0; i<times.size(); i++)
            graph[times[i][0]].emplace_back(times[i][1], times[i][2]);
        
        priority_queue<edge, vector<edge>, greater<edge>> minHeap;
        vector<bool> isVisited(n+1, false);
        minHeap.emplace(0, k);
        int ans = 0;
        while(!minHeap.empty())
        {
            int w1, n1;
            w1 = minHeap.top().first, n1 = minHeap.top().second;
            minHeap.pop();
            if(isVisited[n1])
                continue;
            isVisited[n1] = true;
            ans = max(ans, w1);

            for(int i=0; i<graph[n1].size(); i++)
            {
                int w2 = graph[n1][i].second, n2 = graph[n1][i].first;
                if(!isVisited[n2])
                    minHeap.emplace(w1 + w2, n2);
            }
        }
        for(int i=1; i<=n; i++)
        {
            if(!isVisited[i])
                return -1;
        }
        return ans;
    }
};

2023年3月31日 星期五

684. Redundant Connection

解題思路

用 union find 來解這題。

如果 edge 的兩個 node 已屬於同個 union,即可知該 edge 為多餘的。

程式碼

class Solution {
public:
    int *dsu, *rank;
    int size;

    int find_set(int v)
    {
        if(dsu[v] == v) return v;
        return dsu[v] = find_set(dsu[v]);
    }
    void make_union(int u, int v)
    {
        u = find_set(u), v = find_set(v);
        if(u != v)
        {
            if(rank[u] > rank[v])
            {
                dsu[v] = u;
                rank[u] += rank[v]; 
            }
            else
            {
                dsu[u] = v;
                rank[v] += rank[u]; 
            }
        }
    }
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        this->size = edges.size() + 1;
        this->dsu = new int[size];
        this->rank = new int[size];

        for(int i=0; i<size; i++)
        {
            dsu[i] = i;
            rank[i] = 1;
        }

        for(int i=0; i<edges.size(); i++)
        {
            if(find_set(edges[i][0]) == find_set(edges[i][1]))
                return edges[i];
            make_union(edges[i][0], edges[i][1]);
        }    
        return edges[0];
    }
};

2023年3月28日 星期二

130. Surrounded Regions

解題心得

從邊緣的 O 往內走訪,最後再回頭重新檢視誰要被翻過去。

程式碼

class Solution {
public:
    void helper(vector<vector<char>>& board, vector<vector<bool>>& notFlip, int x, int y)
    {
        if(x < 0 || y < 0 || x >= board.size() || y >= board[0].size())
            return;
        if(board[x][y] == 'X' || notFlip[x][y])
            return;

        int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
        notFlip[x][y] = true;
        for(int i=0; i<4; i++)
        {
            helper(board, notFlip, x+dx[i], y+dy[i]);
        }
    }
    void solve(vector<vector<char>>& board) {
        vector<vector<bool>> notFlip(board.size(), vector<bool>(board[0].size(), false));
        for(int i=0; i<board.size(); i++)
        {
            for(int j=0; j<board[0].size(); j++)
            {
                if(board[i][j] == 'O' && (i == 0 || i == board.size() - 1 || j == 0 || j == board[0].size() - 1))
                {
                    helper(board, notFlip, i, j);
                }
            }
        }
        for(int i=0; i<board.size(); i++)
        {
            for(int j=0; j<board[0].size(); j++)
            {
                if(board[i][j] == 'O' && !notFlip[i][j])
                    board[i][j] = 'X';
            }
        }
    }
};

2023年3月22日 星期三

90. Subsets II

解題思路

因為有重複的數字,所以可能會有重複的組合出現。

要避免這種情況,那麼就要知道,這個求解的過程就是每次都在選或不選當下的數字。如果不選,就代表該數字未來也不會選,所以要把 i 往後推。

程式碼

class Solution {
public:
    void helper(vector<int>& nums, vector<vector<int>>& ans, vector<int> current, int start)
    {
        ans.push_back(current);
        for(int i=start; i<nums.size(); i++)
        {
            
            current.push_back(nums[i]);
            helper(nums, ans, current, i+1);
            current.pop_back();
            int next = i+1;
            while(next <nums.size() &&nums[next] == nums[i])
                next++;
            i = next-1;
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> current;
        sort(nums.begin(), nums.end());
        helper(nums, ans, current, 0);
        return ans;
    }
};

2023年3月20日 星期一

215. Kth Largest Element in an Array

解題思路

覺得這題跟 703. Kth Largest Element in a Stream 非常像,甚至還比這題簡單,但兩個題目的難度標示卻不是這樣,不懂。

程式碼

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> pq;
        for(int i=0; i<nums.size(); i++)
        {
            pq.push(nums[i]);
            if(pq.size() > k)
                pq.pop();
        }
        return pq.top();
    }
};

1046. Last Stone Weight

解題思路

每次要找出最大與次大,最方便的方法是用 max heap。

程式碼

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> pq;
        for(int i=0; i<stones.size(); i++)
            pq.push(stones[i]);
        while(pq.size() != 1)
        {
            int first = pq.top(); pq.pop();
            int second = pq.top(); pq.pop();
            pq.push(first - second);
        }
        return pq.top();
    }
};

2023年3月19日 星期日

703. Kth Largest Element in a Stream

解題思路

minHeap 以 priority queue 的實作練習。

程式碼

class KthLargest {
public:
    priority_queue<int, vector<int>, greater<int>> pq;
    int size;

    KthLargest(int k, vector<int>& nums) {
        size = k;
        for(int i=0; i<nums.size(); i++)
        {
            pq.push(nums[i]);
            if(pq.size() > size)
                pq.pop();
        }
    }
    
    int add(int val) {
        pq.push(val);
        if(pq.size() > size)
            pq.pop();
        return pq.top();
    }
};

2023年3月18日 星期六

關於 vscode 調整 interpreter 之後炸掉的那回事

 vscode 底下那條藍色的 bar 偏右側有一個地方,點擊後可選擇 interpreter。隨便選了一個後,莫名的用 vscode terminal 做某些操作就會出現問題,把 python 與 vscode 刪掉重裝仍然沒有解決。


後來是把 default 的 interpreter 改到新安裝的 python 的路徑就正常了,但是執行指令要打 py 而不 python,例如:py -m venv myenv。這個部分感覺跟這個有關,先存著以後有需要再來看。

1472. Design Browser History

解題思路

其實就照題目敘述實作即可。

只是 back() 的部分要注意,如果 stack 裡面只剩一個就不要 pop 了,不然連首頁都會不見。

程式碼

class BrowserHistory {
public:
    stack<string> backHistory;
    stack<string> forwardHistory;
    
    BrowserHistory(string homepage) {
        backHistory.push(homepage);
    }
    
    void visit(string url) {
        while (!forwardHistory.empty())
            forwardHistory.pop();
        backHistory.push(url);
    }
    
    string back(int steps) {
        while (steps  && backHistory.size() > 1) {
            forwardHistory.push(backHistory.top());
            backHistory.pop();
            steps--;
        }
        return backHistory.top();
    }
    
    string forward(int steps) {
        while (steps && !forwardHistory.empty()) {
            backHistory.push(forwardHistory.top());
            forwardHistory.pop();
            steps--;
        }
        return backHistory.top();
    }
};

2023年3月17日 星期五

1448. Count Good Nodes in Binary Tree

解題思路

基本上就是 traverse 整棵樹,然後不斷紀錄這條 path 的最大值,以及更新 count 的次數。

程式碼

class Solution {
public:
    void helper(TreeNode* root, int curMax, int& count)
    {
        if(root == nullptr)
            return;
        if(root->val >= curMax)
            count++;
        curMax = max(curMax, root->val);
        helper(root->left, curMax, count);
        helper(root->right, curMax, count);

    }
    int goodNodes(TreeNode* root) {
        int count = 0;
        helper(root, root->val, count);
        return count;
    }
};

572. Subtree of Another Tree

解題思路

直覺反應是 same tree 的延伸題。

程式碼
class Solution {
public:
    bool isSame(TreeNode* root, TreeNode* subRoot)
    {
        if(root == nullptr && subRoot == nullptr)
            return true;
        if(root == nullptr || subRoot == nullptr)
            return false;
        return root->val == subRoot->val && isSame(root->left, subRoot->left)
        && isSame(root->right, subRoot->right);
    }
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if(root == nullptr)
            return false;
        return isSame(root, subRoot) || isSubtree(root->left, subRoot) ||
            isSubtree(root->right, subRoot);
    }
};

2023年3月15日 星期三

958. Check Completeness of a Binary Tree

解題思路

所謂 complete 的意思是,node 盡可能地滿,只會在最右下方有 null。這代表一旦有 null 出現,後面一定都不會再有 node。利用這樣的特性去 traverse 整棵樹。

程式碼

class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);

        bool flag = false;
        while(!q.empty())
        {
            TreeNode* node = q.front();
            q.pop();

            if(node == nullptr)
                flag = true;
            else if(flag)
                return false;
            else
            {
                q.push(node->left);
                q.push(node->right);
            }
            
        }
        return true;
    }
};

23. Merge k Sorted Lists

解題思路

如果考慮一次 merge k 的太麻煩,就兩兩 merge 來簡化問題。

merge 的部分偷懶用遞迴,有機會的話改成非遞迴的版本。

程式碼

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size() == 0) return nullptr;
        while(lists.size() > 1)
        {
            lists.push_back(merge2Lists(lists[0], lists[1]));
            lists.erase(lists.begin());
            lists.erase(lists.begin());
        }
        return lists[0];
    }
    ListNode* merge2Lists(ListNode* l1, ListNode* l2)
    {
        if(!l1) return l2;
        if(!l2) return l1;
        if(l1->val <= l2->val)
        {
            l1->next = merge2Lists(l1->next, l2);
            return l1;
        }
        else
        {
            l2->next = merge2Lists(l1, l2->next);
            return l2;
        }
    }
};

2023年3月14日 星期二

129. Sum Root to Leaf Numbers

解題心得

把 tree 給走訪一遍。若走到 left node 就把累計的加起來。

程式碼

class Solution {
public:
    void helper(TreeNode* root, int& sum, int current)
    {
        current = current * 10 + root->val;
        if(root->left == nullptr && root->right == nullptr)
        {
            sum += current;
            cout << current << endl;
            return;
        }
        else
        {
            if(root->left) helper(root->left, sum, current);
            if(root->right) helper(root->right, sum, current);
        }
    }
    int sumNumbers(TreeNode* root) {
        int sum = 0;
        helper(root, sum, 0);
        return sum;
    }
};

2023年3月12日 星期日

2. Add Two Numbers

解題思路

很基本的大數加法,只是用 linked list 來做而已。

程式碼

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode();
        ListNode *head = dummy;

        int add = 0;
        while(l1 && l2)
        {
            int sum = 0;
            if(l1)
                sum += l1->val;
            if(l2)
                sum += l2->val;

            sum += add;
            head->next = new ListNode(sum % 10);
            add = sum / 10;
            head = head->next;
            l1 = l1->next;
            l2 = l2->next;
        }
         while(l1)
        {
            head->next = new ListNode((l1->val + add) % 10);
            add = (l1->val + add) / 10;
            head = head->next;
            l1 = l1->next;
        }
         while(l2)
        {
            head->next = new ListNode((l2->val + add) % 10);
            add = (l2->val + add) / 10;
            head = head->next;
            l2 = l2->next;
        }
        if(add != 0)
            head->next = new ListNode(add);
        return dummy->next;
    }
};

138. Copy List with Random Pointer

解題思路

要 deep copy 一個 linked list,而且該 linked list 有名為 random 的屬性,會隨機指到 list 中其他 node。

用 two pass 的方式解題,第一次單純把 node 與 val 弄好,第二次則根據對照把 random 補上去。

程式碼

class Solution {
public:
    Node* copyRandomList(Node* head) {
        Node *dummy = new Node(0);
        Node *newHead = dummy, *p = head;
        unordered_map<Node*, Node*> mp; // old, new

        while(p != nullptr)
        {
            newHead->next = new Node(p->val);
            newHead = newHead->next;
            mp[p] = newHead;
            p = p->next;
        }

        newHead = dummy->next, p = head;
        while(newHead != nullptr)
        {
            newHead->random = mp[p->random];
            newHead = newHead->next;
            p = p->next;
        }
        return dummy->next;
    }
};

2023年3月11日 星期六

143. Reorder List

解題思路

可以把步驟拆分為三大項:

1. 把 list 分為左右半,用 slow-fast pointer 即可求得

2. 把右半 list 給 reverse,這題同樣寫過

3. 兩個 list merge,這題同樣也寫過

程式碼 

class Solution {
public:
    void reorderList(ListNode* head) {
        // find the mid point and split the list to two
        ListNode *slow = head, *fast = head;
        while(fast != nullptr && fast->next != nullptr)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        
        // reverse the second part of the list
        ListNode* prev = nullptr, *second = slow->next;
        ListNode* next;
        slow->next = nullptr;
        while(second != nullptr)
        {
            next = second->next;
            second->next = prev;
            prev = second;
            second = next;
        }
        
        // merge two list
        ListNode *firstHead = head, *secondHead = prev, *next1, *next2;
        while(secondHead != nullptr)
        {
            next1 = firstHead->next;
            next2 = secondHead->next;
            firstHead->next = secondHead;
            secondHead->next = next1;
            firstHead = next1;
            secondHead = next2;
        }
    }
};

2023年3月10日 星期五

153. Find Minimum in Rotated Sorted Array

解題思路

要找斷裂處的右側值。又根據特性,斷裂處右側的數字都會比 index 0 來的小,所以可以用二分搜尋來縮小與排除。

程式碼

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1, mid;
        if(nums.size() == 1 || nums[0] < nums[nums.size() - 1])
            return nums[0];

        while(left <= right)
        {
            mid = (left + right) / 2;
            if(nums[0] <= nums[mid])
                left = mid + 1;
            else
                right = mid - 1;
        }
        return nums[left];
    }
};

2023年3月9日 星期四

875. Koko Eating Bananas

解題思路

直覺想到這題是在解等式,假設答案為 x,那該等式為 ceil(piles[i]/i) 的 sum 要小於等於 h,找出最小的 x。

只是要怎麼求 x?很酷的方法是想成 x 的所有可能範圍值介在 1 ~ max(piles),然後用 binary search 的方式縮小範圍。如果 mid 是可以的,那就再往左邊試看看更小的還有無機會(right shift);如果不行代表 left 要往右移一點。

程式碼

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int maxPile = 0;
        for(int i=0; i<piles.size(); i++)
            maxPile = max(maxPile, piles[i]);

        int left = 1, right = maxPile, mid;
        while(left <= right)
        {
            mid = (left + right) / 2;
            long long int hour = 0;
            for(int i=0; i<piles.size(); i++)
                hour += ceil((double)piles[i] / mid);
            if(hour > h)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return left;
    }
};

2023年3月8日 星期三

74. Search a 2D Matrix

解題思路

先找 row 再找 column 的 binary search 版本

明明題目本身很簡單,卻卡在某些 edge case 上面好久.....

程式碼

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int left = 0, right = matrix.size() - 1, mid = 0;
        // find which row
        while (left <= right) {
            mid = (left + right) / 2;
            if (matrix[mid][0] <= target && (mid == matrix.size()-1 || target < matrix[mid+1][0]))
                break;
            if (matrix[mid][0] > target)
                right = mid - 1;
            else
                left = mid + 1;
        }
        // find which column
        left = 0, right = matrix[0].size() - 1;
        int row = mid;
        while (left <= right) {
            mid = (left + right) / 2;
            if (matrix[row][mid] == target)
                return true;
            if (matrix[row][mid] > target)
                right = mid - 1;
            else
                left = mid + 1; 
        }
        return false;
    }
};

2023年3月6日 星期一

853. Car Fleet

解題思路

第一步是想要怎麼找出最後速度會相等的車?速度最後會相等,代表出發位置靠後的車會趕上前面的車,也表示靠後的車原本到達目的地的時間會比較短。

時間的計算則是 (目的地位置 - 出發位置) / 車速。

又因為兩車相遇後,快車速度變慢,所以用stack紀錄有哪些車,而快車就不放進去。最後stack長度即為解。

程式碼

class Solution {
public:
    int carFleet(int target, vector<int>& position, vector<int>& speed) {
        vector<pair<int, int>> cars;
        for(int i=0; i<position.size(); i++)
            cars.push_back(make_pair(position[i], speed[i]));
        sort(cars.begin(), cars.end());

        stack<pair<int, int>> st;
        st.push(cars.back());
        double currentTime = (target - cars.back().first) / (double)cars.back().second;
        for(int i=cars.size() - 2; i>=0; i--)
        {
            if((target - cars[i].first)/(double)cars[i].second > currentTime)
            {
                st.push(cars[i]);
                currentTime = (target - cars[i].first)/(double)cars[i].second;
            }
        }
        return st.size();
    }
};

2023年3月5日 星期日

22. Generate Parentheses

解題思路

很明顯需要用到遞迴的方式來解。只是要加 ( 或 ) 的條件不一樣。

( 的話,只要數量還沒到 n ,就可以加。

) 的話,除了數量到 n 了沒外,還要看 ( 的數量夠不夠,不然亂加就是 invalid。

終止條件自然是 ( 跟 ) 都夠了。

程式碼

class Solution {
public:
    void helper(string s, int open, int close, int n, vector<string>& v)
    {
        if(open == n && close == n)
            v.push_back(s);
        if(open < n)
            helper(s + "(", open + 1, close, n, v);
        if(open > close)
            helper(s + ")", open, close + 1, n, v);
    }
    vector<string> generateParenthesis(int n) {
        vector<string> v;
        helper("", 0, 0, n, v);
        return v;
    }
};

2023年3月4日 星期六

239. Sliding Window Maximum

解題思路

看 neetcode 的方法來解這題。

btw 問了 chatGPT 發現我寫的程式碼還是太醜了XD

程式碼

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        vector<int> ans;
        for(int i=0; i<k; i++)
        {
            while(!dq.empty() && nums[i] > dq.back())
                dq.pop_back();
            dq.push_back(nums[i]);
        }
        ans.push_back(dq.front());
        for(int i=1; i<(nums.size() - k + 1); i++)
        {
            if(dq.front() == nums[i-1])
            {
                dq.pop_front();
            }
            while(!dq.empty() && nums[i+k-1] > dq.back())
                dq.pop_back();
            dq.push_back(nums[i+k-1]);
            ans.push_back(dq.front());
        }
        return ans;
    }
};

2023年3月3日 星期五

76. Minimum Window Substring

解題思路

很容易聯想到 sliding window,若該 window 中所有字母出現次數與希望的一樣,就看長度決定是否更新。

比對的方式則是該兩個 index  array 以及 have 跟 need 兩個 int。index array 用來記錄該字母的出現次數,need 表示需要幾個「字母」種類(不考慮次數),have 表示現階段的 sliding window 有幾個「字母」(同樣不考慮次數)。

那要怎麼移動 sliding window?暴力解是 O(n^2) 的方法,也就是每個字母依序當開頭,然後每次就開頭 + 1、開頭 + 2的一路看到最後。但有時若已經 valid ,那就可以提前結束。

至此還可以進一步優化。當找到新的 valid window,可以回過頭把 left 往右移,一直到 invalid 為止,這麼做是因為可能前面包含到多餘的子字串。記得這個 pop 的動作也要檢查 have 是否要減少。

程式碼 

class Solution {
public:
    string minWindow(string s, string t) {
        if(t.size() > s.size()) return "";

        int countS[128] = {0}, countT[128] = {0}, left = 0, right = 0;
        int have = 0, need = 0, minLen = s.size()+1, minL = 0, minR = 0;
        bool isFind = false;
        for(int i=0; i<t.size(); i++)
        {
            countT[t[i]]++;
            if(countT[t[i]] == 1) // meet first time
                need++;
        }

        while(right < s.size())
        {
            // add right element into countS
            countS[s[right]]++;
            // check countS[i] == countT[i] ?
                // if true, have++
            if(countS[s[right]] == countT[s[right]])
                have++;
            // check have == need?
                // if true, update window len if needed
                // pop from front until have != need
            while(have == need)
            {
                if((right - left + 1) < minLen)
                {
                    minLen = right - left + 1;
                    minL = left;
                    minR = right;
                    isFind = true;
                }
                countS[s[left]]--;
                if(countS[s[left]] < countT[s[left]])
                    have--;
                left++;
            }
            right++;
        }
        if(!isFind) return "";
        return s.substr(minL, minLen);
    }
};

2023年3月2日 星期四

567. Permutation in String

解題思路

要找 s2 中存不存在 s1 的排列組合,又排列組合肯定是長度為 len(s1) 的,所以就想到用 sliding window,接下來就每次比較出現的字母數量就好。

程式碼

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        if(s1.size() > s2.size()) return false;
        int countS1[26] = {0};
        for(int i=0; i<s1.size(); i++)
            countS1[s1[i] - 'a']++;

        for(int i=0; i<(s2.size() - s1.size() + 1); i++)
        {
            int countS2[26] = {0};
            for(int j=i; j<(i+s1.size()); j++)
            {
                countS2[s2[j] - 'a']++;
            }
            bool isSame = true;
            for(int j=0; j<26; j++)
            {
                if(countS1[j] != countS2[j])
                {
                    isSame = false;
                    break;
                }
                
            }
            if(isSame)
                return true;
        }
        return false;
    }
};

2023年3月1日 星期三

424. Longest Repeating Character Replacement

解題思路

首先,要找到「valid substring」的條件是:

substring length - max frequency letter count in substring <= k

因為最常出現的肯定是主體,剩下不常見的是要被替換的,那這些被替換的字母數量一定要小於題目規定的數字 k。

接著 substring 又是怎麼產生的?概念是 sliding window,所以就會有 left 跟 right pointer。


每次更新完 sliding window 中字母出現次數,都看該 sliding window 是 valid 的嗎?如果是,那就把 right 往右移,以及看看 ans 有無變化;如果不是,那就要把 left 往右移,以及把 count 也更新。


程式碼

class Solution {
public:
    int characterReplacement(string s, int k) {
        int count[26] = {0}, left = 0, right = 0, maxF = 0;
        int ans = 0;
        while(right < s.size())
        {
            count[s[right] - 'A']++;
            maxF = max(maxF, count[s[right] - 'A']);
            
            if((right - left + 1) - maxF > k)
            {
                count[s[left] - 'A']--;
                left++;
            }
            
            ans = max(ans, right - left + 1);
            right++;
        }
        return ans;
    }
};

2023年2月28日 星期二

42. Trapping Rain Water

解題思路

這題看題目時沒想法,但看完 neetcode 的解法後恍然大悟。我覺得分析問題時,如果當下沒辦法想出演算法,可以先用人類笨方法思索人類會怎麼解問題。確定這解法 ok 後,再轉換成比較電腦的形式,一步步轉換過去。

程式碼

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size(), ans = 0, minHeight;
        vector<int> leftMax(n, 0);
        vector<int> rightMax(n, 0);

        for(int i=1; i<n; i++)
        {
            leftMax[i] = max(leftMax[i-1], height[i-1]);
            rightMax[n-1-i] = max(rightMax[n-i], height[n-i]);
        }
        for(int i=0; i<n; i++)
        {
            minHeight = min(leftMax[i], rightMax[i]);
            ans += max(minHeight - height[i], 0);
        }
        
        return ans;
    }
};

2023年2月27日 星期一

167. Two Sum II - Input Array Is Sorted

解題思路

因為 sorted array 的特性,選擇用 two pointer 來解。

當 left pointer 往右移,代表數字總和會變大;當 right pointer 往左移,代表數字總和會變小。由於一定能找到解,因此就不斷重述這樣的動作,查看當下兩個 pointer 的數字和並跟 target 比較,一直到找到為止。

程式碼

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0, right = numbers.size() - 1;
        while((numbers[left] + numbers[right]) != target)
        {
            if((numbers[left] + numbers[right]) > target)
                right--;
            else
                left++;
        }

        vector<int> ans;
        ans.push_back(left + 1);
        ans.push_back(right + 1);
        return ans;
    }
};

2023年2月26日 星期日

347. Top K Frequent Elements

解題思路

這題可以用 maxHeap 的概念來解。又因為 sort 的依據是出現次數,但 key 是數字本身的值,所以用 pair。

首先建立 integer 跟其出現次數的 map,接著再從該 map 轉換放進 maxHeap 中。由於 priority_queue 是看 first 來 sort ,因此這邊選擇以 {e.second, e.first} 的形式來 push。

接下來只要 pop k 次 maxHeap 即可。注意此時要的是 maxHeap 的 second。

程式碼

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        priority_queue<pair<int, int>> maxHeap; // integer, occurence
        vector<int> ans;
        unordered_map<int, int> mp;
        for(int i=0; i<nums.size(); i++)
            mp[nums[i]]++;
        
        for(auto e:mp)
            maxHeap.push({e.second, e.first});
        
        for(int i=0; i<k; i++)
        {
            ans.push_back(maxHeap.top().second);
            maxHeap.pop();
        }
        return ans;
    }
};

2023年2月25日 星期六

128. Longest Consecutive Sequence

解題思路

基本上就是把不同的連續數列串在一起,每串的頭是最小的數,ex: 1->2->3->4。

所以先用 set 紀錄整個 array 中有哪些數字,接著再從頭看起。若該數是串的頭(不存在 nums[i]-1),哪麼就計算該串的長度(用 set 一直檢查 nums[i]+offset 存不存在)。

程式碼

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(nums.size() <= 1) return nums.size();
        
        set<int> s;
        for(int i=0; i<nums.size(); i++)
            s.insert(nums[i]);
        
        int maxLen = 1;
        for(int i=0; i<nums.size(); i++)
        {
            // check if it the head of seq first
            if(!s.count(nums[i] - 1))
            {
                int curLen = 1, offset = 1;
                while(s.count(nums[i] + offset))
                {
                    offset++;
                    curLen++;
                    maxLen = max(maxLen, curLen);
                }
            }
        }
        return maxLen;
    }
};

2023年2月24日 星期五

19. Remove Nth Node From End of List

解題思路

不用 reverse 就能刪倒數第  n 個節點,只要用 two pointer。left pointer 跟 right pointer 不是平常的差一個,而是差 n 個節點。如此一來,當 right pointer 指向 null 時,left pointer 指到的恰好就是我們想要刪掉的節點。

但真正方便的是指向要刪掉的前一個節點,這樣才能進行刪除。為了達成此目標,選擇 left node 一開始指向 dummy node。

程式碼

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *dummy = new ListNode();
        ListNode *left = dummy, *right = head;
        dummy->next = head;

        for(int i=0; i<n; i++)
            right = right->next;
        
        while(right != nullptr)
        {
            left = left->next;
            right = right->next;
        }
        left->next = left->next->next;
        return dummy->next;
    }
};

2023年2月22日 星期三

417. Pacific Atlantic Water Flow

解題思路

反向思考,從海到陸是否可以。

用 dfs 解兩次。

程式碼

class Solution {
public:

    void dfs(int x, int y, vector<vector<int>>& heights, vector<vector<bool>>& isVisited, int prevH)
    {
        if(x < 0 || y < 0 || x >= heights.size() || y >= heights[0].size() 
        || isVisited[x][y] || heights[x][y] < prevH)
            return;
        isVisited[x][y] = true;
        dfs(x - 1, y, heights, isVisited, heights[x][y]);
        dfs(x + 1, y, heights, isVisited, heights[x][y]);
        dfs(x, y - 1, heights, isVisited, heights[x][y]);
        dfs(x, y + 1, heights, isVisited, heights[x][y]);
    }

    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        vector<vector<bool>> pac(heights.size(), vector<bool>(heights[0].size(), false));
        vector<vector<bool>> alt(heights.size(), vector<bool>(heights[0].size(), false));

        for(int i=0; i<heights.size(); i++)
        {
            dfs(i, 0, heights, pac, heights[i][0]);
            dfs(i, heights[0].size() - 1, heights, alt, heights[i][heights[0].size() - 1]);
        }
        for(int i=0; i<heights[0].size(); i++)
        {
            dfs(0, i, heights, pac, heights[0][i]);
            dfs(heights.size() - 1, i, heights, alt, heights[heights.size()- 1][i]);
        }

        vector<vector<int>> ans;
        for(int i=0; i<heights.size(); i++)
        {
            for(int j=0; j<heights[0].size(); j++)
            {
                if(pac[i][j] && alt[i][j])
                    ans.push_back({i, j});
            }
        }
        return ans;

    }
};

208. Implement Trie (Prefix Tree)

解題思路

看題目敘述直接想到之前寫過的 208. Implement Trie (Prefix Tree),所以直接拿那題的程式改改看。

Node class 跟 addWord 直接複製貼上,而 search 需要修改。兩題差別在於要思考遇到 . 要怎麼辦,其實就是找當下節點底下有哪些路徑,全走過一遍找看看,所以會需要重複呼叫函式。進一步改寫後就變 dfs 了。

程式碼

class Node{
public:
    bool isEnd;
    Node* child[26];
    Node()
    {
        isEnd = false;
        for(int i=0; i<26; i++)
            child[i] = nullptr;
    }
};
class WordDictionary {
public:
    Node* root = new Node();
    WordDictionary() {
        
    }
    
    void addWord(string word) {
        Node* current = root;
        for(int i=0; i<word.size(); i++)
        {
            if(current->child[word[i] - 'a'] == nullptr)
                current->child[word[i] - 'a'] = new Node();
            current = current->child[word[i] - 'a'];
        }
        current->isEnd = true;
    }
    bool dfs(Node* root, int start, string& word)
    {
        Node* current = root;
        for(int i=start; i<word.size(); i++)
        {
            if(word[i] == '.')
            {
                for(auto child : current->child)
                {
                    if(child != nullptr && dfs(child, i+1, word))
                        return true;
                }
                return false;
            }
            else if(current->child[word[i] - 'a'] == nullptr)
                return false;
            current = current->child[word[i] - 'a'];
        }
        return current->isEnd == true;
    }
    bool search(string word) {
        return dfs(root, 0, word);
    }
};

2023年2月21日 星期二

152. Maximum Product Subarray

解題思路

題目敘述讓我想到之前寫過 53. Maximum Subarray 這題,只是變成乘積最大。

一樣另外開陣列,存當下那個數的 subarray 最大能多少。但乘法與加法不一樣,兩個負數相乘會變回正,所以也要存最負 array。

程式碼

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        vector<int> maxArr(nums.size(), 0);
        vector<int> minArr(nums.size(), 0);
        maxArr[0] = nums[0];
        minArr[0] = nums[0];

        int maxP = maxArr[0];
        for(int i=1; i<nums.size(); i++)
        {
            maxArr[i] = max({nums[i], maxArr[i-1] * nums[i], minArr[i-1] * nums[i]});
            minArr[i] = min({nums[i], maxArr[i-1] * nums[i], minArr[i-1] * nums[i]});
            maxP = max(maxP, maxArr[i]);
        }
        return maxP;
    }
};

2023年2月20日 星期一

49. Group Anagrams

解題思路

anagram 經過 sort 後會長的一樣,用這個特性以 map 與 vector 紀錄,再轉成指定的型態回傳。

程式碼

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<int>> mp; // word -> index
        string s;
        for(int i=0; i<strs.size(); i++)
        {
            s = strs[i];
            sort(s.begin(), s.end());
            mp[s].push_back(i);
        }
        vector<vector<string>> ans;
        for(auto word : mp)
        {
            vector<string> v;
            for(int i=0; i<word.second.size(); i++)
            {
                v.push_back(strs[word.second[i]]);
            }
            ans.push_back(v);
        }
        return ans;
    }
};

2023年2月19日 星期日

36. Valid Sudoku

解題思路

分成 row, column 以及九個 box,個別計算。 

程式碼

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int row[9][10] = {0}, col[9][10] = {0}, box[9][10] = {0};
        for(int i=0; i<9; i++)
        {
            for(int j=0; j<9; j++)
            {
                if(board[i][j] == '.') continue;
                row[i][board[i][j] - '0']++;
                col[j][board[i][j] - '0']++;
                box[i/3*3 + j/3][board[i][j] - '0']++;
                if(row[i][board[i][j] - '0'] > 1 || col[j][board[i][j] - '0'] > 1 || box[i/3*3 + j/3][board[i][j] - '0'] > 1)
                {
                    cout << row[i] << " " << col[j] << " " << box[i/3*3 + j/3] << endl;
                    return false;
                }    
            }
        }
        return true;
    }
};

2023年2月16日 星期四

198. House Robber

解題思路

是要 rob 當下這間以及上上間能 rob 的總和,還是不 rob 這間而取上間 rob 的總和?

程式碼

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size() == 1) return nums[0];
        if(nums.size() == 2) return max(nums[0], nums[1]);
        vector<int> money(nums.size(), 0);
        money[0] = nums[0], money[1] = max(nums[0], nums[1]);

        for(int i=2; i<nums.size(); i++)
            money[i] = max(money[i-1], nums[i] + money[i-2]);
        return money[nums.size() - 1];
    }
};

2023年2月15日 星期三

739. Daily Temperatures

解題思路

用 stack 紀錄還沒找到 warmer 的日子。用 pair 同時保有日期跟溫度。

pair 用法:

pair<type, type> p;

p.first = ???, p.second = ???

make_pair(???, ???);

程式碼

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> ans(temperatures.size(), 0);
        stack<pair<int, int>> st; // stack for pair(temp, index)

        for(int i=0; i<temperatures.size(); i++)
        {
            while(!st.empty() && st.top().first < temperatures[i])
            {
                ans[st.top().second] = i - st.top().second;
                st.pop();
            }
            st.push(make_pair(temperatures[i], i));
        }
        return ans;
    }
};

230. Kth Smallest Element in a BST

解題思路

拿數字 k 來檢查現在用 inorder 走訪過幾個 node,每次走訪都把 k 減 1。

當 k 為 0,表示這個 node 就是我們要的。存在 ans 裡面。

程式碼

class Solution {
public:
    int ans = 0;

    void helper(TreeNode* root, int& k)
    {
        if(root == nullptr)
            return;
        
        helper(root->left, k);
        k--;
        if(k == 0) ans = root->val;
        helper(root->right, k);
    }
    int kthSmallest(TreeNode* root, int k) {
        helper(root, k);
        return this->ans;
    }
};

2023年2月14日 星期二

146. LRU Cache

解題思路

看 neetcode 的影片,用他的解法來解。

改天自己重新思考重寫一次。

程式碼

class Node {
public:
    int key, value;
    Node *prev, *next;
    Node(int key, int value) {
        this->key = key;
        this->value = value;
        this->prev = this->next = nullptr;
    }
};

class LRUCache {
public:
    int cap;
    unordered_map<int, Node*> cache; // key to node pointer
    Node *left, *right; // least recent, most recent

    LRUCache(int capacity) {
        this->cap = capacity;
        this->left = new Node(0, 0);
        this->right = new Node(0, 0);
        this->left->next = this->right;
        this->right->prev = this->left;
    }

    void remove(Node* node) { // remove node from double linked-list
        Node *pre = node->prev, *nxt = node->next;
        pre->next = nxt;
        nxt->prev = pre;
    }

    void insert(Node* node) { // insert node into double linked-list
        Node *pre = this->right->prev, *nxt = this->right;
        pre->next = nxt->prev = node;
        node->prev = pre;
        node->next = nxt;
    }
    
    int get(int key) {
        if(cache.count(key)) { // first update the node to the right-most
            remove(cache[key]);
            insert(cache[key]);
            return cache[key]->value;
        }
        return -1;
    }
    
    void put(int key, int value) {
        if(cache.count(key))
        {
            remove(cache[key]);
        }
        cache[key] = new Node(key, value); // update hashmap
        insert(cache[key]); // update linked-list

        if(cache.size() > this->cap)
        {
            Node* LRU = this->left->next;
            remove(LRU); // remove the LRU 
            cache.erase(LRU->key);
        }
    }
};

2023年2月13日 星期一

621. Task Scheduler

解題思路

用公式計算。

程式碼

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        if(n == 0) return tasks.size();
        int arr[26] = {0}, maxTask = 0, maxTaskCount = 0;
        for(int i=0; i<tasks.size(); i++)
        {
            arr[tasks[i] - 'A']++;
            maxTask = max(maxTask, arr[tasks[i] - 'A']);
        }
        for(int i=0; i<26; i++)
        {
            if(arr[i] == maxTask)
                maxTaskCount++;
        }
        int ans = (n+1) * (maxTask-1) + maxTaskCount;
        return max((int)tasks.size(), ans);
    }
};

2023年2月12日 星期日

310. Minimum Height Trees

解題思路

照著網路上其他人「一層層剝開 leaf node」的思維去寫。

有空再寫一次。

程式碼

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if(n == 1) return vector<int>(1, 0);
        vector<set<int>> graph(n);
        for(int i=0; i<edges.size(); i++)
        {
            graph[edges[i][0]].insert(edges[i][1]);
            graph[edges[i][1]].insert(edges[i][0]);
        }
        vector<int> leafNode, nextLeafNode;
        for(int i=0; i<n; i++)
        {
            if(graph[i].size() == 1)
                leafNode.push_back(i);
        }

        while(!leafNode.empty())
        {
            for(auto node : leafNode)
            {
                for(auto connect : graph[node])
                {
                    graph[connect].erase(node);
                    if(graph[connect].size() == 1)
                        nextLeafNode.push_back(connect);
                }
            }
            if(nextLeafNode.empty()) break;
            swap(leafNode, nextLeafNode);
            nextLeafNode.clear();
        }
        
        return leafNode;

    }
};

438. Find All Anagrams in a String

解題思路

兩個 index 分別記錄出現次數,每次比對一不一樣。

滑動 window 的時候不用重新計算,而是以「拔掉 left」與「加上 right」的方式節省時間。

程式碼

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ans;
        int sArr[26] = {0}, pArr[26] = {0}, left = 0;
        if(p.size() > s.size()) return ans;

        for(int i=0; i<p.size(); i++)
        {
            pArr[p[i] - 'a']++;
            sArr[s[i] - 'a']++;
        }
        while(left <= s.size() - p.size())
        {
            bool isSame = true;
            for(int i=0; i<26; i++)
            {
                if(sArr[i] != pArr[i])
                    isSame = false;
            }
            if(isSame) ans.push_back(left);

            if(left == s.size() - p.size()) break;
            sArr[s[left] - 'a']--; sArr[s[left+p.size()] - 'a']++;
            left++;
        }
        return ans;
    }
};

2023年2月11日 星期六

79. Word Search

解題思路

base case 是 word 只剩一個字而且是要找的字。以及錯誤判斷寫對。

isVisited 要先標記走過,接著遞迴下去找,最後記得改回來。

程式碼

class Solution {
public:
    bool search(vector<vector<char>>& board, string word, vector<vector<bool>>& isVisited, int x, int y)
    {
        if(x < 0 || y < 0 || x >= board.size() || y >= board[0].size()) return false;
        if(isVisited[x][y] || word[0] != board[x][y]) return false;
        if(word.size() == 1 && word[0] == board[x][y]) return true;

        isVisited[x][y] = true;
        
        bool isFind = search(board, word.substr(1), isVisited, x-1, y) || search(board, word.substr(1), isVisited, x+1, y) || search(board, word.substr(1), isVisited, x, y-1) || search(board, word.substr(1), isVisited, x, y+1);

        isVisited[x][y] = false;
        return isFind;
    }
    bool exist(vector<vector<char>>& board, string word) {
        vector<vector<bool>> isVisited(board.size(), vector<bool>(board[0].size(), false));
        
        for(int i=0; i<board.size(); i++)
        {
            for(int j=0; j<board[0].size(); j++)
            {
                if(search(board, word, isVisited, i, j))
                    return true;
            }
        }
        return false;
    }
};

2023年2月10日 星期五

17. Letter Combinations of a Phone Number

解題思路

對照的部分用 string array 紀錄,同時以 auto 方式遍歷會比較方便。

程式碼

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        string mapping[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        queue<string> q;
        vector<string> ans;
        if(digits == "")
            return ans;

        q.push("");
        for(int i=0; i<digits.size(); i++)
        {
            int n = q.size();
            while(n--)
            {
                string temp = q.front();
                q.pop();
                for(auto c : mapping[digits[i] - '0'])
                    q.push(temp + c);
            }
        }

        while(!q.empty())
        {
            ans.push_back(q.front());
            q.pop();
        }
        return ans;
    }
};

11. Container With Most Water

解題思路

哪兩條直線能圍出最大面積?用 two pointer 分別指向兩端,慢慢往內縮求極值。

程式碼

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int maxA = 0, curA;
        while(left < right)
        {
            curA = min(height[left], height[right]) * (right - left);
            maxA = max(maxA, curA);
            if(height[left] < height[right])
                left++;
            else
                right--;            
        }
        return maxA;
    }
};

2023年2月9日 星期四

105. Construct Binary Tree from Preorder and Inorder Traversal

解題思路

藉由 inorder 與 preorder 還原出原本的 binary tree 是資料結構中的內容,因此照著演算法模擬即可。

不過好像在時間複雜度上還有可進步的空間XD

程式碼

class Solution {
public:
    TreeNode* append(TreeNode* root, int value, unordered_map<int, int>& mp)
    {
        if(root == nullptr)
            root = new TreeNode(value);
        else if(mp[root->val] < mp[value])
            root->right = append(root->right, value, mp);
        else
            root->left = append(root->left, value, mp);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        unordered_map<int, int> mp;
        for(int i=0; i<inorder.size(); i++)
            mp[inorder[i]] = i;
        
        TreeNode* root = nullptr;
        for(int i=0; i<preorder.size(); i++)
            root = append(root, preorder[i], mp);
        return root;
    }
};

62. Unique Paths

解題思路

直覺想到高中數學的排列組合。套公式為 C(m+n-2, m-1),也就是 (m+n-2)! / (m-1)!(n-1)!。

寫成程式的話,必須進一步化簡計算量,模擬分母 (m+n-2)! 跟 (m-1)!, (n-1)! 中較大的數字約分,以及乘上(m-1)!, (n-1)! 中較小的數字。

可以進一步一邊乘 (top-i) 又一邊除 (i+1) 而不會說數字無法整除而有錯,背後的想法是連續整數在同樣乘或除第N個數的時候,因為連續的特性所以就能除盡。

也可以用 DP,下次試看看。

程式碼

class Solution {
public:
    int uniquePaths(int m, int n) {
        int top = m + n - 2;
        int down = min(m, n) - 1;

        long long int ans = 1;
        for(int i=0; i<down; i++)
        {
            ans = ans * (top - i) / (i + 1);
        }
        return ans;
    }
};

2023年2月7日 星期二

5. Longest Palindromic Substring

解題思路

根據 neetcode 的直覺解法解題。以「自己」為中心,左右尋找最佳可能解,分成偶數奇數長度兩種來判斷。

程式碼

class Solution {
public:
    string longestPalindrome(string s) {
        int maxLen = 0, left, right;
        string maxP = "";

        for(int i=0; i<s.size(); i++)
        {
            // odd
            left = i, right = i;
            while(left >=0 && right < s.size() && s[left] == s[right])
            {
                if((right - left + 1) > maxLen)
                {
                    maxLen = right - left + 1;
                    maxP = s.substr(left, right - left + 1);
                }
                left--;
                right++;
            }

            // even
            left = i, right = i+1;
            while(left >=0 && right < s.size() && s[left] == s[right])
            {
                if((right - left + 1) > maxLen)
                {
                    maxLen = right - left + 1;
                    maxP = s.substr(left, right - left + 1);
                }
                left--;
                right++;
            }
        }
        return maxP;
    }
};

199. Binary Tree Right Side View

解題思路

一次檢查一個 level,每次都先把最右邊的紀錄下來,其他的把左右子節點放進 queue。

程式碼

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;
        if(!root) return ans;

        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty())
        {
            ans.push_back(q.back()->val);
            int size = q.size();
            for(int i=0; i<size; i++)
            {
                if(q.front()->left) q.push(q.front()->left);
                if(q.front()->right) q.push(q.front()->right);
                q.pop();
            }
        }
        return ans;
    }
};

2023年2月6日 星期一

78. Subsets

解題思路

找出所有可能的子集。

方法就是用 for 看過從「開頭」以後的每個位置,每次都是「選」或者「不選」兩種可能。

程式碼

class Solution {
public:
    void helper(vector<int>& nums, int start, vector<vector<int>>& ans, vector<int> v)
    {
        ans.push_back(v);
        for(int i=start; i<nums.size(); i++)
        {
            v.push_back(nums[i]);
            helper(nums, i+1, ans, v);
            v.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> v;
        helper(nums, 0, ans, v);
        return ans;
    }
};

54. Spiral Matrix

解題思路

模擬好難......

程式碼

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ans;
        int up = 0, down = matrix.size() - 1, left = 0, right = matrix[0].size() - 1;

        while(true)
        {
            for(int i=left; i<=right; i++) ans.push_back(matrix[up][i]);
            up++; if(up > down || left > right) break;
            for(int i=up; i<=down; i++) ans.push_back(matrix[i][right]);
            right--; if(up > down || left > right) break;
            for(int i=right; i>=left; i--) ans.push_back(matrix[down][i]);
            down--; if(up > down || left > right) break;
            for(int i=down; i>=up; i--) ans.push_back(matrix[i][left]);
            left++; if(up > down || left > right) break;
        }
        return ans;
    }
};

2023年2月4日 星期六

8. String to Integer (atoi)

解題心得

很多 edge case 需要考慮的一題。

程式碼

class Solution {
public:
    int myAtoi(string s) {
        long double ans = 0;
        int i=0;
        bool isPositive = true;
        while(s[i] == ' ')
            i++; // ignore the leading whitespace
        if(s[i] == '-')
        {
            isPositive = false;
            i++;
        }
        else if(s[i] == '+')
        {
            isPositive = true;
            i++;
        }

        for(; i<s.size(); i++)
        {
            if(s[i] > '9' || s[i] < '0')
                break;
            ans = ans * 10 + s[i] - '0';
        }

        if(!isPositive) ans *= -1;
        if(ans > INT_MAX) return INT_MAX;
        else if(ans < INT_MIN) return INT_MIN;
        return ans;
    }
};

2023年2月3日 星期五

416. Partition Equal Subset Sum

解題思路

1. 如果 array 的總和是奇數,那麼不用想了,一定找不到能分兩半的組合

2. 接下來,題目被簡化成找 target = sum / 2 在 array 中是否有該組合

原本想用 set 做,traverse array[i] 的時候把新的可能加進去,但沒想到效率很慢。

改用 bool vector 來記錄 sum = i 的組合是否能找到。

程式碼

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(int i=0; i<nums.size(); i++)
            sum += nums[i];
        
        if(sum % 2 == 1) return false;

        int target = sum / 2;
        vector<bool> dp(target + 1, false);
        dp[0] = true;
        for(int i=0; i<nums.size(); i++)
        {
            for(int j=target; j>=nums[i]; j--)
                dp[j] = dp[j] || dp[j - nums[i]];
        }
        return dp[target];
    }
};

2023年2月2日 星期四

139. Word Break

解題思路

零錢問題的字串版(?)

要用 hashMap 來存已經看過的節省時間,不然就 TLE。

程式碼

class Solution {
public:
    unordered_map<string, bool> mp;
    bool helper(string s, vector<string>& wordDict)
    {
        if(mp.count(s))
            return mp[s];
        if(s == "")
            return true;
        for(int i=0; i<wordDict.size(); i++)
        {
            if(s.rfind(wordDict[i], 0) == 0)
            {
                if(helper(s.substr(wordDict[i].size()), wordDict))
                {
                    mp[s] = true;
                    return true;
                }
            }
        }
        mp[s] = false;
        return false;
    }
    bool wordBreak(string s, vector<string>& wordDict) {
        return helper(s, wordDict);
    }
};

75. Sort Colors

解題思路

不能用寫好的 sort 函式,而且要 in-place。提示裡面說紀錄 0 跟 1 的數量,所以就照這個做法。

程式碼

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int count0 = 0, count1 = 0;
        for(int i=0; i<nums.size(); i++)
        {
            if(nums[i] == 0)
                count0++;
            else if(nums[i] == 1)
                count1++;
        }
        for(int i=0; i<count0; i++)
            nums[i] = 0;
        for(int i=count0; i<count0+count1; i++)
            nums[i] = 1;
        for(int i=count0+count1; i<nums.size(); i++)
            nums[i] = 2;
    }
};

2023年2月1日 星期三

721. Accounts Merge

解題思路

這類「誰跟誰是一個小群體」的題目跟 union find 有關,這題額外加上還有 "name" 這一個標示群體名稱的字串。

解題分為四步,

step1: 初始化,每一個 email 的老大(parent)都是自己,並且記錄 email 的擁有者叫甚麼名字。

step2: 透過 find function,把每串除了第一個(本來就指向自己)的其餘的老大都指向第一個。在這個過程中,如果兩串都有同一個 email 出現,那自然會被歸在同一個群體之中(因為老大都一樣)。

step3: 先前只是記錄 email 跟對應的老大是誰。在 step3 要轉成 map 結構,一個老大 string 所屬的擁有者名字會對應到 set of other strings in the same group。做法是 traverse 每一個 email,map[老大].insert(自己)

step4:  依題目要求把 email 們先 sort,接著把名字加入即可。


這題好難,改天再寫一次。

程式碼

class Solution {
public:
    string find(string email, unordered_map<string, string>& parent)
    {
        if(email != parent[email])
            parent[email] = find(parent[email], parent); // compress
        return parent[email];
    }
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        unordered_map<string, string> owner; // email's owner(email -> name)
        unordered_map<string, string> parent; // email's parent for union
        unordered_map<string, set<string>> unions; // answer

        // Step 1
        for (auto account : accounts) {
            for (int i = 1; i < account.size(); i++) {
                owner[account[i]] = account[0];
                parent[account[i]] = account[i];
            }
        }
        
        // Step 2
        for (auto account : accounts) {
            string p = find(account[1], parent);
            for (int i = 2; i < account.size(); i++) {
                parent[find(account[i], parent)] = p;
            }
        }
        
        // Step 3
        for (auto email : owner) {
            unions[find(email.first, parent)].insert(email.first);
        }
        
        // Step 4
        vector<vector<string>> result;
        for (auto union_ : unions) {
            vector<string> emails(union_.second.begin(), union_.second.end());
            emails.insert(emails.begin(), owner[union_.first]);
            result.push_back(emails);
        }
        return result;

    }
};

2023年1月31日 星期二

981. Time Based Key-Value Store

解題思路

這題必須用到 map,然後因為還有 timestamp,要在時限內的話要用到 binary search。

從這題中學到:

1. unordered_map 可以用來加速、提升效率

2. upper_bound 可以用來找到第一個大於給定數值的

3. auto iterator 可以用 -- 移到上一個

程式碼

class TimeMap {
public:
    unordered_map<string, map<int, string>> mp;

    TimeMap() {
    }
    
    void set(string key, string value, int timestamp) {
        mp[key][timestamp] = value;
    }
    
    string get(string key, int timestamp) {
        if(!mp.count(key)) return "";
        auto it = mp[key].upper_bound(timestamp);
        if(it == mp[key].begin()) return "";
        return (--it)->second;
    }
};

2023年1月30日 星期一

236. Lowest Common Ancestor of a Binary Tree

解題思路

會有兩種情況: p, q 屬於同一個 subtree 或不是。如果不是,那麼回傳的就會是他們的再往上的 root,不然就是 p 跟 q 自己。

判斷方法就是一直往下看左右子樹有沒有 p 跟 q,如果有的話就回傳那個 node,如果沒有就是回傳 root。

程式碼

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == nullptr || root == p || root == q)
            return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

        if(left != nullptr && right != nullptr)
            return root;
        else if(left != nullptr)
            return left;
        else
            return right;
    }
};

56. Merge Intervals

解題思路

先把 interval 給 sort 過一次,確保數字至少是遞增上去的。

接下來 traverse 每一個 element,因為新 element 只可能跟上一個 overlap,或乾脆就在上一個右邊,因此依照情況決定是要 merge 還是 push_back 就好。

比 57. Insert Interval 簡單很多。

程式碼

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> ans;

        ans.push_back(intervals[0]);
        for(int i=1; i<intervals.size(); i++)
        {
            if(ans.back()[1] >= intervals[i][0]) // merge
            {
                ans.back()[0] = min(ans.back()[0], intervals[i][0]);
                ans.back()[1] = max(ans.back()[1], intervals[i][1]);
            }
            else
                ans.push_back(intervals[i]);
        }
        return ans;
    }
};

2023年1月29日 星期日

46. Permutations

解題思路

排列組合經典題。

想像每一次都從現有的 nums 拿一個走,接著繼續再從剩的在選一個,重複這個動作直到所有的都被選過為止。

程式碼

class Solution {
public:
    void helper(vector<int>& nums, vector<vector<int>>& ans, vector<int> comb, vector<bool> isUsed)
    {
        if(comb.size() == nums.size())
        {
            ans.push_back(comb);
            return;
        }
        for(int i=0; i<nums.size(); i++)
        {
            if(isUsed[i]) continue;
            comb.push_back(nums[i]);
            isUsed[i] = true;
            helper(nums, ans, comb, isUsed);
            comb.pop_back();
            isUsed[i] = false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> comb;
        vector<bool> isUsed(nums.size(), false);
        helper(nums, ans, comb, isUsed);
        return ans;
    }
};

39. Combination Sum

解題思路

也是經典的題型。

如果要確保 combination 是唯一的,用 start 標記起始點可以避免重複拿取 element,以至於產生相同的組合。

程式碼

class Solution {
public:
    void helper(vector<int>& candidates, vector<vector<int>>& ans, vector<int> result, int target, int start)
    {
        if(target == 0)
            ans.push_back(result);
        if(target < 0)
            return ;

        for(int i=start; i<candidates.size(); i++)
        {
            vector<int> result_new = result;
            result_new.push_back(candidates[i]);
            helper(candidates, ans, result_new, target - candidates[i], i);
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        vector<int> result;
        helper(candidates, ans, result, target, 0);
        return ans;
    }
};

2023年1月28日 星期六

33. Search in Rotated Sorted Array

解題思路

分三個部分:

1. 藉由 binary search 的方式找到 pivot。

2. 由 pivot 可推知 target 在其左邊還右邊,更新 left 與 right

3. 拿更新後的 left 與 right 再做一次 binary search 找 target。


pivot 是指 sorted array 經過旋轉後產生的不連續遞增斷點的右側,ex: [4,5,6,7,0,1,2] 中的 0。


一直卡在 pivot 求法,最後求助於 chatGPT 生出答案,改天再寫一次。

程式碼

class Solution {
public:
    int findPivot(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) left = mid + 1;
            else right = mid;
        }
        return left;
    }
    int search(vector<int>& nums, int target) {
        if (nums.empty()) return -1;
        int pivot = findPivot(nums);
        int left, right;
        if (target >= nums[pivot] && target <= nums[nums.size() - 1]) {
            left = pivot;
            right = nums.size() - 1;
        } else {
            left = 0;
            right = pivot - 1;
        }
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }
};

2023年1月27日 星期五

994. Rotting Oranges

解題思路

看出來是 BFS 後,就很好解了。

程式碼

struct P {
    int x;
    int y;
};
class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        queue<P> q1, q2;
        int minute = 0, dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
        for(int i=0; i<grid.size(); i++)
        {
            for(int j=0; j<grid[i].size(); j++)
            {
                if(grid[i][j] == 2)
                    q1.push({i, j});
            }
        }
        while(true)
        {
            while(!q1.empty())
            {
                for(int i=0; i<4; i++)
                {
                    int newX = q1.front().x+dx[i], newY = q1.front().y+dy[i];
                    if(0 <= newX && newX < grid.size() && 0 <= newY && newY < grid[0].size() && grid[newX][newY] == 1)
                    {
                        q2.push({newX, newY});            
                        grid[newX][newY] = 2;
                    }
                }
                q1.pop();
            }
            minute += 1;
            if(q2.empty()) break;
            swap(q1, q2);
        }
        for(int i=0; i<grid.size(); i++)
            for(int j=0; j<grid[i].size(); j++)
                if(grid[i][j] == 1)
                    return -1;

        return minute - 1;
    }
};

2023年1月26日 星期四

238. Product of Array Except Self

解題思路

分別算出從前與從後算到該 index 的乘積,最後再相乘到 output 。

程式碼

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int prefix[100001] = {0}, suffix[100001] = {0};
        int pre = 1;
        for(int i=0; i<nums.size(); i++)
        {
            prefix[i] = pre * nums[i];
            pre = prefix[i];
        }
        int suf = 1;
        for(int i=nums.size() - 1; i>=0; i--)
        {
            suffix[i] = suf * nums[i];
            suf = suffix[i];
        }
        vector<int> ans;
        for(int i=0; i<nums.size(); i++)
        {
            if(i == 0)
                ans.push_back(suffix[i+1]);
            else if(i == nums.size()-1)
                ans.push_back(prefix[i-1]);
            else
                ans.push_back(prefix[i-1] * suffix[i+1]);
        }
        return ans;
    }
};

208. Implement Trie (Prefix Tree)

解題思路

先自定義 node,用 pointer 的方式連接。檢查 node 是否已經是字的結尾,就用 bool 來記錄。

程式碼

class Node{
public:
    bool isEnd;
    Node* child[26];
    Node()
    {
        isEnd = false;
        for(int i=0; i<26; i++)
            child[i] = nullptr;
    }
};
class Trie {
public:
    Node* root = new Node();

    Trie() {
    }
    
    void insert(string word) {
        Node* current = root;
        for(int i=0; i<word.size(); i++)
        {
            if(current->child[word[i] - 'a'] == nullptr)
                current->child[word[i] - 'a'] = new Node();
            current = current->child[word[i] - 'a'];
        }
        current->isEnd = true;
    }
    
    bool search(string word) {
        Node* current = root;
        for(int i=0; i<word.size(); i++)
        {
            if(current->child[word[i] - 'a'] == nullptr)
                return false;
            current = current->child[word[i] - 'a'];
        }
        return current->isEnd == true;
    }
    
    bool startsWith(string prefix) {
        Node* current = root;
        for(int i=0; i<prefix.size(); i++)
        {
            if(current->child[prefix[i] - 'a'] == nullptr)
                return false;
            current = current->child[prefix[i] - 'a'];
        }
        return true;
    }
};

2023年1月25日 星期三

207. Course Schedule

解題思路

感覺只是把 neetcode 的解法寫成 C++ 版本而已,改天要再練習一次。

程式碼

class Solution {
public:
    map<int, set<int>> preMap;
    set<int> checkCycle;
    bool dfs(int currentCourse)
    {
        if(checkCycle.find(currentCourse) != checkCycle.end()) // alreadly visited
            return false;
        if(preMap[currentCourse].empty()) // no prerequisites or are all valid
            return true;
        
        checkCycle.insert(currentCourse);
        for(auto c : preMap[currentCourse])
        {
            if(!dfs(c))
                return false;
        }
        checkCycle.erase(currentCourse);
        preMap[currentCourse].clear();
        return true;
    }
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        for(int i=0; i<prerequisites.size(); i++)
            preMap[prerequisites[i][0]].insert(prerequisites[i][1]);
        
        for(int i=0; i<numCourses; i++)
        {
            if(!dfs(i))
                return false;
        }
        return true;
    }
};

2023年1月24日 星期二

150. Evaluate Reverse Polish Notation

解題心得

很經典的 stack 題目

程式碼

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(int i=0; i<tokens.size(); i++)
        {
            if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/")
            {
                int second = st.top(); st.pop();
                int first = st.top(); st.pop();
                if(tokens[i] == "+") st.push(first + second);
                else if(tokens[i] == "-") st.push(first - second);
                else if(tokens[i] == "*") st.push(first * second);
                else if(tokens[i] == "/") st.push(first / second);
            }
            else
            {
                st.push(stoi(tokens[i]));
            }
        }
        return st.top();
    }
};

133. Clone Graph

解題思路

用 map 紀錄走訪過該 node 與否,並用 DFS 看過整張圖。

程式碼

class Solution {
public:
    map<Node*, Node*> oldToNew;
    Node* dfs(Node* node)
    {
        if(oldToNew.count(node))
            return oldToNew[node];

        Node* clone = new Node(node->val);
        oldToNew[node] = clone;
        for(int i=0; i<node->neighbors.size(); i++)
        {
            clone->neighbors.push_back(dfs(node->neighbors[i]));
        }
        return clone;
    }
    Node* cloneGraph(Node* node) {
        if(node == nullptr)
            return nullptr;

        return dfs(node);
    }
};

2023年1月23日 星期一

200. Number of Islands

解題思路

每當找到一個沒看過的島,就四方探索整個範圍並且把該位置抹掉。

程式碼

class Solution {
public:
    void bfs(vector<vector<char>>& grid, int x, int y)
    {
        int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, 1, -1, 0};
        if(0 <= x && x < grid.size() && 0 <= y && y < grid[0].size() && grid[x][y] == '1')
        {
            grid[x][y] = '0';
            for(int i=0; i<4; i++)
                bfs(grid, x+dx[i], y+dy[i]);
        }
    }
    int numIslands(vector<vector<char>>& grid) {
        int num = 0;

        for(int i=0; i<grid.size(); i++)
        {
            for(int j=0; j<grid[0].size(); j++)
            {
                if(grid[i][j] == '1')
                {
                    num++;
                    bfs(grid, i, j);
                }
            }
        }
        return num;
    }
};

322. Coin Change

解題思路

零錢問題之找最少零錢數。

程式碼
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int index[10001] = {0};
        for(int i=1; i<10001; i++)
            index[i] = amount + 1;
        for(int i=1; i<10001; i++)
        {
            for(int j=0; j<coins.size(); j++)
            {
                if((i - coins[j]) >= 0)
                {
                    index[i] = min(index[i], 1 + index[i - coins[j]]);
                }
            }
        }
        if(index[amount] == amount + 1) return -1;
        return index[amount];
    }
};

2023年1月22日 星期日

155. Min Stack

解題思路

要 getMin,就要想方法去紀錄最小值。沒辦法只用一個變數記錄當下最小值,因為如果 pop 掉的剛好是最小值,那要如何再回溯找到上一個最小值?

所以會需要另一個 stack,用來記錄當下以這個 element 為 top 時,最小值是誰?然後每當有 push 或 pop ,要同步更新。

程式碼

class MinStack {
public:
    stack<int> st;
    stack<int> minSt; // record the min value at that point

    MinStack() {
        
    }
    
    void push(int val) {
        st.push(val);
        if(minSt.empty())
            minSt.push(val);
        else if(val < minSt.top())
            minSt.push(val);
        else
            minSt.push(minSt.top());
    }
    
    void pop() {
        st.pop();
        minSt.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return minSt.top();
    }
};

98. Validate Binary Search Tree

解題心得

如果只比 root 值還有 root 左子樹右子樹三個節點會錯。

改用傳當前區間去做比對。

程式碼

class Solution {
public:
    bool isValid(TreeNode* root, long min, long max)
    {
        if(root == nullptr)
            return true;
        if(!(min < root->val && root->val < max))
            return false;
        return isValid(root->left, min, root->val) && isValid(root->right, root->val, max);
    }
    bool isValidBST(TreeNode* root) {
        return isValid(root, LLONG_MIN, LLONG_MAX);
    }
};