# 2022-05-30 ## [82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/) ### Description Given the `head` of a sorted linked list, *delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list*. Return *the linked list **sorted** as well*. **Example 1:** ![](https://img.content.cc/a/2022/05/30/09-39-04-987-660f952a3b16aa11de97081f306cf666-c03202.jpeg) ``` Input: head = [1,2,3,3,4,4,5] Output: [1,2,5] ``` **Example 2:** ![](https://img.content.cc/a/2022/05/30/09-39-20-908-e5ea2dae9e9a33fea2ef4d8acf2289a0-c8e5e7.jpeg) ``` Input: head = [1,1,1,2,3] Output: [2,3] ``` **Constraints:** * The number of nodes in the list is in the range `[0, 300]`. * `-100 <= Node.val <= 100` * The list is guaranteed to be **sorted** in ascending order. ### Solution #### Approach #0 ```go /** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func deleteDuplicates(head *ListNode) *ListNode { return dfs(head, -101) } func dfs(cur *ListNode, val int) *ListNode { if cur == nil { return nil } if cur.Val == val || (cur.Next != nil && cur.Next.Val == cur.Val) { return dfs(cur.Next, cur.Val) } cur.Next = dfs(cur.Next, cur.Val) return cur } ``` #### Approach #1 ```go /** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func deleteDuplicates(head *ListNode) *ListNode { if head == nil { return nil } newHead := &ListNode{Next: head} cur := newHead for cur.Next != nil && cur.Next.Next != nil { if cur.Next.Val == cur.Next.Next.Val { v := cur.Next.Val for cur.Next != nil && cur.Next.Val == v { cur.Next = cur.Next.Next } } else { cur = cur.Next } } return newHead.Next } ``` ## [15. 3Sum](https://leetcode.com/problems/3sum/) ### Description 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: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] ``` **Example 2:** ``` Input: nums = [] Output: [] ``` **Example 3:** ``` Input: nums = [0] Output: [] ``` **Constraints:** * `0 <= nums.length <= 3000` * `-10^5 <= nums[i] <= 10^5` ### Solution #### Approach #0 ```go func threeSum(nums []int) [][]int { sort.Ints(nums) n := len(nums) var res [][]int for i := 0; i < n; i++ { if i > 0 && nums[i] == nums[i-1] { continue } k := n - 1 for j := i + 1; j < n; j++ { if j > i+1 && nums[j] == nums[j-1] { continue } for j < k && nums[i]+nums[j]+nums[k] > 0 { k-- } if j == k { break } if nums[i]+nums[j]+nums[k] == 0 { res = append(res, []int{nums[i], nums[j], nums[k]}) } } } return res } ``` ## [1022. Sum of Root To Leaf Binary Numbers](https://leetcode.com/problems/sum-of-root-to-leaf-binary-numbers/) ### Description You are given the `root` of a binary tree where each node has a value `0` or `1`. Each root-to-leaf path represents a binary number starting with the most significant bit. * For example, if the path is `0 -> 1 -> 1 -> 0 -> 1`, then this could represent `01101` in binary, which is `13`. For all leaves in the tree, consider the numbers represented by the path from the root to that leaf. Return *the sum of these numbers*. The test cases are generated so that the answer fits in a **32-bits** integer. **Example 1:** ![](https://img.content.cc/a/2022/05/30/14-30-21-934-36029c6aea051f3a535267cd23ce9342-6f931c.png) ``` Input: root = [1,0,1,0,1,0,1] Output: 22 Explanation: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22 ``` **Example 2:** ``` Input: root = [0] Output: 0 ``` **Constraints:** * The number of nodes in the tree is in the range `[1, 1000]`. * `Node.val` is `0` or `1`. ### Solution #### Approach #0 ```go /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func sumRootToLeaf(root *TreeNode) int { return sum(root, 0) } func sum(node *TreeNode, num int) int { if node.Left != nil && node.Right != nil { return sum(node.Left, num<<1+node.Val) + sum(node.Right, num<<1+node.Val) } if node.Left != nil { return sum(node.Left, num<<1+node.Val) } if node.Right != nil { return sum(node.Right, num<<1+node.Val) } return num<<1 + node.Val } ``` #### Approach #1 ```go /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func sumRootToLeaf(root *TreeNode) int { var val, res int var stack []*TreeNode var pre *TreeNode for root != nil || len(stack) > 0 { for root != nil { val = val<<1 | root.Val stack = append(stack, root) root = root.Left } root = stack[len(stack)-1] if root.Right == nil || root.Right == pre { if root.Left == nil && root.Right == nil { res = res + val } val = val >> 1 stack = stack[:len(stack)-1] pre = root root = nil } else { root = root.Right } } return res } ``` --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://a.b.cr/dictionary/algorithm/diary/2022/05/2022-05-30.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.