leetcode解题思路分析（三十九）328 - 334题

待我称王封你为后i 2022-12-01 14:05 75阅读 0赞

1.  奇偶链表  
    给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

**从题目要求可看出，把奇结点按原有顺序排到偶结点（保持原有顺序）之前即可。因此，我们只需要 把奇结点 一个一个地保持原有顺序插入到head之后即可**

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */
    class Solution { 
    public:
        ListNode *oddEvenList(ListNode *head) { 
            if (head == NULL )
                return head;
            ListNode *_swap = head->next; //要交换的节点的 前屈
            ListNode *p = head;             //把奇结点用尾插法插入到p->next
            while (_swap != NULL && _swap->next != NULL) { 
                //每一次循环，要交换一个结点，并且后移一位，所以需要检查两个结点
                ListNode *Tmp = _swap->next;  //保留交换结点，用于插入
                _swap = _swap->next = _swap->next->next; 
            //先进行删除 _swap后面的结点， 然后 让_swap 后移一位
                Tmp->next = p->next;  //把奇结点 尾插法 插入到p->next上
                p = p->next = Tmp;    //p要记得一直指向 奇结点的尾端
            }
            return head;
        }
    };

1.  矩阵中的最长递增路径  
    给定一个整数矩阵，找出最长递增路径的长度。

**将矩阵看成一个有向图，计算每个单元格对应的出度，即有多少条边从该单元格出发。对于作为边界条件的单元格，该单元格的值比所有的相邻单元格的值都要大，因此作为边界条件的单元格的出度都是 0。基于出度的概念，可以使用拓扑排序求解。从所有出度为 0 的单元格开始广度优先搜索，每一轮搜索都会遍历当前层的所有单元格，更新其余单元格的出度，并将出度变为 0 的单元格加入下一层搜索。当搜索结束时，搜索的总层数即为矩阵中的最长递增路径的长度。**

class Solution { 
    public:
        static constexpr int dirs[4][2] = { { -1, 0}, { 1, 0}, { 0, -1}, { 0, 1}};
        int rows, columns;
    
        int longestIncreasingPath(vector< vector<int> > &matrix) { 
            if (matrix.size() == 0 || matrix[0].size() == 0) { 
                return 0;
            }
            rows = matrix.size();
            columns = matrix[0].size();
            auto outdegrees = vector< vector<int> > (rows, vector <int> (columns));
            for (int i = 0; i < rows; ++i) { 
                for (int j = 0; j < columns; ++j) { 
                    for (int k = 0; k < 4; ++k) { 
                        int newRow = i + dirs[k][0], newColumn = j + dirs[k][1];
                        if (newRow >= 0 && newRow < rows && newColumn >= 0 && 
                        newColumn < columns && matrix[newRow][newColumn] > matrix[i][j]) { 
                            ++outdegrees[i][j];
                        }
                    }
                }
            }
            queue < pair<int, int> > q;
            for (int i = 0; i < rows; ++i) { 
                for (int j = 0; j < columns; ++j) { 
                    if (outdegrees[i][j] == 0) { 
                        q.push({ i, j});
                    }
                }
            }
            int ans = 0;
            while (!q.empty()) { 
                ++ans;
                int size = q.size();
                for (int i = 0; i < size; ++i) { 
                    auto cell = q.front(); q.pop();
                    int row = cell.first, column = cell.second;
                    for (int k = 0; k < 4; ++k) { 
                        int newRow = row + dirs[k][0], newColumn = column + dirs[k][1];
                        if (newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns && matrix[newRow][newColumn] < matrix[row][column]) { 
                            --outdegrees[newRow][newColumn];
                            if (outdegrees[newRow][newColumn] == 0) { 
                                q.push({ newRow, newColumn});
                            }
                        }
                    }
                }
            }
            return ans;
        }
    };

1.  按要求补齐数组  
    给定一个已排序的正整数数组 nums，和一个正整数 n 。从 \[1, n\] 区间内选取任意个数字补充到 nums 中，使得 \[1, n\] 区间内的任何数字都可以用 nums 中某几个数字的和来表示。请输出满足上述要求的最少需要补充的数字个数。

**贪心法的经典运用**

class Solution { 
    public:
        int minPatches(vector<int>& nums, int n) { 
            int patches = 0, i = 0;
            long miss = 1; // use long to avoid integer overflow error
            while (miss <= n) { 
                if (i < nums.size() && nums[i] <= miss) // miss is covered
                    miss += nums[i++];
                else {  // patch miss to the array
                    miss += miss;
                    patches++; // increase the answer
                }
            }
            return patches;
        }
    };

1.  验证二叉树的前序序列化  
    给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。

**本题和二叉树序列化是反向操作，可以记录槽数（每新加一个节点相当于多了两个新槽，一个NULL或者数字会消耗一个槽，NULL不会新加两个槽），也可以使用栈，遍历一次即可完成**

class Solution { 
    public:
        bool isValidSerialization(string preorder) { 
            if (preorder.empty()) return false;
            stack<bool> s;
            for (int i = 0; i < preorder.size(); ++i) { 
                if (preorder[i] == '#') { 
                    if (s.empty()) return i == preorder.size() - 1;
                    else { 
                        s.pop();
                        i++;
                    }
                }
                else { 
                    while (i < preorder.size() && preorder[i] != ',') i++;
                    s.push(0);
                }
            }
            return false;
        }
    };

class Solution { 
    public:
        bool isValidSerialization(string preorder) { 
            // number of available slots
            int slots = 1;
    
            int n = preorder.size();
            for(int i = 0; i < n; ++i) { 
                if (preorder[i] == ',') { 
                    // one node takes one slot
                    --slots;
    
                    // no more slots available
                    if (slots < 0) return false;
    
                    // non-empty node creates two children slots
                    if (preorder[i - 1] != '#') 
                        slots += 2;
                }
            }
    
            // the last node
            slots = (preorder[(n - 1)] == '#') ? slots - 1 : slots + 1;
            // all slots should be used up
            return slots == 0;
        }
    };

1.  重新安排行程  
    给定一个机票的字符串二维数组 \[from, to\]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。

**本题是图中的欧拉通路问题，类似题目还有753题，解法是Hierholzer算法，首先从起点开始深度优先搜索，如果一个分支无法走完，则保存至栈中，再回到上一分支继续走（入度与出度差为 11 的节点会导致死胡同，而该节点必然是最后一个遍历到的节点）**

class Solution { 
    public:
        unordered_map<string, priority_queue<string, vector<string>, std::greater<string>>> vec;
    
        vector<string> stk;
    
        void dfs(const string& curr) { 
            while (vec.count(curr) && vec[curr].size() > 0) { 
                string tmp = vec[curr].top();
                vec[curr].pop();
                dfs(move(tmp));
            }
            stk.emplace_back(curr);
        }
    
        vector<string> findItinerary(vector<vector<string>>& tickets) { 
            for (auto& it : tickets) { 
                vec[it[0]].emplace(it[1]);
            }
            dfs("JFK");
    
            reverse(stk.begin(), stk.end());
            return stk;
        }
    };

1.  递增的三元子序列  
    给定一个未排序的数组，判断这个数组中是否存在长度为 3 的递增子序列。  
    **保存最小值small和中间值mid，遍历数组并更新两个值，如果遇到比Mid大则直接返回true**

class Solution { 
    public:
      bool increasingTriplet(vector<int>& nums) { 
        if (nums.size() < 3) return false;
        int small = INT_MAX, mid = INT_MAX;
        for (auto num : nums) { 
          if (num <= small) { 
            small = num;
          } else if (num <= mid) { 
            mid = num;
          } 
          else if (num > mid) { 
            return true;
          }
        }
        return false;    
      }
    };