题目总结
lc1979
给你一个整数数组
nums，返回数组中最大数和最小数的 最大公约数 。两个数的 最大公约数 是能够被两个数整除的最大正整数。
会求 gcd 就行
class Solution {
public:
int gcd(int a, int b){
return b ? gcd(b, a % b) : a;
}
int findGCD(vector<int>& nums) {
int mn = 2e9, mx = -2e9;
for(auto x : nums){
mn = min(mn, x);
mx = max(mx, x);
}
return gcd(mn, mx);
}
};
lcr024
给定单链表的头节点
head，请反转链表，并返回反转后的链表的头节点。
- sol1
将链表结点加入数组，生成一个新链表（不会之举）
/**
* 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* reverseList(ListNode* head) {
vector<int> nums;
while(head != nullptr){
nums.push_back(head -> val);
head = head -> next;
}
int sz = nums.size();
ListNode *p = new ListNode;
p -> next = nullptr;
for(auto x : nums){
cout << x << ' ';
ListNode *tmp = new ListNode(x);
tmp -> next = p -> next;
p -> next = tmp;
}
return p -> next;
}
};
// 暴力写法 : 存下链表值, 重新生成链表
- sol2
迭代处理，让当前节点指向左边的结点
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *pre = nullptr;
while(head != nullptr){
ListNode *tmp = head -> next;
head -> next = pre;
pre = head;
head = tmp;
}
return pre;
}
};
- sol3
递归处理, dfs 一路搜到尾结点指向的 nullptr ，返回尾结点，一路回溯过程中，令每个结点都指向 pre 结点，最后返回从一路回溯上来的尾结点
class Solution {
public:
ListNode* dfs(ListNode* now, ListNode* pre){
if(now == nullptr) return pre; // 一路递归返回头结点
ListNode* res = dfs(now -> next, now);
now -> next = pre;
return res;
}
ListNode* reverseList(ListNode* head) {
return dfs(head, nullptr);
}
};
汉诺塔问题
在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。
你需要原地修改栈。
处理 n n n 个盘子，递归为处理 n − 1 n-1 n−1 个盘子
class Solution {
public:
// 把 n 个盘子从 A 移动到 C 借助 B
void op(int n, vector<int> &A, vector<int> &B, vector<int> &C){
if(n == 1){ // 递归终止
C.push_back(A.back());
A.pop_back();
return ;
}
op(n - 1, A, C, B);
C.push_back(A.back());
A.pop_back();
op(n - 1, B, A, C);
}
void hanota(vector<int>& A, vector<int>& B, vector<int>& C) { // 表示从 A 移动到 C, 借助 B
op(A.size(), A, B, C);
}
};
翻转二叉树
给定一棵二叉树的根节点
root，请左右翻转这棵二叉树，并返回其根节点。
递归处理，将原二叉树左子树作为新二叉树右子树，将原二叉树右子树作为新二叉树左子树；
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* mirrorTree(TreeNode* root) {
if(root == nullptr) return nullptr;
TreeNode* newRoot = new TreeNode(root -> val);
newRoot -> left = mirrorTree(root -> right);
newRoot -> right = mirrorTree(root -> left);
return newRoot;
}
};
lcr051
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给定一个二叉树的根节点
root，返回其 最大路径和，即所有路径上节点值之和的最大值。
一道比较好写的树形 dp
/**
* 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) {}
* };
*/
// dp[u] 表示以 u 为根节点的子树且选择 u 作为路径的一个结点所能得到的最大路径点
// 更新dp : dp[u] = w[u] + max(dp[lson], dp[rson], 0);
// 更新答案 : ans = max(ans, w[u] + max(dp[lson], 0) + max(dp[rson], 0));
class Solution {
public:
int ans = - 2e9;
map<TreeNode*, int> dp;
void dfs(TreeNode* r){
if(r == nullptr) return ;
dp[r] = r -> val;
dfs(r -> left);
dfs(r -> right);
dp[r] += max({dp[r -> left], dp[r -> right], 0});
ans = max(ans, r -> val + max(0, dp[r -> left]) + max(0, dp[r -> right]));
}
int maxPathSum(TreeNode* root) {
dfs(root);
return ans;
}
};
