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

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

登录后可回复主题

您需要登录才可以下载或查看，没有帐号？注册账号

x

【 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]) {
            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[i] != prices[i - 1] - 1) {
            j = i;
      }
         // [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[j]);
      }
         result += increasing(list);
   }
   return result;
  }

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

   return nums.size() - len;
  }
}

帐号		自动登录	找回密码
密码			注册账号

[吹水聊天] 上岸算法LeetCode Weekly Contest 272解题报告

登录后可回复主题