上岸算法 发表于 2021-12-21 00:08:58

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

【 NO.1 找出数组中的第一个回文字符串】

解题思路
签到题,遍历一次即可。

代码展示

class Solution {
   public String firstPalindrome(String[] words) {
       for (var w : words) {
         boolean found = true;
         for (int i = 0, j = w.length() - 1; i < j; i++, j--) {
               if (w.charAt(i) != w.charAt(j)) {
                   found = false;
                   break;
            }
          }
         if (found) {
               return w;
          }
      }
       return "";
}
}


【 NO.2 向字符串添加空格】

解题思路
使用一个 StringBuilder 维护新的字符串。

代码展示

class Solution {
   public String addSpaces(String s, int[] spaces) {
       StringBuilder sb = new StringBuilder();
       int sp = 0;
       for (int i = 0; i < s.length(); i++) {
         if (sp < spaces.length && i == spaces) {
               sp++;
               sb.append(' ');
          }
         sb.append(s.charAt(i));
      }
       return sb.toString();
}
}


【 NO.3 向字符串添加空格】

解题思路
双指针。

代码展示

class Solution {
   public long getDescentPeriods(int[] prices) {
       long result = 0;
       for (int i = 0, j = 0; i < prices.length; i++) {
         if (i > 0 && prices != prices - 1) {
               j = i;
          }
         // 是一个平滑下跌阶段
         result += i - j + 1;
      }
       return result;
}
}


【 NO.4 使数组 K 递增的最少操作次数】

解题思路
原数组可以拆分成 K 个子数组,这 K 个子数组之间互不影响。

然后问题就变成了使一个数组变成递增的至少要改变几个元素,直接求最长递增子序列即可,使用 nlogn 的算法。

代码展示

class Solution {
   public int kIncreasing(int[] arr, int k) {
       int result = 0;
       for (int i = 0; i < k; i++) {
         List<Integer> list = new ArrayList<>();
         for (int j = i; j < arr.length; j += k) {
               list.add(arr);
          }
         result += increasing(list);
      }
       return result;
}

   private int increasing(List<Integer> nums) {
       // 将 nums 变成递增
       // nlogn 求 LIS
       int[] dp = new int;
       int len = 0;
       for (int num : nums) {
         int l = 0, r = len;
         while (l < r) {
               int mid = (l + r) / 2;
               if (dp <= num) { // 非严格递增,等于也可
                   l = mid + 1;
            } else {
                   r = mid;
            }
          }
         if (r >= len) {
               len++;
          }
         dp = num;
      }

       return nums.size() - len;
}
}
页: [1]
查看完整版本: 上岸算法LeetCode Weekly Contest 272解题报告