Fw: [請益] 廻文數/remove_dump_memory / MaxLevel

看板C_and_CPP作者tropical72 (藍影)時間14年前 (2012/02/04 17:47)推噓3(3推 0噓 32→)

留言35則, 6人參與討論串1/1

※ [本文轉錄自 Prob_Solve 看板 #1FBFuaqO ] 作者: tropical72 (藍影) 站內: Prob_Solve 標題: [分享][請益] 廻文數/remove_dump_memory / MaxLevel 時間: Sat Feb 4 17:45:04 2012 最近拿到 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 ※ 發信站: 批踢踢實業坊(ptt.cc) ※ 轉錄者: tropical72 (123.195.165.40), 時間: 02/04/2012 17:47:22 ※ 編輯: tropical72 來自: 123.195.165.40 (02/04 17:50)

→