学习帖， 每天总结今天学习成果

想问战拖组和个人有什么区别呢？

arnold8968 发表于 2019-3-27 23:16
想问战拖组和个人有什么区别呢？

不知道，我就随便找个地方写点东西。

一道概率题：
a box has six fair dice and a single unfair die with all sixes. One die is chosen at random and rolled twice. On both rolls, six appears.
What is the probability that the selected die is the unfair one?
First, bayes rule:
P(unfair | two sixes) = P(two sixes | unfair) * P(unfair) / P(two sixes)
                             = P(two sixes | unfair) * P(unfair) / (P(two sixes, unfair) + P(two sixes, fair))
                             = 1*1/7/(1*1/7 + 1/6*1/6*6/7)
                             = 6/7
Second, by drawing trees:
P(unfair | two sixes) = 6*6/(6*6 + 6) = 6/7

Coding:
Q1: Given a random generator, only generating 0 or 1, design a random generator to generate a number between a and b.
Python code:
Import numpy as np
#0, 1 generator
Def random_01():
        Return np.random.randint(2)
#a, b generator
Def random_ab(a, b, size):
        Target_range = b – a
        Target_length = len(format(target_range, ‘b’))
        For I In range(size):
                Generated_sum = 0
                For j in range(target_length):
                        Generated_sum += 2**j*random_01()
                If generated_sum <= target_range:
                        Print(a + target_range)

Q2:
Given an array[0, 4, 3, 5, 0, 2, 6], the start profit is 0, every element indicates the profit you can get, every time jump one step or two steps, can’t keep jumping twice, jump one step cost 2 profit, jump two steps cost 3 profit, you can stop in the middle. What is the largest profit you can get?
Using dynamic programming
Python code:

def find_largest(array):
    #indicating whether the previous jump is two steps jump
    two_steps = [0]*(len(array) + 1)
    #indicating from 0th element to the i-1th element in the array, the largest profit
    profit = [0]*(len(array) + 1)
    global_max = 0
    profit[1] = profit[0] + array[0] - 2
    global_max = max(global_max, profit[1])
    for i in range(2, len(array) + 1):
        if two_steps[i - 2] == 1:
            profit[i] = profit[i - 1] + array[i - 1] -2
            global_max = max(global_max, profit[i])
        else:
            #jump one step
            s1 = profit[i - 1] + array[i - 1] - 2
            #jump two steps
            s2 = profit[i - 2] + array[i - 1] - 3
            if s2 > s1:
                two_steps[i] = 1
                profit[i] = s2
                global_max = max(global_max, profit[i])
            else:
                profit[i] = s1
                global_max = max(global_max, profit[i])
return global_max

Q3: design KNN function, using heap



Probability:
Q1: You request a Lyft first which follows uniform distribution (0, 6). You will request another Uber if and only if the Lyft ride does not arrive after 3 minutes. Suppose that it takes no time to request a ride and that the Uber ride will arrive uniformly randomly between 0 and 8 minutes after the request, what will be the expected waiting time if you take whichever ride that arrives first.
手算的就不贴图了。结果是93/32

Python:
dp = [[0]*2]*2, dp: [[0, 0], [0, 0]]
dp[1][1] = 1 ==> dp: [[0, 1], [0, 1]]

dp = [[0]*2 for _ in range(2)], dp: [[0, 0], [0, 0]]
dp[1][1] = 1 ==> dp: [[0, 0], [0, 1]]

Leetcode 516:
Python:
# dp follows i*j, i represents the left index, j represents the rigth index, keep i <= j
# dp[j] represents the longest palindromic start from i end at j
# the diagonal elements have value 1# for off diagnonal element there are two situations, if s[i] == s[j] then the longest palindromic within [i+1, j-1]' length will increase 2; if s[i] != s[j] then the longest is either the longest length within [i, j - 1] or the longest length within [i + 1, j], the dp will start from bottom right[/i][/i]
[/i]
[i][i][i]def longestPalindromeSubseq(s):[/i][/i]
[i][i]     dp = [[0] * len(s) for _ in range(len(s))][/i][/i]
[i][i]     for i in range(len(s) - 1, -1, -1):[/i][/i]
[i][i]        dp[i][i] = 1[/i][/i]
[i][i]            for j in range(i + 1, len(s)):[/i][/i]
[i][i]                if s[i] == s[j]:[/i][/i]
[i][i]                    dp[i][j] = dp[i + 1][j - 1] + 2[/i][/i]
[i][i]                else:[/i][/i]
[i][i]                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])[/i][/i]
[i][i]    return dp[0][len(s) - 1][/i][/i]

You are working in Samara, Russia for a few days, Each day has a new pay per unit of work and a new cost per unit of food. Working 1 unit costs 1 unit of energy, and eating 1 unit of food adds 1 unit of energy. Here are some specifications of your employment:

+You arrive with no money, but with energy. You can never have more energy than you arrive with, and it can never be negative.

+You can do any amount of work every day (possibly not do any work at all), limited only by your energy. You cannot work when your energy is zero.

+You can eat any amount of food every day (possibly not have any food at all), limited by the money you have. You cannot eat when the money you have is zero.

+You can eat food at the end of the day, and cannot return to work after eating. You can return to work on the next day. Your true goal is to return home with as much money as possible. Compute the maximum amount of money you can take home.

For example, consider a 3 day stay where pay per unit work for each day is as follows: earning=[1, 2, 4]. The cost of food is cost=[1, 3, 6]. You start with e=5 units of energy.

*First day: 1 unit work is worth 1, and 1 unit food costs 1. There is no financial incentive to go to work this day.

*Second day: 1 unit work earns 2, and 1 unit food costs 3, Thus you spend more to eat than total earning so there is no financial incentive to go to work on this day.

*Third day: You earn 4 units per unit of work. The cost of food is irrelevant this day, as you are leaving for the home straight from work. You spend all of your energy working, collect your pay: 5 x 4 = 20 units of money and go home without buying dinner.

Function Description Complete the function calculateProfit in the editor below. The function must return an integer that represents the maximum earnings that can be taken home at the end of your stay.

Python code:
n = 3
earning = [7, 2, 4]
costing = [7, 3, 6]
e = 5
def maxProfit(n , earning, costing, e):
    dp = [[0]*(2*n - 1) for _ in range(e + 1)] #dp is (e+1)*(2*n - 1), odd column represents after work, even column represents after eat
    for j in range(2*n - 1): #j represents column
        for I in range(e + 1): #I represents row, I = 0 represents energy 5
            if j == 0: #the first day work
                  dp[i][j] = i*earning[j]
            elif j % 2 != 0: #the day eat
                  potential_max = [] #different after work energy can go to same energy after eat
                  for k in range(I, e + 1):
                        if dp[k][j - 1] >= (k - i)*costing[j//2]: #make sure having enough money to buy food
                             potential_max.append(dp[k][j - 1] - (k - i)*costing[j//2])
                  dp[i][j] = max(potential_max)
            elif j % 2 == 0: #the day work
                potential_max = [] #different after eat energy can go to the same after work energy
                for k in range(e + 1 - i):
                    potential_max.append(dp[k][j - 1] + (e - k - i)*costing[j//2])
                dp[e - i][j] = max(potential_max)
     return dp[-1][-1]