上岸算法 发表于 2021-10-31 22:58:16

上岸算法LeetCode Weekly Contest 265解题报告

【 NO.1 值相等的最小索引】
解题思路
签到题。

代码展示

class Solution {
   public int smallestEqual(int[] nums) {
       for (int i = 0; i < nums.length; i++) {
         if (i % 10 == nums) {
               return i;
          }
      }
       return -1;
}
}

【 NO.2 找出临界点之间的最小和最大距离】
解题思路
遍历链表即可。

代码展示

class Solution {
   public int[] nodesBetweenCriticalPoints(ListNode head) {
       if (head.next == null) {
         return new int[]{-1, -1};
      }
       List<Integer> pos = new ArrayList<>();
       int last = head.val;
       int p = 1;
       for (ListNode i = head.next; i.next != null; i = i.next) {
         if (last < i.val && i.next.val < i.val) {
               pos.add(p);
          } else if (i.val < last && i.val < i.next.val) {
               pos.add(p);
          }
         last = i.val;
         p++;
      }
       if (pos.size() < 2) {
         return new int[]{-1, -1};
      }
       int[] res = new int[]{pos.get(1) - pos.get(0), pos.get(pos.size() - 1) - pos.get(0)};
       for (int i = 2; i < pos.size(); i++) {
         int dis = pos.get(i) - pos.get(i - 1);
         res = Math.min(res, dis);
      }
       return res;
}
}

【 NO.3 转化数字的最小运算数】
解题思路
相当于 BFS 求最短路,为了提高运算速度,使用一个长度为 2001 的数组储存 [-1000, 1000] 范围内的数字,从 start 达到它们的最小步数。

因为题目规定,绝对值超过 1000 的数字不能继续运算,所以无需储存到达这些数字的最小步数。

代码展示

class Solution {
   public int minimumOperations(int[] nums, int start, int goal) {
       int[] min = new int;
       Arrays.fill(min, 0x7fffffff);
       min = 0;
       LinkedList<Integer> queue = new LinkedList<>();
       queue.add(start);
       while (!queue.isEmpty()) {
         int cur = queue.poll();
         int dis = min + 1;
         for (int i : nums) {
               int nxt = cur + i;
               if (nxt == goal) {
                   return dis;
            } else if (Math.abs(nxt) <= 1000 && min > dis) {
                   min = dis;
                   queue.add(nxt);
            }
          }
         for (int i : nums) {
               int nxt = cur - i;
               if (nxt == goal) {
                   return dis;
            } else if (Math.abs(nxt) <= 1000 && min > dis) {
                   min = dis;
                   queue.add(nxt);
            }
          }
         for (int i : nums) {
               int nxt = cur ^ i;
               if (nxt == goal) {
                   return dis;
            } else if (Math.abs(nxt) <= 1000 && min > dis) {
                   min = dis;
                   queue.add(nxt);
            }
          }
      }
       return -1;
}
}

【 NO.4 同源字符串检测】
解题思路
动态规划,细节见注释。

代码展示

class Solution {
   public boolean possiblyEquals(String s1, String s2) {
       // f 表示 s1 的前 i 个字符和 s2 的前 j 个字符匹配时可能的长度差
       Set<Integer>[][] f = new Set;
       for (int i = 0; i <= 40; i++) {
         for (int j = 0; j <= 40; j++) {
               f = new HashSet<>();
          }
      }
       int n = s1.length();
       int m = s2.length();
       f.add(0); // 初始化 f = {0}
       for (int i = 0; i <= n; i++) {
         for (int j = 0; j <= m; j++) {
               for (Integer diff : f) {
                   // 当 s1 为字母,且目前 s2 比 s1 长的时候,该字母可以直接被 s2 中的数字消化掉
                   if (i < n && !Character.isDigit(s1.charAt(i)) && diff < 0) {
                     f.add(diff + 1);
                  }
                   // 当 s2 为字母,且目前 s1 比 s2 长的时候,该字母可以直接被 s1 中的数字消化掉
                   if (j < m && !Character.isDigit(s2.charAt(j)) && diff > 0) {
                     f.add(diff - 1);
                  }
                   // 当 s1 == s2 且都为字母时,必须完全匹配(即要求 diff == 0)
                   if (i < n && j < m && s1.charAt(i) == s2.charAt(j) && !Character.isDigit(s1.charAt(i)) && diff == 0) {
                     f.add(0);
                  }
                   // 枚举 s1 的数字,加入到集合中
                   for (int o = i, p = 0; o < n && Character.isDigit(s1.charAt(o)); o++) {
                     p = p * 10 + (s1.charAt(o) - '0');
                     f.add(diff + p);
                  }
                   // 枚举 s2 的数字,加入到集合中
                   for (int o = j, p = 0; o < m && Character.isDigit(s2.charAt(o)); o++) {
                     p = p * 10 + (s2.charAt(o) - '0');
                     f.add(diff - p);
                  }
            }
          }
      }
       return f.contains(0);
}
}
页: [1]
查看完整版本: 上岸算法LeetCode Weekly Contest 265解题报告