关于Python的笔记

我为什么会写这个.

收到了一份亚马逊学生测试题,跟飞哥探讨了一下,又摸了下例题,选择放弃.
不过还是记载了.

翻例题答案时回想起自己也曾在python写过def main的function.
小葱拌豆腐行为,脑子清清白白.
上一次写纯python还是cs230或者cs231,那时还没有博客于是没有笔记记载,有些遗憾.

不知道这次图书馆更新结束后还会不会再续跟unity爱恨情仇的孽缘.

模拟题

今日嘉宾例题.

Find the missing number in the array

You are given an array of positive numbers from 1 to n, such that all numbers from 1 to n are present except one number x. You have to find x. The input array is not sorted.

import random #random.randint() function

def find_missing(input):
  # calculate sum of all elements
  # in input list
  sum_of_elements = sum(input)

  # There is exactly 1 number missing
  n = len(input) + 1
  actual_sum = (n * ( n + 1 ) ) / 2 # 哇一键计算arithmetic series sum好怀念
  return int(actual_sum - sum_of_elements) # 计算的时候默认return float,这里的int()从float转变为int,注意格式


def test(n):
  missing_element = random.randint(1, n)
  v = []
  for i in range(1, n): # 这里是在造missing一个值的array
    if i != missing_element:
      v.append(i)

  actual_missing = find_missing(v)
  print("Expected Missing = ", missing_element, " Actual Missing = ", actual_missing)
  assert missing_element == actual_missing


def main():
  for n in range(1, 10):
    test(1000000)

main()

这道题有意思的是:
The difference between these i.e. ‘expected_sum - sum_of_elements’, is the missing number in the array.
做了一个sum和difference.

Aside: Asset.

Determine if the sum of two integers is equal to the given value

Given an array of integers and a value, determine if there are any two integers in the array whose sum is equal to the given value. Return true if the sum exists and return false if it does not.

def find_sum_of_two(A, val): # A is the array
  found_values = set() # 这里create hash set
  for a in A:
    if val - a in found_values:
      return True

    found_values.add(a)

  return False

v = [5, 7, 1, 2, 8, 4, 3]
test = [3, 20, 1, 2, 7]

for i in range(len(test)):
  output = find_sum_of_two(v, test[i])
  print("find_sum_of_two(v, " + str(test[i]) + ") = " + str(output))

Aside: Set.
原来cs的set跟数学的set不一样啊!
set用于储存数据,好处可以guarantee search return O(1).
这里只做了一个array copy,然后比较差值是否在array中:从来看两数的sum是否在array里.

In this solution, you can use the following algorithm to find a pair that add up to the target (say val).
Scan the whole array once and store visited elements in a hash set.
During scan, for every element e in the array, we check if val - e is present in the hash set i.e. val - e is already visited.
If val - e is found in the hash set, it means there is a pair (e, val - e) in array whose sum is equal to the given val.
If we have exhausted all elements in the array and didn’t find any such pair, the function will return false.

Merge two sorted linked lists

好经典的题!

Given two sorted linked lists, merge them so that the resulting linked list is also sorted. Consider two sorted linked lists and the merged list below them as an example.

def merge_sorted(head1, head2):
  # if both lists are empty then merged list is also empty
  # if one of the lists is empty then other is the merged list
  # 当头就忘记empty的情况
  if head1 == None:
    return head2
  elif head2 == None:
    return head1

  mergedHead = None;
  if head1.data <= head2.data:
    mergedHead = head1
    head1 = head1.next
  else:
    mergedHead = head2
    head2 = head2.next

  mergedTail = mergedHead

  while head1 != None and head2 != None:
    temp = None
    if head1.data <= head2.data:
      temp = head1
      head1 = head1.next
    else:
      temp = head2
      head2 = head2.next

    mergedTail.next = temp
    mergedTail = temp

  if head1 != None:
    mergedTail.next = head1
  elif head2 != None:
    mergedTail.next = head2

  return mergedHead


array1 = [2, 3, 5, 6]
array2 = [1, 4, 10]
list_head1 = create_linked_list(array1)
print("Original1:")
display (list_head1)
list_head2 = create_linked_list(array2)
print("\nOriginal2:")
display (list_head2)
new_head = merge_sorted(list_head1, list_head2)

print("\nMerged:")
display(new_head)

Copy linked list with arbitrary pointer

You are given a linked list where the node has two pointers.
The first is the regular next pointer. The second pointer is called arbitrary_pointer and it can point to any node in the linked list.
Your job is to write code to make a deep copy of the given linked list. Here, deep copy means that any operations on the original list should not affect the copied list.

def deep_copy_arbitrary_pointer(head):
  if head == None:
    return None

  current = head;
  new_head = None
  new_prev = None
  ht = dict()

  # create copy of the linked list, recording the corresponding
  # nodes in hashmap without updating arbitrary pointer
  while current != None:
    new_node = LinkedListNode(current.data)

    # copy the old arbitrary pointer in the new node
    new_node.arbitrary = current.arbitrary;

    if new_prev != None:
      new_prev.next = new_node
    else:
      new_head = new_node

    ht[current] = new_node

    new_prev = new_node
    current = current.next

  new_current = new_head

  # updating arbitrary pointer
  while new_current != None:
    if new_current.arbitrary != None:
      node = ht[new_current.arbitrary]

      new_current.arbitrary = node

    new_current = new_current.next

  return new_head

def create_linked_list_with_arb_pointers(length):
  head = create_random_list(length)
  v = []
  temp = head
  while temp != None:
    v.append(temp)
    temp = temp.next

  for i in range(0, len(v)):
    j = random.randint(0, len(v) - 1)
    p = random.randint(0, 100)
    if p < 75:
      v[i].arbitrary = v[j]

  return head

def print_with_arb_pointers(head):
  while head != None:
    print(str(head.data) + " (", end="")
    if head.arbitrary != None:
      print(head.arbitrary.data, end ="")
    print("), ", end="")
    head = head.next;

  print()

# Test Program.
def main():
  head = create_linked_list_with_arb_pointers(9)
  print_with_arb_pointers(head)

  head2 = deep_copy_arbitrary_pointer(head)
  print_with_arb_pointers(head2)


main()

Level Order Traversal of Binary Tree

Given the root of a binary tree, display the node values at each level.
Node values for all levels should be displayed on separate lines.
Let’s take a look at the below binary tree.

# Using two queues
def level_order_traversal_1(root):
  if root == None:
    return

  queues = [deque(), deque()]

  current_queue = queues[0]
  next_queue = queues[1]

  current_queue.append(root)
  level_number = 0

  while current_queue:
    temp = current_queue.popleft()
    print(str(temp.data) , end = " ")

    if temp.left != None:
      next_queue.append(temp.left)

    if temp.right != None:
      next_queue.append(temp.right)

    if not current_queue:
      print()
      level_number += 1
      current_queue = queues[level_number % 2]
      next_queue = queues[(level_number + 1) % 2]
  print()

arr = [100,50,200,25,75,350]
root = create_BST(arr)
print("InOrder Traversal:", end = "")
display_inorder(root)
print("\nLevel Order Traversal:\n", end = "")
level_order_traversal_1(root)

Here, you are using two queues: current_queue and next_queue. You push the nodes in both queues alternately based on the current level number.
You’ll dequeue nodes from the current_queue, print the node’s data, and enqueue the node’s children to the next_queue. Once the current_queue becomes empty, you have processed all nodes for the current level_number. To indicate the new level, print a line break (’\n’), swap the two queues, and continue with the above-mentioned logic.
After printing the leaf nodes from the current_queue, swap current_queue and next_queue. Since the current_queue would be empty, you can terminate the loop.

然后放弃了思考

(测试的题目)

Reverse array queries

For a given array of integers, perform operations on the array. Return the resulting array after all operations have been applied in the order given.
Each operation contains two indices. Reverse the subarray between those zero-based indices, inclusive.

Example:
arr = [5, 3, 2, 1, 3]
operations = [[0, 1], [1, 3]]

In the first operations, reverse the subarray from arr[0] through arr[1]: arr’ = [3, 5, 2, 1, 3]
In the second operation, reverse the subarray from arr’[1] through arr’[3]: arr” = [3, 1, 2, 5, 3]
All operations have been performed, so return the array [3, 1, 2, 5, 3]

Function Description:
Complete the function performOperations in the editor below.

The function has the following parameter(s):

int arr[n]: an array of integers
int operations[q][2]: a 2-dimensional array of starting and ending indices

Returns:

int[n]: the final array after all operations have been performed

Constraints:

- 1 <= n, q <= 10^3
- 1 <= arr[i] <= 10^3
- 0 <= operations[i][0] <= operations[i][1] < n

Input from stdin will be processed as follows and passed to the function.

The first line contains an integer, n, the size of arr.
Each of the following n lines contains a single integer, arr[i].
The next line contains an integer, q, the size of operations.
In the second line, there is a single integer 2, the number of columns in each operations[i].
Each of the following q lines contains two space-separated integers, operations[i].

Sample Case 0:
Sample Input:

STDIN   Function
----    ----
3    -> arr[] size n = 3
1    -> arr = [1, 2, 3]
2
3
3    -> operations[] size q = 3
2    -> operations[q][] size columns = 2 (always = 2)
0 2  -> operations = [[0, 2], [1, 2], [0, 2]]
1 2
0 3

Sample Output:

2
1
3

Explanation:
The original array arr = [1, 2, 3].
Reverse arr[0] through arr[2]: arr’ = [3, 2, 1].
Reverse arr’[1] through arr[2]: arr” = [3, 1, 2].
Reverse arr”[0] through arr”[2]: arr’’’ = [2, 1, 3].

Sample Case 1:
Sample Input:

STDIN   Function
----    ----
4    -> arr[] size n = 4
5    -> arr = [5, 2, 5, 1]
2
5
1
2    -> operations[] size q = 2
2    -> operations[q][] size columns = 2
1 2  -> operations = [[1, 2], [1, 1]]
1 1

Sample Output:

5
5
2
1

Explanation:
The original array arr = [5, 2, 5, 1].
Reverse arr[1] through arr[2]: arr’ = [5, 5, 2, 1].
Reverse arr’[1] through arr[1]: arr” = [5, 5, 2, 1].

Code workspace:

#!/bin/python3

import math
import os
import random
import re
import sys


#
# Complete the 'performOperations' function below.
#
# The function is expected to return an INTEGER_ARRAY.
# The function accepts following parameters:
#  1. INTEGER_ARRAY arr
#  2. 2D_INTEGER_ARRAY operations
#

def performOperations(arr, operations):
    # Write your code here
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    arr_count = int(input().strip())

    arr = []

    for _ in range(arr_count):
        arr_item = int(input().strip())
        arr.append(arr_item)

    operations_rows = int(input().strip())
    operations_columns = int(input().strip())

    operations = []

    for _ in range(operations_rows):
        operations.append(list(map(int, input().rstrip().split())))

    result = performOperations(arr, operations)

    fptr.write('\n'.join(map(str, result)))
    fptr.write('\n')

    fptr.close()

Validating Strings with RegEx

Given a list of strings made up of the characters ‘a’ and ‘b’, create a regular expression that will match strings that begin and end with the same letter.

Example:
‘a’, ‘aa’, and ‘bababbb’ match.
‘ab’ and ‘baba’ do not match.

Replacing the blank (i.e., “__”) with a regular expression that matches strings as described.
Locked code in the editor prints True for each correct match and False for each incorrect match.

Constraints:

• 1 <= query <= 10^3
• 1 <= |string| <= 10^3
• Each character string[i] belongs to {a, b}

Input Format for Custom Testing:
Input from stdin will be processed as follows and passed to the function:

The first line contains an integer query, the number of strings to be tested.
Each of the next query lines contains a string to validate.

Sample Case 0:
Sample Input:

STDIN   Function
----    ----
5    -> number of strings to be tested, query = 5
a    -> query strings = 'a', 'b', 'ab', 'ba', 'aba'
b
ab
ba
aba

Sample Output:

True
True
False
False
True

Explanation:
The following query = 5 validations are performed:

• ‘a’ starts and ends with ‘a’, so it matches.
• ‘b’ starts and ends with ‘b’, so it matches.
• ‘ab’ starts with ‘a’ but ends with ‘b’, so it does not match.
• ‘ba’ starts with ‘b’ but ends with ‘a’, so it does not match.
• ‘aba’ starts and ends with ‘a’, so it matches.

Code workspace:

#!/bin/python3

from os import environ
from re import compile
from re import match


#
# Write the regular expression in the blank space below
#
regularExpression = '________'
pattern = compile(regularExpression)

query = int(input())
result = ['False'] * query

for i in range(query):
    someString = input()

    if pattern.match(someString):
        result[i] = 'True'

with open(environ['OUTPUT_PATH'], 'w') as fileOut:
    fileOut.write('\n'.join(result))

Precision and Recall

Given a 2-D matrix P of predicted values and actual values, write a function precision_recall to calculate precision and recall metrics.

Return the ordered pair (precision, recall).

This problem tests your familiarity with a confusion matrix.

A confusion matrix represents is a simple 2x2 array where each entry is the number of True Positive, False Positive, True Negative, and False Negative data points from any given binary experiment. The positions of each data category are shown in the example.

Let’s recall the definitions of precision and recall.

The formula for calculating precision is as follows:

$\frac{TP}{TP + FP}$

The precision value decreases as the number of False Positives increases. A lower FP value means our experiment was more precise.

The formula for calculating recall is:

$\frac{TP}{TP+FN}$

​The recall value decreases as the number of False Negatives increases. A False Negative indicates that we rejected a data point when we shouldn’t have and thus it should be recalled.

Once we are clear on the definitions of precision and recall, the problem is very easy to solve. We simply grab the relevant values from our input array P and plug them into the formulas which define precision and recall.

Our final code is as follows:

def precision_recall(P):

  precision = P[0][0] / (P[0][0] + P[1][0])

  recall = P[0][0] / (P[0][0] + P[0][1])

  return(precision,recall)

Alternates the cases of every alphabetic characters

这道题,我使用了set,用loop读取每个char,如果是alphabet就变更.用一个bool来记录要不要upper.

创造set.

Check duplicates

这道题比较经典,在stackoverflow上有找到.

Balanced smileys

这道题有点烦.但是有出处.

笔记

Basic

在LinkedIn上听python最基础的课程.
因为当年是一周内把基础语法扫过,直接开始整题.
现在补一点基础笔记.

Shebang

#!/usr/bin/env python3

演示的视频把这一行写在了python script的第一行,也就是让环境去跑python.
我不记得当年是怎么写python了,现在用jupyter,就不用shebang code了.

Scope

Python是用indention来区分block的.但不同block内define的variable,不同block都可以用.
原句:block does not define the scope of variables in Python.
但是functions, objects, modules do define scope in Python.

x = 42
y = 73

if x < y:
  z = 112

print('z is {}',format(z)) #这里z在不同block里define但是可以print

• Main

def main():
 theFunction()

if __name__ == '__main__': main()

Class

Class里的function会把self给扔回去.

class Duck:
  sound = 'Quaaaaack!'
  walking = 'Walking like a duck.'

  def quack(self):
    print(self.sound)

  def walf(self):
    print(self.walking)

def main():
  donald = Duck()
  donald.quack()
  donald.walk()

Type

Python uses a form of dynamic typing, sometimes called duck typing where the type of a value is determined by the value itself.
不像c语言,define一个variable会先写出variable的type.
python就直接写x = theValue.
然后跟着value的值,x成为不同的type.

关于precision python也有这个问题.
x = .1 + .1 + .1 - .3不等于零,会有一个小小小小的数.
为解决这个问题.

from decimal import *

a = Decimal('.10')
b = Decimal('.30')

x = a + a + a - b

可以使用decimal class.

Bitwise operators

& : And
| : Or
^ : Xor
<< : Shift left
>> : Shift right

阅读更多 - Python 中的位运算符.

Loop

secret = 'swordfish'
pw = ''
auth = False
count = 0
max_attempt = 5

while pw != secret:
    count += 1
    if count > max_attempt: break
    # continue can shortcut the loop
    # it sends back up to the top of the loop
    # and tests the condition again at whatever point.
    if count == 3: continue # then 3rd loop will skip pw = input line
    pw = input(f"{count}: What's the secret word? ")
else: # else only execute after while normally ends
    auth = True

print("Authorized" if auth else "Calling the FBI...")

Function

All function return a value, if not specified, then return [None].

Call by value:
When you pass a variable to a function, the function operates on a copy of the variable, the value is passed, but not the object itself.
就比如说在c里面.Function(a).
function里reassign a to 5,不会改变a是3的事实.

但python不同.Python全部都是pointer,python会把reference(指向实际的数值)pass过去.

Integer(in python) is not mutable, it cannot change when you assign a new value to an integer, you’re actually assigning an entirely different object to the name. The original integer is not changed. The name simply refers to a new object.

然而integer又又是个特例.Integer不会给reassign.
所以比如数值是存在array里的,就会被改变了.

Passing a value to the function acts exactly the same way. A reference of object has passed and acts exactly like an assignment.

A generator is a special class of function that serves as an iterator. Instead of returning a single value, the generator returns a stream of values.

#!/usr/bin/env python3
# Copyright 2009-2017 BHG http://bw.org/

def main():
    for i in inclusive_range(25):
        print(i, end = ' ')
    print()

def inclusive_range(*args):
    numargs = len(args)
    start = 0
    step = 1

    # initialize parameters
    if numargs < 1:
        raise TypeError(f'expected at least 1 argument, got {numargs}')
    elif numargs == 1:
        stop = args[0]
    elif numargs == 2:
        (start, stop) = args
    elif numargs == 3:
        (start, stop, step) = args
    else: raise TypeError(f'expected at most 3 arguments, got {numargs}')

    # generator
    i = start
    while i <= stop:
        yield i
        i += step

if __name__ == '__main__': main()

这里对yield的解释:yield is like return but for generator.

Yield

Omake之遇到一个data analyst相关的面试测试,要求写python.
以为是pandas/numpy相关,结果一打开:卧槽纯python.
不过比较简单,稍微查了下,用到了没用过的yieldfunction.
我理解为跟C中的std:in相似.