Python面接試験問題-積み上げ&演算過程
4138 ワード
今日は最初にpython募集の筆記試験問題をくださいましたが、難しさを見せてもらえますか?
最後のプログラミングの大きな問題は、pythonを使って整数配列のプッシュ・ソートを実現してください.
あまりにもずっとこの顺位に対してとても触発的なため、どのようにpythonを使って実现しますか?
具体的な概念は参考してください.http://blog.csdn.net/v_jurlyuv/articale/detail/6198644
=============華やかな分割線====================================================================
名詞の解釈:
初期配列:入力すると並べ替えが必要な配列
初期ヒープ:初期配列に基づいて、スタックの特徴に合う完全な二叉樹を作成します.
大きいルートの積み重ね:大きいルートの積み重ねるルートのノード
無秩序ヒープ:並べ替えの中で大きい根の積み重ねを取り出した後の残りの山.
1[0]:1は配列の値、0は識別ビットを表します.
以下は推演過程です.
A.初期配列:1[0]2[1]7[2]4[3]34[4]25[5]67[6]
B.初期ヒープ:
条件区間:
leftChild:3*2+1=7 right Child:3*2+2=8この時はarrSize Passよりも大きいです.
2.条件: 2
leftChild:2*2+1=5 right Child:2*2+2=6この時の最大値は67[6]で、7[2]と交換します.
このとき配列は、1[0]2[1]67[2]4[3]34[4]25[5]7[6]となります.
2.1サブ条件:6
leftChild:6*2+1=13 right Child:6*2+2=14この時はarrSizeよりも大きいです.再帰回帰します.
3.条件:1
leftChild:1*2+1=3 right Child:1*2+2=4この時の最大値34[4]は、2[1]と交換します.
このとき配列は、1[0]34[1]67[2]4[3]2[4]25[5]7[6]となります.
3.1サブ条件:4
leftChild:4*2+1=9 right Child:4*2+2=10この時はいずれもarrSizeより大きい再帰回帰です.
4.条件:0
leftChild:0*2+1=1 right Child:0*2+2=2この時の最大値は67[2]で、1[0]と交換します.
このとき配列は67[0]34[1]1[2]4[3]2[4]25[5]7[6]になります.
4..1サブ条件:2
leftChild:2*2+1=5 right Child:2*2+2=6この時の最大値は25[5]で、1[2]と交換します.
配列はこの時になります. 67[0]34[1]25[2]4[3]2[4]1[5]7[6]
4.2サブ条件:5
leftChild:5*2+1=11 right Child:5*2+2=12この時はarrSizeよりも大きい再帰回帰です.
初期ヒープは67[0]34[1]25[2]4[3]2[4]1[5]7[6]である.
ツリーは次のように表示されます
67[0] / \ 34[1] 25[2] / \ / \ 4[3]2[4]1[5] 7[6]
Cヒープの並べ替え:
条件は常に無秩序山の0です.
1.山の根元と最後の要素を交換します.
67[0]と7[6]を交換し、67[0]を無秩序山から取り出し、この時無秩序山: 7[0]34[1]25[2]4[3]2[4]1[5]
条件0で無秩序ヒータ(論理同上)を整理する:34[0]7[1]25[2]4[3]2[4]1[5]
2. 34[0]と1[5]を交換し、34[0]を無秩序ヒープから取り出します.このとき無秩序ヒープ:1[0]7[1]25[2]4[3]2[4]
条件0で無秩序ヒープを整理します.25[0]7[1]1[2]4[3]2[4]です.
3.1と2を繰り返す
最後の無秩序な山の中の元素は全部取り出して、そして山の並べ替えの最後の結果を構成します.
[1,2,4,7,25,34,67]
【備考】はっきりしたところが説明できないまで、ニヤリと笑って指摘してください.
助けてくれてありがとうございます.
仕事を楽しんでください
--------------------------------
Lawrency Meng
メール:[email protected]
本人Lawrencyはこのブログのすべての文章、内容、資料に対して著作権を有しています.
転載は必ず著者本人と出典を明記し、本人に通知します.二〇一三年三月五日です.
最後のプログラミングの大きな問題は、pythonを使って整数配列のプッシュ・ソートを実現してください.
あまりにもずっとこの顺位に対してとても触発的なため、どのようにpythonを使って実现しますか?
具体的な概念は参考してください.http://blog.csdn.net/v_jurlyuv/articale/detail/6198644
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim: tabstop=4 shiftwidth=4 softtabstop=4
# TODO: left child
# param: index
# return: the index of left child
def leftChild(index):
return index*2+1
# TODO: right child
# param: index
# return: the index of right child
def rightChild(index):
return index*2+2
# TODO: max exchange
# param: array index headSize
def maxHeap(array, index, heapSize):
# 01 Get the left and right node
leftInd = leftChild(index)
rightInd = rightChild(index)
# 02 compare the left,right,index vals
# get the max val and ind
largest = index
if leftInd < heapSize and array[index] < array[leftInd]:
largest = leftInd
if rightInd < heapSize and array[leftInd] < array[rightInd]:
largest = rightInd
# 03 exchange the largest and index val when index -ne largest and then recursive
if largest != index:
array[largest], array[index] = array[index], array[largest]
maxHeap(array,largest,heapSize)
# TODO build the heap
# param: array
def buildHeap(array):
for i in range(len(array)/2,-1,-1):
maxHeap(array,i,len(array))
# TODO: heap sort
# param: array
# return: heap sorted array
def heapSort(array):
buildHeap(array)
for i in range(len(array)-1,0,-1):
array[0], array[i] = array[i], array[0]
maxHeap(array,0,i)
arr=[1,2,7,4,34,25,67]
heapSort(arr)
print arr=============華やかな分割線====================================================================
名詞の解釈:
初期配列:入力すると並べ替えが必要な配列
初期ヒープ:初期配列に基づいて、スタックの特徴に合う完全な二叉樹を作成します.
大きいルートの積み重ね:大きいルートの積み重ねるルートのノード
無秩序ヒープ:並べ替えの中で大きい根の積み重ねを取り出した後の残りの山.
1[0]:1は配列の値、0は識別ビットを表します.
以下は推演過程です.
A.初期配列:1[0]2[1]7[2]4[3]34[4]25[5]67[6]
B.初期ヒープ:
条件区間:
range(len(array)/2,-1,-1) # 3,2,1,0maxHeap(array,largest,heapSize) # indexleftChild:3*2+1=7 right Child:3*2+2=8この時はarrSize Passよりも大きいです.
2.条件: 2
leftChild:2*2+1=5 right Child:2*2+2=6この時の最大値は67[6]で、7[2]と交換します.
このとき配列は、1[0]2[1]67[2]4[3]34[4]25[5]7[6]となります.
2.1サブ条件:6
leftChild:6*2+1=13 right Child:6*2+2=14この時はarrSizeよりも大きいです.再帰回帰します.
3.条件:1
leftChild:1*2+1=3 right Child:1*2+2=4この時の最大値34[4]は、2[1]と交換します.
このとき配列は、1[0]34[1]67[2]4[3]2[4]25[5]7[6]となります.
3.1サブ条件:4
leftChild:4*2+1=9 right Child:4*2+2=10この時はいずれもarrSizeより大きい再帰回帰です.
4.条件:0
leftChild:0*2+1=1 right Child:0*2+2=2この時の最大値は67[2]で、1[0]と交換します.
このとき配列は67[0]34[1]1[2]4[3]2[4]25[5]7[6]になります.
4..1サブ条件:2
leftChild:2*2+1=5 right Child:2*2+2=6この時の最大値は25[5]で、1[2]と交換します.
配列はこの時になります. 67[0]34[1]25[2]4[3]2[4]1[5]7[6]
4.2サブ条件:5
leftChild:5*2+1=11 right Child:5*2+2=12この時はarrSizeよりも大きい再帰回帰です.
初期ヒープは67[0]34[1]25[2]4[3]2[4]1[5]7[6]である.
ツリーは次のように表示されます
67[0] / \ 34[1] 25[2] / \ / \ 4[3]2[4]1[5] 7[6]
Cヒープの並べ替え:
条件は常に無秩序山の0です.
1.山の根元と最後の要素を交換します.
67[0]と7[6]を交換し、67[0]を無秩序山から取り出し、この時無秩序山: 7[0]34[1]25[2]4[3]2[4]1[5]
条件0で無秩序ヒータ(論理同上)を整理する:34[0]7[1]25[2]4[3]2[4]1[5]
2. 34[0]と1[5]を交換し、34[0]を無秩序ヒープから取り出します.このとき無秩序ヒープ:1[0]7[1]25[2]4[3]2[4]
条件0で無秩序ヒープを整理します.25[0]7[1]1[2]4[3]2[4]です.
3.1と2を繰り返す
最後の無秩序な山の中の元素は全部取り出して、そして山の並べ替えの最後の結果を構成します.
[1,2,4,7,25,34,67]
【備考】はっきりしたところが説明できないまで、ニヤリと笑って指摘してください.
助けてくれてありがとうございます.
仕事を楽しんでください
--------------------------------
Lawrency Meng
メール:[email protected]
本人Lawrencyはこのブログのすべての文章、内容、資料に対して著作権を有しています.
転載は必ず著者本人と出典を明記し、本人に通知します.二〇一三年三月五日です.