【LeetCode 02】暴力法总结

简介: 【LeetCode 02】暴力法总结

一、适用条件

适用条件为:

  • 数组问题
  • 大部分例题都能用暴力破解法
    如【LeetCode 27】:给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

二、方法总结

  • 数组问题for循环遍历,有时候一成for循环,有时候两成for循环

for(int i=0;i<n;i++){
    xxx;//找val值
    for(int j=i+1;j<n;j++)
    {
        xxx;//覆盖
    }
}

三、暴力破解具体案例

3.1移除元素

根据例题:

int removeElement(int* nums, int numsSize, int val){
  for(int i=0;i<numSize;i++){//step1暴力循环查找
        if(nums[i]==val){//step2 查找值
        for(int j=i+1;j<numSize;j++){//step1暴力循环覆盖
            nums[j-1]=nums[j];
        }
            //step3数组元素i回退
            i--;
            numSize--;//数组长度因为覆盖值跟着减1
      }
    }
    return numSize;//新数组长度
}

3.2长度最小的子数组

step1:确定范围(最小子数组)的起点i终点j

for(int i=0;i<numsSize;i++){//起点
    
    for(int j=i;j<numSize;j++){//终点
        
    }
}

step2:累计记录子数组元素之和,一旦元素之和sum大于等于数组长度numsSize,就获取子数组的长度subLength(j-i+1

for(int i=0;i<numsSize;i++){//起点
    sum=0;
    for(int j=i;j<numSize;j++){//终点
        sum+=nums[j];
        if(sum>=numsSize){
            subLength=j-i+1;
        }
    }
}

step3:确定一个更新值result,初值赋为最大值 int32_max

int result=int32_max;//最小值为int32_min
result=result<subLength?result:subLength;//比较subLength与result并赋值
return result==int32_max?0:result;//没有符合条件的子数组,那么返回0

总过程:

int minSubArrayLen(int target, int* nums, int numsSize){
    int result=INT32_MAX;//最终的结果
    int sum=0;//子数组元素之和
    int subLength=0;//子数组的长度
    for(int i=0;i<numsSize;i++){
        sum=0;
        for(int j=i;j<numsSize;j++){
            sum+=nums[j];
            if(sum>=numsSize){
            subLength=j-i+1;
            result=result<subLength?result:subLength;
            break;
            }
        }
    }
    return result==INT32_MAX?0:result;
}

3.3两数之和

题意:

过程:

用暴力法解决:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for(int i=0;i<nums.size();i++){
            for(int j=i+1;j<nums.size();j++){//暴力破解标准模板
                if(nums[i]+nums[j]==target){
                    return {i,j};
                }
            }
        }
        return {};
    }
};

文章知识点

目录
相关文章
|
7月前
leetcode-1518:换酒问题
leetcode-1518:换酒问题
35 0
|
索引
|
算法 Java
一和零(LeetCode 474)
一和零(LeetCode 474)
102 0
leetcode第53题
解法一和解法二的动态规划,只是在定义的时候一个表示以 i 开头的子数组,一个表示以 i 结尾的子数组,却造成了时间复杂度的差异。问题就是解法一中求出了太多的没必要的和,不如解法二直接,只保存最大的和。
leetcode第53题
leetcode第54题
在 leetcode 的 solution 和 discuss 看了下,基本就是这个思路了,只是实现上有些不同,怎么用来标记是否走过,当前方向,怎么遍历,实现有些不同,但本质上是一样的。就是充分理解题意,然后模仿遍历的过程。
108 0
leetcode第54题
leetcode第55题
当自己按照 45 题的思路写完的时候,看 Solution 的时候都懵逼了,这道题竟然这么复杂?不过 Solution 把问题抽象成动态规划的思想,以及优化的过程还是非常值得学习的。
leetcode第55题
leetcode第51题
较经典的回溯问题了,我们需要做的就是先在第一行放一个皇后,然后进入回溯,放下一行皇后的位置,一直走下去,如果已经放的皇后的数目等于 n 了,就加到最后的结果中。然后再回到上一行,变化皇后的位置,然后去找其他的解。 期间如果遇到当前行所有的位置都不能放皇后了,就再回到上一行,然后变化皇后的位置。再返回到下一行。 说起来可能还费力些,直接看代码吧。
leetcode第51题
leetcode第36题
一个 9 * 9 的数独的棋盘。判断已经写入数字的棋盘是不是合法。需要满足下边三点, • 每一行的数字不能重复 • 每一列的数字不能重复 • 9 个 3 * 3 的小棋盘中的数字也不能重复。 只能是 1 - 9 中的数字,不需要考虑数独最后能不能填满
leetcode第36题
leetcode第48题
将一个矩阵顺时针旋转 90 度,并且不使用额外的空间。大概属于找规律的题,没有什么一般的思路,观察就可以了。 解法一 可以先转置,然后把每列对称交换交换一下
leetcode第48题