381. O(1) 时间插入、删除和获取随机元素 - 允许重复
和第380题不同的是，这一题的数字可以重复，所以某一个数字在动态数组中的位置可能会有多个，使用哈希表Set来存储位置，这样可以满足在O1的时间删除某个位置的要求。
class RandomizedCollection {
Map<Integer, Set<Integer>> map;
List<Integer> list;
Random random;
/**
* Initialize your data structure here.
*/
public RandomizedCollection() {
map = new HashMap<>();
list = new ArrayList<>();
random = new Random();
}
/**
* Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
*/
public boolean insert(int val) {
Set<Integer> set = map.getOrDefault(val, new HashSet<>());
int size = list.size();
list.add(val);
set.add(size);
map.put(val, set);
return set.size() == 1;
}
/**
* Removes a value from the collection. Returns true if the collection contained the specified element.
*/
public boolean remove(int val) {
if (!map.containsKey(val)) {
return false;
}
Set<Integer> set = map.get(val);
int index = set.iterator().next();
int lastElement = list.get(list.size() - 1);
list.set(index, lastElement);
set.remove(index);
//改最后一个元素的信息
Set<Integer> set2 = map.get(lastElement);
set2.remove(list.size() - 1);
if (index < list.size() - 1) {
set2.add(index);
}
map.put(lastElement, set2);
if (set.size() == 0) {
map.remove(val);
}
list.remove(list.size() - 1);
return true;
}
/**
* Get a random element from the collection.
*/
public int getRandom() {
return list.get(random.nextInt(list.size()));
}
}
382. 链表随机节点
容易想到的是把所有数都加载到数组中，时间复杂度On，空间复杂度On。
class Solution {
List<Integer> list;
Random random = new Random();
/**
* @param head The linked list's head.
* Note that the head is guaranteed to be not null, so it contains at least one node.
*/
public Solution(ListNode head) {
list = new ArrayList<>();
ListNode cur = head;
while (cur != null) {
list.add(cur.val);
cur = cur.next;
}
}
/**
* Returns a random node's value.
*/
public int getRandom() {
return list.get(random.nextInt(list.size()));
}
}
但是当链表十分大且长度未知时，由于要等概率的抽取一个数,On的时间复杂度是不可避免的，但是On空间复杂度太占内存了，下面给出O1空间复杂度的算法。
蓄水池抽样算法：
对于第i个数，以1/i的概率去替换第i-1个数，这样每个数被选的概率都是1/n。
class Solution {
ListNode head;
Random random;
/**
* @param head The linked list's head.
* Note that the head is guaranteed to be not null, so it contains at least one node.
*/
public Solution(ListNode head) {
this.head = head;
random = new Random();
}
/**
* Returns a random node's value.
*/
public int getRandom() {
ListNode cur = head;
int i = 1;
int val = cur.val;
while (cur != null) {
if (random.nextInt(i) == 0) {
val = cur.val;
}
i++;
cur = cur.next;
}
return val;
}
}
383. 赎金信
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] count = new int[26];
for (char c : ransomNote.toCharArray()) {
count[c - 'a']--;
}
for (char c : magazine.toCharArray()) {
count[c - 'a']++;
}
for (int i = 0; i < 26; i++) {
if (count[i] < 0) {
return false;
}
}
return true;
}
}
384. 打乱数组
暴力法：
先将原始数组改成动态数组，每次随机抽一个元素，然后删掉它，直到抽完所有元素。
时间复杂度On2，主要来源于list的remove操作,空间复杂度On。
class Solution {
int[] origin;
int[] shuffle;
Random random;
public Solution(int[] nums) {
this.origin = nums;
this.shuffle = origin.clone();
this.random = new Random();
}
/**
* Resets the array to its original configuration and return it.
*/
public int[] reset() {
return origin;
}
private List<Integer> getList() {
List<Integer> list = new ArrayList<>();
for (int i : origin) {
list.add(i);
}
return list;
}
/**
* Returns a random shuffling of the array.
*/
public int[] shuffle() {
List<Integer> list = getList();
for (int i = 0; i < shuffle.length; i++) {
int index = random.nextInt(list.size());
shuffle[i] = list.get(index);
list.remove(index);
}
return shuffle;
}
}
Fisher-Yates 洗牌算法:
第i轮从第i个数到最后一个数中抽一个数与shuffle[i]交换，这样可以保证每次抽到的数一定是之前未选过的。
时间复杂度On，空间复杂度On。
class Solution {
int[] origin;
int[] shuffle;
Random random;
public Solution(int[] nums) {
this.origin = nums;
this.shuffle = origin.clone();
this.random = new Random();
}
/**
* Resets the array to its original configuration and return it.
*/
public int[] reset() {
return origin;
}
private void swap(int i, int j, int[] nums) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
/**
* Returns a random shuffling of the array.
*/
public int[] shuffle() {
for (int i = 0; i < origin.length; i++) {
int index = i + random.nextInt(origin.length - i);
swap(i, index, shuffle);
}
return shuffle;
}
}
386. 字典序排数
class Solution {
List<Integer> res = new ArrayList<>();
public List<Integer> lexicalOrder(int n) {
for (int i = 1; i <= 9; i++) {
dfs(i, n);
}
return res;
}
private void dfs(int num, int n) {
if (num > n) {
return;
}
res.add(num);
for (int i = num * 10; i <= num * 10 + 9; i++) {
dfs(i, n);
}
}
}
387. 字符串中的第一个唯一字符
class Solution {
public int firstUniqChar(String s) {
Map<Character, Integer> map = new HashMap<>();
for (char c : s.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
for (int i = 0; i < s.length(); i++) {
if (map.get(s.charAt(i)) == 1) {
return i;
}
}
return -1;
}
}
388. 文件的最长绝对路径
class Solution {
public int lengthLongestPath(String input) {
int res = 0;//最终答案
int level = 0;//当前的层数
boolean flag = false;//是否是文件
int length = 0;//长度
int[] dp = new int[25];//当前每一层的长度
dp[0] = -1;
for (char c : input.toCharArray()) {
if (c == '\n') {
dp[level + 1] = length + 1 + dp[level];
if (flag == true) {
res = Math.max(res, dp[level + 1]);
}
length = 0;
level = 0;
flag = false;
} else if (c == '\t') {
level++;
} else {
if (c == '.') {
flag = true;
}
length++;
}
}
if (flag == true) {
res = Math.max(res, length + 1 + dp[level]);
}
return res;
}
}
389. 找不同
class Solution {
public char findTheDifference(String s, String t) {
int[] count = new int[26];
for (char c : s.toCharArray()) {
count[c - 'a']++;
}
for (char c : t.toCharArray()) {
count[c - 'a']--;
}
for (int i = 0; i < 26; i++) {
if (count[i] == -1) {
return (char) ('a' + i);
}
}
return 'B';
}
}
390. 消除游戏
模拟，超时：
class Solution {
public int lastRemaining(int n) {
boolean[] isDelete = new boolean[n + 1];
boolean flag = true;
int count = 0;
while (count < n - 1) {
for (int i = 1; i <= n && count < n - 1; i++) {
if (isDelete[i] == false && flag == true) {
isDelete[i] = true;
flag = false;
count++;
} else if (isDelete[i] == false) {
flag = true;
}
}
if (count == n - 2) {
break;
}
flag = true;
for (int i = n; i >= 1 && count < n - 1; i--) {
if (isDelete[i] == false && flag == true) {
isDelete[i] = true;
flag = false;
count++;
} else if (isDelete[i] == false) {
flag = true;
}
}
flag = true;
}
for (int i = 1; i <= n; i++) {
if (isDelete[i] == false) {
return i;
}
}
return -1;
}
}
找规律，和约瑟夫问题类似。找到f(2n),f(2n+1)和f(n)的关系:
class Solution {
public int lastRemaining(int n) {
if (n == 1) {
return 1;
}
if (n % 2 == 0) {
return n + 2 - 2 * lastRemaining(n / 2);
} else {
return n + 1 - 2 * lastRemaining((n - 1) / 2);
}
}
}
数学方法：
f(1) = α
f(2n) = -2f(n) + γn + β0
f(2n+1) = -2f(n) + γn + β1
假设f(n) = A(n)α + B(n)β0 + C(n)β1 + D(n)γ，求解出这个四参数递归式之后。
带入α=1,β0=2,β1=2,γ=2即可。
class Solution {
public int lastRemaining(int n) {
int a, b = 0, c = 0, d;
String binaryN = Integer.toBinaryString(n);
int len = binaryN.length();
a = (int) Math.pow(-2, len - 1);
for (int i = len - 1; i >= 1; i--) {
if (binaryN.charAt(i) == '0') {
b += Math.pow(-2, len - i - 1);
} else {
c += Math.pow(-2, len - i - 1);
}
}
d = (n - a - c) / 4;
return a + 2 * b + 2 * c + 2 * d;
}
}
391. 完美矩形
如果是完美矩形，符合两点要求。
一个是所有小矩形的面积加起来等于大矩形的面积。
还有就是除了大矩形的四个点外，其他所有点都出现偶数次。
class Solution {
public boolean isRectangleCover(int[][] rectangles) {
Map<String, Integer> map = new HashMap<>();
int leftMin = Integer.MAX_VALUE, rightMax = Integer.MIN_VALUE, upMax = Integer.MIN_VALUE, downMin = Integer.MAX_VALUE;
int area = 0;
for (int[] rectangle : rectangles) {
int x1 = rectangle[0], y1 = rectangle[1], x2 = rectangle[2], y2 = rectangle[3];
map.put(x1 + "+" + y1, map.getOrDefault(x1 + "+" + y1, 0) + 1);
map.put(x2 + "+" + y2, map.getOrDefault(x2 + "+" + y2, 0) + 1);
map.put(x1 + "+" + y2, map.getOrDefault(x1 + "+" + y2, 0) + 1);
map.put(x2 + "+" + y1, map.getOrDefault(x2 + "+" + y1, 0) + 1);
leftMin = Math.min(leftMin, x1);
rightMax = Math.max(rightMax, x2);
upMax = Math.max(upMax, y2);
downMin = Math.min(downMin, y1);
area += (y2 - y1) * (x2 - x1);
}
if (area != (rightMax - leftMin) * (upMax - downMin)) {
return false;
}
if (!map.containsKey(leftMin + "+" + downMin)) {
return false;
}
map.put(leftMin + "+" + downMin, map.get(leftMin + "+" + downMin) + 1);
if (!map.containsKey(leftMin + "+" + upMax)) {
return false;
}
map.put(leftMin + "+" + upMax, map.get(leftMin + "+" + upMax) + 1);
if (!map.containsKey(rightMax + "+" + upMax)) {
return false;
}
map.put(rightMax + "+" + upMax, map.get(rightMax + "+" + upMax) + 1);
if (!map.containsKey(rightMax + "+" + downMin)) {
return false;
}
map.put(rightMax + "+" + downMin, map.get(rightMax + "+" + downMin) + 1);
for (String key : map.keySet()) {
if (map.get(key) % 2 != 0) {
return false;
}
}
return true;
}
}
392. 判断子序列
class Solution {
public boolean isSubsequence(String s, String t) {
int index = 0;
for (char c : s.toCharArray()) {
index = t.indexOf(c, index);
if (index == -1) {
return false;
}
index = index + 1;
}
return true;
}
}
393. UTF-8 编码验证
很多容易出错的细节。
UTF-8 中的一个字符可能的长度为 1 到 4 字节，如果num >4直接return false。
如果只有一个字符，那么只要首位为0就行。
可能会有多个UTF-8字符。
如果一个字符到最后超出数组下标了，直接返回false。
class Solution {
public boolean validUtf8(int[] data) {
if (data.length == 0) {
return false;
}
String[] dataStr = new String[data.length];
for (int i = 0; i < data.length; i++) {
dataStr[i] = String.format("%08d", Integer.parseInt(Integer.toBinaryString(data[i])));
}
if (data.length == 1) {
if (dataStr[0].charAt(0) == '0') {
return true;
}
}
int num = 0, index = 0;
while (index < dataStr.length) {
if (dataStr[index].charAt(0) == '0') {
index++;
continue;
}
for (int i = 0; i < dataStr[index].length(); i++) {
if (dataStr[index].charAt(i) == '1') {
num++;
} else {
break;
}
}
if (num == 1 || num > 4) {
return false;
}
for (int i = index + 1; i < index + num; i++) {
if (i >= dataStr.length || dataStr[i].charAt(0) != '1' || dataStr[i].charAt(1) != '0') {
return false;
}
}
index = index + num;
num = 0;
}
return true;
}
}
394. 字符串解码
class Solution {
public String decodeString(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c != ']') {
stack.push(c);
} else {
StringBuilder sb = new StringBuilder();
while (stack.peek() != '[') {
sb.append(stack.pop());
}
stack.pop();
int product = 1, num = 0;
while (!stack.isEmpty() && Character.isDigit(stack.peek())) {
num += (stack.pop() - '0') * product;
product *= 10;
}
String str = sb.toString();
for (int j = 0; j < num - 1; j++) {
sb.append(str);
}
sb.reverse();
str = sb.toString();
for (char ch : str.toCharArray()) {
stack.push(ch);
}
}
}
StringBuilder res = new StringBuilder();
while (!stack.isEmpty()) {
res.append(stack.pop());
}
res.reverse();
return res.toString();
}
}
395. 至少有K个重复字符的最长子串
分治
class Solution {
public int longestSubstring(String s, int k) {
if (s.length() < k) {
return 0;
}
int[] count = new int[26];
for (char c : s.toCharArray()) {
count[c - 'a']++;
}
int index = 0;
while (index < s.length() && count[s.charAt(index) - 'a'] >= k) {
index++;
}
if (index == s.length()) {
return index;
}
int l = longestSubstring(s.substring(0, index), k);
while (index < s.length() && count[s.charAt(index) - 'a'] < k) {
index++;
}
int r = longestSubstring(s.substring(index), k);
return Math.max(l, r);
}
}
396. 旋转函数
先计算出f[0]，然后推出 f(i) = f(i-1) + sum - len * A[len-i]，这样就可以快速求出所有的f(n)，取最大值。
class Solution {
public int maxRotateFunction(int[] A) {
if (A.length == 0) {
return 0;
}
int sum = 0;
int[] f = new int[A.length];
for (int i = 0; i < A.length; i++) {
sum += A[i];
f[0] += i * A[i];
}
int res = f[0];
int len = A.length;
for (int i = 1; i < A.length; i++) {
f[i] = f[i - 1] + sum - len * A[len - i];
res = Math.max(res, f[i]);
}
return res;
}
}
397. 整数替换
class Solution {
private long helper(long n) {
if (n == 1) {
return 0;
}
if (n % 2 == 0) {
return helper(n / 2) + 1;
} else {
return Math.min(helper(n + 1), helper(n - 1)) + 1;
}
}
public int integerReplacement(int n) {
return (int) helper(n);
}
}
398. 随机数索引
蓄水池抽样算法，和 382. 链表随机节点类似。
class Solution {
int[] nums;
Random random;
public Solution(int[] nums) {
this.nums = nums;
this.random = new Random();
}
public int pick(int target) {
int res = -1;
int count = 1;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
if (random.nextInt(count) == 0) {
res = i;
}
count++;
}
}
return res;
}
}
399. 除法求值
先转化成有向图，再用dfs判断
class Solution {
boolean isVisit[];
Map<String, Integer> map = new HashMap<>();//字符在图中的序号
double[][] G;
private double dfs(int start, int end) {
if (start == end) {
return 1;
}
isVisit[start] = true;
for (int i = 0; i < G[start].length; i++) {
if (G[start][i] != 0 && isVisit[i] == false) {
double res = dfs(i, end);
if (res != -1) {
return res * G[start][i];
}
}
}
return -1;
}
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
int count = 0;
for (int i = 0; i < equations.size(); i++) {
String str1 = equations.get(i).get(0);
String str2 = equations.get(i).get(1);
if (!map.containsKey(str1)) {
map.put(str1, count++);
}
if (!map.containsKey(str2)) {
map.put(str2, count++);
}
}
isVisit = new boolean[count];
G = new double[count][count];
for (int i = 0; i < equations.size(); i++) {
int a = map.get(equations.get(i).get(0));
int b = map.get(equations.get(i).get(1));
G[a][b] = values[i];
G[b][a] = 1 / values[i];
}
double[] res = new double[queries.size()];
for (int i = 0; i < queries.size(); i++) {
int start, end;
if (map.containsKey(queries.get(i).get(0)) && map.containsKey(queries.get(i).get(1))) {
start = map.get(queries.get(i).get(0));
end = map.get(queries.get(i).get(1));
} else {
res[i] = -1;
continue;
}
Arrays.fill(isVisit, false);
res[i] = dfs(start, end);
}
return res;
}
}
400. 第N个数字
class Solution {
public int findNthDigit(int n) {
if (n < 10) {
return n;
}
long[] arr = {9, 90, 900, 9000, 90000, 900000, 9000000, 90000000, 900000000};
for (int i = 0; i < arr.length; i++) {
arr[i] = arr[i] * (i + 1);
arr[i] += (i - 1 >= 0) ? arr[i - 1] : 0;
}
int i;
for (i = 0; i < arr.length; i++) {
if (arr[i] > n) {
break;
}
}
int a = (int) (n - arr[i - 1]);//在该数字区间的第几个位置
int b = (int) Math.pow(10, i);//该数字区间的起始数字
int c = (a - 1) / (i + 1);//在该数字区间的第几个数
int d = (a - 1) % (i + 1);//在某个数的第几个位置
int e = b + c;
//System.out.println("a = " + a + ",b = " + b + ",c= " + c + ",d = " + d + ",e = " + e);
return String.valueOf(e).charAt(d) - '0';
}
}
401. 二进制手表
class Solution {
List<String> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
int[] nums = {8, 4, 2, 1, 32, 16, 8, 4, 2, 1};//前四个数代表小时，后六个数代表分钟
private void dfs(int begin, int selected, int num) {
if (selected == num) {
int hour = 0, minute = 0;
for (int index : temp) {
if (index <= 3) {
hour += nums[index];
} else {
minute += nums[index];
}
if (hour > 11) {
return;
}
if (minute > 59) {
return;
}
}
res.add(String.format("%d:%02d", hour, minute));
return;
}
if (begin == 10) {//最多只有10个灯
return;
}
//选
temp.add(begin);
dfs(begin + 1, selected + 1, num);
temp.remove(temp.size() - 1);
//不选
dfs(begin + 1, selected, num);
}
public List<String> readBinaryWatch(int num) {
dfs(0, 0, num);
return res;
}
}
402. 移掉K位数字
class Solution {
public String removeKdigits(String num, int k) {
Deque<Character> deque = new LinkedList<Character>();
int length = num.length();
for (int i = 0; i < length; ++i) {
char digit = num.charAt(i);
while (!deque.isEmpty() && k > 0 && deque.peekLast() > digit) {
deque.pollLast();
k--;
}
deque.offerLast(digit);
}
for (int i = 0; i < k; ++i) {
deque.pollLast();
}
StringBuilder ret = new StringBuilder();
boolean leadingZero = true;
while (!deque.isEmpty()) {
char digit = deque.pollFirst();
if (leadingZero && digit == '0') {
continue;
}
leadingZero = false;
ret.append(digit);
}
return ret.length() == 0 ? "0" : ret.toString();
}
}
403. 青蛙过河
dp[i]代表可以以大小为jumpsize的一跳跳到第i个位置的集合。
边界：
dp[0]的集合只有一个元素0，只需要0跳就可以到达第一个位置。
转移方程：
遍历集合，那么下一跳可以跳的步数为step-1 ~ step+1，判断可以到达的位置是否有石块，如果有，就把那个石块对应的集合增加这一跳的步数。
最后判断最后一个石头的集合是否为空即可。如果不为空，说明可以跳到这里来。
class Solution {
public boolean canCross(int[] stones) {
int len = stones.length;
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < len; i++) {
map.put(stones[i], i);
}
Set<Integer>[] dp = new Set[len];
for (int i = 0; i < len; i++) {
dp[i] = new HashSet<>();
}
dp[0].add(0);
for (int i = 0; i < len; i++) {
for (int j : dp[i]) {
for (int step = j - 1; step <= j + 1; step++) {
if (step > 0 && map.containsKey(stones[i] + step)) {
dp[map.get(stones[i] + step)].add(step);
}
}
}
}
return dp[len - 1].size() > 0;
}
}
改进：
直接用Map<Integer, Set<Integer>> 代表某个位置可以跳到的集合数。
class Solution {
public boolean canCross(int[] stones) {
int len = stones.length;
Map<Integer, Set<Integer>> map = new HashMap<>();
for (int i = 0; i < len; i++) {
map.put(stones[i], new HashSet<>());
}
map.get(0).add(0);
for (int i = 0; i < len; i++) {
for (int j : map.get(stones[i])) {
for (int step = j - 1; step <= j + 1; step++) {
if (step > 0 && map.containsKey(stones[i] + step)) {
map.get(stones[i] + step).add(step);
}
}
}
}
return map.get(stones[len - 1]).size() > 0;
}
}
404. 左叶子之和
class Solution {
int sum = 0;
private void dfs(TreeNode root) {
if (root == null) {
return;
}
if (root.left != null && root.left.left == null && root.left.right == null) {
sum += root.left.val;
}
dfs(root.left);
dfs(root.right);
}
public int sumOfLeftLeaves(TreeNode root) {
dfs(root);
return sum;
}
}
405. 数字转换为十六进制数
class Solution {
public String toHex(int num) {
char[] hex = "0123456789abcdef".toCharArray();
StringBuilder res = new StringBuilder();
while (num != 0) {
int end = num & 15;
res.append(hex[end]);
num >>>= 4;//逻辑右移>>>补0，算数右移>>补符号位
}
if (res.length() == 0) {
return "0";
}
res.reverse();
return res.toString();
}
}
406. 根据身高重建队列
先排序，如果身高不等，按照身高从大到小排序，如果身高相等，按k从小到大排序。
使用List<int[]>记录答案。
由于k值代表排在h前面且身高大于或等于h的人数 ，所以k就是list中 插入的位置。
class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, (o1, o2) -> o1[0] != o2[0] ? -o1[0] + o2[0] : o1[1] - o2[1]);
List<int[]> res = new ArrayList<>();
for (int[] p : people) {
res.add(p[1], p);
}
return res.toArray(new int[res.size()][]);
}
}
407. 接雨水 II
/**
* 把每一个元素称作块。因为那个图片给的好像瓷砖啊。
* 其实做这题一开始都是想的是对于每一个块，去找它四个方向最高的高度中的最小值(二维下则是左右最高的高度取较小的那一个)作为上界，当前块作为下界
但是这4个方向每次遍历复杂度过高，且不能像二维那样去提前预存每个方向的最大值
* 那可以反过来我不以每个块为处理单元，而是以块的四周作为处理单元
* 那如何保证所有四周的可能性都考虑到呢？
我们从矩阵的最外围往里面遍历，像一个圈不断缩小的过程
* 为了防止重复遍历用visited记录
* 其次要用小顶堆(以高度为判断基准)来存入所有快的四周(即圈是不断缩小的，小顶堆存的就是这个圈)
* 为什么要用小顶堆？
这样可以保证高度较小的块先出队
** 为什么要让高度较小的块先出队？(关键点)
1. 一开始时候就讲了基础做法是：对于每一个块，去找它四个方向最高的高度中的最小值(二维下则是左右最高的高度取较小的那一个)作为上界，当前块作为下界
2. 而我们现在反过来不是以中心块为处理单元，而是以四周作为处理单元
3. 我们如果能确保当前出队的元素对于该中心块来说是它周围四个高度中的最小值那么就能确定接雨水的大小
4. 为什么队头元素的高度比中心块要高它就一定是中心块周围四个高度中的最小值呢？
因为我们的前提就是小顶堆：高度小的块先出队，所以对于中心块来说，先出队的必然是中心块四周高度最小的那一个
* 步骤：
1. 构建小顶堆，初始化为矩阵的最外围(边界所有元素)
2. 不断出队，倘若队头元素的四周(队头元素的四周其实就是上面说的中心块，队头元素是中心块的四周高度中最矮的一个)
即代表能够接雨水：队头元素减去该中心块即当前中心块能接雨水的值
3. 但是接完雨水之后中心块还要存进队列中，但这时要存入的中心块是接完雨水后的中心块
*/
class Solution {
int[] dir = {1, 0, -1, 0, 1};
public int trapRainWater(int[][] heightMap) {
Queue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[2] - o2[2]);
int m = heightMap.length;
int n = heightMap[0].length;
boolean[][] vis = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
pq.offer(new int[]{i, j, heightMap[i][j]});
vis[i][j] = true;
}
}
}
int res = 0;
while (!pq.isEmpty()) {
int[] poll = pq.poll();
for (int i = 0; i < 4; i++) {
int nx = poll[0] + dir[i];
int ny = poll[1] + dir[i + 1];
if (nx < 0 || nx == m || ny < 0 || ny == n || vis[nx][ny]) {
continue;
}
if (heightMap[nx][ny] < poll[2]) {
res += poll[2] - heightMap[nx][ny];
}
pq.offer(new int[]{nx, ny, Math.max(heightMap[nx][ny], poll[2])});
vis[nx][ny] = true;
}
}
return res;
}
}
409. 最长回文串
class Solution {
public int longestPalindrome(String s) {
int[] count = new int[52];
for (char c : s.toCharArray()) {
if (Character.isLowerCase(c)) {
count[c - 'a']++;
} else {
count[c - 'A' + 26]++;
}
}
int res = 0;
boolean flag = false;
for (int i = 0; i < 52; i++) {
if (count[i] % 2 == 0) {
res += count[i];
} else {
flag = true;
res += count[i] - 1;
}
}
return flag == true ? res + 1 : res;
}
}
410. 分割数组的最大值
class Solution {
public int splitArray(int[] nums, int m) {
int n = nums.length;
int[][] dp = new int[n + 1][m + 1];
for (int i = 0; i <= n; i++) {
Arrays.fill(dp[i], Integer.MAX_VALUE);
}
int[] sum = new int[n + 1];
for (int i = 0; i < n; i++) {
sum[i + 1] = sum[i] + nums[i];
}
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= Math.min(i, m); j++) {
for (int k = 0; k < i; k++) {
dp[i][j] = Math.min(dp[i][j], Math.max(dp[k][j - 1], sum[i] - sum[k]));
}
}
}
return dp[n][m];
}
}
网友评论