[思路]LeetCode Problems- 657. Judge Route Circle

Leetcode於每周末都會舉辦線上的程式解題比賽,在比賽結束後便會釋出最新的題目供大家練習.這次要介紹的便是上週出現的新題目.題目原文如下:

Initially, there is a Robot at position (0, 0). Given a sequence of its moves, judge if this robot makes a circle, which means it moves back to the original place.

The move sequence is represented by a string. And each move is represent by a character. The valid robot moves are R (Right), L(Left), U (Up) and D (down). The output should be true or false representing whether the robot makes a circle.

Example 1:

Input: "UD"
Output: true

Example 2:

Input: "LL"
Output: false

題目假設有一機器人在原點位置,則給定字串UDLR來讓它上下左右在二維平面中移動,回傳最後位置是否還停留在原點上.

一開始看到時我的想法是先假設好一個二維的空間,
若程式偵測到有'U'的話,則在Y軸方向加1,
有'R'的話則在X軸方向加1....諸如此類.

但是其實就程式的結果來看,我們並不需要知道機器人最後會落在座標平面上的哪個位置,重點是只要知道"在不在原點上"就好了.
因此程式設計的邏輯還可以再簡單
精簡成為一目標就是"走向左邊的步數"等於"走向右邊的步數",並且"走向上的步數"等於"走向下的步數"
意指在要看字串中"U的個數=D的個數"並且"L的個數=R的個數"
達成這個條件就知道機器人已經回到原點了

C語言要在字串中找尋特定字元的方法,我們可以用strpbrk()這個函式:

先前在[思路]LeetCode Problems- 537. Complex Number Multiplication 中有提到一些字串函式的用法,使用這函式時這會回傳字串中特定符號的位址,所以要指派一個指標給它.
此外這函式只會找出字串中"第一次"出現的位址,這樣我們就要用迴圈-----例如while-----來讓這函式能重複查詢.

首先,定義好要搜尋的字元字串以及指標,以其中一個步數"向右走"為例:

char key[] = "R";
char * pch;

並且定義一個用來存取"字母R出現了多少次"的int變數,初始為0:

int R=0;

假設存放一連串UDLR指定步數的目標字串定義為moves,則要找出有多少個R的話一開始先寫:

pch = strpbrk (moves, key);

這裡只有找出第一次出現R字元的位址.欲要讓這函式不斷執行則要搭配while迴圈如下:

while (pch != NULL)
  {
    R++;
    pch = strpbrk (pch+1,key);
  }

當指標不為空位址時,則紀錄R步數+1,並且從下一個位置再開始查詢一次,直到把整個字串都走完為止.

我們將這方法依序使用到針對 U,L,D上,則就能知道上下左右的步數各走多少次了,
最後就是再判斷機器人經過這些步數後,是否還在原點上:

if  ( R= =L && U= =D )
    {
        return true;    
     
    }
    else
    {
        return false;
    }

此題的程式就這樣解決了~~!