Jackson.tmm

LeetCode 1679 - Max Number of K-Sum Pairs

You are given an integer array nums and an integer k.

In one operation, you can pick two numbers from the array whose sum equals k and remove them from the array.

Return the maximum number of operations you can perform on the array.

example

1
2
3
4
5
6

Input: nums = [1,2,3,4], k = 5
Output: 2
Explanation: Starting with nums = [1,2,3,4]:
- Remove numbers 1 and 4, then nums = [2,3]
- Remove numbers 2 and 3, then nums = []
There are no more pairs that sum up to 5, hence a total of 2 operations.

1
2
3
4
5

Input: nums = [3,1,3,4,3], k = 6
Output: 1
Explanation: Starting with nums = [3,1,3,4,3]:
- Remove the first two 3's, then nums = [1,4,3]
There are no more pairs that sum up to 6, hence a total of 1 operation.

How can we solve this problem?

這題就是要移除Array中2個elements加起來等於k的操作有幾次。
第一個解法，我們可以使用sorting以及two-pointer approach來解決。先將array排序，然後設置i為0,j為n-1,直接使用iteration找出nums[i]+nums[j] = k的數，然後answer+1即可。

LeetCode 581 - Shortest Unsorted Continuous Subarray

Given an integer array nums, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order.

Return the shortest such subarray and output its length.

example:

1
2
3

Input: nums = [2,6,4,8,10,9,15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

1
2

Input: nums = [1,2,3,4]
Output: 0

1
2

Input: nums = [1]
Output: 0

How can we solve this problem?

這題比較難懂一點點，這裡先做一下題目的解釋。這題主要先問的是在輸入的Array裡面找到一個最小需要排序的Sub-array。
從例子[2,6,4,8,10,9,15]中，我們可以很明顯的看到[6,4,8,10,9]並不是ascending order(順序),而這個sub-array要進行排序的話，所有elements都需要進行排序，所以，他的length是5。
再舉另外一個例子[1,3,2,3,3]，這個Array我們可以看到[3,2,3,3]並不是順序的，但是在這個sub-array裡面,只有[3,2]需要排序,所以，他的結果會是2。

LeetCode 905 - Sort Array By Parity

Given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers.

Return any array that satisfies this condition.

example:

1
2
3

Input: nums = [3,1,2,4]
Output: [2,4,3,1]
Explanation: The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

1
2

Input: nums = [0]
Output: [0]

How can we solve this problem?

這個問題很簡單，就是把偶數移動到Array的前面，基數移動到後面。我們這裡可以使用Two-pointer approach, i為尋找前面的基數，而j 為尋找後面的偶數，只要nums[i]為基數,nums[j]為偶數就進行交換。

LeetCode 844 - Backspace String Compare

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

example:

1
2
3

Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".

1
2
3

Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Both s and t become "".

1
2
3

Input: s = "a#c", t = "b"
Output: false
Explanation: s becomes "c" while t becomes "b".

How can we solve this problem?

這題主要要什麼比較2個String移除於#前的字符後是否為相同的String，就相當於Backspace(#) 字符。 這題有2種解法:

LeetCode 669 - Trim a Binary Search Tree

Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node’s descendant should remain a descendant). It can be proven that there is a unique answer.

LeetCode 700 - Search in a Binary Search Tree

You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node’s value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

example

1
2

Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]

1
2

Input: root = [4,2,7,1,3], val = 5
Output: []

How can we solve this problem?

在解決問題之前，我們需要知道什麼是Binary Search Tree。根據BST的定義:

LeetCode 1260 - Shift 2D Grid

Given a 2D grid of size m x n and an integer k. You need to shift the grid k times.

In one shift operation:

• Element at grid[i][j] moves to grid[i][j + 1].
• Element at grid[i][n - 1] moves to grid[i + 1][0].
• Element at grid[m - 1][n - 1] moves to grid[0][0].

Return the 2D grid after applying shift operation k times.

example

LeetCode 59 - Spiral Matrix II

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n² in spiral order.

example

1
2

Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]

1
2

Input: n = 1
Output: [[1]]

How can we solve this problem?

這題跟Spiral Matrix做法差不多，我們不難發現他的移動模式就是(右→下↓左←上)，我們只需要通過幾個變數來限制移動的步數。另外，這題需要我們返回一個n²的array，所以，需要額外定義一個counter來記錄每次插入的數值為多少，因此，只要counter 到達n²的大小就知道是否完成插入所需的值。

LeetCode 289 - Game of Life

According to Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”

The board is made up of an m x n grid of cells, where each cell has an initial state: live (represented by a 1) or dead (represented by a 0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

LeetCode 682 - Baseball Game

You are keeping score for a baseball game with strange rules. The game consists of several rounds, where the scores of past rounds may affect future rounds’ scores.

At the beginning of the game, you start with an empty record. You are given a list of strings ops, where ops[i] is the ith operation you must apply to the record and is one of the following: