軟體/韌體工程師《面試重點與觀念複習》: Leetcode實戰討論

本文章目錄:
--- 面試須知與應答技巧
--- 資料結構 / 變數儲存與記憶體
--- 程式語言 / 演算法
--- 作業系統 / 多執行緒(多程序)的觀念與實作控制
--- 轉自ptt: [重要] 發文前務必閱讀：C/C++常見問題十三誡
--- 擬真試題1/擬真試題2/擬真試題3/擬真試題4
--- 直接列出考古題1(精華完整53題含解答)
--- 直接列出考古題2(精華完整35題含解答)
--- 深度討論考古題1(DEMO完整10題含解答) 選擇使用C,C++,C#或JAVA
--- 深度討論考古題2(DEMO完整11題含解答) 選擇使用C,C++,C#或JAVA
--- 撲克牌(大老二)洗牌與牌型判斷(JAVA)
--- Python基本教學
--- Leetcode實戰討論

Leetcode實戰討論

線上知名的 Leetcode網站裡面有許多演算法考題, 內容以英文方式陳述不論是外商或是台商企業都適用, 軟體也有各式程式語言, C/C++/JAVA/Python/Javascript/Ruby/Swift/Go/Scala/kotlin/Rust/PHP, 涵蓋領域很廣, 演算法可以比喻為軟體開發的內功, 而這些程式語言為外在的武功招式, 臨場要表現好要視該職缺的程式語言武功招式, 搭配強大的邏輯演算法內功才能發揮最大表現, 多練習提高自我能力為不二法門! 目前內容為976題, 分為 Easy/ Midium/ Hard, 我們再逐步加入熱門題型的演練:

Easy:

難度為容易的等級, 可以先挑easy的題目建立手感以及熟悉度!

* Same Tree:

給定兩個二叉樹，編寫一個函數來檢查它們是否相同。
如果兩個二叉樹在結構上相同並且節點具有相同的值，則認為它們是相同的。

解法:

/** 樹節點的內容定義如下:
 * Definition for a binary tree node. 
 * struct TreeNode {
 *     int val;      //數值
 *     struct TreeNode *left;  //左子節點
 *     struct TreeNode *right; //右子節點
 * };
 */
bool isSameTree(struct TreeNode* p, struct TreeNode* q) { //參數傳進來兩個欲比較之樹節點的指標
        if(p == NULL && q == NULL) //檢查空值, 若皆為空則True
            return true;
        else if(p != NULL && q != NULL) //否則, 兩者都非空的話,就必須要進行內容比較
        { 
            if(p->val == q->val  //內容相同
               && isSameTree(p->left, q->left) //而且遞迴呼叫function, 判斷左子樹是否相同 
               && isSameTree(p->right, q->right))//而且遞迴呼叫function, 判斷右子樹是否相同
            {
                return true; //以上三項都相同才能回傳true
            }
        }
        
        return false; //其他狀況,則為false
}

/** 樹節點的內容定義如下:

* Definition for a binary tree node.

* struct TreeNode {

* int val; //數值

* struct TreeNode *left; //左子節點

* struct TreeNode *right; //右子節點

* };

bool isSameTree(struct TreeNode* p, struct TreeNode* q) { //參數傳進來兩個欲比較之樹節點的指標

if(p == NULL && q == NULL) //檢查空值, 若皆為空則True

return true;

else if(p != NULL && q != NULL) //否則, 兩者都非空的話,就必須要進行內容比較

{

if(p->val == q->val //內容相同

&& isSameTree(p->left, q->left) //而且遞迴呼叫function, 判斷左子樹是否相同

&& isSameTree(p->right, q->right))//而且遞迴呼叫function, 判斷右子樹是否相同

{

return true; //以上三項都相同才能回傳true

}

return false; //其他狀況,則為false

}

* Roman to Integer:

羅馬數字由七個不同的符號表示：I，V，X，L，C，D和M.
Symbol – Value
I – 1
V – 5
X – 10
L – 50
C – 100
D – 500
M – 1000

例如，兩個用羅馬數字寫成II，只有兩個加在一起。十二寫為XII，簡稱為X + II。第二十七號寫成XXVII，即XX + V + II。　羅馬數字通常從左到右從最大到最小。但是，4這個數字不是IIII，而是為IV。因為一個在五個之前，我們減去四個。同樣的原則適用於九號，即九號。有六個使用減法的實例：

I可以放在　V（5）和　X（10）之前表達 4 和 9。
X可以放在　L（50）和　C（100）之前，以產生40和90。
C可以放在　D（500）和　M（1000）之前，以產生400和900。
給定羅馬數字，將其轉換為整數。輸入保證在1到3999的範圍內。
Example 1:
Input: “III”
Output: 3

Example 2:
Input: “IV”
Output: 4

Example 3:
Input: “IX”
Output: 9

Example 4:
Input: “LVIII”
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 5:
Input: “MCMXCIV”
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

解法:

/* 羅馬符號與數值的對應定義表
Symbol       Value
  I             1
  V             5
  X             10
  L             50
  C             100
  D             500
  M             1000
*/

int romanToInt(char* s) { //參數傳進來字串指標
    int i, sum=0;
    
    for(i=0; s[i]!='\0'; i++){ //字串指標可以透過array方式個別取值, 搭配for迴圈逐一檢查
        switch (s[i]) {  //建立switch-case語法以個別處理
            case 'M': 
                sum += 1000; //先加1000
                if(s[i-1] == 'C') sum -= 100*2; //檢查它的前一位元, 若為C必須扣除2次100, 因為之前C有重復加100, 以下以此類推
                break; 
            case 'D': 
                sum += 500; 
                if(s[i-1] == 'C') sum -= 100*2;                
                break; 
            case 'C': 
                sum += 100; 
                if(s[i-1] == 'X') sum -= 10*2;                
                break; 
            case 'L': 
                sum += 50; 
                if(s[i-1] == 'X') sum -= 10*2;               
                break;
            case 'X': 
                sum += 10; 
                if(s[i-1] == 'I') sum -= 1*2;  
                break;
            case 'V':    
                sum += 5; 
                if(s[i-1] == 'I') sum -= 1*2;  
                break;
            case 'I': 
                sum += 1; //I的話, 不用扣值
                break;                 
            default: 
                printf("Wrong Character!\n"); //其他字元不支援
        }
    }
    
    return sum; //加總結果回傳
}

/* 羅馬符號與數值的對應定義表

Symbol Value

I 1

V 5

X 10

L 50

C 100

D 500

M 1000

int romanToInt(char* s) { //參數傳進來字串指標

int i, sum=0;

for(i=0; s[i]!='\0'; i++){ //字串指標可以透過array方式個別取值, 搭配for迴圈逐一檢查

switch (s[i]) { //建立switch-case語法以個別處理

case 'M':

sum += 1000; //先加1000

if(s[i-1] == 'C') sum -= 100*2; //檢查它的前一位元, 若為C必須扣除2次100, 因為之前C有重復加100, 以下以此類推

break;

case 'D':

sum += 500;

if(s[i-1] == 'C') sum -= 100*2;

break;

case 'C':

sum += 100;

if(s[i-1] == 'X') sum -= 10*2;

break;

case 'L':

sum += 50;

if(s[i-1] == 'X') sum -= 10*2;

break;

case 'X':

sum += 10;

if(s[i-1] == 'I') sum -= 1*2;

break;

case 'V':

sum += 5;

if(s[i-1] == 'I') sum -= 1*2;

break;

case 'I':

sum += 1; //I的話, 不用扣值

break;

default:

printf("Wrong Character!\n"); //其他字元不支援

}

return sum; //加總結果回傳

}

* Two Sum:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target) {
    int i, j, tmpsum;
    int *ret = malloc( 2 * sizeof(int) );

    
    for(i=0; i < numsSize; i++){
        for(j=i+1; j< numsSize; j++){
            tmpsum = nums[i] + nums[j];
            if( target == tmpsum){
                ret[0] = i;
                ret[1] = j;
                return ret; 
            }
        }
    }
    
    free(ret);
    
    return NULL;
}

/**

* Note: The returned array must be malloced, assume caller calls free().

int* twoSum(int* nums, int numsSize, int target) {

int i, j, tmpsum;

int *ret = malloc( 2 * sizeof(int) );

for(i=0; i < numsSize; i++){

for(j=i+1; j< numsSize; j++){

tmpsum = nums[i] + nums[j];

if( target == tmpsum){

ret[0] = i;

ret[1] = j;

return ret;

}

free(ret);

return NULL;

}

Reverse Integer

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:
Input: 123
Output: 321

Example 2:
Input: -123
Output: -321

Example 3:
Input: 120
Output: 21

Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

解答:

int reverse(int x){
    
    int i = 0;
    int revNum =0;     //用來代表最後reverse Integer
    int zeroCounter =0;   //紀錄原本x數字, 尾巴帶有多少個0
    int onesDigit =0;     //個位數的值
    
    bool isPositiveNum = true;    //是負數嗎
    bool isFirstgetZero = true;   //是第一次遇到尾數有0嗎
        
    if(x < 0 )  //如果原本 x 小於0
    {    
        isPositiveNum = false;  //設為false
        if(x <= pow(-2,31))     //處理overflows算術溢位
            return 0;
        else                    //如果沒overflows算術溢位, 就取x為正數
            x = -x;
    } 
    
    while( x > 0 ){             //只要x為正數, 就要處理
        onesDigit = x % 10;     //取餘數
        if(onesDigit == 0 )     //若餘數是0, 就開始計數
            zeroCounter ++;
        else                    //若餘數非0, 就重置clear計數
            zeroCounter = 0;
        
        if(revNum > (pow(2,31)-1)/10)   //處理overflows算術溢位, 
            return 0;
        else
            revNum = revNum*10 + onesDigit; //如果revNum太大就不適合再加乘10, 會在assign時候出錯!
        
        x = x / 10;  //為下一次loop作準備
    }

    revNum /= pow(10, zeroCounter); //跳出迴圈後, 必須處理掉尾數的0
    
    
    if(!isPositiveNum)    //如果原本x是負數, 則在這裡轉回負數
        revNum =- revNum;

    return revNum;
}

int reverse(int x){

int i = 0;

int revNum =0; //用來代表最後reverse Integer

int zeroCounter =0; //紀錄原本x數字, 尾巴帶有多少個0

int onesDigit =0; //個位數的值

bool isPositiveNum = true; //是負數嗎

bool isFirstgetZero = true; //是第一次遇到尾數有0嗎

if(x < 0 ) //如果原本 x 小於0

{

isPositiveNum = false; //設為false

if(x <= pow(-2,31)) //處理overflows算術溢位

return 0;

else //如果沒overflows算術溢位, 就取x為正數

x = -x;

}

while( x > 0 ){ //只要x為正數, 就要處理

onesDigit = x % 10; //取餘數

if(onesDigit == 0 ) //若餘數是0, 就開始計數

zeroCounter ++;

else //若餘數非0, 就重置clear計數

zeroCounter = 0;

if(revNum > (pow(2,31)-1)/10) //處理overflows算術溢位,

return 0;

else

revNum = revNum*10 + onesDigit; //如果revNum太大就不適合再加乘10, 會在assign時候出錯!

x = x / 10; //為下一次loop作準備

}

revNum /= pow(10, zeroCounter); //跳出迴圈後, 必須處理掉尾數的0

if(!isPositiveNum) //如果原本x是負數, 則在這裡轉回負數

revNum =- revNum;

return revNum;

}

* Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:
Input: [1,3,5,6], 5
Output: 2

Example 2:
Input: [1,3,5,6], 2
Output: 1

Example 3:
Input: [1,3,5,6], 7
Output: 4

Example 4:
Input: [1,3,5,6], 0
Output: 0

解答:

/* 方法1: 透過 Array 與 index 循序尋找 */
int searchInsert(int* nums, int numsSize, int target){
    int i = 0;  //索引數字
    for(i = 0; i < numsSize; i++){ //初始index為0, 循序i++可以透過nums[i]取出int數字
        if(nums[i] >= target)
            return i;  //回傳index
    }
    return numsSize;
}

/* 方法2: 透過 pointer指標 循序尋找, 更省空間 */    
int searchInsert(int* nums, int numsSize, int target){
    int *ptr = NULL;  //索引指標, 注意關鍵在於它被定義為 int*, 所以會以 int的大小找出下一個索引
    for(ptr = nums; ptr != nums+numsSize ;ptr++){ //把初始位置nums給ptr, 之後ptr++就可以找出下一個int數字
        if( *ptr >= target)        
            return (ptr - nums); //透過剪法, 就可以知道是第幾個index
    }
    return numsSize;
}

/* 方法1: 透過 Array 與 index 循序尋找 */

int searchInsert(int* nums, int numsSize, int target){

int i = 0; //索引數字

for(i = 0; i < numsSize; i++){ //初始index為0, 循序i++可以透過nums[i]取出int數字

if(nums[i] >= target)

return i; //回傳index

}

return numsSize;

}

/* 方法2: 透過 pointer指標循序尋找, 更省空間 */

int searchInsert(int* nums, int numsSize, int target){

int *ptr = NULL; //索引指標, 注意關鍵在於它被定義為 int*, 所以會以 int的大小找出下一個索引

for(ptr = nums; ptr != nums+numsSize ;ptr++){ //把初始位置nums給ptr, 之後ptr++就可以找出下一個int數字

if( *ptr >= target)

return (ptr - nums); //透過剪法, 就可以知道是第幾個index

}

return numsSize;

}

Medium:

陸續新增中…

* Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

解答:

筆記轉型成部分不對外開放。
閱讀請繳交3,280元，您就會收到授權一年的邀請函Email，以及紙本重點筆記郵寄給您!

匯款帳號請來信詢問，站長信箱:eeepage@gmail.com
匯款後，請告知您的帳號後三碼與您Gmail作為帳號，易春木會寄出權限開啟之邀請函，三個工作日內可開啟權限。
(*若需信用卡支付, 請來信詢問)

Hard:

陸續新增中…

Leetcode實戰討論

Easy:

* Same Tree:

* Roman to Integer:

* Two Sum:

Reverse Integer

* Search Insert Position

Medium:

* Add Two Numbers

Hard:

發表迴響取消回覆