编写一个函数，将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

思路分析:

翻转其实就是相当于第一个字符和最后一个交换

首先实现一个交换函数,依次枚举

引用传递:被调函数的形式参数虽然也作为局部变量在堆栈中开辟了内存空间,但是这时存放的是主调函数

放进来的实参变量地址.被调函数对形参的任何操作都被处理成间接寻址.就是通过对阵中存放的地址访问主调函数中

的实参变量.

 /* 简单的说,就是在函数调用的参数,可以传引用,从而使得函数返回时,传参值的改变依旧生效 */ class Solution { public: void swap(char& a, char& b) {//引用传递 char tmp = a; a = b; b = tmp; } void reverseString(vector<char>&)s){ int len = s.size(); for (int i = 0; i < len / 2; i++) {//注意枚举范围 swap(s[i], s[len - i - 1]) } } };

??给定一个字符串，需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

思路分析:

记录一个pre变量,初始化为0,然后开始枚举整个字符串,只要遇到空格或字符串结尾.就令当前枚举的位置为i,我们就将[pre,i-1]的字符逆序放入字符串中.再加一个空格.枚举完毕,将结果字符串返回即可

/* 两个for循环嵌套枚举时,算法时间复杂度不一定是n的平方.也不一定是乘法关系.也有可能的加法关系 */ class Solution { public: string reverseWords(string s) { //传参是string,返回值也是string 支持动态扩容 string ans = ""; // (1)初始化结果字符串ans为空字符串 int pre = 0; // (2)初始化pre变量为0,代表字符串下标0开始 for(int i = 0; i <= s.length(); ++i) { // (3)注意这里需要枚举到s.length(),以空格分隔的字符串 //最后部分会漏掉 if(i == s.length() || s[i] == ' ') { // (4)遇到字符串结尾或者空格,就开始处理pre到i-1的部分 for(int j = i-1; j >= pre; --j) { ans.push_back(s[j]); // (5)对这部分字符.逆序放进结果数组,采用push_back接口 } if(i < s.length()) // (6)如果不是字符串结尾.则补上一个空格 ans.push_back(' '); pre = i + 1; // (7)更新pre的位置为空格下一个字符的下标 } } return ans; } }; 

给出一个有序数组 nums ，请 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。不要使用额外的数组空间。

传参是一个vector<int>类型的引用,要求在这个数组基础上进行修改

思路分析;

由于数组是有序的.所以大小相等的数一定出现在连续的一段区间.所以.核心是比较,如果

相等则舍弃,不相等就放入候选数组.由于我们做的是删除操作,所以候选数组的长度

在任何时候一定小于原数组,所以候选数组可以和原数组是同一块内存空间

class Solution { public: int removeDuplicates(vector<int>& nums) { int nowIdx = 0; // (1)nowIdx记录的是有序不重复数组最后一个元素的下标 if(nums.size() == 0) { return 0; } for(int i = 1; i < nums.size(); ++i) { // (2)从第一个元素开始枚举.将当前元素和有序 //不重复数组最后一个元素进行比较.如果不相等.则将当前元素放到有序不重复数组最后 //一个元素.更新下标 if(nums[i] != nums[nowIdx]) { nums[++nowIdx] = nums[i]; } } return nowIdx + 1; // (3)由于数组下标从0 开始.所以返回长度需要+1 } }; 

给你一个整数数组nums，请你选择数组的两个不同下标 i 和 j ，使 (nums[i]-1)*(nums[j]-1)取得最大值。请你计算并返回该式的最大值。

思路分析;

由于所有数都是整数,其实这个问题就是找到有个数列中的前两个大的数即可

线性枚举,往往就是对数组进行操作.而且是进行遍历操作

int maxProduct(int* nums, int numsSize){ int i; int max = -1, nextmax = -1; // (1) 初始化最大值和次大值 for(i = 0; i < numsSize; ++i) { if(nums[i] > max) { // (2) 枚举到的当前数和最大值换大,则更新次大值 //和最大值 nextmax = max; max = nums[i]; }else if(nums[i] > nextmax) { // (3) 枚举到的当前数在次大值和最大值之间,则更新次大值 nextmax = nums[i]; } } return (max-1) * (nextmax-1); } 

给定一个二进制数组， 计算其中最大连续 1 的个数。

思路分析:

连续就是当前这个数和前一个数的关系,二进制数组不是0就是1.当前数为0,sum=0

当前数为1时,++sum;然后统计这个过程中sum最大值

int findMaxConsecutiveOnes(int* nums, int numsSize){ int i; int sum = 0, max = 0; for(i = 0; i < numsSize; ++i) { if(nums[i] == 0) { sum = 0; // (1)当前数字为0, }else { ++sum; // (2)当前数字为1,则sum=sum+1 if(sum > max) { max = sum; // (3)随时记录最大值 } } } return max; } 

寻找数组中的最小值并返回

思路分析;

这个很简单,不要想太多.直接遍历一遍,比较小的数存在临时变量上,最后这个临时变量就是最小值

int findMin(int* nums, int numsSize){ int i, min = 100000; for(i = 0; i < numsSize; ++i) { if(nums[i] < min) { // (1)如果当前枚举的数比最小值小,直接赋值给最小值 min = nums[i]; } } return min; } 

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
??最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
??你可以假设除了整数 0 之外，这个整数不会以零开头。

思路分析:

考虑全是9的情况,数组长度需要+1,其他情况直接顺位模拟加法和进位即可

利用数组可以对大整数进行进位模拟加法

int* plusOne(int* digits, int digitsSize, int* returnSize){ int i, add; int *ret = NULL; for(i = 0; i < digitsSize; ++i) { if(digits[i] != 9) { break; } } if(i == digitsSize) { // (1)处理99999+1 ret = (int *) malloc( (digitsSize + 1) * sizeof(int)); ret[0] = 1; for(i = 1; i < digitsSize + 1; ++i) { ret[i] = 0; } *returnSize = digitsSize + 1; return ret; } // (2)处理其他情况 ret = (int *) malloc( digitsSize * sizeof(int)); *returnSize = digitsSize; add = 1; // (3)add代表上一个位的进位,由于是+1,默认最低位进位是1 for(i = digitsSize - 1; i >= 0; --i) { ret[i] = digits[i] + add; if(ret[i] >= 10) { // (4)如果大于等于10,产生进位 ret[i] -= 10; add = 1; }else { add = 0; // (5)不产生进位 } } return ret; } 

输入数字 n ，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

思路分析:

通过遍历,不段乘10,乘了n次.得到的就是10的n次方,10的n次方-1就是n位数的最大值

剩下的就是从1开始遍历到这个最大值的过程了

int* printNumbers(int n, int* returnSize){ int i; int f = 1; int *ret; for(i = 0; i < n; ++i) { f *= 10; // (1)计算10的n次方 } --f; *returnSize = f; ret = (int *)malloc( f * sizeof(int) ); for(i = 1; i <= f; ++i) { ret[i-1] = i; // (2)遍历,存储在数组中 } return ret; } 

给定一个整型数组 nums，在数组中找出由三个数组成的最大乘积，并输出这个乘积

思路分析:

线性枚举要先排序,接下来处理问题会很方便

三个负数: 排序后,找最接近零的三个数

两个负数:最大的正数,最小的负数

一个负数:最小的两个正数,最接近零的负数

没有负数:最大的三个正数

int threeNegative(int* nums, int numsSize) { int i; for(i = 0; i < numsSize; ++i) { if(nums[i] >= 0) { break; } } if(i - 3 < 0) { return -1000000009; } return nums[i-1] * nums[i-2] * nums[i-3]; } int twoNegative(int* nums, int numsSize) { int i; for(i = 0; i < numsSize; ++i) { if(nums[i] >= 0) { break; } } if(nums[0] >= 0 || nums[1] >= 0) { return -1000000009; } return nums[0] * nums[1] * nums[numsSize-1]; } int oneNegative(int* nums, int numsSize) { int i; for(i = 0; i < numsSize; ++i) { if(nums[i] >= 0) { break; } } if(i < 1 || i+1 >= numsSize ) { return -1000000009; } return nums[i] * nums[i+1] * nums[i-1]; } int zeroNegative(int* nums, int numsSize) { int i; for(i = 0; i < numsSize; ++i) { if(nums[i] >= 0) { break; } } if(numsSize-3 < i ) { return -1000000009; } return nums[numsSize-1] * nums[numsSize-2] * nums[numsSize-3]; } int Max(int a, int b) { return a > b ? a : b; } int comp(const void *a, const void *b) { return *(int*)a - *(int*)b; } int maximumProduct(int* nums, int numsSize){ int ans = -1000000009; qsort(nums, numsSize, sizeof(int), comp); ans = Max(ans, threeNegative(nums, numsSize)); // (1) ans = Max(ans, twoNegative(nums, numsSize)); // (2) ans = Max(ans, oneNegative(nums, numsSize)); // (3) ans = Max(ans, zeroNegative(nums, numsSize)); // (4) return ans; } 

给你一个数组nums 和一个值val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

思路分析:

这种方法只适用对顺序要求不高的
遍历整个数组,如果遇到和给定数字一样的,就将它和数组最后一个元素交换,然后数组元素-1,指针回退1,知道没有相同元素为止

int swap(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; return tmp; } int removeElement(int* nums, int numsSize, int val){ int i; for(i = 0; i < numsSize; ++i) { while(nums[i] == val) { // (1) while!!! swap(&nums[i], &nums[numsSize-1]); // (2) 如果发现这个数是需要删除的,就和最后一个数交换 --numsSize; // (3) 最后那个数直接弹出不管了 if(i >= numsSize) { // (4) 没有多余元素时,就直接跳出循环 break; } } } return numsSize; }