Brain teaser

292  Nim Game   

You can always win a Nim game if the number of stones n in the pile is not divisible by 44.







Second Time 
=============================================


319 Bulb Switcher (N)

A light will be toggled only during the round of its factors, e.g. number 6 light will be toggled at 1,2,3,6 and light 12 will be toggled at 1,2,3,4,6,12. The final state of a light is on and off only depends on if the number of its factor is odd or even. If odd, the light is on and if even the light is off. The number of one number’s factor is odd if and only if it is a perfect square!
So we will only need to loop to find all the perfect squares that are smaller than n!
Actually, the number of perfect square number within n is sqrt(n)



777  Swap Adjacent in LR String  

题目要求根据给定的规则，判断能否从 start string 变换到 end string 。
给出了两种变换的规则，从“XL”到“LX”和从“RX”到“XR”。所以我们可以给出两条规律：
  • 如果start能变换到end，那么除去两个字符串中的"X"，剩余的字符串一定相同。因为任意"R"和"L"的相对顺序都不会发生变化，我们定义出去"X"的字符串为有效字符串
  • 根据变换的规则，"L"不能向右移，“R”不能向左移，所以 start 中“L”对应的 index "i" 一定不小于 end 中 “L”对应的index "j"；start 中“R”对应的 index "i" 一定不大于 end 中 “R”对应的index "j"；
    1. i >= j, 如果 start[i]==end[j]==”L”
    2. i <= j, 如果 start[i]==end[j]==”R”

    Rule 2 (version 2)
      We must make sure that we have less or equal number of L seen in start than in end and
       less or equal number of R seen in end than in start so that it is possible that after
       shifting L left and R right we can transform start to end.
    Use count sl,el,sr,er while traversing start and end, make sure it always obey (sl <= el && sr >= er)

Comments

Post a Comment

Popular posts from this blog

zhitongguigu

Lecture 1: To do: (117? 199) Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree . In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree. numerical_limits<int>::min()   <==> INT_MIN
Read more

Array Part2

Two pointers 977 Squares of a Sorted Array      We can use two pointers to read the positive and negative parts of the array - one pointer  j  in the positive direction, and another  i  in the negative direction. Now that we are reading two increasing arrays (the squares of the elements), we can merge these arrays together using a two-pointer technique. 11 Container With Most Water      O(N) time and O(1) space, since better candidadates must use the taller line of l and r therefore we can use two pointer keep moving towards each other until they meet. Always abandon the shorter line while moving. 80 Remove Duplicates from Sorted Array II      tail = 0; for (int i = 0;  i < nums.size(); i++)           if (i < 2 || nums[i] > nums[tail - 2]) // not included twice yet                 nums[tail++] = nums...
Read more

Two pointers (Part 1)

344 Reverse String      Use two pointers i, j. keep switching elements at position i, j while i < j.     string reverseString(string s) {        for (int i = 0, j = s.size() - 1; i < j; i++, j--)            swap(s[i], s[j]);                  return s;     } 345 Reverse Vowels of a String      Similar with 344  Reverse String ,  except we need to guard the swap operation conditionally based on whether the current two chars are vowels or not. 283 Move Zeroes      Use two pointers, the front iterates the elements in the array. while the tail one keeps the current store position. If front is not zero, store it to the tail position and increase tail pointer. After the loop, set all the remaining with zero. 349 Intersection of Two Arrays      ...
Read more