Programming Skills

Remove K Digits

[題目]

https://leetcode.com/problems/remove-k-digits/

Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.

Example 1:

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

給你一個數字1432219, 允許你刪掉其中3數字，例如刪掉1432219就會變成2219，刪掉1432219就會變成1321。

請問怎麼刪會使結果最小 ? 回傳最小的那個數字

[Solution]

Make most significant digit lower.

We should do our best, use all our barging chip 'k' to make most significant digit lower.

It is better than make other digit lower.

e.g.

original number = 4999

Make 4999 --> 3999 is way better than make 4999->4000. No matter how hard you try to reduce other digits, it will never be better than reduce most significant digit.

Use a stack with N-K size to store the answer. Bottom is most sign digit. Top is less sign digit.

1.Since original size of number is N, and we can remove K digits from it. The best choice is to remove exactly K digits. It makes the answer lower.

2.Use a stack to put answer. Stack bottom represent the most sign digit. Stack top represent the less sign digit.

Decide digit[0]~digit[i] should stay or not according to digit[i+1].

New we are pushing digit into stack.

1.When push d[0] to stack, we don't know if d[0] is a good choice for most sign digit or not. But let's assume it is (we don't have choice actually, we can't just remove d[0] without more information). So we just push d[0] into stack, and wait for more info.

2.When push d[1] to stack, there is two condition :

a. d[0] <= d[1] : d[0] is lower, so d[0] is better than d[1] to be a most sign digit. Then we just simply push(d[1]).

b. d[0] > d[1] : d[1] is lower than d[0], which makes it a better choice for that slot, so we let d[1] take d[0]'s place.

We pop d[0] and push d[1], so d[1] replace d[0] and become bottom of stack, and most sign digit.

2.b is the most important step. The core concept is : "We should not allow the big number take the most sign place. So if d[i+1] is smaller(better) than d[i](which is at stack.top()), we should pop d[i] out. Furthermore, we should pop stack continuously until stack.top() is smaller or equal to d[i+1]. "

[code]

class Solution {
public:
string removeKdigits(string num, int k) {
string maxS;

//this is doing "1/2.a/2.b" steps
for (auto ch : num){
while(!maxS.empty() && maxS.back() > ch && k > 0){
maxS.pop_back();
k--;
}
maxS.push_back(ch);
}
//if still barging chip K left, then we start pop from back(the most biggest number)
while (k-->0) maxS.pop_back();

//this is just to remove the 0 on the stack.bottom
bool foundFirstNonZero=false;
string ans;
for (auto ch : maxS){
if(ch!='0') foundFirstNonZero=true;
if(foundFirstNonZero){
ans +=ch;
}
}
return ans.empty() ? "0" : ans;
}
};

Next Greater Element 1

[題目]

https://leetcode.com/problems/next-greater-element-i/

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.

You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.

For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.

Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

給一串數列num1，求其中的每個元素在num2中的"下一個大於我的值"

例如, num1[1]是1，所以num2中的1，在num2中的下一個大於1的值是nums[2]=4

[Solution]

Steps :
1. Find "Next greater element" for all element in nums2.
2. Use a hash map to record <value, next greater element value>

3. For each element in num1, check it's 'next greater element value' by look up hash map.

And the most difficult and important is step 1.

Push element from "right to left" to min top monotonic stack

Then NGE will be in the min top mono stack

1. push element in nums2 from RIGHT to LEFT (<---) into mono Stack

2. decrease Monotonic stack operation :

Before pushing new element 'e' into Stack, pop out all the element smaller the 'e'.

Pop them because of below reasons :
A.Pop them is safe, because they are smaller than 'e', so useless for 'e' and all elements on the left of 'e'.

B.If we don't pop, they will become redundant elements, and delay us to find closest and greater element on right side.

After popping, the top() will be the next greater element of 'e'.

Take '4' as example : we have monoStack (2] and wanna find next greater element for '4'.

As explained below, '2' is useless for '4' and element on left of '4'.

So pop out '2' is safe. We don't need it in the future.

Pop smaller elements is necessary because if we don't, we will have to check all of useless element when finding NGE.

If we pop, we will need just to check few possible element.

For example, the nums2=[1,3,4,2]

check 2's NGE : none, and monoS became (2]

check 4's NGE : none, and monoS became (4]
check 3's NGE : we got '4', and monoS became (3,4]

check 1's NGE : we got '3', and monoS became (1,3,4]

[Code]

class Solution {

public:

vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {

vector<int> ans;

stack<int> stk;

unordered_map<int,int> ht;//num, the next greater num

for(auto i:nums){

while(!stk.empty() && stk.top() < i){

ht[stk.top()]=i;//record the "next greater" on hashtable

stk.pop();

}

stk.push(i);

}

for(auto i:findNums){

if(ht.find(i)==ht.end()) ans.push_back(-1);

else ans.push_back(ht[i]);

}

return ans;

}

};

點亮LED

今天要用arduino點亮外部LED
有參考到網路上前輩的文章
http://drho.club/2017/12/arduino-unit-2/

[組裝]
[基本觀念]
想點亮一個LED, 當然就要給他供電
所以取出一個LED component
然後把一腳接GND, 另一腳接正電壓就會亮了
然後分別討論這幾個元素要從哪來

[1.電]
Arduino的pin可以提供5V的正電壓
只要用選一個pin(例如pin 10)
然後用函式
pinMode(12, OUTPUT); //定义数字接口11 为输出
digitalWrite(12,HIGH);//輸出5v電壓
即可

[2.GND]
板子上有一個pin是"GND"

[3.電阻]
我們還需要一個限流電阻，原因是Arduino的輸出電壓是5V大於LED的工作電壓，限流電阻可以讓在LED上工作的電壓降低，可以避免LED被過大的電流燒毀。(電阻值大小有一定的計算公式，每一種LED需要的電阻值不一定相同。一般來說，只要大於220歐姆即可運作，如果使用的電阻值過大，頂多就是亮度較低或是不會亮而已)

[程式]


void setup()
{
  pinMode(10, OUTPUT);
  digitalWrite(10, HIGH);
}
void loop()
{

}

First Time Arduino

這個已經紅了好多年的嵌入式小板
雖然耳聞多年但一直沒有玩過
今天就來好好地把玩一下

[設備]
[arduino uno 3]

[usb type A to type B]

[流程]
真的是超級簡單
1.到官網下載arduino IDE
https://www.arduino.cc/en/Main/Software

像我是win10上作業, 就點選
"Windows app"
然後全部無腦安裝, 甚麼都不用選

2.連接電腦
把arduino用usb線連接到電腦上
(由於出廠時有預先燒錄program進去了
所以你會看到一個綠燈恆亮, 黃燈閃爍這是正常的)

3.打開IDE
Tool-->serial port-->選com8(理論上只有一個可以選, 我的是com8, 你是別的也無所謂)
好了到這步已經可以開始寫code了

[測試一下]
測試也是超級簡單
IDE有內建許多測試程式讓你直接使用, 都不用自己寫

1.程式碼
File-->Example-->Basic-->blink
選完後你會發現他開啟一個視窗, 把內建的程式碼打開了
這是一個讓黃色LED閃爍的程式

2.編譯與上傳
IDE左上角有一個"向右的箭頭", 滑鼠移上去會寫"upload"("上傳")
按下去後會進行編譯-->上傳
上傳完畢tx和rx兩個LED會快速閃一兩秒
然後arduino就會開始程式了
你會看到黃色LED一直閃爍(只要你電還插著就一直閃)

Abstract Factory

[Purpose]

基本上就是factory兩方面進化

1.有很多種factory(例如audi, BMW)

2.一個factory可以生產多種東西, 但是彼此關聯的(例如car, wheel)
所以factory的public API會有多個
car* createCar()
wheel* createWheel()

但car和wheel是有緊密的, 例如audi專用輪胎, 配audi car

好處是 :

1.user不能知道car的全部的member method/variable (因為interface能隱藏實作細節,甚至隱藏類別的存在)

2.user可以用同一種pointer type指向各種car, car再多也不用改code (因為interface能提供多型)

3.factory把車子的創建集中在一個function內, 就不怕外界用錯誤的方法創建car.
4.不同廠牌的車子用不同的xxxFactory創建, (close for modification)

5.你想要創品牌只要建立新的xxxFactory和xxxCar和xxxWhel class就好 (open for extension)

6.建立新的xxxCar並不影響其他car或user內的code (close for modification)

[Implementation]

Factory Pattern

[Purpose]

一款賽車遊戲, 玩家可以換開很多車

而每款車外觀參數解鎖條件都不相同

但使用方法都一樣(加速/減速)

那麼就可以

把一樣的抽取出來 : 寫一個interface "Car", 支援所有車子該有的操作

把不同的隱藏起來 : 寫一個"factory" class或method, 你給他型號, 他給你車子的指標

好處是 :

1.user不能知道car的全部的member method/variable (因為interface能隱藏實作細節,甚至隱藏類別的存在)

2.user可以用同一種pointer type指向各種car, car再多也不用改code (因為interface能提供多型)

3.factory把車子的創建集中在一個function內, 就不怕外界用錯誤的方法創建car.

4.你想要創新的car只要建立新的xxxCar class就好 (open for extension)

4.建立新的xxxCar並不影響其他car或user內的code (close for modification)

[Implementation]

Strategy Pattern

[Purpose]

有時候你的class有某個行為, 但在不同的場景中, 該行為有不同的實現方式。

例如你的遊戲角色, 有"移動"這樣的行為,

在學校中的移動只能慢走

在草原的移動只能跑

在海中的移動只能游

你想角色, 在不同場景, 擁有不同的移動方式

這時候就適合用Strategy Pattern

你的主體context, 擁有一個strategy指標, 可以動態指向不同的strategy實體

用strategy Pattern的好處是 :

1.你可以assign不同的Strategy給context

2.多個context, 每個人都可以擁有自己獨特的Strategy

3.你想要創新的strategy只要建立新的Concrete strategy就好 (open for extension)

4.建立新的Concrete strategy並不影響其他class內的code (close for modification)

[Implementation]




#include <iostream>
using namespace std;

class Strategy{ //interface
public:
 virtual void execute() = 0;  
};

class ConcreteStrategy1 : public Strategy{
public:
 void execute(){
  cout << "run Strategy 1" << endl;
 }
};

class ConcreteStrategy2 : public Strategy{
public:
 void execute(){
  cout << "run Strategy 2" << endl;
 }
};


class Context{
private:
  Strategy* mystg;
public:
 Context(Strategy* stg) : mystg(stg){}
 void setstg(Strategy* stg){
  delete mystg;
  mystg = stg;
 }
 void runstg(){
  mystg->execute();
 }
};


int main(int argc, char** argv) {
 Context c1(new ConcreteStrategy2());
 c1.runstg();
 c1.setstg(new ConcreteStrategy1());
 c1.runstg();
 
 return 0;
}

輸出:

run Strategy 2

run Strategy 1

template pattern

[Purpose]

有些時候你要執行的任務 :

有幾個固定的步驟順序, 但是每個步驟執行方式是有很多選擇

比如說你開一間餐廳

服務生接待客人有固定的步驟順序,

1.說些問候語 (您好, 歡迎光臨本店, 請問有幾位消費, ...)

2.遞上菜單

但是有時候會客人是外國人

那麼問候語和菜單也要改用英語

這個例子中, 就是兩個固定的步驟，但有兩種不同的執行的方式

用Template Pattern的好處是 :

1.固定的步驟, code寫一份就好

2.不同的執行方式需要各別寫，但能和原本的步驟自動連結上

[Implementation]


class AbstractClass{
public:
    void executeSteps(){
  step1();
  step2();
 }
    virtual void step1() = 0;
    virtual void step2() = 0;
};

class Concrete1: public AbstractClass{
public :
 void step1(){
  cout << "您好" << endl;
 }
 void step2(){
  cout << "遞上中文菜單" << endl;
 } 
}; 

class Concrete2: public AbstractClass{
public :
 void step1(){
  cout << "hello" << endl;
 }
 void step2(){
  cout << "present english menu" << endl;
 } 
};

int main(int argc, char** argv) {
 AbstractClass* chinese = new Concrete1();
 AbstractClass* english = new Concrete2();
 chinese->executeSteps();
 english->executeSteps();
 
 return 0;
}

用Template Pattern的好處是:
1.今天你想支援法語的功能, 只要多寫一個Concrete Class3即可
這滿足了Open for extension

2.今天你新增法語功能的時候, 不會動到Concrete Class1/2與Abstract Class
這滿足了Close for modification

3.今天你想顛倒步驟順序, 改為先上菜單再說歡迎, 你只要改executeSteps()
就可以同時套用到中文, 英語, 法語
不用改三次

Image overlap

[Problem]
https://leetcode.com/problems/image-overlap/

Two images 'A' and 'B' are given, represented as binary, square matrices of the same size. (A binary matrix has only 0s and 1s as values.)

We translate one image however we choose (sliding it left, right, up, or down any number of units), and place it on top of the other image. After, the overlap of this translation is the number of positions that have a 1 in both images.

(Note also that a translation does not include any kind of rotation.)

What is the largest possible overlap?

Example 1:

Input: A = [[1,1,0],
                  [0,1,0],
                  [0,1,0]]
           B = [[0,0,0],
                  [0,1,1],
                  [0,0,1]]
Output: 3
Explanation: We slide A to right by 1 unit and down by 1 unit.

Notes:
1. 1 <= A.length = A[0].length = B.length = B[0].length <= 30
2. 0 <= A[i][j], B[i][j] <= 1

中文翻譯:

給兩個正方形二維陣列A and B，裡面的值是1 or 0。

我們可以上下左右移動A，接著將A貼合到B的上面。
如果貼合時A and B同一位置中的元素都是1，就得一分。

請問所有可能的情況中(A可以上下左右移動會有很多情況)

最高得分會是多少?

舉例來說:

上例中，若將A右一格再下移一格

貼合時能得3分，是最好的情況

所以return 3

[Solution]

Step 1: For all '1' in A, find and record all the movements which we can get score from it.

Input: A = [[1,1,0],
                  [0,0,0],
                  [0,0,0]]
           B = [[0,0,0],
                  [0,1,1],
                  [0,0,1]]

For Red '1' on A(0,0).
We can score from one of these movements: (+1,+1) or (+1,+2) or (+2,+2)
For Blue '1' on A(0,1).
We can score from one of these movements: (+1,+0) or (+1,+1) or (+2,+1)

Step 2: For all movements found in step1, find the one who scores most. Return the score.

There are 5 unique movements in step1: (+1,+1) / (+1,+2) / (+2,+2) / (+1,+0) / (+2,+1)

Among them, "(+1,+1)" scores most.

(Because it makes both Red '1' and Blue '1' score)

Return the score.

Finish.

[Implement]

There are some tricks in implementation:
1.We transform "movements" to "integers":
(delta R, delta C) ---> delta R*100 + delta C
(+3,-2) --> 3*100 - 2
2.We use the interger(represent movement) as the hashkey
And use hash table unordered_map<int, score> to record score of movement.

Of course there is another way, such as using 'String' as the hashkey.
Then use hash table unordered_map<string, score> to record score of movement.


    int largestOverlap(vector<vector<int>>& A, vector<vector<int>>& B) {
        //record the coordinate of all the '1' in A
        //record the coordinate of all the '1' in B
        vector<pair<int,int>> A1;
        vector<pair<int,int>> B1;
        for(int r=0;r<A.size();r++)
            for(int c=0;c<A[0].size();c++){
                if(A[r][c]==1)  A1.push_back(pair<int,int>(r,c));
                if(B[r][c]==1)  B1.push_back(pair<int,int>(r,c));
            }
        

        //Step1: For all '1' in A, find all the movements which we can get score from it.
        unordered_map<int, int> ht;
        for(auto ca:A1){
            for(auto cb:B1){
                int hashkey=(ca.first-cb.first)*100
                    +(ca.second-cb.second);
                ht[hashkey]++;
            }
        }
        
        //Step 2: For all movements found in step1, find the one who scores most. Return the score.
        int ans=0;
        for(auto it:ht){
            ans = max(ans,it.second);            
        }
        
        return ans;
    }

Contains Duplicate II

[Problem]
https://leetcode.com/problems/contains-duplicate-ii/

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1
Output: true

Example 3:

Input: nums = [1,2,3,1,2,3], k = 2
Output: false

[Solution]

Using STL"set" as a sliding window.

For example:
Let's say k=3, then you should use a sliding window with size 4(=k+1) to scan the input array.
If two elements in the sliding window are identical,
it means they are identical and their distance is no greater than 3.
And you should return True under that condition.
If you scan through the entire array and nothing happen, then return False.

About the implementation, using STL "set" as the sliding window is a good idea.
During "sliding",
1.Remove the left element from window(because the window is moving to the right)
2.Check if the right element is identical to any one in the window.(return True if exist.)
3.Add the right element into the window

---

class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_set<int> ht;
for (int i=0; i<nums.size();i++)
{
if(i>k) ht.erase(nums[i-k-1]);
if(ht.find(nums[i])!=ht.end()) return true;
ht.insert(nums[i]);
}
return false;
}
};

訂閱：意見 (Atom)