PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[分享][請益] 廻文數/remove_dump_memory / MaxLevel

看板Prob_Solve (計算數學 Problem Solving)作者tropical72 (藍影)時間12年前 (2012/02/04 17:45)推噓4(4推 0噓 18→)

留言22則, 5人參與討論串1/1

最近拿到 C/C++ 面試卷，比較有印象的是其中三題，由於時間有限，沒能把所有題目記下來，且為原文 (所以我的敘述可能有點差異)，也僅憑印象一起來探討。 1. 迴文數迴文數的定義版上很多人都知道了 < ACM 基礎題 >，但這題隱喻中加了幾個限制： a. effect b. unsigned IsPalindrome(unsigned num); c. 不可調用任何 C/C++ 函式庫完成所以和 ACM 不同的是不可以用 char* 來存。當下我想到的作法是二種，一種是用 while(num) {num/=10;} 技巧，每個位數塞到 const int MAX=20; int dig[MAX]; 裡面去，同時紀錄使用了 used_dig 位數，問題便轉成了對一 array/string 判斷回文數 <最後是用這解法>。另一想法是直接找 min pwr, st pwr>=num, 之後再做一個 rst 為 num 的 inverse，最後再 return rst==num <直覺較麻煩，所以沒用這個>，請教各版友針對此三限制之 Palindrome number 有何想法？ 2. 移除陣列裡重覆之元素 unsigned remove_dumped_memory(unsigned *array, unsigned nItem); 假設一 array 已經過遞增排序, int array[] = {1,1,2,2,2,3,5,8,8,9}，由於元素有 10 個，所以在傳入 nItem 的時候會先確定是 10 << 也就是元素個數 >>。但題意是，經過 remove_dumped_memory 後，能把 array 重覆的拿掉，然後傳回不重覆的元素個數，以上述為例，最後 array[] = {1,2,3,5,8,9}; 傳回6 (如果問我 array[6]~array[9] 哪去了？我只能說從題意看不出來)。同樣的題目裡有個 keyword : effective 直覺掃一遍即可，當時粗寫大概是 unsigned remove_dumped_memory(unsigned *array, unsigned nItem) { int cnt=0, last_position=0; for(i=0; i<nItem-1; ++i){ if(array[i]!=array[i+1]) { array[last_position++]=array[i]; ++cnt; } } return cnt; } 但還有另一份試題沒寫，沒再花時間磨這個。 3. MaxLevel 這個資料結構的東西我很亂，要求要 C 寫。題意是要求 binary tree deep level ( 如果我沒意會錯的話 ... ) typedef struct node{ int value; struct node* left; struct node* right; }mynode; int MaxLevel(struct node* p); 因為不熟，時間也來不急，就亂寫了。大概是寫得像 int max(int a, int b) { return (a>b)? a : b; } int MaxLevel(struct node* p) { if(p==NULL) return 0; else return 1+max(MaxLevel(p->left), MaxLevel(p->right)); } 最後這題反而被抓出來電 Orz -- 世界上有種，將不可能轉換為無限可能的強大力量，我稱它為 - 信念。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 123.195.165.40 ※ tropical72:轉錄至看板 C_and_CPP 02/04 17:47 ※ 編輯: tropical72 來自: 123.195.165.40 (02/04 17:51)

→

firejox

02/04 18:11, , 1^F

02/04 18:11, 1^F

→

tkcn

02/04 18:37, , 2^F

02/04 18:37, 2^F

→

suhorng

02/04 19:13, , 3^F

02/04 19:13, 3^F