Leetcode-cn.com 2021-09-12
🟡 678.valid-parenthesis-string

🏷️ Tags
#stack #greedy #string #dynamic_programming

Description
给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：


任何左括号 ( 必须有相应的右括号 )。
任何右括号 ) 必须有相应的左括号 ( 。
左括号 ( 必须在对应的右括号之前 )。
* 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
一个空字符串也被视为有效字符串。


Example

输入: "()"
输出: True

Leetcode.com 2021-09-11
🔴 224.basic-calculator

🏷️ Tags
#stack #recursion #math #string

Description
Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example

Input: s = "1 + 1"
Output: 2

Leetcode-cn.com 2021-09-13
🟡 447.number-of-boomerangs

🏷️ Tags
#array #hash_table #math

Description
给定平面上 n 对 互不相同 的点 points ，其中 points[i] = [xi, yi] 。回旋镖 是由点 (i, j, k) 表示的元组 ，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）。

返回平面上所有回旋镖的数量。
 

Example

输入：points = [[0,0],[1,0],[2,0]]
输出：2
解释：两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

Leetcode.com 2021-09-12
🔴 882.reachable-nodes-in-subdivided-graph

🏷️ Tags
#graph #shortest_path #heap_priority_queue

Description
You are given an undirected graph (the "original graph") with n nodes labeled from 0 to n - 1. You decide to subdivide each edge in the graph into a chain of nodes, with the number of new nodes varying between each edge.

The graph is given as a 2D array of edges where edges[i] = [ui, vi, cnti] indicates that there is an edge between nodes ui and vi in the original graph, and cnti is the total number of new nodes that you will subdivide the edge into. Note that cnti == 0 means you will not subdivide the edge.

To subdivide the edge [ui, vi], replace it with (cnti + 1) new edges and cnti new nodes. The new nodes are x1, x2, ..., xcnti, and the new edges are [ui, x1], [x1, x2], [x2, x3], ..., [xcnti+1, xcnti], [xcnti, vi].

In this new graph, you want to know how many nodes are reachable from the node 0, where a node is reachable if the distance is maxMoves or less.

Given the original graph and maxMoves, return the number of nodes that are reachable from node 0 in the new graph.

Example

Input: edges = [[0,1,10],[0,2,1],[1,2,2]], maxMoves = 6, n = 3
Output: 13
Explanation: The edge subdivisions are shown in the image above.
The nodes that are reachable are highlighted in yellow.

Leetcode-cn.com 2021-09-14
🟡 524.longest-word-in-dictionary-through-deleting

🏷️ Tags
#array #two_pointers #string #sorting

Description
给你一个字符串 s 和一个字符串数组 dictionary 作为字典，找出并返回字典中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。

如果答案不止一个，返回长度最长且字典序最小的字符串。如果答案不存在，则返回空字符串。

 

Example

输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
输出："apple"

Leetcode.com 2021-09-13
🟢 1189.maximum-number-of-balloons

🏷️ Tags
#hash_table #string #counting

Description
Given a string text, you want to use the characters of text to form as many instances of the word "balloon" as possible.

You can use each character in text at most once. Return the maximum number of instances that can be formed.

Example

Input: text = "nlaebolko"
Output: 1

Leetcode-cn.com 2021-09-15
🟡 162.find-peak-element

🏷️ Tags
#array #binary_search

Description
峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

Example

输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。

Leetcode.com 2021-09-14
🟢 917.reverse-only-letters

🏷️ Tags
#two_pointers #string

Description
Given a string s, reverse the string according to the following rules:


All the characters that are not English letters remain in the same position.
All the English letters (lowercase or uppercase) should be reversed.


Return s after reversing it.

Example

Input: s = "ab-cd"
Output: "dc-ba"

Leetcode-cn.com 2021-09-16
🔴 212.word-search-ii

🏷️ Tags
#trie #array #string #backtracking #matrix

Description
给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，找出所有同时在二维网格和字典中出现的单词。

单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

 

Example

输入：board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
输出：["eat","oath"]

Leetcode.com 2021-09-15
🟡 978.longest-turbulent-subarray

🏷️ Tags
#array #dynamic_programming #sliding_window

Description
Given an integer array arr, return the length of a maximum size turbulent subarray of arr.

A subarray is turbulent if the comparison sign flips between each adjacent pair of elements in the subarray.

More formally, a subarray [arr[i], arr[i + 1], ..., arr[j]] of arr is said to be turbulent if and only if:


For i <= k < j:


arr[k] > arr[k + 1] when k is odd, and
arr[k] < arr[k + 1] when k is even.


Or, for i <= k < j:

arr[k] > arr[k + 1] when k is even, and
arr[k] < arr[k + 1] when k is odd.




Example

Input: arr = [9,4,2,10,7,8,8,1,9]
Output: 5
Explanation: arr[1] > arr[2] < arr[3] > arr[4] < arr[5]

Leetcode-cn.com 2021-09-17
🟡 36.valid-sudoku

🏷️ Tags
#array #hash_table #matrix

Description
请你判断一个 9x9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。


数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考Example

输入：board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：true

Leetcode.com 2021-09-16
🟡 54.spiral-matrix

🏷️ Tags
#array #matrix #simulation

Description
Given an m x n matrix, return all elements of the matrix in spiral order.

Example

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

Leetcode-cn.com 2021-09-18
🟢 292.nim-game

🏷️ Tags
#brainteaser #math #game_theory

Description
你和你的朋友，两个人一起玩 Nim 游戏：


桌子上有一堆石头。
你们轮流进行自己的回合，你作为先手。
每一回合，轮到的人拿掉 1 - 3 块石头。
拿掉最后一块石头的人就是获胜者。


假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。

 

Example

输入：n = 4
输出：false 
解释：如果堆中有 4 块石头，那么你永远不会赢得比赛；
     因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。

Leetcode.com 2021-09-17
🟢 350.intersection-of-two-arrays-ii

🏷️ Tags
#array #hash_table #two_pointers #binary_search #sorting

Description
Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

Example

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Leetcode-cn.com 2021-09-19
🟡 650.2-keys-keyboard

🏷️ Tags
#math #dynamic_programming

Description
最初记事本上只有一个字符 'A' 。你每次可以对这个记事本进行两种操作：


Copy All（复制全部）：复制这个记事本中的所有字符（不允许仅复制部分字符）。
Paste（粘贴）：粘贴 上一次 复制的字符。


给你一个数字 n ，你需要使用最少的操作次数，在记事本上输出 恰好 n 个 'A' 。返回能够打印出 n 个 'A' 的最少操作次数。

Example

输入：3
输出：3
解释：
最初, 只有一个字符 'A'。
第 1 步, 使用 Copy All 操作。
第 2 步, 使用 Paste 操作来获得 'AA'。
第 3 步, 使用 Paste 操作来获得 'AAA'。

Leetcode.com 2021-09-18
🔴 282.expression-add-operators

🏷️ Tags
#math #string #backtracking

Description
Given a string num that contains only digits and an integer target, return all possibilities to add the binary operators '+', '-', or '*' between the digits of num so that the resultant expression evaluates to the target value.

Example

Input: num = "123", target = 6
Output: ["1*2*3","1+2+3"]

Leetcode-cn.com 2021-09-20
🟡 673.number-of-longest-increasing-subsequence

🏷️ Tags
#binary_indexed_tree #segment_tree #array #dynamic_programming

Description
给定一个未排序的整数数组，找到最长递增子序列的个数。

Example

输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

Leetcode.com 2021-09-19
🔴 115.distinct-subsequences

🏷️ Tags
#string #dynamic_programming

Description
Given two strings s and t, return the number of distinct subsequences of s which equals t.

A string's subsequence is a new string formed from the original string by deleting some (can be none) of the characters without disturbing the remaining characters' relative positions. (i.e., "ACE" is a subsequence of "ABCDE" while "AEC" is not).

It is guaranteed the answer fits on a 32-bit signed integer.

Example

Input: s = "rabbbit", t = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from S.
rabbbit
rabbbit
rabbbit

Leetcode-cn.com 2021-09-21
🟢 58.length-of-last-word

🏷️ Tags
#string

Description
给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中最后一个单词的长度。

单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

Example

输入：s = "Hello World"
输出：5

Leetcode.com 2021-09-20
🟢 1275.find-winner-on-a-tic-tac-toe-game

🏷️ Tags
#array #hash_table #matrix #simulation

Description
Tic-tac-toe is played by two players A and B on a 3 x 3 grid.

Here are the rules of Tic-Tac-Toe:


Players take turns placing characters into empty squares (" ").
The first player A always places "X" characters, while the second player B always places "O" characters.
"X" and "O" characters are always placed into empty squares, never on filled ones.
The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal.
The game also ends if all squares are non-empty.
No more moves can be played if the game is over.


Given an array moves where each element is another array of size 2 corresponding to the row and column of the grid where they mark their respective character in the order in which A and B play.

Return the winner of the game if it exists (A or B), in case the game ends in a draw return "Draw", if there are still movements to play return "Pending".

You can assume that moves is valid (It follows the rules of Tic-Tac-Toe), the grid is initially empty and A will play first.

Example

Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: "A"
Explanation: "A" wins, he always plays first.
"X  "    "X  "    "X  "    "X  "    "X  "
"   " -> "   " -> " X " -> " X " -> " X "
"   "    "O  "    "O  "    "OO "    "OOX"