算法小抄.md

算法小抄

两数之和

Map {a[i],i}

字母异位词分组-把排序之后相等的单词放到一个Map里面

char[] chars = str.toCharArray();
Arrays.sort(chars);
String key = Arrays.toString(chars);

数组中最长连续序列

数组放入一个HashSet，如果num-1不存在，在往后遍历，收集答案

for (int num : set) {
            int cur = num;
            // 只有当num-1不存在时，才开始向后遍历num+1，num+2，num+3......
            if (!set.contains(cur - 1)) {
                while (set.contains(cur + 1)) {
                    cur++;
                }
            }
            // [num, cur]之间是连续的，数字有cur - num + 1个
            ans = Math.max(ans, cur - num + 1);
        }
        return ans;

移动零-把数组中非0的元素移动到前面，0移动到后面

使用k=0来表示新数组的下标

int k = 0;
for(int x : nums)
    if(x != 0) nums[k++] = x;
while(k < nums.length)  nums[k++] = 0;

盛最多水的容器

三数之和

数组排序，k，i，j 其中遍历k，sum小了就增大i，sum大了就缩写j 注意 去重

		   int i = k+1;
            int j = nums.length - 1;
            while(i<j){
                int sum = nums[k] +  nums[j] + nums[i];
                if(sum > 0){
                    j --;
                }else if(sum<0){
                    i++;
                }else{
                    result.add(List.of(nums[k],nums[j],nums[i]));
                    i++;
                    j--;
                    while(i<j&&nums[i]==nums[i-1]) i++;
                    while(i<j&&nums[j] == nums[j+1]) j--;
                }
            }

无重复最长子串

双指针-使用一个boolen表示指针窗口有没有字符

boolean[] has = new boolean[128];
int left = 0;
int res = 0;
for(int right = 0; right<str.length;right++){
    char cur = str[right];
    // 如果右节点已经重复，移动左节点
    while(has[cur]){
        has[str[left++]] = false;
    }
    //当前节点加入has 
    has[cur] = true;
    res = Math.max(res,right-left+1);
}

找到所有字符串中的字母异位词

// l 和 r 分别表示滑动窗口的左右边界
int l = 0;
for(int r = 0; r < s.length(); r++){
    // 更新当前窗口中字符的计数数组
    cnt[s.charAt(r) - 'a']--;
    // 从左侧收缩窗口，直到当前字符的计数在限定范围内
    while(cnt[s.charAt(r) - 'a'] < 0){
        cnt[s.charAt(l) - 'a']++;
        l++;
    }
    // 检查当前窗口大小是否等于字符串 p 的大小
    if(r - l + 1 == p.length()){
        ans.add(l);
    }
}
return ans;

和为k的子数组

滑动窗口-双指针

 for(int right = 0; right<nums.length; right++){
            sum += nums[right];
            while(sum >= k && left<=right){
                if(sum == k){
                    res++;
                }             
                sum-=nums[left++];
            }
        }
        return res;

滑动窗口最大值

最小覆盖子串

覆盖&最小 没有覆盖 left++ s[left]>t[left] 都会移动

for(int right = 0; right<s.length();right++){
            sMap[s.charAt(right)]++;
            //left想要右移
            while(left<right){
                char c = s.charAt(left);
                //第一种情况，left指向的字母，t里面没有，直接移动
                if(tMap[c]==0){
                    left++;
                //第二种情况，left指向的字母，多余t里面的个数
                }else if(sMap[c]>tMap[c]){
                    sMap[c]--;
                    left++;
                }else{
                    break;
                }
            }
            //开始收集答案
            if(isWindow(sMap,tMap)){
                int len  = right - left +1;
                if(res.equals("")||res.length()>len){
                    res = s.substring(left,right+1);
                }
            }

        }

补码转为十进制

public class BinaryToDecimal {

    public static int toDecimal(int[] binary) {
        int length = binary.length;
        boolean isNegative = (binary[0] == 1); // 检查最高位，判断是否为负数

        int decimal = 0;
        
        // 如果是负数，将补码转换成原码
        if (isNegative) {
            // 先将补码取反
            for (int i = 0; i < length; i++) {
                binary[i] = (binary[i] == 0) ? 1 : 0;
            }

            // 然后将取反后的数组加1
            boolean carry = true;
            for (int i = length - 1; i >= 0; i--) {
                if (carry) {
                    if (binary[i] == 1) {
                        binary[i] = 0;
                    } else {
                        binary[i] = 1;
                        carry = false;
                    }
                }
            }
        }

        // 计算十进制值
        for (int i = 0; i < length; i++) {
            decimal += binary[i] * Math.pow(2, length - 1 - i);
        }

        // 如果是负数，需要将十进制值变为负数
        return isNegative ? -decimal : decimal;
    }

    public static void main(String[] args) {
        int[] binary = {1, 1, 0, 1}; // 示例数组，补码表示 -3
        int decimal = toDecimal(binary);
        System.out.println("十进制值为: " + decimal);
    }
}