1. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]
提示：
? ?0 <= digits.length <= 4
? ?digits[i] 是范围 ['2', '9'] 的一个数字。
代码：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<string> str;
vector<string> ret;
string getStr( int x ) {
switch( x ) {
case 2: return "abc";
case 3: return "def";
case 4: return "ghi";
case 5: return "jkl";
case 6: return "mno";
case 7: return "pqrs";
case 8: return "tuv";
case 9: return "wxyz";
default: return "";
}
}
void dfs( string& ans, int k ) {
if ( k >= str.size() ) {
ret.push_back( ans );
return;
}
for ( auto& it : str[k] ) {
ans.push_back( it );
dfs(ans, k + 1);
ans.pop_back();
}
}
vector<string> letterCombinations(string digits) {
if ( !digits.size() ) return {};
for ( auto& it : digits )
str.push_back( getStr( it & 15 ) );
string ans = "";
dfs( ans, 0 );
return ret;
}
};
int main()
{
Solution s1;
string digits = "23";
for (auto comb : s1.letterCombinations(digits))
cout << comb << " ";
cout <<endl;
Solution s2;
digits = "";
for (auto comb : s2.letterCombinations(digits))
cout << comb << " ";
cout <<endl;
Solution s3;
digits = "2";
for (auto comb : s3.letterCombinations(digits))
cout << comb << " ";
return 0;
}
输出：
ad ae af bd be bf cd ce cf
# 注意此行为空
a b c
其他3种代码：?
代码1：
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
vector<string> result;
vector<string> letterCombinations(string digits)
{
string temp;
if (digits.length() == 0)
return result;
getAns(digits, 0, temp, result);
return result;
}
void getAns(string digits, int start, string temp, vector<string> &result)
{
if (temp.size() == digits.length())
result.push_back(temp);
else
{
vector<char> let = getLet(digits[start]);
for (int i = 0; i < let.size(); i++)
{
temp.append(1, let[i]);
getAns(digits, start + 1, temp, result);
temp.pop_back();
}
}
}
vector<char> getLet(char i)
{
vector<char> let;
switch(i){
case '2':
let.push_back('a');
let.push_back('b');
let.push_back('c');
break;
case '3':
let.push_back('d');
let.push_back('e');
let.push_back('f');
break;
case '4':
let.push_back('g');
let.push_back('h');
let.push_back('i');
break;
case '5':
let.push_back('j');
let.push_back('k');
let.push_back('l');
break;
case '6':
let.push_back('m');
let.push_back('n');
let.push_back('o');
break;
case '7':
let.push_back('p');
let.push_back('q');
let.push_back('r');
let.push_back('s');
break;
case '8':
let.push_back('t');
let.push_back('u');
let.push_back('v');
break;
case '9':
let.push_back('w');
let.push_back('x');
let.push_back('y');
let.push_back('z');
break;
default: break;
}
return let;
}
};
int main()
{
Solution s1;
string digits = "23";
for (auto comb : s1.letterCombinations(digits))
cout << comb << " ";
cout <<endl;
Solution s2;
digits = "";
for (auto comb : s2.letterCombinations(digits))
cout << comb << " ";
cout <<endl;
Solution s3;
digits = "2";
for (auto comb : s3.letterCombinations(digits))
cout << comb << " ";
return 0;
}
代码2：
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
unordered_map<char, string> map = {{'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}};
vector<string> res;
void backtrack(string &s, int index, string cur)
{
if (index == s.size())
{
res.push_back(cur);
return;
}
for (int i = 0; i < map[s[index]].size(); ++i)
backtrack(s, index + 1, cur + map[s[index]][i]);
}
vector<string> letterCombinations(string digits)
{
if (digits.size() == 0)
return res;
string cur;
backtrack(digits, 0, cur);
return res;
}
};
int main()
{
Solution s1;
string digits = "23";
for (auto comb : s1.letterCombinations(digits))
cout << comb << " ";
cout <<endl;
Solution s2;
digits = "";
for (auto comb : s2.letterCombinations(digits))
cout << comb << " ";
cout <<endl;
Solution s3;
digits = "2";
for (auto comb : s3.letterCombinations(digits))
cout << comb << " ";
return 0;
} 代码3：
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
vector<string> letterCombinations(string digits)
{
if (digits.size() == 0)
return {};
map<char, string> a;
a.insert(map<char, string>::value_type('2', "abc"));
a.insert(map<char, string>::value_type('3', "def"));
a.insert(map<char, string>::value_type('4', "ghi"));
a.insert(map<char, string>::value_type('5', "jkl"));
a.insert(map<char, string>::value_type('6', "mno"));
a.insert(map<char, string>::value_type('7', "pqrs"));
a.insert(map<char, string>::value_type('8', "tuv"));
a.insert(map<char, string>::value_type('9', "wxyz"));
int count = 1;
for (int i = 0; i < digits.size(); i++)
{
count *= a[digits[i]].size();
}
vector<string> res(count);
count = 1;
for (int i = 0; i < digits.size(); i++)
{
int index = 0;
vector<string> temp(res.begin(), res.begin() + count);
for (int k = 0; k < count; k++)
{
for (auto c : a[digits[i]])
{
res[index] = temp[k] + c;
index++;
}
}
count *= a[digits[i]].size();
}
return res;
}
};
int main()
{
Solution s1;
string digits = "23";
for (auto comb : s1.letterCombinations(digits))
cout << comb << " ";
cout <<endl;
Solution s2;
digits = "";
for (auto comb : s2.letterCombinations(digits))
cout << comb << " ";
cout <<endl;
Solution s3;
digits = "2";
for (auto comb : s3.letterCombinations(digits))
cout << comb << " ";
return 0;
}
2. 删除链表倒数第 N 个结点
给你一个链表，删除链表的倒数第 n?个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
示例 3：
输入：head = [1,2], n = 1
输出：[1]
提示：
? ?链表中结点的数目为 sz
? ?1 <= sz <= 30
? ?0 <= Node.val <= 100
? ?1 <= n <= sz
#include <bits/stdc++.h>
using namespace std;
struct ListNode
{
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution
{
public:
ListNode *removeNthFromEnd(ListNode *head, int n)
{
ListNode empty_node(0, head);
ListNode *p = &empty_node;
std::vector<ListNode *> pv;
while (p != nullptr)
{
pv.push_back(p);
p = p->next;
}
p = pv[pv.size() - 1 - n];
p->next = p->next->next;
return empty_node.next;
}
};
ListNode* CreateList(vector<int>& nums)
{
ListNode *head, *temp, *node;
head = nullptr;
temp = nullptr;
for (const auto data : nums)
{
node = new ListNode;
node->val = data;
if (head == nullptr)
head = node;
else
temp->next = node;
temp = node;
temp->next = nullptr;
}
return head;
}
void PrintList(ListNode* p)
{
while(p->next != nullptr)
{
cout << p->val << "->";
p = p->next;
}
cout << p->val << endl;
}
int main()
{
Solution s;
ListNode* head = (ListNode*)malloc(sizeof(ListNode));
vector <int> nums = {1,2,3,4,5};
head = CreateList(nums);
PrintList(head);
head = s.removeNthFromEnd(head, 2);
PrintList(head);
return 0;
}
输出：
? ?1->2->3->4->5
? ?1->2->3->5
? ?1
? ?(null)
? ?1->2
? ?1
? ?--------------------------------
? ?Process exited after 0.02629 seconds with return value 0
? ?请按任意键继续. . .
3. 海港(port)
问题描述
小谢是海港的海关工作人员，每天都有许多船只到达海港，船上通常有很多来自不同国家的乘客。
小谢对这些到达海港的船只非常感兴趣，他按照时间记录下了到达海港的每一艘船只情况；对于第i艘到达的船，他记录了这艘船只到达的时间ti（单位：秒），船上的乘客数量Ki，以及每名乘客的国籍x（i，1），x（i，2），···，x(i,k)。
小谢统计了n艘船的信息，希望你帮忙计算出以每一艘船到达时间为止的24小时（24小时=86400秒）内所有乘船到达的乘客来自多少个不同的国家。
形式化的讲，你需要计算n条信息。对于输出的第i条信息，你需要统计满足：ti-86400<tp<=ti的船只p，在所有的x（p，j）中，总共有多少个不同的数。
输入格式
第1行输入一个正整数n，表示小谢统计了n艘船的信息。
接下来的n行，每行描述一艘船的信息：前两个整数ti和ki分别表示这艘船到达海港的时间和船上的乘客数量，接下来的ki个整数x(i，j)表示从小谢第一次上班开始计时，这艘船在第ti秒到达海港。
保证1<=n<=105,ki>=1,∑ki<=3×105,1<=x(i,j)<=105,1<=ti-1<ti<=109。其中∑ki表示所有ki的和。输出格式
输出n行，第i行输出一个整数表示第i艘船到达后的统计信息。
输入样例1
1. 3
2. 1 4 4 1 2 2
3. 2 2 2 3
4. 10 1 3
输出样例1
样例1说明：第一艘船在第一秒到达海港，最近24小时到达的船是第一艘船，共4个乘客，分别来自国家4，1，2，2，共来自3个不同的国家。
第2艘船在第2秒到达海港，最近24小时到达的船是第1艘船和第2艘船，共有4+2=6个乘客，分别来自国家4,1,2,2,2,3，共来自4个不同的国家；
第三艘船在第10秒到达海港，最近24小时到达的船是第1艘船、第2艘船和第3艘船，共有4+2+1=7个乘客，分别是来自国家4,1,2,2,2,3,3，共来自4个不同的国家。
输入样例2
1. 4
2. 1 4 1 2 2 3
3. 3 2 2 3
4. 86401 2 3 4
5. 86402 1 5
输出样例2
样例2说明：第一艘船在第一秒到达海港，最近24小时到达的船是第1艘，共有4个乘客，分别是来自国家1,2,2,3，共来自3个不同的国家。
第2艘船是第3秒到达海港，最近24小时到达的船是第一艘船和第2艘船，共有4+2=6个乘客，分别来自1,2,2,3,2,3，共来自3个不同的国家
第3艘船是第86401秒到达海港，最近24小时到达的船是第2艘船和第3艘船，共有2+2=4个乘客，分别来自2.3,3,4，共来自3个不同的国家
第4艘船是第86402秒到达海港，最近24小时到达的船是第2艘船、第3艘船和第4艘船，共有2+2+1=5个乘客，分别来自2,3,3,4,5，共来自4个不同的国家。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
int a[100100];
int people[500100];
struct node
{
int country;
int time;
};
queue<node> q;
int main()
{
int n, sum = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
int t, p;
scanf("%d%d", &t, &p);
node temp;
temp.time = t;
for (int i = 1; i <= p; i++)
{
int cty;
scanf("%d", &cty);
temp.country = cty;
q.push(temp);
if (!people[cty])
sum++;
people[cty]++;
}
while (1)
{
node old;
old = q.front();
if (temp.time - 86400 >= old.time)
{
int tc = old.country;
people[tc]--;
if (!people[tc])
sum--;
q.pop();
}
else
break;
}
cout << sum << endl;
}
return 0;
}
输入输出：
? ?3
? ?1 4 4 1 2 2
? ?3
? ?2 2 2 3
? ?4
? ?10 1 3
? ?4
? ?--------------------------------
? ?Process exited after 58.98 seconds with return value 0
? ?请按任意键继续. . .
