LeetCode100题总结【算法】

前言

写作于
2022-10-16 17:04:07

发布于
2022-11-21 20:12:22

双指针

11. 盛最多水的容器

//暴力算法
class Solution {public int maxArea(int[] height) {int length=height.length;int maxA=0;for(int i=0;ifor(int j=i+1;jint area=(j-i)*Math.min(height[i],height[j]);maxA=(Math.max(maxA,area));}}return maxA;}
}

因为贪心，所以实现不对
//[2,3,4,5,18,17,6]

//双指针
class Solution {public int maxArea(int[] height) {int length=height.length;int left=0;int right=length-1;while(leftint floor=right-left;int lh=height[left];int rh=height[right];int area=Math.min(lh,rh)*floor;int ll=left+1;int rr=right-1;int larea=Math.min(height[ll],rh)*(floor-1);int rarea=Math.min(lh,height[rr])*(floor-1);int marea=Math.min(height[ll],height[rr])*(floor-2);int maxA=Math.max(larea,rarea);maxA=Math.max(maxA,marea);if(area>maxA){ //有点贪心return area;}if(maxA==larea){left++;} else if(maxA==rarea){right--;} else if(maxA==marea){left++;right--;}else{left++;}}return 0;}
}

package src.leetcode100;public class MaxArea {public static void main(String[] args) {//[1,8,6,2,5,4,8,3,7]//[1,3,2,5,25,24,5]int [] height={1,3,2,5,25,24,5};System.out.println(maxArea(height));}public static int maxArea(int[] height) {int length=height.length;int left=0;int right=length-1;int maxa=0;while(leftint floor=right-left;int lh=height[left];int rh=height[right];int area=Math.min(lh,rh)*floor;int ll=left+1;int rr=right-1;int larea=Math.min(height[ll],rh)*(floor-1);int rarea=Math.min(lh,height[rr])*(floor-1);int marea=Math.min(height[ll],height[rr])*(floor-2);int maxA=Math.max(larea,rarea);maxA=Math.max(maxA,marea);if(maxA==larea){left++;} else if(maxA==rarea){right--;} else if(maxA==marea){left++;right--;}if(area>maxa){ //打擂台算法maxa=area;}}return maxa;}
}

/*
思路
如何看待这个问题？
可以将我们要计算的数字公式转化为直观的物理意义-面积，控制这个几何图形面积的因素有两个：底、高
我们可以用两个指针来底因素，左指针指向最左，右指针指向最右。
通过控制指针的移动来直接改变底，间接改变高，那该如何控制这个指针走向。
分析可得：
假设我们的左指针移动了，那么我们的底肯定小了，如果这时候高返回小了，那就没有移动的必要了，这样只让area越来越小。
所以可以确定的一点是，指针移动势必会让底变小，想尽快找到答案就必须让高适当增高！
那我们该如何控制高的问题呢？
本题而言，高这个因素是由最小的hight决定的，那明确了这个点好办了，
我们通过简单的判断高的问题，来控制左右指针的走向，指针发生移动之后，就可以通过计算面积，取对应的最大值来进行下一步的判断了，
当整个循环走完的时候，就我们的问题找出答案的时候。*/

//双指针
class Solution {public int maxArea(int[] height) {int f,l,area;f=0;area=0;l=height.length-1;while (f//Math.min(height[f],height[l])表示几何图形的高area=Math.max(area,Math.min(height[f],height[l])*(l-f));if(height[f]f++;}else  l--;}return area;}
}

如果我们移动数字较大的那个指针，那么前者「两个指针指向的数字中较小值」不会增加，后者「指针之间的距离」会减小，那么这个乘积会减小。因此，我们移动数字较大的那个指针是不合理的。因此，我们移动 数字较小的那个指针。

234.回文链表

翻转整个链表
再将翻转链表和原链表挨个
比较到一半长度即可

转数组的左右指针

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*///转换为数组
class Solution {public boolean isPalindrome(ListNode head) {List list=new ArrayList();while(head!=null){list.add(head.val);head=head.next;}int left=0;int right=list.size()-1;while(left<=right){if(list.get(left)!=list.get(right)){return false;}left++;right--;}return true;}
}

递归

class Solution {private ListNode frontPointer;private boolean recursivelyCheck(ListNode currentNode) {if (currentNode != null) {if (!recursivelyCheck(currentNode.next)) {return false;}if (currentNode.val != frontPointer.val) {return false;}frontPointer = frontPointer.next;}return true;}public boolean isPalindrome(ListNode head) {frontPointer = head;return recursivelyCheck(head);}
}作者：LeetCode-Solution
链接：https://leetcode.cn/problems/palindrome-linked-list/solution/hui-wen-lian-biao-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

方法三：快慢指针
思路

避免使用 O(n)O(n) 额外空间的方法就是改变输入。

我们可以将链表的后半部分反转（修改链表结构），然后将前半部分和后半部分进行比较。比较完成后我们应该将链表恢复原样。虽然不需要恢复也能通过测试用例，但是使用该函数的人通常不希望链表结构被更改。

该方法虽然可以将空间复杂度降到 O(1)O(1)，但是在并发环境下，该方法也有缺点。在并发环境下，函数运行时需要锁定其他线程或进程对链表的访问，因为在函数执行过程中链表会被修改。

算法

整个流程可以分为以下五个步骤：

找到前半部分链表的尾节点。
反转后半部分链表。
判断是否回文。
恢复链表。
返回结果。
执行步骤一，我们可以计算链表节点的数量，然后遍历链表找到前半部分的尾节点。

我们也可以使用快慢指针在一次遍历中找到：慢指针一次走一步，快指针一次走两步，快慢指针同时出发。当快指针移动到链表的末尾时，慢指针恰好到链表的中间。通过慢指针将链表分为两部分。

若链表有奇数个节点，则中间的节点应该看作是前半部分。

步骤二可以使用「206. 反转链表」问题中的解决方法来反转链表的后半部分。

步骤三比较两个部分的值，当后半部分到达末尾则比较完成，可以忽略计数情况中的中间节点。

步骤四与步骤二使用的函数相同，再反转一次恢复链表本身。

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/palindrome-linked-list/solution/hui-wen-lian-biao-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {public boolean isPalindrome(ListNode head) {if (head == null) {return true;}// 找到前半部分链表的尾节点并反转后半部分链表ListNode firstHalfEnd = endOfFirstHalf(head);ListNode secondHalfStart = reverseList(firstHalfEnd.next);// 判断是否回文ListNode p1 = head;ListNode p2 = secondHalfStart;boolean result = true;while (result && p2 != null) {if (p1.val != p2.val) {result = false;}p1 = p1.next;p2 = p2.next;}        // 还原链表并返回结果firstHalfEnd.next = reverseList(secondHalfStart);return result;}private ListNode reverseList(ListNode head) {ListNode prev = null;ListNode curr = head;while (curr != null) {ListNode nextTemp = curr.next;curr.next = prev;prev = curr;curr = nextTemp;}return prev;}private ListNode endOfFirstHalf(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast.next != null && fast.next.next != null) {fast = fast.next.next;slow = slow.next;}return slow;}
}作者：LeetCode-Solution
链接：https://leetcode.cn/problems/palindrome-linked-list/solution/hui-wen-lian-biao-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

75. 颜色分类

package src.leetcode100;import com.sun.org.apache.bcel.internal.generic.SWAP;/*** @author CSDN@日星月云* @date 2022/10/19 10:58*/
public class SortColors {public static void main(String[] args) {int[] nums={2,0,2,1,1,0};
//        int[] nums={2,0,0,2,0,0};sortColors(nums);for (int i = 0; i < nums.length; i++) {System.out.println(nums[i]);}}public static void sortColors(int[] nums) {//选择排序 把小的值换到前面了
//        for (int i = 0; i < nums.length; i++) {
//            for (int j = i; j < nums.length; j++) {
//                if (nums[i]>nums[j]){
//                    swap(nums,i,j);
//                }
//            }
//        }//选择排序 把大的值换到后面了
//        for (int i = 0; i < nums.length; i++) {
//            for (int j = 0; j < nums.length-1-i; j++) {
//                if (nums[i]
//                    swap(nums,i,j);
//                }
//            }
//        }//冒泡排序for (int i = 0; i < nums.length; i++) {for (int j = 0; j < nums.length-1-i; j++) {if (nums[j]>nums[j+1]){swap(nums,j,j+1);}}}//两次单指针// 0 1int ptr=0;for (int i = 0; i < nums.length; i++) {if (nums[i]==0){swap(nums,i,ptr);ptr++;}}for (int i = 0; i < nums.length; i++) {if (nums[i]==1){swap(nums,i,ptr);ptr++;}}//双指针 2个状态值可以
//        int left=0;
//        int right=nums.length-1;
//
//        while (left
//
//            if (nums[left]==0){
//                left++;
//            }
//            if (nums[right]==2){
//                right--;
//            }
//
//            if (nums[left]==2){
//                swap(nums,left,right);
//                left++;
//                right--;
//            }
//
//            if (nums[right]==0){
//                swap(nums,left,right);
//                left++;
//                right--;
//            }
//        }int []tmp =new int[nums.length];int left=0;int right=tmp.length-1;for (int i=0;iif (nums[i]==0){tmp[left++]=nums[i];}if (nums[i]==2){tmp[right--]=nums[i];}}//或者把tmp元素初始化为1for (int i=0;iif (nums[i]==1){tmp[left++]=nums[i];}}for (int i=0;inums[i]=tmp[i];}}public static void swap(int[] nums,int i,int j){int temp=nums[i];nums[i]=nums[j];nums[j]=temp;}
}