23.合并K个升序链表
题目描述：
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例：
思路：
对于k个升序链表合并，先想到两个升序链表合并。然后加入归并排序的思想，划分到两两排序，在逐级合并。
/** * 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* mergeKLists(vector<ListNode*>& lists) { int len = lists.size(); return merge(lists,0,len-1); } ListNode* merge(vector<ListNode*>& lists,int l,int r) { if(l == r) return lists[l]; if(l > r) return nullptr; int mid = (l + r)/2; return mergeTwoLists(merge(lists,l,mid),merge(lists,mid+1,r)); //熟悉又不熟悉的归并 } ListNode* mergeTwoLists(ListNode* l1,ListNode* l2) { if(l1 == nullptr || l2 ==nullptr) { return l1 ? l1 : l2; } ListNode *a,*b; a = l1; b = l2; ListNode head; ListNode* c = &head; //这里 忘记malloc咋用了 要死 while(a != nullptr && b != nullptr) { if(a->val < b->val) { c->next = a; a = a->next; } else { c->next = b; b = b->next; } c = c->next; } if(a != nullptr) { c->next = a; } if(b != nullptr) { c->next = b; } return head.next; } };
剑指 Offer II 047. 二叉树剪枝
给定一个二叉树 根节点 root ，树的每个节点的值要么是 0，要么是 1。请剪除该二叉树中所有节点的值为 0 的子树。
节点 node 的子树为 node 本身，以及所有 node 的后代。
示例：
思路：
后序遍历的思想，看左子树，再看右子树。 对于叶子结点来判断是否为0，进行剪枝操作。这里注意root是一个临时变量，不能在if语句里面令root等于nullptr，再返回root。这里与下一题，链表结点里面的res那里使用一致，当进入dfs函数后，res保存的东西就会丢失。
通过代码：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* pruneTree(TreeNode* root) { if(root == nullptr) return nullptr; TreeNode* left = pruneTree(root->left); TreeNode* right = pruneTree(root->right); if(root->val == 0 && left == nullptr && right == nullptr) { return nullptr; } root->left = left; root->right = right; return root; } };
剑指 Offer II 028. 展平多级双向链表
多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。
给定位于列表第一级的头节点，请扁平化列表，即将这样的多级双向链表展平成普通的双向链表，使所有结点出现在单级双链表中。
示例：
思路：
深度优先搜索，对于dfs到最深处返回的是当前的最后一个结点，而不是有孩子结点的下一个结点。有孩子结点就要进行一次深度优先搜索，然后找到的child_结点指向，孩子结点的next结点。
/* // Definition for a Node. class Node { public: int val; Node* prev; Node* next; Node* child; }; */ class Solution { public: Node* res; Node* dfs(Node* head){ if(head == nullptr) { return nullptr; } Node* pre = head; Node* last = nullptr; while(pre != nullptr) { // res = pre->next; if(pre->child == nullptr) { last = pre; pre = pre->next; } else{ Node *child_ = dfs(pre->child); // printf("%d",res->val); res = pre->next; pre->next = pre->child; pre->child->prev = pre; pre->child = nullptr; // child_->prev = pre; if(res != nullptr) { child_->next = res; res->prev = child_; } last = child_; pre = res; } // pre = res; } return last; } Node* flatten(Node* head) { if(head == nullptr) { return nullptr; } dfs(head); return head; } };
剑指 Offer II 036. 后缀表达式
根据 逆波兰表示法，求该后缀表达式的计算结果。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
思路：
栈的应用+小细节c++里的switch参数要求
//注意：c++只能字符或者整型，java的switch就能不用整数类型了 class Solution { public: vector<string> s {"+","-","*","/"}; stack<int> mystack; int evalRPN(vector<string>& tokens) { int len = tokens.size(); int a,b,c; for(string i:tokens) { // cout<<tokens[i]<<endl; if(count(s.begin(), s.end(), i)) { // char c = char(i); b = mystack.top(); mystack.pop(); a = mystack.top(); mystack.pop(); // switch(int(i)){ if (i == "+") c = a + b; // break; else if (i =="-") c = a - b; // break; else if (i == "*") c = a * b; // break; else if (i == "/") c = a / b; // break; // } mystack.push(c); } else { mystack.push(stoi(i)); } } return mystack.top(); } };
