2023/10/10 LeetCode

LeetCode p11 盛最多水的容器

描述： 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。

思路 :既然是要求当前可以存储的最大水量，那么按照常规思路，只需要定义两个指针指向首尾作为容器的边界，我们每次将最小的值的指针向另一指针移动，记录每次移动的容器中的大小值，即可找到最大的容器盛水量。

代码 ：

 /**
     * P11盛最多水的容器
     * @param height
     * @return
     */
    public int maxArea(int[] height) {
        int result = 0;
        int heightMax = 0;
        for (int i=0,j=height.length-1;i<j;)
        {
            heightMax = Math.min(height[i], height[j]); //取最小的高度
            int curMax = (j-i)*heightMax; //求当前面积
            System.out.println("i="+i+",j="+j+",cur="+curMax);
            result = Math.max(result,curMax);
            if (height[i]>height[j]) {
                j--;
            }
            else {
                i++;
            }
        }
        return result;
    }

LeetCode P160 相交链表
描述 ：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null。

思路： 按照题目所需要找到两个链表的交点，那么我们思考一下如果存在交点，那么这个交点后面的节点必是相同节点，既然如此，我们直接将短的一个链表与长链表进行一个右对齐，然后遍历连个链表，只要存在节点相等，即可说明该节点是两个节点的交点，如果链表遍历完成都未找到相等节点，即说明不存在交点，直接返回null值即可。

代码：

/**
     * P160 相交链表
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA;
        ListNode b = headB;
        int aLength = 0;
        int bLength = 0;
        // 判断哪个链表比较长
        while (a!=null) {
            aLength++;
            a = a.next;
        }
        while (b!=null){
            bLength++;
            b = b.next;
        }
        ListNode longList;
        ListNode shortList;
        int sub;
        if (aLength>bLength){
            longList = headA;
            shortList = headB;
            sub = aLength-bLength;
        }
        else {
            longList = headB;
            shortList = headA;
            sub = bLength - aLength;
        }
        //移动长链表与短链表进行对齐
        while (sub>0) {
            longList = longList.next;
            sub--;
        }
        while (longList!=null) {
            if (longList==shortList)
                return longList;
            longList = longList.next;
            shortList = shortList.next;
        }
        return null;
    }