iis 多网站安全设置,做网站的的人收入多少钱,江苏省住房和城市建设厅网站,北京清控人居建设集团网站算法学习——LeetCode力扣补充篇9 912. 排序数组
912. 排序数组 - 力扣#xff08;LeetCode#xff09;
描述
给你一个整数数组 nums#xff0c;请你将该数组升序排列。
示例
示例 1#xff1a;
输入#xff1a;nums [5,2,3,1] 输出#xff1a;[1,2,3,5]
示例 2LeetCode
描述
给你一个整数数组 nums请你将该数组升序排列。
示例
示例 1
输入nums [5,2,3,1] 输出[1,2,3,5]
示例 2
输入nums [5,1,1,2,0,0] 输出[0,0,1,1,2,5]
提示
1 nums.length 5 * 104 -5 * 104 nums[i] 5 * 104
代码解析
冒泡排序
class Solution {
public:vectorint sortArray(vectorint nums) {for(int i0 ; inums.size() ; i){for(int ji ; jnums.size();j){if(nums[i] nums[j]) swap(nums[i],nums[j]);}}return nums;}
};快速排序
class Solution {
public:void quickSort(vectorint nums,int left ,int right){int mid_value nums[left (right-left)/2] ;int i left ;int j right;while(i j){while(nums[i] mid_value) i;while(nums[j] mid_value) j--;if(i j){int tmp nums[j];nums[j] nums[i];nums[i] tmp;i;j--;}}if(left j) quickSort(nums,left,j);if(i right) quickSort(nums,i,right);}vectorint sortArray(vectorint nums) {quickSort(nums,0,nums.size()-1);return nums;}
};归序并排
class Solution {vectorint tmp;void mergeSort(vectorint nums, int l, int r) {if (l r) return;int mid (l r) 1;mergeSort(nums, l, mid);mergeSort(nums, mid 1, r);int i l, j mid 1;int cnt 0;while (i mid j r) {if (nums[i] nums[j]) {tmp[cnt] nums[i];}else {tmp[cnt] nums[j];}}while (i mid) {tmp[cnt] nums[i];}while (j r) {tmp[cnt] nums[j];}for (int i 0; i r - l 1; i) {nums[i l] tmp[i];}}
public:vectorint sortArray(vectorint nums) {tmp.resize((int)nums.size(), 0);mergeSort(nums, 0, (int)nums.size() - 1);return nums;}
};
21. 合并两个有序链表
21. 合并两个有序链表 - 力扣LeetCode
描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例
示例 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 均按 非递减顺序 排列
代码解析
/*** 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* list1, ListNode* list2) {ListNode *head new ListNode;ListNode *tmp head;while(list1 ! nullptr || list2 ! nullptr){if((list1 ! nullptr list2 ! nullptr list1-val list2-val)||(list1 ! nullptr list2 nullptr)){tmp-next list1;tmp tmp-next;list1 list1-next;}if((list1 ! nullptr list2 ! nullptr list1-val list2-val)||(list1 nullptr list2 ! nullptr)){tmp-next list2;tmp tmp-next;list2 list2-next;}}return head-next;}
};33. 搜索旋转排序数组
33. 搜索旋转排序数组 - 力扣LeetCode
描述
整数数组 nums 按升序排列数组中的值 互不相同 。
在传递给函数之前nums 在预先未知的某个下标 k0 k nums.length上进行了 旋转使数组变为 [nums[k], nums[k1], …, 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(vectorint nums, int target) {for(int i0 ; inums.size() ;i)if(nums[i] target) return i;return -1;}
};二分查找法
class Solution {
public:int find(vectorint nums, int target , int left ,int right){if(left right) return -1;if(nums[right] nums[left] nums[left] target) return -1;else if(nums[right] nums[left] nums[right] target) return -1;if(left right nums[left] target) return left;else if(left right nums[left] ! target) return -1;int mid (leftright)/2;if(nums[mid] target) return mid;if(left right){int left_value find(nums,target,left,mid-1);int right_value find(nums,target,mid1,right);if(left_value ! -1) return left_value;if(right_value ! -1) return right_value;}return -1;}int search(vectorint nums, int target) {return find(nums,target,0,nums.size()-1);}
};103. 二叉树的锯齿形层序遍历
103. 二叉树的锯齿形层序遍历 - 力扣LeetCode
描述
给你二叉树的根节点 root 返回其节点值的 锯齿形层序遍历 。即先从左往右再从右往左进行下一层遍历以此类推层与层之间交替进行。
示例
示例 1
输入root [3,9,20,null,null,15,7] 输出[[3],[20,9],[15,7]]
示例 2
输入root [1] 输出[[1]]
示例 3
输入root [] 输出[]
提示
树中节点数目在范围 [0, 2000] 内 -100 Node.val 100
代码解析
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vectorvectorint zigzagLevelOrder(TreeNode* root) {queueTreeNode* my_que;vectorvectorint result;if(root nullptr) return result;bool flag false;my_que.push(root);while(my_que.size() ! 0){int size my_que.size();vectorint tmp;for(int i0 ; isize ;i){TreeNode* tmp_node my_que.front();my_que.pop();tmp.push_back(tmp_node-val);if(tmp_node-left ! nullptr) my_que.push(tmp_node-left);if(tmp_node-right ! nullptr) my_que.push(tmp_node-right);}if(flag true) reverse(tmp.begin(),tmp.end());result.push_back(tmp);flag !flag;tmp.clear();}return result;}
};
