42. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
class Solution {
public:
int trap(vector<int>& height) {
int leftmax=0,rightmax=0;
int left=0,right=height.size()-1;
int sum=0;
while(left<right)
{
leftmax=max(height[left],leftmax);
rightmax=max(height[right],rightmax);
if(height[left]<height[right])
{
sum=sum+leftmax-height[left];
left++;
}
else
{
sum=sum+rightmax-height[right];
right--;
}
}
return sum;
}
};
- 维护两个指针left和right，以及两个变量leftMax和rightMax，初始时 left = 0,right= n - 1,leftMax =0,rightMax= 0
- 当两个指针没有相遇时，进行如下操作:
- 使用height[left]和height[right]的值更新leftMax和rightMax的值;
如果height(left) < height(right)，则必有leftMax <rightMax，下标 left处能接的雨水量等于leftMaz -height(left)，将下标left处能接的雨水量加到能接的雨水总量，然后将left加1(即向右移动一位); - 如果height(left) ≥ height(vight)，则必有leftMax ≥ rightMax，下标right处能接的雨水量等于rightMaa - height(right)，将下标right处能接的雨水量加到能接的雨水总量，然后将right 减1(即向左移动一位)。
- 当两个指针相遇时，即可得到能接的雨水总量。
124. 二叉树中的最大路径和
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
class Solution {
public:
int ans=INT_MIN;
int maxPathSum(TreeNode* root) {
f(root);
return ans;
}
int f(TreeNode*root)
{
if(!root) return 0;
int left=max(0,f(root->left));
int right=max(0,f(root->right));
int cur=left+right+root->val;
ans=max(ans,cur);
return root->val+max(left,right);
}
};
- 后序遍历，自底向上
剑指 Offer 03. 数组中重复的数字
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
for(int i=0;i<nums.size();i++)
{
while(nums[i]!=i)
{
if(nums[i]==nums[nums[i]])
{
return nums[i];
}
else
swap(nums[i],nums[nums[i]]);
}
}
return -1;
}
};
- 从头遍历数组，若无重复元素排序后num[n]的元素一定在下标为n的位置
- 判断当前数字nums[i]和下标i是否相等
- 如果相等则遍历下一个
- 如果不相等
- 判断是否和num[nums[i]]相等，若相等则返回
- 不相等的话则交换两个元素的位置
- 时间复杂度O(n)，空间复杂度O(1)
剑指 Offer 04. 二维数组中的查找
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
class Solution {
public:
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
if(matrix.size()==0) return false;
int n=0;
int m=matrix[0].size()-1;
while(n<matrix.size()&&m>=0)
{
if(matrix[n][m]>target)
{
m--;
}
else if(matrix[n][m]<target)
{
n++;
}
else return true;
}
return false;
}
};
- 从右上角开始查找
剑指 Offer 05. 替换空格
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
class Solution {
public:
string replaceSpace(string s) {
int spaceNum=0;
int left=s.size()-1;
for(auto i:s)
{
if(i==' ') spaceNum++;
}
int n=s.size()+spaceNum*2;
s.resize(n);
int right=s.size()-1;
while(left>=0)
{
if(s[left]!=' ')
{
s[right]=s[left];
left--;
right--;
}
else
{
s[right]='0';
s[right-1]='2';
s[right-2]='%';
right-=3;
left--;
}
}
return s;
}
};
- 双指针，从后往前遍历
- 时间复杂度O(N),空间复杂度O(1)
剑指 Offer 06. 从尾到头打印链表
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
class Solution {
public:
vector<int> reversePrint(ListNode* head) {
vector<int> vec;
while(head)
{
vec.push_back(head->val);
head=head->next;
}
reverse(vec.begin(),vec.end());
return vec;
}
};
剑指 Offer 07. 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if(preorder.empty()||inorder.empty()) return nullptr;
TreeNode* node=new TreeNode(preorder[0]);
for(int i=0;i<inorder.size();i++)
{
if(preorder[0]==inorder[i])
{
vector<int> leftPre(preorder.begin()+1,preorder.begin()+i+1);
vector<int> leftIn(inorder.begin(),inorder.begin()+i);
vector<int> rightPre(preorder.begin()+i+1,preorder.end());
vector<int> rightIn(inorder.begin()+i+1,inorder.end());
node->left=buildTree(leftPre, leftIn);
node->right=buildTree(rightPre, rightIn);
}
}
return node;
}
};
- 前序遍历的第一个元素为根节点，后序遍历的最后一个元素为根节点
- 在中序遍历中找到根节点，根节点的左边为左子树的元素，右边为右子树的元素
- 重复这个过程
06. 从中序与后序遍历序列构造二叉树
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if(inorder.empty()||postorder.empty()) return nullptr;
TreeNode *node=new TreeNode(postorder[postorder.size()-1]);
for(int i=0;i<inorder.size();i++)
{
if(postorder[postorder.size()-1]==inorder[i])
{
vector<int> leftPost(postorder.begin(),postorder.begin()+i);
vector<int> leftIn(inorder.begin(),inorder.begin()+i);
vector<int> rightPost(postorder.begin()+i,postorder.end()-1);
vector<int> rightIn(inorder.begin()+i+1,inorder.end());
node->left=buildTree(leftIn, leftPost);
node->right=buildTree(rightIn, rightPost);
break;
}
}
return node;
}
};
剑指 Offer 09. 用两个栈实现队列
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
class CQueue {
public:
stack<int> sk1,sk2;
CQueue() {
}
void appendTail(int value) {
sk1.push(value);
}
int deleteHead() {
int del;
if(sk1.empty()&&sk2.empty()) return -1; //队列无任何元素
if(sk2.empty())
{
while(!sk1.empty())
{
sk2.push(sk1.top());
sk1.pop();
}
}
del=sk2.top();
sk2.pop();
return del;
}
};
/**
* Your CQueue object will be instantiated and called as such:
* CQueue* obj = new CQueue();
* obj->appendTail(value);
* int param_2 = obj->deleteHead();
*/
剑指 Offer 10- I. 斐波那契数列
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
class Solution {
public:
int fib(int n) {
long long p=0,q=1,r=p+q;
if(n==0) return 0;
if(n==1||n==2) return 1;
for(int i=3;i<=n;i++)
{
p=q;
q=r;
r=(p+q)%1000000007;
}
return r;
}
};
剑指 Offer 11. 旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为1。
class Solution {
public:
int minArray(vector<int>& numbers) {
int l=0,r=numbers.size()-1;
while(l<r)
{
int mid=l+((r-l)>>1);
if(numbers[mid]>numbers[r]) l=mid+1; //此情况mid一定在左部分，一定不可能是最小值，所以可以mid+1
else if(numbers[mid]<numbers[r]) r=mid; //此情况mid在右半部分，有可能mid就是最小值，
//所以不能l=mid-1，只能l=mid
else r--; //相等时，说明有重复元素，l--即可
}
return numbers[r];
}
};
剑指 Offer 13. 机器人的运动范围
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
class Solution {
public:
vector<vector<bool>> visited;
int getx(int x)
{
int s=0;
while(x!=0)
{
s+=x%10;
x=x/10;
}
return s;
}
int movingCount(int m, int n, int k) {
visited=vector<vector<bool>>(m,vector<bool>(n));
int ans=dfs(m,n,0,0,k);
return ans;
}
int dfs(int m,int n,int x,int y,int k)
{
if(x<0||x>=m||y<0||y>=n||visited[x][y]==true) return 0;
if(getx(x)+getx(y)>k) return 0;
visited[x][y]=true;
int ans= 1+dfs(m,n,x+1,y,k)+dfs(m,n,x,y+1,k);
return ans;
}
};
- DFS，无需回溯
剑指 Offer 14- I. 剪绳子
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问
class Solution {
public:
int cuttingRope(int n) {
vector<int> dp(n+1);
dp[2]=1;
int ans;
for(int i=3;i<=n;i++)
{
for(int j=1;j<i;j++)
{
dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]));
}
}
return dp[n];
}
};
- 长度为i时，从j处剪成两段，分别为j和j-i
- 若继续剪，则是j*dp[j-i]
- 若不剪，则是j*(j-i）
- 两者取最大值
剑指 Offer 15. 二进制中1的个数
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数
class Solution {
public:
int hammingWeight(uint32_t n) {
int ans=0;
while(n)
{
if(n&1) ans++;
n=n>>1;
}
return ans;
}
};
- 时间复杂度O(K) K为二进制位数
class Solution {
public:
int hammingWeight(uint32_t n) {
int ans=0;
while(n)
{
n=n&(n-1);
ans++;
}
return ans;
}
};
- 时间复杂度从O(n)
剑指 Offer 16. 数值的整数次方
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。
class Solution {
public:
double myPow(double x, int n) {
long long pow=abs(n);
double ans=1.0;
while(pow)
{
if(pow&1)
{
ans*=x;
}
pow>>=1;
x*=x;
}
if(n<0) ans=1/ans;
return ans;
}
};
- 快速幂
剑指 Offer 17. 打印从1到最大的n位数
输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
class Solution {
public:
string s;
vector<int> vec;
vector<int> printNumbers(int n) {
char num[]={'0','1','2','3','4','5','6','7','8','9'};
for(int i=1;i<=n;i++)
backtracking(n, num,i);
return vec;
}
void backtracking (int n, char num[],int index)
{
if(s.size()==index)
{
vec.push_back(stoi(s));
return;
}
for(int i=0;i<10;i++)
{
if(i==0&&s.size()==0) continue; //去除首位为0的情况
s.push_back(num[i]);
backtracking(n, num,index);
s.pop_back();
}
return ;
}
};
- 大数全排列
- 回溯
剑指 Offer 18. 删除链表的节点
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
if(head->val==val) return head->next;
ListNode *cur=head;
while(head!=nullptr)
{
if(head->next!=nullptr && head->next->val==val)
{
if(head->next->next==nullptr) //尾节点
{
head->next=nullptr;
}
else //非尾结点
{
head->next=head->next->next;
}
}
head=head->next;
}
return cur;
}
};
83. 删除排序链表中的重复元素
给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode *temp=head;
if(head==nullptr) return head;
if(head->next==nullptr) return head;
ListNode *left=head;
ListNode *right=left->next;
while(right!=nullptr)
{
if(left->val==right->val)
{
left->next=right->next;
right=left->next;
}
else
{
left=left->next;
right=left->next;
}
}
return temp;
}
};
82. 删除排序链表中的重复元素 II
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode*pre=new ListNode(-1);
pre->next=head;
ListNode*cur=head,*t=pre;
while(cur!=nullptr)
{
while(cur->next!=nullptr&&cur->val==cur->next->val) //如果有重复
{
cur=cur->next; //则移动到最后一个无重复的节点
}
if(pre->next==cur) //如果无重复，即没移动节点
{
pre=pre->next; //则都往后移动一位
cur=cur->next;
}
else //移动了的话就把pre->next指向cur->next
{ //pre不需要移动，执行完pre->next==cur，在 上面的if里就会移动了
pre->next=cur->next;
cur=cur->next;
}
}
return t->next;
}
};
560. 和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int,int> mp;
mp[0]=1;
int n=0,pre=0;
for(auto& i:nums)
{
pre+=i;
if(mp.find(pre-k)!=mp.end())
{
n+=mp[pre-k];
}
mp[pre]++; //若k=2 nums=2,0,0,0,0时，pre一直是2，所以要mp[pre]++，而不是mp[pre]=1；
}
return n;
}
};
剑指 Offer 22. 链表中倒数第k个节点
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
ListNode *fast=head;
ListNode *slow=head;
while(k--)
{
fast=fast->next;
}
while(fast!=nullptr)
{
fast=fast->next;
slow=slow->next;
}
return slow;
}
};
剑指 Offer 24. 反转链表
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *pre=nullptr;
while(head!=nullptr)
{
ListNode *t=head->next;
head->next=pre;
pre=head;
head=t;
}
return pre;
}
};
剑指 Offer 25. 合并两个排序的链表
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1==nullptr) return l2;
if(l2==nullptr) return l1;
if(l1->val<=l2->val)
{
l1->next=mergeTwoLists(l1->next, l2);
return l1;
}
else
{
l2->next=mergeTwoLists(l1, l2->next);
return l2;
}
return nullptr;
}
};
剑指 Offer 26. 树的子结构
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
class Solution {
public:
bool isSubStructure(TreeNode* A, TreeNode* B) { //遍历A树，调用recur
if(B==nullptr||A==nullptr) return false;
return recur(A,B)||isSubStructure(A->left, B)||isSubStructure(A->right, B);
}
bool recur(TreeNode* A, TreeNode* B) //判断A和B是否相同
{
if(B==nullptr) return true; //在前面
if(A==nullptr||A->val!=B->val) return false;
return recur(A->left, B->left)&&recur(A->right, B->right);
}
};
剑指 Offer 27. 二叉树的镜像
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
class Solution {
public:
TreeNode* mirrorTree(TreeNode* root) {
if(root==nullptr) return root;
TreeNode *t=root;
swapNode(root);
return t;
}
void swapNode(TreeNode* root)
{
if(root==nullptr) return;
TreeNode *t=root->left;
root->left=root->right;
root->right=t;
swapNode(root->left);
swapNode(root->right);
}
};
剑指 Offer 28. 对称的二叉树
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(root==nullptr) return true;
return recur(root->left,root->right);
}
bool recur(TreeNode *root1,TreeNode *root2)
{
if(root1==nullptr&&root2==nullptr) return true;
if(root1==nullptr || root2==nullptr) return false;
if(root1->val!=root2->val) return false;
return recur(root1->left, root2->right)&&recur(root1->right, root2->left);
}
};
剑指 Offer 29. 顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
if(matrix.size()==0) return {};
int up=0,down=matrix.size()-1,left=0,right=matrix[0].size()-1;
vector<int> vec;
while(1)
{
for(int j=left;j<=right;j++)
{
vec.push_back(matrix[up][j]);
}
if(++up>down) break;
for(int j=up;j<=down;j++)
{
vec.push_back(matrix[j][right]);
}
if(--right<left) break;
for(int j=right;j>=left;j--)
{
vec.push_back(matrix[down][j]);
}
if(--down<up) break;
for(int j=down;j>=up;j--)
{
vec.push_back(matrix[j][left]);
}
if(++left>right) break;
}
return vec;
}
};
Q.E.D.