hihoCoder 1543-SCI表示法

hihoCoder 1543-SCI表示法

输出

2
15
8

5
1

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>
#include<string>
#include<unordered_map>
#include<queue>
using namespace std;
typedef long long ll;
ll t, n;
int main() {
freopen("input.txt", "r", stdin);
scanf("%lld", &t);
while (t--) {
scanf("%lld", &n);
if (n == 1 || n == 2) {
printf("1\n");
} else {
ll i = 1, j = 2;
ll sum = i + j, ans = 0;
while (true) {
while (j <= n && sum < n) {
++j;
sum += j;
}
if (j > n)break;
while (i < j && sum > n) {
sum -= i;
++i;
}
if (sum == n) {
//printf("%d\n", j - i + 1);
ans = max(ans, j - i + 1);
break;
}
}
printf("%lld\n", ans);
}
}
return 0;
}


#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>
#include<string>
#include<unordered_map>
#include<queue>
using namespace std;
typedef long long ll;
ll t, n;
int main() {
freopen("input.txt", "r", stdin);
scanf("%lld", &t);
while (t--) {
scanf("%lld", &n);
if (n == 1 || n == 2) {
printf("1\n");
}
else {
ll ans = 1;
for (ll i = 1; i < n; ++i) {
ll sum = (1 + i)*i / 2;
if (sum > n)break;
ll left = sum - n;
if (left%i == 0) {
ans = max(ans, i);
}
}
printf("%lld\n", ans);
}
}
return 0;
}


hihoCoder 1542-无根数变有根树

hihoCoder 1542-无根数变有根树

输出

5 4
1 2
3 1
4 3
5 1

3 1 4 0 1

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>
#include<string>
#include<unordered_map>
#include<queue>
using namespace std;
const int kMaxN = 1005;
int n, k;
vector<int> parent(kMaxN, 0);
vector<vector<int>> graph(kMaxN, vector<int>(kMaxN, 0));
void DFS(int node, int pre) {
parent[node] = pre;
graph[node][pre] = 0;
graph[pre][node] = 0;
for (int i = 1; i <= n; ++i) {
if (graph[node][i] == 1) {
DFS(i, node);
}
}
graph[node][pre] = 1;
graph[pre][node] = 1;
}
int main() {
//freopen("input.txt", "r", stdin);
scanf("%d %d", &n, &k);
int a, b;
for (int i = 0; i < n - 1; ++i) {
scanf("%d %d", &a, &b);
graph[a][b] = 1;
graph[b][a] = 1;
}
DFS(k, 0);
for (int i = 1; i <= n; ++i)
printf("%d ", parent[i]);
return 0;
}


LeetCode Dota2 Senate

LeetCode Dota2 Senate
In the world of Dota2, there are two parties: the Radiant and the Dire.
The Dota2 senate consists of senators coming from two parties. Now the senate wants to make a decision about a change in the Dota2 game. The voting for this change is a round-based procedure. In each round, each senator can exercise one of the two rights:

1. Ban one senator's right:
A senator can make another senator lose all his rights in this and all the following rounds.
2. Announce the victory:
If this senator found the senators who still have rights to vote are all from the same party, he can announce the victory and make the decision about the change in the game.

Given a string representing each senator's party belonging. The character 'R' and 'D' represent the Radiant party and the Dire party respectively. Then if there are n senators, the size of the given string will be n.
The round-based procedure starts from the first senator to the last senator in the given order. This procedure will last until the end of voting. All the senators who have lost their rights will be skipped during the procedure.
Suppose every senator is smart enough and will play the best strategy for his own party, you need to predict which party will finally announce the victory and make the change in the Dota2 game. The output should be Radiant or Dire.
Example 1:

Input: "RD"
Explanation: The first senator comes from Radiant and he can just ban the next senator's right in the round 1.
And the second senator can't exercise any rights any more since his right has been banned.
And in the round 2, the first senator can just announce the victory since he is the only guy in the senate who can vote.


Example 2:

Input: "RDD"
Output: "Dire"
Explanation:
The first senator comes from Radiant and he can just ban the next senator's right in the round 1.
And the second senator can't exercise any rights anymore since his right has been banned.
And the third senator comes from Dire and he can ban the first senator's right in the round 1.
And in the round 2, the third senator can just announce the victory since he is the only guy in the senate who can vote.


Note:

1. The length of the given string will in the range [1, 10,000].

1. DXDRR
2. DXDXR
3. XXDXR
4. XXDXX

Dire胜利；第一个D如果杀其后的第二个R：

1. DRDXR
2. DRXXR
3. XRXXR

round-based的方式是用%n的方式实现，代码如下：

class Solution {
public:
string predictPartyVictory(string senate) {
int r_cnt = 0, d_cnt = 0, n = senate.size();
for (int i = 0; i < n; ++i) {
if (senate[i] == 'R')
++r_cnt;
else
++d_cnt;
}
int pos = 0;
while (r_cnt > 0 && d_cnt > 0) {
if (senate[pos] == 'X') {
pos = (pos + 1) % n;
continue;
}
int pos_next = (pos + 1) % n;
while (senate[pos_next] == senate[pos] || senate[pos_next] == 'X')
pos_next = (pos_next + 1) % n;
if (senate[pos_next] == 'R')
--r_cnt;
else
--d_cnt;
senate[pos_next] = 'X';
pos = (pos + 1) % n;
}
return r_cnt == 0 ? "Dire" : "Radiant";
}
};


LeetCode 4 Keys Keyboard

LeetCode 4 Keys Keyboard
Imagine you have a special keyboard with the following keys:
Key 1: (A): Prints one 'A' on screen.
Key 2: (Ctrl-A): Select the whole screen.
Key 3: (Ctrl-C): Copy selection to buffer.
Key 4: (Ctrl-V): Print buffer on screen appending it after what has already been printed.
Now, you can only press the keyboard for N times (with the above four keys), find out the maximum numbers of 'A' you can print on screen.
Example 1:

Input: N = 3
Output: 3
Explanation:
We can at most get 3 A's on screen by pressing following key sequence:
A, A, A


Example 2:

Input: N = 7
Output: 9
Explanation:
We can at most get 9 A's on screen by pressing following key sequence:
A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V


Note:

1. 1 <= N <= 50
2. Answers will be in the range of 32-bit signed integer.

• A: 打印一个字符A
• Ctrl-A: 全选
• Ctrl-C: 复制
• Ctrl-V: 粘贴

class Solution {
public:
int maxA(int N) {
if (N <= 6)return N;
vector<int> dp(N + 1, 0);
for (int i = 1; i <= 6; ++i)dp[i] = i;
for (int i = 7; i <= N; ++i) {
for (int b = i - 3; b >= 1; --b) {
dp[i] = max(dp[i], dp[b] + dp[b] * (i - b - 2));
}
}
return dp[N];
}
};


LeetCode 2 Keys Keyboard

LeetCode 2 Keys Keyboard
Initially on a notepad only one character 'A' is present. You can perform two operations on this notepad for each step:

1. Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
2. Paste: You can paste the characters which are copied last time.

Given a number n. You have to get exactly n 'A' on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n 'A'.
Example 1:

Input: 3
Output: 3
Explanation:
Intitally, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.


Note:

1. The n will be in the range [1, 1000].

class Solution {
private:
struct Node {
int presented_cnt_; // 现在有多少个字符
int copied_cnt_; // 剪切板中有多少个字符
int step_; // 走过多少步了
Node(int p, int c, int s) :presented_cnt_(p), copied_cnt_(c), step_(s) {};
};
public:
int minSteps(int n) {
queue<Node> q;
Node node(1, 0, 0);
q.push(node);
while (!q.empty()) {
Node cur = q.front();
q.pop();
if (cur.presented_cnt_ == n)
return cur.step_;
if (cur.presented_cnt_ > n)continue;
Node copy_node(cur.presented_cnt_, cur.presented_cnt_, cur.step_ + 1); // 全选
q.push(copy_node);
if (cur.copied_cnt_ != 0) { // 粘贴
Node paste_node(cur.presented_cnt_ + cur.copied_cnt_, cur.copied_cnt_, cur.step_ + 1);
q.push(paste_node);
}
}
}
};


class Solution {
public:
int minSteps(int n) {
vector<int> dp(n + 1, INT_MAX);
dp[1] = 0;
for (int i = 2; i <= n; ++i) {
dp[i] = i;
for (int j = i - 1; j >= 1; --j) {
if (i%j == 0) {
dp[i] = min(dp[i], dp[j] + i / j);
}
}
}
return dp[n];
}
};


class Solution {
public:
int minSteps(int n) {
vector<int> dp(n + 1, INT_MAX);
dp[1] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 2 * i, k = 2; j <= n; j += i, ++k) {
dp[j] = min(dp[j], dp[i] + k);
}
}
return dp[n];
}
};


LeetCode Find Duplicate Subtrees

LeetCode Find Duplicate Subtrees
Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them.
Two trees are duplicate if they have the same structure with same node values.
Example 1:

        1
/ \
2   3
/   / \
4   2   4
/
4


The following are two duplicate subtrees:

      2
/
4


and

    4


Therefore, you need to return above trees' root in the form of a list.

  1
/
2


 2
\
1

class Solution {
private:
string DFS(TreeNode* root, unordered_map<string, vector<TreeNode*>>& inorders) {
if (root == NULL)return "";
string left = DFS(root->left, inorders);
string right = DFS(root->right, inorders);
string cur = "(" + left + "," + to_string(root->val) + "," + right + ")";
inorders[cur].push_back(root);
return cur;
}
public:
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
unordered_map<string, vector<TreeNode*>> inorders;
DFS(root, inorders);
vector<TreeNode*> ans;
for (auto &it : inorders) {
if (it.second.size() > 1)
ans.push_back(it.second[0]);
}
return ans;
}
};


LeetCode Replace Words

LeetCode Replace Words

In English, we have a concept called root, which can be followed by some other words to form another longer word - let's call this word successor. For example, the root an, followed by other, which can form another word another.
Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the rootforming it. If a successor has many roots can form it, replace it with the root with the shortest length.
You need to output the sentence after the replacement.
Example 1:

Input: dict = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"


Note:

1. The input will only have lower-case letters.
2. 1 <= dict words number <= 1000
3. 1 <= sentence words number <= 1000
4. 1 <= root length <= 100
5. 1 <= sentence words length <= 1000

const int kMaxN = 26;
class Solution {
private:
struct Node {
bool is_word_;
vector<Node*> children_;
Node() :is_word_(false) {
for (int i = 0; i < kMaxN; ++i)
children_.push_back(NULL);
}
};
Node *root_;
void InsertWord(const string& word) {
Node *cur = root_;
for (const auto& c : word) {
int idx = c - 'a';
if (cur->children_[idx] == NULL)cur->children_[idx] = new Node();
cur = cur->children_[idx];
}
cur->is_word_ = true;
}
void ConstructTree(const vector<string>& dict) {
root_ = new Node();
for (const auto& w : dict) {
InsertWord(w);
}
}
string SearchTree(const string& word) {
Node *cur = root_;
string ans = "";
for (const auto& c : word) {
int idx = c - 'a';
if (cur->children_[idx] == NULL)return "";
cur = cur->children_[idx];
ans.push_back(c);
if (cur->is_word_)return ans;
}
return "";
}
public:
string replaceWords(vector<string>& dict, string sentence) {
ConstructTree(dict);
string ans = "";
int i = 0, n = sentence.size();
for (int j = 0; j <= n; ++j) {
if (j == n || sentence[j] == ' ') {
string successor = sentence.substr(i, j - i);
string root = SearchTree(successor);
if (root == "")
ans += successor + " ";
else
ans += root + " ";
i = j + 1;
}
}
return ans.substr(0, ans.size() - 1);
}
};


LeetCode Palindromic Substrings

LeetCode Palindromic Substrings
Given a string, your task is to count how many palindromic substrings in this string.
The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.
Example 1:

Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".


Example 2:

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".


Note:

1. The input string length won't exceed 1000.

class Solution {
public:
int countSubstrings(string s) {
int ans = 0, n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = 0; i < n; ++i) {
dp[i][i] = 1;
++ans;
}
for (int len = 2; len <= n; ++len) {
for (int i = 0; i < n; ++i) {
int j = i + len - 1;
if (j >= n)break;
if (s[i] == s[j] && (len == 2 || dp[i + 1][j - 1] == 1)) {
dp[i][j] = 1;
++ans;
}
}
}
return ans;
}
};


LeetCode Maximum Length of Pair Chain

LeetCode Maximum Length of Pair Chain
You are given n pairs of numbers. In every pair, the first number is always smaller than the second number.
Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion.
Given a set of pairs, find the length longest chain which can be formed. You needn't use up all the given pairs. You can select pairs in any order.
Example 1:

Input: [[1,2], [2,3], [3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4]


Note:

1. The number of given pairs will be in the range [1, 1000].

bool cmp(const vector<int>& p1, const vector<int>& p2) {
return p1[0] < p2[0] || (p1[0] == p2[0] && p1[1] < p2[1]);
}
class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(), pairs.end(), cmp);
int n = pairs.size();
vector<vector<int>> dp(n, vector<int>(2, 0));
dp[0][0] = 0;
dp[0][1] = 1;
int ans = 1;
for (int i = 1; i < n; ++i) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = 1;
int j = i - 1;
while (j >= 0 && pairs[i][0] <= pairs[j][1]) {
--j;
}
if (j >= 0) {
dp[i][1] = max(dp[i][1], dp[j][1] + 1);
}
ans = max(ans, dp[i][0]);
ans = max(ans, dp[i][1]);
}
return ans;
}
};


class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(), pairs.end(), [](const vector<int>& p1, const vector<int>& p2) {return p1[0] < p2[0] || (p1[0] == p2[0] && p1[1] < p2[1]); });
int n = pairs.size(), ans = 1;
vector<int> dp(n, 1);
for (int i = 1; i < n; ++i) {
for (int j = i - 1; j >= 0; --j) {
if (pairs[i][0] > pairs[j][1]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
ans = max(ans, dp[i]);
}
return ans;
}
};


class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(), pairs.end(), [](const vector<int>& p1, const vector<int>& p2) {return p1[1] < p2[1]; });
int ans = 0;
for (int i = 0, j = 0; j < pairs.size(); ++j) {
if (j == 0 || pairs[j][0] > pairs[i][1]) {
++ans;
i = j;
}
}
return ans;
}
};


LeetCode Set Mismatch

LeetCode Set Mismatch
The set S originally contains numbers from 1 to n. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetition of one number and loss of another number.
Given an array nums representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array.
Example 1:

Input: nums = [1,2,2,4]
Output: [2,3]


Note:

1. The given array size will in the range [2, 10000].
2. The given array's numbers won't have any order.

class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
vector<int> ans(2, 0);
unordered_set<int> hash;
int sum = 0, n = nums.size();
for (const auto& num : nums) {
if (hash.find(num) != hash.end())ans[0] = num;
hash.insert(num);
sum += num;
}
ans[1] = ans[0] - sum + n*(n + 1) / 2;
return ans;
}
};


class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
vector<int> ans(2, 0);
for (int i = 0; i < nums.size(); ++i) {
int idx = nums[i] < 0 ? -nums[i] : nums[i];
if (nums[idx - 1] < 0) {
ans[0] = idx;
} else {
nums[idx - 1] = -nums[idx - 1];
}
}
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] > 0) {
ans[1] = i + 1;
break;
}
}
return ans;
}
};