如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) – 从数据流中添加一个整数到数据结构中。
double findMedian() – 返回目前所有元素的中位数。
示例 1：
输入：
[“MedianFinder”,“addNum”,“addNum”,“findMedian”,“addNum”,“findMedian”]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]
示例 2：
输入：
[“MedianFinder”,“addNum”,“findMedian”,“addNum”,“findMedian”]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]
限制：
最多会对 addNum、findMedian 进行 50000 次调用。
1、插入排序
class MedianFinder { /** initialize your data structure here. */ int size=0; List<Double> list; public MedianFinder() { list=new ArrayList<Double>(); } public void addNum(int num) { //插入排序 //之前的数组已经有序的情况下，时间复杂度为O(n) //查找O(n),插入O(n) int j=0; for(Double i:list){ if(i<num)j++; el break; } list.add(j,(double)num); } public double findMedian() { //时间复杂度为O(1) if(list.size()%2==1)return list.get(list.size()/2); el return (list.get(list.size()/2)+list.get(list.size()/2-1))/2; }}1、堆
class MedianFinder { Queue<Integer> A, B; public MedianFinder() { A = new PriorityQueue<>(); // 小顶堆，保存较大的一半 B = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆，保存较小的一半 } public void addNum(int num) { if(A.size() != B.size()) { A.add(num); B.add(A.poll()); } el { B.add(num); A.add(B.poll()); } } public double findMedian() { return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0; }}作者：jyd
链接：link
来源：力扣（LeetCode）
2、插入排序优化：查找位置改为二分查找，
class MedianFinder { vector<int> store; // resize-able containerpublic: // Adds a number into the data structure. void addNum(int num) { if (store.empty()) store.push_back(num); el store.inrt(lower_bound(store.begin(), store.end(), num), num); // binary arch and inrtion combined } // Returns the median of current data stream double findMedian() { int n = store.size(); return n & 1 ? store[n / 2] : (store[n / 2 - 1] + store[n / 2]) * 0.5; }};作者：z1m
链接： link
来源：力扣（LeetCode）
1、堆
class MedianFinder { /** initialize your data structure here. */ int size=0; Queue<Integer> small,big; public MedianFinder() { small=new PriorityQueue<Integer>((o1,o2)->o2-o1);//较小，大顶堆 big=new PriorityQueue<Integer>();//较大的一半，小顶堆 } public void addNum(int num) { //插入排序 if(small.size()==big.size()){ small.offer(num); big.offer(small.poll()); } el{ big.offer(num); small.offer(big.poll()); } size++; } public double findMedian() { if(size%2==0){ return (double)(small.peek()+big.peek())/2; } el return (double)big.peek(); }}/** * Your MedianFinder object will be instantiated and called as such: * MedianFinder obj = new MedianFinder(); * obj.addNum(num); * double param_2 = obj.findMedian(); */2、插入排序优化：二分查找，O(logn)+O(n)
二分查找目标：第一个>=num的元素x，
即x左边那个元素<num,x本身>=num
3、插入排序优化：边找边移动 O(n)
堆（多练几遍）
插入排序（二分，边找边移动）
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
提示：
1 <= arr.length <= 10^5
-100 <= arr[i] <= 100
class Solution { public int maxSubArray(int[] nums) { int max=Integer.MIN_VALUE,temp=0; for(int i=0;i<nums.length;i++){ temp+=nums[i]; if(nums[i]>temp)temp=nums[i]; if(temp>max){ max=temp;} } return max; }}class Solution { public int maxSubArray(int[] nums) { int res = nums[0]; for(int i = 1; i < nums.length; i++) { nums[i] += Math.max(nums[i - 1], 0); res = Math.max(res, nums[i]); } return res; }}作者：jyd
链接：link
来源：力扣（LeetCode）
class Solution { public int maxSubArray(int[] nums) { int max=nums[0]; for(int i=1;i<nums.length;i++){ nums[i]+=Math.max(nums[i-1],0); max=Math.max(max,nums[i]); } return max; }}动态规划
输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
示例 1：
输入：n = 12
输出：5
示例 2：
输入：n = 13
输出：6
限制：
1 <= n < 2^31
只想到了超时的方法
class Solution { public int countDigitOne(int n) { int result=0,temp=0; for(int i=1;i<=n;i++){ temp=i; while(temp>0){ if(temp%10==1)result++; temp/=10; } } return result; }}感觉就是找规律。。太难找了
class Solution { public int countDigitOne(int n) { int digit = 1, res = 0; int high = n / 10, cur = n % 10, low = 0; while(high != 0 || cur != 0) { if(cur == 0) res += high * digit; el if(cur == 1) res += high * digit + low + 1; el res += (high + 1) * digit; low += cur * digit; cur = high % 10; high /= 10; digit *= 10; } return res; }}2、
class Solution { public int countDigitOne(int n) { return f(n); } private int f(int n ) { if (n <= 0) return 0; String s = String.valueOf(n); int high = s.charAt(0) - '0'; int pow = (int) Math.pow(10, s.length()-1); int last = n - high*pow; if (high == 1) { 中国传说故事 return f(pow-1) + last + 1 + f(last); } el { return pow + high*f(pow-1) + f(last); } }}作者：xujunyi
链接：link
来源：力扣（LeetCode）
class Solution { public int countDigitOne(int n) { int digit=1,res=0; int high=n/10,cur=n%10,low=0; whil向党说句心里话e(n>0){ if(cur==0)res+=high*digit; el if(cur==1)res+=high*digit+low+1; el res+=(high+1)*digit; low+=cur*digit; digit*=10; n/=10; high=n/10;cur=n%10; } return res; }}找规律
数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。
请写一个函数，求任意第n位对应的数字。
示例 1：
输入：n = 3
输出：3
示例 2：
输入：n = 11
输出：0
限制：
0 <= n < 2^31
不会。。。找规律的题好让人绝望啊
0 占第0位
1～9 共9×1 = 9个数字 占位9×1 = 9 位
10～99 共9×10 = 90个数字 占位90×2 = 180 位
100～999 共9×100 = 900个数字 占位900×3 = 2700 位
…
规律是不是很好理解啦，算法的逻辑就是：我们依次算一下占位数字，并不断地累加得到当前的总占位数，并判断和输入n的关系，总占位数小于n的话说明，第n位不在目前的范围內，继续累加；否则，说明在范围，然后找到相应数字返回。
举个例子秒懂：
假设输入n为14，我们想找到第14位：
(1)此时设置当前位置为0的位置 temp=0
(2)占1位的数字有9个: num=9,（1～9,除了0因为temp已设为0了）
(3)占1位 ba=1
(4)我们判断一下，当占1位的数字都走完了，目前一共占到了多少位： temp + num x ba = 0 + 9×1 = 9，说明占1位的数字走完后，当前占到了第9位。(更新temp=temp + num x ba = 9）
(5)和输入的值比较下，9 < 14,说明我们想找的第14位不在当前占1位的数字中。
(6)那就有可能在占2位的数字中，所以这一轮我们看看占2位的数字（10～99）：
每个数字占位 ba = ba + 1 = 2
有多少个数字 num = num x 10 = 90
再回到第（4)步，算一下当占2位的数字也都走完了，目前一共占到了多少位
temp + num x ba = 9 + 90 x 2 = 189
说明当占2位的数字走完后，当前占到了第189位
再回到第5步，发现 189 > 14,说明我们想找到的数字就在10～99之间
此时，循环终止…因为没必要再往下算占3位的情况了
(7)我们知道第14位就在10～99之间的话就很好办了：
前一轮我们知道占1位的数字走完后，占到了第9位，那我们想找的第14位的值也就是9之后的第5位：
14 – 9 = 5位
占两位的数字中（10～99），第一个起始数字是10，（10 = 10的1次方，也就10的(ba-1)次方）
由于10～99这个范围内的数字，都是占ba=2位，
所以 5/2 = 2
10 + 2 = 12，第14位就在数字12里
5%2 = 1，说明第14位就是数字12中的第一个位置值，如果把12当成字符串，那就是下标为0的值
“12”.charAt(1-1) = 1
最终我们找到了这个1
验证下0123456789101112…第14位确实是1
联系上面的思路，带到下面的代码，很好理解啦。
注意大数越界问题，所以这里用long型
class Solution { public int findNthDigit(int n) { if(n<0) return 0; el if(n>=0 && n<=9) return n; el { long m = n; long temp = 0; long ba = 1; long num = 9; char res = '0'; while((temp+ba*num) < m) { temp += ba*num; ba += 1; num *= 10; } long a = (m-temp)/ba; long b = (m-temp)%ba; if(b!=0) { long c = (long) (Math.pow(10, ba-1) + a); res = String.valueOf(c).charAt((int)b-1); }el { long c = (long) (Math.pow(10, ba-1) + a - 1); res = String.valueOf(c).charAt((int)ba-1); } return Integer.parInt(String.valueOf(res)); } }}作者：zhuguangyu
链接：link
来源：力扣（LeetCode）
class Solution { public int findNthDigit(int n) { if(n>=0&&n<=9)return n; long ba=1,addNum=9,preNum=0,num=9;//preNum即下限，num即上限 while(num<n){ ba++; addNum*=10; preNum=num; num+=ba*addNum; } long pianyi=n-preNum; long index=pianyi/ba;//第几个数 long wei=pianyi%ba;//第几位 if(wei==0){ wei=ba;index--;} long number=(long)Math.pow(10,ba-1)+index;//数字 String numberString=number+""; int result=numberString.charAt((int)wei-1)-'0'; return result; }}找规律
有可能越界的地方用Long
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2]
输出: “102”
示例 2:
输入: [3,30,34,5,9]
输出: “3033459”
提示:
0 < nums.length <= 100
说明:
输出结果可能非常大，所以你需要返回一个字符串而不是整数
拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0
感觉我想复杂了。。。。用了桶排序+堆排序
class Solution { public String minNumber(int[] nums) { StringBuilder sb=new StringBuilder(); List<PriorityQueue<Integer>> number=new ArrayList<>(); for(int i=0;i<10;i++)number.add(new PriorityQueue<Integer>(new Comparator<Integer>(){ public int compare(Integer o1,Integer o2){ int a=o1,b=o2; int len1=(a+"").length(),len2=(b+"").length(); if(len1==len2)return a-b; el { return Integer.parInt(a+""+b)-Integer.parInt(b+""+a); } } })); int high=0;//最高位 for(int i=0;i<nums.length;i++){ high=(nums[i]+"").charAt(0)-'0'; number.get(high).offer(nums[i]); } PriorityQueue<Integer> temp=null; for(int i=0;i<10;i++){ temp=number.get(i); if(temp.size()==0)continue; while(!temp.isEmpty())sb.append(""+temp.poll()); } return sb.toString(); }}1、内置
class Solution { public String minNumber(int[] nums) { String[] strs = new String[nums.length]; for(int i = 0; i < nums.length; i++) strs[i] = String.valueOf(nums[i]); Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x)); StringBuilder res = new StringBuilder(); for(String游戏女名 s : strs) res.append(s); return res.toString(); }}2、自己写
class Solution { public String minNumber(int[] nums) { String[] strs = new String[nums.length]; for(int i = 0; i < nums.length; i++) strs[i] = String.valueOf(nums[i]); fastSort(strs, 0, strs.length - 1); StringBuilder res = new StringBuilder(); for(String s : strs) res.append(s); return res.toString(); } void fastSort(String[] strs, int l, int r) { if(l >= r) return; int i = l, j = r; String tmp = strs[i]; while(i < j) { while((strs[j] + strs[l]).compareTo(strs[l] + strs[j]) >= 0 && i < j) j--; while((strs[i] + strs[l]).compareTo(strs[l] + strs[i]) <= 0 && i < j) i++; tmp = strs[i]; strs[i] = strs[j]; strs[j] = tmp; } strs[i] = strs[l]; strs[l] = tmp; fastSort(strs, l, i - 1); fastSort(strs, i + 1, r); }}作者：jyd
链接：link
来源：力扣（LeetCode）
1、
class Solution { public String minNumber(int[] nums) { StringBuilder sb=new StringBuilder(); String[] Nums=new String[nums.length]; for(int i=0;i<nums.length;i++)Nums[i]=nums[i]+""; Arrays.sort(Nums,(o1,o2)->(o1+o2).compareTo(o2+o1)); for(int i=0;i<Nums.length;i++)sb.append(Nums[i]); return sb.toString(); }}2、用String.valueOf()可以大幅提升效率
这是因为每个+号底层都会生成一个StringBuilder对象，
class Solution { public String minNumber(int[] nums) { StringBuilder sb=new StringBuilder(); String[] Nums=new String[nums.length]; for(int i=0;i<nums.length;i++)Nums[i]=String.valueOf(nums[i]); Arrays.sort(Nums,(o1,o2)->(o1+o2).compareTo(o2+o1)); for(int i=0;i<Nums.length;i++)sb.append(Nums[i]); return sb.toString(); }}3、手写快排
class Solution { public String minNumber(int[] nums) { StringBuilder sb=new StringBuilder(); String[] Nums=new String[nums.length]; for(int i=0;i<nums.length;i++)Nums[i]=String.valueOf(nums[i]); quickSort(Nums,0,Nums.length-1); for(int i=0;i<Nums.length;i++)sb.append(Nums[i]); return sb.toString(); } public void quickSort(String[] Nums,int start,int end){ int i=start,j=end; if(start>end)return; String X=Nums[start]; while(i<j){ while(i<j&&(Nums[j]+X).compareTo(X+Nums[j])>=0)j--; if(i<j)Nums[i++]=Nums[j]; while(i<j&&(Nums[i]+X).compareTo(X+Nums[i])<=0)i++; if(i<j)Nums[j--]=Nums[i]; } Nums[i]=X; quickSort(Nums,start,i-1); quickSort(Nums,i+1,end); }}4、堆排序
class Solution { public String minNumber(int[] nums) { StringBuilder sb=new StringBuilder(); PriorityQueue<Integer> pq=new PriorityQueue<>((o1,o2)->(o1.toString()+o2.toString()).compareTo(o2.toString()+o1.toString())); for(int i=0;i<nums.length;i++)pq.offer(nums[i]); int high=0;//最高位 while(!pq.isEmpty())sb.append(pq.poll()); return sb.toString(); }}用String.valueOf()替代 x+””;
因为使用加号时，每个+号底层都会生成一个StringBuilder对象
快速排序
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例 1:
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是”bccfi”, “bwfi”, “bczi”, “mcfi”和”mzi”
提示：
0 <= num < 231
class Solution { public int translateNum(int num) { char[] arr=String.valueOf(num).toCharArray(); ArrayList[] dp=new ArrayList[arr.length]; dp[0]=new ArrayList<Integer>(); dp[0].add(arr[0]-'0'); for(int i=1;i<arr.length;i++){ dp[i]=new ArrayList<Integer>(); for(int j=0;j<dp[i-1].size();j++){ int number= arr[i]-'0'+(int)dp[i-1].get(j)*10; dp[i].add(arr[i]-'0'); if((int)dp[i-1].get(j)!=0&&number<26&&number>=0){ dp[i].add(number); } } } return dp[arr.length-1].size(); }}1、空间优化的动态规划
class Solution { public int translateNum(int num) { String s = String.valueOf(num); int a = 1, b = 1; for(int i = 2; i <= s.length(); i++) { String tmp = s.substring(i - 2, i); int c = tmp.compareTo("10") >= 0 && tmp.compareTo("25") <= 0 ? a + b : a; b = a; a = c; } return a; }}逆序
class Solution { public int translateNum(int num) { String s = String.valueOf(num); int a = 1, b = 1; for(int i = s.length() - 2; i > -1; i--) { String tmp = s.substring(i, i + 2); int c = tmp.compareTo("10") >= 0 && tmp.compareTo("25") <= 0 ? a + b : a; b = a; a = c; } return a; }}2、再次优化的动态规划
class Solution { public int translateNum(int num) { int a = 1, b = 1, x, y = num % 10; while(num != 0) { num /= 10; x = num % 10; int tmp = 10 * x + y; int c = (tmp >= 10 && tmp <= 25) ? a + b : a; b = a; a = c; y = x; } return a; }}作者：jyd
链接： link
来源：力扣（LeetCode）
1、
class Solution { public int translateNum(int num) { char[] arr=String.valueOf(num).toCharArray(); int[] dp=new int[arr.length+1]; dp[0]=1; dp[1]=1; for(int i=2;i<arr.length+1;i++){ int number=(arr[i-2]-'0')*10+arr[i-1]-'0'; dp[i]=(arr[i-2]-'0'!=0&&number>=0&&number<26)?dp[i-1]+dp[i-2]:dp[i-1]; } return dp[arr.length]; }}2、空间优化
class Solution { public int translateNum(int num) { char[] arr=String.valueOf(num).toCharArray(); int a=1, b=1,result=1,number=0; for(int i=2;i<arr.length+1;i++){ number=(arr[i-2]-'0')*10+arr[i-1]-'0'; result=(arr[i-2]-'0'!=0&&number>=0&&number<26)?a+b:b; a=b; b=result; } return result; }}3、
class Solution { public int translateNum(int num) { char[] arr=String.valueOf(num).toCharArray(); int a=1, b=1,result=1,number=0; for(int i=arr.length-2;i>=0;i--){ number=(arr[i]-'0')*10+arr[i+1]-'0'; result=(arr[i]-'0'!=0&&number>=0&&number<26)?a+b:b; a=b; b=result; } return result; }}4、
class Solution { public int translateNum(int num) { int a=1, b=1,result=1,number=0; int cur=0,next=0;//当前位，后一位 while(num>0){ cur=(num/10)%10;next=num%10; number=cur*10+next; result=(cur!=0&&number>=0&&number<26)?a+b:b; a=b; b=result; num/=10; } return result; }}动态规划
通过找规律找出状态转移方程
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
示例 1:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
提示：
0 < grid.length <= 200
0 < grid[0].length <= 200
class Solution { public int maxValue(int[][] grid) { for(int i=0;i<grid.length;i++){ for(int j=0;j<grid[0].length;j++){ if(i==0&&j==0)continue; el if(i==0||j==0)grid[i][j]+=(i==0)?grid[i][j-1]:grid[i-1][j]; el grid[i][j]+=Math.max(grid[i-1][j],grid[i][j-1]); } } return grid[grid.length-1][grid[0].length-1]; }}1、
class Solution { public int maxValue(int[][] grid) { int m = grid.length, n = grid[0].length; for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { if(i == 0 && j == 0) continue; if(i == 0) grid[i][j] += grid[i][j - 1] ; el if(j == 0) grid[i][j] += grid[i - 1][j]; el grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]); } } return grid[m - 1][n - 1]; }}2、优化
以上代码逻辑清晰，和转移方程直接对应，但仍可提升效率：当 gridgrid 矩阵很大时， i = 0 或 j = 0的情况仅占极少数，相当循环每轮都冗余了一次判断。因此，可先初始化矩阵第一行和第一列，再开始遍历递推。
class Solution { public int maxValue(int[][] grid) { int m = grid.length, n = grid[0].length; for(int j = 1; j < n; j++) // 初始化第一行 grid[0][j] += grid[0][j - 1]; for(int i = 1; i < m; i++) // 初始化第一列 grid[i][0] += grid[i - 1][0]; for(int i = 1; i < m; i++) for(int j = 1; j < n; j++) grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]); return grid[m - 1][n - 1]; }}作者：jyd
链接：link
来源：力扣（LeetCode）
class Solution { public int maxValue(int[][] grid) { for(int i=1;i<grid[0].length;i++){ grid[0][i]+=grid[0][i-1]; } for(int i=1;i<grid.length;i++){ grid[i][0]+=grid[i-1][0]; } for(int i=1;i<grid.length;i++){ for(int j=1;j<grid[0].length;j++){ grid[i][j]+=Math.max(grid[i-1][j],grid[i][j-1]); } } return grid[grid.length-1][grid[0].length-1]; }}动态规划
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例 1:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。
提示：
s.length <= 40000
1、
class Solution { public int lengthOfLongestSubstring(String s) { Map<Character,Integer> map=new HashMap<>(); int max=0,temp=0; char c='0'; for(int i=0;i<s.length();i++){ c正态分布概率=s.charAt(i); if(map.containsKey(c)){ temp=i-map.get(c)-1; int start=map.get(c)+1; map.clear(); for(int j=start;j<i;j++)map.put(s.charAt(j),j); } map.put(c,i); temp++; max=Math.max(max,temp); } return max; }}2、优化
class Solution { public int lengthOfLongestSubstring(String s) { Map<Character,Integer> map=new HashMap<>(); int max=0,temp=0,start=0; char c='0'; for(int i=0;i<s.length();i++){ c=s.charAt(i); if(map.containsKey(c)&&map.get(c)>=start){ temp=i-map.get(c)-1; start=map.get(c)+1; map.remove(c); } map.put(c,i); temp++; max=Math.max(max,temp); } return max; }}1、
class Solution { public int lengthOfLongestSubstring(String s) { Map<Character, Integer> dic = new HashMap<>(); int res = 0, tmp = 0; for(int j = 0; j < s.length(); j++) { int i = dic.getOrDefault(s.charAt(j), -1); // 获取索引 i dic.put(s.charAt(j), j); // 更新哈希表 tmp = tmp < j - i ? tmp + 1 : j - i; // dp[j - 1] -> dp[j] res = Math.max(res, tmp); // max(dp[j - 1], dp[j]) } return res; }}2、
class Solution { public int lengthOfLongestSubstring(String s) { Map<Character, Integer> dic = new HashMap<>(); int i = -1, res = 0; for(int j = 0; j < s.length(); j++) { if(dic.containsKey(s.charAt(j))) i = Math.max(i, dic.get(s.charAt(j))); // 更新左指针 i dic.put(s.charAt(j), j); // 哈希表记录 res = Math.max(res, j - i); // 更新结果 } return res; }}作者：jyd
链接：link
来源：力扣（LeetCode）
评论区：
public int lengthOfLongestSubstring(String s) { //if(s==null) return 0;这句话可以不加，s.length()长度为0时，不进入下面的循环，会直接返回max=0; //划定当前窗口的坐标为(start,i],左开右闭,所以start的初始值为-1，而非0。 int max = 0,start =-1; //使用哈希表map统计各字符最后一次出现的索引位置 HashMap<Character,Integer> map = new HashMap<>(); for(int i=0;i<s.length();i++){ char tmp = s.charAt(i); //当字符在map中已经存储时，需要判断其索引值index和当前窗口start的大小以确定是否需要对start进行更新: //当index>start时，start更新为当前的index,否则保持不变。 //注意若index作为新的start，计算当前滑动空间的长度时也是不计入的，左开右闭，右侧s[i]会计入，这样也是防止字符的重复计入。 if(map.containsKey(tmp)) start = Math.max(start,map.get(tmp)); //如果map中不含tmp，此处是在map中新增一个键值对，否则是对原有的键值对进行更新 map.put(tmp,i); //i-start,为当前滑动空间(start,i]的长度，若其大于max，则需要进行更新。 max = Math.max(max,i-start); } return max; }3、滑动窗口
class Solution { public int lengthOfLongestSubstring(String s) { Set<Character> t = new HashSet<>(); int left = 0, right = 0, res = 0; while(right < s.length()){ char c = s.charAt(right++); //存在重复的字符，则移动左指针，直到滑动窗口中不含有该字符 while(t.contains(c)){ t.remove(s.charAt(left++)); } t.add(c); res = Math.max(res, right-left); } return res; }}作者：eager-2
链接：link
来源：力扣（LeetCode）
class Solution { public int lengthOfLongestSubstring(String s) { Map<Character,Integer> map=new HashMap<>(); int max=0,start=-1;//start为-1，在只有一个字符时用 char c='0'; for(int i=0;i<s.length();i++){ c=s.charAt(i); if(map.containsKey(c))start=Math.max(start,map.get(c)); map.put(c,i); max=Math.max(max,i-start); } return max; }}滑动窗口，HashMap
边界值的考虑
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
1 是丑数。
n 不超过1690。
1、暴力（超时）
class Solution { public int nthUglyNumber(int n) { int i=1,num=0; Set<Integer> t=new HashSet<>(); t.add(1);t.add(2);t.add(3);t.add(5); while(true){ if(t.contains(i))num++; el if((i%2==0&&t.contains(i/2))||(i%3==0&&t.contains(i/3))||(i%5==0&&t.contains(i/5))){ num++; t.add(i); } if(num==n)break; i++; } return i; }}2、动态规划
class Solution { public int nthUglyNumber(int n) { int[] dp=new int[n+1]; int index2=1,index3=1,index5=1; dp[1]=1; int min=0; for(int i=2;i<=n;i++){ //三指针 //三个指针分别用来*2，*3，*5 min=Math.min(dp[index2]*2,Math.min(dp[index3]*3,dp[index5]*5)); if(min==dp[index2]*2){ dp[i]=min; index2++; } if(min==dp[index3]*3){ dp[i]=min; index3++; } if(min==dp[index5]*5){ dp[i]=min; index5++; } } return dp[n]; }}class Solution { public int nthUglyNumber(int n) { int a = 0, b = 0, c = 0; int[] dp = new int[n]; dp[0] = 1; for(int i = 1; i < n; i++) { int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5; dp[i] = Math.min(Math.min(n2, n3), n5); if(dp[i] == n2) a++; if(dp[i] == n3) b++; if(dp[i] == n5) c++; } return dp[n - 1]; }}作者：jyd
链接：link
来源：力扣（LeetCode）
class Solution { public int nthUglyNumber(int n) { int[] dp=new int[n]; int index2=0,index3=0,index5=0; dp[0]=1; int min=0; for(int i=1;i<n;i++){ //三指针 min=Math.min(dp[index2]*2,Math.min(dp[index3]*3,dp[index5]*5)); if(min==dp[index2]*2){ dp[i]=min; index2++; } if(min==dp[index3]*3){ dp[i]=min; index3++; } if(min==dp[index5]*5){ dp[i]=min; index5++; } } return dp[n-1]; }}动态规划
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
示例:
s = “abaccdeff”
返回 “b”
s = “”
返回 ” “
限制：
0 <= s 的长度 <= 50000
1、两次遍历
class Solution { public char firstUniqChar(String s) { Map<Character,Integer> map=new HashMap<>(); for(char c:s.toCharArray()){ if(!map.2016黑色星期五containsKey(c))map.put(c,1); el map.put(c,map.get(c)+1); } for(char c:s.toCharArray()){ if(map.get(c)==1)return c; } return ' '; }}1、
class Solution { public char firstUniqChar(String s) { HashMap<Character, Boolean> dic = new HashMap<>(); char[] sc = s.toCharArray(); for(char c : sc) dic.put(c, !dic.containsKey(c)); for(char c : sc) if(dic.get(c)) return c; return ' '; }}2、
class Solution { public char firstUniqChar(String s) { Map<Character, Boolean> dic = new LinkedHashMap<>(); char[] sc = s.toCharArray(); for(char c : sc) dic.put(c, !dic.containsKey(c)); for(Map.Entry<Character, Boolean> d : dic.entrySet()){ if(d.getValue()) return d.getKey(); } return ' '; }}作者：jyd
链接：link
来源：力扣（LeetCode）
class Solution { public char firstUniqChar(String s) { Map<Character,Integer> map=new LinkedHashMap<>(); char result=' '; for(char c:s.toCharArray()){ if(!map.containsKey(c))map.put(c,1); el map.put(c,map.get(c)+1); } for(Map.Entry<Character,Integer> entry:map.entrySet()){ if(entry.getValue()==1)return entry.getKey(); } return ' '; }}有序哈希表
Map<Character,Integer> map=new LinkedHashMap<>();
Map.Entry<Character,Integer> map.entrySet() 得到所有键值对
entry.getValue()获取value entry.getKey()获取key
本文地址：https://blog.csdn.net/weixin_43674414/article/details/109177347
本文发布于:2023-04-03 20:45:20，感谢您对本站的认可！
本文链接：https://www.wtabcd.cn/fanwen/zuowen/530b7f715b4f63c2e5ac1a910d68f03c.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
本文word下载地址：Leetcode剑指offer（六）.doc
本文 PDF 下载地址：Leetcode剑指offer（六）.pdf
| 留言与评论（共有 0 条评论） |
