WHCSRL 技术网

LeetCode刷题day09(思路明天进行完善...)

算法打卡第九天,今天你刷题了吗
😄😄😄😄😄😄😄😄😄😄
😃😃😃😃😃😃😃😃😃😃
💓💓💓大家一起来刷题!💓💓💓
😍😍😍😍😍😍😍😍😍😍
😘😘😘😘😘😘😘😘😘😘
请添加图片描述

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
在这里插入图片描述

示例 1:

输入:digits = "23"
输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]
  • 1
  • 2

示例 2:

输入:digits = ""
输出:[]
  • 1
  • 2

示例 3:

输入:digits = "2"
输出:["a","b","c"]
  • 1
  • 2

方法一:递归回溯

每次根据一个数字然后获得对应的一个字母,进行下一个数字,直到达到字符串长度.然后回溯尝试下一个相同数字对应不同的字母.

参考代码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;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100

方法二:队列

思路:先将输入的digits中的第一个数字对应的字母入队,然后将出队的元素与第二个数字对应的每一个字母组合后入队…直到遍历到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;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54

请添加图片描述

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

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

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

示例 1:

输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]
  • 1
  • 2

示例 2:

输入:head = [1], n = 1
输出:[]
  • 1
  • 2

示例 3:

输入:head = [1,2], n = 1
输出:[1]
  • 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) {
	ListNode* p = head;
	int cnt = 1;
	while(p->next!=NULL){
		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;
	}
	if(p->next->next==NULL){
		p->next = NULL;
	}else{
		p->next = p->next->next;
	}
	return head; 
	
}

int main(){
	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38

方法二:

快慢指针

参考代码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;//返回第一个节点对应的指针. 
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

😜😜😜😜😜 大家卷起来! 😝😝😝😝😝
请添加图片描述

推荐阅读