Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists: A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b1 → b2 → b3 begin to intersect at node c1. Note If the two linked lists have no intersection at all, return null. The linked lists must retain their original structure after the function returns.
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. push(x) – Push element x onto stack. pop() – Removes the element on top of the stack. top() – Get the top element. getMin() – Retrieve the minimum element in the stack. Example MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> Returns -3. minStack.pop(); minStack.top(); --> Returns 0. minStack.getMin(); --> Returns -2.
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. Note The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words. Example 1 Input: s = "leetcode", wordDict = ["leet", "code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code".
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. Example 1 Input: 11110 11010 11000 00000 Output: 1 Example 2 Input: 11000 11000 00100 00011 Output: 3 DFS Solution (DFS in Java) DFS
Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root. Example 1 Input: [1,2,3] 1 / \ 2 3 Output: 6 Example 2 Input: [-10,9,20,null,null,15,7] -10 / \ 9 20 / \ 15 7 Output: 42 Solution Python
Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set). Note The solution set must not contain duplicate subsets. Example: Input: [1,2,2] Output: [ [2], [1], [1,2,2], [2,2], [1,2], [] ] Solution Time: O(n * 2^n) Space: O(n * 2^n) keep all the subsets of length N, since each of N elements could be present or absent. class Solution: def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: results = [] subset = [] # Edge case 1 if nums == None: return results # Edge case 2 if len(nums) == 0: results.
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Note The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. Example Input: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 Output: `[1,2,2,3,5,6]` Solution # Time: o(m+n) # Space: o(1) class Solution: def merge(self, nums1, m, nums2, n): """ :type nums1: List[int] :type m: int :type nums2: List[int] :type n: int :rtype: void Do not return anything, modify nums1 in-place instead.
A message containing letters from A-Z is being encoded to numbers using the following mapping: ‘A’ -> 1 ‘B’ -> 2 … ‘Z’ -> 26 Given a non-empty string containing only digits, determine the total number of ways to decode it. Example 1 Input: "12" Output: 2 Explanation: It could be decoded as "AB" (1 2) or "L" (12). Example 2 Input: "226" Output: 3 Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Given a string containing only digits, restore it by returning all possible valid IP address combinations. Example Input: "25525511135" Output: ["255.255.11.135", "255.255.111.35"] Solution class Solution: def restoreIpAddresses(self, s: str) -> List[str]: results = [] self.backtrack(results, s, 0, "", 0) return results def backtrack(self, results, s, start, partial, segment_count): # pruning for performance improvement if (4 - segment_count) * 3 < len(s) - start or (4 - segment_count) > len(s) - start: return # base case goal if start == len(s) and segment_count == 4: results.
Reverse a linked list from position m to n. Do it in one-pass. Note: 1 ≤ m ≤ n ≤ length of list. Example: Input: 1->2->3->4->5->NULL, m = 2, n = 4 Output: 1->4->3->2->5->NULL Solution: /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { ListNode dummy = new ListNode(0); dummy.