這題的通過時間改為 1s

我的程式再怎麼精簡都無法通過，請問有人可以嗎?

這題的通過時間改為 1s

我的程式再怎麼精簡都無法通過，請問有人可以嗎?

我也不能Q

哈，

這題雖然有人過，

但是也有可能是當時 server 的速度造成的 AC。

我用 cpp 寫 AC(90 ms) 了，

想說拿一樣的方法用 python 寫寫看，

結果吃了一個 TLE (3s killed)。

建議也算法正確的話，

python 的朋友可以試試看用 cpp。

bytearray + sys.stdout.buffer.write

bytearray + sys.stdout.buffer.write

完全不會 一樣TLE 可是我測資3.4ms  AC 耶 需要把輸出資料的跳行都刪掉 要不然會一直WA(line2)

以下是我的py code:

class Solution:

# @param {integer} n

# @return {string[]}

    def generateParenthesis(self, n):

        if not n:

            return []

        left, right, ans = n, n, []

        self.dfs(left,right, ans, "")

        return(ans)

    def dfs(self, left, right, ans, string):

        if right < left:

            return

        if not left and not right:

            ans.append(string)

            return

        if left:

            self.dfs(left-1, right, ans, string + "(")

        if right:

            self.dfs(left, right-1, ans, string + ")")

try:

    while True:

        N = 0

        N=int(input())

        print('\n')

        if 1<=N<=13:

            ans =Solution()

            String =(ans.generateParenthesis(N))

            for x in range(len(String)):

                print(String[x])

            print('\n')

        print('\n')

except EOFError:

    pass

一、儲存資料及輸出的方式

python string 是 immutable，每次對 string 內容修改，都會重新分配新的記憶體(可以用 print(id(var_name)) 來看物件是否有改變)，

為了減少這些時間，

先想到使用一個 char array list 來存 string，最後再將 list 轉成 string 輸出，

例如:

buf = ['(', '(', ')', ')']

# buf[1] = ord('(') , ord 也花時間

buf[1] = 41

# buf[2] = ord(')')

buf[2] = 40

print(''.join(buf))

但發現 char array list 轉 string 也花時間，

再進一步減少輸出轉換的時間，

最後改用既可修改內容又可以直接輸出不需要額外轉換的 bytearray

例如: 

buf = bytearray(b'(())\n')

# 輸出 (())

sys.stdout.buffer.write(buf);

buf[1] = 41

buf[2] = 40

# 輸出 ()()

sys.stdout.buffer.write(buf);

# 輸出 ()()

sys.stdout.buffer.write(b'()' + b'()' + b'\n');

二、演算法改進

常見的是 dfs 分別對每個位置做 '(' 和 ')' 遞迴

因為括號是成對出現的，所以也可以把  '(' 和 ')' 看成一組來處理，也就是以 '()'為單位，就少了一倍的運算

# buf[1] = ord(')')

# buf[2] = ord('(')

更正筆誤

from sys import stdin
from itertools import chain

legals = {1: {0b10}}

def parent(N):
	try:
		return sorted(legals[N],reverse=True)
	except KeyError:
		for i in range(max(legals.keys())+1, N+1):
			legals[i] = set(chain.from_iterable(((l+4**(i-1))*2, l+2**(2*i-1), l*4+2) for l in legals[i-1])).union(
				chain.from_iterable((a*4**j+b for a in legals[i-j] for b in legals[j]) for j in range(2, i-1)))
	return sorted(legals[N],reverse=True)


for line in stdin:
	line=line.strip('\n')
	if line:
		N = int(line)
		print(*(f"{i:b}".translate({49: 40, 48: 41}) for i in  parent(N)), sep='\n', end='\n\n')

我這樣可以耶

from sys import stdin
from itertools import chain

legals = {1: {0b10}}

def parent(N):
	try:
		return sorted(legals[N],reverse=True)
	except KeyError:
		for i in range(max(legals.keys())+1, N+1):
			legals[i] = set(chain.from_iterable(((l+4**(i-1))*2, l+2**(2*i-1), l*4+2) for l in legals[i-1])).union(
				chain.from_iterable((a*4**j+b for a in legals[i-j] for b in legals[j]) for j in range(2, i-1)))
	return sorted(legals[N],reverse=True)


for line in stdin:
	line=line.strip('\n')
	if line:
		N = int(line)
		print(*(f"{i:b}".translate({49: 40, 48: 41}) for i in  parent(N)), sep='\n', end='\n\n')

我這樣可以耶

 

我試了以上Python code, 一樣TLE

這題的通過時間改為 1s

我的程式再怎麼精簡都無法通過，請問有人可以嗎?

好像不會ㄚ

我今天再丟我的也是2s (< 1s* 3)

應該是穩穩的