双向BFS未看 leetcode 1. 两数之和 126. 单词接龙 II 1442. 形成两个异或相等数组的三元组数目

1. 两数之和

我想的是全部排进哈希表再查，但是可以一边放一边查，效率更高。

class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:num_count = defaultdict(list)for i in range(len(nums)):num_count[nums[i]]+=[i]for val,li in num_count.items():if target-val ==val:if len(li)>1:return [li[0],li[1]]elif target-val in num_count:return [li[0],num_count[target-val][0]]

class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:num_pos = {
    }for i,val in enumerate(nums):if target-val in num_pos:return [num_pos[target-val],i]else:num_pos[val]=i

126. 单词接龙 II

只能想到构建邻接表，然后深搜，但是超时了。

class Solution:def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:if len(wordList) == 0 or endWord not in wordList:return []degree = defaultdict(set)lenword = len(wordList[0])show_first_pos = {
    }show_first_pos[beginWord] = len(wordList) + 1for val in wordList:show_first_pos[val] = len(wordList) + 1def neighbour(word1, word2, lenword):one_diff = Falsefor k in range(lenword):if word1[k] != word2[k]:if not one_diff:one_diff = Trueelse:one_diff = Falsebreakreturn one_difffor i in range(len(wordList)):for j in range(i + 1, len(wordList)):if neighbour(wordList[i], wordList[j], lenword):degree[wordList[i]].add(wordList[j])degree[wordList[j]].add(wordList[i])if beginWord not in wordList:for j in range(len(wordList)):if neighbour(beginWord, wordList[j], lenword):degree[beginWord].add(wordList[j])def dfs(degree, start, end, visited, path, result, minlen, show_first_pos):if len(path) > show_first_pos[start] or len(path) > minlen:returnif start == end or end in degree[start]:path += [start] if start != end else []path += [end]if len(path) < minlen:minlen = len(path)result.append(path.copy())for i, val in enumerate(path):show_first_pos[val] = min(show_first_pos[val], i)returnif start in visited:returnfor word in degree[start]:dfs(degree, word, end, visited + [start], path + [start], result, minlen, show_first_pos)result = []dfs(degree, beginWord, endWord, [], [], result, 9999, show_first_pos)minlen = 9999for li in result:if len(li) < minlen:minlen = len(li)return [x for x in result if len(x) == minlen]

已经尽力优化了，在 21 / 39 个通过测试用例还是超时。看解析学习一下。

一个优化的点就是判断单词是否只有一个字母不同时，不用两次循环，用替换一个字母，然后查找集合里是否存在这个单词。

class Solution:def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:if len(wordList) == 0 or endWord not in wordList:return []degree = defaultdict(set)lenword = len(wordList[0])show_first_pos = {
    }show_first_pos[beginWord] = len(wordList) + 1for val in wordList:show_first_pos[val] = len(wordList) + 1wordset = set(wordList)import timecur2 = time.time()for i in range(len(wordList)):for j in range(lenword):for k in range(97,123):new_word = wordList[i][:j]+chr(k)+wordList[i][j+1:]if new_word in wordset:degree[wordList[i]].add(new_word)degree[new_word].add(wordList[i])if beginWord not in wordList:for j in range(lenword):for k in range(97,123):new_word = beginWord[:j]+chr(k)+beginWord[j+1:]if new_word in wordset:degree[beginWord].add(new_word)print(time.time()-cur2)def bfs(degree,beginWord, endWord):stop = Falseresult = []queue = deque()queue.append([beginWord])while queue and not stop:size = len(queue)for i in range(size):tmp_path = queue.popleft()for word in degree[tmp_path[-1]]:if word in tmp_path:continueif word==endWord:result.append(tmp_path.copy()+[word])stop=Trueelse:if len(tmp_path)>show_first_pos[word]:continueelse:show_first_pos[word] = len(tmp_path)queue.append(tmp_path.copy()+[word])return resultresult = bfs(degree, beginWord, endWord)return result

1442. 形成两个异或相等数组的三元组数目

class Solution:def countTriplets(self, arr: List[int]) -> int:dp = [[0]*len(arr) for _ in range(len(arr))]for i in range(len(arr)):dp[i][i] = arr[i]for j in range(i+1,len(arr)):dp[i][j]=dp[i][j-1]^arr[j]result = 0dp_set = [defaultdict(int) for _ in dp]for i in range(len(arr)):for j in range(i,len(arr)):dp_set[i][dp[i][j]] += 1for i in range(len(arr)):for j in range(i+1,len(arr)):if dp[i][j-1] in dp_set[j]:result+=dp_set[j][dp[i][j-1]]return result

出处

解题思路：

时间复杂度O(N^2)，空间复杂度O(1)。

首先，数组长度小于2的时候，必然是0。其次，观察到a = arr[i] ^ arr[i + 1] ^ … ^ arr[j - 1],b = arr[j] ^ arr[j + 1] ^ … ^ arr[k],那么根据位运算的规则， a^b=arr[i] arr[i + 1] ^ … ^ arr[k]，即i到k。
此外，根据位运算，如果a^b==0,那么a==b，这是逆否命题，即反推也成立。

而固定了两端之后，中间的j可以任意取，故有k-i种。每次计算完，如果满足条件，在ans里加上k-i即可。

代码

class Solution:def countTriplets(self, arr: List[int]) -> int:if len(arr)<2:return 0ans=0for i in range(len(arr)):temp=arr[i]for j in range(i+1,len(arr)):temp=temp^arr[j]if temp==0:ans+=j-ireturn ans

class Solution:def countTriplets(self, arr: List[int]) -> int:res = defaultdict(list)tmp=0res[0]=[-1]for i,a in enumerate(arr):tmp^=ares[tmp]+=[i]result = 0for s,li in res.items():if len(li)==0:continuefor i in range(len(li)):for j in range(i+1,len(li)):result+=li[j]-li[i]-1return result