Leetcode-cn.com 2021-09-10
🟡 1894.find-the-student-that-will-replace-the-chalk

🏷️ Tags
#array #binary_search #prefix_sum #simulation

Description
一个班级里有 n 个学生，编号为 0 到 n - 1 。每个学生会依次回答问题，编号为 0 的学生先回答，然后是编号为 1 的学生，以此类推，直到编号为 n - 1 的学生，然后老师会重复这个过程，重新从编号为 0 的学生开始回答问题。

给你一个长度为 n 且下标从 0 开始的整数数组 chalk 和一个整数 k 。一开始粉笔盒里总共有 k 支粉笔。当编号为 i 的学生回答问题时，他会消耗 chalk[i] 支粉笔。如果剩余粉笔数量 严格小于 chalk[i] ，那么学生 i 需要 补充 粉笔。

请你返回需要 补充 粉笔的学生 编号 。

 

Example

输入：chalk = [5,1,5], k = 22
输出：0
解释：学生消耗粉笔情况如下：
- 编号为 0 的学生使用 5 支粉笔，然后 k = 17 。
- 编号为 1 的学生使用 1 支粉笔，然后 k = 16 。
- 编号为 2 的学生使用 5 支粉笔，然后 k = 11 。
- 编号为 0 的学生使用 5 支粉笔，然后 k = 6 。
- 编号为 1 的学生使用 1 支粉笔，然后 k = 5 。
- 编号为 2 的学生使用 5 支粉笔，然后 k = 0 。
编号为 0 的学生没有足够的粉笔，所以他需要补充粉笔。

Leetcode.com 2021-09-09
🟡 764.largest-plus-sign

🏷️ Tags
#array #dynamic_programming

Description
You are given an integer n. You have an n x n binary grid grid with all values initially 1's except for some indices given in the array mines. The ith element of the array mines is defined as mines[i] = [xi, yi] where grid[xi][yi] == 0.

Return the order of the largest axis-aligned plus sign of 1's contained in grid. If there is none, return 0.

An axis-aligned plus sign of 1's of order k has some center grid[r][c] == 1 along with four arms of length k - 1 going up, down, left, and right, and made of 1's. Note that there could be 0's or 1's beyond the arms of the plus sign, only the relevant area of the plus sign is checked for 1's.

Example

Input: n = 5, mines = [[4,2]]
Output: 2
Explanation: In the above grid, the largest plus sign can only be of order 2. One of them is shown.

Leetcode-cn.com 2021-09-11
🔴 600.non-negative-integers-without-consecutive-ones

🏷️ Tags
#dynamic_programming

Description
给定一个正整数 n，找出小于或等于 n 的非负整数中，其二进制表示不包含 连续的1 的个数。

Example

输入: 5
输出: 5
解释: 
下面是带有相应二进制表示的非负整数<= 5：
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中，只有整数3违反规则（有两个连续的1），其他5个满足规则。

Leetcode.com 2021-09-10
🔴 446.arithmetic-slices-ii-subsequence

🏷️ Tags
#array #dynamic_programming

Description
Given an integer array nums, return the number of all the arithmetic subsequences of nums.

A sequence of numbers is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.


For example, [1, 3, 5, 7, 9], [7, 7, 7, 7], and [3, -1, -5, -9] are arithmetic sequences.
For example, [1, 1, 2, 5, 7] is not an arithmetic sequence.


A subsequence of an array is a sequence that can be formed by removing some elements (possibly none) of the array.


For example, [2,5,10] is a subsequence of [1,2,1,2,4,1,5,10].


The test cases are generated so that the answer fits in 32-bit integer.

Example

Input: nums = [2,4,6,8,10]
Output: 7
Explanation: All arithmetic subsequence slices are:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

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"]