Pythonで最小の部分行列を見つけるプログラム
2D行列と別の値kがあるとします。私たちの目標は、すべてのkxkサブ行列の最小値を含む行列を返すことです。
したがって、入力が次のような場合
3 | 5 | 6 |
8 | 6 | 5 |
4 | 3 | 12 |
およびk=2、
その場合、出力は[[3、5]、[3、3]]になります。
入力から、左上の部分行列の最小値が3であることがわかります
3 5 8 6
右上の部分行列の最小値は5です
5 6 6 5
左下の部分行列の最小値は3です
8 6 4 3
右下の部分行列の最小値は3です
6 5 3 12
これを解決するには、次の手順に従います-
-
各r、インデックスrの行、およびマトリックスの項目行について、実行します
-
q:=新しい両端キュー
-
nrow:=新しいリスト
-
0から行のサイズまでの範囲のiの場合、実行します
-
qとq[0]がi--kと同じである場合、
-
qの左端のアイテムをポップ
-
-
qおよびrow[q[-1]]> row [i]がゼロ以外の場合、実行
-
qの右端のアイテムをポップ
-
-
qの右端にiを挿入します
-
nrowの最後にrow[q[0]]を挿入します
-
-
matrix [r]:=nrow
-
-
0からmatrix[0]のサイズまでの範囲のjの場合、実行
-
q:=新しい両端キュー
-
ncol:=新しいリスト
-
0から行列のサイズまでの範囲のiについては、次のようにします
-
qとq[0]がi--kと同じである場合、
-
qの左端のアイテムをポップ
-
-
qおよびmatrix[q[-1]] [j]> matrix [i] [j]がゼロ以外の場合、do
-
qの右端のアイテムをポップ
-
-
qの右端にiを挿入します
-
ncolの右端にmatrix[q[0]、j]を挿入します
-
0から行列のサイズまでの範囲のiについては、次のようにします
-
matrix [i、j]:=ncol [i]
-
-
-
-
ret:=0で初期化された行列のサイズの新しいリスト-k+ 1
-
0からretのサイズまでの範囲のiの場合、実行します
-
0からret[0]のサイズまでの範囲のjの場合、実行
-
ret [i、j]:=matrix [i + k-1、j + k-1]
-
-
-
retを返す
例
理解を深めるために、次の実装を見てみましょう-
import collections class Solution: def solve(self, matrix, k): for r, row in enumerate(matrix): q = collections.deque() nrow = [] for i in range(len(row)): if q and q[0] == i - k: q.popleft() while q and row[q[-1]] > row[i]: q.pop() q.append(i) nrow.append(row[q[0]]) matrix[r] = nrow for j in range(len(matrix[0])): q = collections.deque() ncol = [] for i in range(len(matrix)): if q and q[0] == i - k: q.popleft() while q and matrix[q[-1]][j] > matrix[i][j]: q.pop() q.append(i) ncol.append(matrix[q[0]][j]) for i in range(len(matrix)): matrix[i][j] = ncol[i] ret = [[0] * (len(matrix[0]) - k + 1) for _ in range(len(matrix) - k + 1)] for i in range(len(ret)): for j in range(len(ret[0])): ret[i][j] = matrix[i + k - 1][j + k - 1] return ret ob = Solution() print(ob.solve(matrix = [ [3, 5, 6], [8, 6, 5], [4, 3, 12] ], k = 2))
入力
[[3, 5, 6],[8, 6, 5],[4, 3, 12]], 2
出力
[[3, 5], [3, 3]]
-
グラフがPythonのすべての人によってトラバース可能かどうかを確認するプログラム
0からn-1までの番号が付けられたn個の頂点を含むグラフが与えられたとします。グラフは無向であり、各エッジには重みがあります。グラフには3種類の重みを設定でき、各重みは特定のタスクを示します。グラフをトラバースできるのは、ジャックとケーシーの2人です。エッジの重みが1の場合、ジャックはグラフをトラバースできます。重みが2の場合、ケーシーはグラフをトラバースできます。エッジの重みが3の場合、両方がグラフをトラバースできます。グラフを両方でトラバース可能にするために必要なエッジをすべて削除する必要があります。ジャックとケーシー。グラフをトラバース可能にするために削除するエッジの数を返します。トラバ
-
Pythonプログラムで配列の合計を見つける
この記事では、以下に示す問題ステートメントの解決策について学習します。 問題の説明 −配列の合計を計算するために必要な配列が与えられます。 合計を取得するために各インデックスで配列と要素全体をトラバースするブルートフォースアプローチについては、以下で説明します。合計を取得するための各インデックスについては、以下で説明します。 例 # sum function def sum_(arr,n): # using built-in function return(sum(arr)) # main arr = [11,22,33,44,55,66