东莞正规制作网站公司吗,进出成都最新通知,阳泉住房建设局网站,丁香园做科室网站专注 效率 记忆 预习 笔记 复习 做题 欢迎观看我的博客#xff0c;如有问题交流#xff0c;欢迎评论区留言#xff0c;一定尽快回复#xff01;#xff08;大家可以去看我的专栏#xff0c;是所有文章的目录#xff09; 文章字体风格#xff1a; 红色文字表示#…专注 效率 记忆 预习 笔记 复习 做题 欢迎观看我的博客如有问题交流欢迎评论区留言一定尽快回复大家可以去看我的专栏是所有文章的目录 文章字体风格 红色文字表示重难点★✔ 蓝色文字表示思路以及想法★✔ 如果大家觉得有帮助的话感谢大家帮忙 点赞收藏转发 本博客带大家一起学习我们不图快只求稳扎稳打。 由于我高三是在家自学的经验教训告诉我学习一定要长期积累并且复习所以我推出此系列。 只求每天坚持40分钟一周学5天复习2天 也就是一周学10道题 50天后我们就可以学完76道题相信50天后我们一定可以有扎实的代码基础我们每天就40分钟和我一起坚持下去吧 qq群866984458 本题出自 acwing网站 这个系列是免费的 打卡即刻退回费用。 第四十七天【剑指Offer例题代码 系列】 72. 求12…n【递归】73. 不用加减乘除做加法【二进制 加法】int sum num1 ^ num2;//不进位的加法int carry (num1 num2)1;//进位 74. 构建乘积数组 72. 求12…n【递归】 (递归) O(n) 最直接的想法就是用递归sum(n) nsum(n-1)但是要注意终止条件由于求的是12…n的和所以需要在n0的时候跳出递归但是题目要求不能使用if,while等分支判断可以考虑利用短路运算来终止判断。
时间复杂度分析递归复杂度为O(n)。
class Solution {
public:int getSum(int n) {int res n;n 0 (res getSum(n - 1));return res;}
};73. 不用加减乘除做加法【二进制 加法】
int sum num1 ^ num2;//不进位的加法
int carry (num1 num2)1;//进位 class Solution {
public:int add(int num1, int num2){while(num2!0){int sum num1 ^ num2;//不进位的加法int carry (num1 num2)1;//进位num1 sum;num2 carry;}return num1;}
};74. 构建乘积数组 (动归) O(n) 用两个数组left和rightleft[i]A[0]A[1]…*A[i-1], left[i]A[i-1]*left[i-1]; right[i] A[i1]A[i2]…*A[n-1]则right[i]A[i1]*right[i1]。
最后结果B[i]left[i]*right[i]。
时间复杂度分析需要遍历数组复杂度为O(n)
class Solution {
public:vectorint multiply(const vectorint A) {vectorintleft(A.size(),1);vectorintright(A.size(),1);for(int i 1;iA.size();i){left[i] A[i-1]*left[i-1];}for(int i A.size()-2;i0;i--){right[i] A[i1]*right[i1];}vectorintB(A.size(),0);for(int i 0;iA.size();i){B[i] left[i]*right[i];}return B;}
};
