题目

已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数，试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。

不要使用系统的 Math.random() 方法。

示例 1:

输入: 1
输出: [7]

示例 2:

输入: 2
输出: [8,4]

示例 3:

输入: 3
输出: [8,1,10]

提示:

1. rand7 已定义。
2. 传入参数: n 表示 rand10 的调用次数。

进阶:

1. rand7()调用次数的 期望值 是多少 ?
2. 你能否尽量少调用 rand7() ?

   思路

3. 重复调用10次rand7(),这样能够生成1~70的随机数，接着对10取余即可。
4. 基于公式
   $$(randX()-1)*randY()+randY()$$
   生成1~X*Y之内的随机数。

• 为了减少对rand7()的调用，需要对不同的1~X*Y之内的随机数进行判断。
  • 首先生成1~49之间的数，如果在1~40之间，直接对10取余即可。
  • 如果在41~49之间，减去40后就是一个1~9之间的随机数，仍然调用以上公式，生成1~63之间的随机数。
    • 如果在1~60之间，直接对10取余即可。
    • 如果在61~63之间，减去60后就是一个1~3之间的随机数，仍然调用上述公式，生成一个1~21之间的随机数……
      到这里，如果想要继续嵌套可以，但是此时还没有生成的概率已经很小了。如果还没有生成直接在大循环中重新生成也可以。

3. 其他思考
   我尝试将两种概率分布都转化为正态分布，
   $$\frac{(rand7()-mean(rand7())}{std(rand7()))}=\frac{(rand10()-mean(rand10())}{std(rand10())}$$
   之后移项的方式来进行生成，但是不知道为什么一直不对：
   $$\frac{(rand7()-mean(rand7())*std(rand10())}{std(rand7())}+mean(rand10()))=rand10()$$

代码

1. 暴力法

   1 2 3 4 5 6 7 8 9 10 11 12

   // The rand7() API is already defined for you. // int rand7(); // @return a random integer in the range 1 to 7 class Solution { public: int rand10() { int n = 0; for(int i=0;i<10;i++) n+=rand7(); return n%10+1; } };

2. 公式法

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

   // The rand7() API is already defined for you. // int rand7(); // @return a random integer in the range 1 to 7 class Solution { public: int rand10() { while(true){ int num = (rand7()-1)*7+rand7(); if(num<=40) return 1+num%10; num = (num-40-1)*rand7()+rand7(); if(num<=60) return 1+num%10; num = (num-60-1)*rand7()+rand7(); if(num<=20) return 1+num%10; } return -1; } };

题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

思路

1. 最简单的暴力，复杂度O(N^2)
2. 使用Hash，复杂度O(NlogN)。使用unordered_map来实现已经logN级别的搜索。

代码

1. 暴力解法

   1 2 3 4 5 6 7 8 9 10 11 12 13

   class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { for(int i=0;i<nums.size();i++){ for(int j=nums.size()-1;j>i;j--){ if(nums[i]+nums[j]==target){ return {i,j}; } } } return {}; } };

1. Hash解法

   1 2 3 4 5 6 7 8 9 10 11 12 13 14

   class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int,int> m; for(int i=0;i<nums.size();i++){ auto f = m.find(target-nums[i]); if(f!=m.end()){ return {min(i,f->second),max(i,f->second)}; } m[nums[i]]=i; } return {}; } };

题目

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

• 每个链表中的节点数在范围 [1, 100] 内
• 0 <= Node.val <= 9
• 题目数据保证列表表示的数字不含前导零

思路

​ 思路比较简单，就是从末尾开始相加，设置一个进位符op，循环结束条件为两个指针都为NULL并且进位符为0。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* head = new ListNode(0);
        ListNode* point = head;
        int op = 0;
        while(l1!=NULL||l2!=NULL||op==1){
            int v1 = l1==NULL?0:l1->val;
            int v2 = l2==NULL?0:l2->val;
            int v = v1 + v2 + op;
            op = v / 10;
            head->next = new ListNode(v%10);
            head=head->next;
            l1 = l1==NULL?NULL:l1->next;
            l2 = l2==NULL?NULL:l2->next;
        }
        return point->next;
    }
};