Shuntw6096

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };

Shuntw6096

// Online C compiler to run C program online
#include <stdio.h>
#include <stdbool.h>
/* 給一個int a[20]已排序的陣列，請寫一個function(a, size)能印出0~500的數字，
   且不包含a陣列內的元素，請用最少的時間和空間複雜度完成 */
void solution1(int a[], int size) {
    int cur = 0;
    while (cur < size && *(a + cur) < 0)
        cur += 1;
    for (int i = 0; i <= 500; i += 1) {

Shuntw6096

// Online C compiler to run C program online
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

void shuffle(int arr[], int size) {
    //打亂數組, 當pivot是最大值或最小值是worse case,打亂降低機率
    //洗牌算法: 把第i張牌和i之後(包括i)任意一張牌互換
    srand(5);
    int tmp;

Shuntw6096

// Online C compiler to run C program online
#include <stdio.h>
#include <stdlib.h>

void merge(int arr[], int l, int m, int r) {
    //先複製左半和右半arr到新的arr left和right
    //left和right最左邊未排序的元素用leftIdx和rightIdx指著
    //兩個指針誰的元素小誰先放進arr的位置上
    int n1 = m - l + 1, n2 = r - m;// n1 左半長度, n2 右半長度
    int left[n1], right[n2];

Shuntw6096

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

/*
100 -> 1100100
從最左位進stack
stack 1 -> [0,0,1,0,0] bottom
1100100 -> [1,1,0,0,1,0,0] bottom
從top取出最右位放進char array

Shuntw6096

// Online C compiler to run C program online
#include <stdio.h>
#include <stdlib.h>
/*
init
top
bot

top          
9 -> 8 -> 7 -> bot

Shuntw6096

// Online C compiler to run C program online
#include <stdio.h>
#include <stdlib.h>

typedef struct Node{
    char val;
    struct Node* next;
} Node;

void Node_init(Node* n){

Shuntw6096

'''
https://www.geeksforgeeks.org/convert-array-into-zig-zag-fashion/
給定一個一維整數陣列, 輸出為鋸齒狀排列的陣列, 沒有唯一答案, 鋸齒狀排列即可

暴力解: 排列然後, 然後兩兩交換 tc O(nlogn + n)
解法
0. 鋸齒的上行和下行交替出現, 假設第一齒為下行, prev表示上一齒是上下行(t/f), 右側值pointer right
1. 如果前一個是上行, 比右側值大, 右側值互換, 所以現在是下行
2. 續1, 比右側值小, 更新右側值, 所以現在是下行
3. 如果前一個是下行, 比右側值大, 更新右側值, 所以現在是上行

Shuntw6096

'''
給定一個字串, 只有小寫字母, 給定一整數k,
只要有連續的k個字母, 刪除他們持續刪除直到不能再刪為止
輸出最後的字串

解法: 使用stack
stack存 (字符, 連續數量),
走過一次字串, 把它放進stack裡, 只要字符與stack的top的字符相同
數量就會累加, 一旦stack的top的字符數量等於k, 將它從stack移除
最後再用stack剩下的字符構造答案

Shuntw6096

'''
給定一個矩陣, 裡面只有整數0和1, 在每個row中, 1和0會聚在一起, 左邊排1,右邊排0,
輸出是每個row的index, 照1的數量排序, 如果數量相同, 照index大小排序.
Input: mat =
[[1,1,0,0,0],	// 2
 [1,1,1,1,0],	// 4
 [1,0,0,0,0],	// 1
 [1,1,0,0,0],	// 2
 [1,1,1,1,1]]	// 5
 Output: [2,0,3,1,4]