题海战术——线性枚举

编写一个函数，将输入的字符串反转过来。输入字符串以字符数组 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;
}