你也不是我的救赎

发表于 分类于 ， 本文字数： 2.9k 阅读时长 ≈ 3 分钟

146. LRU 缓存

146. LRU 缓存

解法1

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
package leetcode.editor.cn.mycode.ID146;

import java.util.HashMap;


/**
 * 手写双向链表加哈希表
 */
public class LRUCache1 {
        class node{
            public int val,key;
            public node prev,next;

            public node(int key, int val) {
                this.key = key;
                this.val = val;
            }
        }
        class doubleList{
            public node tail;
            public node head;
            private int size;

            public doubleList() {
                this.size=0;
                head=new node(0,0);
                tail=new node(0,0);
                head.next=tail;
                tail.prev=head;
            }

            /**
             * 在尾部插入
             * @param x
             */
            public void addList(node x)
            {
                x.prev=tail.prev;
                x.next=tail;
                tail.prev.next=x;
                tail.prev=x;
                size++;
            }

            /**
             * 一定存在
             *
             * @param x
             */
            public void remove(node x){
            x.prev.next=x.next;
            x.next.prev=x.prev;
            size--;
            }

            public node removeFirst(){
                if(head.next==tail)
                {
                    return null;
                }
                node first = head.next;
                remove(first);
                return first;
            }

            public int size()
            {
                return size;
            }

        }



    HashMap<Integer,node> map;
    doubleList cache;

    int cap;
    public LRUCache1(int capacity) {
        this.cap=capacity;
        this.map =new HashMap<>();
        this.cache=new doubleList();
    }

    private void makeRecently(int key)
    {
        node node = map.get(key);
        cache.remove(node);
        cache.addList(node);
    }
    private void addRecently(int key ,int value)
    {
        node node = new node(key, value);
        cache.addList(node);
        map.put(key,node);
    }
    private void deleteKey(int key)
    {
        node node = map.get(key);
        cache.remove(node);
        map.remove(key);
    }

    private void removeLeastRecently(){
        node node = cache.removeFirst();
        map.remove(node.key);
    }


    public int get(int key) {
        if(!map.containsKey(key))
        {

            return -1;
        }
        makeRecently(key);
        return map.get(key).val;

    }

    public void put(int key, int value) {
        if(map.containsKey(key))
        {
            deleteKey(key);
            addRecently(key,value);
            return ;
        }
        if(cap==cache.size){
            removeLeastRecently();
        }
        addRecently(key,value);
    }


}

解法2

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
package leetcode.editor.cn.mycode.ID146;

import java.util.LinkedHashMap;

/**
 * 使用java中自带的linkedHashMap
 */
public class LRUCache2 {
        int cap;
        LinkedHashMap<Integer,Integer> cache=new LinkedHashMap<>();


    public LRUCache2(int capacity) {
            this.cap=capacity;
    }

    public void makeRecently(int key)
    {
        Integer value = cache.get(key);
        //删除重新插入到队尾
        cache.remove(key);
        cache.put(key,value);
    }

    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        Integer value = cache.get(key);
        makeRecently(key);
    return value;
    }

    public void put(int key, int value) {
        if(cache.containsKey(key))
        {
            cache.put(key,value);
            makeRecently(key);
            return;
        }
        if(cache.size()>=cap)
        {
            //链表头部就是最久未使用的key
            Integer oldKey = cache.keySet().iterator().next();
            cache.remove(oldKey);
        }
        cache.put(key, value);
    }
}

发表于 分类于 本文字数： 319 阅读时长 ≈ 1 分钟

11盛最多水的容器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

 public static int maxArea(int[] height) {
        int res = 0;
        for (int l = 0, r = height.length-1;l<r; ) {
            //移动右边的面积比移动左边的面积大，那么就移动右边的否则移动左边
            //计算面积
            int are = Math.min(height[l], height[r]) * (r - l);
            res = Math.max(are, res);
            if (height[l] < height[r]) {
               l++;

            } else {
                r--;
            }
        }
        return res;
}


发表于 本文字数： 1.1k 阅读时长 ≈ 1 分钟
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
37
38
39
40
41
42
43
44
45
46
47
48
49


public class ID15三数之和 {
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
//        for (int i = 0; i < nums.length; i++) {
//            for (int j = i+1; j < nums.length; j++) {
//                for (int k = j+1; k < nums.length; k++) {
//                    if(nums[i] + nums[j] + nums[k] == 0){
//                        res.add(Arrays.asList(nums[i] , nums[j] , nums[k]));
//                    }
//                }
//
//            }
//        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length-2; i++) {
            if(i>0&&nums[i]==nums[i-1])continue;
            int l=i+1;
            int r=nums.length-1;
            while (l<r)
            {
                int sum = nums[i] + nums[l] + nums[r];
                if(sum==0) {
                    res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    // 去重l和r
                    while (l < r && nums[l] == nums[l + 1]) l++;
                    while (l < r && nums[r] == nums[r - 1]) r--;
                    l++;
                    r--;
                }
                else if (sum<0) l++;
                else r--;


            }
        }
        return res;
    }

    public static void main(String[] args) {
        List<List<Integer>> lists = threeSum(new int[]{0, 0, 0,0
        });
        System.out.println("lists = " + lists);
    }
}



发表于 本文字数： 1.1k 阅读时长 ≈ 1 分钟

方法一：定长滑窗

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
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
          //保存答案
        List<Integer> res = new ArrayList<>();

        //p的异位词
        //给定两个字符串 s 和 p，找到 s 中所有 p 的
        //异位词
        // 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
        int[] cntS = new int[30];
        int[] cntP = new int[30];
        //取出子串
        for (char c : p.toCharArray()) {
              cntP[c-'a']++;
        }
        for(int r=0;r<s.length();r++)
        {
            cntS[s.charAt(r)-'a']++;
            int l = r - p.length() + 1;
            if(l<0){
                continue;
            }
            if(Arrays.equals(cntS,cntP)){
                res.add(l);
            }
            cntS[s.charAt(l) - 'a']--;
        }

        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
class Solution {
    public List<Integer> findAnagrams(String s, String p) { List<Integer> res = new ArrayList<>();
        int[] cnt = new int[30];

        for (char c : p.toCharArray()) {
            cnt[c-'a']++;
        }
        int l=0;
        for(int r=0;r<s.length();r++)
        {
            int c = s.charAt(r)-'a';
            cnt[c]--;
           while(cnt[c]<0) {  
            cnt[s.charAt(l)-'a']++;
            l++;
           }
            if(r-l+1==p.length())
            {
                res.add(l);
            }

        }
        
        return res;
    }
}

发表于 本文字数： 4 阅读时长 ≈ 1 分钟

注意配置

OpenGL配置截图

发表于 本文字数： 30 阅读时长 ≈ 1 分钟

idae踩坑

修改示例
需要在这里将java设置与项目相同，否则无法打包

发表于 本文字数： 23 阅读时长 ≈ 1 分钟

学习有感

学习三角

  • 学习加深方式便是练习与交流想法

alt text

发表于 本文字数： 10 阅读时长 ≈ 1 分钟

新建主题中的评论机制

发表于 本文字数： 14 阅读时长 ≈ 1 分钟

通过chatgpt-4o生成

也许会一直喜欢

也许会一直喜欢

0%