[数据结构与算法]LeetCode笔记——8/31-2021

LeetCode笔记——8/31-2021

1. 两数之和（简单）

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

思路：

• 暴力破解法

  • 使用两个for循环，遍历数组进行比较（自己想到的）

• HashMap检验法

  • 利用HashMap的不可重复性，将数组存入哈希表后，用target-当前数值是否在哈希中存在以得到目标

• 双指针法

  • 利用两根指针，一头一尾

/*
 * HashMap检验法
 */
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i<nums.length;i++){
            if(!map.containsKey(target-nums[i])){
                map.put(nums[i],i);
            }else{
                return new int[]{i,map.get(target-nums[i])};
            }
        }
        return null;
    }
}

2. 两数相加（中等）

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

算法分析点：

• 会有进位，再下一次赋值时加入
• 进位突破原来的位数时，需要开辟新节点
• 当两数的位数不一致时，仍然需要相加（+0）
• 结果加上进位才发生进位时（ 原本结果9 + 进位1 = 10在次产生进位）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        
        ListNode end,list;
        end = list = new ListNode();
        int i = 0;
        while(l1!=null||l2!=null||i==1){ // i==1 解决：进位突破原来的位数时，需要开辟新节点

            if(l1!=null){
                i += l1.val;
                l1 = l1.next;
            }
            if(l2!=null){
                i += l2.val;
                l2 = l2.next;
            }

            list.next = new ListNode(i%10);
            list = list.next;

            i = i/10;
        }
        return end.next;
    }
}

3. 无重复字符的最长子串（中等）

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

算法分析：

• 使用HashMap判断重复的字符

我一开始是想着，先按步将要检测的字符存入HashMap中，当再次出现相同字符的时候触发条件，

• 对当前所得子串长度与最长长度进行比较从而得出最终解，
• 重新洗牌 （将Hashmap重洗）

然鹅后面发现有几个特殊用例通过不了 " ","ab","","kwwkpw"

class Solution { // 没通过
   public int lengthOfLongestSubstring(String s) {
       int i = s.length();
       if(s.equals(""))
           return 0;
       int end = 1;
       char[] ch = s.toCharArray();
       
       Map<Character,Character> map ;

       for(int j = 0;j<i-1;j++){
           map = new HashMap<>();
           
           int num = 0;
           for(int k = j;!map.containsKey(ch[k]);){
               map.put(ch[k],ch[k]);
               num++;
               k++;
               if(k>i-j-1)
                break;
           }
           end = Math.max(end,num);
       }
       return end;
   }
}

查看答案后算法分析：

• 使用HashMap/Set查看是否有重复项
• 将寻找最长子串转换为寻找两个相同字符之间最多相隔多少个字符（记得在结果上算上自己）

// 参考后通过写法
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        int num = 0;
        // int end , start; // 定义前后两个指针
        // end = start = 0; 

        char[] ch = s.toCharArray();
        Map<Character,Integer> map = new HashMap<>();
        for(int end = 0,start=0;end<len;end++){
            if(map.containsKey(ch[end])){
                start = Math.max(map.get(ch[end])+1,start); // 用于更换此时重复了的字符位置
            }
            map.put(ch[end],end);// 用于及时更新Map中各个字符的位置
            num = Math.max(num,end-start+1);// 用于找出此时最长的子串
        }
        return num;
    }
}