1. 输出最长的递增数字字符串
如何在一亿位整数组成的字符串中找到最长的递增数字字符串？
以下程序实现了这一功能，请你填补空白处内容：
```c++ #include <stdio.h> #include <string.h> #define MAX_SIZE 100000 int main() { char buf[MAX_SIZE] = {0}; int i = 0, len = 0, index = 0; char maxbuf[12] = {0}; char maxbuf2[12] = {0}; int maxlen = 0; gets(buf); len = strlen(buf); maxbuf2[0] = buf[0]; i = 1; index = 1; while (i < len) { if (buf[i] > buf[i - 1]) { maxbuf2[index] = buf[i]; index++; } else { _________________; } i++; } if (index > maxlen) { maxlen = index; strcpy(maxbuf, maxbuf2); maxbuf[index] = '\0'; } printf("最大串长度:%d,字符串:%s\n", maxlen, maxbuf); return 0; } ```
出处：
https://edu.csdn.net/practice/26974815
代码：
#include <stdio.h> #include <string.h> #define MAX_SIZE 100000 int main() { char buf[MAX_SIZE] = {0}; int i = 0, len = 0, index = 0; char maxbuf[12] = {0}; char maxbuf2[12] = {0}; int maxlen = 0; gets(buf); len = strlen(buf); maxbuf2[0] = buf[0]; i = 1; index = 1; while (i < len) { if (buf[i] > buf[i - 1]) { maxbuf2[index] = buf[i]; index++; } else { if (index > maxlen) { maxlen = index; strcpy(maxbuf, maxbuf2); maxbuf[index] = '\0'; } maxbuf2[0] = buf[i]; index = 1; } i++; } if (index > maxlen) { maxlen = index; strcpy(maxbuf, maxbuf2); maxbuf[index] = '\0'; } printf("最大串长度:%d,字符串:%s\n", maxlen, maxbuf); return 0; }
输出：
略
2. 缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
进阶：你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗？
示例 1：
输入：nums = [1,2,0]
输出：3
示例 2：
输入：nums = [3,4,-1,1]
输出：2
示例 3：
输入：nums = [7,8,9,11,12]
输出：1
提示：
0 <= nums.length <= 300
-2^31 <= nums[i] <= 2^31 - 1
以下程序实现了这一功能，请你填补空白处的内容：
```c++ #include <bits/stdc++.h> using namespace std; class Solution { public: int firstMissingPositive(vector<int> &nums) { if (nums.size() == 0) { return 1; } int i = 0; while (i < nums.size()) { ____________________________; } for (i = 0; i < nums.size(); i++) { if (nums[i] != i + 1) { break; } } return i + 1; } }; ```
出处：
https://edu.csdn.net/practice/26974816
代码：
#include <bits/stdc++.h> using namespace std; class Solution { public: int firstMissingPositive(vector<int> &nums) { if (nums.size() == 0) { return 1; } int i = 0; while (i < nums.size()) { if (nums[i] > 0 && nums[i] != i + 1 && nums[i] - 1 < nums.size() && nums[nums[i] - 1] != nums[i]) { swap(nums[i], nums[nums[i] - 1]); } else { i++; } } for (i = 0; i < nums.size(); i++) { if (nums[i] != i + 1) { break; } } return i + 1; } }; int main() { Solution s; vector<int> nums = {1,2,0}; cout << s.firstMissingPositive(nums) << endl; nums = {3,4,-1,1}; cout << s.firstMissingPositive(nums) << endl; nums = {7,8,9,11,12}; cout << s.firstMissingPositive(nums) << endl; return 0; }
输出：
3
2
1
3. 最大矩形
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例 1：
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。
示例 2：
输入：matrix = []
输出：0
示例 3：
输入：matrix = [["0"]]
输出：0
示例 4：
输入：matrix = [["1"]]
输出：1
示例 5：
输入：matrix = [["0","0"]]
输出：0
提示：
rows == matrix.length
cols == matrix[0].length
0 <= row, cols <= 200
matrix[i][j] 为 '0' 或 '1'
以下程序实现了这一功能，请你填补空白处的内容：
```c++
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <string.h> static inline int max(int a, int b) { return a > b ? a : b; } static int area_calc(int *heights, int size) { int *indexes = malloc(size * sizeof(int)); int *lhist = malloc(size * sizeof(int)); int *rhist = malloc(size * sizeof(int)); int i, pos = 0; for (i = 0; i < size; i++) { while (pos > 0 && heights[indexes[pos - 1]] >= heights[i]) { pos--; } lhist[i] = pos == 0 ? -1 : indexes[pos - 1]; indexes[pos++] = i; } pos = 0; for (i = size - 1; i >= 0; i--) { _________________________; } int max_area = 0; for (i = 0; i < size; i++) { int area = heights[i] * (rhist[i] - lhist[i] - 1); max_area = max(area, max_area); } return max_area; } static int maximalRectangle(char **matrix, int matrixRowSize, int matrixColSize) { int i, j, max_area = 0; int *heights = malloc(matrixColSize * sizeof(int)); memset(heights, 0, matrixColSize * sizeof(int)); for (i = 0; i < matrixRowSize; i++) { for (j = 0; j < matrixColSize; j++) { heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0; } max_area = max(max_area, area_calc(heights, matrixColSize)); } return max_area; } int main(int argc, char **argv) { if (argc < 2) { fprintf(stderr, "Usage: ./test row1 row2...\n"); exit(-1); } int i, j; int row_size = argc - 1; int col_size = strlen(argv[1]); for (i = 0; i < row_size; i++) { printf("%s\n", argv[i + 1]); } printf("%d\n", maximalRectangle(argv + 1, argc - 1, strlen(argv[1]))); return 0; } ```
出处：
https://edu.csdn.net/practice/26974817
代码：
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <string.h> static inline int max(int a, int b) { return a > b ? a : b; } static int area_calc(int *heights, int size) { int *indexes = (int*)malloc(size * sizeof(int)); int *lhist = (int*)malloc(size * sizeof(int)); int *rhist = (int*)malloc(size * sizeof(int)); int i, pos = 0; for (i = 0; i < size; i++) { while (pos > 0 && heights[indexes[pos - 1]] >= heights[i]) { pos--; } lhist[i] = pos == 0 ? -1 : indexes[pos - 1]; indexes[pos++] = i; } pos = 0; for (i = size - 1; i >= 0; i--) { while (pos > 0 && heights[indexes[pos - 1]] >= heights[i]) { pos--; } rhist[i] = pos == 0 ? size : indexes[pos - 1]; indexes[pos++] = i; } int max_area = 0; for (i = 0; i < size; i++) { int area = heights[i] * (rhist[i] - lhist[i] - 1); max_area = max(area, max_area); } return max_area; } static int maximalRectangle(char **matrix, int matrixRowSize, int matrixColSize) { int i, j, max_area = 0; int *heights = (int*)malloc(matrixColSize * sizeof(int)); memset(heights, 0, matrixColSize * sizeof(int)); for (i = 0; i < matrixRowSize; i++) { for (j = 0; j < matrixColSize; j++) { heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0; } max_area = max(max_area, area_calc(heights, matrixColSize)); } return max_area; } int main() { char* matrix[] = { (char*)"10100", (char*)"10111", (char*)"11111", (char*)"10010" }; printf("%d\n", maximalRectangle(matrix, 4, 5)); return 0; }
输出：
6
