2024.6.11 刷题总结

2024.6.11

**每日一题**

419.甲板上的战舰，一看题目，就感觉是用dfs来求解，但是再想想更简易的方法。我们可以看到战舰是一个特殊的连通块，即一列或者一行，并且没有相邻的战舰，所以我们可以通过枚举战舰起点的方式来求解。遍历二维数组，如果找到'X',只需要判断其左边或者上面是否有'X'就可以判断出它是否是战舰的起点，如果是起点，那么答案加一。

15.三数之和，这一题我的方法是利用三种循环实现，但是最后会超时，于是我增加了一些剪枝操作，当一些情况下提前退出循环，但是始终无法通过，于是我发现了自己对于双指针的理解还没有很彻底。我认为我的代码实现了双指针，双循环枚举起点和终点，用while不断将mid向前，但是分析一下逻辑，这实际上还是三重循环，并没有真正实现双指针，所以这告诉我们，实现双指针不是用特定的代码结构就可以，而是真正的代码逻辑层面实现。所以我们应该通过枚举起点，固定终点，再枚举中间点，逐步寻找满足条件的三元组即可。

以下是我的错误代码，仅供思考：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n=nums.size();
        sort(nums.begin(),nums.end());
        vector<vector<int>> ans;
        if(nums[0]>0||nums[n-1]<0) return ans;
        for(int i=0;i<n;i++){
            if(i>0&&nums[i]==nums[i-1]) continue;
            if(nums[i]>0) break;
           for(int j=n-1;j>i;j--)
              {
                if(j<n-1&&nums[j]==nums[j+1]) continue;
                if(nums[j]<0)
                int mid=i+1;
                while(mid<j){
                    if((nums[i]+nums[j]+nums[mid]==0)&&(mid==i+1||nums[mid]!=nums[mid-1])) ans.push_back({nums[i],nums[mid],nums[j]});
                    if(nums[i]+nums[mid]+nums[j]>0) break;
                    mid++;
                }
              }
        }
        return ans;      
    }
};