17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = "" 输出：[]
示例 3：
输入：digits = "2" 输出：["a","b","c"]
方法一:递归回溯
每次根据一个数字然后获得对应的一个字母,进行下一个数字,直到达到字符串长度.然后回溯尝试下一个相同数字对应不同的字母.
参考代码1
#include<bits/stdc++.h> using namespace std; vector<string> ans; void dfs(string &s,int num); vector<string> letterCombinations(string digits) { if(digits=="") { return {}; } dfs(digits,0); return ans; } void dfs(string s,int num) {//这里不能使用引用,因为这次的字符串等到回溯回来 if(num==s.size()) { //结束条件 ans.push_back(s); return; } switch(s[num]) { case '2': s[num] = 'a'; dfs(s,num+1); s[num] = 'b'; dfs(s,num+1); s[num] = 'c'; dfs(s,num+1); break; case '3': s[num] = 'd'; dfs(s,num+1); s[num] = 'e'; dfs(s,num+1); s[num] = 'f'; dfs(s,num+1); break; case '4': s[num] = 'g'; dfs(s,num+1); s[num] = 'h'; dfs(s,num+1); s[num] = 'i'; dfs(s,num+1); break; case '5': s[num] = 'j'; dfs(s,num+1); s[num] = 'k'; dfs(s,num+1); s[num] = 'l'; dfs(s,num+1); break; case '6': s[num] = 'm'; dfs(s,num+1); s[num] = 'n'; dfs(s,num+1); s[num] = 'o'; dfs(s,num+1); break; case '7': s[num] = 'p'; dfs(s,num+1); s[num] = 'q'; dfs(s,num+1); s[num] = 'r'; dfs(s,num+1); s[num] = 's'; dfs(s,num+1); break; case '8': s[num] = 't'; dfs(s,num+1); s[num] = 'u'; dfs(s,num+1); s[num] = 'v'; dfs(s,num+1); break; case '9': s[num] = 'w'; dfs(s,num+1); s[num] = 'x'; dfs(s,num+1); s[num] = 'y'; dfs(s,num+1); s[num] = 'z'; dfs(s,num+1); break; } } int main() { string digits = "23"; letterCombinations(digits); for(int i = 0;i < ans.size();i++){ cout<<ans[i]<<endl; } cout<<ans.size()<<endl; return 0; }
方法二:队列
思路:
先将输入的digits中的第一个数字对应的字母入队,假设此时队列中的元素个数为len.
然后出去一个元素和第二个数字对应的每一个字母组合然后入队…之后再出去一个元素和第二个数字对应的字母组合入队…之后再…
等待len个元素都进行过该操作,则进行下一个数字;直到遍历到digits的结尾.最后队列中的元素即为所求.
参考代码2
#include<bits/stdc++.h> using namespace std; string phone[]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; queue<string> Q; vector<string> ans; vector<string> letterCombinations(string digits) { string temp,s1,s2; int pos,len; if(digits==""){ return {}; } for(int i = 0;i < digits.size();i++){ pos = digits[i]-'0'; s1 = phone[pos];//当前数字对应的序列 if(!i){//第一个数字 for(int j = 0;j < s1.size();j++){ temp = ""; temp+=s1[j]; Q.push(temp); } }else{//如果不是第一个字符. 弹出一个,拼接新的字符,重新放入. len = Q.size(); for(int j = 0;j < len;j++){// s2 = Q.front(); Q.pop(); for(int k = 0; k < s1.size();k++){ temp = ""; temp += s2; temp+=s1[k]; Q.push(temp); } } } } while(!Q.empty()){ temp = Q.front(); Q.pop(); ans.push_back(temp); } return ans; } int main() { string digits = ""; letterCombinations(digits); for(int i = 0;i < ans.size();i++){ cout<<ans[i]<<endl; } cout<<ans.size()<<endl; return 0; }
时间复杂度:
19. 删除链表的倒数第 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]
方法一
链表的基本使用:
逆向删除第n个节点,相当于正向删除第m = cnt-n+1个节点.
删除一个节点,则需要一个辅助指针指向当前节点的前一个节点.
如果当前只有一个节点,则直接进行删除(因为n>=1)
否则用辅助指针p找到m-1个节点.然后修改指针的指向:p->next = p->next->next;
参考代码
#include<bits/stdc++.h> using namespace std; //https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-b-61/ //链表的基本使用 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) {} }; ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* p = head; int cnt = 1; while(p->next!=NULL){ p = p->next; cnt++; } int m = cnt - n + 1;//正向删除 cng=5 n=1 5 n=2 4 cnt+1-n p = head; if(m==1){ return p->next; } for(int i = 1;i <= m-2;i++){ p = p->next; } p->next = p->next->next; return head; } int main(){ return 0; }
方法二:
快慢指针
- 时间复杂度：O(L)，其中 L是链表的长度。
- 空间复杂度：O(1)。
参考代码2
#include<bits/stdc++.h> using namespace std; //https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-b-61/ //链表的基本使用 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) {} }; ListNode* removeNthFromEnd(ListNode* head, int n) { if(head->next==NULL){//如果只有一个结点,则删除的必定是头结点因为n>1 return NULL; } ListNode *fast = head,*slow = head; for(int i = 0;i < n;i++){ fast = fast->next; } if(!fast){//如果移动n位后为null,说明删除的是第一个节点 return head->next; } while(fast->next){ fast = fast->next; slow = slow->next; } slow->next = slow->next->next; return head;//返回第一个节点对应的指针. }
