LeetCode刷题记(一):1~30题

 1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target  的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1:

输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

示例 2:

输入:nums = [3,2,4], target = 6
输出:[1,2]

示例 3:

输入:nums = [3,3], target = 6
输出:[0,1]

提示:

  • 2 <= nums.length <= 10^4
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9
  • 只会存在一个有效答案
#include <iostream>
#include <vector>
#include <map>
using namespace std;

vector<int> twoSum(vector<int>& nums, int target) {
    map<int, int> map;
    vector<int> result;
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];  // 差值
        if (map.find(complement) != map.end()) {
            result.push_back(map[complement]);
            result.push_back(i);
            return result;
        }
        map[nums[i]] = i;
    }
    return result;
}

int main() {
    vector<int> nums;
    int target;
    int temp;
    while(cin>>temp){
    	nums.push_back(temp);
    	if(cin.get() == '\n')
    		break;
	}
	cin>>target;
    vector<int> result = twoSum(nums, target);
    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << " ";
    }
    return 0;
}

2. 两数相加

给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。

请你将两个数相加,并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例 1:

输入:l1 = [2,4,3], l2 = [5,6,4]
输出:[7,0,8]
解释:342 + 465 = 807.

示例 2:

输入:l1 = [0], l2 = [0]
输出:[0]

示例 3:

输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出:[8,9,9,9,0,0,0,1]

提示:

  • 每个链表中的节点数在范围 [1, 100] 内
  • 0 <= Node.val <= 9
  • 题目数据保证列表表示的数字不含前导零
#include<iostream>
using namespace std;

struct ListNode {
	int val;
	ListNode *next;
	ListNode() : val(0), next(NULL) {}
	ListNode(int x) : val(x), next(NULL) {}
	ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
	public:
		ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
			ListNode* dummy = new ListNode(0);
			ListNode* curr = dummy;
			int carry = 0;  // 进位
			
			while(l1 != NULL || l2 != NULL) {
				int x = (l1 != NULL) ? l1->val : 0;  
				int y = (l2 != NULL) ? l2->val : 0;
				int sum = x + y + carry;
				carry = sum / 10;
				curr->next = new ListNode(sum % 10);
				curr = curr->next;
				
				if(l1 != NULL) l1 = l1->next;
				if(l2 != NULL) l2 = l2->next;
			} 
			// 增添1位 
			if(carry > 0) {
				curr->next = new ListNode(carry);
			}
			return dummy->next;
		}
};


ListNode* createList() {
	ListNode* head = NULL;
	ListNode* current = NULL;
	int val;
	while(cin >> val) {
		ListNode* newNode = new ListNode(val);
		if(head == NULL) {
			head = newNode;
			current = newNode;
		} else {
			current->next = newNode;
			current = current->next;
		}
		if(cin.get() == '\n')
			break;
	}
	return head;
}

void printList(ListNode* head) {
	ListNode* current = head;
	while(current != NULL) {
		cout << current->val << " ";
		current = current->next;
	}
}

int main() {
	Solution solution;
	ListNode* list1 = createList();
	ListNode* list2 = createList();
	ListNode* result = solution.addTwoNumbers(list1, list2);
	printList(result);
	return 0;
}

 3. 无重复字符的最长子串

给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。请注意,你的答案必须是子串的长度,"pwke"是一个子序列,不是子串。

提示:

  • 0 <= s.length <= 5 * 10^4
  • s 由英文字母、数字、符号和空格组成
#include<iostream>
#include<vector>
using namespace std;

class Solution {
	public:
		int lengthOfLongestSubstring(string s) {
			// 使用滑动窗口来找出最长的不含重复字符的子串 
			int n = s.length();
			int res = 0;  // 记录最长子串的长度 
			vector<int> index(128, -1);  // 记录每个字符在字符串s中最近出现的位置 
			for(int i = 0, j = 0; j < n; j++) {
				i = max(i, index[s[j]] + 1);  // 当遇到重复的字符时,将左边界i移动到该重复字符的下一个位置,确保窗口内没有重复字符 
				res = max(res, j - i + 1);  // 每次更新窗口长度并与res比较,取较大者 
				index[s[j]] = j;  // 更新字符在index数组中的位置为当前位置 
			}
			return res;
		}
};

int main() {
	Solution solution;
	string s;
	cin >> s;
	cout << solution.lengthOfLongestSubstring(s);
	return 0;
}

4. 寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1:

输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 2

示例 2:

输入:nums1 = [1,2], nums2 = [3,4]
输出:2.50000
解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5
^

提示:

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -10^6 <= nums1[i], nums2[i] <= 10^6

解法一:

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

class Solution {
	public:
		double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
			vector<int> curr;
			int m = nums1.size();
			int n = nums2.size();
			for(int i = 0; i < m; i++) {
				curr.push_back(nums1[i]);
			}
			for(int i = 0; i < n; i++) {
				curr.push_back(nums2[i]);
			}
			sort(curr.begin(), curr.end());
			
			if((m + n) % 2 == 0) {
				return (curr[(m + n) / 2] + curr[(m + n) / 2 - 1] ) / 2.0; 
			} else {
				return curr[(m + n) / 2];
			}
		}
};

int main() {
	Solution solution;
	vector<int> nums1, nums2;
	int tmp;
	cout << "请输入nums1数组的元素:" << endl;
	while(cin >> tmp) {
		nums1.push_back(tmp);
		if(cin.get() == '\n')
			break;
	}
	
	cout << "请输入nums2数组的元素:" << endl;
	while(cin >> tmp) {
		nums2.push_back(tmp);
		if(cin.get() == '\n')
			break;
	}
	
	cout << solution.findMedianSortedArrays(nums1, nums2);
	return 0;
}

解法二:

class Solution {
	public:
		double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
			vector<int> curr;
			int m = nums1.size();
			int n = nums2.size();
            int i = 0, j = 0;
            while(i < m && j < n) {
                if(nums1[i] < nums2[j]) {
                    curr.push_back(nums1[i]);
                    i++;
                }
                else {
                    curr.push_back(nums2[j]);
                    j++;
                }
            }

            while(i < m) {
                curr.push_back(nums1[i]);
                i++;
            }

            while(j < n) {
                curr.push_back(nums2[j]);
                j++;
            }
			if((m + n) % 2 == 0) {
				return (curr[(m + n) / 2] + curr[(m + n) / 2 - 1] ) / 2.0; 
			} else {
				return curr[(m + n) / 2];
			}
		}
};

 5. 最长回文子串

给你一个字符串 s,找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。

示例 1:

输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。

示例 2:

输入:s = "cbbd"
输出:"bb"

提示:

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成
// C++
#include<iostream>
#include<vector>
#include<string>
using namespace std;

class Solution {
	public:
		string longestPalindrome(string s) {
			int n = s.size();
			if(n < 2) {
				return s;
			}
			int maxLen = 1;
			int begin = 0;
			//dp[i][j]表示s[i··j]是否为回文串
			vector<vector <int> > dp(n,vector<int>(n, true));

			//递归开始
			//先枚举子串长度
			for(int L = 2; L <= n; L++) {
				//枚举左边界,左边界的上限设置可以宽松一些
				for(int i = 0; i < n; i++) {
					int j = L + i - 1;
					//如果右边界越界,就可以退出当前循环
					if(j >= n) {
						break;
					}

					if(s[i] != s[j]) {
						dp[i][j] = false;
					} else {
						if(j-i < 3) {
							dp[i][j] = true;
						} else {
							dp[i][j] = dp[i + 1][j - 1];
						}
					}
					// 只要dp[i][j] == true成立,就表示子串s[i···L]是回文,此时记录回文长度和起始位置。
					if(dp[i][j] && j - i + 1 > maxLen) {
						maxLen = j - i + 1;
						begin = i;
					}
				}
			}
			return s.substr(begin,maxLen);
		}
};

int main() {
	string s = "";
	cin>>s;
	Solution solution;
	cout<<solution.longestPalindrome(s)<<endl;
	return 0;
}

解法二:

// C++
#include<iostream>
#include<vector>
#include<string>
using namespace std;

class Solution {
	public:
		string longestPalindrome(string s) {
			if(s.empty()) {
				return "";
			}
			int start = 0, end = 0;
			for(int i = 0; i < s.size(); i++) {
				int len1 = expandAroundCenter(s, i, i);
				int len2 = expandAroundCenter(s, i, i + 1);
				 int len = max(len1, len2);
				 
				 if(len > end - start) {
				 	start = i - (len - 1) / 2;
				 	end = i + len / 2;
				 }
			}
			return s.substr(start, end - start + 1);
		}
		
		int expandAroundCenter(string s, int left, int right) {
			while(left >= 0 && right < s.size() && s[left] == s[right]) {
				left--;
				right++;
			}
			return right - left - 1;
		}
};

int main() {
	string s = "";
	cin>>s;
	Solution solution;
	cout<<solution.longestPalindrome(s)<<endl;
	return 0;
}

6. Z字型变换

将一个给定字符串 s 根据给定的行数 numRows ,以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时,排列如下:

P   A   H   N
A P L S I I G
Y   I   R

之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:"PAHNAPLSIIGYIR"

请你实现这个将字符串进行指定行数变换的函数:

string convert(string s, int numRows);

示例 1:

输入:s = "PAYPALISHIRING", numRows = 3
输出:"PAHNAPLSIIGYIR"

示例 2:

输入:s = "PAYPALISHIRING", numRows = 4
输出:"PINALSIGYAHRPI"
解释:
P     I    N
A   L S  I G
Y A   H R
P     I

示例 3:

输入:s = "A", numRows = 1
输出:"A"

提示:

  • 1 <= s.length <= 1000
  • s 由英文字母(小写和大写)、',' 和 '.' 组成
  • 1 <= numRows <= 1000
#include<iostream>
#include<vector> 
#include<algorithm>
using namespace std;

class Solution {
	public:
		string covert(string s, int numRows) {
			if(numRows == 1) return s;
			
			int n = s.size();
			int k = 2 * numRows - 2;  // 计算 Z 字形的周期长度,即每个完整的 Z 字形有多少个字符
			vector<string> a(numRows);
            // 创建一个长度为 numRows 的字符串数组 a,用于存储 Z 字形排列后的每一行字符串
			for(int i = 0; i < n; i++) {
				a[min(k - i % k, i % k)] += s[i];
                // k - i % k 和 i % k 分别表示当前字符在 Z 字形周期中的上半部分和下半部分的位置
			}
			return accumulate(a.begin(), a.end(), string(""));  // 拼接
		}
};

int main() {
	string s;
	cin >> s;
	int numRows;
	cin >> numRows; 
	Solution solution;
	cout << solution.covert(s, numRows);
	return 0;
}

 7. 整数反转

给你一个 32 位的有符号整数 x ,返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−2^31, 2^31 − 1] ,就返回 0。

假设环境不允许存储 64 位整数(有符号或无符号)。

示例 1:

输入:x = 123
输出:321

示例 2:

输入:x = -123
输出:-321

示例 3:

输入:x = 120
输出:21

示例 4:

输入:x = 0
输出:0

提示:

  • -2^31 <= x <= 2^31 - 1
#include<iostream>
#include<vector>
using namespace std;

class Solution {
	public:
		int reverse(int x) {
//			if(x == 0)	return 0;
			int res = 0;
			while(x != 0) {
				if(res < INT_MIN / 10 || res > INT_MAX / 10) {
					return 0;
				}
				res = res * 10 + x % 10;
				x /= 10;
			}
			return res;
		}
};

int main() {
	int x;
	cin >> x;
	Solution solution;
	cout << solution.reverse(x) << endl;
	return 0;
}

8. 字符串转换正数(atoi)

请你来实现一个 myAtoi(string s) 函数,使其能将字符串转换成一个 32 位有符号整数(类似 C/C++ 中的 atoi 函数)。

函数 myAtoi(string s) 的算法如下:

  1. 读入字符串并丢弃无用的前导空格
  2. 检查下一个字符(假设还未到字符末尾)为正还是负号,读取该字符(如果有)。 确定最终结果是负数还是正数。 如果两者都不存在,则假定结果为正。
  3. 读入下一个字符,直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
  4. 将前面步骤读入的这些数字转换为整数(即,"123" -> 123, "0032" -> 32)。如果没有读入数字,则整数为 0 。必要时更改符号(从步骤 2 开始)。
  5. 如果整数数超过 32 位有符号整数范围 [−231,  231 − 1] ,需要截断这个整数,使其保持在这个范围内。具体来说,小于 −231 的整数应该被固定为 −231 ,大于 231 − 1 的整数应该被固定为 231 − 1 。
  6. 返回整数作为最终结果。

注意:

  • 本题中的空白字符只包括空格字符 ' ' 。
  • 除前导空格或数字后的其余字符串外,请勿忽略 任何其他字符。

示例 1:

输入:s = "42"
输出:42
解释:加粗的字符串为已经读入的字符,插入符号是当前读取的字符。
第 1 步:"42"(当前没有读入字符,因为没有前导空格)
         ^
第 2 步:"42"(当前没有读入字符,因为这里不存在 '-' 或者 '+')
         ^
第 3 步:"42"(读入 "42")
           ^
解析得到整数 42 。
由于 "42" 在范围 [-231, 231 - 1] 内,最终结果为 42 。

示例 2:

输入:s = "   -42"
输出:-42
解释:
第 1 步:"   -42"(读入前导空格,但忽视掉)
            ^
第 2 步:"   -42"(读入 '-' 字符,所以结果应该是负数)
             ^
第 3 步:"   -42"(读入 "42")
               ^
解析得到整数 -42 。
由于 "-42" 在范围 [-231, 231 - 1] 内,最终结果为 -42 。

示例 3:

输入:s = "4193 with words"
输出:4193
解释:
第 1 步:"4193 with words"(当前没有读入字符,因为没有前导空格)
         ^
第 2 步:"4193 with words"(当前没有读入字符,因为这里不存在 '-' 或者 '+')
         ^
第 3 步:"4193 with words"(读入 "4193";由于下一个字符不是一个数字,所以读入停止)
             ^
解析得到整数 4193 。
由于 "4193" 在范围 [-231, 231 - 1] 内,最终结果为 4193 。

提示:

  • 0 <= s.length <= 200
  • s 由英文字母(大写和小写)、数字(0-9)、' ''+''-' 和 '.' 组成
#include<iostream>
#include<ctype.h>
using namespace std;

class Solution {
	public:
		int myAtoi(string s) {
			int i = 0;  // 索引 
			int sign = 1;  // 符号位
			long long result = 0;
			
			// 跳过前面的空格字符
			while(i < s.size() && s[i] == ' ') {
				i++;
			} 
			
			// 检查最终结果为正数还是负数
			if(i < s.size() && (s[i] == '+' || s[i] == '-')) {
				sign = (s[i++] == '-' ? -1 : 1);
			} 
			
			// 把字符串转换成数字 
			while(i < s.size() && isdigit(s[i])) {
				result = result * 10 + (s[i++] - '0');
				if(result * sign > INT_MAX) {
					return INT_MAX;
				} 
				if(result * sign < INT_MIN) {
					return INT_MIN;
				}
			} 
			return result * sign;
		}
};

int main() {
	string s;
	cin >> s;
	Solution solution;
	cout << solution.myAtoi(s);
	return 0;
}
 

 9. 回文数

给你一个整数 x ,如果 x 是一个回文整数,返回 true ;否则,返回 false 。

回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。

  • 例如,121 是回文,而 123 不是。

示例 1:

输入:x = 121
输出:true

示例 2:

输入:x = -121
输出:false
解释:从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3:

输入:x = 10
输出:false
解释:从右向左读, 为 01 。因此它不是一个回文数。

提示:

  • -2^31 <= x <= 2^31 - 1
#include<iostream>
using namespace std;

bool isPalindrome(int num){
	if(num < 0){ 
		return false;
	} 
	int original = num;
	long long reversed = 0;
	while(num > 0) {
		reversed = reversed * 10 + num % 10;
		num /= 10;
	}
	return original == reversed;
}

int main()
{
	int num;
	cin>>num;
	cout<<boolalpha<<isPalindrome(num)<<endl;
	return 0;
}

10. 正则表达式匹配

给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

  • '.' 匹配任意单个字符
  • '*' 匹配零个或多个前面的那一个元素

所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。

示例 1:

输入:s = "aa", p = "a"
输出:false
解释:"a" 无法匹配 "aa" 整个字符串。

示例 2:

输入:s = "aa", p = "a*"
输出:true
解释:因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此,字符串 "aa" 可被视为 'a' 重复了一次。

示例 3:

输入:s = "ab", p = ".*"
输出:true
解释:".*" 表示可匹配零个或多个('*')任意字符('.')。

提示:

  • 1 <= s.length <= 20
  • 1 <= p.length <= 20
  • s 只包含从 a-z 的小写字母。
  • p 只包含从 a-z 的小写字母,以及字符 . 和 *
  • 保证每次出现字符 * 时,前面都匹配到有效的字符
#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size();
        int n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        dp[0][0] = true;
        /*
        使用两层循环遍历dp数组,其中i表示s的长度,j表示p的长度。
        在内层循环中,分情况讨论:
        如果p[j-1]为'',则dp[i][j]为dp[i][j-2](''匹配0次)或者(s的第i个字符和p的第j-1个字符匹配,
        并且dp[i-1][j]为true)。
        如果p[j-1]不为'*',则dp[i][j]为dp[i-1][j-1](s的第i个字符和p的第j个字符匹配)。
        */

        for (int i = 0; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j - 1] == '*') {
                    dp[i][j] = dp[i][j - 2] || (i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j]);
                } else {
                    dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
                }
            }
        }
        
        return dp[m][n];
    }
};

int main() {
	string s, p;
	cin >> s >> p;
	Solution solution;
	cout << boolalpha << solution.isMatch(s, p);
	return 0;
}

 11. 盛最多的水

给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明:你不能倾斜容器。

示例 1:

输入:[1,8,6,2,5,4,8,3,7]
输出:49 
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

示例 2:

输入:height = [1,1]
输出:1

提示:

  • n == height.length
  • 2 <= n <= 10^5
  • 0 <= height[i] <= 10^4
#include<iostream>
#include<vector>
using namespace std;

class Solution {
	public:
		int maxArea(vector<int>& height) {
			int n = height.size();
			int left = 0;
			int right = n - 1;
			int result = 0;
			while(left < right) {
				result = max(result, (right - left) * min(height[left], height[right]));
				if(height[left] > height[right]) {
					--right;
				} else {
					++left;
				}
			}
			return result;
		}
}; 

int main() {
	Solution solution;
	vector<int> height;
	int tmp;
	while(cin >> tmp) {
		height.push_back(tmp);
		if(cin.get() == '\n')
			break;
	}
	cout << solution.maxArea(height);
	return 0;
}

12. 整数转罗马数字

罗马数字包含以下七种字符: I, V, X, LCD 和 M

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。

通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:

  • I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。 
  • C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。

给你一个整数,将其转为罗马数字。

示例 1:

输入: num = 3
输出: "III"

示例 2:

输入: num = 4
输出: "IV"

示例 3:

输入: num = 9
输出: "IX"

示例 4:

输入: num = 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.

示例 5:

输入: num = 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示:

  • 1 <= num <= 3999

解法一:

#include<iostream>
#include<map>
#include<vector>
using namespace std;

class Solution {
	public:
		string intToRoman(int num) {
			vector<int> values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
			vector<string> symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
			string result = "";
			for(int i = 0; i < values.size(); i++) {
				while(num >= values[i]) {
					num -= values[i];
					result += symbols[i];
				}
			}
			return result;
		}
};

int main() {
	Solution solution;
	int num;
	cin >> num;
	cout << solution.intToRoman(num);
	return 0;
}

解法二:

#include<iostream>
#include<map>
#include<vector>
using namespace std;

class Solution {
	public:
		string intToRoman(int num) {
			map<int, string> romanMap;
			romanMap[1] = "I";
			romanMap[4] = "IV";
			romanMap[5] = "V";
			romanMap[9] = "IX";
			romanMap[10] = "X";
			romanMap[40] = "XL";
			romanMap[50] = "L";
			romanMap[90] = "XC";
			romanMap[100] = "C";
			romanMap[400] = "CD";
			romanMap[500] = "D";
			romanMap[900] = "CM";
			romanMap[1000] = "M";
			
			string result = "";
			for(auto it = romanMap.rbegin(); it != romanMap.rend(); ++it) {
				while(num >= it->first) {
					result += it->second;
					num -= it->first;
				}
			}
			return result;
		}
};

int main() {
	Solution solution;
	int num;
	cin >> num;
	cout << solution.intToRoman(num);
	return 0;
}

 13. 罗马数字转整数

罗马数字包含以下七种字符: I, V, X, LCD 和 M

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如, 罗马数字 2 写做 II ,即为两个并列的 1 。12 写做 XII ,即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。

通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:

  • I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。 
  • C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。

给定一个罗马数字,将其转换成整数。

示例 1:

输入: s = "III"
输出: 3

示例 2:

输入: s = "IV"
输出: 4

示例 3:

输入: s = "IX"
输出: 9

示例 4:

输入: s = "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5:

输入: s = "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示:

  • 1 <= s.length <= 15
  • s 仅含字符 ('I', 'V', 'X', 'L', 'C', 'D', 'M')
  • 题目数据保证 s 是一个有效的罗马数字,且表示整数在范围 [1, 3999] 内
  • 题目所给测试用例皆符合罗马数字书写规则,不会出现跨位等情况。
  • IL 和 IM 这样的例子并不符合题目要求,49 应该写作 XLIX,999 应该写作 CMXCIX 。
  • 关于罗马数字的详尽书写规则,可以参考 罗马数字 - Mathematics 。
#include<iostream>
#include<map>
using namespace std;

int romanToInt(string s){
	map<char, int> romanMap;
	romanMap['I'] = 1;
	romanMap['V'] = 5;
	romanMap['X'] = 10;
	romanMap['L'] = 50;
	romanMap['C'] = 100;
	romanMap['D'] = 500;
	romanMap['M'] = 1000;
	
	int result = 0;
	for(int i = 0; i < s.length(); i++) {
		if(i < s.length() - 1 && romanMap[s[i]] < romanMap[s[i + 1]]) {
			result -= romanMap[s[i]];
		} else {
			result += romanMap[s[i]];
		}
	}
	return result;
} 

int main(){
	string romanNum;
	cin>>romanNum;
	cout<<romanToInt(romanNum);
	return 0;
} 

14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 ""

示例 1:

输入:strs = ["flower","flow","flight"]
输出:"fl"

示例 2:

输入:strs = ["dog","racecar","car"]
输出:""
解释:输入不存在公共前缀。

提示:

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] 仅由小写英文字母组成
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

string longestCommonPrefix(vector<string>& strs) {
	if(strs.empty()) {
		return "";
	} 
	string ans = strs[0];
	for(int i = 1; i < strs.size(); i++) {
		int j = 0;
		for(; j < ans.length() && j < strs[i].length(); j++) {
			if(ans[j] != strs[i][j])
				break;
		}
		ans = ans.substr(0, j);
		if(ans == "")
			return ans;
	} 
	return ans;
}

int main() {
	vector<string> strs;
	string tmp;
	while(cin>>tmp) {
		strs.push_back(tmp);
		if(cin.get() == '\n') 
			break;
	}
	cout<<longestCommonPrefix(strs)<<endl;
	return 0;
} 

15. 三数之和

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != ji != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意:答案中不可以包含重复的三元组。

示例 1:

输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。

示例 2:

输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0 。

示例 3:

输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0 。

提示:

  • 3 <= nums.length <= 3000
  • -10^5 <= nums[i] <= 10^5
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

class Solution {
	public:
		vector<vector<int> > threeSum(vector<int>& nums) {
			vector<vector<int> > result;
			sort(nums.begin(), nums.end());
			
			for(int i = 0; i < nums.size(); i++) {
				if(i > 0 && nums[i] == nums[i - 1]) {
					continue;  // 重复 
				}
				
				int target = -nums[i];
				int left = i + 1;
				int right = nums.size() - 1;
				while(left < right) {
					int sum = nums[left] + nums[right];
					if(sum < target) {  // 小于0 
						left++;
					} else if(sum > target) {  // 大于0 
						right--;
					} else {  // 等于0 
						result.push_back({nums[i], nums[left], nums[right]});
						
						while(left < right && nums[left] == nums[left + 2]) {
							left++;
						}
						
						while(left < right &&nums[right] == nums[right - 1]) {
							right--;
						}
						left++;
						right--;
					}
				}
			}
			return result;
		}
};

int main() {
	int tmp;
	vector<int> nums;
	while(cin >> tmp) {
		nums.push_back(tmp);
		if(cin.get() == '\n')
			break;
	}
	Solution solution;
	vector<vector<int>> result = solution.threeSum(nums);
//	for(const auto& triplet : result) {
//		cout << "[";
//		for(int i = 0; i < 3; i++) {
//			cout << triplet[i];
//			if(i < 2) {
//				cout << ", ";
//			}
//		}
//		cout << "] ";
//	}
	cout << "[";
	 for(vector<vector<int> >::iterator it = result.begin(); it != result.end(); ++it) {
        cout << "[";
        for(int i = 0; i < 3; ++i) {
            cout << (*it)[i];
            if(i < 2) {
                cout << ",";
            }
        }
        if(it == result.end() - 1) {
        	cout << "]";
		} else {
			cout << "], ";
		}
    }
    cout << "]";
	return 0; 
} 

16. 最接近的三数之和

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数,使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例 1:

输入:nums = [-1,2,1,-4], target = 1
输出:2
解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

示例 2:

输入:nums = [0,0,0], target = 1
输出:0

提示:

  • 3 <= nums.length <= 1000
  • -1000 <= nums[i] <= 1000
  • -10^4 <= target <= 10^4
#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>
using namespace std;

class Solution {
	public:
		int threeSumClosest(vector<int>& nums, int target) {
			sort(nums.begin(), nums.end());
			int closestSum = INT_MAX;
			int minDiff = INT_MAX;
			
			for(int i = 0; i < nums.size() - 2; i++) {
				int left = i + 1;
				int right = nums.size() - 1;
				while(left < right) {
					int sum = nums[i] + nums[left] + nums[right];
					int diff = abs(sum - target);
					
					if(diff < minDiff) {  // 更新最小差值 
						minDiff = diff;
						closestSum = sum;
					}
					
					if(sum < target) {
						++left;  // 偏小 
					} else if(sum > target) {
						--right;  // 偏大 
					} else {
						return sum;   // 相等 
					}
				}
			}
			return closestSum;
		}
};

int main() {
	int target;
	vector<int> nums;
	while(cin >> target) {
		nums.push_back(target);
		if(cin.get() == '\n')
			break;
	}
	cin >> target;
	Solution solution;
	cout << solution.threeSumClosest(nums, target);
	return 0;
}

17. 电话号码的字母组合

给定一个仅包含数字 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 <iostream>
#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> result;
        if (digits.empty()) {
            return result;
        }

        unordered_map<char, string> digitToLetters = {
            {'2', "abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"}
        };

        string current;
        backtrack(digits, 0, current, result, digitToLetters);

        return result;
    }

    void backtrack(string& digits, int index, string& current, vector<string>& result, unordered_map<char, string>& digitToLetters) {
        if (index == digits.length()) {
            result.push_back(current);
            return;
        }

        char digit = digits[index];
        string letters = digitToLetters[digit];
        for (char letter : letters) {
            current.push_back(letter);
            backtrack(digits, index + 1, current, result, digitToLetters);
            current.pop_back();
        }
    }
};

int main() {
    string digits;
    cin >> digits;

    Solution solution;
    vector<string> result = solution.letterCombinations(digits);

    for (string& combination : result) {
        cout << combination << " ";
    }

    return 0;
}

18. 四数之和

给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复):

  • 0 <= a, b, c, d < n
  • abc 和 d 互不相同
  • nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1:

输入:nums = [1,0,-1,0,-2,2], target = 0
输出:[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2:

输入:nums = [2,2,2,2,2], target = 8
输出:[[2,2,2,2]]

提示:

  • 1 <= nums.length <= 200
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

class Solution {
	public:
		vector<vector<int>> fourSum(vector<int>& nums, int target) {
			vector<vector<int>> result;
			int n = nums.size();
			if(n < 4) {
				return result;
			}
			sort(nums.begin(), nums.end());
			
			for(int i = 0; i < n - 3; i++) {
				if(i > 0 && nums[i] == nums[i - 1]) {
					continue;
				}
				
				for(int j = i + 1; j < n - 2; j++) {
					if(j > i + 1 && nums[j] == nums[j - 1]) {
						continue;
					}
					
					int left = j + 1;
					int right = n - 1;
					while(left < right) {
						long sum = static_cast<long>(nums[i]) + nums[j] + nums[left] + nums[right];
						if(sum < target) {
							++left;
						} else if(sum > target) {
							--right;
						} else {
							result.push_back({nums[i], nums[j], nums[left], nums[right]});
							while(left < right && nums[left] == nums[left + 1]) {
								++left;
							}
							
							while(left < right && nums[right] == nums[right - 1]) {
								--right;
							}
							++left;
							--right;
						}
					}
				}
			}
			return result;
		}
};

int main() {
	int target;
	vector<int> nums;
	while(cin >> target) {
		nums.push_back(target);
		if(cin.get() == '\n')
			break;
	}
	cin >> target;
	Solution solution;
	vector<vector<int>> result = solution.fourSum(nums, target);
	for(vector<int>& quadruplet : result) {
		cout << "[";
		for(int num : quadruplet) {
			cout << num << " ";
		}
		cout << "] ";
	}
	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]

提示:

  • 链表中结点的数目为 sz
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

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

解题思路:要删除链表的倒数第n个结点,可以使用双指针技巧。首先定义两个指针,分别为快指针和慢指针,初始时均指向头节点。然后让快指针先向后移动n + 1步,这样快指针和慢指针之间就会相隔n个节点。接着同时移动快指针和慢指针,直到快指针指向链表末尾。此时慢指针指向的节点就是要删除的节点的前一个结点。

#include<iostream>
using namespace std;

// Definition for single-linked list
struct ListNode {
	int val;
	ListNode *next;
	ListNode() : val(0), next(NULL) {}
	ListNode(int x) : val(x), next(NULL) {}
	ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
	public:
		ListNode* removeNthFromEnd(ListNode* head, int n) {
			ListNode* dummy = new ListNode(0);
			dummy->next = head;
			ListNode* fast = dummy;
			ListNode* slow = dummy;
			
			// 向后移动n + 1步 
			for(int i = 0; i < n + 1; i++) {
				fast = fast->next;
			}
			
			while(fast != NULL) {
				fast = fast->next;
				slow = slow->next;
			}
			
			// 删除结点 
			ListNode * q = slow->next;
			slow->next = slow->next->next;
			delete q;
			return dummy->next;
		}
};

ListNode* createList() {
	ListNode* head = NULL;
	ListNode* current = NULL;
	int val;
	while(cin >> val) {
		ListNode* newNode = new ListNode(val);
		if(head == NULL) {
			head = newNode;
			current = newNode;
		} else {
			current->next = newNode;
			current = newNode;
		}
		if(cin.get() == '\n')
			break;
	}
	return head;
}

void printList(ListNode* head) {
	ListNode* current = head;
	while(current != NULL) {
		cout << current->val << " ";
		current = current->next;
	}
}

int main() {
	ListNode* head = createList();
	int n;
	cin >> n;
	Solution solution;
	ListNode* result = solution.removeNthFromEnd(head, n);
	printList(result);
	return 0;
}

20. 有效的括号

给定一个只包括 '('')''{''}''['']' 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1:

输入:s = "()"
输出:true

示例 2:

输入:s = "()[]{}"
输出:true

示例 3:

输入:s = "(]"
输出:false

提示:

  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成
#include<iostream>
#include<stack>
#include<map>
using namespace std;


bool isValid(string s) {
	stack<char> stk;
	map<char, char> brackets;
	brackets.insert(make_pair(')', '('));
	brackets.insert(make_pair('}', '{'));
	brackets.insert(make_pair(']', '['));
	
	for(string::iterator it = s.begin(); it != s.end(); ++it) {
		char c = *it;
		// 如果是右括号
		if(brackets.find(c) != brackets.end()) {
			// 栈为空或者栈顶元素与当前右括号不匹配,返回false
			if(stk.empty() || stk.top() != brackets[c]) {
				return false;
			}
			stk.pop(); 
		} else {
			stk.push(c);  // 左括号 
		}
	}
	return stk.empty();
}

int main() {
	string s;
	cin>>s;
	cout<<boolalpha<<isValid(s)<<endl;
	return 0;
}

21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例 1:

输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]

示例 2:

输入:l1 = [], l2 = []
输出:[]

示例 3:

输入:l1 = [], l2 = [0]
输出:[0]

提示:

  • 两个链表的节点数目范围是 [0, 50]
  • -100 <= Node.val <= 100
  • l1 和 l2 均按 非递减顺序 排列
#include<iostream>
using namespace std;


struct ListNode {
	int val;
	ListNode *next;
	ListNode() : val(0), next(NULL) {}
	ListNode(int x) : val(x), next(NULL) {}
	ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
	public:
		ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {  // 递归
			if(list1 == NULL) 
				return list2;
			if(list2 == NULL)
				return list1;
			if(list1->val < list2->val) {
				list1->next = mergeTwoLists(list1->next, list2);
				return list1;
			}else {
				list2->next = mergeTwoLists(list1, list2->next);
				return list2;
			}
		}
};

int main() {
    ListNode* list1 = NULL;
    ListNode* list2 = NULL;
    
    cout << "Enter elements for list1 (enter -1 to stop): ";
    int val;
    while (cin >> val && val != -1) {
        ListNode* node = new ListNode(val);
        if (list1 == NULL) {
            list1 = node;
        } else {
            ListNode* temp = list1;
            while (temp->next != NULL) {
                temp = temp->next;
            }
            temp->next = node;
        }
    }
    
    cout << "Enter elements for list2 (enter -1 to stop): ";
    while (cin >> val && val != -1) {
        ListNode* node = new ListNode(val);
        if (list2 == NULL) {
            list2 = node;
        } else {
            ListNode* temp = list2;
            while (temp->next != NULL) {
                temp = temp->next;
            }
            temp->next = node;
        }
    }
    
    Solution solution;
    ListNode* mergedList = solution.mergeTwoLists(list1, list2);
    
    // Print the merged list
    ListNode* temp = mergedList;
    cout << "Merged list: ";
    while (temp != NULL) {
        cout << temp->val << " ";
        temp = temp->next;
    }
    cout << endl;
    
    return 0;
}

22. 括号生成

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

示例 1:

输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]

示例 2:

输入:n = 1
输出:["()"]

提示:

  • 1 <= n <= 8
#include<iostream>
#include<vector>
using namespace std;

class Solution {
	public:
		void helper(vector<string>& result, string current, int open, int close, int n) {
			if(current.size() == 2 * n) {
				result.push_back(current);
				return;  // 递归结束 
			}
			
			if(open < n) {
				helper(result, current + "(", open + 1, close, n);
			}
			
			if(close < open) {
				helper(result, current + ")", open, close + 1, n);
			}
		}
		
		vector<string> generateParenthesis(int n) {
			vector<string> result;
			helper(result, "", 0, 0, n);
			return result;
		}
}; 

int main() {
	int n;
	cin >> n;
	Solution solution;
	vector<string> result = solution.generateParenthesis(n);
	cout << "[";
	for(auto it = result.begin(); it != result.end(); ++it) {
		if(it == result.end() - 1) {
			cout << *it;
		} else {
			cout << *it <<", ";
		}
	}
	cout << "]";
	return 0;
}

23. 合并K个升序链表

给你一个链表数组,每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中,返回合并后的链表。

示例 1:

输入:lists = [[1,4,5],[1,3,4],[2,6]]
输出:[1,1,2,3,4,4,5,6]
解释:链表数组如下:
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2:

输入:lists = []
输出:[]

示例 3:

输入:lists = [[]]
输出:[]

提示:

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i] 按 升序 排列
  • lists[i].length 的总和不超过 10^4

解题思路:要合并K个升序链表,可以使用优先队列(最小堆)来实现。首先将每个链表的头节点加入到优先队列中,然后不断从优先队列中取出最小的节点,将其加入到结果链表中,并将该节点的下一个节点加入到优先队列中。重复这个过程直到优先队列为空。

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

// Definition for singly-linked list
struct ListNode {
	int val;
	ListNode *next;
	ListNode() : val(0), next(NULL) {}
	ListNode(int x) : val(x), next(NULL) {}
	ListNode(int x, ListNode *next) : val(x), next(next) {}
};

struct compare {
	bool operator()(ListNode* a, ListNode* b) {
		return a->val > b->val;
	}
};

class Solution {
	public:
		ListNode* mergeKLists(vector<ListNode*>& lists) {
			priority_queue<ListNode*, vector<ListNode*>, compare> pq;
		
			for(ListNode* list : lists) {  // 添加各个链表的头节点 
				if(list) {
					pq.push(list);
				}
			}
			ListNode* dummy = new ListNode(0);
			ListNode* tail = dummy;
			
			while(!pq.empty()) {
				ListNode* node = pq.top();  // 获取堆顶元素
				pq.pop();
				tail->next = node;
				tail = tail->next;
				if(node->next) {
					// 把堆顶元素所在链表的下一个节点入队 
					pq.push(node->next);
				} 
			}
			return dummy->next; 
		}
};

ListNode* createList() {
	ListNode* head = NULL;
	ListNode* current = NULL;
	int val;
	while(cin >> val) {
		ListNode* newNode = new ListNode(val);
		if(head == NULL) {
			head = newNode;
			current = newNode;
		} else {
			current->next = newNode;
			current = newNode;
		}
		if(cin.get() == '\n')
			break;
	}
	return head;
}

void printList(ListNode* head) {
	ListNode* current = head;
	while(current != NULL) {
		cout << current->val << " ";
		current = current->next;
	}
}


int main() {
    vector<ListNode*> lists;
    int flag = 0;
    while(true) {
		cout << "请输入链表元素:";
    	ListNode* head = createList();
    	lists.push_back(head);
    	cout << "是否需要继续创建链表数组:0(继续), 1(结束):"; 
    	cin >> flag;
    	if(flag == 1) {  // flag = 1时,结束创建链表数组 
    		break;
		}
	}
    cout << "Merged List: ";
    Solution solution;
    ListNode* mergedList = solution.mergeKLists(lists);
    printList(mergedList);

    return 0;
}

24. 两两交换链表中的节点

给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。

示例 1:

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

示例 2:

输入:head = []
输出:[]

示例 3:

输入:head = [1]
输出:[1]

提示:

  • 链表中节点的数目在范围 [0, 100] 内
  • 0 <= Node.val <= 100
#include<iostream>
using namespace std;

// Definition for singly-linked list
struct ListNode {
	int val;
	ListNode *next;
	ListNode() : val(0), next(NULL) {}
	ListNode(int x) : val(x), next(NULL) {}
	ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
	public:
		ListNode* swapPairs(ListNode* head) {
			if(!head || !head->next) {
				return head;
			}
			ListNode *dummy = new ListNode(0);
			dummy->next = head;
			ListNode *prev = dummy;
			
			while(prev->next && prev->next->next) {
				ListNode *first = prev->next;
				ListNode *second = prev->next->next;
				
				prev->next = second;
				first->next = second->next;
				second->next = first;
				
				prev = first;
			}
			return dummy->next;
		}
};

ListNode* createList() {
	ListNode *head = NULL;
	ListNode *current = NULL;
	int val;
	while(cin >> val) {
		ListNode *newNode = new ListNode(val);
		if(head == NULL) {
			head = newNode;
			current = newNode;
		} else {
			current->next = newNode;
			current = current->next;
		}
		if(cin.get() == '\n') {
			break;
		}
	}
	return head;
}

void printList(ListNode *head) {
	ListNode *current = head;
	while(current != NULL) {
		cout << current->val << " ";
		current = current->next;
	}
}

int main() {
	Solution solution;
	ListNode *head = createList();
	ListNode *result = solution.swapPairs(head);
	printList(result);
	return 0;
	
}

25. K个一组翻转链表

给你链表的头节点 head ,每 k 个节点一组进行翻转,请你返回修改后的链表。

k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。

示例 1:

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

示例 2:

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

提示:

  • 链表中的节点数目为 n
  • 1 <= k <= n <= 5000
  • 0 <= Node.val <= 1000

进阶:你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗?

#include<iostream>
using namespace std;

// Definition for singly-linked list
struct ListNode {
	int val;
	ListNode *next;
	ListNode() : val(0), next(NULL) {}
	ListNode(int x) : val(x), next(NULL) {}
	ListNode(int x, ListNode *next) : val(x), next(next) {}
}; 

class Solution {
	public:
		ListNode* reverseKGroup(ListNode* head, int k) {
			if(!head || k == 1) {
				return head;
			}
			
			ListNode* dummy = new ListNode(0);
			dummy->next = head;
			ListNode* pre = dummy;
			int count = 0;
			ListNode* cur = head;
			
			while(cur) {
				count++;
				ListNode* nextNode = cur->next;
				if(count == k) {
					pre = reverse(pre, nextNode);  // 翻转 
					count = 0;
				}
				cur = nextNode;
			}
			return dummy->next;
		}
		
		
		ListNode* reverse(ListNode* pre, ListNode* end) {
			if(!pre || !pre->next || !pre->next->next) {
				return pre->next;
			}
			
			ListNode* head = pre->next;
			ListNode* cur = head->next;
			
			while(cur != end) {
				head->next = cur->next;
				cur->next = pre->next;
				pre->next = cur;
				cur = head->next;
			}
			return head;
		}
};

ListNode* createList() {
	ListNode *head = NULL;
	ListNode *current = NULL;
	int val;
	while(cin >> val) {
		ListNode *newNode = new ListNode(val);
		if(head == NULL) {
			head = newNode;
			current = newNode;
		} else {
			current->next = newNode;
			current = current->next;
		}
		if(cin.get() == '\n') {
			break;
		}
	}
	return head;
}

void printList(ListNode *head) {
	ListNode *current = head;
	while(current != NULL) {
		cout << current->val << " ";
		current = current->next;
	}
}

int main() {
	Solution solution;
	ListNode *head = createList();
	int k;
	cin >> k;
	ListNode *result = solution.reverseKGroup(head, k);
	printList(result);
	return 0;
}

26. 删除有序数组中的重复项

给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ,你需要做以下事情确保你的题解可以被通过:

  • 更改数组 nums ,使 nums 的前 k 个元素包含唯一元素,并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
  • 返回 k 。

判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有断言都通过,那么您的题解将被 通过

示例 1:

输入:nums = [1,1,2]
输出:2, nums = [1,2,_]
解释:函数应该返回新的长度 2,并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2:

输入:nums = [0,0,1,1,1,2,2,3,3,4]
输出:5, nums = [0,1,2,3,4]
解释:函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。不需要考虑数组中超出新长度后面的元素。

提示:

  • 1 <= nums.length <= 3 * 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums 已按 非严格递增 排列
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;


class Solution {
	public:
		int removeDuplicates(vector<int>& nums) {
			int size = nums.size();
			int left = 0, right = 1;
			while(--size) {
				if(nums[left] == nums[right]) {
					right++;
				} else {
					nums[left + 1] = nums[right];
					right++;
					left++;
				}
			}
			return left + 1;
		}
};

int main() {
	vector<int> nums;
	int temp;
	while(cin >> temp) {
		nums.push_back(temp);
		if(cin.get() == '\n')
			break;
	}
	Solution solution;
	cout<<solution.removeDuplicates(nums);
	return 0;
}

解法2:使用STL中的unique函数进行优化。unique函数可以将重复的元素移动到数组的末尾,并返回指向不重复部分的尾后迭代器。我们可以利用这个特性来简化代码。只需要调用unique函数,并返回结果与数组起始位置之间的距离,即为不重复元素的个数。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;


class Solution {
	public:
		int removeDuplicates(vector<int>& nums) {
			return distance(nums.begin(), unique(nums.begin(), nums.end()));
		}
};

int main() {
	vector<int> nums;
	int temp;
	while(cin >> temp) {
		nums.push_back(temp);
		if(cin.get() == '\n')
			break;
	}
	Solution solution;
	cout<<solution.removeDuplicates(nums);
	return 0;
}

解法3:在这个优化后的代码中,我们使用了两个指针left和right,其中left指针指向不重复部分的最后一个元素,right指针用于遍历数组。当遇到一个与left指针指向的元素不相同的元素时,将该元素移动到left指针的下一个位置,并将left指针后移一位。遍历完成后,left指针的位置加1即为不重复元素的个数。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;


class Solution {
	public:
		int removeDuplicates(vector<int>& nums) {
			int n = nums.size();
			if(n < 2) {
				return n;
			}
			int left = 0;
			for(int right = 1; right < n; right++) {
				if(nums[left] != nums[right]) {
					left++;
					nums[left] = nums[right];
				}
			}
			return left + 1;
		}
};

int main() {
	vector<int> nums;
	int temp;
	while(cin >> temp) {
		nums.push_back(temp);
		if(cin.get() == '\n')
			break;
	}
	Solution solution;
	cout<<solution.removeDuplicates(nums);
	return 0;
}

27. 移除元素

给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。

不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数,但输出的答案是数组呢?

请注意,输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说,不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1:

输入:nums = [3,2,2,3], val = 3
输出:2, nums = [2,2]
解释:函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如,函数返回的新长度为 2 ,而 nums = [2,2,3,3] 或 nums = [2,2,0,0],也会被视作正确答案。

示例 2:

输入:nums = [0,1,2,2,3,0,4,2], val = 2
输出:5, nums = [0,1,3,0,4]
解释:函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示:

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 50
  • 0 <= val <= 100
#include<iostream>
#include<vector>
using namespace std;

class Solution {
	public:
		int removeElement(vector<int>& nums, int val) {
			int j = 0;
			for(int i = 0; i < nums.size(); i++) {
				if(nums[i] != val) {
					nums[j++] = nums[i];  // 不需要考虑数组中超出新长度后面的元素
				}
			}
			return j;
		}
};

int main() {
	int val;
	int temp;
	vector<int> nums;
	while(cin >> temp) {
		nums.push_back(temp);
		if(cin.get() == '\n') {
			break;
		}
	}
	cin>>val;
	Solution solution;
	int len = solution.removeElement(nums, val);
	cout << len;
	return 0;
} 

28.找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分,则返回  -1 

示例 1:

输入:haystack = "sadbutsad", needle = "sad"
输出:0
解释:"sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ,所以返回 0 。

示例 2:

输入:haystack = "leetcode", needle = "leeto"
输出:-1
解释:"leeto" 没有在 "leetcode" 中出现,所以返回 -1 。

提示:

  • 1 <= haystack.length, needle.length <= 10^4
  • haystack 和 needle 仅由小写英文字符组成
#include<iostream>
#include<vector>
using namespace std;

class Solution {
	public:
		int strStr(string haystack, string needle) {
			return haystack.find(needle);
		}
};

int main() {
	string haystack, needle;
	cin >> haystack >> needle;
	Solution solution;
	cout<<solution.strStr(haystack, needle);
	return 0;
}

注:在C++中,string类的find()函数用于在一个字符串中查找子字符串,并返回第一次出现的位置find()函数有多种重载形式,常用的形式包括:

  1. size_t find(const string& str, size_t pos = 0) const: 在当前字符串中从指定位置pos开始查找子字符串str,返回第一次出现的位置。如果未找到则返回string::npos
  2. size_t find(const char* s, size_t pos = 0) const: 在当前字符串中从指定位置pos开始查找C风格字符串s,返回第一次出现的位置。如果未找到则返回string::npos
  3. size_t find(char c, size_t pos = 0) const: 在当前字符串中从指定位置pos开始查找字符c,返回第一次出现的位置。如果未找到则返回string::npos

示例用法:

#include <iostream>
#include <string>
using namespace std;

int main() {
    string str = "Hello, World!";
    
    // 查找子字符串
    size_t found = str.find("World");
    if (found != string::npos) {
        cout << "Found at position: " << found << endl;
    } else {
        cout << "Not found" << endl;
    }
    
    // 查找字符
    size_t foundChar = str.find(',');
    if (foundChar != string::npos) {
        cout << "Found character at position: " << foundChar << endl;
    } else {
        cout << "Character not found" << endl;
    }
    
    return 0;
}

29. 两数相除

给你两个整数,被除数 dividend 和除数 divisor。将两数相除,要求 不使用 乘法、除法和取余运算。

整数除法应该向零截断,也就是截去(truncate)其小数部分。例如,8.345 将被截断为 8 ,-2.7335 将被截断至 -2 。

返回被除数 dividend 除以除数 divisor 得到的  。

注意:假设我们的环境只能存储 32 位 有符号整数,其数值范围是 [−231,  231 − 1] 。本题中,如果商 严格大于 231 − 1 ,则返回 231 − 1 ;如果商 严格小于 -231 ,则返回 -231 。

示例 1:

输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = 3.33333.. ,向零截断后得到 3 。

示例 2:

输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = -2.33333.. ,向零截断后得到 -2 。

提示:

  • -2^31 <= dividend, divisor <= 2^31 - 1
  • divisor != 0
#include<iostream>
#include<climits>
using namespace std;

class Solution {
	public:
		int divide(int dividend, int divisor) {
			if(dividend == INT_MIN && divisor == -1) {
				return INT_MAX;
			}
			
			long dvd = labs(dividend);
			long dvs = labs(divisor);
			int sign = (dividend > 0) ^ (divisor > 0) ? -1 : 1;
			
			long res = 0;
			while(dvd >= dvs) {
				long temp = dvs, m = 1;
				while(temp<<1 <= dvd) {
					temp <<= 1;
					m <<= 1;  // 左移一位 
				}
				dvd = -= temp;
				res += m;
			}
			return sign * res;
		}
}; 

int main() {
	int dividend, divisor;
	cin >> dividend >> divisor;
	Solution solution;
	cout << solution.divide(dividend, divisor);
	return 0;
}

30. 串联所有单词的子串

给定一个字符串 s 和一个字符串数组 words words 中所有字符串 长度相同

 s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。

  • 例如,如果 words = ["ab","cd","ef"], 那么 "abcdef", "abefcd""cdabef", "cdefab""efabcd", 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串,因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例 1:

输入:s = "barfoothefoobarman", words = ["foo","bar"]
输出:[0,9]

解释:因为 words.length == 2 同时 words[i].length == 3,连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

示例 2:

输入:s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出:[]
解释:因为 words.length == 4 并且 words[i].length == 4,所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

示例 3:

输入:s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出:[6,9,12]
解释:因为 words.length == 3 并且 words[i].length == 3,所以串联子串的长度必须为 9。
子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。

提示:

  • 1 <= s.length <= 104
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 30
  • words[i] 和 s 由小写英文字母组成

解法一:超时版

#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
using namespace std;

class Solution {
	public:
		vector<int> findSubstring(string s, vector<string>& words) {
			vector<int> result;
			if(s.empty() || words.empty()) {
				return result;
			}
			
			int wordLen = words[0].length();
			int wordCount = words.size();
			int totalLen = wordLen * wordCount;
			unordered_map<string, int> wordFreq;
			
			for(const string& word : words) {
				wordFreq[word]++;
			}
			
			for(int i = 0; i <= (int)s.length() - totalLen; ++i) {
				unordered_map<string, int> seen;
				int j = 0;
				for(; j < wordCount; ++j) {
					string word = s.substr(i + j * wordLen, wordLen);
					if(wordFreq.find(word) == wordFreq.end()) {
						break;
					}
					seen[word]++;
					if(seen[word] > wordFreq[word]) {
						break;
					}
				}
				
				if(j == wordCount) {
					result.push_back(i);
				}
			}
			return result;
		}
};

int main() {
	string s;
	vector<string> words;
	string tmp;
	cin >> s;
	while(cin >> tmp) {
		words.push_back(tmp);
		if(cin.get() == '\n')
			break;
	} 
	Solution solution;
	vector<int> result = solution.findSubstring(s, words);
	for(auto num : result) {
		cout << num << " ";
	}
	return 0;
}

解法二:在每个可能的位置只遍历一次,使用滑动窗口来优化时间复杂度。

#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
using namespace std;

class Solution {
	public:
		vector<int> findSubstring(string s, vector<string>& words) {
			vector<int> result;
			if(s.empty() || words.empty()) {
				return result;
			}
			
			int wordLen = words[0].length();
			int wordCount = words.size();
			int totalLen = wordLen * wordCount;
			unordered_map<string, int> wordFreq;
			
			for(const string& word : words) {
				wordFreq[word]++;
			}
			
			for(int i = 0; i < wordLen; i++) {
				int left = i, count = 0;
				unordered_map<string, int> seen;
				
				for(int j = i; j <= (int)s.length() - totalLen; j += wordLen) {
					string word = s.substr(j, wordLen);
					if(wordFreq.find(word) != wordFreq.end()) {
						seen[word]++;
						count++;
						while(seen[word] > wordFreq[word]) {
							string temp = s.substr(left, wordLen);
							seen[temp]--;
							count--;
							left += wordLen;
						}
						
						if(count == wordCount) {
							result.push_back(left);
							string temp = s.substr(left, wordLen);
							seen[temp]--;
							count--;
							left += wordLen;
						}
					} else {
						seen.clear();
						count = 0;
						left = j + wordLen;
					}
					
				}
			}
			return result;
		}
};

int main() {
	string s;
	vector<string> words;
	string tmp;
	cin >> s;
	while(cin >> tmp) {
		words.push_back(tmp);
		if(cin.get() == '\n')
			break;
	} 
	Solution solution;
	vector<int> result = solution.findSubstring(s, words);
	for(auto num : result) {
		cout << num << " ";
	}
	return 0;
}

原题链接:题库 - 力扣 (LeetCode) 全球极客挚爱的技术成长平台

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/511046.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

直流电源电路(下)

直流电源电路&#xff08;下&#xff09; 综述&#xff1a;本篇文章讲述了直流电源电路的BOOST电路以及DC-DC电路的组成原理。 四、BOOST电路 原理&#xff1a;当mos导通时&#xff0c;电源上的电流给电感充电&#xff0c;通过mos管构成回路&#xff0c;电容放电给负载供电&…

从零实现一个Http服务器

HttpServer HTTPServer项目是一个基于C编写的简单的HTTP服务器实现&#xff0c;用于处理客户端的HTTP请求并提供相应的服务。该项目使用了Socket编程来实现服务器与客户端之间的通信&#xff0c;通过监听指定的端口并接受客户端连接&#xff0c;然后解析HTTP请求并生成对应的H…

Octavia Venture 成立,打造数十亿美元规模的 AI 价值体系

​随着 OpenAI 相继发布 ChatGPT、Sora 等 AIGC 大模型后&#xff0c;AI 赛道的发展迎来了一轮又一轮的热潮&#xff0c;这也让极具想象力的 AI 赛道涌入大量资金&#xff0c;比如英伟达股票市值短时间内从 1 万亿美元暴涨至 2 万亿美元&#xff0c;就是最好的佐证。当然&#…

Maven依赖管理项目构建工具

一、Maven简介 1、为什么学习Maven 1.1、Maven是一个依赖管理工具 ①jar 包的规模 随着我们使用越来越多的框架&#xff0c;或者框架封装程度越来越高&#xff0c;项目中使用的jar包也越来越多。项目中&#xff0c;一个模块里面用到上百个jar包是非常正常的。 比如下面的例…

表白墙项目(JAVA实现)

1、在html里 class使用. id使用# 2、记得引入响应依赖&#xff08;举例lombok&#xff09; 3、messageController package com.example.demo.demos.web; import org.springframework.util.StringUtils; import org.springframework.web.bind.annotation.RequestMapping; i…

惊喜!这一国产数据库认证考试限免了!

今年第一个季度过去了&#xff0c;又到春暖花开时&#xff0c;群里的小伙伴开始躁动不安&#xff0c;焦虑加倍。 有考虑被 cloud 淘汰的&#xff0c;有考虑被共享 emp 的&#xff0c;还有问粗粮 car 能不能当专车开的。 但技术人&#xff0c;更多时间还是在讨论正能量&#xff…

使用纯注解的方式管理bean对象

前置知识&#xff1a; Component , Repository , Controller , Service 这些注解只局限于自己编写的类&#xff0c;而Bean注解能把第三方库中的类实例加入IOC容器中并交给spring管理。 其中&#xff1a; Component一般用于公共类 Repository 用于dao数据访问层 Service 用…

基本电路理论入门讲解系列-电路和电路模型

&#x1f308;个人主页&#xff1a;会编程的果子君 &#x1f4ab;个人格言:“成为自己未来的主人~” 电路 电路概念&#xff1a;把若干个电气设备和电气元件按照一定的方式组合起来&#xff0c;构成电流的通路&#xff0c;此路径的总体称为电路。在电子通信&#xff0c;自…

Spring IoCDI(2)

IoC详解 通过上面的案例, 我们已经知道了IoC和DI的基本操作, 接下来我们来系统地学习Spring IoC和DI的操作. 前面我们提到的IoC控制反转, 就是将对象的控制权交给Spring的IoC容器, 由IoC容器创建及管理对象. (也就是Bean的存储). Bean的存储 我们之前只讲到了Component注解…

SpringBoot项目使用SpringSecurity和JWT实现登录功能

使用SpringSecurity,Redis实现登录功能 首先&#xff0c;思路如下&#xff1a; 登录 ①自定义登录接口 调用ProviderManager的方法进行认证 如果认证通过生成jwt 把用户信息存入redis中 ②自定义UserDetailsService 在这个实现类中去查询数据库 注意配置passwordEncoder为BCry…

数据结构进阶篇 之 【插入排序】详细讲解(直接插入排序,希尔排序)

千万不要因为一件事不会做而失去信心&#xff0c;你又不是只有这一件事不会&#xff0c;你还有很多呢 一、插入排序 1.直接插入排序 InsertSort 1.1 基本思想 1.2 实现原理 1.3 代码实现 1.4 直接插入排序的特性总结 2.希尔排序 ShellSort 2.1 基本思想 2.2 实现原理 …

视觉Transformer和Swin Transformer

视觉Transformer概述 ViT的基本结构&#xff1a; ①输入图片首先被切分为固定尺寸的切片&#xff1b; ②对展平的切片进行线性映射&#xff08;通过矩阵乘法对维度进行变换&#xff09;&#xff1b; ③为了保留切片的位置信息&#xff0c;在切片送入Transformer编码器之前&…

基于vue实现动态table

1、代码 <div style"height: 600px; overflow: scroll;"> <!-- height: 600px; overflow: scroll;作用是超出页面可以滑动 --><div ng-repeat"row in entity.procedureList"><cb-title title"工序{{row.procedireLocation}}&quo…

【保姆级讲解下MySQL中的drop、truncate和delete的区别】

&#x1f308;个人主页:程序员不想敲代码啊 &#x1f3c6;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f44d;点赞⭐评论⭐收藏 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共…

【面试八股总结】传输控制协议TCP(三)

参考资料 &#xff1a;小林Coding、阿秀、代码随想录 一、TCP拥塞控制⭐ 1. 慢启动 – Slow Start 慢启动是指TCP连接刚建立&#xff0c;一点一点地提速&#xff0c;试探一下网络的承受能力&#xff0c;以免直接扰乱了网络通道的秩序。 慢启动算法&#xff1a; 初始拥塞窗口…

OpenCV项目实战-深度学习去阴影-图像去阴影

往期热门博客项目回顾&#xff1a; 计算机视觉项目大集合 改进的yolo目标检测-测距测速 路径规划算法 图像去雨去雾目标检测测距项目 交通标志识别项目 yolo系列-重磅yolov9界面-最新的yolo 姿态识别-3d姿态识别 深度学习小白学习路线 //正文开始&#xff01; 图…

NoSQL(非关系型数据库)之Redis的简介与安装

一、简介 1.1 关系型数据库与非关系型数据库 1.1.1 概念 1.1.2 区别 1.2 非关系型数据库产生背景 1.3 redis 简介 1.4 redis 优点 1.5 redis 快的原因 二、安装 2.1 关闭核心防护 2.2 安装相关依赖 2.3 解压软件包并进行编译安装 2.4 设置 Redis 服务所需相关配置文…

聚道云软件连接器:助力企业财务效率提升的成功案例

客户介绍 某公司是一家实力雄厚的综合性企业&#xff0c;自成立以来&#xff0c;公司始终秉持着创新、务实、高效的经营理念&#xff0c;深耕多个领域&#xff0c;不断拓展业务版图&#xff0c;逐渐发展成为业界翘楚。公司经营范围广泛&#xff0c;涵盖了科技研发、生产制造、…

【保姆级讲解下Docker容器】

&#x1f308;个人主页:程序员不想敲代码啊 &#x1f3c6;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f44d;点赞⭐评论⭐收藏 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共…

数据分析:品牌如何借势小红书热点?

导语 近期&#xff0c;一碗麻辣烫&#xff0c;让甘肃天水成为了不少人旅行计划单上的榜首&#xff0c;各地食客心甘情愿地排队5、6个小时&#xff0c;赶赴一场“麻辣烫之约”。千瓜数据&#xff0c;近30天浏览量破500W&#xff0c;且增势迅猛。 图 | 千瓜数据 去有人的地方 &…