思维类型题OJ篇2

落日映苍穹つ 2023-06-27 06:25 54阅读 0赞

### 思维类型题OJ篇2 ###

*   *   *  1、区域和检索-数组不可变
         *  2、灯泡开关
         *  3、除自身以外数组的乘积
         *  4、滑动窗口最大值
         *  5、搜索二维矩阵 II
         *  6、只出现一次的数字

### 1、区域和检索-数组不可变 ###

给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。

> 示例  
> 给定 nums = \[-2, 0, 3, -5, 2, -1\]，求和函数为 sumRange()  
> sumRange(0, 2) -> 1  
> sumRange(2, 5) -> -1  
> sumRange(0, 5) -> -3

说明:假设数组不可变，**会多次调用 sumRange 方法**

方法一：常规思路

vector<int>v;
        NumArray(vector<int>& nums) { 
            for(auto&e:nums){ 
                v.push_back(e);
            }
        }
        int sumRange(int i, int j) { 
            int sum = 0;
            for(int m = i;m<j+1;++m){ 
                sum+=v[m];
            }
            return sum;
        }

方法二：由于会多次调用 sumRange 方法，所以我们用另一个数组 stack 的第 i 位存储 num 的前 i 项和；那么第 k 到第 j 位的和为 `stack[j]-stack[i-1]`,由于 k 可能为0，所以我们提前在数组第一个位置插入一个数字0，这样就不会导致数组越界，对应的公式就变为`stack[j+1] - stack[i]`

vector<int>stack;
        NumArray(vector<int>& nums) { 
            int temp = 0;
            stack.push_back(temp);
            for(auto&e:nums){ 
                temp+=e;
                stack.push_back(temp);
            }
        }
        
        int sumRange(int i, int j) { 
            return stack[j+1]-stack[i];
        }

python 写法

def __init__(self, nums: List[int]):
            self.stack = [0]
            for num in nums:
                self.stack.append(num+self.stack[-1])        
    
        def sumRange(self, i: int, j: int) -> int:
            return self.stack[j+1]-self.stack[i]

### 2、灯泡开关 ###

初始时有 n 个灯泡关闭

第 1 轮，你打开所有的灯泡  
第 2 轮，每两个灯泡你关闭一次  
第 3 轮，每三个灯泡切换一次开关（如果关闭则开启，如果开启则关闭）  
第 i 轮，每 i 个灯泡切换一次开关

对于第 n 轮，你只切换最后一个灯泡的开关。 找出 n 轮后有多少个亮着的灯泡

> 示例  
> 输入: 3  
> 输出: 1  
> 解释:  
> 初始时, 灯泡状态 \[关闭, 关闭, 关闭\].  
> 第一轮后, 灯泡状态 \[开启, 开启, 开启\].  
> 第二轮后, 灯泡状态 \[开启, 关闭, 开启\].  
> 第三轮后, 灯泡状态 \[开启, 关闭, 关闭\].

思路：一个数的因数如果有偶数个的话，最终状态就是关闭状态，如果有奇数个就是开启状态，那么一个数如果是某个整数的完全平方数，那么他最终的状态就是开启的。所以只需要找出n中包含多少个完全平方数即可，即对n进行开方取整

其中 0 代表关闭，1 代表开启  
![灯泡开关][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70]

import math
    class Solution:
        def bulbSwitch(self, n: int) -> int:
            return int(math.sqrt(n))

### 3、除自身以外数组的乘积 ###

给定长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output\[i\] 等于 nums 中除 nums\[i\] 之外其余各元素的乘积

> 示例  
> 输入: \[1,2,3,4\]  
> 输出: \[24,12,8,6\]

说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题

先求每个数左边的数组的乘积，再求每个数右边的数组的乘积，最后左右两边的乘积相乘就是最后的结果

vector<int> productExceptSelf(vector<int>& nums) { 
            int n = nums.size();
            vector<int>res(n,1);
            for(int i = 1;i<n;++i){ 
                res[i] = nums[i-1]*res[i-1];
            }
            int temp = 1;
            for(int i = n-1;i>=0;--i){ 
                res[i] *= temp;
                temp *=nums[i]; 
            }
            return res;
        }

def productExceptSelf(nums):
            n = len(nums)
            res = [1]*n
            # 这一遍历下来，res 中的值就是左边的乘积
            for i in range(n-1):
                res[i+1]= nums[i]*res[i]
            # 计算右边的乘积
            right = 1
            for i in range(n-1,-1,-1):
                res[i]*=right
                right*=nums[i]
            return res

### 4、滑动窗口最大值 ###

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位

返回滑动窗口最大值

> 示例  
> 输入: nums = \[1,3,-1,-3,5,3,6,7\], 和 k = 3  
> 输出: \[3,3,5,5,6,7\]  
> 解释:滑动窗口的位置 最大值  
> \[1 3 -1\] -3 5 3 6 7 3  
> 1 \[3 -1 -3\] 5 3 6 7 3  
> 1 3 \[-1 -3 5\] 3 6 7 5  
> 1 3 -1 \[-3 5 3\] 6 7 5  
> 1 3 -1 -3 \[5 3 6\] 7 6  
> 1 3 -1 -3 5 \[3 6 7\] 7

方法一：思路特别简单，就是利用两个下标控制窗口，并且计算出最大值添加到返回列表中

def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
            if not nums:
                return []
            res = []
            n = len(nums)
            s = 0
            while k<n+1:
                temp = max(nums[s:k])
                res.append(temp)
                k+=1
                s +=1
            return res

在 python 中有自己的 max 函数去计算列表的最大值，如果C++还要自己去实现

方法二：优化版本

def maxSlidingWindow(nums, k):
        n = len(nums)
        if n < 2 or k == 1:
            return nums
        res = []
        # 里面存放的是下标位置
        index = [0]
        for i in range(1, n):
        	# 必须要弹出首元素,因为已经超过 k 个位置
            if index[0] <= i-k:
                index.pop(0)
            while index and nums[index[-1]] < nums[i]:
                index.pop()
            index.append(i)
            # 如果下标大于等于 k -1 的话，就可以插入了
            if i >= k-1:
                res.append(nums[index[0]])
        return res

C++ 写法，利用双端队列来存储下标

vector<int> maxSlidingWindow(vector<int>& nums, int k) { 
            if(nums.size()<2 || k==1){ 
                return nums;
            }
            vector<int>res;
            deque<int>dq; //里面存放下标
            for(int i = 0;i<nums.size();++i){ 
                if(!dq.empty() && dq.front() <= i-k){ 
                    dq.pop_front();
                }
                while(!dq.empty() && nums[dq.back()] < nums[i]){ 
                    dq.pop_back();
                }
                dq.push_back(i);
                if(i>=k-1){ 
                    res.push_back(nums[dq.front()]);
                }
            }
            return res;
        }

### 5、搜索二维矩阵 II ###

编写一个高效的算法来搜索 m \* n 矩阵 matrix 中的一个目标值 target，该矩阵具有以下特性：

每行的元素从左到右升序排列  
每列的元素从上到下升序排列

> 示例  
> 现有矩阵 matrix 如下：  
> \[  
> \[1, 4, 7, 11, 15\],  
> \[2, 5, 8, 12, 19\],  
> \[3, 6, 9, 16, 22\],  
> \[10, 13, 14, 17, 24\],  
> \[18, 21, 23, 26, 30\]  
> \]  
> 给定 target = 5，返回 true  
> 给定 target = 20，返回 false

方法一：可以通过O(N2) 遍历的方法去判断元素

方法二：时间复杂度为O(N+M),其中 M 和 N 为矩阵的行和列

从第一行的最后一列最为起点去遍历，如果小于目标值则到下一行遍历，如果大于目标值则去前一列遍历，

def searchMatrix(self, matrix, target):
            if not matrix:
                return False
            rows = len(matrix)
            cols = len(matrix[0])
            row,col = 0,cols-1
            while row<rows and col>=0:
                if matrix[row][col]==target:
                    return True
                elif matrix[row][col]<target:
                    row+=1
                else:
                    col-=1
            return False

### 6、只出现一次的数字 ###

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素

> 示例1  
> 输入: \[2,2,1\]  
> 输出: 1

> 示例2  
> 输入: \[4,1,2,1,2\]  
> 输出: 4

两个相同的数字经过异或运算符后会变为0

def singleNumber(self, nums: List[int]) -> int:
            temp = nums[0]
            for i in range(1,len(nums)):
                temp ^=nums[i]
            return temp

进阶：如果给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素

> 示例1  
> 输入: \[2,2,3,2\]  
> 输出: 3

> 示例2  
> 输入: \[0,1,0,1,0,1,99\]  
> 输出: 99

方法一：可以使用 set 容器进行去重，比如\[a,b,b,b,c,c,c\] 去重后为 \[a,b,c\] 要得到a,可以这样算(3 \* \[a,b,c\] - \[a,b,b,b,c,c,c\]) / 2

或者利用 unordered\_map 进行计数，然后找出 value 为1 的 key，这些方法都利用了 O(N) 的空间复杂度

方法二：python 写法，遍历数组，弹出当前元素，如果该值在列表中则在添加到末尾，如果不存在就说明它只存在数组中一次，直接返回就可了

def singleNumber(self, nums: List[int]) -> int:
            for i in range(len(nums)):
                temp = nums.pop(0)
                if temp not in nums:
                    return temp
                else:
                    nums.append(temp)

方法三：电路转换思维，我们平时都是一个二进制位来判断一个数字出现一次还是两次，如果出现两个则抵消为0，但是可以借助两个二进制位判断一个数如果出现三次，则抵消为0

def singleNumber(self, nums: List[int]) -> int:
            a = b = 0
            for i in range(len(nums)):
                a = (a^nums[i])&~b
                b = (b^nums[i])&~a
            return a

稍微解释以下，如果一个数字 x 出现一次，`a == x,b == 0；`(所以最后返回的是a),出现两次的时候 `a==0 ,b==x` ，出现三次的时候 `a==0 ，b==0`,又回到了0的初始状态

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191225211439692.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0,size_16,color_FFFFFF,t_70