联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-21:00
  • 微信:codinghelp

您当前位置:首页 >> Python编程Python编程

日期:2021-03-05 11:11

Default Dictionaries

The following code returns a dictionary with the word count for each word in a list of words.

def count_words(l):

d = {}

for word in l:

if word not in d:

d[word] = 1

else:

d[word] += 1

return d

Notice that we need to have two cases: one for if the word is not in the dictionary, and the other

for if it is.

We can shorten the code by using a default dictionary.

from collections import defaultdict

def count_words2(l):

d = defaultdict(int)

for word in l:

d[word] += 1

return d

When creating a default dictionary, we must pass it the type of the values that will be stored in

the dictionary. We can use any type that we want, including lists. The following code takes a list

of words as an argument and returns a dictionary containing lists of the words that have the same

first letter.

def list_words(dictionary_of_words):

d = defaultdict(list)

for word in dictionary_of_words:

d[word[0]].append(word)

return d

result = list_words(["antelope", "bear", "alligator", "aardvark", "cat", "bee"])

print(result)

1

Deques

So far in this course, we have been working with lists. A list is an object that is built on top of an

array. Arrays store elements in contiguous computer memory. This allows us constant time access

to any element in the array through indexing. Arrays do have a drawback, however. If we remove

the first element in an array, every other element in the array needs to be shifted to the left. In

other words, removing an element from a list can take linear time.

Figure 1: The list before the first element is removed.

Figure 2: The first element is removed.

Figure 3: The remaining elements must be shifted to the left.

A Deque is a double-ended queue which is implemented using a linked-list. Unlike with lists,

you can’t access elements in constant time. However, you can remove the first element of a deque

in constant time. Here is what a doubly linked-list looks like.

2

Figure 4: A doubly link list.

Tp remove the first element, simply remove the links off of the first element and have the headpointer

point to the second element. This can be done is constant time regardless of the length of

the linked list.

Deques can be used as both stacks and queues. Use the methods append() and pop() to emulate

a stack using a deque. The methods append() and popleft() can be used to emulate a queue.

The deque class must be imported before you can use it.

from collections import deque

To create an empty deque use

deque_name = deque()

Homework

1. Write a method called is balanced(s) that take a string of open and closed parentheses and

returns True if the string is balanced, False otherwise. The method should use a deque as a

stack.

For example, the following parentheses are balanced:

()()

(())()

While the following are not:

()(

))()

2. Write a method that implements breadth-first search on an undirected graph. Your method

should be called bfs(graph, start), where graph is a dictionary representation of a graph, and

start is the starting vertex. The vertices of the graph are number 0, 1, 2, 3, . . . , n. The

method should return a list containing the distance from the starting vertex for each vertex

in the graph.

Below is the psuedo-code for the method you will inplement:

Create a list that holds the distance of each vertex from the source vertex. Set distance

of the starting vertex to 0, the rest to infinity.

3

Create a queue and put the starting vertex on the queue.

while the queue has elements in it:

Remove the element at the front of the queue.

For each vertex that the element you removed is adjacent to in the graph, check to see if

that vertex has been visited yet using the distance list from above. If it hasn’t been visited,

then set its distance from the starting vertex and add it to the queue.

When the loop breaks, return the list of distances.

4


版权所有:编程辅导网 2021 All Rights Reserved 联系方式:QQ:99515681 微信:codinghelp 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。 站长地图

python代写
微信客服:codinghelp