解决本道题目首先需要求解出一个整数二进制表示法中 1 的个数。
朴实的解法：将整数转化为二进制字符串，再统计 1 的个数。
更加效率的解法： 利用位运算的特性去掉转化的过程并且减少迭代的次数 。
最后通过 JavaScript 中 sort 方法进行多条件排序，即可解题。
02 实现每隔 n 个顾客打折 题目描述【Medium】 超市里正在举行打折活动，每隔 n 个顾客会得到 discount 的折扣。超市里有一些商品，第 i 种商品为 products[i] 且每件商品的价格为 prices[i]。 结账系统会统计顾客的数目，每隔 n 个顾客结账时，该顾客的账单都会打折，折扣为 discount，然后系统会重新开始计数。 顾客会购买一些商品，product[i] 是顾客购买的第 i 种商品，amount[i] 是对应的购买该种商品的数目。 请实现 Cashier 类。
这道题目给的条件相对比较多，需要仔细阅读条件，注意 几个变量之间的下标关系，具体实现代码如下：
通过暴力枚举，可以在 O(n^2) 的时间复杂度内统计合法的子串。
对于字符串 [0, i]，如果 [0, j] 为合法字串，那么 [0, j+1] 必然也为合法字串。
利用上述特性，可以减少内循环的次数，具体实现代码如下：
但是，本道题 O(n^2) 的时间复杂度是没法 AC 的。
从上述暴力枚举的过程中，可以发现只要找到最小的合法字串，其他包含该字串的数目很容易计算。而对于任意一个子串，无非就是开始下标和结束下标，那么就可以采用双指针技巧，将时间复杂度降低为 O(n) 。
再利用哈希表记录当前子串中字符的状态，从而减少子串验证合法性的时间复杂度。
这是一道动态规划的题目，可以定义 dp[i] 表示 i 笔订单有效序列的个数。
由上述题目中给出的信息，可以很容易知道：
-
dp[0] = 0
-
dp[1] = 1
那么当 i = 2 时，可以基于 i = 1 进行如下操作得到所有有效序列。
第一种情况：将 P2D2 合并在一起插入到前一个状态中。
第二种情况：将 P2D2 分开插入，保证 P2 在 D2 之前。
根据上述推导过程，可以得到如下状态转移方程：
由推导公式，可以发现下一个状态只与前一个状态有关系，那么就没必要利用数组记录无关的状态，时间复杂度可以降低为 O(1)。
最后千万不要忘记对结果取余哦。
