java数据结构刷题练习

class Solution {public boolean containsDuplicate(int[] nums) {Arrays.sort(nums);for(int i=1;i<nums.length;i++){if(nums[i-1]==nums[i])return true;}return false;
}
}作者：affectionate-albattani7tn
链接：https://leetcode.cn/problems/contains-duplicate/solution/pai-xu-xun-huan-by-affectionate-albattan-bvdp/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：

输入：nums = [1]
输出：1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-subarray
著作权归领扣网

class Solution {public int maxSubArray(int[] nums) {int ans = nums[0];int sum = 0;for(int num: nums) {if(sum > 0) {sum += num;} else {sum = num;}ans = Math.max(ans, sum);}return ans;}
}作者：guanpengchn
链接：https://leetcode.cn/problems/maximum-subarray/solution/hua-jie-suan-fa-53-zui-da-zi-xu-he-by-guanpengchn/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

络所有。商业转载

class Solution {（优化见下面）public int maxSubArray(int[] nums) {int ans = nums[0]; // 记录当前最大子序和int cur = nums[0]; // 记录当前连续子序列的和for (int i = 1; i < nums.length; i++) {if (nums[i] <= 0 && cur <= 0)cur = nums[i]; // 如果当前元素小于等于 0，且前面的连续子序列的和也小于等于 0，则以当前元素更新连续子序列的起点else if (nums[i] <= 0)cur = cur + nums[i]; // 如果当前元素小于等于 0，但前面的连续子序列的和大于 0，则将当前元素加入连续子序列中，因为加入后整体变大else if (nums[i] >= 0 && cur <= 0)cur = nums[i]; // 如果当前元素大于 0，且前面的连续子序列的和小于等于 0，则以当前元素更新连续子序列的起点else if (nums[i] >= 0 )cur = nums[i] + cur; // 如果当前元素大于 0，且前面的连续子序列的和也大于 0，则将当前元素加入连续子序列中，加入后更大ans = Math.max(cur,ans); // 更新当前最大子序和}return ans; // 返回当前最大子序和}
}作者：eyi-gu-bi-gu-e
链接：https://leetcode.cn/problems/maximum-subarray/solution/yi-yan-kan-dong-you-qian-ru-shen-by-eyi-sr9nn/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

请联系官方授权，非商业转载请注明出处。

题目3

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]
 

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

public class Solution {public int[] twoSum(int[] nums, int target) {int key;for (int i = 1; i < nums.length; ++i) {key = target - nums[i];//求出值for (int j = 0; j < i; ++j) {//在之前数组中找是否有该值，如果有就找到这二个数if (nums[j] == key) return new int[]{i, j};}}return null;}
}作者：jiang-cu-san-wen-yu
链接：https://leetcode.cn/problems/two-sum/solution/liang-shu-zhi-he-bao-li-mei-ju-ha-xi-bia-vtce/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
解法二
class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> map = new HashMap<Integer, Integer>();for (int i = 0; i < nums.length; ++i) {if (map.containsKey(target - nums[i])) {return new int[]{map.get(target - nums[i]), i};}map.put(nums[i], i);}return null;}
}作者：jiang-cu-san-wen-yu
链接：https://leetcode.cn/problems/two-sum/solution/liang-shu-zhi-he-bao-li-mei-ju-ha-xi-bia-vtce/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

题目四

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。
示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
 

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/merge-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

public void merge(int[] nums1, int m, int[] nums2, int n) {/* 双指针利用nums1和nums2已经升序排列的，每次从两个数组第一个元素取出较小的放入结果数组时间复杂度O(m+n),指针需要移动m+n次，空间复杂度O(m+n),需要建立一个新数组存储，最后再把结果赋值到nums1 */int p1 = 0;int p2 = 0;int[] sorted = new int[m+n];int cur;while (p1 < m || p2 < n) {if (p1 == m) {// 如果p1已经走完，后续的cur都是nums2的元素cur = nums2[p2++];} else if (p2 == n) {// 如果p2已经走完，后续的cur都是nums1的元素cur = nums1[p1++];} else if (nums1[p1] < nums2[p2]) {// 如果p1 p2都没走完，cur为两者较小的值cur = nums1[p1++];} else {// 如果p1 p2都没走完，cur为两者较小的值cur = nums2[p2++];}// 将cur赋值给排序结果值对应的下标元素，注意这里的-1和上面的p1++ p2++sorted[p1 + p2 - 1] = cur;}// 额外的空间重新赋值给nums1for (int i = 0; i < m + n; i++) {nums1[i] = sorted[i];}
}作者：s1amduncan
链接：https://leetcode.cn/problems/merge-sorted-array/solution/he-bing-liang-ge-you-xu-shu-zu-by-s1amdu-xfeq/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
解法二
public void merge(int[] nums1, int m, int[] nums2, int n) {// 逆向双指针，上述双指针之所以用临时变量，是因为如果直接合并到nums1中，从前往后，// 但是实际nums1后半部分是空的0占位，// 直接覆盖不会影响结果，因此指针可以设置从后往前遍历，每次取两则较大值放入nums1的后面，// 时间复杂度O(m+n),指针移动单调递减最多移动m+n次，空间复杂度O(1)，直接对nums1原址修改,不需要额外的空间int p1 = m - 1; // nums1的指针起始位置int p2 = n - 1; // nums2的指针起始位置int tail = m + n - 1; // 合并后的nums1的指针起始位置int cur; // 当前指针需要赋值的元素// 如果p1或p2没有往前走到头，则不断循环while (p1 >= 0 || p2 >= 0) {if (p1 == -1) {// 如果nums1的指针走到头，即nums1的元素都已经取出cur = nums2[p2--];} else if (p2 == -1) {// 如果nums2的指针走到头，即nums2的元素都已经取出cur = nums1[p1--];} else if (nums1[p1] > nums2[p2]) {// nums1和nums2都没取完，选择两个较大的加入到tailcur = nums1[p1--];} else {// nums1和nums2都没取完，选择两个较大的加入到tailcur = nums2[p2--];}// 将当前cur值赋值给tail后,tail往前移动一位nums1[tail--] = cur;}
}作者：s1amduncan
链接：https://leetcode.cn/problems/merge-sorted-array/solution/he-bing-liang-ge-you-xu-shu-zu-by-s1amdu-xfeq/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

题目5

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
示例 2:

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/intersection-of-two-arrays-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {public int[] intersect(int[] nums1, int[] nums2) {Arrays.sort(nums1);Arrays.sort(nums2);int i=0,j=0,k=0;int[] temp = new int[nums1.length];while(i<nums1.length && j<nums2.length){if(nums1[i]==nums2[j]){temp[k++] = nums1[i];i++;j++;}else if(nums1[i]<nums2[j]){i++;}else{j++;}}int[] result = new int[k];for(int m=0; m<k; m++){result[m] = temp[m];}return result;}
}作者：charming-shternrsa
链接：https://leetcode.cn/problems/intersection-of-two-arrays-ii/solution/350liang-ge-shu-zu-de-jiao-ji-ii-by-char-hhg4/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
解法二
class Solution {public int[] intersect(int[] nums1, int[] nums2) {// 数组法int[] cnt = new int[1005];List<Integer> ansList = new ArrayList<>();for (int n : nums1) {cnt[n]++;}for (int n : nums2) {if (cnt[n] > 0) {ansList.add(n);cnt[n]--;}}int[] ans = new int[ ansList.size()];for (int i = 0; i < ansList.size(); i++) {ans[i] = ansList.get(i);}return ans;}
}作者：JSJohnsonJS
链接：https://leetcode.cn/problems/intersection-of-two-arrays-ii/solution/gen-ju-xian-zhi-tiao-jian-ding-yi-shu-zu-8hf8/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

题目6

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
 

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock
著作权归

public int maxProfit(int[] prices) {// 在第j天卖出，维护一个第1天到j-1天里面的最小值作为买入// 然后每能够卖出的一天用当天价格-前面买入最小值作为利润，一直扫描下直到结束我们获取最大的利润值int minPrice = prices[0];  // 初始化最小的买入为第一天的价格int maxProfit = 0;// 一遍扫描，扫描里面同步判断更新当前最小买入和最大利润，从1开始即可，因为0的哪天已经赋值给minPrice初始值了for (int i = 1; i < prices.length; i++) {// 如果当前价格比minPrice还要小，那么就调整最小买入值为当前价格if (prices[i] < minPrice) {minPrice = prices[i];// 否则计算当前卖出的话是否比最大利润打，如果大则更新最大利润} else if (prices[i] - minPrice > maxProfit) {maxProfit = prices[i] - minPrice;}}return maxProfit;
}作者：s1amduncan
链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/solution/mai-mai-gu-piao-de-zui-jia-shi-ji-by-s1a-q95w/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
解法二class Solution {public int maxProfit(int[] prices) {int buy = 0;int max = 0;//走到购买不会亏的那一天，也就是下一个数字比当前数字大的那一天while(buy < prices.length - 1 && prices[buy + 1] < prices[buy]){buy++;}//若走到头，说明序列非递增，比可能赚钱。if(buy == prices.length - 1){return max;}//直接从能赚钱的后一天开始遍历for(int sell = buy + 1; sell < prices.length; sell++){//如果走到了一个更加小的买入点，直接保存该买入点if(prices[sell] - prices[buy] <= 0){buy = sell;continue;}//否则计算当前买入点和卖出点的差价max = Math.max(max,prices[sell] - prices[buy]);}return max;}
}作者：hydogdog
链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/solution/jian-dan-yi-dong-de-shuang-zhi-zhen-by-h-qfkp/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。