精密科技东莞网站建设,贵阳哪家网站做优化排名最好,微信公众号是干什么用的,企业形象设计报价题目总结
lc1979 给你一个整数数组 nums #xff0c;返回数组中最大数和最小数的 最大公约数 。 两个数的 最大公约数 是能够被两个数整除的最大正整数。 会求 gcd 就行
class Solution {
public:int gcd(int a, int b){return b ? gcd(b, a % b) : a;}int findGCD(vector返回数组中最大数和最小数的 最大公约数 。 两个数的 最大公约数 是能够被两个数整除的最大正整数。 会求 gcd 就行
class Solution {
public:int gcd(int a, int b){return b ? gcd(b, a % b) : a;}int findGCD(vectorint 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) {vectorint 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 借助 Bvoid op(int n, vectorint A, vectorint B, vectorint 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(vectorint A, vectorint B, vectorint C) { // 表示从 A 移动到 C, 借助 Bop(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;mapTreeNode*, 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;}
};
