当前位置： 首页 > news >正文

leetcode 刷题1

news 2025/8/16 10:28:22

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 <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • 只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

//我的解法：双指针class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {//定义左右指针int left = 0, right = nums.size()-1;int n = nums.size();int a[n];for(int i=0; i<n; ++i){a[i] = nums[i];}//排序sort(a, a+n);int sum;vector<int> ans;ans.clear();int le, re;while(1){sum = a[left]+a[right];if(sum > target){--right;}else if(sum < target){++left;}else{le = a[left];re = a[right];break;}}//在原数组中寻找这两个元素的位置for(int i=0; i<n; ++i){if(nums[i]==le){ans.push_back(i);break;}}for(int i=n-1; i>=0; --i){if(nums[i]==re){ans.push_back(i);break;}}return ans;}
};

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
  • 题目数据保证列表表示的数字不含前导零
class Solution {
public:ListNode* plus(ListNode* l1, ListNode* l2, int i){//判断为空的情况if(l1==NULL && l2==NULL && i==0){return NULL;}//将两个链表的数据用整形表示int value = i;if(l1!=NULL){value += l1->val;}if(l2!=NULL){value += l2->val;}//存储个位数字ListNode* result = new ListNode(value%10);//递归处理result->next = plus(l1==NULL?NULL:l1->next, l2==NULL?NULL:l2->next, value>=10?1:0);return result;}ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* ans = plus(l1, l2, 0);return ans;}
};

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 * 104
  • s 由英文字母、数字、符号和空格组成
class Solution {
public:int lengthOfLongestSubstring(string s) {string queue;  //非重复队列，本问题的解即为该队列的长度int ans = 0;for(int i=0; i<s.size(); ++i){//入队前检查是否已经在队列中，如果已经在队列中，该队列从头删除元素来保持非重复特性while(!queue.empty() && queue.find(s[i])!=string::npos){queue.erase(queue.begin());}queue.push_back(s[i]);int len = queue.size();ans = max(ans,len);}return ans;  }
};

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成
class Solution {
public:string longestPalindrome(string s) {string res;for(int i=0; i<s.size(); ++i){//枚举中心点，奇数长度回文子串for(int j=i,k=i; j>=0&&k<s.size()&&s[j]==s[k]; --j,++k){if(k-j+1 > res.size()){res = s.substr(j,k-j+1);}}}for(int i=0; i<s.size(); ++i){//枚举中心点，偶数长度回文子串for(int j=i,k=i+1; j>=0&&k<s.size()&&s[j]==s[k]; --j,++k){if(k-j+1 > res.size()){res = s.substr(j,k-j+1);}}}return res;}
};

6. 

将一个给定字符串 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
class Solution {
public:
/*
下标有规律：
第一行：首项是0，公差是2（n-1）的等差数列
中间n-2行：两个等差数列交错
最后一行：首项是n-1，公差是2（n-1）的等差数列
*/string convert(string s, int n) {if(n == 1) return s;string res;//i表示每一行的起始坐标for(int i=0; i<n; ++i){if(i==0 || i==n-1){    //第一行或最后一行int j = i;while(j<s.size()){res += s[j];j += 2*(n-1);}}else{//j,k初值，可通过例子确定，关于k的初值，因为是从下到上的遍历，所以因子有n-iint j = i, k = i + 2*(n-i-1);   while(j<s.size() || k<s.size()){if(j<s.size()) res += s[j];if(k<s.size()) res += s[k];j += 2*(n-1);k += 2*(n-1);}}}return res;}
};

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

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

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

示例 1：

输入：x = 121
输出：true

示例 2：

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

示例 3：

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

提示：

  • -231 <= x <= 231 - 1

进阶：你能不将整数转为字符串来解决这个问题吗？

class Solution {
public:bool isPalindrome(int x) {char c[100];string s, s1;sprintf(c, "%d", x);    //将数字转换为字符串s = c;s1 = c;reverse(s.begin(), s.end());    //字符串反转if(s1 == s){return true;}else{return false;}}
};

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

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] 如果非空，则仅由小写英文字母组成
//我的解法：求交集
class Solution {
public:string longestCommonPrefix(vector<string>& strs) {if(strs.empty()) return "";    //样例为空的情况string res = strs[0];    //res表示公共前缀for(int i=1; i<strs.size(); ++i){//L表示公共长度int L = min(res.size(), strs[i].size());    while(L){if(res.substr(0, L) == strs[i].substr(0, L)){res = strs[i].substr(0, L);    //当前的公共前缀break;}L--;    //不断减小公共长度}if(L==0) return "";}return res;}
};

19. 

给你一个链表，删除链表的倒数第 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

进阶：你能尝试使用一趟扫描实现吗？

/*** 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;int i = 0;//先让p2跑一段距离while(i < n){p2 = p2->next;++i;}//p1,p2同步跑，确定要删除的结点while(p2 != NULL){p1 = p1->next;p2 = p2->next;}//结点的删除操作ListNode* tmp = head;head = (ListNode *)malloc(sizeof(ListNode));//把head作为虚拟头节点，以便删除第一个结点head->next = tmp;ListNode* pre = head;ListNode* p = pre;while(p != NULL){if(p == p1){//删除操作pre->next = p->next;}else{//更新pre指针pre = p;}//遍历p = p->next;}return head->next; }
};

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 均按 非递减顺序 排列
//考研408经典题目/*** Definition for singly-linked list.* 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* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode* l3 = new ListNode(0);ListNode* p1 = l1;ListNode* p2 = l2;ListNode* p3 = l3;while(p1!=NULL && p2!=NULL){//不断挂接小的结点到结果链表中if(p1->val < p2->val){p3->next = new ListNode(p1->val);p3 = p3->next;p1 = p1->next;}else{p3->next = new ListNode(p2->val);p3 = p3->next;p2 = p2->next;}}//挂接剩余结点if(p1!=NULL){p3->next = p1;}if(p2!=NULL){p3->next = p2;}return l3->next;}
};

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 * 104
  • -104 <= nums[i] <= 104
  • nums 已按 非严格递增 排列
//经典题目：覆盖前面的元素
class Solution {
public:int removeDuplicates(vector<int>& nums) {if(nums.empty()) return 0;int k = 1;    //k表示非重复元素的索引for(int i=1; i<nums.size(); ++i){if(nums[i] != nums[k-1])     //不相等的话索引就同步增长nums[k++] = nums[i];}return k;}
};

27. 

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

  • 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
  • 返回 k。

用户评测：

评测机将使用以下代码测试您的解决方案：

int[] nums = [...]; // 输入数组
int val = ...; // 要移除的值
int[] expectedNums = [...]; // 长度正确的预期答案。// 它以不等于 val 的值排序。int k = removeElement(nums, val); // 调用你的实现assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i = 0; i < actualLength; i++) {assert nums[i] == expectedNums[i];
}

如果所有的断言都通过，你的解决方案将会 通过。

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

提示：

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 50
  • 0 <= val <= 100
//跟上一题思路基本一致
class Solution {
public:int removeElement(vector<int>& nums, int val) {int k = 0;for(int i=0; i<nums.size(); ++i){if(nums[i] != val){nums[k++] = nums[i];}}return k;}
};

给你两个字符串 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 <= 104
  • haystack 和 needle 仅由小写英文字符组成
//调用find函数
class Solution {
public:int strStr(string haystack, string needle) {if(haystack.find(needle) != string::npos){return haystack.find(needle);}else{return -1;}}
};

33. 

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 向左旋转 3 次后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：

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

提示：

  • 1 <= nums.length <= 5000
  • -104 <= nums[i] <= 104
  • nums 中的每个值都 独一无二
  • 题目数据保证 nums 在预先未知的某个下标上进行了旋转
  • -104 <= target <= 104
class Solution {
public:int search(vector<int>& nums, int target) {if(nums.empty()) return -1;int l = 0, r = nums.size() - 1;//l, r 括住最小的元素while(l < r){int mid = (l + (long long)r) >> 1;if(nums[mid] <= nums.back()){r = mid;    //mid位置满足条件，用mid缩小右边界}else{l = mid + 1;    //mid位置元素不满足条件，左边界+1，以期满足条件}}if(target <= nums.back()){    //说明在右半部分l = r, r = nums.size()-1;}else{                        //说明在左半部分l = 0, r--;}while(l < r){int mid = (l + (long long)r) >> 1;if(target <= nums[mid]){r = mid;}else{l = mid + 1;}}if(nums[l] != target){return -1;}else{return l;}}
};

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

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

提示：

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • nums 是一个非递减数组
  • -109 <= target <= 109
class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if(nums.empty()) return {-1,-1};vector<int> ans;int l = 0, r = nums.size()-1;//寻找左坐标while(l < r){//向下取整int mid = (l+(long long)r) >> 1;if(nums[mid] >= target){r = mid;}else{l = mid+1;}}if(nums[l] != target) return {-1,-1};ans.push_back(l);        l = 0, r = nums.size()-1;//寻找右坐标while(l < r){//向上取整，否则对于如下标为a和a+1会陷入死循环int mid = (l+(long long)r+1) >> 1;if(nums[mid] <= target){l = mid;}else{r = mid-1;}}ans.push_back(r);return ans;}
};

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

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

示例 2:

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

示例 3:

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

提示:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums 为 无重复元素 的 升序 排列数组
  • -104 <= target <= 104
class Solution {
public:int searchInsert(vector<int>& nums, int target) {if(target <= nums[0]) return 0;if(target > nums[nums.size()-1]) return nums.size();int l = 0, r = nums.size()-1;while(l < r){//向下取整，找到最左边满足条件的位置int mid = (l + (long long)r) >> 1;if(nums[mid] >= target){r = mid;}else{l = mid+1;}}return l;}
};

37. 

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1：

输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

提示：

  • board.length == 9
  • board[i].length == 9
  • board[i][j] 是一位数字或者 '.'
  • 题目数据 保证 输入数独仅有一个解

http://www.lryc.cn/news/622090.html

相关文章：

  • Chrome插件开发全指南
  • 【fwk基础】repo sync报错后如何快速修改更新
  • 集成电路学习：什么是Object Detection目标检测
  • Linux学习-软件编程（进程与线程）
  • Java生态中，实现MCP（Model Context Protocol）服务端工具开发主要的两大主流框架选择
  • 从前端框架到GIS开发系列课程（25）mapbox基础介绍以及加载第三方底图高德地图的实现
  • 数据结构初阶：排序算法（二）交换排序
  • ffmpeg-调整视频分辨率
  • 计算机视觉（opencv）实战五——图像平滑处理（均值滤波、方框滤波、高斯滤波、中值滤波）附加：视频逐帧平滑处理
  • Unity中的延迟调用方法详解
  • [微服务]ELK Stack安装与配置全指南
  • STM32在使用DMA发送和接收时的模式区别
  • 机器学习之 KNN 算法学习总结
  • YTHDC1介导MAFF核输出减轻肝细胞缺血再灌注氧化应激损伤
  • exec函数族、线程
  • 新手入门Makefile：FPGA项目实战教程（二）
  • 【计算机视觉与深度学习实战】02基于形态学的权重自适应图像去噪系统
  • 大模型 + 垂直场景：搜索 / 推荐 / 营销 / 客服领域开发有哪些新玩法？
  • 短剧小程序系统开发：打造个性化娱乐新体验
  • Apache 如何支持SHTML(SSI)的配置方法
  • 告别手动优化！React Compiler 自动记忆化技术深度解析
  • Docker部署Spring Cloud微服务实战
  • vue一个超简单的菜单栏伸缩示例
  • 剧本杀小程序系统开发：重构推理娱乐生态
  • C语言第八章指针五
  • linux服务器查看某个服务启动，运行的时间
  • Chrome插件开发
  • 最长递增子序列-dp问题+二分优化
  • 智能巡检技术浅析
  • 最新chrome浏览器elasticsearch-head无法安装使用问题