著书三年倦写字，如今翻书不识志，若知倦书悔前程 ，无如渔樵未识时
给你一个整数数组 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;
}
}给你两个字符串：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;
}
}如果两个字符串 word1 和 word2 中从 'a' 到 'z' 每一个字母出现频率之差都 不超过 3 ，那么我们称这两个字符串 word1 和 word2 几乎相等 。
给你两个长度都为 n 的字符串 word1 和 word2 ，如果 word1 和 word2 几乎相等 ，请你返回 true ，否则返回 false 。
一个字母 x 的出现 频率 指的是它在字符串中出现的次数。
示例 1：
输入：word1 = "aaaa", word2 = "bccb" 输出：false 解释：字符串 "aaaa" 中有 4 个 'a' ，但是 "bccb" 中有 0 个 'a' 。 两者之差为 4 ，大于上限 3 。
示例 2：
输入：word1 = "abcdeef", word2 = "abaaacc" 输出：true 解释：word1 和 word2 中每个字母出现频率之差至多为 3 ： - 'a' 在 word1 中出现了 1 次，在 word2 中出现了 4 次，差为 3 。 - 'b' 在 word1 中出现了 1 次，在 word2 中出现了 1 次，差为 0 。 - 'c' 在 word1 中出现了 1 次，在 word2 中出现了 2 次，差为 1 。 - 'd' 在 word1 中出现了 1 次，在 word2 中出现了 0 次，差为 1 。 - 'e' 在 word1 中出现了 2 次，在 word2 中出现了 0 次，差为 2 。 - 'f' 在 word1 中出现了 1 次，在 word2 中出现了 0 次，差为 1 。
示例 3：
输入：word1 = "cccddabba", word2 = "babababab" 输出：true 解释：word1 和 word2 中每个字母出现频率之差至多为 3 ： - 'a' 在 word1 中出现了 2 次，在 word2 中出现了 4 次，差为 2 。 - 'b' 在 word1 中出现了 2 次，在 word2 中出现了 5 次，差为 3 。 - 'c' 在 word1 中出现了 3 次，在 word2 中出现了 0 次，差为 3 。 - 'd' 在 word1 中出现了 2 次，在 word2 中出现了 0 次，差为 2 。
提示：
n == word1.length == word2.length1 <= n <= 100word1 和 word2 都只包含小写英文字母。哈希、统计
class Solution {
public boolean checkAlmostEquivalent(String word1, String word2) {
int n = word1.length();
int[] count = new int[26];
while (--n >=0){
count[word1.charAt(n)-'a']++;
count[word2.charAt(n)-'a']--;
}
for (int i : count) {
if (i>3 || i<-3){
return false;
}
}
return true;
}
}你在和朋友一起玩 猜数字（Bulls and Cows）游戏，该游戏规则如下：
写出一个秘密数字，并请朋友猜这个数字是多少。朋友每猜测一次，你就会给他一个包含下述信息的提示：
给你一个秘密数字 secret 和朋友猜测的数字 guess ，请你返回对朋友这次猜测的提示。
提示的格式为 "xAyB" ，x 是公牛个数， y 是奶牛个数，A 表示公牛，B 表示奶牛。
请注意秘密数字和朋友猜测的数字都可能含有重复数字。
示例 1：
输入：secret = "1807", guess = "7810" 输出："1A3B" 解释：数字和位置都对（公牛）用 '|' 连接，数字猜对位置不对（奶牛）的采用斜体加粗标识。 "1807" | "7810"
示例 2：
输入：secret = "1123", guess = "0111" 输出："1A1B" 解释：数字和位置都对（公牛）用 '|' 连接，数字猜对位置不对（奶牛）的采用斜体加粗标识。 "1123" "1123" | or | "0111" "0111" 注意，两个不匹配的 1 中，只有一个会算作奶牛（数字猜对位置不对）。通过重新排列非公牛数字，其中仅有一个 1 可以成为公牛数字。
提示：
1 <= secret.length, guess.length <= 1000secret.length == guess.lengthsecret 和 guess 仅由数字组成题目有点绕，看的有点懵。还是简单点处理
secret和guess中有位置对应的，则减去一个，表示待匹配数量减少一个，同时countA++map中留下的是待匹配的数字未被匹配中的数量guess中这个位置的字符有待匹配的数量，则countB++，表示有一个匹配位置错了map[guess.charAt(idx)-'0']--表示处理过了一个未被匹配中的情况最终输出结果
class Solution {
public String getHint(String secret, String guess) {
int countA = 0;
int countB = 0;
int[] map = new int[10];
int idx = -1;
while (++idx < secret.length()){
map[secret.charAt(idx)-'0']++;
if (secret.charAt(idx) == guess.charAt(idx)){
countA++;
map[secret.charAt(idx)-'0']--;
}
}
idx=-1;
while (++idx < secret.length()){
if (secret.charAt(idx) != guess.charAt(idx) && map[guess.charAt(idx)-'0'] > 0){
countB++;
map[guess.charAt(idx)-'0']--;
}
}
return countA + "A" + countB + "B";
}
}给定正整数 n ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。
如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。
示例 1：
输入：n = 1 输出：true
示例 2：
输入：n = 10 输出：false
提示：
1 <= n <= 109明明各方面都非常的符合题意，但是只击败了5.28%的勇者【怎么都在打表】
emmm，emmm，emmm，能AC，海星
思路什么的，就回溯，转2进制，判断除了第一位之后有没有其他的1
class Solution {
int[] arr;
int[] sizeMap = {0,9,99,999,9999,99999,999999,9999999,99999999,999999999,2147483647};
public boolean reorderedPowerOf2(int n) {
if (n==0){
return false;
}
int size = 0;
//看看这个数字能转成多大的int[]数组，然后用来执行回溯
for (int i = 0; i < sizeMap.length; i++) {
if (sizeMap[i] >= n){
size = i;
break;
}
}
arr = new int[size];
//把n数字的个位置上的数字放入数组中
while (n > 0){
arr[--size] = n % 10;
n /= 10;
}
//执行回溯
return dfs(0,0,new boolean[arr.length]);
}
/**
* 判断一个数字是否是2的幂
* @param num
* @return
*/
public boolean isPowerOf2(int num){
int[] intArr = toBinaryArr(num);
for (int i = 1; i < intArr.length; i++) {
//2的幂的二进制有一个特点，就是只有第一位是1，后面都是0，
//从第二位开始判断但凡有一个数字等于1，就返回false
if (intArr[i] == 1){
return false;
}
}
//后面都没有1，只有第一位是1，那么返回true;
return true;
}
/**
* 把一个数字转换成二进制int[]数组
* @param num
* @return
*/
public int[] toBinaryArr(int num){
int size = 32;
//最大就32位，往大了写，之间判断某个数字的二进制数字有多长有点麻烦
int[] intArr = new int[size];
while (num > 0 ){
//依次余2赋值在每一位上
intArr[--size] = num % 2;
num = num >> 1;
}
//到这里就已经知道之前用了多少位了，返回一个新的不含前面多余0的二进制数数字
int[] res = new int[32 - size];
System.arraycopy(intArr,size,res,0,32-size);
return res;
}
/**
* 回溯算法
* @param num 当前数字
* @param idx 当前数字的位数的
* @param used arr[]数组中哪些位置已经被用过了
* @return
*/
public boolean dfs(int num, int idx, boolean[] used){
if (idx == arr.length ){
//终止条件，判断下这个数是否是2的幂数
if (isPowerOf2(num)){
return true;
}
return false;
}
//当前数字乘以10，准备在后面再加上一个数字
num *= 10;
for (int i = 0; i < arr.length; i++) {
//第一位数字不能为0
//或者这个位置的数字已经用过了，那么跳过到下一个选项
if ((idx == 0 && arr[i] == 0) || used[i]){
continue;
}
//标记当前数字用过了
used[i] = true;
//构建了新数字num+arr[i] 然后处理下一个情况
if (dfs(num+arr[i],idx+1,used)){
//如果能满足就直接终止
return true;
}
//回溯的重要操作，将状态改回
used[i] = false;
}
//如果都不能满足，返回false
return false;
}
}
看了一圈好像都在打表。。。。
我也凑个热闹吧
class Solution {
int[][] arr = {
{1,1,0,0,0,0,0,0,0,0,0},
{1,2,0,0,0,0,0,0,0,0,0},
{1,4,0,0,0,0,0,0,0,0,0},
{1,8,0,0,0,0,0,0,0,0,0},
{2,1,6,0,0,0,0,0,0,0,0},
{2,2,3,0,0,0,0,0,0,0,0},
{2,4,6,0,0,0,0,0,0,0,0},
{3,1,2,8,0,0,0,0,0,0,0},
{3,2,5,6,0,0,0,0,0,0,0},
{3,1,2,5,0,0,0,0,0,0,0},
{4,0,1,2,4,0,0,0,0,0,0},
{4,0,2,4,8,0,0,0,0,0,0},
{4,0,4,6,9,0,0,0,0,0,0},
{4,1,2,8,9,0,0,0,0,0,0},
{5,1,3,4,6,8,0,0,0,0,0},
{5,2,3,6,7,8,0,0,0,0,0},
{5,3,5,5,6,6,0,0,0,0,0},
{6,0,1,1,2,3,7,0,0,0,0},
{6,1,2,2,4,4,6,0,0,0,0},
{6,2,2,4,5,8,8,0,0,0,0},
{7,0,1,4,5,6,7,8,0,0,0},
{7,0,1,2,2,5,7,9,0,0,0},
{7,0,1,3,4,4,4,9,0,0,0},
{7,0,3,6,8,8,8,8,0,0,0},
{8,1,1,2,6,6,7,7,7,0,0},
{8,2,3,3,3,4,4,5,5,0,0},
{8,0,1,4,6,6,7,8,8,0,0},
{9,1,1,2,2,3,4,7,7,8,0},
{9,2,3,4,4,5,5,6,6,8,0},
{9,0,1,2,3,5,6,7,8,9,0},
{10,0,1,1,2,3,4,4,7,7,8}
};
int[] sizeMap = {0,9,99,999,9999,99999,999999,9999999,99999999,999999999,2147483647};
public boolean reorderedPowerOf2(int n) {
if (n==0){
return false;
}
int size = 0;
//看看这个数字能转成多大的int[]数组
for (int i = 0; i < sizeMap.length; i++) {
if (sizeMap[i] >= n){
size = i;
break;
}
}
int[] numArr = new int[size];
//把n数字的个位置上的数字放入数组中
while (n > 0){
numArr[--size] = n % 10;
n /= 10;
}
Arrays.sort(numArr);
for (int[] ints : arr) {
if (ints[0] == numArr.length){
int idx = 0;
while (++idx<=ints[0] && ints[idx] == numArr[idx-1]){}
if(--idx == ints[0] && ints[idx] == numArr[idx-1]){
return true;
}
}
}
return false;
}
}
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
示例 1:
输入：s = "abaccdeff" 输出：'b'
示例 2:
输入：s = "" 输出：' '
限制：
0 <= s 的长度 <= 50000
HashMap<Character,Integer> firstShowMap记录各个字符第一次出现的位置HashSet<Character> moreThenOneSet保存出现超过一次的字符firstShowMap，对比moreThenOneSet处理只有出现一次的字符firstSingle保存单个的字符和firstSingleIndex对应的出现位置firstShowMap的过程中如果找到一个新的只出现过一次的字符，两者比较firstSingleIndex，留下位置跟靠前的那一个代码
class Solution {
public char firstUniqChar(String s) {
HashMap<Character,Integer> firstShowMap = new HashMap<>();
HashSet<Character> moreThenOneSet = new HashSet<>();
int i = -1;
while (++i < s.length()){
if (!firstShowMap.containsKey(s.charAt(i))){
firstShowMap.put(s.charAt(i),i);
}else{
moreThenOneSet.add(s.charAt(i));
}
}
final char[] firstSingle = {' '};
final int[] firstSingleIndex = {s.length()};
firstShowMap.forEach((theChar,theIndex)->{
if (!moreThenOneSet.contains(theChar)){
if (theIndex < firstSingleIndex[0]){
firstSingleIndex[0] = theIndex;
firstSingle[0] = theChar;
}
}
});
return firstSingle[0];
}
}思路就是这样，实现形式有很多种
比如
firstSingleIndex也可以不存下来，直接回firstShowMap中取到moreThenOneSet可以省略，有重复的直接修改firstShowMap对应的value为一个不合理的值，后面判断的时候也就根据这个不合理的值来判断。class Solution {
public char firstUniqChar(String s) {
if (s.length()==0){
return ' ';
}
//重复的
boolean[] map1 = new boolean[26];
//第一次出现的位置
int[] map2 = new int[26];
Arrays.fill(map2,-1);
int idx = -1;
while (++idx < s.length()){
int charIdx = s.charAt(idx)-'a';
if (!map1[charIdx]){
if (map2[charIdx] != -1){
map1[charIdx] = true;
map2[charIdx] = -1;
}else{
map2[charIdx] = idx;
}
}
}
char ans = ' ';
int min = s.length();
for (int i = 0; i < map2.length; i++) {
if (map2[i] != -1 && map2[i] < min){
min = map2[i];
ans = s.charAt(min);
}
}
return ans;
}
}再次思考，也可以不用两个map，在一个map上定义更多的状态来实现，除了现有的-1表示默认没处理的情况，也可以再定一个-2为已经有多个相同字符出现的情况
给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
示例 1：
输入：[3,2,3] 输出：[3]
示例 2：
输入：nums = [1] 输出：[1]
示例 3：
输入：[1,1,1,3,3,2,2,2] 输出：[1,2]
提示：
1 <= nums.length <= 5 * 104-109 <= nums[i] <= 109
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。
1/3的个数的1/3的留下不好理解的话，我们换个角度。假如你有一根火腿肠，但是吃火腿肠的话有一个奇怪的习惯，需要把火腿肠分成N段，然后凑齐其中的3段，并排在一起，然后一起咬一块。
大概就。。这样？一根长度为9的火腿肠（毕竟比较好除以3）
此时你切成的N段火腿肠中，确保有一段是长度大于1/3的，那么思考一下，在每次都要拿着3段一起吃的情况下，即使你一直拿着那个大于1/3的那段，到最后这段也会生下来，毕竟到最后凑不出3段一起吃了。
或者换个思路，除去最长的大于1/3的那段，剩下的总和是小于2/3的，那么这个2/3再分成两段的，最极限情况下，要保持3段的情况，这边分出来的也都是小于1/3的。
最后剩余的情况
剩下的数字并不一定的大于1/3的，还是上面的长度9的举例子，比如分成了4，3，2这样的长度组合的，3个一起进行消除，最后剩下的长度的2，1，所以还得回去再统计一遍，不过再统计的时候只需要统计剩下的两个数字的，如果是剩下1个，必然是大于1/3的。
先决条件：需要保证给出的数组中一定存在数量超过1/3的数字
那么在理解了思想的情况下这个之后，如果是类似的题目就基本都是这个套路能解决了
代码
class Solution {
/**
* 初始化了边界外的数值，表示一个空位子
*/
int[] nums = {1000000001,1000000001,1000000001};
int[] countArr = {0,0,0};
public List<Integer> majorityElement(int[] nums) {
for (int i = 0; i < nums.length; i++) {
processNum(nums[i]);
}
//数量重新归零
countArr[0] = 0;
countArr[1] = 0;
countArr[2] = 0;
for (int i = 0; i < nums.length; i++) {
//统计剩下的数字出现的次数
countArr[0] += this.nums[0] == nums[i]?1:0;
countArr[1] += this.nums[1] == nums[i]?1:0;
countArr[2] += this.nums[2] == nums[i]?1:0;
}
List<Integer> list = new ArrayList<>();
for (int i = 0; i < this.nums.length; i++) {
//留下大于1/3的
if (this.nums[i] < 1000000001 && countArr[i] > nums.length/3){
list.add(this.nums[i]);
}
}
return list;
}
public void processNum(int num){
//是否是新插入的
boolean insertFlag = false;
for (int i = 0; i < 3; i++) {
//原有有这个数字
if (nums[i] == num){
//数量加1
countArr[i]++;
insertFlag = true;
}
}
//是原来不存在的数字，
if (!insertFlag){
for (int i = 0; i < 3; i++) {
//找个空位子给安排下，并计数为1
if (nums[i] == 1000000001){
nums[i] = num;
countArr[i] = 1;
break;
}
}
}
//如果没凑到3个数字，就继续往里一个新数字来处理
if (countArr[0]==0 || countArr[1] == 0 || countArr[2]==0){
return;
}
//如果是3个不同的数字，每个数字减一，
// 并把剩余0的那个数字占的位子空出来
for (int i = 0; i < 3; i++) {
countArr[i]--;
if (countArr[i]==0){
nums[i] = 1000000001;
}
}
}
}