著书三年倦写字，如今翻书不识志，若知倦书悔前程 ，无如渔樵未识时
给你一个整数数组 nums 。
如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。
返回好数对的数目。
示例 1：
输入：nums = [1,2,3,1,1,3] 输出：4 解释：有 4 组好数对，分别是 (0,3), (0,4), (3,4), (2,5) ，下标从 0 开始
示例 2：
输入：nums = [1,1,1,1] 输出：6 解释：数组中的每组数字都是好数对
示例 3：
输入：nums = [1,2,3] 输出：0
提示：
1 <= nums.length <= 1001 <= nums[i] <= 100哈希表边统计数字次数边更新结果，一次遍历
int[] arr = new int[101]统计每个数字出现的次数，题目中已知1 <= nums[i] <= 100int[] nums，统计同一个数字出现的次数，每统计一个数字num，这个数字可以和之前的统计到的所有数字num分别组成好数对，即新增了arr[num]-1对好数对class Solution {
public int numIdenticalPairs(int[] nums) {
int[] arr = new int[101];
int ans = 0;
for (int num : nums) {
arr[num]++;
ans += arr[num]-1;
}
return ans;
}
}给你一个字符串 licensePlate 和一个字符串数组 words ，请你找出 words 中的 最短补全词 。
补全词 是一个包含 licensePlate 中所有字母的单词。忽略 licensePlate 中的 数字和空格 。不区分大小写。如果某个字母在 licensePlate 中出现不止一次，那么该字母在补全词中的出现次数应当一致或者更多。
例如：licensePlate = "aBc 12c"，那么它的补全词应当包含字母 'a'、'b' （忽略大写）和两个 'c' 。可能的 补全词 有 "abccdef"、"caaacab" 以及 "cbca" 。
请返回 words 中的 最短补全词 。题目数据保证一定存在一个最短补全词。当有多个单词都符合最短补全词的匹配条件时取 words 中 第一个 出现的那个。
示例 1：
输入：licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"] 输出："steps" 解释：最短补全词应该包括 "s"、"p"、"s"（忽略大小写） 以及 "t"。 "step" 包含 "t"、"p"，但只包含一个 "s"，所以它不符合条件。 "steps" 包含 "t"、"p" 和两个 "s"。 "stripe" 缺一个 "s"。 "stepple" 缺一个 "s"。 因此，"steps" 是唯一一个包含所有字母的单词，也是本例的答案。
示例 2：
输入：licensePlate = "1s3 456", words = ["looks", "pest", "stew", "show"] 输出："pest" 解释：licensePlate 只包含字母 "s" 。所有的单词都包含字母 "s" ，其中 "pest"、"stew"、和 "show" 三者最短。答案是 "pest" ，因为它是三个单词中在 words 里最靠前的那个。
提示：
1 <= licensePlate.length <= 7licensePlate 由数字、大小写字母或空格 ' ' 组成1 <= words.length <= 10001 <= words[i].length <= 15words[i] 由小写英文字母组成哈希表，字符统计，简单，特纯粹的哈希表统计
licensePlate中字符出现次数words[] 分别统计每个word的字符出现次数licensePlate中出现的字符，在word中出现的次数要大于等于在licensePlate中出现的次数ans 和当前word的长度，取较小的一个，相等的情况不变，即长度相等取现出现的就…纯粹的哈希表统计
class Solution {
public String shortestCompletingWord(String licensePlate, String[] words) {
int[] arr = charCnt(licensePlate);
String ans = null;
for (String word : words) {
int[] wArr = charCnt(word);
boolean flag = true;
for (int i = 0; flag && i < arr.length; i++) {
if (arr[i]>0 && wArr[i] <arr[i]){
flag = false;
}
}
ans = flag && ( ans == null || word.length() < ans.length()) ? word : ans;
}
return ans;
}
private int[] charCnt(String str){
int[] arr = new int[26];
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (c >= 'a' && c <= 'z'){
arr[str.charAt(i)-'a']++;
}
if (c >= 'A' && c <= 'Z'){
arr[str.charAt(i)-'A']++;
}
}
return arr;
}
}我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
1 是丑数。n 不超过1690。注意：本题与主站 264 题相同：https://leetcode-cn.com/problems/ugly-number-ii/
dp,算是dp吧
此处撰写解题思路
class Solution {
public int nthUglyNumber(int n) {
int[] dp = new int[n];
dp[0] = 1;
int[] numArr = new int[]{2,3,5};
int[] pArr = new int[3];
for (int i = 1; i < n; i++) {
dp[i] = Math.min(Math.min(dp[pArr[0]]*numArr[0],dp[pArr[1]]*numArr[1]),dp[pArr[2]]*numArr[2]);
for (int p = 0; p < pArr.length; p++) {
if (dp[i] == dp[pArr[p]]*numArr[p]){
pArr[p]++;
}
}
}
return dp[n-1];
}
}输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
示例 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7]
示例 2:
Input: preorder = [-1], inorder = [-1] Output: [-1]
限制：
0 <= 节点个数 <= 5000
注意：本题与主站 105 题重复：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/ Related Topics
👍 830👎 0
学二叉树入门必做题
关键信息
前中后序遍历
左右两个子节点的顺序不变都是先左子节点，后右子节点，区别就在于根节点是先遍历，还是中间，还是最后
这分别就是前中后序遍历
相关特性
现有如图这个一对前序遍历和中序遍历结果
根据相关特效，前序遍历的第一个就是根节点，所以我们知道了，根节点为3
又中序遍历中左侧只有一个，所以左子树只有一个节点9，右子树部分暂时不知道只知道剩下部分为右侧的前序和中序遍历结果，二叉树如下
再接下来，我们把右子树部分的按照同样的逻辑处理
我们知道了右子树的根节点为20，20的左子树只有一个节点15，右子树只有一个节点7
这样我们就重新构建完成了整棵二叉树
class Solution {
int[] preorder;
int[] inorder;
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
this.inorder = inorder;
int len = preorder.length-1;
return buildTree(0,len,0,len);
}
public TreeNode buildTree( int preL, int preR, int inL, int inR){
if (preL > preR){
return null;
}
TreeNode node = new TreeNode(preorder[preL]);
int len = 0;
for (int i = inL; i <= inR; i++) {
if (inorder[i] == preorder[preL]){
len = i - inL;
}
}
node.left = buildTree(preL+1,preL+len,inL,inL+len-1);
node.right = buildTree(preL+len+1,preR,inL+len+1,inR);
return node;
}
}给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
示例 1：
输入：ransomNote = "a", magazine = "b" 输出：false
示例 2：
输入：ransomNote = "aa", magazine = "ab" 输出：false
示例 3：
输入：ransomNote = "aa", magazine = "aab" 输出：true
提示：
1 <= ransomNote.length, magazine.length <= 105ransomNote 和 magazine 由小写英文字母组成哈希统计
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] arr = new int[26];
for (int i = 0; i < magazine.length(); i++) {
arr[magazine.charAt(i)-'a']++;
}
for (int i = 0; i < ransomNote.length(); i++) {
arr[ransomNote.charAt(i)-'a']--;
if (arr[ransomNote.charAt(i)-'a'] < 0 ){
return false;
}
}
return true;
}
}给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1:
输入: s = "cbaebabacd", p = "abc" 输出: [0,6] 解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
示例 2:
输入: s = "abab", p = "ab" 输出: [0,1,2] 解释: 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
提示:
1 <= s.length, p.length <= 3 * 104s 和 p 仅包含小写字母滑动窗口+哈希表统计，联动可以参考下76题最小覆盖子串
类似的可以看下76题，非常相似
滑动窗口，带注释
区别就是76题是非固定长度窗口，本题中窗口长度固定
class Solution {
public List<Integer> findAnagrams(String s, String p) {
if (s.length()<p.length()){
return new ArrayList<>();
}
int[] arr = new int[26];
int count = 0;
for (int i = 0; i < p.length(); i++) {
arr[p.charAt(i)-'a']++;
if (arr[p.charAt(i)-'a'] == 1){
count++;
}
arr[s.charAt(i)-'a']--;
if (arr[s.charAt(i)-'a'] == 0){
count--;
}
}
List<Integer> res = new ArrayList<>();
if (count == 0){
res.add(0);
}
int idx = p.length()-1;
while (++idx < s.length()){
arr[s.charAt(idx-p.length())-'a']++;
if (arr[s.charAt(idx-p.length())-'a'] == 1){
count++;
}
arr[s.charAt(idx)-'a']--;
if (arr[s.charAt(idx)-'a'] == 0){
count--;
}
if (count == 0){
res.add(idx-p.length()+1);
}
}
return res;
}
}给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
示例 1：
输入：nums = [1,1,1], k = 2 输出：2
示例 2：
输入：nums = [1,2,3], k = 3 输出：2
提示：
1 <= nums.length <= 2 * 104-1000 <= nums[i] <= 1000-107 <= k <= 107连续区间和，必然会想到的内容前缀和数组
所以在这题目中，我们的思路是这样的
K的子数组的话，那么就需要判断 在当前位置前面，是否存在前缀和为当前区间和减去K的情况存在K的区间就可以等价🐟， 当前位置之前有多少个 当前位置区间和 减去 K的值的区间和的数量class Solution {
public int subarraySum(int[] nums, int k) {
int[] preSum = new int[nums.length];
HashMap<Integer,Integer> hashMap = new HashMap<>();
hashMap.put(0,1);
int idx = -1;
int count = 0;
while (++idx < nums.length){
preSum[idx] = nums[idx] + (idx>0?preSum[idx-1]:0);
count += hashMap.getOrDefault(preSum[idx] - k,0);
hashMap.put(preSum[idx], hashMap.getOrDefault(preSum[idx],0)+1);
}
return count;
}
}