力扣第一周错题集

力扣的错题以及解法个人总结

• LeetCode1：两数之和
• LeetCode20：有效的括号
• LeetCode21：合并两个有序链表
• LeetCode121：买卖股票的最佳时机
• LeetCode125：验证回文串
• LeetCode226：翻转二叉树
• LeetCode242：有效的字母异位词
• LeetCode704：二分查找
• LeetCode733：图像渲染
• LeetCode53：最大子数组和
• LeetCode235：二叉搜索树的最近公共祖先
• LeetCode力扣110：平衡二叉树
• LeetCode141：环形链表

LeetCode1：两数之和
解法一：暴力破解
直接用两个for循环，把一个数和它后面所有的数逐一比较，相加等于target的值反复对应的下标

//暴力解法
    public int[] twoSum(int[] nums, int target) {
    
        int[] index = new int[2];
        for(int i=0;i<nums.length;i++){
    
            for(int j=i+1;j<nums.length;j++){
    
                if(nums[i]+nums[j]==target){
    
                    index[0] = i;
                    index[1] = j;
                }
            }
        }
        return index;
    }

解法二：利用hashmap来处理
先遍历数组的每一数，且每次把当前数的补数作为key，下标作为value存如hashmap中，然后每次循环时判断当前数的补数是否存在与hashmap中，存在的话返回当前下标和目标map的value值

    public int[] twoSum2(int[] nums, int target) {
    
        int[] indexs = new int[2];

        //建立k-v , 一一对应的哈希表
        HashMap<Integer,Integer> hash = new HashMap<Integer,Integer>();
        for(int i = 0;i<nums.length;i++){
    
            if(hash.containsKey(nums[i])){
    
                indexs[0] = i;
                indexs[1] = hash.get(nums[i]);
                return indexs;
            }
            //将数据存入key为补数，value为下标
            hash.put(target-nums[i],i);
        }
        return indexs;
    }

HashMap的一些用法

• HashMap.containsKey (Object key)，如果 hashMap 中存在指定的 key 对应的映射关系返回 true，否则返回 false。 检查key是否存在
• HashMap.get(key)，通过key来获取相应的value
• HashMap.put(key,value)想hashMap中添加元素

LeetCode20：有效的括号
解法一：
使用栈的典型例题，先创建栈，把字符串转换为字符数组进行遍历，先把第一个元素对应的元素放进栈，后面的元素是左括号的时候就存进栈，是右括号类型的就会先判断栈是否为空或弹出一个栈顶的元素和当前值进行比较不相等的话就直接返回false，直到遍历完整个字符数组，直接返回stack.isEmpty，为空时返回true说明字符串完全匹配，返回false则说明字符串不符合规范。

   public static boolean isValid(String s) {
    
        Stack<Character> stack=new Stack<Character>();
        for(char c : s.toCharArray()){
    
            if(c=='('){
    
                stack.push(')');
            }else if(c=='['){
    
                stack.push(']');
            }else if(c=='{'){
    
                stack.push('}');
            }else if(stack.isEmpty()||c!=stack.pop()){
    
                return false;
            }
        }
        return stack.isEmpty();
    }

• string.toCharArray（）：将字符串对象中的字符转换为一个字符数组
• stack.push(E item) 入栈，将项目推送到此堆栈的顶部
• stack.pop 出栈，删除此堆栈顶部的对象，并将该对象作为此函数的值返回
• stack.peek 栈顶元素，查看此堆栈顶部的对象，而不从堆栈中删除它
• stack.isEmpty 判读此堆栈是否为空

LeetCode21：合并两个有序链表
解法一：构建新链表，通过递归将两个链表的值较小的那个插入新链表中。
对比两个链表把较小的值插入新链表中，最后得到的就是一个升序序列

 if(list1 == null) {
    return list2;}
        if(list2 == null) {
    return list1;}
        ListNode listNode = new ListNode();
        if(list1.val > list2.val){
    
            listNode.val = list2.val;
            list2 = list2.next;
        }else{
    
            listNode.val = list1.val;
            list1 = list1.next;
        }
        ListNode tmp = mergeTwoLists(list1,list2);
        //递归查找
        listNode.next = tmp;
        return listNode;

• list.val指的的当前结点的值
• list.next指的是指向链表下一个结点的指针

LeetCode121：买卖股票的最佳时机
方法一：DP思想
1.记录之前买入的最小值
2.计算出今天之前最小值买入，今天卖出的获利，也就是今天卖出的最大获利
3.比较每天的最大获利，取最大值即可

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

• 比较最大（小）值的方法Math.max(int a,int b) or Math.min(int a,int b)
• 数组中找最大值

 int max=arr[0]
 for(int i=0;i<arr.length;i++){
    
         max=arr[i] > max ? arr[i] : max;
 }

LeetCode125：验证回文串
方法一：双指针比较
先将字符串放进的StringBuffer区域，然后循环i<=j(i是头指针i=0，j是为指针j=sb.length()-1)，两边向中间靠逐一比较指针指向的值直到退出循环，如果都相等就返回true，为回文串，如果有不相等就返回false，该字符串不是回文串。

   public boolean isPalindrome(String s) {
    
        StringBuffer sb = new StringBuffer();
        for(int i=0;i>s.length();i++){
    
            char temp=s.charAt(i);
            if(temp >= '0' && temp <= '9'){
    
                sb.append(temp);
            }else if(temp > 'a' && temp <= 'z'){
    
                sb.append(temp);
            }else if(temp >= 'A' && temp <='Z'){
    
                sb.append((char)(temp+32));
            }
        }
        int i=0,j=sb.length()-1;
        while(i<=j){
    
            if(sb.charAt(i) == sb.charAt(j)){
    
                i++;
                j--;
            }else{
    
                return false;
            }
        }
        return true;
    }

• char类型的数据参与运行会先转换成int类型（ASCII编码表‘A’对应十进制65，‘a’对应的十进制为97），所以(char)(temp+32)为大写转换成小写，即’A’转换成’a’
• 对字符串操作的方法，应该把字符串s存入StringBuffer区再进行操作