算法学习——LeetCode力扣补充篇2

724. 寻找数组的中心下标

724. 寻找数组的中心下标 - 力扣（LeetCode）

描述

给你一个整数数组 nums ，请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。

示例

示例 1：

输入：nums = [1, 7, 3, 6, 5, 6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。

示例 2：

输入：nums = [1, 2, 3]
输出：-1
解释：
数组中不存在满足此条件的中心下标。

示例 3：

输入：nums = [2, 1, -1]
输出：0
解释：
中心下标是 0 。
左侧数之和 sum = 0 ，（下标 0 左侧不存在元素），
右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。

提示

1 <= nums.length <= 104
-1000 <= nums[i] <= 1000

代码解析

class Solution {
public:int pivotIndex(vector<int>& nums) {int result = -1;int sum = 0 , left_sum=0;for(int it:nums) sum += it;for(int i=0 ; i<nums.size() ;i++){if((sum-nums[i])%2 ==0  && (sum-nums[i])/2 == left_sum ) return i;else left_sum += nums[i];}return result;}
};

34. 在排序数组中查找元素的第一个和最后一个位置

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

描述

给你一个按照非递减顺序排列的整数数组 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) {int left = -1 ,right = -1;for(int i=0 , j=nums.size()-1 ; i<nums.size(); i++ ,j-- ){if(left == -1 && nums[i] == target ) left = i;if(right == -1 && nums[j] == target) right = j;} return {left, right};}
};

二分查找

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int left = -1 , right = -1;int left_ptr = 0 , right_ptr = nums.size()-1;int mid = 0;while (left_ptr <= right_ptr){mid = (left_ptr + right_ptr)/2;if(nums[mid] == target) break;else if(nums[mid] > target ) right_ptr = mid-1;else if(nums[mid] < target ) left_ptr = mid+1;}for(int i=mid , j=mid ; i>=0 , j<nums.size();i--,j++){if(i>0 && nums[i] == target && nums[i-1] != target) left = i;else if(i==0 && nums[i] == target) left = i;if(j<nums.size()-1 && nums[j] == target && nums[j+1] != target) right = j;else if(j==nums.size()-1 && nums[j] == target) right = j;if(left != -1 && right != -1) break;}return {left,right};}
};

922. 按奇偶排序数组 II

922. 按奇偶排序数组 II - 力扣（LeetCode）

描述

给定一个非负整数数组 nums， nums 中一半整数是 奇数 ，一半整数是 偶数 。

对数组进行排序，以便当 nums[i] 为奇数时，i 也是 奇数 ；当 nums[i] 为偶数时， i 也是 偶数 。

你可以返回 任何满足上述条件的数组作为答案 。

示例

示例 1：

输入：nums = [4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。

示例 2：

输入：nums = [2,3]
输出：[2,3]

提示

2 <= nums.length <= 2 * 104
nums.length 是偶数
nums 中一半是偶数
0 <= nums[i] <= 1000

代码解析

class Solution {
public:vector<int> sortArrayByParityII(vector<int>& nums) {sort(nums.begin() , nums.end());vector<int> result(nums.size() , 0);int left = 0 ,right = 1;for(int i=0 ; i<nums.size() ;i++){if(nums[i]%2 == 0){result[left] = nums[i];left += 2;}else{result[right] = nums[i];right += 2;}}return result;}
};

35. 搜索插入位置

35. 搜索插入位置 - 力扣（LeetCode）

描述

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

请必须使用时间复杂度为 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) {for(int i=0 ; i<nums.size() ;i++){if(nums[i] >= target ) return i;}return nums.size();}
};

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

24. 两两交换链表中的节点 - 力扣（LeetCode）

描述

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

示例

示例 1：

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

示例 2：

输入：head = []
输出：[]

示例 3：

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

提示

链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100

代码解析

/*** 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* swapPairs(ListNode* head) {ListNode* pre, * cur, *temp ,*aft,*pre2,*head_test;if (head == nullptr || head->next == nullptr)return head;ListNode test(0,nullptr);head_test = head->next;pre = head;pre2 = &test;cur = pre->next;while (cur){aft = cur->next;if (pre != nullptr|| cur != nullptr){temp = cur->next;cur->next = pre;pre->next = temp;pre2->next = cur;}else break;pre2 = pre;pre = aft;if (pre != nullptr)cur = pre->next;else break;}return head_test;}
};

234. 回文链表

234. 回文链表 - 力扣（LeetCode）

描述

给你一个单链表的头节点 head ，请你判断该链表是否为
回文链表
。如果是，返回 true ；否则，返回 false 。

示例

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

提示

链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9

代码解析

/*** 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:bool isPalindrome(ListNode* head) {stack<int> mystack;int node_num = 0;ListNode *tmp = head;while(tmp != nullptr){tmp = tmp->next;node_num ++;}tmp = head;for(int i=1 ; i<=node_num ;i++){if(i<=node_num/2) mystack.push(tmp->val);if(i>node_num/2+node_num%2){if(tmp->val != mystack.top()) return false;mystack.pop();} tmp = tmp->next;}return true;}
};