慢速更新中

java基础语法

Math

1
Math.max(1,2);

基本数据类型

string

1
2
3
4
String s;
s.length();
int i=0;
s.charAt(i);

基本数据结构

数组

1
2
3
Arrays.fill(数组名, 需要填充的内容);
//自带sort
Arrays.sort(数组名);

List

以下情况使用 ArrayList :

  • 频繁访问列表中的某一个元素。
  • 只需要在列表末尾进行添加和删除元素操作。
1
2
3
4
5
6
7
ArrayList<E> xx =new ArrayList<>();
//访问
xx.get(index);
//add
xx.add(ans);
//size
xx.size();

以下情况使用 LinkedList :

  • 你需要通过循环迭代来访问列表中的某些元素。
  • 需要频繁的在列表开头、中间、末尾等位置进行添加和删除元素操作。
1
2
3
4
//嵌套list
List<List<Integer>> result = new LinkedList<>();
List<Integer> ans = new LinkedList<>();
//与 ArrayList 相比，LinkedList 的增加和删除对操作效率更高，而查找和修改的操作效率较低。

HashMap

基本定义与使用案例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
HashMap<Character, Integer> map = new HashMap<Character, Integer>();//key value
if(map.containsKey(s.charAt(i))){}
map.put(s.charAt(i),i);
value = map.get(key);
//
put(K key, V value)
     key - 与指定值相关联的键。
    value - 与指定键关联的值。
返回值：当存在这个key的时候,会覆盖掉原来的value并返回oldvalue,也就是旧值。
对返回值的进一步解释：
    如果没有键映射，则返回NULL。
    该函数返回与指定键关联的旧值。
    这个操作不管啥条件都会覆盖旧的。

get（key）：
    Key - 其关联值将被返回的键。
返回值：指定键映射到的值，如果此映射不包含键的映射，则为NULL。
返回值进一步阐述：
    使用get函数，那么应该有先调用put函数对m表进行存储，不然肯定是返回null；
    由于m表的存储跟put函数有关，在实际工程应用中get返回值是受到put函数影响的。

妈妈让我总结题型

滑动窗口

待冲

  1. 串联所有单词的子串

  2. 最小覆盖子串

  3. 至多包含两个不同字符的最长子串

  4. 长度最小的子数组

  5. 滑动窗口最大值

  6. 字符串的排列

  7. 最小区间

  8. 最小窗口子序列

已冲

3. 无重复字符的最长子串 比较需要注意的地方是hashmap的用法，还有就是理解left=max(left,map.get(s.charAt(right))+1)

最终提交：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int left = 0;
        int right = 0;
        int answer = 0;
        HashMap<Character,Integer> map = new HashMap<Character,Integer>();
        int strSize = s.length();
        while(right<=strSize-1){
            if(map.containsKey(s.charAt(right))){
                //answer = Math.max(answer,right-left);
                left = Math.max(left,map.get(s.charAt(right))+1);
            }

            answer = Math.max(answer,right-left+1);
            map.put(s.charAt(right),right);
            right++;
        }
        return answer;
    }
}

双指针

已冲

11. 盛最多水的容器

最终提交：

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
class Solution {
    public int maxArea(int[] height) {
        int size = height.length;
        int left = 0;
        int right = size - 1;
        int ans = 0;
        int current = 0;
        while(left<right){
            int _width;
            if(height[left]>height[right]){
                _width = height[right];
            }
            else{
                _width = height[left];
            }
            current = (right - left)* _width;
            if(current>=ans){ans = current;}
            //
            if(height[left]>height[right]){
                right--;
            }
            else{
                left++;
            }
        }

        return ans;
    } 
}

快慢指针

区间合并

循环排序

链表翻转

树上的BFS

树上的DFS

双堆类型

子集类型

改造过的二分

前K个系列

多路归并

0/1背包类型

拓扑排序类型

参考：LeetCode按照怎样的顺序来刷题比较好？ - 穷码农的回答 - 知乎 https://www.zhihu.com/question/36738189/answer/908664455

妈妈让我重视动态规划(DP)

0/1背包

无限背包

斐波那契数列/单串

已冲

70. 爬楼梯

最终提交：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int climbStairs(int n) {
        int[] memo = new int[n+1];

        if(n==0){return 1;}
        if(n==1){return 1;}
        if(n==2){return 2;}

        memo[0]=1;
        memo[1]=1;
        memo[2]=2;

        for(int i=2;i<=n;i++){
            memo[i] = memo[i-1]+memo[i-2];
        }

        return memo[n];
    }
}

343. 整数拆分

首次提交：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int integerBreak(int n) {
        int[] ans = new int[n+1];

        //虽然默认填充为0，但这里明确写出来比较好一点
        ans[0]=0;
        ans[1]=0;

        for(int k=2;k<=n;k++){
            int currmax = 0;
            for(int j = 0;j<k;j++){
            //下面这个我注释起来的是状态转移方程
                //currmax = Math.max(j*(k-j),j*ans[k-j]);
                currmax = Math.max(currmax,Math.max(j*(k-j),j*ans[k-j]));
            }
            ans[k]=currmax;
        }



        return ans[n];
    }
}

优化后最终提交：

(优化了状态转移方程)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int integerBreak(int n) {
        if (n < 4) {
            return n - 1;
        }

        int[] ans = new int[n+1];

        ans[0]=0;
        ans[1]=0;
        ans[2]=1;

        for(int k=3;k<=n;k++){
            ans[k] = Math.max(Math.max(2 * (k - 2), 2 * ans[k - 2]), Math.max(3 * (k - 3), 3 * ans[k - 3]));
        }
        return ans[n];
    }
}

279. 完全平方数

初次提交：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];

        for(int p = 0;p<=n;p++){
            dp[p] = p;//隐藏初始化：dp[0]=0;dp[1]=1，那么,p为平方数时，dp[p-p*p]=0
            for(int k =0;k*k<=p;k++){
                dp[p] = Math.min(dp[p-k*k]+1,dp[p]); //重要的是状态转移方程
            }
        }
        return dp[n];
    }
}

回文

最长子字符串

君の算法本当上手

妈妈都爱的答题技巧

从时间复杂度揣摩出算法搭配方案

image.png

上图仅列出了时间复杂度较为固定的常见算法，而类似于动态规划、贪心、暴力等时间复杂度百变多样的算法并未列出。
O(logn)O(logn)O(logn) 的算法通常与 O(n)O(n)O(n) 的算法组合在一起，用于实现 O(nlogn)O(nlogn)O(nlogn) 要求的题目

妈妈让我不要暴力膜哩（大悲

妈妈让我重做的mark题

  1. 4. 寻找两个正序数组的中位数
    1. 妈妈让用二分查找再做亿遍
    2. 妈妈让用划分数组再做亿遍
  2. 264. 丑数 II
    1. 优先队列
    2. 动态规划（重要）

虽然不想碰ACM但妈妈让我数论一下

快速幂

矩阵快速幂

70. 爬楼梯