如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[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++; else break; } list.add(j,(double)num); } public double findMedian() {//时间复杂度为O(1) if(list.size()%2==1)return list.get(list.size()/2); else 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()); } else { 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 container public: // Adds a number into the data structure. void addNum(int num) { if (store.empty()) store.push_back(num); else store.insert(lower_bound(store.begin(), store.end(), num), num); // binary search and insertion 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()); } else{ big.offer(num); small.offer(big.poll()); } size++; } public double findMedian() { if(size%2==0){ return (double)(small.peek()+big.peek())/2; } else 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
作者：jyd 链接：link 来源：力扣（LeetCode）
动态规划
输入一个整数 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; } }感觉就是找规律。。太难找了
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); } else { return pow + high*f(pow-1) + f(last); } } }作者：xujunyi 链接：link 来源：力扣（LeetCode）
找规律
数字以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 共9x1 = 9个数字 占位9x1 = 9 位 10～99 共9x10 = 90个数字 占位90x2 = 180 位 100～999 共9x100 = 900个数字 占位900x3 = 2700 位 …
规律是不是很好理解啦，算法的逻辑就是：我们依次算一下占位数字，并不断地累加得到当前的总占位数，并判断和输入n的关系，总占位数小于n的话说明，第n位不在目前的范围內，继续累加；否则，说明在范围，然后找到相应数字返回。
举个例子秒懂：
假设输入n为14，我们想找到第14位：
(1)此时设置当前位置为0的位置 temp=0 (2)占1位的数字有9个: num=9,（1～9,除了0因为temp已设为0了） (3)占1位 base=1 (4)我们判断一下，当占1位的数字都走完了，目前一共占到了多少位： temp + num x base = 0 + 9x1 = 9，说明占1位的数字走完后，当前占到了第9位。(更新temp=temp + num x base = 9） (5)和输入的值比较下，9 < 14,说明我们想找的第14位不在当前占1位的数字中。 (6)那就有可能在占2位的数字中，所以这一轮我们看看占2位的数字（10～99）： 每个数字占位 base = base + 1 = 2 有多少个数字 num = num x 10 = 90 再回到第（4)步，算一下当占2位的数字也都走完了，目前一共占到了多少位 temp + num x base = 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的(base-1)次方） 由于10～99这个范围内的数字，都是占base=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; else if(n>=0 && n<=9) return n; else { long m = n; long temp = 0; long base = 1; long num = 9; char res = '0'; while((temp+base*num) < m) { temp += base*num; base += 1; num *= 10; } long a = (m-temp)/base; long b = (m-temp)%base; if(b!=0) { long c = (long) (Math.pow(10, base-1) + a); res = String.valueOf(c).charAt((int)b-1); }else { long c = (long) (Math.pow(10, base-1) + a - 1); res = String.valueOf(c).charAt((int)base-1); } return Integer.parseInt(String.valueOf(res)); } } }作者：zhuguangyu 链接：link 来源：力扣（LeetCode）
找规律
有可能越界的地方用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; else { return Integer.parseInt(a+""+b)-Integer.parseInt(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
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
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] ; else if(j == 0) grid[i][j] += grid[i - 1][j]; else 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）
动态规划
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例 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> set = new HashSet<>(); int left = 0, right = 0, res = 0; while(right < s.length()){ char c = s.charAt(right++); //存在重复的字符，则移动左指针，直到滑动窗口中不含有该字符 while(set.contains(c)){ set.remove(s.charAt(left++)); } set.add(c); res = Math.max(res, right-left); } return res; } }作者：eager-2 链接：link 来源：力扣（LeetCode）
滑动窗口，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> set=new HashSet<>(); set.add(1);set.add(2);set.add(3);set.add(5); while(true){ if(set.contains(i))num++; else if((i%2==0&&set.contains(i/2))||(i%3==0&&set.contains(i/3))||(i%5==0&&set.contains(i/5))){ num++; set.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]; } }作者：jyd 链接：link 来源：力扣（LeetCode）
动态规划
在字符串 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.containsKey(c))map.put(c,1); else 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）
有序哈希表 Map<Character,Integer> map=new LinkedHashMap<>();
Map.Entry<Character,Integer> map.entrySet() 得到所有键值对
entry.getValue()获取value entry.getKey()获取key
