LeetCode283 移动零
题目详情
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
提示:
1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1
代码
public class LeetCode283 {
public static void main(String[] args) {
int[] nums1 = {0, 1, 0, 3, 12};
new Solution().moveZeroes(nums1);
System.out.println(Arrays.toString(nums1));
int[] nums2 = {0, 1, 0, 3, 12};
new Solution().moveZeroes2(nums2);
System.out.println(Arrays.toString(nums2));
}
static class Solution {
/*
自己写的，利用队列，存储为0的下标
*/
public void moveZeroes(int[] nums) {
if (nums == null || nums.length < 2) {
return;
}
Queue<Integer> zeroQueue = new LinkedList<Integer>();
int i = 0;
while (i < nums.length) {
if (nums[i] == 0) {
zeroQueue.offer(i);
} else {
if (!zeroQueue.isEmpty()) {
int j = zeroQueue.poll();
nums[j] = nums[i];
nums[i] = 0;
//这个不要忘记
zeroQueue.offer(i);
}
}
i++;
}
}
/*
双指针
左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。
右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交互，同时左指针右移。
注意以下性质；
1，左指针左边均为非零数
2，右指针左边直到左边指针均为0
因此每次交换，都是将左指针的0与右指针的非零数交换，且非零数的相对顺序并未改变。
*/
public void moveZeroes2(int[] nums) {
int n = nums.length, left = 0, right = 0;
while (right < n) {
if (nums[right] != 0) {
swap(nums, left, right);
left++;
}
right++;
}
}
/*
* 交换数组 arr 中下标为 i 和下标为 j 位置的元素
*/
public void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
LeetCode287 寻找重复数
题目详情
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
示例 1：
输入：nums = [1,3,4,2,2]
输出：2
示例 2：
输入：nums = [3,1,3,4,2]
输出：3
提示：
1 <= n <= 105
nums.length == n + 1
1 <= nums[i] <= n
nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次
进阶：
如何证明 nums 中至少存在一个重复的数字?
你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？
代码
public class LeetCode287 {
public static void main(String[] args) {
int[] nums = {1, 3, 4, 2, 2};
System.out.println(new Solution().findDuplicate(nums));
System.out.println(new Solution().findDuplicate2(nums));
System.out.println(new Solution().findDuplicate3(nums));
}
static class Solution {
/*
快慢指针
*/
public int findDuplicate(int[] nums) {
int slow = 0, fast = 0;
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
slow = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
/*
排序
*/
public int findDuplicate2(int[] nums) {
Arrays.sort(nums);
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1]) {
return nums[i];
}
}
return -1;
}
/*
循环遍历
*/
public int findDuplicate3(int[] nums) {
int n = nums.length;
int l = 1, r = n - 1, ans = -1;
while (l <= r) {
int mid = (l + r) >> 1;
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (nums[i] <= mid) {
cnt++;
}
}
if (cnt <= mid) {
l = mid + 1;
} else {
r = mid - 1;
ans = mid;
}
}
return ans;
}
}
}
LeetCode297 二叉树的序列化和反序列化
题目详情
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
示例 1：
输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[1,2]
提示：
树中结点数在范围 [0, 104] 内
-1000 <= Node.val <= 1000
代码
public class LeetCode297 {
public static void main(String[] args) {
TreeNode.prettyPrintTree(new Codec().deserialize("1,2,3,4,5"));
}
static class Codec {
public String serialize(TreeNode root) {
return rserialize(root, "");
}
public TreeNode deserialize(String data) {
String[] data_array = data.split(",");
List<String> data_list = new LinkedList<String>(Arrays.asList(data_array));
return rdeserialize(data_list);
}
public String rserialize(TreeNode root, String str) {
if (root == null) {
str += "None,";
} else {
str += str.valueOf(root.val) + ",";
str = rserialize(root.left, str);
str = rserialize(root.right, str);
}
return str;
}
public TreeNode rdeserialize(List<String> l) {
if (l.get(0).equals("None")) {
l.remove(0);
return null;
}
TreeNode root = new TreeNode(Integer.valueOf(l.get(0)));
l.remove(0);
root.left = rdeserialize(l);
root.right = rdeserialize(l);
return root;
}
}
}
LeetCode300 最长递增子序列
题目详情
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
提示：
1 <= nums.length <= 2500
-104 <= nums[i] <= 104
进阶：
你能将算法的时间复杂度降低到 O(n log(n)) 吗?
代码
class LeetCode300 {
public static void main(String[] args) {
System.out.println(new Solution1().lengthOfLIS(new int[]{3, 5, 6, 2, 5, 4, 19, 5, 6, 7, 12}));
System.out.println(new Solution2().lengthOfLIS(new int[]{3, 5, 6, 2, 5, 4, 19, 5, 6, 7, 12}));
}
/*
方法一：动态规划
*/
static class Solution1 {
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
dp[0] = 1;
int maxans = 1;
for (int i = 1; i < dp.length; i++) {
int maxval = 0;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
maxval = Math.max(maxval, dp[j]);
}
}
dp[i] = maxval + 1;
maxans = Math.max(maxans, dp[i]);
}
return maxans;
}
}
static class Solution2 {
public int lengthOfLIS(int[] nums) {
int len = nums.length;
if (len <= 1) {
return len;
}
// tail 数组的定义：长度为 i + 1 的上升子序列的末尾最小是几
int[] tail = new int[len];
// 遍历第 1 个数，直接放在有序数组 tail 的开头
tail[0] = nums[0];
// end 表示有序数组 tail 的最后一个已经赋值元素的索引
int end = 0;
for (int i = 1; i < len; i++) {
// 【逻辑 1】比 tail 数组实际有效的末尾的那个元素还大
if (nums[i] > tail[end]) {
// 直接添加在那个元素的后面，所以 end 先加 1
end++;
tail[end] = nums[i];
} else {
// 使用二分查找法，在有序数组 tail 中
// 找到第 1 个大于等于 nums[i] 的元素，尝试让那个元素更小
int left = 0;
int right = end;
while (left < right) {
// 选左中位数不是偶然，而是有原因的，原因请见 LeetCode 第 35 题题解
// int mid = left + (right - left) / 2;
int mid = left + ((right - left) >>> 1);
if (tail[mid] < nums[i]) {
// 中位数肯定不是要找的数，把它写在分支的前面
left = mid + 1;
} else {
right = mid;
}
}
// 走到这里是因为 【逻辑 1】 的反面，因此一定能找到第 1 个大于等于 nums[i] 的元素
// 因此，无需再单独判断
tail[left] = nums[i];
}
// 调试方法
// printArray(nums[i], tail);
}
// 此时 end 是有序数组 tail 最后一个元素的索引
// 题目要求返回的是长度，因此 +1 后返回
end++;
return end;
}
// 调试方法，以观察是否运行正确
private void printArray(int num, int[] tail) {
System.out.print("当前数字：" + num);
System.out.print("\t当前 tail 数组：");
int len = tail.length;
for (int i = 0; i < len; i++) {
if (tail[i] == 0) {
break;
}
System.out.print(tail[i] + ", ");
}
System.out.println();
}
}
}
LeetCode301
题目详情
给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
示例 1：
输入：s = "()())()"
输出：["(())()","()()()"]
示例 2：
输入：s = "(a)())()"
输出：["(a())()","(a)()()"]
示例 3：
输入：s = ")("
输出：[""]
提示：
1 <= s.length <= 25
s 由小写英文字母以及括号 '(' 和 ')' 组成
s 中至多含 20 个括号
代码
public class LeetCode301 {
public static void main(String[] args) {
System.out.println(new Solution().removeInvalidParentheses("(a)())()"));
}
/*
回溯+剪枝
*/
static class Solution {
private List<String> res = new ArrayList<String>();
public List<String> removeInvalidParentheses(String s) {
int lremove = 0;
int rremove = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
lremove++;
} else if (s.charAt(i) == ')') {
if (lremove == 0) {
rremove++;
} else {
lremove--;
}
}
}
helper(s, 0, lremove, rremove);
return res;
}
private void helper(String str, int start, int lremove, int rremove) {
if (lremove == 0 && rremove == 0) {
if (isValid(str)) {
res.add(str);
}
return;
}
for (int i = start; i < str.length(); i++) {
if (i != start && str.charAt(i) == str.charAt(i - 1)) {
continue;
}
// 如果剩余的字符无法满足去掉的数量要求，直接返回
if (lremove + rremove > str.length() - i) {
return;
}
// 尝试去掉一个左括号
if (lremove > 0 && str.charAt(i) == '(') {
helper(str.substring(0, i) + str.substring(i + 1), i, lremove - 1, rremove);
}
// 尝试去掉一个右括号
if (rremove > 0 && str.charAt(i) == ')') {
helper(str.substring(0, i) + str.substring(i + 1), i, lremove, rremove - 1);
}
}
}
private boolean isValid(String str) {
int cnt = 0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '(') {
cnt++;
} else if (str.charAt(i) == ')') {
cnt--;
if (cnt < 0) {
return false;
}
}
}
return cnt == 0;
}
}
}
LeetCode309 最佳买卖股票时机含冷冻期
题目详情
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:
输入: prices = [1]
输出: 0
提示：
1 <= prices.length <= 5000
0 <= prices[i] <= 1000
代码
class LeetCode309 {
public static void main(String[] args) {
System.out.println(new Solution().maxProfit(new int[]{1, 2, 3, 0, 2}));
System.out.println(new Solution2().maxProfit(new int[]{1, 2, 3, 0, 2}));
}
/*
动态规划
*/
static class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
if (len < 2) return 0;
//0表示本不持有，1表示持有，2表示当天卖出，不持有
int[][] dp = new int[len][3]; //用二维数组记录当天各种情况的最优解(收益的最大值)
dp[0][1] = -prices[0]; //第一天若持有，则收益为负；不持有则收益为零
for (int i = 1; i < len; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2]); //当天的本不持有可以由前一天本不持有或前一天卖出得到
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]); //当天的持有可以由前一天的持有或前一天的本不持有-当天的股票价格得到, 即买进一只股票
dp[i][2] = dp[i - 1][1] + prices[i]; //当天卖出可以由前一天的持有+当天的股票价格得到, 即卖出手中的股票
}
return Math.max(dp[len - 1][0], dp[len - 1][2]); //返回最后一天不持有股票的状态，此处可以得到收益的最大值
}
}
static class Solution2 {
public int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;
}
int n = prices.length;
int f0 = -prices[0];
int f1 = 0;
int f2 = 0;
for (int i = 1; i < n; ++i) {
int newf0 = Math.max(f0, f2 - prices[i]);
int newf1 = f0 + prices[i];
int newf2 = Math.max(f1, f2);
f0 = newf0;
f1 = newf1;
f2 = newf2;
}
return Math.max(f1, f2);
}
}
}
LeetCode312 戳气球
题目详情
有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
求所能获得硬币的最大数量。
示例 1：
输入：nums = [3,1,5,8]
输出：167
解释：
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 315 + 358 + 138 + 181 = 167
示例 2：
输入：nums = [1,5]
输出：10
提示：
n == nums.length
1 <= n <= 300
0 <= nums[i] <= 100
代码
class Solution {
public int maxCoins(int[] nums) {
int n = nums.length;
int[][] rec = new int[n + 2][n + 2];
int[] val = new int[n + 2];
val[0] = val[n + 1] = 1;
for (int i = 1; i <= n; i++) {
val[i] = nums[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
for (int j = i + 2; j <= n + 1; j++) {
for (int k = i + 1; k < j; k++) {
int sum = val[i] * val[k] * val[j];
sum += rec[i][k] + rec[k][j];
rec[i][j] = Math.max(rec[i][j], sum);
}
}
}
return rec[0][n + 1];
}
}
LeetCode322 零钱兑换
题目详情
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
提示：
1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104
代码
class LeetCode322 {
public static void main(String[] args) {
System.out.println(new Solution1().coinChange(new int[]{1, 2, 5}, 11));
System.out.println(new Solution2().coinChange(new int[]{1, 2, 5}, 11));
System.out.println(new Solution3().coinChange(new int[]{1, 2, 5}, 11));
}
/*
方法一、搜索回溯 [超出时间限制]
*/
static class Solution1 {
public int coinChange(int[] coins, int amount) {
return coinChange(0, coins, amount);
}
private int coinChange(int idxCoin, int[] coins, int amount) {
if (amount == 0)
return 0;
if (idxCoin < coins.length && amount > 0) {
int maxVal = amount / coins[idxCoin];
int minCost = Integer.MAX_VALUE;
for (int x = 0; x <= maxVal; x++) {
if (amount >= x * coins[idxCoin]) {
int res = coinChange(idxCoin + 1, coins, amount - x * coins[idxCoin]);
if (res != -1)
minCost = Math.min(minCost, res + x);
}
}
return (minCost == Integer.MAX_VALUE) ? -1 : minCost;
}
return -1;
}
}
/*
方法二、动态规划-自上而下 [通过]
*/
static class Solution2 {
public int coinChange(int[] coins, int amount) {
if (amount < 1) return 0;
return coinChange(coins, amount, new int[amount]);
}
private int coinChange(int[] coins, int rem, int[] count) {
if (rem < 0) return -1;
if (rem == 0) return 0;
if (count[rem - 1] != 0) return count[rem - 1];
int min = Integer.MAX_VALUE;
for (int coin : coins) {
int res = coinChange(coins, rem - coin, count);
if (res >= 0 && res < min)
min = 1 + res;
}
count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
return count[rem - 1];
}
}
/*
方法三、动态规划：自下而上 [通过]
*/
static class Solution3 {
public int coinChange(int[] coins, int amount) {
int max = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, max);
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];
}
}
}
LeetCode337
题目详情
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
示例 1:
输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
示例 2:
输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9
提示：
树的节点数在 [1, 104] 范围内
0 <= Node.val <= 104
代码
public class LeetCode337 {
public static void main(String[] args) {
System.out.println(new Solution().rob(TreeNode.buildBinaryTree(new Integer[]{3, 2, 3, null, 3, null, 1})));
System.out.println(new Solution2().rob(TreeNode.buildBinaryTree(new Integer[]{3, 2, 3, null, 3, null, 1})));
System.out.println(new Solution3().rob(TreeNode.buildBinaryTree(new Integer[]{3, 2, 3, null, 3, null, 1})));
}
static class Solution {
public int rob(TreeNode root) {
if (root == null) return 0;
int money = root.val;
if (root.left != null) {
money += (rob(root.left.left) + rob(root.left.right));
}
if (root.right != null) {
money += (rob(root.right.left) + rob(root.right.right));
}
return Math.max(money, rob(root.left) + rob(root.right));
}
}
static class Solution2 {
public int rob(TreeNode root) {
HashMap<TreeNode, Integer> memo = new HashMap<>();
return robInternal(root, memo);
}
public int robInternal(TreeNode root, HashMap<TreeNode, Integer> memo) {
if (root == null) return 0;
if (memo.containsKey(root)) return memo.get(root);
int money = root.val;
if (root.left != null) {
money += (robInternal(root.left.left, memo) + robInternal(root.left.right, memo));
}
if (root.right != null) {
money += (robInternal(root.right.left, memo) + robInternal(root.right.right, memo));
}
int result = Math.max(money, robInternal(root.left, memo) + robInternal(root.right, memo));
memo.put(root, result);
return result;
}
}
static class Solution3 {
public int rob(TreeNode root) {
int[] result = robInternal(root);
return Math.max(result[0], result[1]);
}
public int[] robInternal(TreeNode root) {
if (root == null) return new int[2];
int[] result = new int[2];
int[] left = robInternal(root.left);
int[] right = robInternal(root.right);
result[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
result[1] = left[0] + right[0] + root.val;
return result;
}
}
}
LeetCode
题目详情
给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
示例 1：
输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10
示例 2：
输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
提示：
0 <= n <= 105
进阶：
很容易就能实现时间复杂度为 O(n log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？
你能不使用任何内置函数解决此问题吗？（如，C++ 中的 __builtin_popcount ）
代码
public class LeetCode338 {
public static void main(String[] args) {
System.out.println(Arrays.toString(new Solution().countBits(3)));
System.out.println(Arrays.toString(new Solution2().countBits(3)));
System.out.println(Arrays.toString(new Solution3().countBits(3)));
System.out.println(Arrays.toString(new Solution4().countBits(3)));
}
/*
动态规划-最高有效位
*/
static class Solution {
public int[] countBits(int n) {
int[] bits = new int[n + 1];
int highBit = 0;
for (int i = 1; i <= n; i++) {
if ((i & (i - 1)) == 0) {
highBit = i;
}
bits[i] = bits[i - highBit] + 1;
}
return bits;
}
}
static class Solution2 {
public int[] countBits(int n) {
int[] bits = new int[n + 1];
for (int i = 1; i <= n; i++) {
bits[i] = bits[i >> 1] + (i & 1);
}
return bits;
}
}
static class Solution3 {
public int[] countBits(int n) {
int[] bits = new int[n + 1];
for (int i = 1; i <= n; i++) {
bits[i] = bits[i & (i - 1)] + 1;
}
return bits;
}
}
static class Solution4 {
public int[] countBits(int num) {
int[] ans = new int[num + 1];
int i = 0, b = 1;
// [0, b) 被计算
while (b <= num) {
// 从 [0, b) 生成 [b, 2b) 或 [b, num)
while (i < b && i + b <= num) {
ans[i + b] = ans[i] + 1;
++i;
}
i = 0; // 重置 i
b <<= 1; // b = 2b
}
return ans;
}
}
}
网友评论