1. 给你一个整数数组 arr 和两个整数 k 和 threshold 。 请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。
示例 1：
输入：arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4 输出：3 解释：子数组 [2,5,5],[5,5,5] 和 [5,5,8] 的平均值分别为 4，5 和 6 。其他长度为 3 的子数组的平均值都小于 4（threshold 的值)。
示例 2：
输入：arr = [1,1,1,1,1], k = 1, threshold = 0 输出：5
示例 3：
输入：arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5 输出：6 解释：前 6个长度为 3 的子数组平均值都大于 5 。注意平均值不是整数。
示例 4：
输入：arr = [7,7,7,7,7,7,7], k = 7, threshold = 7 输出：1
示例 5：
输入：arr = [4,4,4,4], k = 4, threshold = 1 输出：1
提示：
1 <= arr.length <= 10^5 1 <= arr[i] <= 10^4 1 <= k <= arr.length 0 <=threshold <= 10^4
//子数组和子序列是不同的概念，要分清，明白了什么是子数组该题就很简单 class Solution { public: int numOfSubarrays(vector<int>& arr, int k, int threshold) { int result=0; int count=0; for(int i=0;i<k;i++) result+=arr[i]; if(result>=k*threshold)count++; for(int i=k;i<arr.size();i++) { result-=arr[i-k]; result+=arr[i]; if(result>=k*threshold)count++; } return count; } };2. 设计一个算法，判断玩家是否赢了井字游戏。输入是一个 N x N 的数组棋盘，由字符" "，“X"和"O"组成，其中字符” "代表一个空位。
以下是井字游戏的规则：
玩家轮流将字符放入空位（" “）中。 第一个玩家总是放字符"O”，且第二个玩家总是放字符"X"。 "X"和"O"只允许放置在空位中，不允许对已放有字符的位置进行填充。 当有N个相同（且非空）的字符填充任何行、列或对角线时，游戏结束，对应该字符的玩家获胜。 当所有位置非空时，也算为游戏结束。 如果游戏结束，玩家不允许再放置字符。 如果游戏存在获胜者，就返回该游戏的获胜者使用的字符（“X"或"O”）；如果游戏以平局结束，则返回 “Draw”；如果仍会有行动（游戏未结束），则返回 “Pending”。
示例 1：
输入： board = [“O X”," XO",“X O”] 输出： “X”
示例 2：
输入： board = [“OOX”,“XXO”,“OXO”] 输出： “Draw” 解释： 没有玩家获胜且不存在空位
示例 3：
输入： board = [“OOX”,“XXO”,"OX "] 输出： “Pending” 解释： 没有玩家获胜且仍存在空位
提示：
1 <= board.length == board[i].length <= 100 输入一定遵循井字棋规则
//解题思路参照用户jinhong class Solution { public: string tictactoe(vector<string>& board) { int N=board.size(); int m_nRow=0,m_nColumn=0,m_nDiaLeft=0,m_nDiaRight=0; int flag=0; for(int i=0;i<N;i++) { m_nDiaLeft+=board[i][i]; m_nDiaRight+=board[i][N-i-1]; for(int j=0;j<N;j++) { m_nRow+=board[i][j]; m_nColumn+=board[j][i]; if(board[i][j]==' ')flag=1; } if(m_nRow==N*(int)'X'||m_nColumn==N*(int)'X') return string("X"); if(m_nRow==N*(int)'O'||m_nColumn==N*(int)'O') return string("O"); m_nRow = m_nColumn = 0; } if(m_nDiaLeft==N*(int)'X'||m_nDiaRight==N*(int)'X') return string("X"); if(m_nDiaLeft==N*(int)'O'||m_nDiaRight==N*(int)'O') return string("O"); if(flag==1)return string("Pending"); else return string("Draw"); } };3. 给你一个整数数组 nums，每次 操作 会从中选择一个元素并 将该元素的值减少 1。 如果符合下列情况之一，则数组 A 就是 锯齿数组： 每个偶数索引对应的元素都大于相邻的元素，即 A[0] > A[1] < A[2] > A[3] < A[4] > … 或者，每个奇数索引对应的元素都大于相邻的元素，即 A[0] < A[1] > A[2] < A[3] > A[4] < … 返回将数组 nums 转换为锯齿数组所需的最小操作次数。
示例 1：
输入：nums = [1,2,3] 输出：2 解释：我们可以把 2 递减到 0，或把 3 递减到 1。
示例 2：
输入：nums = [9,6,1,6,2] 输出：4
提示：
1 <= nums.length <= 1000 1 <= nums[i] <= 1000
//思路是比较简单的：分别算出奇数索引值和偶数索引值小于两边的情况下的步数，输出较小的即可。 //代码来自用户皋军 #define MIN_NUM(a,b) ((a)<(b)?(a):(b)) #define MAX_NUM(a,b) ((a)>(b)?(a):(b)) class Solution { public: int movesToMakeZigzag(vector<int>& nums) { int min1=0; int min2=0; int N=nums.size(); for(int i=1;i<N-1;i+=2) min1+=MAX_NUM(0,(nums[i]-MIN_NUM(nums[i-1],nums[i+1])+1)); if(N%2==0) min1+=MAX_NUM(0,(nums[N-1]-nums[N-2]+1)); for(int i=2;i<N-1;i+=2) min2+=MAX_NUM(0,(nums[i]-MIN_NUM(nums[i-1],nums[i+1])+1)); if(N%2==1) min2+=MAX_NUM(0,(nums[N-1]-nums[N-2]+1)); min2+=MAX_NUM(0,(nums[0]-nums[1]+1)); return MIN_NUM(min1, min2); } };4. 学校在拍年度纪念照时，一般要求学生按照 非递减 的高度顺序排列。 请你返回能让所有学生以 非递减 高度排列的最小必要移动人数。 注意，当一组学生被选中时，他们之间可以以任何可能的方式重新排序，而未被选中的学生应该保持不动。
示例1：
输入：heights = [1,1,4,2,1,3] 输出：3 解释： 当前数组：[1,1,4,2,1,3] 目标数组：[1,1,1,2,3,4] 在下标 2 处（从 0 开始计数）出现 4 vs 1 ，所以我们必须移动这名学生。 在下标 4 处（从0 开始计数）出现 1 vs 3 ，所以我们必须移动这名学生。 在下标 5 处（从 0 开始计数）出现 3 vs 4，所以我们必须移动这名学生。
示例 2：
输入：heights = [5,1,2,3,4] 输出：5
示例 3：
输入：heights = [1,2,3,4,5] 输出：0
提示：
1 <= heights.length <= 100 1 <= heights[i] <= 100
//阅读理解题，返回排序后和排序前位置不一样的个数 class Solution { public: int heightChecker(vector<int>& heights) { vector<int> a = heights; int cnt = 0; int n = heights.size(); sort(a.begin(), a.end()); for (int i = 0;i < n;i++) { if (a[i]!=heights[i]) cnt++; } return cnt; } };5. 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
示例 1:
输入: m = 3, n = 2 输出: 3 解释: 从左上角开始，总共有 3 条路径可以到达右下角。
向右 -> 向右 -> 向下向右 -> 向下 -> 向右向下 -> 向右 -> 向右示例 2:
输入: m = 7, n = 3 输出: 28
提示：
1 <= m, n <= 100 题目数据保证答案小于等于 2 * 10 ^ 9
//动态规划 static int a[101][101]={0}; class Solution { public: int uniquePaths(int m, int n) { for(int i=0;i<m;i++) for(int j=0;j<n;j++) { if(i==0||j==0) { a[i][j]=1; } else a[i][j]=a[i][j-1]+a[i-1][j]; } return a[m-1][n-1]; } };6. 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
示例 1:
输入: [0,1,3] 输出: 2
示例 2:
输入: [0,1,2,3,4,5,6,7,9] 输出: 8
限制：
1 <= 数组长度 <= 10000
//题目很简单，解法多种多样 class Solution { public: int missingNumber(vector<int>& nums) { int n=nums.size(); int i; for(i=0;i<n;i++) { if(i!=nums[i]) break; } return i; } };