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

(null)

1->2

--------------------------------

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. 3
2. 4
3. 4

样例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

1. 3
2. 3
3. 3
4. 4

样例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;
}