hot100_Twice

15.三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> result;
        for (int i = 0; i < nums.size(); i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1;
            int right = nums.size() - 1;
            while (left < right) {
                // 先找到一组解
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0) right--;
                else if (sum < 0) left++;
                else {
                    result.push_back({nums[i],nums[left],nums[right]});
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++;
                    right--;
                }
            }
        }

        return result;
    }

560.和为k的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。 子数组是数组中元素的连续非空序列。

int subarraySum(vector<int>& nums, int k) {
    // 通过遍历数组，计算每个位置的前准和，用一个哈希表来存储每个前缀和出现的次数
    unordered_map<int,int> prefixSum;
    prefixSum[0] = 1; // 0表示前缀和为0的数组组合 这里是空的 是一种情况
    int pre = 0,count = 0;
    for (const auto& num: nums) {
        pre += num;
        if (prefixSum.find(pre - k) != prefixSum.end()) 
            count += prefixSum[pre - k]; // 这里是对每一个新的pre都会有一堆 pre - k的情况 不会重复的
        prefixSum[pre]++;
    }
    return count;
}

54.螺旋矩阵

给你一个m行n列的矩阵matrix，请按照顺时针螺旋顺序，返回矩阵中的所有元素。

这道题卡在几个地方：

1. 自己想用directions来处理，但是directions数组写的不对
2. 按照这种思路需要处理一行或者是一列的特殊情况
3. 循环中条件容易少考虑，例如if (!condition1 || !condition2 || flag[next_i][next_j])
4. 整体来说，按照自己的思路这个题目比较好接受，正解我觉得挺绕的

自己的做法

vector<int> spiralOrder(vector<vector<int>>& matrix) {
        //时间复杂度可以 空间有点高 特殊情况需要处理
        if (matrix.empty() || matrix[0].empty()) return {};// 检查空的情况
        // 只有一行
        if (matrix.size() == 1) return matrix[0];
        vector<int> result;
        // 只有一列
        if (matrix[0].size() == 1) {
            for (int i  = 0; i < matrix.size();i++) {
                result.push_back(matrix[i][0]);
            }
            return result;
        }
        // 轮转的顺序 啊这里错了
        // 注意不要从 x y的角度考虑 代入矩阵想一想
        vector<vector<int>> directions = {{0,1},{1,0},{0,-1},{-1,0}};
        
        vector<vector<bool>> flag(matrix.size(), vector<bool>(matrix[0].size(), false));
        int i = 0,j = 0;
        int cur_dir = 0;

        while (flag[i][j] == false) {
            result.push_back(matrix[i][j]);
            flag[i][j] = true;
            int next_i = i + directions[cur_dir][0];
            int next_j = j + directions[cur_dir][1];
            // 应该是
            bool condition1 = (next_i >= 0) && (next_i < matrix.size());    // i对应行数
            bool condition2 = (next_j >= 0) && (next_j < matrix[0].size()); // j对应列数
            // 注意这里！！ 如果访问过也不能再访问
            if (!condition1 || !condition2 || flag[next_i][next_j]) {
                cur_dir = (cur_dir + 1) % directions.size();
                next_i = i + directions[cur_dir][0];
                next_j = j + directions[cur_dir][1];
                condition1 = (next_i >= 0) && (next_i < matrix.size()); 
                condition2 = (next_j >= 0) && (next_j < matrix[0].size());
            }
            i = next_i;
            j = next_j;
        }
        return result;
    }

官方解法

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    // 其实也就是使用上下左右四个变量控制 同时不用存储当前的位置了！
    // 边界条件就是上下、左右都要满足小于关系
    if (matrix.empty()) return {};
    int left = 0,right = matrix[0].size() - 1,top = 0,bottom = matrix.size() - 1;
    vector<int> ans;

    while (left <= right && top <= bottom) {
        // 从左到右
        for (int i = left; i <= right; i++) {
            ans.push_back(matrix[top][i]);
        }
        top++;
        // 从上到下
        for (int i = top; i <= bottom; i++) {
            ans.push_back(matrix[i][right]);
        }
        right--;
        
        // 从右到左
        if (top <= bottom) {
            for (int i = right; i >= left; i--) {
                ans.push_back(matrix[bottom][i]);
            }
            bottom--;
        }
        

        // 从下到上
        if (left <= right) {
            for (int i = bottom; i >= top; i--) {
                ans.push_back(matrix[i][left]);
            }
            left++;
        }
        
    }
    return ans;
}

240. 搜索二维矩阵 II

编写一个高效的算法来搜索m×n矩阵matrix中的一个目标值target。该矩阵具有以下特性： 每行的元素从左到右升序排列。 每列的元素从上到下升序排列。

这个题，自己再做的时候想当然写出了DFS，但这样肯定超时，要能够利用矩阵的规律。 可以从右上角或者是左下角出发，这样如果是当前元素小于target或者是大于都只有一个固定的移动方向。

记得还有类似的题，等做到再拿出来看一看，一时想不起来了💭💭

bool searchMatrix(vector<vector<int>>& matrix, int target) {
       // 从矩阵的右上角开始搜索 这时候所有大于他的都在下面 所有小于他的都在左面
       if (matrix.empty()|| matrix[0].empty()) return false; // 空的
       
       int rows = matrix.size();
       int cols = matrix[0].size();
       int row = 0,col = cols - 1;

       while (row < rows && col >= 0) {
           if (matrix[row][col] == target) return true;
           if (matrix[row][col] > target) col--;
           else row++;
       }
       return false;
   }

206. 反转链表

给你单链表的头节点head，请你反转链表，并返回反转后的链表。

哦莫，链表的题目总是容易出问题😭😭

这次没AC的原因是，我想让prev指向head，这样第一次prev指针没有处理好，导致指针混乱，其实可以从prev为空的时候开始处理

ListNode* reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return head;
    ListNode* prev = nullptr; // 前一个节点
    ListNode* curr = head; // 头节点
    
    while (curr != nullptr) { // 处理到最后 curr正好变为空
        ListNode* temp = curr->next; // 记录当前的下一个节点
        curr->next = prev;
        prev = curr;
        curr = temp;
    }
    
    return prev; // 这是prev指向最后一个节点
}

142.环形链表Ⅱ

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

还是使用Floyd判圈算法，快慢指针都从head出发，快指针一次走两步，慢指针一次走一步，那么快慢指针第一次相遇，快指针在圈内比慢指针多走了一圈。

之后，让快指针回到起点，每次走一步，再和慢指针相遇，相遇的地方就是入口点！

ListNode *detectCycle(ListNode *head) {
    // 先处理特殊情况
    if (head == NULL || head->next == NULL) return NULL;
    if (head- >next == head) return head;
    
    // 从起点出发
    ListNode* fast = head;
    ListNode* slow = head;
    
    do {
            if (fast->next == NULL || fast->next->next == NULL) return NULL;
            else fast = fast->next->next;
            slow = slow->next;
        } while (fast != slow);
        
        fast = head;
        
        while (fast != slow) {
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
}

543.二叉树的直径

给你一棵二叉树的根节点，返回该树的直径。二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点root。两节点之间路径的长度由它们之间边数表示。

// 在求最大值的时候 顺便不断更新结果ans
int ans = 0;
int diameterOfBinaryTree(TreeNode* root) {
    maxDepth(root);
    return ans - 1; // 深度是节点减一
}

int maxDepth(TreeNode* root) {
    if (root == nullptr) return 0;
    int L = maxDepth(root->left);
    int R = maxDepth(root->right);
    ans = max(ans,L + R + 1);
    return max(L,R) + 1;
}

108. 将有序数组转换为二叉搜索树

给你一个整数数组nums，其中元素已经按升序排列，请你将其转换为一棵平衡二叉搜索树。

思路其实还是从中间的节点出发，然后放置好左右节点，还是使用递归的方法。

TreeNode* sortedArrayToBST(vector<int>& nums) {
    return sortedArrayToBSTHelper(nums,0,nums.size() - 1);
}

TreeNode* sortedArrayToBSTHelper(const vector<int>& nums,int left,int right) {
    if (left > right) return nullptr;
    int mid = left + (right - left) / 2;
    
    TreeNode* root = new TreeNode(mid);
    root->left = sortedArrayToBSTHelper(nums,left,mid - 1);
    root->right = sortedArrayToBSTHelper(nums,mid + 1,right);
    
    return root;
}

105. 从前序与中序遍历序列构造二叉树

给定两个整数数组preorder和inorder，其中preorder是二叉树的先序遍历，inorder是同一棵树的中序遍历，请构造二叉树并返回其根节点。

二叉树的题目，卡壳的几率会比较大一些！ 递归经常想到但是实现困难🤨🤨

这题其实就是利用前序 中序遍历的规律，结合哈希表存储来解答，实现逻辑和108. 将有序数组转换为二叉搜索树 其实类似，中间有一个preIndex需要使用引用传递，有点小绕。

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    unordered_map<int,int> inMap;
    for (int i = 0; i < inorder.size();i++) 
        inMap[inorder[i]] = i;
    int preIndex = 0;
    return build(preorder,inorder,preIndex,0,inorder.size() - 1,inMap);
}

TreeNode* build(vector<int>& preorder,vector<int>& inorder,int& preIndex,int inStart,int inEnd,unordered_map<int,int>& inMap) {
    if (inStart > inEnd) return nullptr;
    
    int rootValue = preorder[preIndex];
    preIndex++;
    
    TreeNode* root = new TreeNode(rootValue);
    int inIndex = inMap[rootValue];
    
    root->left = build(preorder,inorder,preInedx,inStart,inIndex - 1,inMap);
    root->right = build(preorder,inorder,preIndex,inIndex + 1,inEnd,inMap);
    
    return root;
}

437. 路径总和 III

给定一个二叉树的根节点root，和一个整数targetSum，求该二叉树里节点值之和等于targetSum的路径的数目。 路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

两个递归在，一个保证以任何节点为起点，一个从任何节点找到路径。

二叉树卡住不少了QAQ

int count = 0;
int pathSum(TreeNode* root, int targetSum) {
    if (root == nullptr) return 0;
    dfs(root,targetSum);
    
    pathSum(root->left,targetSum);
    pathSum(root->right,targetSum);
    
    return count;
}

void dfs(TreeNode* root,int targetSum) {
    if (root == nullptr) return;
    if (root->val == targetSum) count++;
    
    dfs(root->left,targetSum - root->val);
    dfs(root->right,targetSum - root->val);
}

2025年2月12日元宵节☺️，今天整理一下过年期间做的几道题，明显好久不做手感下降了，以后每日保持做题要有良好手感！

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

像本人对于递归类的题目，往往不太能得心应手，只要稍微难一下就想不到，但是这一题可以使用哈希表记录父节点的方式解决。

unordered_map<int,TreeNode*> fathers; // 记录下自己的祖先
unordered_map<int,bool> record;
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    fathers[root->val] = NULL;
    dfs(root);
    
    while (p != NULL) {
        record[p->val] = true;
        p = fathers[p->val];
    }
    while (q != NULL) {
        if (record[q->val] == true) return q;
        else q = fathers[q->val];
    }
    return NULL;
}

void dfs(TreeNode* root) {
    if (!root) return;
    if (root->left) {
        fathers[root->left->val] = root;
        dfs(root->left);
    }
    if (root->right) {
        fathers[root->right->val] = root;
        dfs(root->right);
    }
}

994. 腐烂的橘子

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一： 值 0 代表空单元格； 值 1 代表新鲜橘子； 值 2 代表腐烂的橘子。 每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。 返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

像这道题，使用四个方向的directions数组把条件合并就会比较合适，同时涉及到前后都要取出元素，用queue也会比较方便。

   int orangesRotting(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    
    int clean = 0;
    queue<pair<int,int>> q;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) clean++;
            if (grid[i][j] == 2) q.push({i,j});
        }
    }
    
    if (clean == 0) return 0;
    if (q.empty()) return -1; 
    
    vector<vector<int>> directions = {{1,0},{-1,0},{0,1},{0,-1}};
    int time = 0;
    
    while (!q.empty()) {
        int newRot = 0;
        int size = q.size();
        for (int i = 0; i < size;i++) {
            auto[x,y] = q.front();
            q.pop();
            for (const auto& dir: directions) {
                int nx = x + dir[0];
                int ny = y + dir[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1) {
                    grid[nx][ny] = 2;
                    newRot++;
                    clean--;
                    q.push({nx,ny});
            }
        }
        }
        if (newRot) time++; // 这里 只有有新的橘子腐烂的时候 time才增加 否则其实已经结束不需要++
    }
    return clean == 0 ? time : -1;
}

207. 课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

题目其实是拓扑排序，使用的算法是基于入度的算法（Kahn算法）：

• 初始化一个入度为0的顶点队列。
• 依次从队列中取出顶点，将它们添加到拓扑排序序列中。
• 对于每个被处理的顶点，将其所有邻接点的入度减1。如果某个邻接点的入度变为0，将其加入队列。
• 重复此过程，直到所有顶点被处理。
• 如果队列为空，但图中还有顶点未被处理，说明图中有环，无法进行拓扑排序。

  bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
      // 判断图中是否存在环 拓扑排序
      vector<vector<int>> adj(numCourses); // 存储边
      vector<int> inDegree(numCourses,0); // 入度数组
  
      for (const auto& pre: prerequisites) {
          adj[pre[1]].push_back(pre[0]); // 每个节点存储从该节点开始的边
          inDegree[pre[0]]++;
      }
  
      queue<int> q;
      // 将所有入度为0的节点加入队列 代表起始节点
      for (int i = 0; i < numCourses;i++) {
          if (inDegree[i] == 0) q.push(i);
      }
  
      int visited = 0; // 已经访问的节点数
  
      while (!q.empty()) {
          int curr = q.front();
          q.pop();
          visited++;
  
          for (int next: adj[curr]) {
              inDegree[next]--;
              if (inDegree[next] == 0) q.push(next);
          }
      }
  
      return visited == numCourses; // 访问的节点数等于总课程数 说明无环
  } 

46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

经典题目，使用回溯法，寒假放的全忘完了。 这里使用一个used数组来记录这个数字有没有被使用过，就卡在这个上面。

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> result; // 结果数组
    vector<int> current;
    vector<bool> used(nums.size(),false);
    backtrack(nums,result,current,used);
    return result;
}

void backtrack(vector<int>& nums,vector<vector<int>>& result,vector<int>& current,vector<bool>& used) {
    if (current.size() == nums.size()) {
        result.push_back(current);
        return;
    }
    
    for (int i = 0; i < nums.size();i++) {
        if (used[i]) continue;
        
        current.push_back(nums[i]);
        used[i] = true;
        backtrack(nums,result,current,used);
        // 进行回溯
        current.pop_back();
        used[i] = false;
    }
}

22.括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

依然是回溯法，引用不引用这里不影响正确性，但是影响运行效率！

vector<string> generateParenthesis(int n) {
    string current;
    vector<string> result;
    backtrack(current,result,n,n);
    return result;
}

void backtrack(string& current, vector<string>& result, int left, int right) {
    if (left == 0 && right == 0) {
        result.push_back(current);
        return;
    }

    // 下面是考虑两种情况
    if (left > 0) {
        current.push_back('(');
        backtrack(current,result,left - 1, right);
        current.pop_back();
    }

    if (right > left) {
        current.push_back(')');
        backtrack(current,result,left, right - 1);
        current.pop_back();
    }
}

79.单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

这道题自己的思路没有问题，但是一直卡在运行时间超限，原因有几点：

1. word从不需要修改，使用引用传递也避免了不停复制
2. 不需要额外使用tag数组，直接改动board数组再复原即可
3. 使用if A || B || C这样的格式，如果A正确就不用再往下判断，否则每次进行回溯都要全走一遍，浪费时间

int m;
int n;
bool exist(vector<vector<char>>& board, string word) {
    m = board.size();
    n = board[0].size();

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (dfs(board,word,0,i,j)) return true;
        }
    }
    return false;
}

bool dfs(vector<vector<char>>& board,string& word,int idx,int i,int j) {
    if (i < 0 || i >= m || j < 0 || j >= n ||board[i][j] != word[idx]) return false;
    if (idx == word.size() - 1) return true;

    board[i][j] = '#'; // 标记
    bool res = dfs(board,word,idx + 1,i + 1,j) || dfs(board,word,idx + 1,i - 1,j)
                || dfs(board,word,idx + 1,i,j + 1) || dfs(board,word,idx + 1,i, j - 1);

    board[i][j] = word[idx]; // 复原
    return res;
}