乐趣区

关于leetcode:LeetCode-Weekly-Contest-258解题报告

【NO.1 反转单词前缀】

解题思路

签到题。

代码展现

class Solution {

public String reversePrefix(String word, char ch) {

   int index = word.indexOf(ch);

   return new StringBuffer(word.substring(0, index + 1)).reverse().toString() +

           word.substring(index + 1);

}

}

【NO.2 可调换矩形的组数】

解题思路

将矩形依照长宽比分类,计数即可。

代码展现

class Solution {

static class Frac {

   int den;

   int num;

   public static int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);

  }

   public Frac(int num, int den) {int g = gcd(num, den);

       this.num = num / g;

       this.den = den / g;

  }

   @Override

   public boolean equals(Object o) {if (this == o) return true;

       if (o == null || getClass() != o.getClass()) return false;

       Frac frac = (Frac) o;

       return den == frac.den && num == frac.num;

  }

   @Override

   public int hashCode() {return Objects.hash(num, den);

  }

}

public long interchangeableRectangles(int[][] rectangles) {

   Map<Frac, Integer> count = new HashMap<>();

   for (var rec : rectangles) {Frac f = new Frac(rec[0], rec[1]);

       count.put(f, count.getOrDefault(f, 0) + 1);

  }

   long res = 0;

   for (var k : count.entrySet()) {int v = k.getValue();

       res += (long) v * (v - 1) / 2;

  }

   return res;

}

}

【NO.3 两个回文子序列长度的最大乘积】

解题思路

暴力枚举。应用二进制位示意一个子序列,枚举所有状况即可。

代码展现

class Solution {

public int maxProduct(String s) {

   int len = s.length();

   int res = 0;

   int[] mem = new int[1 << len];

   Arrays.fill(mem, -1);

   for (int i = 0; i < (1 << len); i++) {for (int j = 0; j < (1 << len); j++) {if ((i & j) > 0) {continue;}

           res = Math.max(res, length(s, i, mem) * length(s, j, mem));

      }

  }

   return res;

}

private int length(String s, int bitset, int[] mem) {

   if (mem[bitset] >= 0) {return mem[bitset];

  }

   mem[bitset] = 0;

   for (int i = 0, j = s.length() - 1; i <= j; i++, j--) {while (i <= j && (bitset & (1 << i)) == 0) i++;

       while (i <= j && (bitset & (1 << j)) == 0) j--;

       if (!(i <= j && (bitset & (1 << i)) != 0 && (bitset & (1 << j)) != 0)) {break;}

       if (s.charAt(i) == s.charAt(j)) {mem[bitset] += i == j ? 1 : 2;

      } else {mem[bitset] = 0;

           break;

      }

  }

   return mem[bitset];

}

}

【NO.4 每棵子树内缺失的最小基因值】

解题思路

DFS 合并 Set 即可。然而有两个优化很重要:

  1. 如果子树中缺失的最大的是 x, 那么枚举查找以后树缺失的只须要从 x 开始即可,而不是 1
  2. 合并 Set 时由小 Set 合并到大 Set 中

代码展现

class Solution {

public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {

   Map<Integer, List<Integer>> children = new HashMap<>();

   for (int i = 1; i < parents.length; i++) {if (!children.containsKey(parents[i])) {children.put(parents[i], new ArrayList<>());

      }

       children.get(parents[i]).add(i);

  }

   int[] ans = new int[parents.length];

   dfs(0, children, nums, ans);

   return ans;

}

private Set<Integer> dfs(int cur, Map<Integer, List<Integer>> children, int[] nums, int[] ans) {

   Set<Integer> set = new HashSet<>();

   set.add(nums[cur]);

   if (!children.containsKey(cur)) {ans[cur] = nums[cur] == 1 ? 2 : 1;

       return set;

  }

   var child = children.get(cur);

   int start = 1;

   for (var c : child) {var r = dfs(c, children, nums, ans);

       if (r.size() > set.size()) {

           Set<Integer> tmp = r;

           r = set;

           set = tmp;

      }

       set.addAll(r);

       start = Math.max(start, ans);

  }

   while (set.contains(start)) {start++;}

   ans[cur] = start;

   return set;

}

}

退出移动版