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

上岸算法 · 发表于 2021-11-21 22:28:20

登录后可回复主题

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

x

【 NO.1 两栋颜色不同且距离最远的房子】

解题思路
签到题，循环判断即可。

代码展示

class Solution {
public int maxDistance(int[] colors) {
   for (int len = colors.length; len >= 1; len--) {
         for (int i = 0; i + len <= colors.length; i++) {
            if (colors[i] != colors[i + len - 1]) {
               return len - 1;
            }
      }
   }
   return 0;
  }
}

【 NO.2 给植物浇水】

解题思路
模拟浇水过程即可。

代码展示

class Solution {
public int wateringPlants(int[] plants, int capacity) {
   int res = 0;
   int water = capacity;
   for (int i = 0; i < plants.length; i++) {
         if (water < plants[i]) {
            water = capacity;
            res += i * 2;
      }
         res++;
         water -= plants[i];
   }
   return res;
  }
}

【 NO.3 区间内查询数字的频率】

解题思路
二分查找。统计出每个数字的所有出现位置，然后在位置列表上进行二分查找即可得到该列表中位于 [left, right] 范围的元素有多少个。

代码展示

class RangeFreqQuery {
Map<Integer, List<Integer>> pos;

public RangeFreqQuery(int[] arr) {
   pos = new HashMap<>();
   for (int i = 0; i < arr.length; i++) {
         if (!pos.containsKey(arr[i])) {
            pos.put(arr[i], new ArrayList<>());
      }
         pos.get(arr[i]).add(i);
   }
  }

public int query(int left, int right, int value) {
   if (!pos.containsKey(value)) {
         return 0;
   }
   List<Integer> p = pos.get(value);
   int start = bSearch2(p, left);
   int end = bSearch(p, right);
   return end - start + 1;
  }

// 二分查找最后一个 <= value 的元素下标
int bSearch(List<Integer> arr, int value) {
   if (arr.size() == 0 || value < arr.get(0)) {
         return -1;
   }
   int left = 0, right = arr.size() - 1;
   while (left + 1 < right) {
         int mid = (left + right) / 2;
         if (arr.get(mid) <= value) {
            left = mid;
      } else {
            right = mid;
      }
   }
   return arr.get(right) <= value ? right : left;
  }

// 二分查找第一个 >= value 的元素下标
int bSearch2(List<Integer> arr, int value) {
   if (arr.size() == 0 || arr.get(arr.size() - 1) < value) {
         return arr.size();
   }
   int left = 0, right = arr.size() - 1;
   while (left + 1 < right) {
         int mid = (left + right) / 2;
         if (arr.get(mid) < value) {
            left = mid;
      } else {
            right = mid;
      }
   }
   return arr.get(left) < value ? right : left;
  }
}

【 NO.4 k 镜像数字的和】
解题思路
回溯法枚举即可。

代码展示

class Solution {
int n;
long sum;

public long kMirror(int k, int n) {
   this.sum = 0;
   this.n = n;
   for (int len = 1; this.n > 0; len++) {
         // 长度为 len 的 k 进制的镜像数字
         char[] chars = new char[len];
         dfs(chars, 0, chars.length - 1, k);
   }
   return sum;
  }

private void dfs(char[] chars, int i, int j, int k) {
   if (this.n == 0) {
         return;
   }
   if (i == j) {
         for (int p = 0; p < k; p++) {
            if (p == 0 && i == 0) {
               continue;
            }
            chars[i] = (char) ('0' + p);
            dfs(chars, i + 1, j - 1, k);
      }
         return;
   }
   if (i > j) {
         long ten = Long.parseLong(String.valueOf(chars), k);
         String str = String.valueOf(ten);
         for (int l = 0, r = str.length() - 1; l < r; l++, r--) {
            if (str.charAt(l) != str.charAt(r)) {
               return;
            }
      }
         this.n--;
         sum += ten;
         return;
   }
   for (int p = 0; p < k && this.n > 0; p++) {
         if (i == 0 && p == 0) {
            continue;
      }
         chars[i] = chars[j] = (char) ('0' + p);
         dfs(chars, i + 1, j - 1, k);
   }
  }
}

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

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

登录后可回复主题