[C Programming] 最長平台問題-延伸

針對最長平台問題，達成新的要求：
1. 請改寫程式，指出最長平台的位置。
2. 請寫一個程式，接收一個已經自小到大排好的陣列，
    把所有平台與它的位置都找出來。
3. 如果給定的陣列沒有依序排好，
    請寫一個程式可以找出所有平台與它們的位置，
    但給定的陣列卻不一定要排列好。
    (程式還可以只比n次就找到答案嗎？)
4.寫成遞迴的模式。

個人解法：
1. 我們插入一個變數來記錄一個平台的結束點，
    按照原方法，當找到一個更長的平台時，
    就把結束點再次變更到該索引值。

Code：

// Use *index to remember the end point.
int longest_pl(int x[], int n, int* index, int* len)
{
 *len = 1;
 int i;
 for(i = 1; i < n; i++)
  if( x[i] == x[i-*len] )
  {
   *len = *len + 1; 
   *index = i;
  }
 return *len;
}

2&3. 改寫大概就不能用原來那套的方法了，
因為必定要加入變數來記錄位置，所以就乾脆換方法吧？

Code：

// Complexity is O(n)
void all_pldata(int x[], int n, int rec[][3])
{
 int i;
 int tmp = 0;
 int cnt = 0;
 for(i = 1; i < n; i++) 
 {
  if( x[i] != x[tmp] )
  {
   rec[cnt][0] = x[tmp]; rec[cnt][1] = tmp; rec[cnt][2] = i-tmp;
   // printf("%d : Index %d ~ %d\n", x[tmp], tmp, i-1);
   tmp = i; cnt++;
  }
  else if( i + 1 == n ) // Last index
  {
   rec[cnt][0] = x[tmp]; rec[cnt][1] = tmp; rec[cnt][2] = i-tmp+1;
   // printf("%d : Index %d ~ %d\n", x[tmp], tmp, i);
   cnt++; rec[cnt][0] = -1;
  }
 }
 for(i=0; i<cnt; i++)
 {
  printf("%d : Index %d ~ %d\n", 
    rec[i][0], rec[i][1], rec[i][1]+rec[i][2]-1); 
 } 
}

int rec[][3]的一維長度設為n。每一組rec[]中存的依序為：
平台的數字、平台起始點、平台長度。
當中注意要處理最後一組的狀況，會有一點點差異。
如果不是全部平台長度為1，則rec不會被用完，在尾端補上-1，
可以方便外界想使用的時候，能有迴圈的終止條件。(否則會一路跑下去)
當然如果覺得多花了記憶體空間的話，也可以先找出共有幾組平台，
再進行宣告並把資料丟進去，只是就會多出先跑一次的執行時間。

比較的次數依舊為n次，因為開頭從i=1開始，
但結束的時候可能會跑過if以及else if兩個判斷式。

其實tricky一點來說，還要考慮n==1的狀況XD

// 把它放在函式的開頭!
if(n==1)
{
 printf("%d : Index %d ~ %d\n", x[0], 0, 0); 
 return;
}

4.其實跟原本的樣子差不多，寫成遞迴不會比較快就是了@@"

Code：

// 丟出來的時候不要忘了用*來取值。
int* recur_pl(int x[], int n, int *i, int* len)
{
 // Let *len = 1, i = 1 when first time calling this function.
 if(*i == n) return len;
 if( x[*i] == x[*i-*len] ) *len = *len + 1; 
 *i = *i + 1;
 return recur_pl(x, n, i, len);
}