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

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

hash拉链法

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

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

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20