xiaolei565

面试题66. 构建乘积数组/238. 除自身以外数组的乘积(一般)给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。 示例:输入: [1,2,3,4,5]输出: [120,60,40,30,24] 提示：所有元素乘积之和不会溢出 32 位整数a.length <= 100000 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof 思路： 算法流程： 初始化：数组 B ，其中 B[0] = 1；辅助变量 tmp=1 ； 计算 B[i] 的 下三角 各元素的乘积，直接乘入 B[i] ； 计算 B[i] 的 上三角 各元素的乘积，记为 tmp ，并乘入 B[i] ； 返回 B 。 作者：jyd链接：https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof/so ...

面试题65. 不用加减乘除做加法(一般)写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。 示例:输入: a = 1, b = 1输出: 2 提示：a, b 均可能是负数或 0结果不会溢出 32 位整数 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof 思路：本题考察对位运算的灵活使用，即使用位运算实现加法。设两数字的二进制形式 a,b ，其求和 s=a+b ，a(i) 代表 a 的二进制第 i位，则分为以下四种情况： a(i) b(i) 无进位和 n(i) 进位c(i+1) 00 00 00 00 00 11 11 00 11 00 11 00 11 11 00 11 观察发现，无进位和 与 异或运算 规律相同，进位 和 与运算 规律相同（并需左移一位）。因此，无进位和 n 与进位 c 的计算公式如下；$$\begin{cases} n = a \oplus b &am ...

面试题64. 求1+2+…+n(一般)求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。 示例 1：输入: n = 3输出: 6 示例 2：输入: n = 9输出: 45 限制：1 <= n <= 10000 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/qiu-12n-lcof 思路：利用短路原则搞定递归返回条件 使用递归解法最重要的是指定返回条件，但是本题无法直接使用 if 语句来指定返回条件。 条件与 && 具有短路原则，即在第一个条件语句为 false 的情况下不会去执行第二个条件语句。利用这一特性，将递归的返回条件取非然后作为 && 的第一个条件语句，递归的主体转换为第二个条件语句，那么当递归的返回条件为 true 的情况下就不会执行递归的主体部分，递归返回。 本题的递归返回条件为 n <= 0，取非后就是 n > 0；递归的主体部分为 sum += Sum_Solutio ...

121. 买卖股票的最佳时机/面试题63. 股票的最大利润(简单)给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。 注意：你不能在买入股票前卖出股票。 示例 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。 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock 思路1：​ 找最大差值即可max(prices[j]-price[i]),j>i 前i日最大利润=max(前(i−1)日最大利润,第i日价格−前i日最低 ...

面试题62. 圆圈中最后剩下的数字(简单)0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。 例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。 示例 1：输入: n = 5, m = 3输出: 3 示例 2：输入:n = 10, m = 17输出: 2 限制： 1 <= n <= 10^51 <= m <= 10^6 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof 思路1：第一反应就是使用数组或者链表进行模拟，但是复杂度太高O（mn） 思路2：约瑟夫环问题递归解法的一点理解 约瑟夫环之二(用递归的思想解决Josephus问题) 约瑟夫环问题，这里参考题中一个解答 约瑟夫问题比较难想的点有两个： 当数到最后一个结点不足m个时，需要跳到第一个结点继续 ...

面试题60. n个骰子的点数(一般)从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。 示例 1:输入: [1,2,3,4,5]输出: True 示例 2:输入: [0,0,1,2,5]输出: True 限制：数组长度为 5 数组的数取值为 [0, 13] . 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof 思路1：注意大小王是可以随配的 可以走个捷径，判断最大值与最小值的差大于小于5，小于5，肯定是同花顺，但是要注意先排序，判断最后一个大小王， 思路2：同思路1，只是将排序换成set进行去重 dp[i] [j]表示掷i个骰子，出现j点数的次数 转移方程为 dp[i] [s] += dp[i-1] [s-j];//转移方程 ，当前n个骰子出现的点数之和等于前一次出现的点数之和加上这一次出现的点数 回看记录200726这个思路真的 ...

面试题60. n个骰子的点数(一般)把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。 你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。 示例 1:输入: 1输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667] 示例 2:输入: 2输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778] 限制： 1 <= n <= 11 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof 思路：动态规划思路： dp[i] [j]表示掷i个骰子，出现j点数的次数 转移方程为 dp[i] [s] += dp[i-1] [s-j];//转移方程 ，当前n个骰子出现的点数之和等于前一次出现的点数之和加 ...

面试题59 - II. 队列的最大值(一般)请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。 若队列为空，pop_front 和 max_value 需要返回 -1 示例 1：输入:[“MaxQueue”,”push_back”,”push_back”,”max_value”,”pop_front”,”max_value”][[],[1],[2],[],[],[]]输出: [null,null,null,2,1,2] 示例 2：输入:[“MaxQueue”,”pop_front”,”max_value”][[],[],[]]输出: [null,-1,-1] 限制：1 <= push_back,pop_front,max_value的总操作数 <= 100001 <= value <= 10^5 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lco ...

面试题58 - II. 左旋转字符串(简单)字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。 示例 1：输入: s = “abcdefg”, k = 2输出: “cdefgab” 示例 2：输入: s = “lrloseumgh”, k = 6输出: “umghlrlose” 限制：1 <= k < s.length <= 10000 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof 思路：逆转前n个字符，再逆转后面的，最后将整体逆转，就实现了整体左旋 代码1：1234567891011121314151617181920class Solution { public String reverseLeftWords(String s, int n) { ...

面试题57 - II. 和为s的连续正数序列(一般)输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。 示例 1：输入：target = 9输出：[[2,3,4],[4,5]] 示例 2：输入：target = 15输出：[[1,2,3,4,5],[4,5,6],[7,8]] 限制：1 <= target <= 10^5 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof 思路1： 创建双指针i，j都指向1，sum求和。i，j之间就是窗口大小 若target大于sum说明数字之和 不够，右指针j需要右移j++直至sum小于target（等于时直接跳出存储结果到list） 若此时target小于sum说明数字之和 超出，调整左指针i–直至满足sum=target 算法步骤 创建指针、求和变量和list集合（用于存储满足的结果） ...