Finding Most Frequent Duplicates Mode(s) in Binary Search Tree (BST) in C

描述

不同於傳統二元搜尋樹，節點的值可以重複，所以左子樹的值小於等於根的值，右子樹的值大於等於根的值，在樹上找到重複頻率最高的節點(們)並回傳

範例

輸入：空樹
輸出：{}

輸入：單節點

    0
   / \

輸出：{0}

輸入：不同節點各出現一次

    0
     \
      1

輸出：{0,1}

輸入：某節點出現二次

    1
     \
     (2)
     /
   (2)

輸出：{2}

輸入：某些節點出現二次

    (3)
   /   \
 (1)    5
 / \   / \
0   2 4   6
   / \
 (1) (3)

輸出：{1,3}

想法

要先知道哪些/個節點出現頻率最高，必須先走訪節點們比一次。取得最高頻率後，找出節點出現頻率等於最高頻率的個數，用這個動態分配回傳陣列的記憶體，再走訪一次把出現頻率最高的節點(們)加入陣列。

情境是記憶體有限，想一次走訪用雜湊表紀錄節點值和頻率，除了發生衝突(conflict)會算錯頻率，記憶體因為表太大爆掉，變成不得不用時間換空間。

實作

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

void get_modes(struct TreeNode *root, double *last, int *freq, int max, int *modes, int *i)
{
    int val = root->val;
    
    if (root->left)
        get_modes(root->left, last, freq, max, modes, i);

    if (*last != val)
    {
        *freq = 1;
        *last = val;
    }
    else
        (*freq)++;
    
    if (*freq == max)
    {
        modes[*i] = *last;
        (*i)++;
    }
    
    if (root->right)
        get_modes(root->right, last, freq, max, modes, i);
}

void get_num_of_modes(struct TreeNode *root, double *last, int *freq, int max, int *returnSize)
{
    int val = root->val;
    
    if (root->left)
        get_num_of_modes(root->left, last, freq, max, returnSize);
    
    if (*last != val)
    {        
        *freq = 1;        
        *last = val;
    }
    else
        (*freq)++;
    
    if (*freq == max)
        (*returnSize)++;


    if (root->right)
        get_num_of_modes(root->right, last, freq, max, returnSize);
}

void get_max_freq(struct TreeNode *root, double *last, int *freq, int *max)
{
    int val = root->val;
    
    if (root->left)
        get_max_freq(root->left, last, freq, max);
    
    if (*last != val)
    {
        *freq = 1;
        *last = val;
    }
    else
        (*freq)++;

    if (*freq > *max)
        *max = *freq;
    
    if (root->right)
        get_max_freq(root->right, last, freq, max);
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* findMode(struct TreeNode* root, int* returnSize){
    *returnSize = 0;
    
    int *modes = NULL;
    double last = -2147483649; // Out of int range to avoid 0 case
    int freq = 0;
    int max = 0;
    int i = 0;
    
    if (root == NULL)
        return NULL;
    
    get_max_freq(root, &last, &freq, &max);
    
    freq = 0;
    last = -2147483649;
    get_num_of_modes(root, &last, &freq, max, returnSize);

    freq = 0;
    last = -2147483649;
    modes = (int *)malloc(sizeof(int) * (*returnSize));
    get_modes(root, &last, &freq, max, modes, &i);
    
    return modes;
}

Validating Binary Search Tree (BST) in C

描述

驗證二元搜尋樹是否有效，有效的二元搜尋樹必須符合下列原則

• 左子樹的值小於根的值
• 右子樹的值大於根的值
• 左右子樹也是二元搜尋樹

範例

• 有效

無節點

單節點

    0
   / \

左右子樹

    2
   / \
  1   3

• 無效
有相同的值

    1
     \
     (1)

右子樹節點的值小於根的值

    10
   / \
  5   15
     / \
   (6)  20

左子樹節點的值大於根的值

    3
     \
     30
    /
   10
     \
     15
       \
      (45)

原理

用中序走訪(inorder traversal)二元搜尋樹取得節點的值會升冪排列，一旦走訪節點的值小於等於前面節點的值，就不是有效二元搜尋樹

實作

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

bool validate(struct TreeNode* root, double *last)
{   
    if (root->left)
        if (validate(root->left, last) == false)
            return false;
    
    // Check ascending order
    if (root->val > *last)
        *last = root->val;
    else
        return false;
    
    if (root->right)
        if (validate(root->right, last) == false)
            return false;
    
    // Subtree is valid
    return true;
}

bool isValidBST(struct TreeNode* root){  
    double last = -2147483649; // integer type minimum is -2147483648, last should be able to store integer minimum
    
    if (root == NULL)
        return true;

    return validate(root, &last);
}

Remove nth node from end of a linked list in C in Linear Time

描述

刪除從串列尾巴往回數第n個節點，n一定有效，回傳輸出串列的head

範例

輸入：1->2->3->4->5, n = 2 輸出：1->2->3->5
輸入：1, n = 1 輸出：NULL
輸入：1->2, n = 2 輸出

想法

用兩個距離n+1的串列指標，一個走訪在前，一個跟在後，走訪在前的指標碰到串列尾節點時，後面的指標在欲刪除節點的前一個。前述的想法適用於3個以上的節點，所以0到2個節點用特殊狀況處理。

實作

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    int x = 0;
    struct ListNode *rear = NULL;
    struct ListNode *ahead = NULL;

    // Empty linked list
    if (!head)
        return head;
    
    // Linked list with one node, n must be 1
    if (!head->next)
        return NULL;
    
    // Linked list with two nodes, n is either 1 or 2
    if (!head->next->next)
    {
        if (n == 1)
        {
            head->next = NULL;
            return head;
        }

        return head->next;
    }
    
    ahead = head;
    for (x = 0; x < n; x++)
        ahead = ahead->next;   
        
    // head is to be removed
    if (!ahead)
        return head->next;
    
    rear = head;    
    while (ahead->next)
    {
        ahead = ahead->next;
        rear = rear->next;
    }
    
    rear->next = rear->next->next;
    return head;
}

Check if Parentheses is Valid in C

規則

• 括弧只有'('、'['與'{'三種
• 括弧必須成對
• 括弧順序必須正確

範例

有效

• "()"
• "{}[]()"
• "[{}]"

無效

• "([{]})"
• "(]"
• "([])("
• "([])}"

原理

• 遞迴：有效的成對括弧內必含有有效括弧
• 堆疊：有效的成對括弧順序是close先進open後出
• 不符合以上原則都是無效括弧

實作

// MODE 0 for recursive, 1 for iterative
#define MODE 1

struct stack {
    char items[65535];
    int top;
};

void push(struct stack *s, char c)
{
    s->items[s->top] = c;
    s->top++;
}

char pop(struct stack *s)
{
    s->top--;
    return s->items[s->top];
}

bool open(char c)
{
    return c == '(' || c== '[' || c == '{';
}

bool worker(struct stack *t, char *s)
{
    char s0 = s[0];
    char top = '\0';
    
    if (s0 == '\0')
    {
        // No pair for open
        if (t->top != 0)
            return false;
        
        return true;
    }
    
    if (open(s0))
    {
        push(t, s0);   
        return worker(t, s + 1);
    }
    
    // No pair for close
    if (t->top == 0)
        return false;
    
    top = t->items[t->top - 1];
    
    if (s0 == ')' && top != '(')
        return false;
    
    if (s0 == ']' && top != '[')
        return false;

    if (s0 == '}' && top != '{')
        return false;

    pop(t);
    return worker(t, s + 1);
}

bool isValid(char * s){
    struct stack t = {0};

#if MODE == 0
    return worker(&t, s);
#else
    int i = 0;
    char c = '\0';
    char top = '\0';

    for (i = 0; s[i] != '\0'; i++)
    {
        c = s[i];
        
        if (open(c))
        {
            push(&t, c);
            continue;
        }
        
        // No pair for close
        if (t.top == 0)
            return false;
        
        top = t.items[t.top - 1];
        if (c == ')' && top != '(')
            return false;
        
        if (c == ']' && top != '[')
            return false;
        
        if (c == '}' && top != '{')
            return false;

        pop(&t);
    }
    
    // Check no pair for open
    return t.top == 0;
#endif
}

Finding Length of Longest Substring without Repeating Characters in C in Linear Time

出處

原理

走訪字串中每個字元，若當前被掃瞄字元沒有被走訪過則暫存到陣列中，目前長度加1，否則判斷當前被掃瞄字元是否在不重複字元的子字串中，若不在則目前長度加1，否則檢查最大長度與目前長度，若目前長度大於最大長度就將最大長度設定為目前長度，並且移動不重複字元子字串的起始點到重複字元的下一個字元，例如輸入為"dxdy"，遇到第二個d而且d已經在不重複字元子字串"dx"中，則不重複字元子字串起始點從d移動到x，例如輸入為"pwwkew"，遇到第二個w而且w已經在不重複自原子字串"pw"中，則不重複自原子字串起始點從p移動到第二個w，最後重設目前長度，長度應為新的不重複字元子字串起始點算到當前被掃瞄字元，走訪完所有字元後的目前長度再跟最大長度比較決定最大長度。

實作

#define NUM_CHAR 256

int hash(char x)
{
    return x % NUM_CHAR;
}

int length_of_longest_substring(char * str)
{
    char visited[NUM_CHAR] = {0};
    char temp[NUM_CHAR] = {0};
    char * current_scanned = NULL;
    char * nrcs_start = NULL;  // nrcs: non-repeating character substring
    int key = 0;
    int cur_length = 0;
    int max_length = 0;
    
    current_scanned = s;
    nrcs_start = str;
    while (*current_scanned != '\0')
    {        
        key = hash(*current_scanned);
        if (visited[key] != *current_scanned)
        {
            visited[key] = *current_scanned;
            cur_length++;
            goto end;
        }
        
        strncpy(temp, nrcs_start, cur_length);
        if (!strchr(temp, *current_scanned))
        {
            cur_length++;
            memset(temp, 0, NUM_CHAR);
            goto end;
        }
        
        memset(temp, 0, NUM_CHAR);
        
        if (cur_length > max_length)
            max_length = cur_length;

        while (*nrcs_start != *current_scanned)
            nrcs_start++;
        nrcs_start++;
        
        cur_length = current_scanned - nrcs_start + 1;

end:
        current_scanned++;
    }

    if (cur_length > max_length)
        max_length = cur_length;
    
    return max_length;
}