一、交叉链表

问题：

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

解题思想：

双指针

备注：不是快慢指针，如果两个长度相同可以用快慢指针，因为两个链表长度不同。

package org.example.YangQianGuan;

class Node {
    int data;
    Node next;

    Node(int val) {
        this.data = val;
        this.next = null;
    }

    @Override
    public String toString() {
        return " {data: " + this.data + " next: " + this.next + "} ";
    }
}

public class IntersectionNode {
    public Node getStartInter(Node headA, Node headB) {
        if (headA == null || headB == null) {
            return null;
        }
        Node pA = headA;
        Node pB = headB;

        while (pA!= pB) {
            pA = pA == null? headB : pA.next;
            pB = pB == null? headA : pB.next;
        }
        return pA;
    }


    public static void main(String[] args) {
        // node list
        Node node8 = new Node(8);
        Node node4 = new Node(4);
        Node node5 = new Node(5);

        node8.next = node4;
        node4.next = node5;

        // A list
        Node headA = new Node(4);
        Node nodeA1 = new Node(1);
        headA.next = nodeA1;
        nodeA1.next = node8;

        // B List
        Node headB = new Node(5);
        Node nodeB1 = new Node(6);
        Node nodeB2 = new Node(1);
        headB.next = nodeB1;
        nodeB1.next = nodeB2;
        nodeB2.next = node8;

        IntersectionNode intersectionNode = new IntersectionNode();
        Node startInter = intersectionNode.getStartInter(headA, headB);
        System.out.println(startInter);
    }
}

二、对称二叉树

Tree

package org.example.YangQianGuan;

class Tree{
    int data;
    Tree left;
    Tree right;

    public Tree(int data, Tree left, Tree right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
}

public class IsMirrorTree {

    public boolean isMirror(Tree root) {
        if (root == null) {
            return true;
        }

        return this.isMirrorCore(root.left, root.right);
    }

    public boolean isMirrorCore(Tree left, Tree right) {
        if (left == null && right == null) {
            return true;
        }

        if (left == null || right == null) {
            return false;
        }

        if (left.data != right.data) {
            return false;
        }

        return isMirrorCore(left.left, right.right) && isMirrorCore(left.right, right.left);
    }

    public static void main(String[] args) {
        Tree right4 = new Tree(3, null, null);
        Tree right3 = new Tree(4, null, null);
        Tree right2 = new Tree(2, right3, right4);

        Tree left4 = new Tree(4, null, null);
        Tree left3 = new Tree(3, null, null);
        Tree left2 = new Tree(2, left3, left4);
        Tree node1 = new Tree(1, left2, right2);

        IsMirrorTree isMirrorTree = new IsMirrorTree();
        boolean mirror = isMirrorTree.isMirror(node1);
        System.out.println(mirror);
    }

}

三、轮转数组

package org.example.YangQianGuan;

import java.util.Arrays;
import java.util.List;

public class RightRunArr {

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6, 7};
        int n = 3;

        RightRunArr rightRunArr = new RightRunArr();
        int[] core = rightRunArr.core(nums, n);
        System.out.println(Arrays.toString(core));
    }

    private int[] core(int[] nums, int n) {
        int[] res = new int[nums.length];
        int bit = n % nums.length;
        System.out.println(bit);

        int[] left = Arrays.copyOfRange(nums, 0, nums.length - bit);
        int[] right = Arrays.copyOfRange(nums, nums.length - bit, nums.length);

        int i = 0;
        for (int i1 : right) {
            res[i] = i1;
            i++;
        }

        for (int i1 : left) {
            res[i] = i1;
            i++;
        }

        return res;
    }
}

四、接雨水

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 
示例 2：输入：height = [4,2,0,3,2,5]   输出：9

提示：

n == height.length
1 <= n <= 2 * 
0 <= height[i] <= 

package org.example.YangQianGuan;

/**
 * 暴力求解法
 * 总水量 = 除了左右两个边界，【1，lenth-1】所有点位能接水的量的总和
 * 题目转化为如何求解每个点位的接水量 = Math.min(次点左边最大高度，此点右边最大高度）-heiht（i）
 */
public class TrapSolution {
    public int trap(int[] height) {
        if (height.length<=1) {
            return 0;
        }

        int totleWater = 0;
        int leftMax = 0, rightMax = 0;

        for (int i = 1; i < height.length-1; i++) {
            // left max
            for (int j = 0; j < i; j++) {
                leftMax = Math.max(leftMax, height[j]);
            }

            // right max
            for (int j = i+1; j < height.length; j++) {
                rightMax = Math.max(rightMax, height[j]);
            }

            totleWater += Math.min(leftMax,rightMax)-height[i];

        }

        return totleWater;
    }

    public static void main(String[] args) {
        TrapSolution solution = new TrapSolution();

        // 测试用例 1
        int[] height1 = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(solution.trap(height1)); // 输出: 6

        // 测试用例 2
        int[] height2 = {4,2,0,3,2,5};
        System.out.println(solution.trap(height2)); // 输出: 9
    }
}

五、字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:输入: strs = [""] 输出: [[""]]

示例 3:输入: strs = ["a"] 输出: [["a"]]

提示：

1 <= strs.length <= 
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

package org.example.YangQianGuan;

import java.util.*;

public class GroupAnagrams {

    public static void main(String[] args) {
        String[] s = {"eat", "tea", "tan", "ate", "nat", "bat"};

        GroupAnagrams groupAnagrams = new GroupAnagrams();
        String[] res = groupAnagrams.getGroup(s);
    }

    private String[] getGroup(String[] s) {
        int length = s.length;
        if (length==0) {
            return new String[0];
        }

        Map<String, List<String>> map = new HashMap<>();
        for (String string : s) {
            char[] charArray = string.toCharArray();
            Arrays.sort(charArray);
            String s1 = new String(charArray);

            List<String> orDefault = map.getOrDefault(s1, new ArrayList<>());
            orDefault.add(string);
            map.put(s1, orDefault);
        }

        String res[] = new String[map.size()];
        int n = 0;

        for (Map.Entry<String, List<String>> stringListEntry : map.entrySet()) {
            List<String> value = stringListEntry.getValue();
            String[] array = value.toArray(String[]::new);
            res[n] = Arrays.toString(array);
            n++;
        }

        System.out.println(Arrays.toString(res));

        return res;
    }
}