算法.md · criustt/麻瓜张的成长之路

1.两数之和

https://leetcode.cn/problems/two-sum/description/

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

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

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

解法1：两次遍历将数据以及下标放进map中，第二次遍历查询下标然后返回

解法2: 实际上可以通过一次遍历，在存下标的同时检查 map中是否包含配对的数据，如果包含则可以直接返回

class Solution {
    public int[] twoSum(int[] nums, int target) {
       //创建一个新数组，存储目标元素的下标
        int[] newArr = new int[]{-1,-1};
        
        //第一次遍历：将数组中的元素存储进哈希表中
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            if(map.get(target-nums[i]) != null){
                return new int[]{i,map.get(target-nums[i])};
            }
            map.put(nums[i], i);
        }
         return new int[]{0,0};
    }
}

2.两数相加

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

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

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

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

https://leetcode.cn/problems/add-two-numbers/description/

解法：这个跟加法一样，2+5 = 7， 4+6 = 10 （需要进位1）3+4+进位 = 8，需要特殊处理的地方就是进位标志参与计算当两个节点都结束后，如果有进位的话则需要单独处理一下

/**
 * 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 pre = new ListNode(-1);
           ListNode node = pre;
           int carry = 0;
           while(l1!=null||l2!=null){
               int x = l1==null?0:l1.val;
               int y = l2==null?0:l2.val;
               int sum = x+y+carry;
               carry = sum/10;
               sum = sum%10;
               node.next = new ListNode(sum);
               node = node.next;
               if(l1!=null) l1 = l1.next;
               if(l2!=null) l2 = l2.next;
           }//对进位进行处理否则会少一位
           if(carry==1){
               node.next = new ListNode(carry); 
           }
           return pre.next;
    }
}

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

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

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/

解法1：用set来检验是否重复，然后循环比较，但是没有跳过重复的元素

class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[] array = s.toCharArray();
        int res = 0;
        HashSet<String> set = new HashSet<>();
         for(int i=0;i<array.length && (array.length-i >=res);i++){
             set = new HashSet<>();
             set.add(String.valueOf(array[i]));
             int j=i+1;
             for(j=i+1;j<array.length;j++){
                if(set.contains(String.valueOf(array[j]))){
                    break;
                } 
                set.add(String.valueOf(array[j]));
             }
            res = Math.max(j-i,res);
         }
        return res;
    }
}

解法2：设置两个指针，一个为i从头到尾，一个ed从0到尾开始，i的作用时计算起始长度，ed的作用是检查是否有重复元素，当我们遇到重复元素的时候，可以计算一次最大值，然后将重复元素剔除，在检查i+1是否有重复元素，如果没有那么ed执行++

class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[] array = s.toCharArray();
        int res = 0;
        //判断是否有重复元素
        HashSet<Character> set = new HashSet<>();
        //ed从零开始为了防止整个字符串都没有异常值
        int ed = 0;
        //i作为起始坐标开始递增
         for(int i=0;i<array.length && (array.length-i >=res);i++){
             //如果发现i重复，那么就将跳出循环，否则将ed元素 放入set中
            while(ed<array.length && !set.contains(array[ed])){
                set.add(array[ed]);
                ed++;
            }
             //计算最大值
            res = Math.max(ed-i,res);
             //移除i元素，因为下一次长度的产生不需要前一次i元素的参与，否则会影响后续计算
            set.remove(array[i]);
         }
        return res;
    }
}

1785. 构成特定和需要添加的最少元素

给你一个整数数组 nums ，和两个整数 limit 与 goal 。数组 nums 有一条重要属性：abs(nums[i]) <= limit 。

返回使数组元素总和等于 goal 所需要向数组中添加的 最少元素数量 ，添加元素 不应改变 数组中 abs(nums[i]) <= limit 这一属性。

注意，如果 x >= 0 ，那么 abs(x) 等于 x ；否则，等于 -x 。

https://leetcode.cn/problems/minimum-elements-to-add-to-form-a-given-sum/description/

class Solution {
    public int minElements(int[] nums, int limit, int goal) {
        int sum = 0;
        int step = 0;
        for(int item:nums){
            sum+=item;
        }
        int re = Math.abs(goal - sum);
        step = re/limit + (re%limit == 0? 0:1);
        return step;
    }
}

有问题，会溢出，变量改成long就可以

class Solution {
    public int minElements(int[] nums, int limit, int goal) {
        long sum = 0;
        long step = 0;
        for(int item:nums){
            sum+=item;
        }
        long re = Math.abs(goal - sum);
        step = re/limit + (re%limit == 0? 0:1);
        
        return (int)step;
    }
}

criustt / 麻瓜张的成长之路

1.两数之和

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

1785. 构成特定和需要添加的最少元素

简介

发行版

贡献者

近期动态

criustt / 麻瓜张的成长之路 .gitee-modal { width: 500px !important; }

1.两数之和

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

1785. 构成特定和需要添加的最少元素

简介

发行版

贡献者

近期动态

搜索帮助

criustt / 麻瓜张的成长之路