刷题笔记19——优势洗牌和去重保持字典序

摆出无比亲密的态度，装模作样地与对方套近乎，频繁地联系对方。这都说明他们并不相信自己得到了对方的信赖，若是互相信赖，便不会依赖亲密的感觉。在外人看来，反而显得冷淡。 ——尼采《人性的，太人性的》

hash拉链法

list和hash的基本用法八百年都学不会

• list
  • add
  • remove（根据下表进行删除）
  • Collections.swap(nums, index, nums.size() - 1); 进行交换
• hash
  • containsKey 判断是否存在
  • get
  • put
  • remove
• set
  • add
  • contains
• stack 栈
  • Stack<Character> res = new Stack<>();
    -size
• String
  • length()

870. 优势洗牌

• 最重要的是学会一些排序的方法

class Solution {public int[] advantageCount(int[] nums1, int[] nums2) {// 排序之后的规则就是，遇弱则强，遇强送人头int len = nums1.length;int[] res = new int[len];// 默认为升序Arrays.sort(nums1);// 降序PriorityQueue<int[]> maxpq = new PriorityQueue<>((int[] pair1,int[] pair2)->{return pair2[1]-pair1[1];});for(int i=0;i<len;i++){maxpq.offer(new int[]{i,nums2[i]});}int left = 0;int right = len-1;for(int i=0;i<len;i++){int[] pair = maxpq.poll();int m = pair[0],maxval = pair[1];if(nums1[right]>maxval){res[m] = nums1[right];right--;}else{res[m] = nums1[left];left++;}}return res;}
}

1081. 不同字符的最小子序列（栈的使用）

316. 去除重复字母

• 如果已经放进去了，那说明在遍历到第一个的时候，尽管后边还有一个备选，但是并没有被弹出，满足大小关系，所以遍历后边这个的时候就直接跳过就好了
• 如果是当前元素是新的元素，那就去检查
  • 满足大小关系吗？满足的话直接放，不满足的话就要看前边的元素能不能惹得起，如果前边元素是独苗，那就不能动，因为本身当前元素就该在前边元素后边，如果不是独苗，那就可以当前边元素弹出，把当前元素压入，反正后边有个替补在而且替补元素本身就比当前元素大，这个元素可以在后边压入而且不会丢掉。

class Solution {public String removeDuplicateLetters(String s) {Stack<Character> res = new Stack<>();for(int i=0;i<s.length();i++){char c = s.charAt(i);if(res.contains(c)){continue;}while(!res.isEmpty() && s.indexOf(res.peek(),i) != -1 && res.peek() > c){res.pop();}res.push(c);}char[] temp = new char[res.size()];for(int i = res.size()-1;i>=0;i--){temp[i] = res.pop();}return new String(temp);}
}