こんにちは。最近やっと春休みに入って少し一息ついています。１週間だけなのでほんとひと息と言う感じですが。。

# 49. lineEncoding

Given a string, return its encoding defined as follows:

First, the string is divided into the least possible number of disjoint substrings consisting of identical characters
for example, "aabbbc" is divided into ["aa", "bbb", "c"]
Next, each substring with length greater than one is replaced with a concatenation of its length and the repeating character
for example, substring "bbb" is replaced by "3b"
Finally, all the new strings are concatenated together in the same order and a new string is returned.

Example:
For s = "aabbbc", the output should be
lineEncoding(s) = "2a3bc".

## 自分の解答

とてもながい(白目)

```std::string lineEncoding(std::string s) {
int c = 1, p = 0;
std::string ret = "";
for (int i = 1; i < s.size(); i++){
if (s[p] == s[i]) c++;
else {
if (c > 1) ret += std::to_string(c);
ret += s[p];
p = i;
c = 1;
}
}
if (c > 1) ret += std::to_string(c);
ret += s[p];

return ret;
}
```

## 別解

fyzixさんより。条件演算子のところ、""の後にsが続いてるのは一体どうして。。。？

```std::string r, lineEncoding(std::string s) {
for (auto i = begin(s), j = i; i != end(s); i = j) {
while (*j == *i) ++j;
r.append(j-i>1 ? to_string(j-i) : ""s).push_back(*i);
}
return r;
}
```

# 50. chessKnight

Given a position of a knight on the standard chessboard, find the number of different moves the knight can perform.

## 自分の解答

```int chessKnight(std::string cell) {
int c = 0;
c += cell[0] < 'h' && cell[1] < '7';
c += cell[0] < 'g' && cell[1] < '8';
c += cell[0] < 'g' && cell[1] > '1';
c += cell[0] < 'h' && cell[1] > '2';
c += cell[0] > 'a' && cell[1] > '2';
c += cell[0] > 'b' && cell[1] > '1';
c += cell[0] > 'b' && cell[1] < '8';
c += cell[0] > 'a' && cell[1] < '7';
return c;
}
```

## 別解１

sir_ementalerさんより。

```bool valid(int a, int b) {
return a >= 0 && a < 8 && b >= 0 && b < 8;
}
int chessKnight(std::string cell) {
int a = cell.front() - 'a', b = cell.back() - '1';
return
+ valid(a - 2, b - 1)
+ valid(a - 2, b + 1)
+ valid(a + 2, b - 1)
+ valid(a + 2, b + 1)
+ valid(a - 1, b - 2)
+ valid(a - 1, b + 2)
+ valid(a + 1, b - 2)
+ valid(a + 1, b + 2)
;
}
```

## 別解２

yasharさんより。

```int chessKnight(std::string c) {
int ans = 0;
for(int i = -2; i < 3; ++i)
for(int j = -2; j < 3; ++j)
{
if(abs(i)+abs(j)==3)
ans += c[0]+i>='a' && c[0]+i<='h' && c[1]+j>='1' && c[1]+j<='8';
}
return ans;
}
```

# 51. deleteDigit

Given some integer, find the maximal number you can obtain by deleting exactly one digit of the given number.

Example:
For n = 152, the output should be
deleteDigit(n) = 52;
For n = 1001, the output should be
deleteDigit(n) = 101.

## 自分の解答

(例えば deleteDigit(32512) = 3512)

```int deleteDigit(int n) {
string s = to_string(n);
for (int i = 1; i < s.size(); i++)
if (s[i - 1] < s[i]) {s.erase(s.begin() + i - 1); return stoi(s);}
s.erase(s.end() - 1);
return stoi(s);
}
```

それと、最後のs.eraseは-1しないとうまくいかないです。s.end()の戻り値がstringの末尾の次を指すiteratorなので。

## 別解１

thienbuiさんより。大した場合の数じゃないし一つ一つ数字を消して見るのもありでした。が、こんな消し方があるんですねびっくり。

```int deleteDigit(int n) {
int ans = 0;
for(int d=1;d <= n; d*=10){
int tmp = n%d + ((n/d)/10)*d;
ans = max(ans,tmp);
}
return ans;
}
```

## 別解２

le_d5さんより。僕と似てるけどもっとシンプル。

```int deleteDigit(int n) {
std::string digitStr = to_string(n);
int index = 0;
for(; index < digitStr.size()-1; index++)
{
if( digitStr[index] < digitStr[index+1]  ) break;
}
return stoi( digitStr.substr(0,index) + digitStr.substr(index+1) );
}
```

# 52. longestWord

Define a word as a sequence of consecutive English letters. Find the longest word from the given string.

Example:

## 自分の解答

```std::string longestWord(std::string text) {
std::string ret = "";
for (int i = 0; i < text.size();) {
int c = 0;
while (isalpha(text[i + c])){c++;}
ret = ret.size() > c ? ret : text.substr(i, c);
c == 0 ? i++ : i += c;
}
return ret;
}
```

## 別解

sir_ementalerさんより。またregexだ。。。 正規表現に関してはあとでしっかり勉強する機会設けよう_:(´ཀ`」 ∠):

```std::string longestWord(std::string text) {
std::regex expr("[A-Za-z]+");
std::sregex_iterator it(text.begin(), text.end(), expr), end;
return std::max_element(it, end, [](const std::smatch& a, const std::smatch& b) {
return a.length() < b.length();
})->str();
}
```

# 53. Valid Time

Check if the given string is a correct time representation of the 24-hour clock.

Example:
For time = "13:58", the output should be
validTime(time) = true;
For time = "25:51", the output should be
validTime(time) = false;
For time = "02:76", the output should be
validTime(time) = false.

## 自分の解答

```bool validTime(std::string time) {
int a, b;
sscanf(time.c_str(),"%d:%d", &a,&b);
return 0<=a && a<24 && 0<=b && b<60;
}
```

## 別解

```bool validTime(std::string time) {
return std::regex_match(time, std::regex("(?:[01]\\d|2[0-3]):[0-5]\\d"));
}
```

# 54. sumUpNumbers

CodeMaster has just returned from shopping. He scanned the check of the items he bought and gave the resulting string to Ratiorg to figure out the total number of purchased items. Since Ratiorg is a bot he is definitely going to automate it, so he needs a program that sums up all the numbers which appear in the given input.

Help Ratiorg by writing a function that returns the sum of numbers that appear in the given inputString.

Example:
For inputString = "2 apples, 12 oranges", the output should be
sumUpNumbers(inputString) = 14.

## 自分の解答

うーーんstringの扱いが特に苦手。

```int sumUpNumbers(std::string s) {
int ret = 0;
for (int i = 0; i < s.size();) {
int c = 0;
while (isdigit(s[i + c])) c++;
if(c == 0) {i ++; continue;}
string sub = s.substr(i, c);
ret += stoi(sub);
i += c;
}
return ret;
}
```

## 別解１

yasharさんより。４行目はなんのためなのか🤔

```int sumUpNumbers(std::string s) {
int cur = 0;
int sum = 0;
s.push_back('@');
for(char c:s)
if(c>='0'&&c<='9')
cur = cur*10 + c-'0';
else
sum += cur, cur = 0;
return sum;
}
```

## 別解２

sir_ementalerさんより。またregexか

```int sumUpNumbers(std::string inputString) {
std::regex expr("\\d+");
std::sregex_iterator it(inputString.begin(), inputString.end(), expr), end;
return std::accumulate(it, end, 0, [](int sum, const std::smatch& s) {
return sum + std::stoi(s.str());
});
}
```

# 55. Different Squares

Given a rectangular matrix containing only digits, calculate the number of different 2 × 2 squares in it.

Example:
For
matrix = [[1, 2, 1],
[2, 2, 2],
[2, 2, 2],
[1, 2, 3],
[2, 2, 1]]
the output should be
differentSquares(matrix) = 6.

## 自分の解答

```int differentSquares(std::vector<std::vector<int>> m) {
if (m.size() < 2 || m.front().size() < 2) return 0;
vector<vector<vector<int>>> vvv(0, vector<vector<int>>(2, vector<int>(2, 0)));
for (int i = 1; i < m.size(); i++) {
vector<vector<int>> t;
for (int j = 1; j < m.front().size(); j++) {
t = vector<vector<int>>{{m[i-1][j-1], m[i-1][j]}, {m[i][j-1], m[i][j]}};
bool found = false;
for (vector<vector<int>> vv: vvv) if (vv == t) {found = true; break;}
if (!found) vvv.push_back(t);
}
}
return vvv.size();
}
```

## 別解

yasharさんより。そうじゃんset使えば自分で被りチェックする必要もなかった！！思い出せなかったの悔しい(´；ω；`)

```int differentSquares(std::vector<std::vector<int>> m) {
set<int> se;
for(int i = 1; i < m.size(); ++i)
for(int j = 1; j < m[0].size(); ++j)
se.insert(m[i][j]+10*m[i-1][j]+100*m[i][j-1]+1000*m[i-1][j-1]);
return se.size();
}
```

### std::set

C++ 順序付集合 std::set 入門

# 56. digitsProduct

Given an integer product, find the smallest positive (i.e. greater than 0) integer the product of whose digits is equal to product. If there is no such integer, return -1 instead.

Example:
For product = 12, the output should be
digitsProduct(product) = 26;
For product = 19, the output should be
digitsProduct(product) = -1.

## 自分の解答

pの一桁の約数を大きいものから、retの小さい桁から大きい桁へと順に追加していけば良いと考えました。

```int digitsProduct(int p) {
if (p == 0) return 10;
if (p > 0 && p < 10) return p;
int ret = 0;
for (int i = 9; i > 1; i--) {
while (p % i == 0) {
if(!ret) ret = i;
else ret += i * pow(10, int(log10(ret)+1));
p /= i;
}
}
if (p != 1) return -1;
return ret;
}
```

## 別解

yasharさんより。コードは僕のよりずっと好きりしていて見やすい。でもこれだとループの回数結構多くならないのかな。。。？

```int digitsProduct(int product) {
for(int i = 1; i < 100000; ++i)
{
int p=1, d = i;
while(d)
{
p *= d%10;
d /= 10;
}
if(p==product)
return i;
}
return -1;
}
```

# 57. File Naming

You are given an array of desired filenames in the order of their creation. Since two files cannot have equal names, the one which comes later will have an addition to its name in a form of (k), where k is the smallest positive integer such that the obtained name is not used yet.

Return an array of names that will be given to the files.

Example:
For names = ["doc", "doc", "image", "doc(1)", "doc"], the output should be
fileNaming(names) = ["doc", "doc(1)", "image", "doc(1)(1)", "doc(2)"].

## 自分の解答

うわなにこれって思いながらコード書いたら意外と解けた。

```std::vector<std::string> fileNaming(std::vector<std::string> n) {
set<string> ms;
for (string &s: n){
int c = 1;
string t = s;
while (ms.find(t) != ms.end())  t = s + "(" + to_string(c++) + ")";
ms.insert(t);
s = t;
}
return n;
}
```

# 58. messageFromBinaryCode

You are taking part in an Escape Room challenge designed specifically for programmers. In your efforts to find a clue, you've found a binary code written on the wall behind a vase, and realized that it must be an encrypted message. After some thought, your first guess is that each consecutive 8 bits of the code stand for the character with the corresponding extended ASCII code.

Assuming that your hunch is correct, decode the message.

Example:
For code = "010010000110010101101100011011000110111100100001", the output should be
messageFromBinaryCode(code) = "Hello!".

The first 8 characters of the code are 01001000, which is 72 in the binary numeral system. 72 stands for H in the ASCII-table, so the first letter is H.
Other letters can be obtained in the same manner.

## 自分の解答

```std::string messageFromBinaryCode(std::string code) {
string ret = "";
for (int i = 0; i < code.size(); i += 8) {
bitset<8> b(code.substr(i, 8));
ret += char(b.to_ulong());
}
return ret;
}
```

### std::bitset

The class template bitset represents a fixed-size sequence of N bits. Bitsets can be manipulated by standard logic operators and converted to and from strings and integers.

## 別解

yasharさんより。bitset使わなかった場合。

```std::string messageFromBinaryCode(std::string s) {
string ans = "";
for(int i = 0; i < s.size(); i += 8)
{
char d = 0;
for(int j = 0; j < 8; ++j)
d = d*2 + (s[i+j]=='1');
ans.push_back(d);
}
return ans;
}
```

# 59. spiralNumbers

Construct a square matrix with a size N × N containing integers from 1 to N * N in a spiral order, starting from top-left and in clockwise direction.

Example:
For n = 3, the output should be

spiralNumbers(n) =
[[1, 2, 3],
[8, 9, 4],
[7, 6, 5]]

## 自分の解答

ぐるぐるぐるぐるぐるぐる

```std::vector<std::vector<int>> spiralNumbers(int n) {
vector<vector<int>> ret(n, vector<int>(n, 0));
int c = 1, s = 0, e = n - 1;
while (c <= n * n) {
for (int lr = s; lr <= e; lr++) ret[s][lr] = c++;
for (int tb = s + 1; tb <= e; tb++) ret[tb][e] = c++;
for (int rl = e - 1; rl >= s; rl--) ret[e][rl] = c++;
for (int bt = e - 1; bt >= s + 1; bt--) ret[bt][s] = c++;
s++, e--;
}
return ret;
}
```

# 60.Sudoku

Sudoku is a number-placement puzzle. The objective is to fill a 9 × 9 grid with digits so that each column, each row, and each of the nine 3 × 3 sub-grids that compose the grid contains all of the digits from 1 to 9.

This algorithm should check if the given grid of numbers represents a correct solution to Sudoku.

## 自分の解答

```bool sudoku(std::vector<std::vector<int>> g) {
set<int> ms;
for (vector<int> v: g) {
ms = set<int>(v.begin(), v.end());
if (ms.size() != 9) return false;
ms.clear();
}
for (int i = 0; i < g.size(); i++) {
for (int j = 0; j < g[0].size(); j++)
ms.insert(g[j][i]);
if (ms.size() != 9) return false;
ms.clear();
}
for (int i = 0; i < g.size(); i += 3)
for (int j = 0; j < g[0].size(); j += 3) {
for (int r = 0; r < 3; r++)
for (int c = 0; c < 3; c++)
ms.insert(g[i + r][j+ c]);
if (ms.size() != 9) return false;
ms.clear();
}
return true;
}
```

## 別解

sir_ementalerさんより。久しぶりになにが起きてるのか全くわからなくて笑った。

```bool sudoku(std::vector<std::vector<int>> grid) {
for (int i = 0; i < 9; i++) {
int a = 0, b = 0, c = 0;
for (int j = 0; j < 9; j++) {
a ^= 1 << grid[i][j];
b ^= 1 << grid[j][i];
c ^= 1 << grid[i - i % 3 + j / 3][i % 3 * 3 + j % 3];
}
if (a != 1022 || b != 1022 || c != 1022)
return false;
}
return true;
}
```