By的博客
0%

力扣

发表于 更新于 分类于

求职在即，把自己在LeetCode上的刷题做一个笔记。

下面为本人在LeetCode上面刷的题目笔记，给出所有代码为本人提交Accepted后记录。

将有序数组转换为二叉搜索树

题目描述

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

解题思路

题中说了要转换为一棵高度平衡的二叉搜索树，并且数组又是排过序的，这就好办了，我们可以使用递归的方式，每次取数组中间的值比如m作为当前节点，m前面的值作为他左子树的结点值，m后面的值作为他右子树的节点值。所得结果不唯一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums==null){
            return null;
        }
        return sortedArrayToBST(nums,0,nums.length-1);    
    }

    public TreeNode sortedArrayToBST(int nums[],int start,int end){
        if(start>end){
            return null;
        }
        int mid=(start+end)>>1;
        TreeNode root=new TreeNode(nums[mid]);
        root.left=sortedArrayToBST(nums,start,mid-1);
        root.right=sortedArrayToBST(nums,mid+1,end);
        return root;
    }
}

图解
Java递归遍历

两数之和

题目描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

解题思路

暴力解法时间复杂度为n平方，使用哈希表我们可以一次完成。在进行迭代并将元素插入到表中的同时，并检查表中是否已经存在当前元素所对应的目标元素。如果它存在，那我们已经找到了对应解，并将其返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map map=new HashMap<>();
        for(int i=0;i
            int temp=target-nums[i];
            if(map.containsKey(temp)){
                return new int[]{map.get(temp),i};
            }
            map.put(nums[i],i);
        }

        throw new IllegalArgumentException("No two sum solution"); //抛出不合法的参数异常
    }
}

通配符匹配

题目描述

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。

解题思路

动态规划，注意细节

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public boolean isMatch(String s, String p) {
        int lens=s.length(),lenp=p.length();
        boolean[][] dp=new boolean[lenp+1][lens+1];
        dp[0][0]=true; //表示空串是匹配的。
        for(int i=1;i<=lenp;i++){
            if(p.charAt(i-1)!='*'){
                break;  处理一下匹配串 p 以若干个星号开头的情况。因为星号是可以匹配空串的：
            }
            dp[i][0]=true;
        }

        for(int i=1;i<=lenp;i++){
            for(int j=1;j<=lens;j++){
                if(p.charAt(i-1)==s.charAt(j-1)||p.charAt(i-1)=='?'){
                    dp[i][j]=dp[i-1][j-1];
                }else if(p.charAt(i-1)=='*'){
                    dp[i][j]=dp[i-1][j] | dp[i][j-1];  //需要匹配‘*’ | 不需要匹配‘*’
                }
            }
        }

        return dp[lenp][lens];
    }
}

题目描述

解题思路

1
2


题目描述

解题思路

1
2


题目描述

解题思路

1
2


题目描述

解题思路

1
2


题目描述

解题思路

1
2


题目描述

解题思路

1
2


题目描述

解题思路

1
2


题目描述

解题思路

1
2


题目描述

解题思路

1
2


题目描述

解题思路

1
2


题目描述

解题思路

1
2


题目描述

解题思路

1
2


题目描述

解题思路

1
2


题目描述

解题思路

1
2


题目描述

解题思路

1
2


题目描述

解题思路

1
2


题目描述

解题思路

1
2


题目描述

解题思路

1
2