Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Note Your returned answers (both index1 and index2) are not zero-based. You may assume that each input would have exactly one solution and you may not use the same element twice.
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list. Solution Solution 1: Insert cloned nodes in between original nodes then connect the cloned nodes # Definition for singly-linked list with a random pointer. # class RandomListNode(object): # def __init__(self, x): # self.label = x # self.next = None # self.
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is. Example Given this linked list: 1->2->3->4->5 For k = 2, you should return: 2->1->4->3->5
Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors. Example: Input: {"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1} Explanation: Node 1's value is 1, and it has two neighbors: Node 2 and 4. Node 2's value is 2, and it has two neighbors: Node 1 and 3. Node 3's value is 3, and it has two neighbors: Node 2 and 4.
Reverse a singly linked list. Example: Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both? Solution: /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode cur = head, prev = null, after = new ListNode(0); // null 1 -> 2 -> 3 -> 4 -> 5 -> NULL // prev cur after while (cur !
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. Example Input: "aab" Output: [ ["aa","b"], ["a","a","b"] ] Solution # Time: O(n*2^n) # Space: `O(n)`. At any time, only one call stack will be in progress # For example, in put 'ababaaeqwds', one possible call stack will look like 'aba'->'b'->'aa'->'e'->'q'->'w'->'d'->'s': n space class Solution: def partition(self, s: str) -> List[List[str]]: if len(s) == 0 or s == None: return [] results = [] temp = [] self.
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. Each number in candidates may only be used once in the combination. Note All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. Example 1 Input: candidates = [10,1,2,7,6,1,5], target = 8, A solution set is: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ] ###Example 2:
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: [ "((()))", "(()())", "(())()", "()(())", "()()()" ] Solution class Solution: def generateParenthesis(self, n: int) -> List[str]: """ :type n: int :rtype: List[str] """ ans = [] self.dfs(ans, '', 0, 0, n) return ans def dfs(self, ans, S, left, right, n): if len(S) == 2 * n: ans.
Given a 2D board and a list of words from the dictionary, find all words in the board. Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word. Example: Input: board = [ ['o','a','a','n'], ['e','t','a','e'], ['i','h','k','r'], ['i','f','l','v'] ] words = ["oath","pea","eat","rain"] Output: ["eat","oath"] Note All inputs are consist of lowercase letters a-z.
You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin. Example 1 Input: amount = 5, coins = [1, 2, 5] Output: 4 Explanation: there are four ways to make up the amount: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 Example 2 Input: amount = 3, coins = [2] Output: 0 Explanation: the amount of 3 cannot be made up just with coins of 2.