LeetCode热题100（三）

LeetCode热题100（三）

108. 将有序数组转换为二叉搜索树

题目详情

https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/

解答过程

并没有想出来解题思路，看了官方答案，重要信息是二叉搜索树的中序遍历是升序序列，所以数组的中间节点就是根节点

publicTreeNodesortedArrayToBST(int[]nums){returnbuildNode(nums,0,nums.length-1);}publicTreeNodebuildNode(int[]nums,intleft,intright){if(left>right){returnnull;}intmid=(left+right)/2;TreeNodenode=newTreeNode(nums[mid]);node.left=buildNode(nums,left,mid-1);node.right=buildNode(nums,mid+1,right);returnnode;}

35. 搜索插入位置

题目详情

https://leetcode.cn/problems/search-insert-position/

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为O(log n)的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5 输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2 输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7 输出: 4

解答过程

看到题目思路是不断移动左右指针确定最终的插入位置，但是解答后耗时很长，并且答案很复杂

publicintsearchInsert(int[]nums,inttarget){intleft=0;intright=nums.length-1;intmid=left;if(nums[left]>=target){return0;}if(nums[right]<target){returnnums.length;}while(left<right){mid=(left+right)/2;System.out.println(left+" "+mid+" "+right);if(nums[mid]<target){left=mid;}elseif(nums[mid]>target){right=mid;}else{returnmid;}if(left+1==right){returnright;}}returnmid;}

看了官方的示例感觉确实写的啰嗦了，核心是每次移动指针的时候使用mid+1-1

publicintsearchInsert(int[]nums,inttarget){intleft=0;intright=nums.length-1;while(left<=right){intmid=(left+right)/2;if(nums[mid]<target){left=mid+1;}elseif(nums[mid]>target){right=mid-1;}else{returnmid;}}returnleft;}

20. 有效的括号

题目详情

https://leetcode.cn/problems/valid-parentheses/

给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

**输入：**s = “()”

**输出：**true

示例 2：

**输入：**s = “()[]{}”

**输出：**true

示例 3：

**输入：**s = “(]”

**输出：**false

示例 4：

**输入：**s = “([])”

**输出：**true

示例 5：

**输入：**s = “([)]”

**输出：**false

解答过程

看到题目感觉需要用栈来处理，但是忽略了只输入[或者]

publicbooleanisValid(Strings){Stack<Character>stack=newStack<>();char[]chars=s.toCharArray();for(charc:chars){if(c=='('||c=='['||c=='{'){stack.push(c);}else{if(stack.isEmpty()){returnfalse;}Characterpc=stack.pop();if(pc=='('&&c!=')'){returnfalse;}if(pc=='['&&c!=']'){returnfalse;}if(pc=='{'&&c!='}'){returnfalse;}}}returnstack.isEmpty();}

121. 买卖股票的最佳时机

题目详情

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/

给定一个数组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。

解答过程

第一想法是两次for循环去寻找差值最大的数字，但是在数组元素过多的时候超时

publicintmaxProfit(int[]prices){intresult=0;for(inti=0;i<prices.length;i++){for(intj=i+1;j<prices.length;j++){result=Math.max(result,prices[j]-prices[i]);}}returnresult;}

看了官方的解答发现很巧妙，如果我是在历史最低点买进的，那么我今天卖出能赚多少钱？当考虑完所有天数之时，我们就得到了最好的答案。

publicintmaxProfit(int[]prices){intresult=0;intmin=Integer.MAX_VALUE;for(intprice:prices){if(price<min){min=price;}else{result=Math.max(result,price-min);}}returnresult;}

70. 爬楼梯

题目详情

https://leetcode.cn/problems/climbing-stairs/

假设你正在爬楼梯。需要n阶你才能到达楼顶。

每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶

示例 2：

输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶

解答过程

直接看题目并没有想出来解法，看了评论区的解题思路蔡锷出来，核心是第n阶台阶的上法是第n-1解法+第n-2解法

publicintclimbStairs(intn){inta=0;intb=1;intsum=0;for(inti=0;i<n;i++){sum=a+b;a=b;b=sum;}returnsum;}

评论区大神

118. 杨辉三角

题目详情

https://leetcode.cn/problems/pascals-triangle/

解答过程

杨辉三角每一行的两端一定是1除却两端其他的内容为上一行中num[i-1]+num[i]

publicList<List<Integer>>generate(intnumRows){List<List<Integer>>lists=newArrayList<>();ArrayList<Integer>arr=newArrayList<>(Collections.singletonList(1));lists.add(arr);for(inti=2;i<=numRows;i++){ArrayList<Integer>arrn=newArrayList<>();for(intj=0;j<i;j++){if(j==0||j==i-1){arrn.add(1);}else{arrn.add(lists.get(i-2).get(j-1)+lists.get(i-2).get(j));}}lists.add(arrn);}returnlists;}

看了解答过程，确实可以继续优化

publicList<List<Integer>>generate(intnumRows){List<List<Integer>>lists=newArrayList<>();for(inti=1;i<=numRows;i++){List<Integer>arr=newArrayList<>();for(intj=0;j<i;j++){if(j==0||j==i-1){arr.add(1);}else{arr.add(lists.get(i-2).get(j-1)+lists.get(i-2).get(j));}}lists.add(arr);}returnlists;}

136. 只出现一次的数字

题目详情

https://leetcode.cn/problems/single-number/

给你一个非空整数数组nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

**输入：**nums = [2,2,1]

**输出：**1

示例 2 ：

**输入：**nums = [4,1,2,1,2]

**输出：**4

示例 3 ：

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

**输出：**1

解答过程

第一反应是hashmap去统计数字出现次数，最后遍历hashmap

publicintsingleNumber(int[]nums){HashMap<Integer,Integer>hashMap=newHashMap<>();for(intnum:nums){hashMap.put(num,hashMap.getOrDefault(num,0)+1);}for(Map.Entry<Integer,Integer>entry:hashMap.entrySet()){if(entry.getValue()==1){returnentry.getKey();}}return-1;}

169. 多数元素

题目详情

https://leetcode.cn/problems/majority-element/

给定一个大小为n的数组nums，返回其中的多数元素。多数元素是指在数组中出现次数大于⌊ n/2 ⌋的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：nums = [3,2,3] 输出：3

示例 2：

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

解答过程

publicintmajorityElement(int[]nums){HashMap<Integer,Integer>hashMap=newHashMap<>();for(intnum:nums){intval=hashMap.getOrDefault(num,0)+1;if(val>nums.length/2){returnnum;}hashMap.put(num,val);}return-1;}

53. 最大子数组和

题目详情

https://leetcode.cn/problems/maximum-subarray/

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [5,4,-1,7,8] 输出：23

解答过程

publicintmaxSubArray(int[]nums){intpreMax=0;intglobalMax=nums[0];for(intnum:nums){preMax=Math.max(preMax+num,num);globalMax=Math.max(globalMax,preMax);}returnglobalMax;}

56. 合并区间

题目详情

https://leetcode.cn/problems/merge-intervals/

以数组intervals表示若干个区间的集合，其中单个区间为intervals[i] = [starti, endi]。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]] 输出：[[1,5]] 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

示例 3：

输入：intervals = [[4,7],[1,4]] 输出：[[1,7]] 解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。

解答过程

首先需要对二元数组进行排序，然后尝试合并区间，使用start <= interval[1] && end >= interval[0]可以判断两个区间有没有交集

publicint[][]merge(int[][]intervals){Arrays.sort(intervals,newComparator<int[]>(){@Overridepublicintcompare(int[]o1,int[]o2){returno1[0]-o2[0];}});ArrayList<int[]>ints=newArrayList<>();intstart=intervals[0][0];intend=intervals[0][1];for(inti=1;i<intervals.length;i++){int[]interval=intervals[i];if(start<=interval[1]&&end>=interval[0]){start=Math.min(start,interval[0]);end=Math.max(end,interval[1]);}else{ints.add(newint[]{start,end});start=interval[0];end=interval[1];}}ints.add(newint[]{start,end});returnints.toArray(newint[][]{});}