第一题
题目描述
解题思路
直接寻找就行了
解题代码
class Solution {
public int mostFrequent(int[] nums, int key) {
int n = nums.length;
int res = 0;
int res_count=0;
HashMap<Integer,Integer> map = new HashMap<>();
for (int i = 0;i<= n-2;i++){
if (nums[i]==key){
int k = map.getOrDefault(nums[i+1],0)+1;
map.put(nums[i+1],k);
if (k>res_count){
res_count = k;
res = nums[i+1];
}
}
}
return res;
}
}
第二题
题目描述
解题思路
要按照mapping的结果进行排序，因此，把原数字和目标数字封装对象，根据目标数字编写Comparator。
解题代码
class Solution {
public int[] sortJumbled(int[] mapping, int[] nums) {
ArrayList<P> list = new ArrayList<>();
for (int n : nums) {
StringBuilder sb = new StringBuilder();
for (char c : String.valueOf(n).toCharArray()) {
sb.append(mapping[c - 48]);
}
int tar = Integer.parseInt(sb.toString());
list.add(new P(n, tar));
}
list.sort(new Comparator<P>() {
@Override
public int compare(P o1, P o2) {
return o1.target - o2.target;
}
});
int[] res = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
res[i] = list.get(i).src;
}
return res;
}
}
class P {
int src;
int target;
public P(int src, int target) {
this.src = src;
this.target = target;
}
}第三题
题目描述
解题思路
?这是一个深度优先遍历，在遍历的时候，可以记录已经遍历的节点，避免重复遍历。
解题代码
class Solution {
private final HashMap<Integer, List<Integer>> map = new HashMap<>();
private final HashMap<Integer, List<Integer>> edg = new HashMap<>();
public List<List<Integer>> getAncestors(int n, int[][] edges) {
// 先把节点加入Map.
for (int[] edge : edges) {
int start = edge[0];
int end = edge[1];
List<Integer> l = edg.getOrDefault(end, new ArrayList<Integer>());
l.add(start);
edg.put(end, l);
}
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < n; i++) {
// 从 i 开始往上分析。 进行深度有限遍历
List<Integer> list = dfs(i);
map.put(i, list);
res.add(list);
}
return res;
}
private List<Integer> dfs(int n) {
if (!edg.containsKey(n)) {
// 我是父节点
return new ArrayList<>();
}
if (map.containsKey(n)) {
// 此节点已经做过计算，可以直接返回
return map.get(n);
}
// 获取当前节点的父节点
List<Integer> fathers = edg.get(n);
HashSet<Integer> temps = new HashSet<>();
for (int f : fathers) {
temps.addAll(dfs(f));
}
fathers.addAll(temps);
List<Integer> res = new ArrayList<>(new HashSet<>(fathers));
Collections.sort(res);
map.put(n, res);
return res;
}
}第四题
题目描述
?
解题思路
本题没有做出来，看了大佬的思路，竟然是个贪心。
由于题目保证原串一定可以变成回文串，那么原串中最多只有一种字母出现奇数次。如果有一种字母出现奇数次，那么将该字母中排在最中间的字符移动到字符串中间，剩下的字符可以转化为所有字母均出现偶数次的情况。
贪心算法是：每次固定字符串最左边的字母 aa 不变，找出距离字符串右侧最近的 aa，把它交换到字符串最右边。这样字符串的头尾字母就相等了。把字符串的头尾去掉，就变成了子问题。把所有子问题的答案加起来就是最少交换次数。
作者：tsreaper
链接：https://leetcode-cn.com/problems/minimum-number-of-moves-to-make-palindrome/solution/tan-xin-zheng-ming-geng-da-shu-ju-fan-we-h57i/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
解题代码
class Solution {
public int minMovesToMakePalindrome(String s) {
int n = s.length();
if (n <= 2) {
return 0;
}
char c = s.charAt(0);
int len = 0;
int i;
for (i = n - 1; i >= 0; i--) {
if (c == s.charAt(i)) {
len = n - i - 1;
break;
}
}
String sub;
if (i==0){
len = len/2;
sub = s.substring(1);
}else {
sub = s.substring(1, i) + s.substring(i + 1, n);
}
return len + minMovesToMakePalindrome(sub);
}
}