Algorithm

问题: Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets. Example 1: Input: 1 nums = [-1,0,1,2,-1,-4] Output: 1 [[-1,-1,2],[-1,0,1]] Example 2: Input: 1 nums = [] Output: 1 [] Example 3: ...

问题 Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order. Example 1: Input: 1 nums = [2,7,11,15], target = 9 Output: 1 [0,1] Output: ...

问题 Given a list of unique words, return all the pairs of the distinct indices (i, j) in the given list, so that the concatenation of the two words words[i] + words[j] is a palindrome. Example 1: Input: 1 words = ["abcd","dcba","lls","s","sssll"] Output: 1 [[0,1],[1,0],[3,2],[2,4]] Explanation: 1 The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"] Example 2: Input: 1 words = ["bat","tab","cat"] Output: 1 [[0,1],[1,0]] Explanation: ...

问题： Given an m x n board of characters and a list of strings words, return all words on the board. Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word. Example 1: Input: 1 board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"] Output: 1 ["eat","oath"] Example 2: ...

问题： Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 ≤ i ≤ j < n. Follow up: Could you do this in O(n) runtime? Example 1: Input: 1 nums = [3,10,5,25,2,8] Output: 1 28 Explanation: Constraints: 1 <= nums.length <= 2 * 104 0 <= nums[i] <= 231 - 1 解答： 穷举 将所有情况进行穷举，时间复杂度O(n2) ，不过不符合题目要求 1 2 3 4 5 6 7 8 class Solution: def findMaximumXOR(self, nums: List[int]) -> int: maxXor = 0 n = len(nums) for i in range(n): for j in range(i+1, n): maxXor = max(maxXor, nums[i]^nums[j]) return maxXor''' Trie树 时间复杂度O(n), 不过需要提前构建trie树 ...

leetcode 211 Trie的添加及搜索 Design a data structure that supports adding new words and finding if a string matches any previously added string. Implement the WordDictionary class: WordDictionary() Initializes the object. void addWord(word) Adds word to the data structure, it can be matched later. bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter. Example: ...

题目： In English, we have a concept called root, which can be followed by some other word to form another longer word - let’s call this word successor. For example, when the root "an" is followed by the successor word "other", we can form a new word "another". Given a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the successors in the sentence with the root forming it. If a successor can be replaced by more than one root, replace it with the root that has the shortest length. ...

题目： Implement a MapSum class with insert, and sum methods. For the method insert, you’ll be given a pair of (string, integer). The string represents the key and the integer represents the value. If the key already existed, then the original key-value pair will be overridden to the new one. For the method sum, you’ll be given a string representing the prefix, and you need to return the sum of all the pairs’ value whose key starts with the prefix. ...

题目： You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition: 1 2 3 4 5 6 struct Node { int val; Node *left; Node *right; Node *next; } Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. ...

题目： Given a binary tree 1 2 3 4 5 6 struct Node { int val; Node *left; Node *right; Node *next; } Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL. Follow up: You may only use constant extra space. Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem. Example 1: ...