1. 买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：prices = [7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
1 <= prices.length <= 10^5
0 <= prices[i] <= 10^4
出处：
https://edu.csdn.net/practice/27913247
代码：
#include <bits/stdc++.h> using namespace std; class Solution { public: int maxProfit(vector<int> &prices) { int profit = INT_MIN; int buy = INT_MAX; for (int i = 0; i < prices.size(); i++) { int temp = prices[i] - buy; if (temp > profit) { profit = temp; } if (temp < 0) { buy = prices[i]; } } return (profit > 0) ? profit : 0; } }; int main() { Solution s; vector<int> prices = {7,1,5,3,6,4}; cout << s.maxProfit(prices) << endl; prices = {7,6,4,3,1}; cout << s.maxProfit(prices) << endl; return 0; }
输出：
5
0
2. 两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
提示：
每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零
以下程序实现了这一功能，请你填补空白处内容：
```c++
struct ListNode { int val; struct ListNode *next; }; struct ListNode *addTwoNumbers(struct ListNode *l1, struct ListNode *l2) { struct ListNode *pp = NULL, *p = l1; struct ListNode *qp = NULL, *q = l2; int carry = 0; while (p != NULL && q != NULL) { p->val += q->val + carry; carry = 0; if (p->val >= 10) { carry = 1; p->val -= 10; } pp = p; p = p->next; qp = q; q = q->next; } if (q) { pp->next = p = q; qp->next = NULL; } ____________________; if (carry) { struct ListNode *n = (struct ListNode *)malloc(sizeof(struct ListNode)); n->val = 1; n->next = NULL; pp->next = n; } return l1; } ```
出处：
https://edu.csdn.net/practice/27913248
代码：
#include <bits/stdc++.h> using namespace std; struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; struct ListNode *addTwoNumbers(struct ListNode *l1, struct ListNode *l2) { struct ListNode *pp = NULL, *p = l1; struct ListNode *qp = NULL, *q = l2; int carry = 0; while (p != NULL && q != NULL) { p->val += q->val + carry; carry = 0; if (p->val >= 10) { carry = 1; p->val -= 10; } pp = p; p = p->next; qp = q; q = q->next; } if (q) { pp->next = p = q; qp->next = NULL; } while (carry && p) { p->val += carry; carry = 0; if (p->val >= 10) { carry = 1; p->val -= 10; } pp = p; p = p->next; } if (carry) { struct ListNode *n = (struct ListNode *)malloc(sizeof(struct ListNode)); n->val = 1; n->next = NULL; pp->next = n; } return l1; } struct ListNode* vectorToListNode(vector<int>& nums) { struct ListNode* head = new ListNode(0); struct ListNode* curr = head; for (int i = 0; i < nums.size(); i++) { curr->next = new ListNode(nums[i]); curr = curr->next; } return head->next; } void printList(ListNode *head) { ListNode *p = head; while (p != NULL) { printf("%d->", p->val); p = p->next; } printf("null\n"); } int main() { vector<int> l1 = {2,4,3}; vector<int> l2 = {5,6,4}; ListNode* L1 = vectorToListNode(l1); ListNode* L2 = vectorToListNode(l2); printList(L1); printList(L2); ListNode* Ls = addTwoNumbers(L1, L2); printList(Ls); l1 = {9,9,9,9,9,9,9}; l2 = {9,9,9,9}; L1 = vectorToListNode(l1); L2 = vectorToListNode(l2); printList(L1); printList(L2); Ls = addTwoNumbers(L1, L2); printList(Ls); return 0; }
输出：
2->4->3->null
5->6->4->null
7->0->8->null
9->9->9->9->9->9->9->null
9->9->9->9->null
8->9->9->9->0->0->0->1->null
3. 二叉树的后序遍历
给定一个二叉树，返回它的 后序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
出处：
https://edu.csdn.net/practice/27913249
代码：
#define null INT_MIN #include <bits/stdc++.h> using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; class Solution { public: vector<int> postorderTraversal(TreeNode *root) { dfs(root); return temp; } void dfs(TreeNode *root) { if (root == NULL) return; dfs(root->left); dfs(root->right); temp.push_back(root->val); } vector<int> temp; }; TreeNode* buildTree(vector<int>& nums) { TreeNode *root = new TreeNode(nums[0]); queue<TreeNode*> q; q.push(root); int i = 1; while(!q.empty() && i < nums.size()) { TreeNode *cur = q.front(); q.pop(); if(nums[i] != null) { cur->left = new TreeNode(nums[i]); q.push(cur->left); } i++; if(i < nums.size() && nums[i] != null) { cur->right = new TreeNode(nums[i]); q.push(cur->right); } i++; } return root; } string vectorToString(vector<int> vect) { stringstream ss; ss << "["; for (size_t i = 0; i < vect.size(); i++) { ss << (vect[i] == null ? "null" : to_string(vect[i])); ss << (i < vect.size() - 1 ? "," : "]"); } return ss.str(); } int main() { Solution s; vector<int> root = {1,null,2,3}; TreeNode* tree = buildTree(root); cout << vectorToString(s.postorderTraversal(tree)) << endl; return 0; }
输出：
[3,2,1]
迭代法：
#define null INT_MIN #include <bits/stdc++.h> using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; class Solution { public: vector<int> postorderTraversal(TreeNode* root) { stack<TreeNode*> s; vector<int> result; if (!root) { return result; } s.push(root); TreeNode* prev = NULL; while (!s.empty()) { TreeNode* curr = s.top(); if (!prev || prev->left == curr || prev->right == curr) { if (curr->left) { s.push(curr->left); } else if (curr->right) { s.push(curr->right); } else { result.push_back(curr->val); s.pop(); } } else if (curr->left == prev) { if (curr->right) { s.push(curr->right); } else { result.push_back(curr->val); s.pop(); } } else if (curr->right == prev) { result.push_back(curr->val); s.pop(); } prev = curr; } return result; } }; TreeNode* buildTree(vector<int>& nums) { TreeNode *root = new TreeNode(nums[0]); queue<TreeNode*> q; q.push(root); int i = 1; while(!q.empty() && i < nums.size()) { TreeNode *cur = q.front(); q.pop(); if(nums[i] != null) { cur->left = new TreeNode(nums[i]); q.push(cur->left); } i++; if(i < nums.size() && nums[i] != null) { cur->right = new TreeNode(nums[i]); q.push(cur->right); } i++; } return root; } string vectorToString(vector<int> vect) { stringstream ss; ss << "["; for (size_t i = 0; i < vect.size(); i++) { ss << (vect[i] == null ? "null" : to_string(vect[i])); ss << (i < vect.size() - 1 ? "," : "]"); } return ss.str(); } int main() { Solution s; vector<int> root = {1,null,2,3}; TreeNode* tree = buildTree(root); cout << vectorToString(s.postorderTraversal(tree)) << endl; return 0; }
