稀土掘金-11.观光景点组合得分问题（11.观光景点组合得分问题）

题目分析：

values数组保存的第i个元素表示第i个景点的评分，i、j两个景点之间的距离由下标之差表示。现在要求values数组中的各个景点两两组合的最高观光得分，表示为values[i] + values[j] + i - j。

解题思路：

使用双指针法遍历数组，两两组合计算得分，并实时更新最高得分，直到遍历完全所得即为最高得分。

public class Main {
    public static int solution(int[] values) {
        int highestScore = 0;
        int n = values.length;
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                highestScore = Math.max(values[i] + values[j] + i - j, highestScore); 
            }
        }
        return highestScore; // Placeholder return
    }

    public static void main(String[] args) {
        System.out.println(solution(new int[]{8, 3, 5, 5, 6}) == 11 ? 1 : 0);
        System.out.println(solution(new int[]{10, 4, 8, 7}) == 16 ? 1 : 0);
        System.out.println(solution(new int[]{1, 2, 3, 4, 5}) == 8 ? 1 : 0);
    }
}

稀土掘金-13.构造特定数组的逆序拼接（13.构造特定数组的逆序拼接）

题目分析：

构造一个这样的数组：对于从1到n的n个i，将n组“数字n到i的逆序”拼接起来，最终返回该数组。

解题思路：

使用双指针法，外层指针是由1到n的i，内层指针是由n到i的j，将元素依次添入ArrayList，最终转换成整型数组。

总结反思：

有待掌握以下技巧：

• .stream()
• .mapToInt()
• 方法引用Integer::intValue
• lamda表达式i -> i.intValue

import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.IntStream;

public class Main {
    public static int[] solution(int n) {
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            for (int j = n; j >= i; j--) {
                res.add(j);
            }
        }
        return res.stream().mapToInt(Integer::intValue).toArray();
    }

    public static void main(String[] args) {
        System.out.println(Arrays.equals(solution(3), new int[]{3, 2, 1, 3, 2, 3}));
        System.out.println(Arrays.equals(solution(4), new int[]{4, 3, 2, 1, 4, 3, 2, 4, 3, 4}));
        System.out.println(Arrays.equals(solution(5), new int[]{5, 4, 3, 2, 1, 5, 4, 3, 2, 5, 4, 3, 5, 4, 5}));
    }
}

稀土掘金-9.超市里的货物架调整(9.超市里的货物架调整)

题目分析：

• n：货物架的格子数
• m：顾客想要购买的商品种类数
• s：货物架上商品的初始顺序
• c：顾客想要购买的商品种类

观察样例可知，m定义有误，实际上表达的是c中的字母个数，及商品数量而非商品种类数。

顾客会依次从第一个格子查找到第n个格子以购买所需商品，若遇到空格子或已到达第n格仍未找到所需商品则自行离开。

解题思路：

由于顾客购物是按照c的顺序，每次都从1到n查找货架格子，因此为使卖出商品的数量尽可能多，则使s重排后，应符合按照c的顺序摆放商品，若到某次购物时对应种类商品的数量已为0，当前顾客的购买需求跳过即可，则此时对应次序的货架上摆放的应为下一个顾客的所需的商品。

现在分类讨论：

• 若n>=m，则货物数量不少于顾客所需的商品总数，此时问题简化为s和c中26个小写字母及其个数的交集所得字符数之和。
• 若n<m，则在前一种情况的基础上约束最大值为n。

import java.util.HashMap;
import java.util.Map;


public class Main {
    public static int solution(int n, int m, String s, String c) {
        int res = 0;
        char[] sArray = s.toCharArray();
        char[] cArray = c.toCharArray();
        Map<Character, Integer> map = new HashMap<>();
        for (char i : sArray) {
            int newValue = 0;
            if (map.containsKey(i)) newValue = map.get(i)+1;
            else newValue = 1;
            map.put(i, newValue);
        }
        for (char j : cArray) {
            if (map.containsKey(j)) {
                if (map.get(j) > 0) {
                    map.put(j, map.get(j)-1);
                    res++;
                }
            }
        }
        return res > n ? n : res;
    }

    public static void main(String[] args) {
        System.out.println(solution(3, 4, "abc", "abcd") == 3);
        System.out.println(solution(4, 2, "abbc", "bb") == 2);
        System.out.println(solution(5, 4, "bcdea", "abcd") == 4);
    }
}

稀土掘金-10.小F的永久代币卡回本计划（10.小F的永久代币卡回本计划）

题目分析：

一个简单的取上限除法问题

public class Main {
    public static int solution(int a, int b) {
        return a % b == 0 ? a/b : a/b + 1;
    }

    public static void main(String[] args) {
        System.out.println(solution(10, 1) == 10);
        System.out.println(solution(10, 2) == 5);
        System.out.println(solution(10, 3) == 4);
    }
}

稀土掘金-8.找出整型数组中占比超过一半的数（8.找出整型数组中占比超过一半的数）

题目分析：

如题

解题思路：

• 先取数组array的长度为n，
• 然后构建一个Map，遍历数组统计键值对
• 遍历Map，找到值大于n/2的键并返回

总结反思：

由于正常的返回情况位于if语句中，因此需在代码段末尾增加return 0;以确保代码健全性。

import java.util.Map;
import java.util.HashMap;
public class Main {
    public static int solution(int[] array) {
        int n = array.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : array) {
            map.put(i, map.containsKey(i) ? map.get(i)+1 : 1);
        }
        for (Integer key : map.keySet()) {
            if (map.get(key) > n/2) return key;
        }
        return 0;
    }

    public static void main(String[] args) {
        System.out.println(solution(new int[]{1, 3, 8, 2, 3, 1, 3, 3, 3}) == 3);
    }
}

稀土掘金-5.寻找最大葫芦（5.寻找最大葫芦）

题目分析：

“葫芦”牌型是由三张面值相同的牌a和另外两张面值相同的牌b，共五张牌组成的牌型。

牌与牌之间比较大小的原则是1 (A) > K > Q > J > 10 > 9 > ... > 2，其中1(A)的面值为1，K的面值为13，以此类推。

葫芦与葫芦之间大小比较的原则为先比较a，再比较b。

增加限定：组成葫芦的五张牌的面值之和不超过给定值max。

此时，需要从给定的一组牌数量为n的牌组array中，找到使“葫芦”按照比较原则是最大的牌a和牌b，并满足“葫芦”的牌面值之和不超过max。

解题思路：

• 先将array中的牌的面值及每种牌的个数映射到一个HashMap中。
• 然后按照牌与牌的比大小顺序，从HashMap中取出当前最大的、张数不少于3的牌，若此时该牌的面值乘3不小于max，则继续取该牌之后第二大的牌做判断，否则该牌的面值即为a；若仍然找不到符合条件的a，返回[0,0]。
• 接着继续按照牌与牌比大小顺序，从HashMap中取出rules中不为a的、最大的、张数不少于2的牌，若该牌与a组成的“葫芦”的面值之和超过max，则继续取该牌之后不为a的第二大的牌做判断，否则该牌的面值即为所求b；若仍然找不到符合条件的b，返回[0,0]。
• 最终返回所得的[a,b]

总结反思：

注意：b不为a，但b不一定小于a，因为若b按照比大小原则大于a，b的张数可能不足3或者3b>=max，但3a+2b<=max是有可能的。

import java.util.Map;
import java.util.HashMap;
public class Main {
    public static int[] solution(int n, int max, int[] array) {
        Map<Integer, Integer> map = new HashMap<>();
        int[] rules = {1, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2};
        for (int card : array) {
            map.put(card, map.getOrDefault(card, 0)+1);
        }
        for (int i = 0; i < 13; i++) {
            int a = rules[i];
            // 检查map中是否包含a，并且a的数量不少于3且面值之和小于max
            if (map.containsKey(a) && map.get(a) >= 3 && a * 3 < max) {
                for (int j = 0; j < 13; j++) {
                    int b = rules[j];
                    // 检查map中是否包含b，并且b的数量不少于2且5张牌面值之和不超过max
                    if (a != b && map.containsKey(b) && map.get(b) >= 2 && a * 3 + b * 2 <= max) {
                        return new int[]{a, b};
                    }
                }
            }
        }
        return new int[]{0, 0};
    }

    public static void main(String[] args) {
        // Add your test cases here
        
        System.out.println(java.util.Arrays.equals(solution(9, 34, new int[]{6, 6, 6, 8, 8, 8, 5, 5, 1}), new int[]{8, 5}));
        System.out.println(java.util.Arrays.equals(solution(9, 37, new int[]{9, 9, 9, 9, 6, 6, 6, 6, 13}), new int[]{6, 9}));
        System.out.println(java.util.Arrays.equals(solution(9, 40, new int[]{1, 11, 13, 12, 7, 8, 11, 5, 6}), new int[]{0, 0}));
    }
}

稀土掘金-17.小M的数组变换（17.小M的数组变换）

题目分析：

题目定义每次操作可以选择任意两个元素i和j，并取i的一个因子x，将i变为i/x，j变为j*x。目标是通过有限次的操作，使得数组中的每个元素最多只包含一个为素数的因子，即素因子。

解题思路：

审题可知：i/x使得更新后的i可能失去x这个因子，但j*x使得更新后的j一定含有x这个因子。

因此，整个数组的素因子总数不会因为执行题目定义的操作而减少或增加。

因而操作步骤如下：

• 首先对每个数进行质因数分解，统计素因子的种类个数，若素因子的种类个数大于数组长度的话，显然无法做到让每个元素只有一种素因子。
• 接下来讨论质因子的种类个数小于数组长度的情况：

• • 以A和B均含有x、y这两个质因子为例，可以连续执行[A,B,x]（A/x,B*x)直至A不再含有x这一质因子为止，然后再连续执行[B,A,y]直至B不再包含y这一质因子为止。
  • 类推可知：任意元素B可以作为“桥梁”，通过连续执行[A,B,x]直至A不再含有x这一质因子为止，从而将x这一质因子“转移”到B上，最终通过有限次的“转移”实现每个元素最多包含一个素因子（可以想象，先将所有质因子转移到一个元素身上，再将每一个质因子分配到不同的元素身上）。
  • 因此可以通过有限次操作使得每个元素最多只包含一种素因子。

import java.util.HashSet;
import java.util.Set;
public class Main {
    public static String solution(int n, int[] a) {
        Set<Integer> set = new HashSet<>();
        for (int num : a) {
            for (int i = 2; i*i <= num; i++){
                if (num % i == 0) set.add(i);
                while(num % i == 0) num /= i;
            }
            if (num > 1) set.add(num);
        }
        if (set.size() > a.length) return "No";
        else return "Yes";
    }

    public static void main(String[] args) {
        System.out.println(solution(4, new int[]{1, 2, 3, 4}).equals("Yes"));
        System.out.println(solution(2, new int[]{10, 12}).equals("No"));
        System.out.println(solution(3, new int[]{6, 9, 15}).equals("Yes"));
    }
}

稀土掘金-4.数字分组求偶数和（4.数字分组求偶数和）

题目分析：

给定的numbers包含将1~9这9个数字分成可能的1至9个数字分组，现要求当从每个数字分组中依次选出一个数字并依次组合成一个各位数字之和为偶数的数，有多少个这样的数并返回其数量。

解题思路：

这是一道动态规划的题目：

• 初始情况下，偶数和的组合数为1，奇数和的组合数为0
• 开始遍历数组中的每一个数字分组

• • 先统计该数字分组的奇偶数个数
  • 更新new偶数和的组合数=原偶数和的组合数*该组的偶数个数+原奇数和的组合数*该组的奇数个数
  • 更新new奇数和的组合数=原偶数和的组合数*该组的奇数个数+原奇数和的组合数*该组的偶数个数

• 最终返回所得的偶数和的组合数即可

public class Main {
    public static int solution(int[] numbers) {
        // 初始化偶数和组合数为1，奇数和组合数为0
        int evenWays = 1;
        int oddWays = 0;
        // 遍历每一个数字组
        for (int number : numbers) {
            int evenCount = 0;
            int oddCount = 0;
            
            // 将数字转换为字符串来遍历每一位
            String group = Integer.toString(number);
            
            // 统计当前组中偶数和奇数的个数
            for (int i = 0; i < group.length(); i++) {
                int digit = group.charAt(i) - '0'; // 将字符转换为数字
                if (digit % 2 == 0) {
                    evenCount++;
                } else {
                    oddCount++;
                }
            }
            
            // 动态规划更新 evenWays 和 oddWays
            int newEvenWays = evenWays * evenCount + oddWays * oddCount;
            int newOddWays = oddWays * evenCount + evenWays * oddCount;
            
            evenWays = newEvenWays;
            oddWays = newOddWays;
        }
        // 返回能够形成偶数和的组合数
        return evenWays;
    }
 
    public static void main(String[] args) {
        // You can add more test cases here
        System.out.println(solution(new int[]{123, 456, 789}) == 14);
        System.out.println(solution(new int[]{123456789}) == 4);
        System.out.println(solution(new int[]{14329, 7568}) == 10);
    }
}