# leetcode_OJ WC74 解題心得

• Contest time: Mar 4, 2018

## PA. 794. Valid Tic-Tac-Toe State 觀察暴力題

• 思路：暴力＋情況邏輯特判。 題目規則所述為：
Players take turns placing characters into empty squares (" ").
The first player always places "X" characters, while the second player always places "O" characters.
"X" and "O" characters are always placed into empty squares, never filled ones.
The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal.
The game also ends if all squares are non-empty.
No more moves can be played if the game is over.

一定要是x先攻，並且有任一方獲勝後則不可以再下標記，獲勝的方法同傳統井字遊戲。 從邏輯來看，首先我們統計o的個數以及x的個數

if(xcnt==0 && ocnt==1)
{
return 0;
}
else if(xcnt>ocnt+1 || ocnt>xcnt+1)
{
return 0;
}
else if(ocnt > xcnt)
{
return 0;
}


//["XOX","O O","XOX"]
class Solution
{
public:
int xcnt,ocnt;
bool validTicTacToe(vector<string>& board)
{
xcnt=0;
ocnt=0;
for(int i=0;i<board.size();i++)
{
for(int j=0;j<board[i].size();j++)
{
if(board[i][j]=='O')
{
ocnt++;
}
else if(board[i][j]=='X')
{
xcnt++;
}
}
}
if(xcnt==0 && ocnt==1)
{
return 0;
}
else if(xcnt>ocnt+1 || ocnt>xcnt+1)
{
return 0;
}
else if(ocnt > xcnt)
{
return 0;
}
else if(!checkwin(board))
{
return 0;
}

return 1;
}
bool checkwin(vector<string>& board)
{
int win_cnt=0;
int xwin=0,owin=0;
for(int i=0;i<board.size();i++)
{
if(board[i][0]==board[i][1] && board[i][0]==board[i][2] && board[i][0]!=' ')
{
if(board[i][0]=='X')
{
xwin=1;
}
else
{
owin=1;
}
win_cnt++;
}
}
for(int i=0;i<3;i++)
{
if(board[0][i]==board[1][i] && board[0][i]==board[2][i] && board[0][i]!=' ')
{
if(board[0][i]=='X')
{
xwin=1;
}
else
{
owin=1;
}
win_cnt++;
}
}
if(board[0][0]==board[1][1]
&& board[0][0]==board[2][2] && board[0][0]!=' ')
{
if(board[0][0]=='X')
{
xwin=1;
}
else
{
owin=1;
}
win_cnt++;
}
if(board[0][2]==board[1][1]
&& board[0][2]==board[2][0] && board[0][2]!=' ')
{
if(board[0][2]=='X')
{
xwin=1;
}
else
{
owin=1;
}
win_cnt++;
}
if(win_cnt==0)
return 1;
else if(win_cnt==1)
{
if(xwin)
{
if(ocnt>=xcnt)
{
return 0;
}
else if(xcnt==ocnt+1)
{
return 1;
}
else
{
return 0;
}
}
else if(owin)
{
if(ocnt<xcnt)
{
return 0;
}
else if(xcnt==ocnt)
{
return 1;
}
else if(ocnt>xcnt)
{
return 0;
}
}

}
else
{
return 0;
}
}
};


## PB. 792. Number of Matching Subsequences a 是否為 b的子序列，經典字串問題

map優化過後AC如下

class Solution
{
public:
int numMatchingSubseq(string str, vector<string>& words)
{
int cnt = 0;
map<string,int> mymap;
for(int i=0 ;i<words.size();i++)
{
mymap[words[i]]++;
}
for(std::map<string,int>::iterator it=mymap.begin() ;it!=mymap.end();it++)
{
std::size_t fd = str.find(it->first);
cout<<it->first<<" , "<<it->second<<endl;
if(it->first.size()>str.size())
{
continue;
}
else if(fd != std::string::npos)
{
cnt+=it->second;
}
else if(issubseq(it->first, str, it->first.size(), str.size()))
{
cnt+=it->second;
}
}
return cnt;
}
bool issubseq(string str1, string str2, int len1, int len2)
{
int same_idx = 0;
for(int i=0;i<len2 && same_idx<len1;i++)
{
if(str1[same_idx] == str2[i])
same_idx++;
}
return (same_idx==len1);
}
};


## PC. 792. Number of Matching Subsequences 找規律推理題

#define FORI(n) for(int i = 0; i < n; ++ i)
class Solution
{
public:
int numSubarrayBoundedMax(vector<int>& arr, int low, int up)
{
int max_val = 0, can = 0, cnt = 0;
int pre_max_val = 0, dist = 0;
FORI(arr.size())
{
pre_max_val = arr[i];
max_val = arr[i];
dist = 0;
for(int j=i+1;j<arr.size();j++)
{
pre_max_val = max_val;
max_val = max(max_val, arr[j]);
if(max_val < low || max_val > up)
{
break;
}
dist = j - i;
}
if( pre_max_val >=low && pre_max_val <= up)
{
cnt += (dist == 0 ) ? 1 : dist + 1;
}
}
return cnt;
}
};


//algorithm and source credit to : https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/discuss/117612/C++-O(n)-solution-with-explanations

class Solution {
public:
int numSubarrayBoundedMax(vector<int>& A, int L, int R)
{
int res = 0, heads = 0, tails = 0;
for (int val : A)
{
if (L <= val && val <= R)
{
//而res變可以新增那個長度
tails = 0;
}
else if (val < L)
{
//舉例：L=32 R=69 今已經iterate，[55 36] 已經有三個了 在多一個5後，便可有[55] [36] [55,36] [55 36 55] [36 55]
tails++;
}
else
{
tails = 0;
}
}
return res;
}
};


32
69

# PD. 793. Preimage Size of Factorial Zeroes Function 高難度找mod規律數學題

class Solution {
public:
int preimageSizeFZF(int kin)
{
int cnt = 0, factorial = 0, zeros = 0, current_pow = 25;
while(1)
{
if(factorial ==  current_pow * 5)
{
cout<<" factorial is now "<<factorial<<" current_pow is now "<<current_pow<<endl;
current_pow*=5;
}
if(factorial % current_pow == 0 && factorial)
{
zeros += ((int)(log(factorial) / log(5)));
cout<<" factorial is of 25 multiple "<<factorial<<" zeros "<<zeros <<" add "<<((int)(log(factorial) / log(5)))<<endl;
}
else if(factorial % 5 ==0 && factorial)
{
cout<<" factorial not 25 "<<factorial<<endl;
zeros++;
}

if(zeros == kin)
{
cnt++;
}
else if(zeros > kin)
{
break;
}
cout<<" factorial "<<factorial<<" zeros "<<zeros<<endl;
factorial++;
}
return cnt;
}
//compare 2 casting, one is the original integer value of log and the other is the double type log, if they are equal of each other
//in double precision
//then this is correct one
bool is_powoffive(int real, int base)
{
int integer = (int)(log(real)/log(base));
double precised = (log(real)/log(base));
return integer == precised;
}
};