2019/01/23

LeerCode 566. Reshape the Matrix

In MATLAB, there is a very useful function called 'reshape', which can reshape a matrix into a new one with different size but keep its original data.
You're given a matrix represented by a two-dimensional array, and two positiveintegers r and c representing the row number and column number of the wanted reshaped matrix, respectively.
The reshaped matrix need to be filled with all the elements of the original matrix in the same row-traversing order as they were.
If the 'reshape' operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.
Example 1:
Input: 
nums = 
[[1,2],
 [3,4]]
r = 1, c = 4
Output: 
[[1,2,3,4]]
Explanation:
The row-traversing of nums is [1,2,3,4]. The new reshaped matrix is a 1 * 4 matrix, fill it row by row by using the previous list.
Example 2:
Input: 
nums = 
[[1,2],
 [3,4]]
r = 2, c = 4
Output: 
[[1,2],
 [3,4]]
Explanation:
There is no way to reshape a 2 * 2 matrix to a 2 * 4 matrix. So output the original matrix.
Note:
  1. The height and width of the given matrix is in range [1, 100].
  2. The given r and c are all positive.

這一題是要將一個原先是 r * c 的陣列轉換成 nr * nc 的陣列，沒有什麼特別的技巧，就是重新排列而已，因為是連續取值，所以原陣列的 row 跟 col 就用 ++ 的方式來處理，以加快速度。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *columnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** matrixReshape(int** nums, int numsRowSize, int numsColSize, int r, int c, int** columnSizes, int* returnSize) {
    int **ret;
    int i, j, rr, cc;
    
    if (numsRowSize * numsColSize != r * c) {
        ret = nums;
        *returnSize = numsRowSize;
        columnSizes[0] = (int *) malloc (numsRowSize * sizeof(int));
        for (i=0; i<numsRowSize; i++) {
            columnSizes[0][i] = numsColSize;
        }
    } else {
        *returnSize = r;
        columnSizes[0] = (int *) malloc (r * sizeof(int));
        ret = (int **) malloc (r * sizeof(int *));
        rr = 0;
        cc = 0;
        for (i=0; i<r; i++) {
            ret[i] = (int *) malloc (c * sizeof(int));
            columnSizes[0][i] = c;
            for (j=0; j<c; j++) {
                ret[i][j] = nums[rr][cc];
                if (++cc == numsColSize) {
                    ++rr;
                    cc = 0;
                }
            }
        }
    }
    return ret;
}




on 沒有留言:

2019/01/19

leetcode 885. Spiral Matrix III

On a 2 dimensional grid with R rows and C columns, we start at (r0, c0)facing east.
Here, the north-west corner of the grid is at the first row and column, and the south-east corner of the grid is at the last row and column.
Now, we walk in a clockwise spiral shape to visit every position in this grid. 
Whenever we would move outside the boundary of the grid, we continue our walk outside the grid (but may return to the grid boundary later.) 
Eventually, we reach all R * C spaces of the grid.
Return a list of coordinates representing the positions of the grid in the order they were visited.

Example 1:
Input: R = 1, C = 4, r0 = 0, c0 = 0
Output: [[0,0],[0,1],[0,2],[0,3]]

Example 2:
Input: R = 5, C = 6, r0 = 1, c0 = 4
Output: [[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]

Note:
  1. 1 <= R <= 100
  2. 1 <= C <= 100
  3. 0 <= r0 < R
  4. 0 <= c0 < C

 這題用沒有向量的C不是很容易解，只好用暴力的方式求解，利用的方法很單純，就是讓 (r0, c0) 去繞圈圈，而且根據旋轉的特性，可以發現右下左上這樣的順序，格數變量是 1,1,2,2,3,3,4,4....，所以程式就長成下面這樣。leetcode 報 20ms，目前百分位置是 100%，期待出現更快的解法可以參考。

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *columnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** spiralMatrixIII(int R, int C, int r0, int c0, int** columnSizes, int* returnSize) {
    int **ret;
    int i, j;
    int step;

    *returnSize = R * C;
    columnSizes[0] = (int *) malloc (R * C * sizeof(int));
    ret = (int **) malloc (R * C * sizeof(int *));

    i = 0;
    ret[i] = (int *) malloc (2 * sizeof(int));
    ret[i][0] = r0;
    ret[i][1] = c0;
    columnSizes[0][i] = 2;
    ++i;
    if (i == *returnSize) {
        return ret;
    }

    step = 1;
    while(1) {
        if (r0 >=0 && r0 < R) {
            for (j=1; j<=step; j++) {
                ++c0;
                if (c0 >= 0 && c0 < C) {
                    ret[i] = (int *) malloc (2 * sizeof(int));
                    ret[i][0] = r0;
                    ret[i][1] = c0;
                    columnSizes[0][i] = 2;
                    ++i;
                    if (i == *returnSize) {
                        return ret;
                    }
                }
            }
        } else {
            c0 += step;
        }
        if (c0 >= 0 && c0 < C) {
            for (j=1; j<=step; j++) {
                ++r0;
                if (r0 >=0 && r0 < R) {
                    ret[i] = (int *) malloc (2 * sizeof(int));
                    ret[i][0] = r0;
                    ret[i][1] = c0;
                    columnSizes[0][i] = 2;
                    ++i;
                    if (i == *returnSize) {
                        return ret;
                    }
                }
            }
        } else {
            r0 += step;
        }
        ++step;
        if (r0 >= 0 && r0 < R) {
            for (j=1; j<=step; j++) {
                --c0;
                if (c0 >= 0 && c0 < C) {
                    ret[i] = (int *) malloc (2 * sizeof(int));
                    ret[i][0] = r0;
                    ret[i][1] = c0;
                    columnSizes[0][i] = 2;
                    ++i;
                    if (i == *returnSize) {
                        return ret;
                    }
                }
            }
        } else {
            c0 -= step;
        }
        if (c0 >= 0 && c0 < C) {
            for (j=1; j<=step; j++) {
                --r0;
                if (r0 >=0 && r0 < R) {
                    ret[i] = (int *) malloc (2 * sizeof(int));
                    ret[i][0] = r0;
                    ret[i][1] = c0;
                    columnSizes[0][i] = 2;
                    ++i;
                    if (i == *returnSize) {
                        return ret;
                    }    
                }
            }
        } else {
            r0 -= step;
        }
        ++step;
    }
    return ret;
}
on 沒有留言:
標籤：

2018/11/07

自製 make menuconfig

linux kernel 提供的 kconfig 功能十分好用，openwrt 和 buildroot 也都拿來使用，但是內容太龐大，整包拿來用並不輕鬆，所幸找到一包已經從 kconfig 抽出來的 standalong 版本 (github 連結)，可以好好的利用，以下就是利用這個 github 當基礎來建立一個簡單的 menuconfig template。

資料夾結構

名稱(Name) 描述(Descript)
~/build/ 編譯空間
~/defconfig/ 放置 defconfig 的地方
~/host-tools/ 集中放置 host 工具的地方，可再擴充，像是 toolchain
~/host-tools/menuconfig/ standalong 的原始碼，內層不再贅述

~/host-tools/menuconfig/Makefile
原始的專案採用 cmake，因為會產生 cmake 相關的檔案，所以自己建一個簡單的 Makefile 來用

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
CC ?= gcc

lxdialog := lxdialog/checklist.o
lxdialog += lxdialog/util.o
lxdialog += lxdialog/inputbox.o
lxdialog += lxdialog/textbox.o
lxdialog += lxdialog/yesno.o
lxdialog += lxdialog/menubox.o

mconf-objs := mconf.o
mconf-objs += zconf.tab.o
mconf-objs += $(lxdialog)

conf-objs := conf.o
conf-objs += zconf.tab.o

clean-files	:= mconf conf
clean-files += $(mconf-objs)
clean-files += $(conf-objs)

all: mconf conf
	
$(obj)/%.o: %.c
	$(CC) -c $< -o $@

mconf: $(mconf-objs)
	$(CC) $(mconf-objs) -o mconf -lncurses

conf: $(conf-objs)
	$(CC) $(conf-objs) -o conf

clean:
	@rm -f $(clean-files)
這個 Makefile 預設使用 gcc 進行編譯，如果需要更改，需要 make 的時候予以告知，例如 make CC=your_compiler
make 完成後會產生 mconf 和 conf 兩個執行檔

~/Makefile 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
ifneq ("$(wildcard .config)","")
	include .config
endif

all: preconfig

preconfig:
ifeq ("$(wildcard .config)","")
	$(error "Please run make menuconfig first.")
endif

menuconfig:
	@mkdir -p build
	@rsync -ur host-tools/menuconfig build
	@make -C build/menuconfig
	@./build/menuconfig/mconf Config.in

list-defconfigs:
	@echo 'Built-in configs:'
	@$(foreach b, $(sort $(notdir $(wildcard defconfig/*_defconfig))), \
	  printf "  %-35s - Build for %s\\n" $(b) $(b:_defconfig=);)
	@echo

%_defconfig:
	@./build/menuconfig/conf --defconfig=defconfig/$@ Config.in~
1~3: 如果已經存在 .config 就將內容 include 進來
5: all 之前要先跑過 preconfig
7~10: preconfig 會檢查 .config 是不是存在，如果不存在就顯示要求執行 menuconfig 並且報錯跳出
12~16: menuconfig 主體，make 的機制是已經編譯過且沒有更改內容，就不會重新編譯
18~22: list-defconfigs 可以列出在 ~/defconfig 裡面的所有 *_defconfig
24~25: 當執行 make xxxx_defconfig 就會依據 xxxx_defconfig 來產生 .config

使用這個 template 可以建立一個基本的 menuconfig 功能，通常會根據不同的 target board 或是個別的客製化來製作 xxxx_defconfig，要編譯的時候就可以直接 make xxxx_defconfig 然後再 make all。

一般來說，build 放置的是 target 的編譯空間，砍掉 build 就會非常乾淨，但是 host-tools 也得重編，所以如果確定 host-tools 跟 target 無依存關係，也可以另外開 host-build 來用。

on 沒有留言:

2018/09/20

如何在 Linux Shell 指令直接建立 partition

利用 pipe line 來模擬手動輸入

echo -e "n\np\n1\n\n\nw\n" | fdisk /dev/mmcblk0


on 沒有留言:

2018/08/09

執行時期控制 linux kernel 印出的訊息

(based on linux kernel version 3.10.104)

在 embedded linux 開發過程中，常常會為了對 kernel space 進行追蹤而使用 printk，但是每次編譯重燒是很耗費時間的，所以直接在執行時期控制 printk 的訊息要不要顯示出來，會是追蹤的一門重要技巧。

參考

printk 提供了一個在執行時期的控制介面，/proc/sys/kernel/printk

#cat /proc/sys/kernel/printk
7 4 1 7

第一個數字代表要印出來的最低等級，也就是等級高於或等於7 (KERN_DEBUG) 都會被印出來
第二個數字代表 printk 沒有指定等級的預設等級 4 (KERN_WARNING)

因為 KERN_WARNING 等級高於 KERN_DEBUG，所以目前不指定等級的 printk() 都會被印出來。

如果只想看到嚴重等級以上的訊息，可以直接

#echo 2 > /proc/sys/kernel/printk
#cat /proc/sys/kernel/printk
2 4 1 7

這樣未指定等級的訊息就不會顯示出來，甚至等級為 KERN_ERR 的訊息也都忍住不噴出了。

以下列出各等級資料：

Name String Meaning alias function
KERN_EMERG "0" Emergency messages, system is about to crash or is unstable pr_emerg
KERN_ALERT "1" Something bad happened and action must be taken immediately pr_alert
KERN_CRIT "2" A critical condition occurred like a serious hardware/software failure pr_crit
KERN_ERR "3" An error condition, often used by drivers to indicate difficulties with the hardware pr_err
KERN_WARNING "4" A warning, meaning nothing serious by itself but might indicate problems pr_warning
KERN_NOTICE "5" Nothing serious, but notably nevertheless. Often used to report security events. pr_notice
KERN_INFO "6" Informational message e.g. startup information at driver initialization pr_info
KERN_DEBUG "7" Debug messages pr_debug, pr_devel if DEBUG is defined
KERN_DEFAULT "d" The default kernel loglevel
KERN_CONT "" "continued" line of log printout (only done after a line that had no enclosing \n) [1] pr_cont
on 沒有留言:
訂閱： 文章 (Atom)