LeetCode-Day45

324 摆动序列II

给定一个无序的数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]… 的顺序。

示例 :

输入: nums = [1, 5, 1, 1, 6, 4]
输出: 一个可能的答案是 [1, 4, 1, 5, 1, 6]

输入: nums = [1, 3, 2, 2, 3, 1]
输出: 一个可能的答案是 [2, 3, 1, 3, 1, 2]

说明:
你可以假设所有输入都会得到有效的结果。

进阶:
你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗？

首先，解决O(n)的时间复杂度。

首先想到的可能是排序，然后按照一小一大重组即可。但是题目中并没有要求这么严苛，因此想到本学期学的线性时间选择，我们可以仅仅将数组分成3部分，中间是中位数，左边元素均比中位数小，右边元素均比中位数大。这个复杂度为$O(n)$

其次，再来解决空间复杂度的问题。我自己写的时候是参照空间复杂度为O(n)写的，看到了更好的可以仅在O(1)空间复杂度下完成该重组。

#define A(i) nums[(1+2*(i))%(n|1)]
void wiggleSort(vector<int>& nums) { 
    int n = nums.size();
    // Find a median 
    vector<int>::iterator midptr = nums.begin() + n / 2;
    nth_element(nums.begin(), midptr, nums.end());
    int mid = *midptr;
    for(int i = 0; i < n; i++) {
        cout << nums[i] << " ";
    }
    cout << endl;
    // Index-rewiring 
    int i = 0, j = 0, k = n - 1;
    while(j <= k) {
        cout << A(j) << endl;
        if(A(j) > mid) {
            swap(A(i++), A(j++));
        } else if(A(j) < mid) {
            swap(A(j), A(k--));
        } else {
            j++;
        }
    } 
    for(int i = 0; i < n; i++) {
        cout << nums[i] << " ";
    }
    cout << endl;
}

PS：3路划分，STL直接调用nth_element即可…我还是自己手写的。

nth_element(a+l,a+k,a+r)

这个函数会使$a$这个数组中区间$[l, r)$内的第k小的元素在第$k$个位置上（相对位置）

但是并不保证其他元素有序，时间复杂度为O(n)

334 递增的三元子序列

给定一个未排序的数组，判断这个数组中是否存在长度为 3 的递增子序列。

数学表达式如下:

如果存在这样的 i, j, k, 且满足 0 ≤ i < j < k ≤ n-1，
使得 arr[i] < arr[j] < arr[k] ，返回 true ; 否则返回 false 。
说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1) 。

示例 :

输入: [1,2,3,4,5]
输出: true

输入: [5,4,3,2,1]
输出: false

小trick

首先，新建两个变量 small 和 mid ，分别用来保存题目要我们求的长度为 3 的递增子序列的最小值和中间值。

接着，我们遍历数组，每遇到一个数字，我们将它和 small 和 mid 相比，若小于等于 small ，则替换 small；否则，若小于等于 mid，则替换 mid；否则，若大于 mid，则说明我们找到了长度为 3 的递增数组！

上面的求解过程中有个问题：当已经找到了长度为 2 的递增序列，这时又来了一个比 small 还小的数字，为什么可以直接替换 small 呢，这样 small 和 mid 在原数组中并不是按照索引递增的关系呀？

Trick 就在这里了！假如当前的 small 和 mid 为 [3, 5]，这时又来了个 1。假如我们不将 small 替换为 1，那么，当下一个数字是 2，后面再接上一个 3 的时候，我们就没有办法发现这个 [1,2,3] 的递增数组了！也就是说，我们替换最小值，是为了后续能够更好地更新中间值！

另外，即使我们更新了 small ，这个 small 在 mid 后面，没有严格遵守递增顺序，但它隐含着的真相是，有一个比 small 大比 mid 小的前·最小值出现在 mid 之前。因此，当后续出现比 mid 大的值的时候，我们一样可以通过当前 small 和 mid 推断的确存在着长度为 3 的递增序列。 所以，这样的替换并不会干扰我们后续的计算！
链接：https://leetcode-cn.com/problems/increasing-triplet-subsequence/solution/c-xian-xing-shi-jian-fu-za-du-xiang-xi-jie-xi-da-b/

bool increasingTriplet(vector<int>& nums) {
    int n = nums.size();
    int small = INT_MAX, mid = INT_MAX; 
    for(int i = 0; i < n; i++) {
        if(nums[i] <= small) {
            small = nums[i];
        } else if(nums[i] <= mid) {
            mid = nums[i];
        } else if {
            return true;
        }
    }
    return false;
}

337 打家劫舍III

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例：

输入: [3,2,3,null,3,null,1]

输入: [3,2,3,null,3,null,1]
	3
   / \
  2   3
    \   \ 
     3   1
输出: 7 
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

输入: [3,4,5,1,3,null,1]
	 3
    / \
   4   5
  / \   \ 
 1   3   1
输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

思路：

其实我都没意识到我自己用了动态规划…

当前节点其实需要记录两个值：一个是如果不偷当前节点所获得的最大值，一个是偷当前节点所获得的最大值

• 如果不偷，则当前节点的最大值为：左节点偷或不偷的最大值 + 右节点偷或不偷的最大值
• 如果偷，当前节点的最大值为：左键点不偷的最大值 + 右节点不偷的最大值

上代码：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 前一个值代表没有偷这一家，后一个值代表偷这一家所获得的财富
pair<int, int> compute(TreeNode* node) {
    if(node == NULL) {
        return make_pair(0, 0);
    }
    pair<int, int> left = compute(node->left);
    pair<int, int> right = compute(node->right);
    return make_pair(max(left.first, left.second) + 
                     max(right.first, right.second), 
                     node->val + left.first + right.first);
}

int rob(TreeNode* root) {
    pair<int, int> res = compute(root);
    cout << max(res.first, res.second);
}

332 重新安排行程

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

说明:

如果存在多种有效的行程，你可以按字符自然排序返回最小的行程组合。例如，行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小，排序更靠前
所有的机场都用三个大写字母表示（机场代码）。
假定所有机票至少存在一种合理的行程。
示例 1:

输入: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
输出: ["JFK", "MUC", "LHR", "SFO", "SJC"]

输入: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出: ["JFK","ATL","JFK","SFO","ATL","SFO"]
解释: 另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。

思路：没啥思路，就是用dfs过的。

bool flag = false;

bool dfs(map<string, vector<string> >& m, string start, int& count, vector<string>& res) {

    for(int i = 0; i < m[start].size(); i++) {
        if(m[start][i] != "") {
            string next = m[start][i];
            m[start][i] = "";
            count--;
            res.push_back(next);
            if(dfs(m, next, count, res)) {
                return true;
            }
            count++;
            m[start][i] = next;
            res.pop_back();
        }
    }
    if(count == 0) {
        return true;
    } else {
        return false;
    }
}

今日新学了Hierholzer。该算法能在$O(E)$时间内求得欧拉路径。

欧拉路径：欧拉路径就是一条能够不重不漏地经过图上的每一条边的路径，即小学奥数中的一笔画问题。

如果这条路径的起点和终点相同，就是欧拉回路了。

满足欧拉路径的条件：

• 首先，这是一个连通图
• 若是无向图，则这个图的度数为奇数的点的格式必须是0或2；若是有向图，则要么所有的点入度和出度相同，要么you且仅有两个点的入度分别比出度大1或少1

算法流程：

• 对于无向图，判断度数为奇数的点和个数，若为0，则增设任意一点为起点，若为2，则从这两个点中任取一个点作为起点。对于有向图，判断入得和出度不同的点的个数，若为0，则设任意一点为起点，若为2，则设入度比出度小1的点作为起点，另一点为终点。具体起点的选择要视题目要求而定。
• 从起点开始递归：对于当前节点x，扫描与x相连的所有边，当扫描到一条$(x, y)$时，删除该边，并递归y，扫描完所有边之后，将x加入答案队列。
• 倒序输出答案队列（因为这里是倒休输出，因此可以用栈哎存储答案，当然用双端队列可以）

Let the initial directed graph be as below

Let’s start our path from 0.
Thus, curr_path = {0} and circuit = {}
Now let’s use the edge 0->1

Now, curr_path = {0,1} and circuit = {}
similarly we reach up to 2 and then to 0 again as

Now, curr_path = {0,1,2} and circuit = {}
Then we go to 0, now since 0 haven’t got any unused edge we put 0 in circuit and back track till we find an edge

We then have curr_path = {0,1,2} and circuit = {0}
Similarly when we backtrack to 2, we don’t find any unused edge. Hence put 2 in circuit and backtrack again.

curr_path = {0,1} and circuit = {0,2}

After reaching 1 we go to through unused edge 1->3 and then 3->4, 4->1 until all edges have been traversed.

The contents of the two containers look as: curr_path = {0,1,3,4,1} and circuit = {0,2}

now as all edges have been used, the curr_path is popped one by one into circuit.

Finally we’ve circuit = {0,2,1,4,3,1,0}

We print the circuit in reverse to obtain the path followed.

i.e., 0->1->3->4->1->1->2->0

https://www.geeksforgeeks.org/hierholzers-algorithm-directed-graph/?tdsourcetag=s_pctim_aiomsg

void printCircuit(vector<vector<int> > adj) 
{ 
    // adj represents the adjacency list of 
    // the directed graph 
    // edge_count represents the number of edges 
    // emerging from a vertex 
    map<int,int> edge_count; 
    for (int i = 0; i < adj.size(); i++) { 
        //find the count of edges to keep track 
        //of unused edges 
        edge_count[i] = adj[i].size(); 
    } 
    if (!adj.size()) 
        return; //empty graph 
    // Maintain a stack to keep vertices 
    stack<int> curr_path;  
    // vector to store final circuit 
    vector<int> circuit; 
    // start from any vertex 
    curr_path.push(0); 
    int curr_v = 0; // Current vertex 
    while (!curr_path.empty()) { 
        // If there's remaining edge 
        if (edge_count[curr_v]) { 
            // Push the vertex 
            curr_path.push(curr_v); 
            // Find the next vertex using an edge 
            int next_v = adj[curr_v].back();
            // and remove that edge 
            edge_count[curr_v]--; 
            adj[curr_v].pop_back(); 
            // Move to next vertex 
            curr_v = next_v; 
        } else {    // back-track to find remaining circuit  
            circuit.push_back(curr_v); 
            // Back-tracking 
            curr_v = curr_path.top(); 
            curr_path.pop(); 
        } 
    } 
    // we've got the circuit, now print it in reverse 
    for (int i=circuit.size()-1; i>=0; i--) { 
        cout << circuit[i]; 
        if (i) 
           cout<<" -> "; 
    } 
}