38.日常算法

1.最短无序连续子数组

题目来源
给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。请你找出符合题意的 最短 子数组，并输出它的长度。

示例 1：
输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

class Solution {
public:int findUnsortedSubarray(vector<int>& nums) {int left = 0;int minx = INT_MAX;// 找左端点，表示以left右的数组已经排好序了// 如果右边已经排好序了，num[i]一定会小于右边排好序的最小值for (int i = nums.size() - 1; i >= 0; --i){minx = min(nums[i], minx);if (nums[i] > minx) left = i;}// 找右端点，表示以right左的数组已经排好序了// 如果左边已经排好序了，num[i]一定会大于左边排好序的最大值int right = -1;int maxx = INT_MIN;for (int i = 0; i < nums.size(); ++i){maxx = max(maxx, nums[i]);if (nums[i] < maxx) right = i;}return right == -1 ? 0 : right - left + 1;}
};

1. 螺旋矩阵 II

题目来源
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

class Solution {
public:vector<vector<int>> generateMatrix(int n) {int maxnum = n * n;vector<vector<int>> diction = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};vector<vector<int>> ret(n, vector<int>(n));int idx = 0;int row = 0, col = 0;for (int i = 1; i <= maxnum; ++i){ret[row][col] = i;int newrow = row + diction[idx][0], newcol = col + diction[idx][1];if (newrow >= n || newrow < 0 || newcol >= n || newcol < 0 || ret[newrow][newcol] != 0){++idx;idx %= 4;}row = row + diction[idx][0], col = col + diction[idx][1];}return ret;}
};