#yyds干货盘点# LeetCode刷题集151 - 160

2021年11月24日 阅读数:12
这篇文章主要向大家介绍#yyds干货盘点# LeetCode刷题集151 - 160,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

博主私藏的LeetCode刷题集合
有些较难的问题都有思路和注释node

151. 翻转字符串里的单词

给定一个字符串,逐个翻转字符串中的每一个单词。算法

示例 1:数组

输入: "the sky is blue"
输出: "blue is sky the"
示例 2:markdown

输入: " hello world! "
输出: "world! hello"
解释: 输入字符串能够在前面或者后面包含多余的空格,可是反转后的字符不能包括。
示例 3:app

输入: "a good example"
输出: "example good a"
解释: 若是两个单词间有多余的空格,将反转后单词间的空格减小到只含一个。ide

说明:设计

无空格字符构成一个单词。
输入字符串能够在前面或者后面包含多余的空格,可是反转后的字符不能包括。
若是两个单词间有多余的空格,将反转后单词间的空格减小到只含一个。指针

进阶:code

请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。blog

class Solution {
    public String reverseWords(String s) {
        String[] s1 = s.trim().split(" ");
        StringBuffer stringBuffer=new StringBuffer();
        for (int i=s1.length-1;i>=0;i--){
            if (s1[i].equals("")){
                continue;
            }
            stringBuffer.append(s1[i]);
            if (i>0){
             stringBuffer.append(" ");
            }
        }
        return stringBuffer.toString();
    }
}

152. 乘积最大子序列

给定一个整数数组 nums ,找出一个序列中乘积最大的连续子序列(该序列至少包含一个数)。

示例 1:

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 由于 [-2,-1] 不是子数组。

class Solution {
    public int maxProduct(int[] nums) {
        int max = Integer.MIN_VALUE, imax = 1, imin = 1; //一个保存最大的,一个保存最小的。
        for(int i=0; i<nums.length; i++){
            if(nums[i] < 0){ int tmp = imax; imax = imin; imin = tmp;} //若是数组的数是负数,那么会致使最大的变最小的,最小的变最大的。所以交换两个的值。
            imax = Math.max(imax*nums[i], nums[i]);
            imin = Math.min(imin*nums[i], nums[i]);

            max = Math.max(max, imax);
        }
        return max;
    }
}

153. 寻找旋转排序数组中的最小值

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

你能够假设数组中不存在重复元素。

示例 1:

输入: [3,4,5,1,2]
输出: 1
示例 2:

输入: [4,5,6,7,0,1,2]
输出: 0

class Solution {
    public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
int mid=0;
    while (left < right) {
        mid = (left + right) / 2;
        if (nums[mid] > nums[mid + 1]) return nums[mid+1];
        if (nums[mid] > nums[right]) left = mid;
        else right = mid;
    }
    return nums[left];
    }
}

154. 寻找旋转排序数组中的最小值 II

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

注意数组中可能存在重复的元素。

示例 1:

输入: [1,3,5]
输出: 1
示例 2:

输入: [2,2,2,0,1]
输出: 0
说明:

这道题是 寻找旋转排序数组中的最小值 的延伸题目。
容许重复会影响算法的时间复杂度吗?会如何影响,为何?

PS:

和 I 的作法相似, 都是二分法, 每次进入无序的那部分找出最小值
可是因为有重复值的状况, 须要加入 mid 元素等于 hi 元素的状况
此时应该将 hi 减 1 防止重复数字是最小元素

class Solution { 
 public int findMin(int[] nums) {

        int lo = 0, hi = nums.length-1;
        while(lo < hi) {
            int mid =  (hi+lo)/2;
            if(nums[mid] > nums[hi])
                lo = mid+1;
            else if(nums[mid] < nums[hi])
                hi = mid;
            else
                hi--;
        }
        return nums[lo];
    }

}

155. 最小栈

设计一个支持 push,pop,top 操做,并能在常数时间内检索到最小元素的栈。

push(x) -- 将元素 x 推入栈中。
pop() -- 删除栈顶的元素。
top() -- 获取栈顶元素。
getMin() -- 检索栈中的最小元素。
示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.
class MinStack {  
    private int min = Integer.MAX_VALUE;
    private Stack<Integer> stack;
    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<>();
    }

    public void push(int x) {
        if(min >= x){
            stack.push(min);
            min = x;
        }
        stack.push(x);
    }

    public void pop() {
        if(stack.pop() == min){
            min = stack.pop();
        }
    }

    public int top() {
      return stack.peek();
    }

    public int getMin() {
        return min;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

160. 相交链表

编写一个程序,找到两个单链表相交的起始节点。

以下面的两个链表:
在这里插入图片描述

在节点 c1 开始相交。

示例 1:
在这里插入图片描述

输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出:Reference of the node with value = 8
输入解释:相交节点的值为 8 (注意,若是两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。

示例 2:

在这里插入图片描述

输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出:Reference of the node with value = 2
输入解释:相交节点的值为 2 (注意,若是两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [0,9,1,2,4],链表 B 为 [3,2,4]。在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。

示例 3:

在这里插入图片描述

输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出:null
输入解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。因为这两个链表不相交,因此 intersectVal 必须为 0,而 skipA 和 skipB 能够是任意值。
解释:这两个链表不相交,所以返回 null。

注意:

若是两个链表没有交点,返回 null.
在返回结果后,两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽可能知足 O(n) 时间复杂度,且仅用 O(1) 内存。

PS:

首先你得弄明白以前的那道题,就是判断一个链表是否是有环。如今有两个链表了,那么咱们先把其中一个链表B的尾节点指向头,对于另外一个链表A,开始用快慢指针从头遍历,若是能碰到一块儿,证实有环,此时再把快慢指针的其中一个(两个如今指向同一位置)指向A的头结点,此时两指针再相遇的地方就是两链表相交的地方。公式证实的话,你画一个图,参数用字母表示,就能推出来

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
      public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode last = headB;
        while (last.next != null) {
            last = last.next;
        }
        last.next = headB;

        ListNode fast = headA;
        ListNode slow = headA;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                slow = headA;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                last.next = null;
                return fast;
            }

        }
        last.next = null;
        return null;
    }
}