题目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]-1while (arr[i] > range + 1) { // arr[i] 1 ~ arr[i]-1if (range > Integer.MAX_VALUE - range - 1) {return patches + 1;}//防止越界 已知给的范围一定是整形 如果满足这个条件 就说明再加 就要越界了 会报错 因为它下一步就会让range+range+1range += 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;}