LeetCode 311-340
2020-11-26 本文已影响0人
1nvad3r
312. 戳气球
把nums数组扩充一下，首尾加一个数字1。
dp[i][j]代表开区间(i,j)所能获得硬币的最大数量。
边界：
(i,j)区间长度小于等于2时，能获得的硬币数为0。
转移方程：
遍历开区间内的所有值，记为k,k代表这个开区间(i,j)最后一个戳破的气球。
那么开区间(i,j)的收益就为dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]。
dp[i][j]等于所有的k取收益最大的一个。
区间长度从3开始遍历，直到区间长度达到数组长度。这样才能保证dp数组更新正确。
最后答案就为dp[0][nums.length-1]
class Solution {
public int maxCoins(int[] nums) {
int[] newNums = new int[nums.length + 2];
newNums[0] = newNums[nums.length + 1] = 1;
System.arraycopy(nums, 0, newNums, 1, nums.length);
nums = newNums;
int[][] dp = new int[nums.length][nums.length];
for (int L = 3; L <= nums.length; L++) {
for (int i = 0; i <= nums.length - L; i++) {
int res = 0;
int j = i + L - 1;
for (int k = i + 1; k < j; k++) {
int left = dp[i][k];
int right = dp[k][j];
res = Math.max(res, left + nums[i] * nums[k] * nums[j] + right);
}
dp[i][j] = res;
}
}
return dp[0][nums.length - 1];
}
}
313. 超级丑数
多指针，思想和第264. 丑数 II一样。
pos[j]代表应该用丑数数组uglies中的第几个数去乘以质数数组primes中的第j个数。 初始pos[j]都等于0，每一轮遍历时，都先选出下一个最小的丑数，为了避免重复，需要把所有的uglies[pos[j]] * primes[j] 等于这个丑数的pos[j]进行加1。
class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
int k = primes.length;
int[] uglies = new int[n], pos = new int[k];
uglies[0] = 1;
for (int i = 1; i < n; i++) {
int min = Integer.MAX_VALUE, index = 0;
for (int j = 0; j < k; j++) {
if (uglies[pos[j]] * primes[j] < min) {
min = uglies[pos[j]] * primes[j];
index = j;
}
}
for (int j = 0; j < k; j++) {
if (min == uglies[pos[j]] * primes[j]) {
pos[j]++;
}
}
uglies[i] = min;
}
return uglies[n - 1];
}
}
315. 计算右侧小于当前元素的个数
暴力法，超时：
class Solution {
public List<Integer> countSmaller(int[] nums) {
List<Integer> res = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
int count = 0;
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] < nums[i]) {
count++;
}
}
res.add(count);
}
return res;
}
}
树状数组：
316. 去除重复字母
先使用一个Map记录每一个字符最后出现的位置，使用一个Set记录某个字符是否在栈中。
遍历字符串，如果栈中没有这个字符，将它进栈，但是进栈之前还需要判断一下：
如果栈顶元素比它大，且栈顶元素之后还会出现，那么将栈顶元素出栈，Set中也要移除栈顶元素。
最后把所有元素出栈就是结果的倒序。
class Solution {
public String removeDuplicateLetters(String s) {
Deque<Character> stack = new ArrayDeque<>();
Set<Character> isVisit = new HashSet<>();
Map<Character, Integer> lastPos = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
lastPos.put(s.charAt(i), i);
}
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (!isVisit.contains(c)) {
while (!stack.isEmpty() && c < stack.peek() && lastPos.get(stack.peek()) > i) {
isVisit.remove(stack.pop());
}
isVisit.add(c);
stack.push(c);
}
}
StringBuilder res = new StringBuilder();
while (!stack.isEmpty()) {
res.append(stack.pop());
}
res.reverse();
return res.toString();
}
}
318. 最大单词长度乘积
class Solution {
public int maxProduct(String[] words) {
Arrays.sort(words, (o1, o2) -> o2.length() - o1.length());
int res = 0;
for (int i = 0; i < words.length; i++) {
Set<Character> set = new HashSet<>();
for (char c : words[i].toCharArray()) {
set.add(c);
}
for (int j = i + 1; j < words.length; j++) {
boolean flag = true;
for (char c : words[j].toCharArray()) {
if (set.contains(c)) {
flag = false;
break;
}
}
if (flag == true) {
res = Math.max(res, words[i].length() * words[j].length());
}
}
}
return res;
}
}
319. 灯泡开关
数学题，找规律，只有是完全平方的数最后是亮着的，1到n中完全平方的个数就等于 sqrt(n)向下取整。
class Solution {
public int bulbSwitch(int n) {
return (int)Math.sqrt(n * 1.0);
}
}
322. 零钱兑换
回溯，超时：
class Solution {
int res = Integer.MAX_VALUE;
List<Integer> temp = new ArrayList<>();
private void dfs(int begin, int[] coins, int amount) {
if (begin > coins.length || amount < 0) {
return;
}
if (amount == 0) {
res = Math.min(res, temp.size());
return;
}
for (int i = begin; i < coins.length; i++) {
temp.add(coins[i]);
dfs(i, coins, amount - coins[i]);
temp.remove(temp.size() - 1);
}
}
public int coinChange(int[] coins, int amount) {
Arrays.sort(coins);
int i = 0, j = coins.length - 1;
while (i < j) {
int temp = coins[i];
coins[i] = coins[j];
coins[j] = temp;
i++;
j--;
}
dfs(0, coins, amount);
return res == Integer.MAX_VALUE ? -1 : res;
}
}
动态规划：
dp[i]代表凑出金额为i所需最少的硬币数。 初始都赋为amount+1 ，如果最终dp[i]的值是amount+1，说明无法凑出。
边界:
dp[0] = 0
转移方程：
从所有硬币中选择一个硬币j，只要这个硬币j的金额小于等于i，dp[i]就等于dp[i-coins[j]] + 1。 遍历所有的硬币，dp[i]等于其中最小的那个。
最终答案就是dp[amount]。
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
324. 摆动排序 II
先排序，然后左半部分和右半部分交叉填入结果中，为了保证答案正确，左边每次要先选最大的，右边每次也要先选最大的。
class Solution {
public void wiggleSort(int[] nums) {
Arrays.sort(nums);
int i = (int) Math.ceil(nums.length / 2.0) - 1, j = nums.length - 1;
int[] res = new int[nums.length];
int pos = 0;
while (pos != nums.length) {
res[pos++] = nums[i--];
if (pos == nums.length) {
break;
}
res[pos++] = nums[j--];
}
for (int k = 0; k < nums.length; k++) {
nums[k] = res[k];
}
}
}
326. 3的幂
class Solution {
public boolean isPowerOfThree(int n) {
if (n <= 0) {
return false;
}
while (n % 3 == 0) {
n /= 3;
}
return n == 1;
}
}
327. 区间和的个数
前缀和暴力法：
class Solution {
public int countRangeSum(int[] nums, int lower, int upper) {
long[] pre = new long[nums.length];
int res = 0;
for (int i = 0; i < nums.length; i++) {
pre[i] = (i - 1 >= 0 ? pre[i - 1] : 0) + nums[i];
}
for (int i = 0; i < nums.length; i++) {
for (int j = i; j < nums.length; j++) {
if (pre[j] - (i - 1 >= 0 ? pre[i - 1] : 0) >= lower &&
pre[j] - (i - 1 >= 0 ? pre[i - 1] : 0) <= upper) {
res++;
}
}
}
return res;
}
}
树状数组：
328. 奇偶链表
class Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null) {
return null;
}
ListNode evenHead = head.next;
ListNode curOdd = head, curEven = evenHead;
while (curEven != null && curEven.next != null) {
curOdd.next = curEven.next;
curEven.next = curEven.next.next;
curOdd = curOdd.next;
curEven = curEven.next;
}
curOdd.next = evenHead;
return head;
}
}
329. 矩阵中的最长递增路径
dfs 超时：
class Solution {
int res = 1;
List<Integer> temp = new ArrayList<>();
boolean[][] isVisit;
int[] X = {1, -1, 0, 0}, Y = {0, 0, 1, -1};
private void dfs(int i, int j, int[][] matrix) {
if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length || isVisit[i][j] == true) {
return;
}
if (temp.size() > 0 && matrix[i][j] <= temp.get(temp.size() - 1)) {
res = Math.max(res, temp.size());
return;
}
temp.add(matrix[i][j]);
res = Math.max(res, temp.size());
isVisit[i][j] = true;
for (int k = 0; k < 4; k++) {
int newI = i + X[k], newJ = j + Y[k];
dfs(newI, newJ, matrix);
}
temp.remove(temp.size() - 1);
isVisit[i][j] = false;
}
public int longestIncreasingPath(int[][] matrix) {
if (matrix.length == 0) {
return 0;
}
isVisit = new boolean[matrix.length][matrix[0].length];
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
dfs(i, j, matrix);
}
}
return res;
}
}
记忆化dfs：
class Solution {
int[][] dp;
int[] X = {0, 0, 1, -1}, Y = {1, -1, 0, 0};
private int dfs(int i, int j, int[][] matrix) {
if (dp[i][j] != 0) {
return dp[i][j];
}
dp[i][j]++;
for (int k = 0; k < 4; k++) {
int newI = i + X[k], newJ = j + Y[k];
if (newI >= 0 && newI < matrix.length && newJ >= 0 && newJ < matrix[0].length && matrix[newI][newJ] > matrix[i][j]) {
dp[i][j] = Math.max(dp[i][j], dfs(newI, newJ, matrix) + 1);
}
}
return dp[i][j];
}
public int longestIncreasingPath(int[][] matrix) {
if (matrix.length == 0) {
return 0;
}
int row = matrix.length, col = matrix[0].length;
dp = new int[row][col];
int res = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
res = Math.max(res, dfs(i, j, matrix));
}
}
return res;
}
}
330. 按要求补齐数组
public class Solution {
public int minPatches(int[] nums, int n) {
int res = 0, i = 0;
long miss = 1;
while (miss <= n) {
if (i < nums.length && nums[i] <= miss) {
miss += nums[i++];
} else {
miss += miss;
res++;
}
}
return res;
}
}
331. 验证二叉树的前序序列化
class Solution {
public boolean isValidSerialization(String preorder) {
int slots = 1;
String[] split = preorder.split(",");
for (String s : split) {
slots--;
if (slots < 0) {
return false;
}
if (!"#".equals(s)) {
slots += 2;
}
}
return slots == 0;
}
}
332. 重新安排行程
通过图中所有边恰好一次且行遍所有顶点的通路称为欧拉通路。
通过图中所有边恰好一次且行遍所有顶点的回路称为欧拉回路。
具有欧拉回路的无向图称为欧拉图。
具有欧拉通路但不具有欧拉回路的无向图称为半欧拉图。
本题是欧拉图或半欧拉图。使用优先队列贪心的每次往字典序更小的结点进行dfs，直到没有新的到达为止，就把这个结点加入到结果中。最后的答案是将res反转得到。
class Solution {
Map<String, PriorityQueue<String>> map = new HashMap<String, PriorityQueue<String>>();
List<String> res = new LinkedList<String>();
public List<String> findItinerary(List<List<String>> tickets) {
for (List<String> ticket : tickets) {
String from = ticket.get(0), to = ticket.get(1);
if (!map.containsKey(from)) {
map.put(from, new PriorityQueue<String>());
}
map.get(from).offer(to);
}
dfs("JFK");
Collections.reverse(res);
return res;
}
public void dfs(String curr) {
while (map.containsKey(curr) && map.get(curr).size() > 0) {
String tmp = map.get(curr).poll();
dfs(tmp);
}
res.add(curr);
}
}
334. 递增的三元子序列
a 始终记录最小元素，b 为某个子序列里第二大的数。
接下来不断更新 a，同时保持 b 尽可能的小。
如果下一个元素比 b 大，说明找到了三元组。
class Solution {
public boolean increasingTriplet(int[] nums) {
int a = Integer.MAX_VALUE, b = Integer.MAX_VALUE;
for (int i : nums) {
if (i <= a) {
a = i;
} else if (i <= b) {
b = i;
} else {
return true;
}
}
return false;
}
}
336. 回文对
暴力法，超时：
class Solution {
private boolean isPar(String str) {
if ("".equals(str)) {
return true;
}
int i = 0, j = str.length() - 1;
while (i < j) {
if (str.charAt(i++) != str.charAt(j--)) {
return false;
}
}
return true;
}
public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < words.length; i++) {
for (int j = i + 1; j < words.length; j++) {
if (isPar(words[i] + words[j])) {
res.add(Arrays.asList(i, j));
}
if (isPar(words[j] + words[i])) {
res.add(Arrays.asList(j, i));
}
}
}
return res;
}
}
337. 打家劫舍 III
树形dp：
dp[0]代表偷当前结点的最大金额，dp[1]代表不偷当前结点的最大金额。
采取后序遍历，这样当到达根结点时，就已经知道左右子结点的信息了。
如果不偷当前结点,dp[0]等于左子树的最大金额加上右子树的最大金额。
如果偷当前结点,dp[1]等于当前结点金额加上左子树不偷的金额加上右子树不偷的金额。
class Solution {
private int[] dfs(TreeNode root) {
if (root == null) {
return new int[]{0, 0};
}
int[] left = dfs(root.left);
int[] right = dfs(root.right);
int[] dp = new int[2];
dp[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
dp[1] = left[0] + right[0] + root.val;
return dp;
}
public int rob(TreeNode root) {
int[] res = dfs(root);
return Math.max(res[0], res[1]);
}
}
338. 比特位计数
n & (n-1)能把n中最低位的1变成0，其它位不变。
这样就很快计算出n中1的个数。
class Solution {
public int[] countBits(int num) {
int[] res = new int[num + 1];
for (int i = 0; i <= num; i++) {
res[i] = count(i);
}
return res;
}
private int count(int n) {
int sum = 0;
while (n != 0) {
sum++;
n &= n - 1;
}
return sum;
}
}
