1. 矩阵中的最长递增路径
给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。
示例 1：
输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出：4
解释：最长递增路径为 [1, 2, 6, 9]。
示例 2：
输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
输出：4
解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
示例 3：
输入：matrix = [[1]]
输出：1
提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
0 <= matrix[i][j] <= 2^31 - 1
出处：
https://edu.csdn.net/practice/23885010
代码：
#include <bits/stdc++.h> using namespace std; class Solution { public: const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; int m, n; int longestIncreasingPath(vector<vector<int>> &matrix) { if (matrix.size() == 0 || matrix[0].size() == 0) { return 0; } m = matrix.size(); n = matrix[0].size(); int res = 0; auto memo = vector<vector<int>>(m, vector<int>(n, 0)); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (memo[i][j]) res = max(res, memo[i][j]); else res = max(res, dfs(i, j, matrix, memo)); } } return res; } int dfs(int i, int j, vector<vector<int>> &matrix, vector<vector<int>> &memo) { int temp = 1; for (int k = 0; k < 4; ++k) { int x = i + dirs[k][0]; int y = j + dirs[k][1]; if ((x >= 0) && (x < m) && (y >= 0) && (y < n) && (matrix[i][j] < matrix[x][y])) { if (memo[x][y]) temp = max(temp, memo[x][y] + 1); else temp = max(temp, dfs(x, y, matrix, memo) + 1); } } memo[i][j] = temp; return temp; } }; int main() { Solution s; vector<vector<int>> matrix = {{9,9,4},{6,6,8},{2,1,1}}; cout << s.longestIncreasingPath(matrix) << endl; matrix = {{3,4,5},{3,2,6},{2,2,1}}; cout << s.longestIncreasingPath(matrix) << endl; return 0; }
输出：
4
4
2. 删除排序链表中的重复元素
存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。
返回同样按升序排列的结果链表。
示例 1：
输入：head = [1,1,2]
输出：[1,2]
示例 2：
输入：head = [1,1,2,3,3]
输出：[1,2,3]
提示：
链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排列
出处：
https://edu.csdn.net/practice/23885011
代码：
#include <bits/stdc++.h> using namespace std; 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 *deleteDuplicates(ListNode *head) { if (head == nullptr) { return nullptr; } ListNode *prev = head; ListNode *p = prev->next; while (p != nullptr) { if (p->val != prev->val) { prev->next = p; prev = p; } p = p->next; } prev->next = p; return head; } }; ListNode* buildNodeList(vector<int> vec) { ListNode *head = new ListNode(0); ListNode *p = head; for (int i = 0; i < vec.size(); i++) { ListNode *node = new ListNode(vec[i]); p->next = node; p = p->next; } return head->next; } string NodeList2String(ListNode *head) { if (head==NULL) return "[]"; ListNode *p = head; string res; res.append("["); while (p != nullptr) { res.append(to_string(p->val)); res.append(","); p = p->next; } res.pop_back(); res.append("]"); return res; } int main() { Solution s; vector<int> nums = {1,1,2}; struct ListNode *head = buildNodeList(nums); cout << NodeList2String(s.deleteDuplicates(head)) << endl; nums = {1,1,2,3,3}; head = buildNodeList(nums); cout << NodeList2String(s.deleteDuplicates(head)) << endl; return 0; }
输出：
[1,2]
[1,2,3]
附： 单链表遍历、vectorToString
/* vector<int> traverseNodeList(ListNode *head) { vector<int> res; ListNode *p = head; while (p != nullptr) { res.push_back(p->val); p = p->next; } return res; } string vectorToString(vector<int> vec) { stringstream ss; ss << "["; for(int i = 0; i < vec.size(); i++) { ss << vec[i]; if(i != vec.size() - 1) { ss << ","; } } ss << "]"; return ss.str(); } */
3. 商品优惠计算器
商品优惠计算器 使用if语句编程实现输入购货金额，输出实际付款金额。购货折扣率如下：
购货金额≤500元 不打折
500元<购货金额≤1000元 9折
1000元<购货金额 8折
出处：
https://edu.csdn.net/practice/23885012
代码：
c++ 略
输出：
略
