# 17. 电话号码的字母组合

题目

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

示例:

输入:"23" 输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. 说明: 尽管上面的答案是按字典序排列的,但是你可以任意选择答案输出的顺序

思路

  1. 用递归来实现。临界条件:参数为单个字母,返回单个字母的数组;否则:递归调用,把得到的数组再进行扩展返回。
public:
    const vector<string> v = {
            "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    };

    vector<string> letterCombinations(string digits) {
        if (digits.size() == 1) {
            int n = digits[0] - '2';
            vector<string> result;
            string s;
            for (int i = 0; i < v[n].size(); i++) {
                s = v[n][i];
                result.push_back(s);
            }
            return result;
        } else {
            char c = digits[0];
            int n = digits[0] - '2';
            digits.erase(digits.begin());
            vector<string> r = letterCombinations(digits);
            vector<string> result;
            string s;
            for (int i = 0; i < v[n].size(); i++) {
                for (int j = 0; j < r.size(); j++) {
                    s = v[n][i] + r[j];
                    result.push_back(s);
                }
            }
            return result;
        }
    }

};
  1. 使用循环来代替递归。

# 18

# 19. 删除链表的倒数第N个节点

题目:

给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。

示例:

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后,链表变为 1->2->3->5.

说明:

给定的 n 保证是有效的。

进阶:

你能尝试使用一趟扫描实现吗?

思路

在王道408中遇到过这道题,最开始时候是用两次遍历,一次求长度,一次删除。但是发现可以巧妙地使用双指针来一次遍历。具体实现方法是,先让指针p1n步,p2再动身,这样p2永远落后p1 n步,于是p1到结尾的时候,p2就到删除节点的前一个位置了。

这里还需要注意,若是n和链表长度一样时候直接返回head->next

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *p1 = head;
        ListNode *p2 = head;
        for (int i = 0; i < n; i++) {
            if(p1->next != NULL) p1 = p1->next;
            else return head->next;
        }
        while(p1->next != NULL) {
            p1 = p1->next;
            p2 = p2->next;
        }
        p2->next = p2->next->next;
        return head;
    }
};