<h1>779. K-th Symbol in Grammar</h1>

On the first row, we write a 0. Now in every subsequent row, we look at the previous row and replace each occurrence of 0 with 01, and each occurrence of 1 with 10.

Given row N and index K, return the K-th indexed symbol in row N. (The values of K are 1-indexed.) (1 indexed).

Examples:
Input: N = 1, K = 1
Output: 0

Input: N = 2, K = 1
Output: 0

Input: N = 2, K = 2
Output: 1

Input: N = 4, K = 5
Output: 1

Explanation:
row 1: 0
row 2: 01
row 3: 0110
row 4: 01101001

Note:
1. N will be an integer in the range [1, 30].
2. K will be an integer in the range [1, 2^(N-1)].

My Solution(36ms 12.8MB)

public class Solution {
public int KthGrammar(int N, int K) {
return recursiveFind(K - 1);
}

private int recursiveFind(int k)
{
if (k == 0)
{
return 0;
}
else if (k % 2 == 1)
{
return inverse(recursiveFind(k / 2));
}
else
{
return recursiveFind(k / 2);
}
}

private int inverse(int k)
{
return k == 1 ? 0 : 1;
}
}

No.1 Solution(36ms)

public class Solution {
public int KthGrammar(int N, int K) {
return helper(N, K-1);
}

public int helper(int N,int K) {
if(N==1||K==0) return 0;
else {
if(K%2==0) return helper(N-1,K/2);
else return helper(N-1,K/2) ^ 1;
}
}
}

Things to improve

There is not much things to improve in this case, it’s recursive logic and I personally don’t like recursive…

<h1>838. Push Dominoes</h1>

There are N dominoes in a line, and we place each domino vertically upright.
In the beginning, we simultaneously push some of the dominoes either to the left or to the right.

There are N dominoes in a line, and we place each domino vertically upright.
In the beginning, we simultaneously push some of the dominoes either to the left or to the right.

After each second, each domino that is falling to the left pushes the adjacent domino on the left.

Similarly, the dominoes falling to the right push their adjacent dominoes standing on the right.

When a vertical domino has dominoes falling on it from both sides, it stays still due to the balance of the forces.

For the purposes of this question, we will consider that a falling domino expends no additional force to a falling or already fallen domino.

Given a string “S” representing the initial state. S[i] = 'L', if the i-th domino has been pushed to the left; S[i] = 'R', if the i-th domino has been pushed to the right; S[i] = '.', if the i-th domino has not been pushed.
Return a string representing the final state.

Example 1:
Input: ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."

Example 2:
Input: "RR.L" Output: "RR.L" Explanation: The first domino expends no additional force on the second domino.

Note:
0 <= N <= 10^5
String dominoes contains only 'L', 'R' and '.'

My Solution(100ms 28.8MB)

public class Solution {
public string PushDominoes (string dominoes) {
var sb = new StringBuilder (dominoes);
for (int i = 0; i < sb.Length; i++) {
if (sb[i] == '.') {
continue;
} else if (sb[i] == 'L') {
for (int j = i - 1; j > -1; j--) {
if (sb[j] == '.') {
sb[j] = 'L';
}
else {
break;
}
}
} else {
int j = i;
while (j < sb.Length && dominoes[j] != 'L') {
if (sb[j] == 'R') {
for (int k = i; k < j; k++)
{
sb[k] = 'R';
}
i = j;
}
j++;
}
//No L til the end
if (j == sb.Length && dominoes[j - 1] != 'L') {
for (int k = i; k < sb.Length; k++) {
sb[k] = 'R';
}
break;
} else {
int remainder = (i + j) % 2;
int step = 0;
if (remainder == 1) {
//All change
step = (j - i) / 2;
} else {
step = (j - i) / 2 - 1;
}

for (int k = i + 1; k <= i + step; k++) {
sb[k] = 'R';
}
for (int l = j - 1; l >= j - step; l--) {
sb[l] = 'L';
}

//Set cursor to current position;
i = j;
}
}
}
return sb.ToString ();
}
}

No.1 Solution(92ms)

public class Solution {
public string PushDominoes(string dominoes)
{
char[] res = dominoes.ToCharArray();

int lastSeenL = -1, lastSeenR = -1;

for (int i = 0; i <= dominoes.Length; i++)
{
if (i == res.Length || res[i] == 'R')
{
if (lastSeenR > lastSeenL)
{
while (lastSeenR < i)
{
res[lastSeenR++] = 'R';
}
}
lastSeenR = i;
}
else if (res[i] == 'L')
{
if (lastSeenL > lastSeenR || (lastSeenR == -1 && lastSeenL == -1))
{
while (++lastSeenL < i)
{
res[lastSeenL] = 'L';
}
lastSeenL = i;
}
else
{
lastSeenL = i;
int low = lastSeenR + 1;
int high = lastSeenL - 1;
while (low < high)
{
res[low++] = 'R';
res[high--] = 'L';
}
}
}
}

return new String(res);
}
}

Things to improve

Compare to the fastest solution, my code has too many loops. It’s not efficient enough. However, the fastest code used more memory.

<h1>19. Remove Nth Node From End of List</h1>

Given a linked list, remove the n-th node from the end of list and return its head.

Example:
Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5.

Given a linked list, remove the n-th node from the end of list and return its head.

Example:
Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.

Could you do this in one pass?

My Solution(92ms 22.5MB)

/**
* public class ListNode {
*     public int val;
*     public ListNode next;
*     public ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode RemoveNthFromEnd(ListNode head, int n) {
ListNode ret = new ListNode(0);
int length = 0;
while(temp != null)
{
temp = temp.next;
length += 1;
}
length -= n;
if (length == 0)
{
{
return null;
}
else
{
}
}
else
{
for(int i = 0; i < length - 1; i++)
{
temp = temp.next;
}
temp.next = temp.next.next;
}
return ret.next;
}
}

No.1 Solution(88ms)

/**
* public class ListNode {
*     public int val;
*     public ListNode next;
*     public ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode RemoveNthFromEnd(ListNode head, int n) {

ListNode preDeleted;
ListNode dummy=new ListNode(0);
preDeleted=dummy;

for(int index=0;index<n;index++)
{
return null;

}

{
preDeleted=preDeleted.next;
}

preDeleted.next=preDeleted.next.next;

return dummy.next;
}
}

Things to improve

I should handle null value early in the first loop to increase speed

<h1>902. Numbers At Most N Given Digit Set</h1>

We have a sorted set of digits D, a non-empty subset of {‘1′,’2′,’3′,’4′,’5′,’6′,’7′,’8′,’9’}. (Note that ‘0’ is not included.)

Now, we write numbers using these digits, using each digit as many times as we want. For example, if D = {‘1′,’3′,’5′}, we may write numbers such as ’13’, ‘551’, ‘1351315’.

Return the number of positive integers that can be written (using the digits of D) that are less than or equal to N.

We have a sorted set of digits D, a non-empty subset of {‘1′,’2′,’3′,’4′,’5′,’6′,’7′,’8′,’9’}. (Note that ‘0’ is not included.)

Now, we write numbers using these digits, using each digit as many times as we want. For example, if D = {‘1′,’3′,’5′}, we may write numbers such as ’13’, ‘551’, ‘1351315’.

Return the number of positive integers that can be written (using the digits of D) that are less than or equal to N.

Example 1:
Input: D = ["1","3","5","7"], N = 100 Output: 20 Explanation: The 20 numbers that can be written are: 1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.
Example 2:

Input: D = ["1","4","9"], N = 1000000000 Output: 29523 Explanation: We can write 3 one digit numbers, 9 two digit numbers, 27 three digit numbers, 81 four digit numbers, 243 five digit numbers, 729 six digit numbers, 2187 seven digit numbers, 6561 eight digit numbers, and 19683 nine digit numbers. In total, this is 29523 integers that can be written using the digits of D.
Note:
1. D is a subset of digits '1'-'9' in sorted order.
2. 1 <= N <= 10^9

My Solution(88ms 22.3MB)

public class Solution {
public int AtMostNGivenDigitSet (string[] D, int N) {
int ret = 0;
bool donotIgnoreMatch = true;
bool currentMatchCheck = false;

// Convert D string[] to int[]
int[] newD = new int[D.Length];
for (int i = 0; i < D.Length; i++) {
newD[i] = int.Parse (D[i]);
}

//Convert int N to string and get Length;
string NString = N.ToString ();
int NLength = NString.Length;
for (int i = 0; i < NLength; i++) {
int num = int.Parse (NString[i].ToString ());
int availableDigit = 0;
if (donotIgnoreMatch) {
currentMatchCheck = false;
foreach (int d in newD) {
if (d < num) {
availableDigit += 1;
} else if (d == num) {
availableDigit += 1;
currentMatchCheck = true;
} else {
break;
}
}
donotIgnoreMatch = currentMatchCheck;
} else {
availableDigit = newD.Length;
}

if (i == 0 && availableDigit == 0) {
continue;
}

// Calculate posibility in current digit
ret += availableDigit * (int) Math.Pow (newD.Length, NLength - i - 1);

}
return ret;
}
}

No.1 Solution(88ms)

public class Solution {
public int AtMostNGivenDigitSet(string[] D, int N) {
string s = N.ToString();
int NLength = s.Length;
int L = D.Length;

int res = 0;

for (int i = 1; i < NLength; ++i)
res += (int)Math.Pow(L, i);

for(int i = 0; i<s.Length; ++i)
{
char curCh = s[i];
int curLength = NLength - i - 1;

bool meetEqual = false;
for(int j = 0; j<D.Length; ++j)
{
if (D[j][0] < curCh)
res += (int)Math.Pow(L, curLength);
else if (D[j][0] == curCh)
{
meetEqual = true;
break;
}
}

if (!meetEqual) return res;
}

return res + 1;
}
}

Things to improve

Even the speed is the same, the memory usage is something I should pay more attention on. Since we are not reach enough to get TB of memory.