力扣｜面试题 ｜task01

本文主要是介绍力扣｜面试题 ｜task01，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

螺旋矩阵 L54

难点在于定义遍历的边界
注意的点：

1. 对于空数组立刻返回结果
2. 定义四个变量变化遍历的边界，四个变量
3. 使用while循环控制四个循环一直执行，四个循环中判断跳出while循环的条件

class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {vector<int> ans;
if(matrix.empty())return ans;//数组为空则返回int u=0,l=0;//u 行 l列起始
int row=matrix.size()-1;
int column=matrix[0].size()-1;while(true){for(int i=l;i<=column;++i)
ans.push_back(matrix[u][i]); //in the first towards rightif(++u>row)break;//  上边界大于下边界，则遍历完成for(int i=u;i<=row;++i)ans.push_back(matrix[i][column]); // in the second towards down
if(--column<l)break;for(int i=column;i>=l;--i)ans.push_back(matrix[row][i]);//in the third towards right
if(--row<u)break;for(int i=row;i>=u;--i)ans.push_back(matrix[i][l]);//in the fourth towards up
if(++l>column)break;}return ans;}
};};**/

48 旋转图像

原地开辟一个数组，填入旋转后的元素，将新数组的元素赋值给旧数组

class Solution {
public:void rotate(vector<vector<int>>& matrix) {
int n=matrix.size();
auto newMatrix=matrix;for(int i=0;i<n;i++){for(int j=0;j<n;j++){newMatrix[j][n-i-1]=matrix[i][j];}}     matrix=newMatrix;}
};

215 数组中第k个最大元素

使用快速选择排序

 int sort(int left,int right,vector<int>& nums){  //   快排中一趟划分int temp = nums[left];      //将当前表中第一个元素设为枢纽，对表进行划分while(left < right){while(left < right && nums[right] >= temp) right--;nums[left] = nums[right];       //将比枢纽小的元素移动到左端while(left < right && nums[left] <= temp) left++;       //将比枢纽大的元素移动到右端nums[right] = nums[left];}nums[left] = temp;      //枢纽元素存放到最终位置return left;            //返回枢纽元素的最终位置}int quickSort(int left,int right,vector<int>& nums,int k){int mid = sort(left,right,nums);if(mid  == nums.size() - k)      //第K大元素，返回return nums[mid];           else if(mid  > nums.size() - k)     //第K大元素在mid左边，则对mid左边继续划分，找出第K大元素return quickSort(left,mid - 1,nums,k);else                                //第K大元素在mid右边，则对mid右边继续划分，找出第K大元素return quickSort(mid + 1,right,nums,k);}int findKthLargest(vector<int>& nums, int k) {return quickSort(0,nums.size() - 1,nums,k);}

912 排序数组

普通的快速选择排序是不符合题目要求的，需要将代码优化才能通过
希尔排序的做法
希尔排序逐渐缩小增量，是直接插入排序的一种特殊情况。
最后一个循环的时候增量为1

class Solution {
public:vector<int> sortArray(vector<int>& nums) {int n=nums.size();int b=n/2;//设置增量while(b>=1){for(int i=1;i<n;i++){sort(b,nums,i);}b/=2;}return nums;}void sort(int b,vector<int>&nums,int i){//直接插入排序int tem=nums[i];while(i>=b&&nums[i-b]>tem){nums[i]=nums[i-b];i-=b;}nums[i]=tem;}
};

88 合并两个有序数组

将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
使用双指针的方法

class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int i=0,j=0;int sorted[m+n];int cur=0;while(i<m&&j<n){if(nums1[i]<nums2[j])sorted[cur++]=nums1[i++];else sorted[cur++]=nums2[j++];}    while(i<m){sorted[cur++]=nums1[i++];}  while(j<n){sorted[cur++]=nums2[j++];}  
for(int i=0;i<m+n;i++){nums1[i]=sorted[i];
}}
};

169 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

使用随机化方法，随便挑一个元素数这个元素的个数，如果个数符合题意则返回

class Solution {
public:int majorityElement(vector<int>& nums) {while(true){int pivot=nums[rand()%nums.size()];int cnt=0;for(int num:nums){if(num==pivot)cnt++;}if(cnt>nums.size()/2)return pivot;}return -1;}
};

136 只出现一次的数字

解题思路跟上面的类似，故不过多赘述

class Solution {
public:int singleNumber(vector<int>& nums) {
while(true){
int pivot=nums[rand()%nums.size()];int cnt=0;for(int num:nums){
if(num==pivot)cnt++;}if(cnt==1)return pivot;
}return -1;}
};

56 合并区间[to be settle]

描述：给定数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。

要求：合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

    vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end());vector<vector<int>> ans;for (int i = 0; i < intervals.size();) {int t = intervals[i][1];int j = i + 1;while (j < intervals.size() && intervals[j][0] <= t) {t = max(t, intervals[j][1]);j++;}ans.push_back({ intervals[i][0], t });i = j;}return ans;}

179 出现最大的数✨

要求：重新排列数组中每个数的顺序，使之将数组中所有数字按顺序拼接起来所组成的整数最大。

使用快速排序比较字符串的大小

class Solution {
public:string largestNumber(vector<int>& nums) {vector<string> strs;for (int i = 0; i < nums.size(); i++)strs.push_back(to_string(nums[i]));quickSort(strs, 0, strs.size() - 1);if (strs[strs.size() - 1] == "0")return "0";string res;for (int i = nums.size() - 1; i >=0; i--)res.append(strs[i]);return res;}
private:void quickSort(vector<string>& strs, int l, int r) {if (l >= r) return;int i = l, j = r;while (i < j) {while (strs[j] + strs[l] >= strs[l] + strs[j] && i < j) j--;while (strs[i] + strs[l] <= strs[l] + strs[i] && i < j) i++;swap(strs[i], strs[j]);}swap(strs[i], strs[l]);quickSort(strs, l, i - 1);quickSort(strs, i + 1, r);}
};

704 二分查找

class Solution {
public:int search(vector<int>& nums, int target) {
int l=0,r=nums.size()-1;while(l<=r){int mid=(r-l)/2+l;if(nums[mid]==target)return mid;else if(nums[mid]<target){l=mid+1;}else{r=mid-1;}}return -1;}
};

34 ✨排序数组指定元素第一个和最后一个位置

class Solution { 
public:int binarySearch(vector<int>& nums, int target, bool lower) {int left = 0, right = (int)nums.size() - 1, ans = (int)nums.size();while (left <= right) {int mid = (left + right) / 2;if (nums[mid] > target || (lower && nums[mid] >= target)) {right = mid - 1;ans = mid;} else {left = mid + 1;}}return ans;}vector<int> searchRange(vector<int>& nums, int target) {int leftIdx = binarySearch(nums, target, true);int rightIdx = binarySearch(nums, target, false) - 1;if (leftIdx <= rightIdx && rightIdx < nums.size() && nums[leftIdx] == target && nums[rightIdx] == target) {return vector<int>{leftIdx, rightIdx};} return vector<int>{-1, -1};}
};

153 旋转数组的最小值

class Solution {
public:int findMin(vector<int>& nums) {
int low =0;
int high=nums.size()-1;while(low<high){int pivot=low+(high-low)/2;if(nums[pivot]<nums[high]){high=pivot;}else{low=pivot+1;}}    return nums[low];}
};

这篇关于力扣｜面试题 ｜task01的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---