Monthly Archives: July 2017

hihoCoder 1543-SCI表示法

hihoCoder 1543-SCI表示法

#1543 : SCI表示法

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

每一个正整数 N 都能表示成若干个连续正整数的和,例如10可以表示成1+2+3+4,15可以表示成4+5+6,8可以表示成8本身。我们称这种表示方法为SCI(Sum of Consecutive Integers)表示法。 小Hi发现一个整数可能有很多种SCI表示,例如15可以表示成1+2+3+4+5,4+5+6,7+8以及15本身。小Hi想知道N的所有SCI表示中,最多能包含多少个连续正整数。例如1+2+3+4+5是15包含正整数最多的表示。

输入

第一行一个整数 T,代表测试数据的组数。 以下 T 行每行一个正整数N。 对于30%的数据,1 ≤ N ≤ 1000 对于80%的数据,1 ≤ N ≤ 100000 对于100%的数据,1 ≤ T ≤ 10,1 ≤ N ≤ 1000000000

输出

对于每组数据输出N的SCI表示最多能包含多少个整数。
样例输入
2
15
8
样例输出
5
1

每一个正整数都可以表示成一串连续正整数的和,比如15=1+2+3+4+5,8=8(8也是一串连续正整数的和,只不过该串长度为1罢了:))。给定一个正整数N,问N最长能由多少个连续的正整数的和表示。 要使连续串的长度越长,则这些数越小越好。我们可以用滑动窗口的方法,设[i,j]的累加和为sum,则当sum>n时,++i;当sum<n时,++j;当sum==n时,len=j-i+1,更新最大长度。当j>n时循环终止。 完整代码如下: [cpp] #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; } [/cpp] 无奈,提交后TLE,只过了80%的数据。 实在想不出哪里还可以优化了,网上搜库,发现是记录A109814,但是没有递推公式,OEIS上给出的MAPLE程序也需要现算,试了一下,还是TLE。 后来请教某大神,发现一个巧妙的优化方法。如果从1加到i的累加和是sum,如果sum<n,令left=n-sum,如果left是i的正数倍,则从1~i这i个数,每个数都加上left/i,得到的新序列也是连续的,且和正好是sum+(left/i)*i=n,所以我们得到一个长度为i的连续和是n。 举个例子,当n=14时,遍历i,当i=4时,sum=1+2+3+4=10,剩余差值为left=n-sum=4,4%i=0,此时,给每个数加上left/i=1,就变成了2+3+4+5=14=n。 所以,我们只是从1开始遍历,知道累加和大于n,并没有从2开始重新遍历,这种方法需要的遍历数其实是很少的。 完整代码如下: [cpp] #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; } [/cpp] 本代码提交AC,用时10MS。]]>

hihoCoder 1542-无根数变有根树

hihoCoder 1542-无根数变有根树

#1542 : 无根数变有根树

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

给定一棵包含 N 个节点的无根树,小Hi想知道如果指定其中某个节点 K 为根,那么每个节点的父节点是谁?

输入

第一行包含一个整数 N 和 K。1 ≤ N ≤ 1000, 1 ≤ K ≤ N。 以下N-1行每行包含两个整数 a 和 b,代表ab之间存在一条边。 1 ≤ ab ≤ N。 输入保证是一棵树。

输出

输出一行包含 N 个整数,分别代表1~N的父节点的编号。对于 K 的父节点输出0。
样例输入
5 4
1 2
3 1
4 3
5 1
样例输出
3 1 4 0 1

给定一个无根树(其实就是DAG),如果以该树的某个顶点K为根,要求输出每个节点的父节点。 简单题,以K为根,进行DFS,遍历过程中记录每个节点的父节点就好了。完整代码如下: [cpp] #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; } [/cpp] 本代码提交AC,用时42MS。]]>

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"
Output: "Radiant"
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].

Dota2中有两个党派,分别是Radiant和Dire,分别用R和D表示。给定一个长度为n的字符串s,表示n个人,如果s[i]=’R’,表示第i个人是Radiant党的人;如果s[i]=’D’,表示第i个人是Dire党的人。 投票过程是从1~n不断重复的,每个人可以禁止任何一个其他人投票。如果某个人投票之后,剩下的人都是同一个党派的,则该党派胜利。问最终是哪个党派的人胜利。 使用贪心的原则,因为是round-based的投票方式,为了获胜,第i个人肯定是禁止其后的第一个非本党人员投票。比如序列DRDRR: 第一个D如果杀其后的第一个R:
  1. DXDRR
  2. DXDXR
  3. XXDXR
  4. XXDXX
Dire胜利;第一个D如果杀其后的第二个R:
  1. DRDXR
  2. DRXXR
  3. XRXXR
Radiant胜利。 这其实很好理解,因为是round-based的投票方式,对于D来说,他必须首先把其后的第一个R杀掉,要不然很快就会轮到这个R杀己方人员了。 round-based的方式是用%n的方式实现,代码如下: [cpp] 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"; } }; [/cpp] 本代码提交AC,用时752MS。]]>

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: 粘贴
问通过n次按键操作,最多可以打印出多少个字符。 稍微分析一下,增加字符比较快的方法是用Ctrl-V,连带着需要Ctrl-C和Ctrl-A的配合,所以要想快速增加字符,必须要以Ctrl-A, Ctrl-C, Ctrl-V结尾,这就需要3个操作。当n比较小时,这3个操作相对来说比较耗时,通过分析可知,当N<=6时,直接用N次Print(A)操作能得到最多的字符。 假设dp[i]表示使用i次操作能得到的最多字符,显然dp[i]=i,当i<=6时。 当i>6时,我们可以考虑用Ctrl-A, Ctrl-C, Ctrl-V,所以结尾我们至少要空出3个操作来使用技能,也就是我们最多只能在i-3的地方开始释放Ctrl-A, Ctrl-C, Ctrl-V技能,假设释放技能的位置是b,则b<=i-3;下界是我们可以在一开始只有一个字符时使用技能,即b>=1。所以我们遍历[1,i-3]的地方释放技能,则我们可以有i-b-2个Ctrl-V结尾,再加上释放技能的位置已经有一个dp[b]了,所以总字符数是dp[b]*(i-b-1)。使用贪心策略求最大值。 完整代码如下: [cpp] 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]; } }; [/cpp] 本代码提交AC,用时0MS。]]>

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].

一个记事本中原本只有一个字符A,每次可以做两种操作中的一种,分别是全选和粘贴。问要得到n个字符A,至少需要经过多少次操作。 这一题我一开始想到用BFS来做,两种操作相当于两条搜索路径,所以很容易能写出BFS的代码: [cpp] 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); } } } }; [/cpp] 预料到了,本代码提交TLE。 搜索会超时的,用DP一般都不会超时。设dp[i]表示要得到i个字符A,至少需要的操作数。显然,dp[1]=0。 假设已经求到了dp[1,…,i-1],现在要求dp[i]。要得到i个字符,最多的操作数是i,即先复制一个A,然后粘贴i-1次,总共需要i次操作。比较快的方法是,如果i是偶数,则可以从i/2个字符开始,全选粘贴就能得到i个字符。 所以我们遍历i前面的所有j,如果i能整除j,则可以全选j,然后粘贴i/j-1次得到i个字符,即操作数是1+(i/j-1)=i/j,当然还需要加上到达i的操作数,所以dp[j]=dp[i]+i/j。 完整代码如下: [cpp] 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]; } }; [/cpp] 本代码提交AC,用时79MS。 还有一种解法类似于素数筛法,我们首先知道dp[1]=0,如果我们对1个字符先全选,然后不停粘贴,则能得到2,3,4,…个字符,且操作数是2,3,4,…;下一次,我们知道dp[2]=2,如果我们对2个字符全选,然后不停粘贴,则能得到4,6,8,…个字符,且操作数是4,5,6,…。每一轮我们都只保留最小操作数。最终筛完之后,就是全局最优结果了。 完整代码如下: [cpp] 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]; } }; [/cpp] 本代码提交AC,用时3MS,速度飞快,因为越到后面,循环倍数越少。]]>

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.
给定一棵二叉树,要求找出其中的重复子树,每组重复子树输出其中一个子树即可。 去重最好的办法就是hash,所以思想是把每个子树hash到一个unordered_map中,如果有多个子树hash到同一个桶,则出现了重复。 所以问题的关键是怎样对一个子树hash。我们可以把一棵子树表示成 (left_hash, root, right_hash),其中left_hash和right_hash分别是左子树和右子树的hash字符串,root表示当前根节点的hash字符串。所以这是一个递归定义。规定空节点的hash值为空串””。 根据子树hash的定义,叶子节点的hash值是(“”,val,””)。求解子树hash值的过程可以用中序遍历,左根右。为什么子树hash中需要逗号和括号呢,就是为了保证不同严格区分不同的子树,因为单纯的中序遍历是无法区分某些子树的,比如下面的两个子树,中序遍历结果都是2,1,无法区分;但是用本文的hash方法,得到的hash值分别是(2,1,)和(,2,1),这两个字符串是有区别的。
  1
 /
2
 2
  \
   1
在DFS的过程中,把每个子树的hash值记录到一个unordered_map中,然后遍历unordered_map,如果该桶放了多个子树,则取出其中一个即可。 完整代码如下: [cpp] 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; } }; [/cpp] 本代码提交AC,用时52MS。]]>

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

给定一个词典和一个句子,词典是一系列的词根,要求把句子中的每个词替换成其最短词根(如果有词根的话)。 简单题,明显是Trie树的应用。首先把词典中的所有词根建一个Trie树,然后对句子中的每个单词,去Trie树中查找,返回最先找到的词根(也就是最短的词根);如果该词不在Trie树中,则说明不存在词根,直接用原来的单词。 完整代码如下: [cpp] 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); } }; [/cpp] 本代码提交AC,用时98MS。]]>

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.

给定一个字符串,问该字符串中有多少个回文子串。 暴力解法就是枚举每个子串,判断子串是否是回文串。判断一个字符串是否是回文串,可以用首尾指针法,也可以用中心扩展法,方法很多,需要O(n)时间,所以暴力总时间是O(n^3)。 稍微高效一点的方法是,不枚举子串,直接对每个字符用中心扩展法,请看讨论区代码。 我的解法是O(n^2)的DP方法,dp[i][j]表示子串[i,j]是否是回文串。首先对于长度为1的子串dp[i][i]=1肯定都是回文串;求dp[i][j]时,如果s[i]==s[j]且dp[i+1][j-1]是回文串,则dp[i][j]=1也是回文串。 最后统计一下dp数组中有多少个1就有多少个回文子串。 代码如下: [cpp] 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; } }; [/cpp] 本代码提交AC,用时12MS。]]>

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].

如果两个数对(a,b)和(c,d)满足b<c,则(c,d)可以跟在(a,b)的后面。给定一系列数对(s,t),问从这些数对中最多能取出多少个数对满足连续满足这种条件。 解法1,使用DP。首先对所有数对(x,y)先按x排序,x相同再按y排序。然后遍历数对,对于每个数对,有两种选择,不要或者要,对应dp[i][0]和dp[i][1],表示到i时能选出来的最多的满足条件的数对。 则dp[i][0]=max(dp[i-1][0], dp[i-1][1]),因为第i个数对不选,所以肯定等于前i-1个能选出来的最大数对,也就是max(dp[i-1][0], dp[i-1][1])。 如果第i个数对选,则要往前找到一个和i不冲突的数对j,接在j的后面,所以dp[i][1]=dp[j][1]+1。 代码如下: [cpp] 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; } }; [/cpp] 本代码提交AC,用时49MS。 我隐隐觉得这种解法有问题,就是在求dp[i][1]的时候,应该要找i前面所有和i不冲突的j,求max,即dp[i][1]=max(dp[j][1]+1)。 所以解法2是无懈可击的DP解法。设dp[i]表示以数对i结尾能得到的最长的链式数对,则初始的时候,所有dp[i]=1。然后对于第i个数对,遍历i前面所有数对j,只要i和j能够链起来,则求dp[i]=max(dp[j]+1)。时间复杂度$$O(n^2)$$,代码如下: [cpp] 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; } }; [/cpp] 本代码提交AC,用时122MS。 解法3,首先还是对所有数对排序,然后把这题看成类似于求最长上升子序列。即设dp[k]=构成链条长度为k时最小的结束时间。那么来了一个数对之后,如果该数对的开始时间大于dp末尾的结束时间,则说明该数对可以追加到dp中,链条长度加1,dp[k+1]=该数对的结束时间。否则,如果该数对的开始时间不大于dp末尾的结束时间,则需要像LIS一样,把该数对插入到dp中,因为dp是排好序的,所以二分插入即可。 该思路请参考:https://discuss.leetcode.com/topic/96814/python-straightforward-with-explanation-n-log-n/2。比较有意思的是,正如第一个评论人所说,因为提前对数对按结束时间排序了,所以后面的数对肯定是大于等于dp末尾的数对的,所以新来的数对只可能追加到dp的末尾,不可能插入到dp的其他位置,所以就可以省略二分插入的过程。完整代码简洁如下: [cpp] 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; } }; [/cpp] 本代码提交AC,用时45MS。 这个题可以把每个数对看成一个活动的开始和结束时间,把问题转换为从所有活动中选出尽量多的不重叠的活动,求最多的活动个数。活动选择问题可以用贪心求解,详细介绍和证明请看维基百科。]]>

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.

一个大小为n的数组,本来包含1~n这n个数,但是某个数x“突变”成y了,这就导致数组中丢了x,而y重复出现了两次,现在要找出丢掉的x和重复的y。 简单题,首先用hash可以找到重复的y,然后根据数学关系可以找到x,本来1~n的和是S=n*(n+1)/2,设现在的和是T,则有x=y-T+S。 代码如下: [cpp] 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; } }; [/cpp] 本代码提交AC,用时59MS。 还有一种空间复杂度O(1)的方法,不过需要改变原有数组。 因为数组元素是1~n的,所以遍历数组,把数值-1当作下标访问数组,使该处的元素变为原来的相反数,如果遇到某个数y-1访问的那个数是负数,说明y重复了,之前有一个y把y-1处的数变成了负数。 遍历完一遍之后,丢失的那个数x指向的x-1处的数应该是正数,因为x丢掉了,没有经过上面的过程,所以再遍历一遍可以找到x。 整个过程不需要借助额外的空间,代码如下: [cpp] 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; } }; [/cpp] 本代码提交AC,用时36MS。]]>