【 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 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 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;

  }

}