力扣hot100刷题记录

二刷hot100，坚持每天打卡3道题！！！Today：2023-09-24

1. 两数之和

// 先求差，再查哈希表
public int[] twoSum(int[] nums, int target) {
    Map<Integer,Integer> map = new HashMap<>();
    for(int i = 0;i<nums.length;i++){
        int key = target - nums[i];
        if(map.containsKey(key)){
            return new int[]{map.get(key),i};
        }
        map.put(nums[i],i);
    }
    return new int[0];
}

2. 两数相加

	// 对应位置相加，记录进位，然后链表尾插法即可
	public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int flag = 0,lv1,lv2;
        ListNode answer = null,target = null;
        while (l1 != null || l2 != null){
            lv1 = l1 == null ? 0:l1.val;
            lv2 = l2 == null ? 0:l2.val;
            l1 = l1 == null ? null:l1.next;
            l2 = l2 == null ? null:l2.next;
            int sum = lv1+lv2+flag;
            flag = sum / 10;
            ListNode listNode = new ListNode(sum % 10);
            if (target == null){
                target = listNode;
                answer = target;
            }else {
                target.next = listNode;
                target = target.next;
            }
        }
        if (flag >0){
            target.next = new ListNode(flag);
        }
        return answer;
    }

3. 无重复字符的最长字串

	// 滑动窗口
	public int lengthOfLongestSubstring(String s){
        Set<Character> set = new HashSet<>();
        int start = 0,end = 0,answer=0;
        while (end < s.length()){
            if (set.contains(s.charAt(end))){
                set.remove(s.charAt(start++));
            }else {
                set.add(s.charAt(end++));
                answer = Math.max(answer,end - start);
            }
        }
        return answer;
    }

4. 最长回文子串

 // 动态规划
 public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }
        int strLen = s.length();
        int maxStart = 0;  //最长回文串的起点
        int maxEnd = 0;    //最长回文串的终点
        int maxLen = 1;  //最长回文串的长度

        boolean[][] dp = new boolean[strLen][strLen];

        for (int r = 1; r < strLen; r++) {
            for (int l = 0; l < r; l++) {
                if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {
                    dp[l][r] = true;
                    if (r - l + 1 > maxLen) {
                        maxLen = r - l + 1;
                        maxStart = l;
                        maxEnd = r;
                    }
                }
            }
        }
        return s.substring(maxStart, maxEnd + 1);
    }

5. 寻找两个正序数组的中位数

		/*
			总体思路：模拟合并数组，合并到中位数停止
			时间：1ms，        击败 100.00%使用 Java 的用户
		    内存：42.03mb     击败 63.77%使用 Java 的用户
		*/
		public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int num = 0; // 偶数中位数数字，奇数中位数右侧数字
            int len = nums1.length + nums2.length;
            boolean b = len % 2 == 0; // 是否为偶数
            len /= 2; // 偶数中位数位置，奇数中位数右侧位置
            if (nums1.length + nums2.length == 0) return 0; // 空数组返回0
            if (nums1.length == 0) return b ? (nums2[len - 1] + nums2[len]) / 2.0 : nums2[len]; // 数组1为空返回数组2中位数
            if (nums2.length == 0) return b ? (nums1[len - 1] + nums1[len]) / 2.0 : nums1[len]; // 数组2为空返回数组1中位数
            int i = 0,j = 0;
            int oldNum = num; // 奇数中位数左侧数字
            while (i + j != len + 1) { // 判断是否循环至中位数
                oldNum = num;
                if (i >= nums1.length || (j < nums2.length && nums1[i] > nums2[j])) num = nums2[j++];
                else num = nums1[i++];
            }
            return b ? (num + oldNum) / 2.0 : num; // 返回中位数
        }

6. 正则表达式匹配

	// 动态规划
    public boolean isMatch(String s, String p) {
        //此处为length+1的目的是放入一个额外的为空的字符情况，以便于判断当*时，添加的字符情况
        boolean table[][]=new boolean[s.length()+1][p.length()+1];
        table[0][0]=true;
        for(int i =1;i<table[0].length;i++){
            char ch=p.charAt(i-1);
            if(i>1){
                //若ch=='*'，则看同一行内回退两格的boolean值：
                //（因为相当于若回退两格为true，即在选择添加该字符时可以选择数量为0（因为是'*'））
                if(ch=='*'){
                    table[0][i]=table[0][i-2];
                }
                //因为第0行的s字符为空，所以和除了*以外的都不匹配，直接false
                else table[0][i]=false;
            }
            else {
                //如果填第一个空格，且字符为*，则赋值为true（因为*的匹配可以选择0个字符）
                if(ch=='*') table[0][i]=true;
            }
        }
        //接下来按照行优先的顺序填充表格
        for(int j =1;j<table.length;j++){
            char ch01=s.charAt(j-1);
            for(int h =1;h<table[j].length;h++){
                char ch02=p.charAt(h-1);
                //如果行和列对应的字符相等 || 列的字符为'.'，则当前位置的值由左斜上方的值确定
                if(ch02==ch01||ch02=='.'){
                    table[j][h]=table[j-1][h-1];
                }
                //如果列的字符为'*'
                else if(ch02=='*'){
                    if(h>1){
                        //按照规则，先在同一行回退两格，若该值为true则直接赋值true
                        if(table[j][h-2]==true) table[j][h]=true;
                        else {
                            //若不为true，则比较当前行的字符（s里的）与当前列-1的字符（p里的）是否相等
                            char prev=p.charAt(h-2);
                            //若相等 || 当前列-1的字符（p里的）为'.'，将当前位置上方的值赋给当前位置
                            if(ch01==prev||prev=='.') table[j][h]=table[j-1][h];
                        }
                    }

                }
            }
        }
        //返回table表的最右下方元素，即为整个字符串的匹配结果
        return table[s.length()][p.length()];
    }

7. 盛水最多的容器

	/**
     * 高往低走，长度变小、高度变小、面积一定变小
     * 低往高走，长度变小、高度可能变大、面积可能变大
     */
	public int maxArea(int[] height) {
        int i = 0, j = height.length - 1, res = 0;
        while(i < j) {
            res = height[i] < height[j]
                    ? Math.max(res, (j - i) * height[i++])
                    : Math.max(res,(j - i) * height[j--]);
        }
        return res;
    }

8. 三数之和

	/*
		思路：排序 + 双指针
		-4,1,2,3
		当前元素(target)的下一个元素(left)为起点、最后一个元素(right)为终点进行计算
		情况1：target + left + right == 0 》 正确
		情况2：target + left + right > 0 》 说明 right 数值太大，right--
		情况3：target + left + right < 0 》 说明 left 数值太小，left++
	*/
	public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < nums.length ; i++) {
            // 当前元素>0 后面的所有元素肯定都>0，所以提前结束
            if(nums[i] > 0) break;
            // 当前元素和前一个元素相同，说明发现重复数字，无需再次计算
            if(i > 0 && nums[i] == nums[i-1]) continue; 
            int left = i+1;
            int right = nums.length-1;
            while(left < right){
                int sum = nums[i] + nums[left] + nums[right];
                if(sum == 0){
                    ans.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    // [-2,0,0,2,2] 跳过相同数字，去重
                    while (left<right && nums[left] == nums[left+1]) left++; 
                    // [-2,0,0,2,2] 跳过相同数字，去重
                    while (left<right && nums[right] == nums[right-1]) right--; 
                    left++;
                    right--;
                }
                else if (sum < 0) left++;
                else right--;
            }
        }
        return ans;
    }

9. 电话号码的字母组合

    private StringBuilder sb = new StringBuilder();
    private List<String> answer = new ArrayList<>();
    /*
      思路：获取对应字母的字符串，递归组合
     */
    public List<String> letterCombinations(String digits) {
        if(digits.equals("")) return new ArrayList<>();
        String[] nums = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        List<String> list = new ArrayList<>(4);
        for (int i = 0; i < digits.length(); i++) list.add(nums[Integer.parseInt(digits.charAt(i)+"")]);
        assemble(list,0);
        return answer;
    }
    private void assemble(List<String> list, int index) {
        if (index == list.size()){
            answer.add(sb.toString());
            return;
        }
        String numChars = list.get(index);
        for (int i = 0; i < numChars.length(); i++) {
            // 组装
            sb.append(numChars.charAt(i));
            assemble(list,index+1);
            // 回溯
            sb.deleteCharAt(index);
        }
    }

10. 删除列表倒数第n个结点

/*
	思路：双指针，start，end
		start定位正数第n个结点，然后end和start循环后移，当start指向最后一个元素时，end就指向了要删除元素的前一个结点
	注意：删除头结点或尾结点时会存在问题，所以新建一个空的前驱结点做为头结点
*/
public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode start = pre, end = pre;
        while(n != 0) {
            start = start.next;
            n--;
        }
        while(start.next != null) {
            start = start.next;
            end = end.next;
        }
        end.next = end.next.next;
        return pre.next;
    }

11. 有效的括号

	/*
	配对问题，优先考虑栈
	*/
	public boolean isValid(String s) {
        final Map<Character,Character> map = new HashMap<Character,Character>(){{
            put('{','}'); put('[',']'); put('(',')');
        }};
        Stack<Character> stack = new Stack<Character>();
        // 保证栈不为空，如果第一个字符为 }]) 中的一种会出现 空栈pop
        stack.push('1');
        for(Character c : s.toCharArray()){
            if(map.containsKey(c)) stack.push(c);
            else if(map.get(stack.pop()) != c) return false;
        }
        return stack.size() == 1;
    }

12. 合并两个有序链表

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode node = new ListNode(),head = node;
        while (true){
            if (list1 == null && list2 == null){
                return head.next;
            }else if (list1 == null){
                node.next = new ListNode(list2.val);
                list2 = list2.next;
            }else if (list2 == null){
                node.next = new ListNode(list1.val);
                list1 = list1.next;
            }else {
                if (list1.val > list2.val){
                    node.next = new ListNode(list2.val);
                    list2 = list2.next;
                }else {
                    node.next = new ListNode(list1.val);
                    list1 = list1.next;
                }
            }
            node = node.next;
        }
    }

13. 括号生成

	/*
		回溯：	左括号的数量 < n那，加'(' 
				右括号的数量 < 左括号的数量,加')'
				StringBuilder的元素长度== n 结束
	*/
	public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        dfs(n, 0, 0,res,sb);
        return res;
    }
    public void dfs(int n, int left, int right,List<String> res,StringBuilder sb) {
        if (sb.length() == n*2){
            res.add(sb.toString());
            return;
        }
        if(left < n){
            sb.append("(");
            dfs(n,left+1,right,res,sb);
            sb.deleteCharAt(sb.length()-1);
        }
        if (right < left){
            sb.append(")");
            dfs(n,left,right+1,res,sb);
            sb.deleteCharAt(sb.length()-1);
        }
    }

14. 合并 k 个升序链表

	//-----------------------------解法1----------------------------------------
	// （不推荐）：暴力求解，获取所有元素排序后生成
    public ListNode mergeKLists(ListNode[] lists) {
        List<Integer> list = new ArrayList<>();
        for (ListNode node : lists) {
            while (node != null){
                list.add(node.val);
                node = node.next;
            }
        }
        list.sort(Comparator.comparingInt(o -> o));
        ListNode listNode = new ListNode(0),p = listNode;
        for (Integer val : list) {
            p.next = new ListNode(val);
            p = p.next;
        }
        return listNode.next;
    }
	//-----------------------------解法2----------------------------------------
	// 解法2：获取每个链表中的最小值
	public ListNode mergeKLists(ListNode[] lists) {
        int k = lists.length;
        ListNode head = new ListNode(0),p = head;
        while (true) {
            int minIndex = -1,minVal = Integer.MAX_VALUE;
            for (int i = 0; i < k; i++) {
                if (lists[i] == null) {
                    continue;
                }
                if (lists[i].val < minVal) {
                    minVal = lists[i].val;
                    minIndex = i;
                }
            }
            if (minVal == Integer.MAX_VALUE) {
                break;
            }
            lists[minIndex] = lists[minIndex].next;
            p.next = new ListNode(minVal);
            p = p.next;
        }
        return head.next;
    }

15. 下一个排列

	/*
		思路：	1. 倒叙遍历，找到大于前一个元素的元素，为了好理解这里称 pre为前一个元素，current为当前元素
				2. 将当前元素及后续元素进行升序排序，用于确保是最小序列。1,3,2=>1,2,3
				3. 查询比pre大的那个最小元素并交换		1,2,3 => 1,3,2
	*/
	public void nextPermutation2(int[] nums) {
        int len = nums.length;
        for (int i = len - 1; i > 0; i--) {
            if (nums[i] > nums[i - 1]) {
                Arrays.sort(nums, i, len);
                for (int j = i; j <len; j++) {
                    if (nums[j] > nums[i - 1]) {
                        swap(nums,i-1,j);
                        return;
                    }
                }
            }
        }
        // 降序排列数组
        Arrays.sort(nums);
    }
    // 交换数组元素
    public void swap(int[] nums,int i,int j){
        int temp = nums[j];
        nums[j] = nums[i];
        nums[i] = temp;
    }

16. 最长有效括号

	/* 
		第11题升级版，在11题的基础上修改成下标存储，下标计算长度
	*/ 
	public int longestValidParentheses(String s) {
        LinkedList<Integer> st = new LinkedList<>();
        int ans = 0;
        for(int i = 0 ,start = 0;i < s.length();i ++){
            if( s.charAt(i) == '(') {
                st.addFirst(i);
            }else if(!st.isEmpty()){
                st.pop();
                ans = st.isEmpty() ? Math.max(ans,i - start + 1) : Math.max(ans,i - st.peek());
            }else{
                start = i + 1;
            }
        }
        return ans;
    }

17. 搜索旋转排序数组

    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1, mid = 0;
        while (l <= r) {
            mid = l + (r - l) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            // 先根据 nums[mid] 与 nums[l] 的关系判断 mid 是在左段还是右段
            if (nums[mid] >= nums[l]) {
                // 再判断 target 是在 mid 的左边还是右边，从而调整左右边界 lo 和 hi
                if (target >= nums[l] && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (target > nums[mid] && target <= nums[r]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }

18. 在排序数组中查找元素的第一个和最后一个位置

	/*
		1. 二分查找左侧边界
		2. 二分查找右侧边界
	*/
	public int[] searchRange(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return new int[]{leftIdx, rightIdx};
        }
        return new int[]{-1, -1};
    }
    /**
     * @param nums 源数组
     * @param target 目标元素
     * @param flag 方向标志：true左 false右
     */
    public int binarySearch(int[] nums, int target, boolean flag) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (nums[mid] > target || (flag && nums[mid] == target)) {
                right = mid - 1;
                ans = mid;
            }else{
                left = mid + 1;
            }
        }
        return ans;
    }

19. 数组总和

	public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 排序用于提前剪枝
        Arrays.sort(candidates);
        List<List<Integer>> listAnswer = new ArrayList<>();
        dfs(candidates,0,target,0,new LinkedList<>(),listAnswer);
        return listAnswer;
    }
    public void dfs(int[] candidates,int beginIndex,int target,int sum,LinkedList<Integer> path,List<List<Integer>> listAnswer){
        if (target == sum){
            listAnswer.add(new ArrayList<>(path)) ;
            return;
        }
        for (int i = beginIndex; i < candidates.length; i++) {
            // 在数组升序的情况下，如果 sum+当前元素> target 那么sum+当前元素之后的任意元素也大于target，所以提前break剪枝
            if (sum + candidates[i] > target)
                break;
            path.addLast(candidates[i]);
            dfs(candidates,i,target,sum+candidates[i],path,listAnswer);
            path.removeLast();
        }
    }

20. 接雨水

	/*
		按列求，当前列的存水量取决于，min = Math.min(左侧最大值,右侧最大值)，分三种情况：
			1. min > 当前列：存水量为 min-当前列
			2. min = 当前列：存水量为0
			3. min < 当前列：存水量为0
		即：只有 min>当前列的时候才会存水
	*/
	public int trap(int[] height) {
        int sum = 0;
        for (int i = 1; i < height.length; i++) {
            int maxLeft = 0,maxRight = 0;
            for (int j = i-1; j >= 0; j--) {
                maxLeft = Math.max(maxLeft,height[j]);
            }
            for (int j = i+1; j < height.length; j++) {
                maxRight = Math.max(maxRight,height[j]);
            }
            int min = Math.min(maxLeft, maxRight);
            if (min > height[i]){
                sum += min-height[i];
            }
        }
        return sum;
    }

21. 全排列

	/*
		不存在重复元素的全排列，优先使用 递归法
		存在重复元素的全排列，优先使用 抓取法
	*/
	private void swap(int[] nums,int i,int j){
        int temp = nums[j];
        nums[j] = nums[i];
        nums[i] = temp;
    }
    public List<List<Integer>> permute(int[] nums) {
        ArrayList<List<Integer>> answer = new ArrayList<>();
        dfs(nums,0, answer);
        return answer;
    }
    public void dfs(int[] nums,int k,List<List<Integer>> answer){
        // 边界
        if (k == nums.length){
            ArrayList<Integer> list = new ArrayList<>();
            for (int num : nums)
                list.add(num);
            answer.add(list);
            return;
        }
        for (int i = k; i < nums.length; i++) {
            swap(nums,i,k);
            dfs(nums,k+1,answer); // 递归
            swap(nums,i,k); // 回溯
        }
    }

22. 旋转图像

	/*
		由外到内原地交换
	*/
	public void rotate(int[][] matrix) {
        int n = matrix.length;
        int len = (n + 1) >>> 1;
        for (int i = 0; i < n/2; i++) {
            for (int j = 0; j < len; j++) {
                int temp = matrix[i][j]; // 左上角
                matrix[i][j] = matrix[n - 1 - j][i]; // 左上角等于左下角
                matrix[n - 1 - j][i] = matrix[n-1-i][n-1-j];// 左下角等于右下角
                matrix[n-1-i][n-1-j] = matrix[j][n-1-i]; // 右下角等于右上角
                matrix[j][n-1-i] = temp; // 右上角等于左上角
            }
        }
    }

23. 字母异位词分组

	/*
		方法1：groupingBy分组
	*/
	public List<List<String>> groupAnagrams(String[] strs) {
        return new ArrayList<>(Arrays.stream(strs).collect(Collectors.groupingBy(e->{
            char[] chars = e.toCharArray();
            Arrays.sort(chars);
            return new String(chars);
        })).values());
    }
	/*
		方法2：stream 对字符串排序，这样只需要一行代码即可
	*/
	public List<List<String>> groupAnagrams(String[] strs) {
        // str -> intstream -> sort -> collect by StringBuilder
        return new ArrayList<>(Arrays.stream(strs).collect(Collectors.groupingBy(str -> str.chars().sorted().collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append).toString())).values());
    }
    /*
   		方法3：对字符串排序，使用字符串分割排序
	*/
	public List<List<String>> groupAnagrams(String[] strs) {
        return new ArrayList<>(Arrays.stream(strs).collect(Collectors.groupingBy(s-> Stream.of(s.split("")).sorted().collect(Collectors.joining()))).values());
    }

24. 最大子数组和

	/*
        动态规划：子问题为 求两个数的和（正向）
        分为两种情况：
            1. currentSum + nums[i] < nums[i];
            2. currentSum + nums[i] >= nums[i];
     */
    public int maxSubArray(int[] nums) {
        int currentSum = 0,maxSum = nums[0];
        for (int i = 0; i < nums.length; i++) {
            currentSum = Math.max(currentSum + nums[i], nums[i]);
            maxSum = Math.max(currentSum,maxSum);
        }
        return maxSum;
    }

25. 跳跃游戏

	/*
		第一次使用递归，但是超时了
		第二次思路：
			1. 如果不存在 0，那么一定会跳跃到最后
			2. 如果存在 0，判断一下0之前的元素能不能跳过当前位置
	*/
	public boolean canJump(int[] nums) {
        int maxIndex = 0; // 可以跳到的最远位置
        for (int i = 0; i < nums.length; i++) {
        	// 如果当前位置超过了可以跳到的最远位置，直接false
            if (i > maxIndex) return false;
            // 最远位置=当前位置+当前可到达的最远位置
            maxIndex = Math.max(maxIndex,i+nums[i]); 
        }
        return true;
    }

26. 合并区间

	 /*
    	{{1,3},{2,6},{8,10},{15,18}}
        在区间有序的情况下
            当前数组的最大元素 >= 下一个数组的最小元素  ： 结束位置取最大
            当前数组的最大元素 < 下一个数组的最小元素  ： 添加新区间
     */
    public int[][] merge(int[][] intervals) {
        // 根据区间的开始位置进行排序
        Arrays.sort(intervals, Comparator.comparingInt(v -> v[0]));
        int[][] res = new int[intervals.length][2];
        res[0] = intervals[0];
        int index = 0;
        for (int i = 1; i < intervals.length; i++) {
            if (res[index][1] < intervals[i][0]) {
                res[++index] = intervals[i];
            } else {
                res[index][1] = Math.max(res[index][1], intervals[i][1]);
            }
        }
        return Arrays.copyOf(res, index+1);
    }

27. 不同路径

	// 动态规划入门题型
	public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) dp[i][0] = 1;
        for (int i = 0; i < n; i++) dp[0][i] = 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }

28. 最小路径和

	// 动态规划入门题
	public int minPathSum(int[][] grid) {
        int m = grid.length,n = grid[0].length;
        // 行
        for (int i = 1; i < n; i++) grid[0][i] += grid[0][i-1];
        // 列
        for (int i = 1; i < m; i++) grid[i][0] += grid[i-1][0];
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] += Math.min(grid[i-1][j],grid[i][j-1]);
            }
        }
        return grid[m - 1][n - 1];
    }

29. 爬楼梯

	/*
		动态规划入门题
		设有 f(n) 种爬法，因为一次可以爬 1 或 2 个台阶
			当剩余一个台阶的时候，有 f(n-1) 种爬法
			当剩余两个台阶的时候，有 f(n-2) 种爬法
		即：f(n) = f(n-1) + f(n-2)
	*/
	public int climbStairs(int n) {
        if (n <= 2) return n;
        int a = 1,b = 2,c;
        for (int i = 3; i <= n; i++) {
            c = b;
            b += a;
            a = c;
        }
        return b;
    }

30. 最长公共子序列

	/*
        动态规划：解题思路
            1. 定义一个二维数组dp，其中dp[i][j]表示序列s1的前i个字符和序列s2的前j个字符的最长公共子序列的长度。
            2. 初始化dp数组的第一行和第一列，即dp[0][j]和dp[i][0]均为0，表示空序列与任意序列的最长公共子序列长度为0。
            3. 遍历序列s1和s2，有两种情况
                1) 如果s1[i-1]等于s2[j-1]，dp[i][j]等于dp[i-1][j-1] + 1，表示当前字符是最长公共子序列的一部分
                2) 不等于的话，dp[i][j]等于dp[i-1][j]和dp[i][j-1]的较大值，表示当前字符不是最长公共子序列的一部分。
            4. 最后，dp[m][n]即为序列s1和s2的最长公共子序列的长度，其中m和n分别为序列s1和s2的长度。
    */
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n =  text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (text1.charAt(i-1) == text2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] +1;
                }else {
                    dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
        return dp[n][m];
    }

31. 编辑距离

	/*
        动态规划：
        dp[i][j] 代表 word1 到 i 位置转换成 word2 到 j 位置需要最少步数
            1. 当 word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]；
            2. 当 word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
               其中，dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作。
     */
    public int minDistance (String word1, String word2) {
        int m = word1.length(), n =  word2.length();
        int[][] dp = new int[m + 1][n + 1];
        // 第一行
        for (int j = 1; j <= n; j++) dp[0][j] = dp[0][j - 1] + 1;
        // 第一列
        for (int i = 1; i <= m; i++) dp[i][0] = dp[i - 1][0] + 1;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
            }
        }
        return dp[m][n];
    }

32. 颜色分类

	/*
    双指针：start表示0的起始位置，end表示2的位置，三种情况
        1. nums[i] == 0，交换 start和0，start后移一位
        2. nums[i] == 2，交换 end和2，end前移一位
        3. nums[i] == 1，不用管，因为1就是在中间位置
        结束条件：i>end，即元素已全部遍历
     */
    public void sortColors(int[] nums) {
        int start = 0,end = nums.length-1,i = 0;
        while (i <= end){
            if (nums[i] == 0){
                swap(nums,start++,i++);
            }else if (nums[i] == 2){
                swap(nums,end--,i);
            }else {
                i++;
            }
        }
    }

33. 最小覆盖子串

	/*
        滑动窗口
     */
    public String minWindow(String s, String t) {
        int[] need = new int[128],had = new int[128];
        for (int i = 0; i < t.length(); i++) {
            need[t.charAt(i)]++;
        }
        int l = 0, r = -1,minLen = s.length()+1, ansL = -1, ansR = -1;
        int sLen = s.length();
        while (r++ < sLen) {
            if (r < sLen && need[s.charAt(r)] > 0)
                had[s.charAt(r)]++;
            while (check(need,had) && l <= r) {
                if (r - l + 1 < minLen) {
                    minLen = r - l + 1;
                    ansL = l;
                    ansR = l + minLen;
                }
                // 去除重复的字符
                if (need[s.charAt(l)] > 0)
                    had[s.charAt(l)]--;
                ++l;
            }
        }
        return ansL == -1 ? "" : s.substring(ansL, ansR);
    }
    private boolean check(int[] need, int[] have) {
        for (int i = 0; i < need.length; i++) {
            if (need[i] >have[i]) return false;
        }
        return true;
    }

34. 字集

	// 递归 
	public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        LinkedList<Integer> temp = new LinkedList<>();
        dfs(nums,0,res,temp);
        return res;
    }

    void dfs(int[] nums,int k,List<List<Integer>> list,LinkedList<Integer> temp){
        list.add(new ArrayList<>(temp));
        for (int i = k; i < nums.length; i++) {
            temp.add(nums[i]);
            dfs(nums,i+1,list,temp);
            temp.removeLast();
        }
    }

35. 单词搜索

	/*
        思路：
            递归深搜，每个元素都可以为起点
            每个起点都面临上下左右四种选择，所以要判断一下边界和是否访问
            剪枝：记录下标，只对那些满足要求的元素进行移动
     */
    public boolean exist(char[][] board, String word) {
        char[] wordChars = word.toCharArray();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfs(board,i,j,0,wordChars)) return true;
            }
        }
        return false;
    }
   public boolean dfs(char[][] board,int r,int c,int k,char[] wordChars){
        // 边界
       if (r < 0 || r>= board.length || c < 0 || c >= board[0].length || board[r][c] != wordChars[k]){
           return false;
       }
       if (k == wordChars.length-1){
           return true;
       }
       // 修改已访问
       board[r][c] = '.';
       // 上下左右移动
       boolean answer = dfs(board,r-1,c,k+1,wordChars) || dfs(board,r+1,c,k+1,wordChars) ||
               dfs(board,r,c-1,k+1,wordChars) || dfs(board,r,c+1,k+1,wordChars);
       // 回溯
       board[r][c] = wordChars[k];
       return answer;
   }

36. 柱状图中的最大矩形

	public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        // 保存左侧下标
        int[] left = new int[n];
        // 保存右侧下标
        int[] right = new int[n];
        Arrays.fill(right, n);

        Deque<Integer> mono_stack = new ArrayDeque<>();
        for (int i = 0; i < n; ++i) {
            // 栈不为空并且上一个元素大于当前元素
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                right[mono_stack.peek()] = i;
                mono_stack.pop();
            }
            left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
            mono_stack.push(i);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }

37. 从前序与中序遍历序列构造二叉树

	/*
		定位中间元素，拆分左右先序和中序数组进行递归
	*/
	private static int find(int[] array, int v){
        for (int i=0;i<array.length;i++){
            if (array[i] == v){
                return i;
            }
        }
        return -1;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length==0){
            return null;
        }
        //1、根据前序，找到根的值，并且创建根节点
        int rootValue = preorder[0];
        TreeNode root = new TreeNode(rootValue);

        //2、在中序中找到根的值所在的下标
        int leftIndex = find(inorder,rootValue);

        //3、切出左子树的前序和中序
        int[] leftPreorder = Arrays.copyOfRange(preorder,1,1+leftIndex);
        int[] leftInorder = Arrays.copyOfRange(inorder,0,leftIndex);
        root.left = buildTree(leftPreorder,leftInorder);

        //4、切出右子树的前序和中序
        int[] rightPreorder = Arrays.copyOfRange(preorder,1+leftIndex,preorder.length);
        int[] rightInorder = Arrays.copyOfRange(inorder,leftIndex+1,preorder.length);
        root.right = buildTree(rightPreorder,rightInorder);
        return root;
    }

38. 最大矩形

	// 不会

39. 二叉树中序遍历

	// 1. 递归法
	public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }
    void inorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        inorder(root.left, list);
        list.add(root.val);
        inorder(root.right, list);
    }
	
	// 2. 迭代法
	public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (stack.size() >0 || root != null){
            if (root != null){
                stack.push(root);
                root = root.left;
            }else {
                TreeNode node = stack.pop();
                res.add(node.val);
                root = node.right;
            }

        }
        return res;
    }

40. 不同的二叉搜索树

	/*
	 	中序遍历：二叉搜索树中序遍历为升序，所以比较上个元素的值和当前元素的值即可
	*/
	long longMin = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        if (!isValidBST(root.left)) return false;
        if (longMin >= root.val) return false;
        longMin = root.val;
        return isValidBST(root.right);
    }

41. 对称二叉树

	/*
		思路：直接递归判断左右结点的值是否相同，需要注意的是当 结点为null的时候有两种情况
			1. 两个结点都为null，返回 true
			2. 两个结点其中一个为null，返回false
	*/
	public boolean isSymmetric(TreeNode node) {
        return checkSymmetric(node.left, node.right);
    }
    private boolean checkSymmetric(TreeNode left, TreeNode right) {
        if (left == null || right == null) return left == right;
        if (left.val != right.val) return false;
        return checkSymmetric(left.right, right.left) && checkSymmetric(left.left, right.right);
    }

42. 二叉树的层序遍历

	/*
		宽搜即可，注意返回结果每层为一个集合，所以记录一下每层结点的数量用for循环去处理
	*/
	public List<List<Integer>> levelOrder(TreeNode root) {
        ArrayList<List<Integer>> answer = new ArrayList<>();
        if (root == null){
            return answer;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            List<Integer> item = new ArrayList<>();
            int currentSize = queue.size();
            for (int i = 0; i < currentSize; i++) {
                TreeNode node = queue.poll();
                if (node == null) continue;
                item.add(node.val);
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            answer.add(item);
        }
        return answer;
    }

43. 二叉树的最大深度

	// 递归
	public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(maxDepth(root.right),maxDepth(root.left))+1;
    }

44. 二叉树展开为链表

	/* 解法1：
        暴力解：先序遍历，将所有元素保存到集合中，遍历集合设置左节点为 null

        树中结点数在范围 [0, 2000] 内
        -100 <= Node.val <= 100
    */
	public void flatten(TreeNode root) {
        // 为空判断
        if (root == null || (root.left == null && root.right == null)){
            return;
        }
        LinkedList<TreeNode> result = new LinkedList<>();
        // 先序遍历添加到result中
        getFirst(root,result);
        TreeNode head = result.get(0);
        for (int i = 1; i < result.size(); i++) {
            head.left = null;
            head.right = result.get(i);
            head = head.right;
        }
    }

    private void getFirst(TreeNode root, LinkedList<TreeNode> result) {
        // 结束
        if (root == null) return;
        result.add(root);
        if (root.left != null) getFirst(root.left,result);
        if (root.right != null) getFirst(root.right,result);
    }
	
	// 解法2，将左子结点转移到右子节点
	public void flatten(TreeNode root) {
        if(root == null){
            return ;
        }
        flatten(root.left);
        flatten(root.right);
        TreeNode temp = root.right;
        root.right = root.left;
        //记得要将左边置空
        root.left = null;
        //找到树的最右边的节点
        while(root.right != null) root = root.right;
        //把右边的链表接到刚才树的最右边的节点
        root.right = temp;
    }

45. 买卖股票的最佳时机

	public int maxProfit(int[] prices){
        int maxAnswer = 0,minTarget = prices[0];
        for (int i = 1; i < prices.length; i++) {
            minTarget = Math.min(minTarget,prices[i]);
            maxAnswer = Math.max(prices[i] - minTarget,maxAnswer);
        }
        return maxAnswer;
    }

46. 二叉树的最大路径和

	/*
		递归计算每个结点的贡献度
	*/
	public int maxPathSum(TreeNode root) {
        dfs(root);
        return maxSum;
    }
    private void dfs(TreeNode node){
        if (node == null){
            return;
        }
        dfs(node.left);
        dfs(node.right);
        // 左子结点贡献值
        int left = node.left == null?0:node.left.val;
        // 右子节点贡献值
        int right = node.right == null ? 0 : node.right.val;
        // 计算当前最大值
        maxSum = Math.max(node.val + left + right,maxSum);
        // 当前结点的值为 max(0，当前结点，当前结点+左子结点，当前结点+右子节点)
        node.val = Math.max(node.val,node.val+Math.max(left,right));
        node.val = Math.max(0, node.val);
    }

47. 最长连续序列

public int longestConsecutive(int[] nums) {
        if (nums.length < 1){
            return 0;
        }
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int currentLen = 0,maxLen = 0;
        for (Integer num : set) {
            // 去重
            if (!set.contains(num-1)){
                while (set.contains(num+1)){
                    num += 1;
                    currentLen++;
                    maxLen = Math.max(currentLen,maxLen);
                }
                currentLen = 0;
            }
                
        }
        return maxLen+1;
    }

48. 只出现一次的数值

	// 异或运算，相同为0，不同为1
	public int singleNumber(int[] nums) {
        int num = 0;
        for (int i : nums) {
            num ^= i;
        }
        return num;
    }

49. 单词拆分

	// 第一时间想到的就是递归，但是时间超了
    public boolean wordBreak(String s, List<String> wordDict) {
        for (int i = 0; i < wordDict.size(); i++) {
            String str = wordDict.get(i);
            // 确定开头字符串
            if (dfs(str,wordDict,s,0)){
                return true;
            }
        }
        return false;
    }
    private boolean dfs(String result,List<String> wordDict,String s,int index){
        // 边界
        if (result.equals(s)){
            return true;
        }
        if (s.startsWith(result) && index < wordDict.size()){
            for (int i = index; i < wordDict.size(); i++) {
                String nowStr = result+wordDict.get(i);
                if (dfs(nowStr,wordDict,s,index) || dfs(result,wordDict,s,index+1)){
                    return true;
                }
            }
        }
        return false;
    }

	// 2. 修改为动态规划，截取字符串并使用哈希表判断包不包含截取的字符串
	public boolean wordBreak(String s, List<String> wordDict){
        Set<String> set = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        for (int r = 1; r <= s.length(); r++) {
            for (int l = 0; l < r; l++) {
                if (dp[l] && set.contains(s.substring(l,r))){
                    dp[r] = true;
                }
            }
        }
        return dp[s.length()];
    }
	

50. 环形链表

	// 1. 双指针
	public boolean hasCycle(ListNode head) {
        ListNode slow = head,fast = head;
        while (slow != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast){
                return true;
            }
        }
        return false;
    }
    // 2. hash表
    public boolean hasCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while (head!=null){
            set.add(head);
            ListNode next = head.next;
            if (next != null && set.contains(next)){
                return true;
            }
            head = next;
        }
        return false;
    }

51. 环形链表2

	// 1. 和上题一样，但空间复杂度为 O(n)
	public boolean hasCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while (head!=null){
            set.add(head);
            ListNode next = head.next;
            if (next != null && set.contains(next)){
                return true;
            }
            head = next;
        }
        return false;
    }
    // 2. 双指针，虽然简单，但是一下子没想出来
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while (true) {
            if (fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }
        fast = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }

52. LRU缓存

	/*
		LRU：最少最近使用
		LFU：最少频率使用
	*/
	class LRUCache {
	    class ListNode {
	        int key;
	        int val;
	        ListNode next;
	        ListNode() {
	        }
	        ListNode(int key,int val) {
	            this.val = val;
	            this.key = key;
	        }
	        ListNode(int val, ListNode next) {
	            this.val = val;
	            this.next = next;
	        }
	    }
    private ListNode listNode;
    private int capacity;
    private int size = 0;
    public LRUCache(int capacity) {
        this.capacity = capacity;
    }
    public ListNode getNode(int key) {
        if (listNode == null) return null;
        ListNode current = listNode.next,pre = listNode;
        if (pre.key == key) return pre;
        while (current != null){
            if (current.key == key){
                pre.next = current.next;
                current.next = listNode;
                listNode = current;
                return current;
            }
            pre = current;
            current = current.next;
        }
        return null;
    }
    public int get(int key){
        ListNode node = getNode(key);
        return node == null ? -1 : node.val;
    }
    public void put(int key, int value) {
        ListNode node = getNode(key);
        if (node != null){
            node.val = value;
            return;
        }
        size++;
        ListNode newNode = new ListNode(key,value);
        if (listNode == null){
            listNode = newNode;
        }else {
            newNode.next = listNode;
            listNode = newNode;
        }
        if (size == capacity+1){
            size = capacity;
            // 删除尾结点
            ListNode pre = listNode,current = listNode.next;
            while (current.next != null){
                pre = current;
                current = current.next;
            }
            pre.next = null;
        }
    }
}

53. 排序链表

	
	public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode fast = head.next, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode tmp = slow.next;
        slow.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(tmp);
        ListNode h = new ListNode(0);
        ListNode res = h;
        while (left != null && right != null) {
            if (left.val < right.val) {
                h.next = left;
                left = left.next;
            } else {
                h.next = right;
                right = right.next;
            }
            h = h.next;
        }
        h.next = left != null ? left : right;
        return res.next;
    }

54. 乘积最大的连续子数组

	/* 动态规划
	记录乘积最大值和最小值
	两种情况：
		1. 当前值 < 0，最小值变最大值
		2. 当前值 >= 0，不变
	*/
	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;
    }

55. 最小栈

// 辅助栈
public class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> min_stack;
    public MinStack() {
        stack = new Stack<>();
        min_stack = new Stack<>();
    }
    public void push(int x) {
        stack.push(x);
        if(min_stack.isEmpty() || x <= min_stack.peek())
            min_stack.push(x);
    }
    public void pop() {
        if(stack.pop().equals(min_stack.peek()))
            min_stack.pop();
    }
    public int top() {
        return stack.peek();
    }
    public int getMin() {
        return min_stack.peek();
    }
 }

56. 相交链表

	public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA, B = headB;
        while (A != B) {
            A = A != null ? A.next : headB;
            B = B != null ? B.next : headA;
        }
        return A;
    }

57. 多数元素

	/*
        方法1：排序，直接返回中间下标元素
        方法2：计数，摩尔投票法，票数正负抵消
     */
    public int majorityElement(int[] nums) {
        int result = 0,answer = 0;
        for (int num : nums) {
            if (result == 0) answer = num;
            result += num == answer ? 1 : -1;
        }
        return answer;
    }

58. 打家劫舍

	/*
        动态规划：[1,2,3,1]
            设可以偷到的最大金额为 f(n)
                1. 当数组只有一个元素时，即 f(1) = 1
                2. 当数组只有两个元素时，即 f(2) = 2
                3. ...，f(3) = max(3+1，f(1))
                n. ...，f(n) = max(n + f(n-2)，f(n-1))
     */
    public int rob(int[] nums) {
        int[] dp = new int[nums.length+1];
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i <= nums.length; i++) {
            dp[i] = Math.max(nums[i-1]+dp[i-2],dp[i-1]);
        }
        return dp[nums.length];
    }

59. 岛屿数量

	/*
		深搜往死搜就完了
		每一个位置只会出现 '0' '1'，也就意味着出现了 ‘1’肯定就会出现岛屿
		所以对为‘1’位置的元素进行连通性检测并把检测到的'1'改为 '0',
	*/
	public int numIslands(char[][] grid) {
        int answer = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1'){
                    dfs(grid,i,j);
                    answer++;
                }
            }
        }
        return answer;
    }
    void dfs(char[][] grid,int i,int j){
        if (i < 0 || i>=grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') return;
        grid[i][j] = '0';
        dfs(grid,i+1,j);
        dfs(grid,i-1,j);
        dfs(grid,i,j+1);
        dfs(grid,i,j-1);
    }

60. 反转链表

	public ListNode reverseList(ListNode head) {
        ListNode p = null,current = head;
        while (current != null) {
            ListNode temp = current.next;
            current.next = p;
            p = current;
            current = temp;
        }
        return p;
    }

61. 课程表

	/*
	 拓扑排序
	*/
	public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> list = new ArrayList<>(numCourses);
        for (int i = 0; i < numCourses; i++) {
            list.add(new ArrayList<>());
        }
        // 设置路径
        for (int i = 0; i < prerequisites.length; i++) {
            list.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }
        int[] flag = new int[numCourses];
        for (int i = 0; i < list.size(); i++) {
            if (!f(list,flag,i)){
                return false;
            }
        }
        return true;
    }
    public boolean f(List<List<Integer>> list,int[] flag,int index){
        if (flag[index] == -1) return true;
        if (flag[index] == 1) return false;
        flag[index] = 1;
        for (Integer j : list.get(index)) {
            if (!f(list,flag,j)){
                return false;
            }
        }
        flag[index] = -1;
        return true;
    }

62. 实现前缀树

	// 1.（不推荐）哈希表暴力直接过

	import java.util.HashSet;
	import java.util.Set;

	class Trie {
	    private static Set<String> set;
	    public Trie() {//初始化前缀树对象。
	        set = new HashSet<>();
	    }
	
	    public void insert(String word) {//向前缀树中插入字符串 word 。
	        set.add(word);
	    }
	
	    public boolean search(String word) {//如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
	        return set.stream().filter(e -> e.equals(word)).count() > 0;
	    }
	
	    public boolean startsWith(String prefix) {//如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
	        return set.stream().filter(e -> e.startsWith(prefix)).count() > 0;
	    }
	}
// --------------------------方法2-----------------------------

/*
    记录插入的每一个字符，isEnd记录结束位置，查询时判断每个字符是否存在
 */
	class Trie {
	    private Trie[] children;
	    private boolean isEnd;
	
	    public Trie() {
	        children = new Trie[26];
	        isEnd = false;
	    }
	
	    public void insert(String word) {
	        Trie node = this;
	        // aab  001
	        for (int i = 0; i < word.length(); i++) {
	            char ch = word.charAt(i);
	            int index = ch - 'a';
	            if (node.children[index] == null) {
	                node.children[index] = new Trie();
	            }
	            node = node.children[index];
	        }
	        node.isEnd = true;
	    }
	
	    public boolean search(String word) {
	        Trie node = searchPrefix(word);
	        return node != null && node.isEnd;
	    }
	
	    public boolean startsWith(String prefix) {
	        return searchPrefix(prefix) != null;
	    }
	
	    private Trie searchPrefix(String prefix) {
	        Trie node = this;
	        for (int i = 0; i < prefix.length(); i++) {
	            char ch = prefix.charAt(i);
	            int index = ch - 'a';
	            if (node.children[index] == null) {
	                return null;
	            }
	            node = node.children[index];
	        }
	        return node;
	    }
	}