给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。 思路： B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]可以看作,B[i]=C[i]×D[i],C[i]=A[0]×A[1]×…×A[i-1],D[i]=A[i+1]×…×A[n-1] 可以先求出C和D，再求答案。 代码： class Solution { public: vector<int> constructArr(vector<int>& a) { int len = a.size(); if(len == 0) return {}; vector<int> left(len); vector<int> right(len); left[0] = 1;

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。 思路： 考虑使用位运算，对于整数a和整数b，求a+b，在位层面进行的话，每一位有四种情况： 0+0=0 1+0=1 0+1=1 1+1=10 前三种情况不需要进位，第四种情况需要进位，并且相加的位变为0。可以把位相加拆为两步：第一步不进位的相加a^b，第二步由第一步的结果加上需要进位的情况,进位的情况就是a&b<<1。而第二步的操作是另一个a+b，所以是递归的过程。终止条件就是(a&b<<1)==0 代码一： class Solution { public: int add(int a, int b) { if(b == 0) { return a; } return add(a^b,(a&b) << 1); } }; 代码二： class Solution { public: int add(int a, int b) {

求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。 思路： 使用递归，因为不能使用if，所以递归出口就要换一种方式，利用且和或的特性，x&&y，如果x为假，则y不执行。如果使用if，代码就是如下： class Solution { public: int sumNums(int n) { if(n == 0) { return 0; } n += sumNums(n-1) return n; } }; 换成且的方式就是如下代码 代码： class Solution { public: int sumNums(int n) { n && (n += sumNums(n-1)); return n; } };

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？ 示例 1: 输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。 示例 2: 输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。 思路： 遍历数组，用当前价格减去之前的最小值得到当前利润，然后和之前的利润比较得出最大利润。 代码： class Solution { public: int maxProfit(vector<int>& prices) { int len = prices.size(); if(len == 0) { return 0; } int maxPro = 0; int minP = prices[0

0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。 例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。 思路 使用链表模拟。 代码 #include <list> class Solution { public: int lastRemaining(int n, int m) { std::list<int> lister; for(int i = 0;i < n;i++) { lister.push_back(i); } auto cur = lister.begin(); while(lister.size() > 1) { for(int i = 1;i < m;i++) {