

leetcode_OJ WC70 解題心得

• Contest time: Feb 4, 2018
• Virtual contest by myself: Mar 4, 2018

PA. 779. K-th Symbol in Grammar 找規律題

• 思路：找規律，前面的N，實際上是障眼法。 以下的N是一(1-based) 2 3 5 8 9 12 14 15 其-1後二進位表示法為： 0001 0010 0100 0111 1000 1011 1101 1110 減一後有奇數個一則為1 否則為0

class Solution
{
public:
    int kthGrammar(int nin, int kin)
    {
        int cnt = 0;
        kin--;
        while(kin)
        {
            if(kin&1)
            {
                cnt++;
            }
            kin>>=1;
        }
        return cnt&1;
    }
};

PB.

被鎖住看不到＠＠，事後賽，需要升級成高級會員才有，看題目是切割二元樹

PC. 777. Swap Adjacent in LR String 字串內部dfs

• 錯誤思路 ：想說用擴散解法，dfs下去視情況交換，然吃了一個大RE(stack overflow) 後來發現是忘了寫visited＝ ＝，根本蠢，看來這方面還得多多磨練造化

  //Runtime Error (stack overflow)
  class Solution {
  public:
      bool can = false;
      bool canTransform(string start, string end)
      {
          if(start == end)
              return 1;
          else
          {
              dfs(start, end, 0, start.size()-1);
          }
          return can;
      }
      void dfs(string start, string end, int lptr, int rptr) //quick sort-like recusrion
      {
          if(lptr >= rptr) //length end
          {
              return ;
          }
          if(start ==  end)
          {
              can = true;
              return ;
          }
          int len = start.size() >> 1;
          int lptr1 = lptr, rptr1 = len;
          int lptr2 = len + 1, rptr2 = rptr;
          for(int pos = lptr;pos <= rptr;pos++)
          {
              if(start[pos]=='X' && start[pos+1]=='L')
              {
                  swap(start[pos],start[pos+1]);
              }
              else if(start[pos]=='R' && start[pos+1]=='X')
              {
                  swap(start[pos],start[pos+1]);
              }
          }
          dfs(start, end, lptr1, rptr1);
          dfs(start, end, lptr2, rptr2);
  
      }
  };
  

• 正確思路，參考了討論區提示：由於R只能向右，而L只能向左，因此我們可以透過兩個指標在兩字串中跑，找到第一個非X的字元，若不一樣則必然無法替換，而要使得R能夠替換成結果 唯有start 的 R 較 end 的 R 左側，才有機會向右，若R已經太右邊了（亦即超出end的R ） 便是換不過去了，同理可得L的概念

class Solution {
public:
    bool can = false;
    bool canTransform(string start, string end)
    {
        if(start == end)
            return 1;
        else if(start.size() != end.size())
        {
            return 0;
        }

        int len = start.size();
        int ptr1 = 0, ptr2 = 0;
        while(ptr1 < len && ptr2 < len) //both in the boundary
        {
            while(ptr1 < len && start[ptr1] == 'X') //iterate till not X in start
                ptr1++;

            while(ptr2 < len && end[ptr2] == 'X') //iterate till not X in end
                ptr2++;

            if(start[ptr1] != end[ptr2]) //example  XL RX they are different, unable to swap
                return 0;

            //iterate till next non X, both increment

            if(start[ptr1] == 'R' && ptr1 > ptr2) //R of start is right to the R of end,
            //R can only move right but this situation needs R to move left, which is a contradiction
            //注意不能寫ptr1 >= ptr2 因為 XRXL XRLX   XR部份已經滿足，是 XR RX才不行！！
            {
                return 0;
            }
            else if(start[ptr1] == 'L' && ptr2 > ptr1)
            //L of start is left to the L of end,
            //L can only move left but this situation needs L to move right, which is a contradiction
            {
                return 0;
            }
            ptr1++;
            ptr2++;

        }
        return 1;
    }

};