DAY22

雨点打透心脏的1/2处 2023-10-14 19:18 61阅读 0赞

## 题目1 ##

给定一个有序的正数数组arr和一个正数range，如果可以自由选择arr中的数字,想累加得到1-range范围上所有的数，返回arr最少还缺几个数。  
\[举例\]  
arr. = \{1.2,3,7\}，range = 15想累加得到1-15范围上所有的数，arr 还缺14这个数，所以返回1 arr=  
\{1,5,7\}，range= 15想累加得到1~15范围上所有的数，arr 还缺2和4，所以返回2

public static int minPatches2(int[] arr, int K) {
    		int patches = 0; // 缺多少个数字
    		int range = 0; // 已经完成了1 ~ range的目标
    		for (int i = 0; i != arr.length; i++) {
    			// 1~range
    			// 1 ~ arr[i]-1
    			while (arr[i] > range + 1) { // arr[i] 1 ~ arr[i]-1
    
    				if (range > Integer.MAX_VALUE - range - 1) {
    					return patches + 1;
    				}//防止越界 已知给的范围一定是整形 如果满足这个条件 就说明再加 就要越界了 会报错 因为它下一步就会让range+range+1
    
    				range += range + 1; // range + 1 是缺的数字
    				patches++;//啊 懂了 例如 1 2 6 此时range为3 要补到6 我们完全不需要把 4 5补上 补个3 range就到6了
    				if (range >= K) {
    					return patches;
    				}
    			}
    			if (range > Integer.MAX_VALUE - arr[i]) {
    				return patches;//这一步也是 如果range再运算一次 他就溢出了
    			}
    			range += arr[i];
    			if (range >= K) {
    				return patches;
    			}
    		}
    		while (K >= range + 1) {
    			if (K == range && K == Integer.MAX_VALUE) {
    				return patches;
    			}
    			if (range > Integer.MAX_VALUE - range - 1) {
    				return patches + 1;
    			}
    			range += range + 1;
    			patches++;
    		}
    		return patches;
    	}

## 题目2 ##

在一个字符串中找到没有重复字符子串中最长的长度。  
例如: .  
abcabcbb没有重复字符的最长子串是abc,长度为3  
bbbbb，答案是b， 长度为1  
pwwkew.答案是wke,长度是3  
要求:答案必须是子串，"pwke" 是-个子字符序列但不是一-个子字符串。

dp\[i\] 表示以i结尾的最长子串长度  
两个瓶颈 第一个str\[i\]位置上字符出现过的次数

第二个 dp\[i-1\]位置的左边界

这两个瓶颈 取一个最差的

public int lengthOfLongestSubstring(String s) {
    		if(s==null||s.length()==0) {
    			return 0 ;
    		}
    		char [] str = s.toCharArray();
            int [] dp = new int [str.length];
            dp[0] = 1;
            HashMap<Character, Integer> map = new HashMap<Character, Integer>();
            map.put(str[0], 0);
            int max = 1;
            for (int i = 1; i < dp.length; i++) {
                    int left;
    			if(!map.containsKey(str[i])) {
    				left = -1;
    			}else {
    				left = map.get(str[i])+1;
    			}
    			left = Math.max(left, i-dp[i-1]);
    			dp[i] = i-left+1;
    			map.put(str[i], i);
    			max = Math.max(dp[i], max);
    		}
            
            return  max;
        }