月のLeetCode 每周刷题之 Week5

2024-02-12 14:18
文章标签 leetcode 刷题 每周 week5

本文主要是介绍月のLeetCode 每周刷题之 Week5，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

剑指 Offer 30. 包含min函数的栈

剑指 Offer 31. 栈的压入、弹出序列

面试题32 - I. 从上到下打印二叉树

剑指 Offer 32 - III. 从上到下打印二叉树 III

剑指 Offer 33. 二叉搜索树的后序遍历序列

剑指 Offer 34. 二叉树中和为某一值的路径

剑指 Offer 35. 复杂链表的复制

剑指 Offer 36. 二叉搜索树与双向链表

剑指 Offer 37. 序列化二叉树

剑指 Offer 38. 字符串的排列

剑指 Offer 39. 数组中出现次数超过一半的数字

剑指 Offer 40. 最小的k个数

剑指 Offer 41. 数据流中的中位数

剑指 Offer 42. 连续子数组的最大和

剑指 Offer 45. 把数组排成最小的数

剑指 Offer 46. 把数字翻译成字符串

剑指 Offer 47. 礼物的最大价值

剑指 Offer 50. 第一个只出现一次的字符

剑指 Offer 52. 两个链表的第一个公共节点

剑指 Offer 53 - I. 在排序数组中查找数字 I

剑指 Offer 53 - II. 0～n-1中缺失的数字

剑指 Offer 54. 二叉搜索树的第k大节点

剑指 Offer 55 - I. 二叉树的深度

剑指 Offer 55 - II. 平衡二叉树

剑指 Offer 30. 包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

class MinStack {
public:/** initialize your data structure here. */stack<int> sk1,sk2;MinStack() {sk2.push(INT_MAX);}void push(int x) {sk1.push(x);if(x<=sk2.top()) sk2.push(x);}void pop() {int t=sk1.top();sk1.pop();if(t==sk2.top()) sk2.pop();}int top() {return sk1.top();}int min() {return sk2.top();}
};
​

剑指 Offer 31. 栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

 

class Solution {
public:bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {int i=0,j=0;stack<int> sk;for(auto i:pushed){sk.push(i);while(!sk.empty()&&sk.top()==popped[j]){sk.pop();j++;}}return j==popped.size();}
};

面试题32 - I. 从上到下打印二叉树

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

class Solution {
public:vector<int> levelOrder(TreeNode* root) {queue<TreeNode*> q;vector<int> vec;if(root==nullptr) return {};q.push(root);while(!q.empty()){vec.push_back(q.front()->val);root=q.front();q.pop();if(root->left!=nullptr) q.push(root->left);if(root->right!=nullptr) q.push(root->right);}return vec;}
};

  • 二叉树的层序遍历

剑指 Offer 32 - III. 从上到下打印二叉树 III

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<int> v;vector<vector<int>> vec;queue<TreeNode*> q;stack<int> sk;int level=1;if(root==nullptr) return {};q.push(root);while(!q.empty()){int size=q.size();while(size--){root=q.front();if(level&1)v.push_back(root->val);else sk.push(root->val);q.pop();if(root->left!=nullptr) q.push(root->left);if(root->right!=nullptr) q.push(root->right);}if(!(level&1)){while(!sk.empty()){v.push_back(sk.top());sk.pop();}}vec.push_back(v);v.clear();level++;}return vec;}
};

  • 用栈模拟倒序插入

剑指 Offer 33. 二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

class Solution {
public:bool verifyPostorder(vector<int>& postorder) {return recur(0, postorder.size()-1,postorder);}
​bool recur(int left,int right,vector<int>& postorder){if(left>=right) return true;
​int index=0;    //第一次大于根节点的下标while(postorder[index]<postorder[right]){index++;}int t=index;while(t<right){if(postorder[t]<postorder[right])   return false;t++;}return recur(left,index-1,postorder)&&recur(index, right-1, postorder);}
};

剑指 Offer 34. 二叉树中和为某一值的路径

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

 

class Solution {
public:vector<int> v;vector<vector<int>>vec;vector<vector<int>> pathSum(TreeNode* root, int target) {dfs(root, target);return vec;}void dfs(TreeNode* root, int target){if(root==nullptr) return;v.push_back(root->val);target-=root->val;if(root->left==nullptr&&root->right==nullptr&&target==0){vec.push_back(v);v.pop_back();return;}if(root->left!=nullptr) dfs(root->left,  target);if(root->right!=nullptr)    dfs(root->right, target);v.pop_back();}
};

剑指 Offer 35. 复杂链表的复制

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

 

class Solution {
public:Node* copyRandomList(Node* head) {Node* t=head;unordered_map<Node*,Node*> um;
​while(t!=nullptr){Node *p=new Node(t->val);um[t]=p;t=t->next;}t=head;while(t!=nullptr){um[t]->random=um[t->random];um[t]->next=um[t->next];t=t->next;}return um[head];}
};

  • 存放旧节点到新节点的映射

剑指 Offer 36. 二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

class Solution {
public:Node* treeToDoublyList(Node* root) {vector<Node*> vec;if(root==nullptr) return nullptr;inOrder(root,vec);vec[0]->left=vec[vec.size()-1];vec[vec.size()-1]->right=vec[0];for(int i=1;i<vec.size();i++){vec[i-1]->right=vec[i];vec[i]->left=vec[i-1];}return vec[0];}
​void inOrder(Node* root,vector<Node*>& vec){if(root==nullptr) return;inOrder(root->left, vec);vec.push_back(root);inOrder(root->right, vec);}
};

  • 中序遍历+存节点

剑指 Offer 37. 序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树。

你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

 

class Codec {
public:
​// Encodes a tree to a single string.string serialize(TreeNode* root) {if ( root == nullptr ) return "";ostringstream output;queue<TreeNode*> que;que.push(root);while ( !que.empty() ) {TreeNode* node = que.front();que.pop();if ( node == nullptr ) output << "# ";else {output << node->val << ' ';que.push(node->left);que.push(node->right);}}return output.str();}
​// Decodes your encoded data to tree.TreeNode* deserialize(string data) {if ( data.empty() ) return nullptr;vector<TreeNode*> nodes;string val;istringstream input(data);while ( input >> val ) {if ( val == "#" ) nodes.push_back(nullptr);else nodes.push_back(new TreeNode(stoi(val)));};int pos = 1;for ( int i = 0; i < nodes.size(); ++i ) {if ( nodes[i] == nullptr ) continue;nodes[i]->left = nodes[pos++];nodes[i]->right = nodes[pos++];}return nodes[0];}
};

剑指 Offer 38. 字符串的排列

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

class Solution {
public:vector<bool> visited;vector<string> vec;string t;vector<string> permutation(string s) {sort(s.begin(),s.end());visited=vector<bool>(s.size());backtracking(s, 0);return vec;}
​void backtracking(string s,int n){if(n==s.size()){vec.push_back(t);return;}
​for(int i=0;i<s.size();i++){if(visited[i]==false){if(i>0&&s[i]==s[i-1]&&visited[i-1]==true) continue;     //去重t.push_back(s[i]);visited[i]=true;backtracking(s, n+1);t.pop_back();visited[i]=false;}}}
};

  • 回溯+去重

剑指 Offer 39. 数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

class Solution {
public:int majorityElement(vector<int>& nums) {int n=0;int target=nums[0];for(int i=1;i<nums.size();i++){if(nums[i]==target) n++;else n--;if(n<0){target=nums[i];n=0;}}return target;}
};

  • 摩尔投票法

剑指 Offer 40. 最小的k个数

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

class Solution {
public:vector<int> getLeastNumbers(vector<int>& arr, int k) {priority_queue<int, vector<int>, greater<int>> pq;vector<int> vec;for(auto &i:arr){pq.push(i);}
​while(k--){vec.push_back(pq.top());pq.pop();}return vec;}
};

  • 小根堆

class Solution {
public:vector<int> getLeastNumbers(vector<int>& arr, int k) {priority_queue<int, vector<int>, less<int>> pq;vector<int> vec;if(k==0) return{};for(int i=0;i<k;i++){pq.push(arr[i]);}for(int j=k;j<arr.size();j++){if(arr[j]<pq.top()){pq.pop();pq.push(arr[j]);}}while(k--){vec.push_back(pq.top());pq.pop();}return vec;}
};

  • 大根堆

  • 先把k个数放入大根堆中，从k+1个数开始遍历，如果当前数比堆顶数小，堆顶弹出，当前数入堆

  • 遍历完成后，堆中的元素即为答案

剑指 Offer 41. 数据流中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。

 

class MedianFinder {
public:/** initialize your data structure here. */int count=0;priority_queue<int, vector<int>, less<int>> maxHeap;priority_queue<int, vector<int>, greater<int>> minHeap;
​MedianFinder() {
​}void addNum(int num) {count++;if(count==1)    //如果该数字为第一个元素{maxHeap.push(num);}else{if(num>maxHeap.top())   minHeap.push(num);else maxHeap.push(num);}int m=maxHeap.size(),n=minHeap.size();if(m-n>1)   //使堆平衡{minHeap.push(maxHeap.top());maxHeap.pop();}if(n-m>1){maxHeap.push(minHeap.top());minHeap.pop();}}double findMedian() {if(count&1) return maxHeap.size()>minHeap.size()?maxHeap.top()*1.0:minHeap.top()*1.0;return (maxHeap.top()+minHeap.top())/2.0;}
};
/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/

剑指 Offer 42. 连续子数组的最大和

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

class Solution {
public:int maxSubArray(vector<int>& nums) {vector<int> dp(nums.size());int sum=0;int ans=INT_MIN;for(int i=0;i<nums.size();i++){if(sum>=0) sum+=nums[i];else sum=nums[i];ans=max(ans,sum);}return ans;}
};

剑指 Offer 45. 把数组排成最小的数

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

class Solution {
public:string minNumber(vector<int>& nums) {vector<string> vec;for(auto &i:nums){vec.push_back(to_string(i));}sort(vec.begin(),vec.end(),[](string&a,string&b){return a+b<b+a;});string s;for(int i=0;i<vec.size();i++){s+=vec[i];}return s;}
};

剑指 Offer 46. 把数字翻译成字符串

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

 

class Solution {
public:int translateNum(int num) {return f(num);}
​int f(int num){if(num<10) return 1;if(num%100>=10&&num%100<=25) return f(num/100)+f(num/10);   //余100是判断后两位数是否在范围内return f(num/10);}
};

剑指 Offer 47. 礼物的最大价值

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

 

class Solution {
public:int maxValue(vector<vector<int>>& grid) {vector<vector<int>> dp(grid.size(),vector<int>(grid[0].size()));dp[0][0]=grid[0][0];for(int i=1;i<grid.size();i++)dp[i][0]=grid[i][0]+dp[i-1][0];for(int i=1;i<grid[0].size();i++)dp[0][i]=grid[0][i]+dp[0][i-1];for(int i=1;i<grid.size();i++){for(int j=1;j<grid[0].size();j++){dp[i][j]=max(dp[i-1][j],dp[i][j-1])+grid[i][j];}}return dp[grid.size()-1][grid[0].size()-1];}
};

class Solution {
public:int maxValue(vector<vector<int>>& grid) {for(int i=1;i<grid.size();i++)grid[i][0]+=grid[i-1][0];for(int i=1;i<grid[0].size();i++)grid[0][i]+=grid[0][i-1];for(int i=1;i<grid.size();i++){for(int j=1;j<grid[0].size();j++){grid[i][j]=max(grid[i-1][j],grid[i][j-1])+grid[i][j];}}return grid[grid.size()-1][grid[0].size()-1];}
};

  • 用原数组代替dp，降低空间复杂度

剑指 Offer 50. 第一个只出现一次的字符

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

class Solution {
public:char firstUniqChar(string s) {unordered_map<char,int> mp;for(auto &i:s){mp[i]++;}for(auto &i:s){if(mp[i]==1) return i;}return ' ';}
};

  • 哈希表，两次遍历

剑指 Offer 52. 两个链表的第一个公共节点

输入两个链表，找出它们的第一个公共节点。

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode *pa=headA,*pb=headB;while(headA!=headB){          if(headA==nullptr) headA=pb;else headA=headA->next;if(headB==nullptr) headB=pa;else headB=headB->next;}return headA;}
};

  • 双指针

剑指 Offer 53 - I. 在排序数组中查找数字 I

统计一个数字在排序数组中出现的次数。

class Solution {
public:int search(vector<int>& nums, int target) {int l=0,r=nums.size()-1;if(nums.size()==0) return 0;while(l<r){int mid=l+((r-l)>>1);if(nums[mid]>=target)  r=mid;else l=mid+1;}int start=l;l=0,r=nums.size()-1;while(l<r){int mid=1+l+((r-l)>>1);if(nums[mid]<=target) l=mid;else r=mid-1;}int end=r;if(nums[start]!=target) return 0;return end-start+1;}
};

  • 二分查找

剑指 Offer 53 - II. 0～n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

class Solution {
public:int missingNumber(vector<int>& nums) {int l=0,r=nums.size()-1;while(l<=r){int mid=l+((r-l)>>1);if(nums[mid]==mid) l=mid+1;else r=mid-1;}return l;}
};

  • 二分查找

剑指 Offer 54. 二叉搜索树的第k大节点

给定一棵二叉搜索树，请找出其中第 k 大的节点的值。

class Solution {
public:vector<int> vec;int kthLargest(TreeNode* root, int k) {dfs(root);return vec[vec.size()-k];}
​void dfs(TreeNode* root){if(root==nullptr) return;if(root->left!=nullptr) dfs(root->left);vec.push_back(root->val);if(root->right!=nullptr) dfs(root->right);       }
};

  • 中序遍历

剑指 Offer 55 - I. 二叉树的深度

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

class Solution {
public:int maxDepth(TreeNode* root) {if(root==nullptr) return 0;return dfs(root);}
​int dfs(TreeNode* root){if(root==nullptr) return 0;return max(dfs(root->left),dfs(root->right))+1;
​}
};

剑指 Offer 55 - II. 平衡二叉树

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

class Solution {
public:bool isBalanced(TreeNode* root) {if(root==nullptr) return true;if(abs(dfs(root->left)-dfs(root->right))>1) return false;return isBalanced(root->left)&&isBalanced(root->right);}
​int dfs(TreeNode* root){if(root==nullptr) return 0;return max(dfs(root->left),dfs(root->right))+1;} 
};

  • 自顶向下，时间复杂度 O(N^2)

class Solution {
public:bool isBalanced(TreeNode* root) {     return dfs(root)!=-1;}
​int dfs(TreeNode* root){if(root==nullptr) return 0;int left=dfs(root->left);if(left==-1) return -1;int right=dfs(root->right);if(right==-1) return -1;if(abs(left-right)>1) return -1;return max(left,right)+1;} 
};

  • 后序遍历

  • 自底向上 ，时间复杂度O（N）

这篇关于月のLeetCode 每周刷题之 Week5的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/702743。

相关文章

哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
leetcode-24Swap Nodes in Pairs

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L
阅读更多...
leetcode-23Merge k Sorted Lists

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists
阅读更多...
C++ | Leetcode C++题解之第393题UTF-8编码验证

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目： 题解： class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...
C语言 | Leetcode C语言题解之第393题UTF-8编码验证

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目： 题解： static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return
阅读更多...
【JavaScript】LeetCode：16-20

【JavaScript】LeetCode：16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i，右指针j，从头遍历数组，若j指针指向的元素不在set中，则加入该元素，否则更新结果res，删除集合中i指针指向的元素，进入下一轮循环。 /*** @param
阅读更多...
【每日刷题】Day113

【每日刷题】Day113

【每日刷题】Day113 🥕个人主页：开敲🍉 🔥所属专栏：每日刷题🍍 🌼文章目录🌼 1. 91. 解码方法 - 力扣（LeetCode） 2. LCR 098. 不同路径 - 力扣（LeetCode） 3. 63. 不同路径 II - 力扣（LeetCode） 1. 91. 解码方法 - 力扣（LeetCode） //思路：动态规划。 cl
阅读更多...
LeetCode：64. 最大正方形 动态规划 时间复杂度O(nm)

LeetCode：64. 最大正方形 动态规划 时间复杂度O(nm)

64. 最大正方形 题目链接 题目描述 给定一个由 0 和 1 组成的二维矩阵，找出只包含 1 的最大正方形，并返回其面积。 示例1: 输入: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输出: 4 示例2: 输入: 0 1 1 0 01 1 1 1 11 1 1 1 11 1 1 1 1输出: 9 解题思路 这道题的思路是使用动态规划
阅读更多...
LeetCode 第414场周赛个人题解

LeetCode 第414场周赛个人题解

目录 Q1. 将日期转换为二进制表示 原题链接 思路分析 AC代码 Q2. 范围内整数的最大得分 原题链接 思路分析 AC代码 Q3. 到达数组末尾的最大得分 原题链接 思路分析 AC代码 Q4. 吃掉所有兵需要的最多移动次数 原题链接 思路分析 AC代码 Q1. 将日期转换为二进制表示 原题链接 Q1. 将日期转换为二进制表示 思路分析
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2