soyo的跨机房部署、同城双活、异地多活、9个9高可用博客yuque笔记同步site

ε=(´ο｀*)))唉，学Java的这辈子有了

发表于 更新于 分类于

无重复字符的最长子串[🔥990][中]

题目：就是给一个str，然后让你找到无重复字符的最长子串

思路：

  1. 整体就是滑动窗口
  2. map来存储子串的字符状态
  3. r++ ,map不断更新，map.put() while(map.get(xx) > 1){ l++; map.put()去把map里的之前状态消掉 } res不断更新

两数之和[🔥285][易]

题目：给你一个数组，一个target。然后让你去从数组中找到能组成target的元素

思路：

  1. 数组 先存一遍 cache set
  2. 遍历一遍数组，然后 cache.contains(target - curV) 如果为true ，就更新

二叉树的中序遍历非递归

题目：用非递归的形式输出二叉树的中序遍历

1

最小覆盖子串[🔥114]

题目：给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

输入：s = “ADOBECODEBANC”, t = “ABC”
输出：”BANC”
解释：最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、’B’ 和 ‘C’。

思路：

  1. 整体还是滑动窗口
  2. 维护一个map，map为t的映射表（k：字符，v：字符出现个数）。一个cnt，cnt初始化为 t的字符个数，表示还剩多少个字符可构成 t
  3. r++直到找到了t的第一个元素，ifxxx>0，cnt–，map[c] –
  4. while(cnt==0) 开始更新结果，且把最左边的东西弹出去
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
class Solution {
    public String minWindow(String s, String t) {
        // 1. 统计 t 中每个字符的需求
        Map<Character, Integer> need = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int cnt = t.length();      // 记录还缺多少个字符才能满足条件
        int l = 0, r = 0;          // 左右双指针
        int minLen = Integer.MAX_VALUE; // 最小子串长度
        String res = "";           // 最终结果

        // 2. 滑动右指针，不断扩展窗口
        for (; r < s.length(); r++) {
            char cr = s.charAt(r);

            // 只有当 cr 在需求表 need 中时才处理
            if (need.containsKey(cr)) {
                // 如果还缺这种字符，满足一个需求 → cnt--
                // ⚠️ 注意：必须是 need(cr) > 0 才 cnt--，
                // 否则可能是冗余字符，多减会出错
                if (need.get(cr) > 0) cnt--;

                // 不管需不需要，窗口多了这个字符，都要在 need 中减去
                need.put(cr, need.get(cr) - 1);
            }

            // 3. 当 cnt == 0 时，说明当前窗口已经满足 t 的需求
            while (cnt == 0) {
                // 更新答案（如果更短就更新）
                if (r - l + 1 < minLen) {
                    minLen = r - l + 1;
                    res = s.substring(l, r + 1);
                }

                // 尝试缩小左边界 l
                char cl = s.charAt(l);
                if (need.containsKey(cl)) {
                    // 把这个字符移出窗口，need要加回去
                    need.put(cl, need.get(cl) + 1);

                    // 如果加回去后 > 0，说明这个字符现在又缺了
                    // 所以 cnt++，窗口不再满足条件
                    if (need.get(cl) > 0) cnt++;
                }
                l++; // 左指针右移
            }
        }
        return res;
    }
}

时间复杂度：O N（s.length）+M（t.length）

找到字符串中所有字母异位词[🔥15][中]

题目：就是给你一个source,一个target，然后找出source字符串里面的包含target所有字符的字符子串

思路：

  1. 整体就是滑动窗口
  2. 然后初始化一个 26个字母的数组 [0 1 2 ……. ]
  3. 长度<target.length()就跳过
  4. 啥时候更新结果：当上面那个数组等于 target的数组模式时就更新
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 List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList();
        int[] target = new int[26];

        //异位词： 包含p所有字符的 字符串
        int[] cs = new int[26];
        for (char c : p.toCharArray()) {
            target[c - 'a']++;
        }
        //滑动窗口
        int l = 0;
        int r = 0;
        for (; r < s.length(); r++) {
            cs[s.charAt(r) - 'a']++;
            //首先得满足长度才能更新结果么
            if (r - l + 1 < p.length()) {
                continue;
            }
            //如果数组全相同就 说明找到了，更新结果
            if (Arrays.equals(cs, target)) {
                res.add(l);
            }
            cs[s.charAt(l) - 'a']--;
            l++;
        }
        return res;
    }
}
评论

评论

最热 | 最新

puffan

2021-06-23

滑动窗口O(n)

3

暂无回复

回复

一天到晚只会刷算法的疯狂javaer

2023-08-16

我直接一个滑动窗口滑滑滑

2

暂无回复

回复

Li

2022-08-19

华子实习手撕

2

暂无回复

回复

伟

2022-02-28

滑动窗口算法, 跟字符串排列思路一样

1

暂无回复

回复

Thirt33n

2024-07-09

字节三面

0

暂无回复

回复

用户OTCHR

2023-02-02

滑动窗口

0

暂无回复

回复

小号备战校招

2022-11-06

字节一面，跟567一样

0

暂无回复

回复

## [和为K的子数组](https://leetcode.cn/problems/subarray-sum-equals-k)[🔥70] 题目：给你一个数组，然后让你从里面找到和为k的子数组，并统计个数

思路1：

  1. 给出前缀和
  2. 转化为两数之和 即求 i（前缀和）-k的元素是否存在

思路2：

  1. 就是map方式的前缀和

思路3：

  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 int subarraySum(int[] nums, int k) {
        // 1 2 3
        // 0 1 3 6 
        //1,1,1 
        //0 1 2 3
        int []preSum=getPreSum(nums);
        //转换成两数之和了
        //k: integer v:出现个数
        Map<Integer,Integer> map=new HashMap<>();
        int res=0;
        for(int i:preSum){
            // i为和 k为目标数
            //看看是否有 k+xx=i 说明k存在
            if(map.containsKey(i-k)){
                res+=map.get(i-k);
            }
            map.put(i,map.getOrDefault(i,0)+1);
        }
        return res;
    }
    public int []getPreSum(int []nums){
        int []preSum=new int[nums.length+1];
        preSum[0] = 0;
        for(int i=1;i<=nums.length;i++){
            preSum[i]=preSum[i-1]+nums[i-1];
        }
        return preSum;

    }
}

最长重复子数组[🔥64]

题目：给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

思路：

  1. 滑动

复制带随机指针的链表[🔥58]

题目：拷贝特殊链表节点

思路：

  1. 普通链表初始化
  2. 初始化两个MAP
  3. 一个记录旧链表里 节点与index的关系
  4. 一个记录新链表里 index与节点的关系
  5. 由于新旧节点 index是一样的
  6. 故 旧链表可以通过node.random拿到该random.index
  7. 再通过index拿到新链表的node
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
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        //构造一个新链表、
        Node node=head;

        Node dummyHead = new Node(0);
        Node cur = dummyHead;
        //记录旧链表里 节点与index的关系
        //记录新链表里 index与节点的关系

        //由于新旧节点 index是一样的
        //故 旧链表可以通过node.random拿到该random.index
        //再通过index拿到新链表的node
        Map<Node,Integer> nodeMap=new HashMap<>();
        Map<Integer,Node> indexMap=new HashMap<>();
        int index=0;
        while(node!=null){
            nodeMap.put(node,index);
            node=node.next;
            index++;
        }
        node=head;
        index=0;
        while(node!=null){
            cur.next=new Node(node.val);
            cur=cur.next;
            node=node.next;
            indexMap.put(index,cur);
            index++;
        }
        //构造Random
        node=head;
        cur=dummyHead.next;
        while(node!=null){
            cur.random=indexMap.get(nodeMap.get(node.random));
            cur=cur.next;
            node=node.next;
        }
        return dummyHead.next;
    } 
}

前 K 个高频元素[35]

思路：hashmap统计+优先级队列维护前k个高频元素

无法单单用TreeMap排序，因为 TreeMap 只能按 key 排序，不能用value

优先级队列：

PriorityQueue

  1. map统计 次数
  2. 构造最小堆，且维护数量为k个，大于就驱逐最小的
  3. 然后到最后剩下的就是前k个高频元素了

Q：为什么不用最大堆？

A：最大堆，堆顶最大元素，你怎么驱逐堆低元素？

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
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> countMap = new HashMap<>();
        for (int num : nums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }

        // 小顶堆，堆顶是频率最小的元素
        PriorityQueue<Map.Entry<Integer,Integer>> heap = new PriorityQueue<>(
            (a,b) -> a.getValue() - b.getValue()
        );

        for (Map.Entry<Integer,Integer> entry : countMap.entrySet()) {
            heap.offer(entry);
            if (heap.size() > k) {
                heap.poll(); // 保持堆大小为 k 如果堆的元素里超过k就要驱逐人了
            }
        }

        int[] res = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            res[i] = heap.poll().getKey();
        }

        return res;
    }
}

两个数组的交集[24]

思路：查重就用Set 或者Map！！！！！！！！！！

contains

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
       HashSet<Integer> set=new HashSet<>();
       int length=Math.max(nums1.length,nums2.length);
       HashSet<Integer> res=new HashSet<>();
        for(int n:nums1){
            set.add(n);
        }
        //查重！！！
        for(int n:nums2){
            if(set.contains(n)){
               res.add(n);
            }
        }
        int []ans=new int[res.size()];
        int count=0;
        for(int i:res){
            ans[count++]=i;
        }
        return ans;
    }
}

retainAll的用法：求两个集合的交集，会把非交集的元素remove掉

1
2
3
4
5
6
7
8
9
HashSet<Integer> objects = new HashSet<>();
objects.add(1);
objects.add(2);
objects.add(3);
ArrayList<Object> objects1 = new ArrayList<>();
objects1.add(1);
objects1.add(2);
objects1.retainAll(objects);
System.out.println(objects1);// 1 2

面试官会先问：两个数组求交集，怎么求？以及说一下时间复杂度（不允许使用编程语言自带的交集功能）。答完之后再问：如果两个数组都是非递减的，又应该怎么求？时间复杂度多少？（本人亲身经历）

三数之和[436]

思路：

  1. 排序 + 三指针（i [l , r]）+ Set（自动去重）
  2. 排序 + 三指针 + 手动去重(剪枝)
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

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        //三指针 i ... [l r]
        // i是主指针， l和r是区间指针


        Set<List<Integer>> res = new HashSet();
        int n = nums.length;
        //排序
        Arrays.sort(nums);
        for(int i = 0; i < n; i++){
            // i ....[l...r]
            int l = i + 1;
            int r = n - 1;
            //剪枝。如果当前 元素为正数，说明没必要往下找了，因为后面都是正数了（因为l和r在i的后面）
            if(nums[i] > 0) break;
                        
            while(l < r){
                int sum = nums[i] + nums[l] + nums[r];
                if(sum == 0){
                    ArrayList<Integer> path = new ArrayList();
                    path.add(nums[i]);
                    path.add(nums[l]);
                    path.add(nums[r]);

                    res.add(path);
                    
                    //其实是可以优化的，不用HashSet的话
                    l++;
                    r--;
                }
                //小了, 因为是有序数组（之前排序了）。故移动左指针，增大整体sum 
                else if(sum < 0) l++;
                //大了，移动右指针，减少整体sum
                else r--;
            }
        }
        return new ArrayList(res);
    }
}

四数之和[21]

二数之和：哈希

三数之和：排序 + 双指针 + 剪枝

四数之和：排序 + 双指针 + 剪枝

思路：

1

O(1) 时间插入、删除和获取随机元素[18]

思路：hashMap+数组

Map：k为值，v为index，这样就可以containsKey了，杜绝重复insert

数组就是用来存放元素的

并且维护一个index

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class RandomizedSet {
    static int[] nums = new int[200010];
    Random random = new Random();
    Map<Integer, Integer> map = new HashMap<>();
    int idx = -1;
    public boolean insert(int val) {
        if (map.containsKey(val)) return false;
        nums[++idx] = val;
        map.put(val, idx);
        return true;
    }
    public boolean remove(int val) {
        if (!map.containsKey(val)) return false;
        int loc = map.remove(val);
        if (loc != idx) map.put(nums[idx], loc);
        nums[loc] = nums[idx--];
        return true;
    }
    public int getRandom() {
        return nums[random.nextInt(idx + 1)];
    }
}

前K个高频单词[18]

题目：

给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

看题啊尼玛的

思路：

  1. hashmap统计
  2. 最小堆维护前k个高频单词
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
class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        // 1. 统计词频
        Map<String, Integer> freqMap = new HashMap<>();
        for (String word : words) {
            freqMap.put(word, freqMap.getOrDefault(word, 0) + 1);
        }

        // 2. 小顶堆维护 Top K
        PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>(
            (a, b) -> {
                if (!a.getValue().equals(b.getValue())) {
                    return a.getValue() - b.getValue(); // 频率升序
                } else {
                    return b.getKey().compareTo(a.getKey()); // 字典序降序
                }
            }
        );

        for (Map.Entry<String, Integer> entry : freqMap.entrySet()) {
            pq.offer(entry);
            if (pq.size() > k) pq.poll(); // 保证堆大小为 K
        }

        // 3. 从堆中取出元素，倒序输出
        List<String> res = new ArrayList<>();
        while (!pq.isEmpty()) {
            res.add(0, pq.poll().getKey());
        }

        return res;
    }
}

167. 招式拆解 I[17]

有效的字母异位词[17]

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean isAnagram(String s, String t) {
        int [] cntS =new int[26];
        int [] cntT =new int[26];
        for(char c: s.toCharArray()){
            cntS[c-'a']++;
        }
        for(char c: t.toCharArray()){
            cntT[c-'a']++;
        }
        return Arrays.equals(cntS,cntT);
    }
}

砖墙

连续数组

发表于 更新于 分类于

最长回文子串

思路：见代码

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
class Solution {
    public String longestPalindrome(String s) {
        //左边界
        int resL=0;
        //右边界
        int resR=0;
        for(int i=0;i<s.length();i++){
            //有两种情况：1为一个中心点 2为两个中心点
            for(int j=0;j<=1;j++){
                int l=i;
                int r=i+j;
                //两边扩张
                while(l>=0&&r<s.length()&&s.charAt(l)==s.charAt(r)){
                    l--;
                    r++;
                }
                //回到正确的位置
                l++;
                r--;
                if(r-l>resR-resL){
                    resL=l;
                    resR=r;
                }


            }
        }
        return s.substring(resL,resR+1);
    }
}

有效的括号

思路：

  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
class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack=new Stack<>();
        for(char c:s.toCharArray()){
            if(c=='['||c=='{'||c=='('){
              stack.add(c);
            }
            else if(!stack.isEmpty()&&equals(stack.peek(),c)){
                stack.pop();
            }
            else return false;
        }
        //为什么不直接返回 true 
        //"[" 这种情况就得判Stack是否为空
        return stack.isEmpty();
    }
    public boolean equals(char a,char b){
        if(a=='['&&b==']'){
           return true;
        }
        else if(a=='{'&&b=='}'){
           return true;
        }
        else if(a=='('&&b==')'){
           return true;
        }
        return false;
    }
}

字符串相加

题目：大数相加

思路：

  1. 倒序相加，p1,p2从后面遍历字符串，然后at(p1) 和 at(p2) 进行相加，若p1 or p2 <0 就at(p) =0
  2. 相加过程：sum = at(p1) +at(p2) + pos（上一次运算进的位），然后当前位置的相加后的值 = sum%10，下一次进位 sum/10
  3. 后面如果出现 9+1这边，while结束后 if(pos > 1) append(1)
  4. 最后结果倒置 reverse()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public String addStrings(String num1, String num2) {
        int p1=num1.length()-1;
        int p2=num2.length()-1;
        int pos=0;
        StringBuilder res=new StringBuilder();
        while(p1>=0||p2>=0){
            int n1=p1>=0?num1.charAt(p1)-'0':0;
            int n2=p2>=0?num2.charAt(p2)-'0':0;
            int sum=n1+n2+pos;
            res.append(sum%10);
            pos=(sum)/10;
            p1--;
            p2--;
        }
        if(pos>0){
            res.append(1);
        }
        return res.reverse().toString();
    }
}

大数相减要怎么做？或者说num1 为负数呢

1

复原IP地址

思路：

  1. 第一步要要思考，当下有几种选择？
    • 以 “25525511135” 为例，第一步时我们有几种选择？
      1. 选 “2” 作为第一个片段
      2. 选 “25” 作为第一个片段
      3. 选 “255” 作为第一个片段
    1. 然后第二步的时候我们又有几种选择，切第二个片段时，又面临三种选择
    2. 这会向下分支，形成一棵树，我们用 DFS 去遍历所有选择，必要时提前回溯。

因为某一步的选择可能是错的，得不到正确的结果，不要往下做了。撤销最后一个选择，回到选择前的状态，去试另一个选择。

回溯的第一个要点：选择，它展开了一颗空间树。

  1. 第二步思考，有什么约束

约束条件限制了当前的选项，这道题的约束条件是：

不能有前导0，截取的字符串不能比255大，字符串截取长度为1-3

我们应该利用这些约束条件，对其进行剪枝。

  • 用这些约束进行充分地剪枝，去掉一些选择，避免搜索「不会产生正确答案」的分支。
  1. 第三部思考，目标是什么
    什么时候应该收集结果
  2. 定义dfs函数

return的作用是退回上一个选择点！！！ 

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
class Solution {
    List<String> res = new ArrayList<>();
    List<String> path = new ArrayList<>();
    int n;

    public List<String> restoreIpAddresses(String s) {
        n = s.length();
        dfs(s, 0);
        return res;
    }

    //我们第一步面临几个选择.
    // 1.选一个
    // 2.选两个
    // 3.选三个
    public void dfs(String s, int start) {
        if (start == n && path.size() == 4) {
            StringBuilder sb = new StringBuilder();
            for (String ss : path) {
                sb.append(ss);
                sb.append(".");
            }
            sb.deleteCharAt(sb.length() - 1);
            res.add(sb.toString());
            return;
        }
        
        //走到底，发现每一个选择都是合理，但整体选择就是错误的了
        //纵向剪枝
        //如：s：123454 path:[1,2,3,4]
        if (start < n && path.size() == 4) {
            return;
        }
        for (int len = 1; len <= 3; len++) {
            //删除不合法的前导0
            // len > 1 才会可能不合法： 01 022
            //横向剪辑
            if (len != 1 && s.charAt(start) == '0') {
                //return的作用是退回上一个选择点！！！
                return;
            }
            //保证后续s.substring() 合法
            if (start + len - 1 >= n) {
                return;
            }
            String t = s.substring(start, start + len);
            //截取后 大小不能超过255
            if (len == 3 && Integer.parseInt(t) > 255)
                return;
            path.add(t);
            dfs(s, start + len);
            path.remove(path.size() - 1);
        }

    }
}

比较版本号

思路：

  1. 分格String，用split，得到string []s
  2. 取两个str数组[] ，mark version
  3. 将s里的值装成Integer比较
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
class Solution {
    public int compareVersion(String version1, String version2) {
        String[] s1 = version1.split("\\.");
        String[] s2 = version2.split("\\.");
        int length = s1.length > s2.length ? s1.length : s2.length;
        String[] ss1 = new String[length];
        String[] ss2 = new String[length];
        for (int i = 0; i < s1.length; i++) {
            ss1[i] = s1[i];
            if (i == s1.length - 1) {
                i++;
                while (i < length) {
                    ss1[i] = "0";
                    i++;
                }
            }
        }
        for (int i = 0; i < length; i++) {
            ss2[i] = s2[i];
            if (i == s2.length - 1) {
                i++;
                while (i < length) {
                    ss2[i] = "0";
                    i++;
                }
            }
        }
        System.out.println(Arrays.toString(ss1));
        System.out.println(Arrays.toString(ss2));
        for (int i = 0; i < length; i++) {
            if (Integer.parseInt(ss1[i]) > Integer.parseInt(ss2[i])) {
                return 1;
            } else if (Integer.parseInt(ss1[i]) < Integer.parseInt(ss2[i])) {
                return -1;
            }
        }
        return 0;
    }
}

字节2面时候遇到过，不让用已知方法（java里String#split 方法），不让分割成String数组，可以试着自己手写一个双指针的方法

括号生成[137]

思路：

  1. 先把树图给列举出来，思考选择（加右括号还是左括号），约束，目标
  2. 回溯属性，path作为参数来说，return时只带恢复现场。而不是像全局属性一样（如下下），得手动恢复现场
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
class Solution {
    List<String> res = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        dfs(0, 0, n, "");
        return res;
    }

    public void dfs(int lcnt, int rcnt, int n, String path) {
        if (lcnt + rcnt == 2 * n) {
            res.add(path.toString());
            return;
        }
        //") xxxx" 肯定不合法
        if (path.length() == 1 && path.charAt(0) == ')')
            return;
        //合法的括号，lcnt的大小肯定是得等于n
        if (lcnt < n) {
            // System.out.println("L");
            // System.out.println(path);
            dfs(lcnt + 1, rcnt, n, path + "(");
        }

        //只有当前位置： lcnt>rcnt,才可以加")"eg： ((() 
        if (rcnt < lcnt) {
            // System.out.println("R");
            // System.out.println(path);
            dfs(lcnt, rcnt + 1, n, path + ")");
        }

    }
}

全局属性path

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 {
    List<String> res = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    public List<String> generateParenthesis(int n) {
        dfs(0, 0, n);
        return res;
    }

    public void dfs(int lcnt, int rcnt, int n) {
        if (lcnt + rcnt == 2 * n) {
            res.add(sb.toString());
            return;
        }
        //合法的括号，lcnt的大小肯定是得等于n
        if (lcnt < n) {
            sb.append("(");
            dfs(lcnt + 1, rcnt, n);
            sb.deleteCharAt(sb.length()-1);
        }

        //只有当前位置： lcnt>rcnt,才可以加")"eg： ((() 
        if (rcnt < lcnt) {
            sb.append(")");
            dfs(lcnt, rcnt + 1, n);
            sb.deleteCharAt(sb.length()-1);
        }

    }
}


字符串转换整数 (atoi)

最长有效括号

思路：

  1. 找到匹配括号的下标，然后存进一个LIst
  2. 接下来就是转换成 寻找最长连续子序列
    1. 两种做法：排序后滑动窗口，时间复杂度O（NlogN）
    2. hashset，时间复杂度O（N）
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 longestValidParentheses(String s) {
        List<Integer> indexList = new ArrayList<>();

        Stack<Integer> st = new Stack();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                st.add(i);
            }
            if (s.charAt(i) == ')' && st.size() != 0) {
                int index = st.pop();
                indexList.add(i);
                indexList.add(index);
            }
        }
        Collections.sort(indexList);
        int res = 0;
        int l = 0;
        int r = 1;
        //找出该数组的最长连续数列的长度
        for (; r < indexList.size(); r++) {
            if (indexList.get(r) != indexList.get(r-1) + 1) {
                l = r;
            }
            res = Math.max(res, r - l + 1);
        }
        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
37
38
39
40
41
42
43
class Solution {
    public int longestValidParentheses(String s) {
        List<Integer> indexList = new ArrayList<>();

        Stack<Integer> st = new Stack();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                st.add(i);
            }
            if (s.charAt(i) == ')' && st.size() != 0) {
                int index = st.pop();
                indexList.add(i);
                indexList.add(index);
            }
        }
        Set<Integer> set = new HashSet<>(indexList);
        int res = 0;
        // int l = 0;
        // int r = 1;
        //找出该数组的最长连续数列的长度
        // for (; r < indexList.size(); r++) {
        //     if (indexList.get(r) != indexList.get(r-1) + 1) {
        //         l = r;
        //     }
        //     res = Math.max(res, r - l + 1);
        // }
        // return res;
        //最长连续子序列
        for(int x: set){
            if(set.contains(x-1)){
                continue;
            }
            int nextX = x+1;
            int cnt  = 1;
            while(set.contains(nextX)){
                nextX++;
                cnt++;
            }
            res = Math.max(res,cnt);
        }
        return res;
    }
}

字符串相乘[116]

思路：

  1. 直接背诵，debug一遍也行
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
class Solution {
    public String multiply(String num1, String num2) {
        // 特殊情况：有一个数为0，结果直接是0
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }

        // 用数组保存结果，最大长度 = num1长度 + num2长度
        int[] res = new int[num1.length() + num2.length()];

        // 从后往前模拟竖式相乘
        for (int i = num1.length() - 1; i >= 0; i--) {
            int n1 = num1.charAt(i) - '0';
            for (int j = num2.length() - 1; j >= 0; j--) {
                int n2 = num2.charAt(j) - '0';

                // res[i+j+1] 存放当前位的结果（个位）
                int sum = res[i + j + 1] + n1 * n2;

                // 更新个位
                res[i + j + 1] = sum % 10;

                // 更新进位（加到前一位）
                res[i + j] += sum / 10;
            }
        }

        // 构建字符串结果，去掉最高位可能的0
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < res.length; i++) {
            if (i == 0 && res[i] == 0) continue; // 跳过前导0
            result.append(res[i]);
        }

        return result.toString();
    }
}

最小覆盖子串

题目：

思路：

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
class Solution {
    public String minWindow(String s, String t) {
        // 1. 构建目标字符表：统计 t 中每个字符需要的数量
        Map<Character, Integer> target = new HashMap<>();
        int cnt = 0; // 还差多少个字符没有被窗口覆盖
        for (char c : t.toCharArray()) {
            target.put(c, target.getOrDefault(c, 0) + 1);
            cnt++; // t 每有一个字符，就多需要一个
        }

        // 2. 定义滑动窗口的左右边界
        int l = 0;
        int r = 0;

        String res = "";              // 记录最终结果
        int size = Integer.MAX_VALUE; // 记录最小窗口大小

        // 3. 滑动右指针，扩大窗口
        for (; r < s.length(); r++) {
            char cr = s.charAt(r);

            // 如果右指针的字符不是目标字符，直接跳过
            if (!target.containsKey(cr)) {
                continue;
            }

            // 如果 cr 仍是需要的字符，就让 cnt--（缺少的字符数减少）
            if (target.get(cr) > 0) {
                cnt--;
            }

            // 把该字符的需求数减一（可能出现负数，表示“多出来的”）
            target.put(cr, target.get(cr) - 1);

            // 4. 当 cnt == 0 时，说明窗口已经包含了 t 的所有字符
            while (cnt == 0) {
                // 更新结果：若当前窗口更小，则替换
                if (size > r - l + 1) {
                    size = r - l + 1;
                    res = s.substring(l, r + 1);
                }

                // 5. 收缩左指针，尝试缩小窗口
                char lc = s.charAt(l);
                if (target.containsKey(lc)) {
                    // 把左边的字符“归还”给 target
                    target.put(lc, target.get(lc) + 1);
                    // 如果归还后需求量 > 0，说明窗口不再满足条件
                    if (target.get(lc) > 0) {
                        cnt++;
                    }
                }
                l++; // 左指针右移，缩小窗口
            }
        }
        return res;
    }
}

反转字符串中的单词

思路：

  1. 先把所有单词挑出来
  2. 然后翻转 String数组
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
class Solution {
    public String reverseWords(String s) {
        //把所有单词都挑出来
        List<String> ss = split(s);
        //System.out.println(ss);
        //翻转单词
        Collections.reverse(ss);

        StringBuilder sb = new StringBuilder();
        for (String v : ss) {
            sb.append(v);
            sb.append(" ");
        }
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }

    public List<String> split(String s) {
        int r = 0;
        List<String> res = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        for (; r < s.length(); r++) {
            if (s.charAt(r) == ' ') {
                if (sb.length() > 0) {
                    res.add(sb.toString());
                    sb = new StringBuilder();
                }
                continue;
            } else {
                sb.append(s.charAt(r));
            }
        }
        //["the sky is blue"] 这种情况会导致blue没法加进去
        //所以最后得做兜底
        if (sb.length() > 0)
            res.add(sb.toString());

        return res;
    }
}

最长公共前缀

耻辱：快手日常侧开一面竟然脑子坏了

思路：

1. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public String longestCommonPrefix(String[] strs) {
        boolean tag = true;
        String res = "";
        //以第一个str为基准
        for (int i = 0; i < strs[0].length(); i++) {
            String preStr = strs[0].substring(0, i + 1);
            //遍历剩余的子串
            for (int j = 1; j < strs.length; j++) {
                //是否以preStr为开头
                if (!strs[j].startsWith(preStr)) {
                    tag = false;
                }
            }
            //所有都为，更新结果
            if (tag) {
                res = preStr;
            }
        }
        return res;
    }
}

验证IP地址

思路：

  1. 就是简单模拟
  2. 学到的东西：Integer.parseInt(x,进制) 可指定进制
  3. 可以学学正则表达式
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
class Solution {
    public String validIPAddress(String queryIP) {
        if (is4Or6(queryIP)) {
            String[] ip = queryIP.split("\\.");
            // String[] ip = queryIP.split("."); 错误的, "." 在正则表达式里是 任意字符的意思
            // System.out.println(queryIP);
            // System.out.println(Arrays.toString(ip));
            if(getCnt('.',queryIP) != 3){
                return "Neither";
            }
            if (ip.length != 4) {
                return "Neither";
            }
            for (String s : ip) {
                try {
                    if (s.length() > 1 && s.charAt(0) == '0') {
                        return "Neither";
                    }
                    if (Integer.parseInt(s,10) > 255) {
                        return "Neither";
                    }
                } catch (Exception e) {
                    return "Neither";
                }
            }
            return "IPv4";
        } else {
            String[] ip = queryIP.split(":");
            if(getCnt(':',queryIP) != 7){
                return "Neither";
            }
            if (ip.length != 8) {
                return "Neither";
            }
            for (String s : ip) {
                if (s.length() > 4) {
                    return "Neither";
                }
                try{
                    //转成16进制
                    Integer.parseInt(s,16);
                }catch(Exception e){
                    return "Neither";
                }
            }
            return "IPv6";
        }
    }

    public boolean is4Or6(String queryIP) {
        if (queryIP.contains(".")) {
            return true;
        } else
            return false;
    }

    public int getCnt(char ch,String str) {
        int count = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == ch) {
                count++;
            }
        }
        return count;
    }
}

基本计算器 II[67]

思路：

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
class Solution {
    Map<Character,Integer> calOrderMap = new HashMap(){
        {
            put('+',1);
            put('-',1);
            put('/',2);
            put('*',2);
            //put();
        }
    };

    public int calculate(String s) {
        //替换掉空格
        s = s.replaceAll(" ", "");
        Deque<Integer> nums = new ArrayDeque<>();
        Deque<Character> ops = new ArrayDeque<>();
        //防止出现 -1 + 5 这种情况
        nums.addLast(0);
        System.out.println(s);
        char[] cs = s.toCharArray();
        int n = cs.length;
        for (int i = 0; i < n; i++) {
            char c = cs[i];
            if (isNumber(c)) {
                int number = 0;
                int numIndex = i;
                while (numIndex < n && isNumber(cs[numIndex])) {
                    numIndex++;
                }
                nums.addLast(Integer.parseInt(s.substring(i, numIndex)));
                i = numIndex - 1;
            }
            //遇到运算符了
            else {
                //防止出现 9 + - 1
                //将其装换成 9 + 0 - 1
                if (i > 0 && (cs[i - 1] == '-' || cs[i - 1] == '+')) {
                    nums.addLast(0);
                }
                //遇到新的运算符，先把stack里能计算的给计算了 eg：9+8-1
                while (!ops.isEmpty()) {

                    if (calOrderMap.get(ops.peekLast()) >= calOrderMap.get(c)) {
                        cal(nums, ops);
                    } else {
                        break;
                    }
                }
                ops.addLast(c);
            }
        }
        // 举例：
        // 2+3*4
        // 遍历完后，栈里的情况大概是：
        // nums = [2, 3, 4]
        // ops = ['+', '*']
        while (!ops.isEmpty())
            cal(nums, ops);
        return nums.peekLast();
    }

    public boolean isNumber(char c) {
        return Character.isDigit(c);
    }

    public void cal(Deque<Integer> nums, Deque<Character> ops) {
        if (nums.isEmpty() || nums.size() <= 1)
            return;
        if (ops.isEmpty())
            return;
        //注意顺序
        int b = nums.pollLast();
        int a = nums.pollLast();
        char op = ops.pollLast();
        int opRes = 0;
        switch (op) {
            case '-':
                opRes = a - b;
                break;
            case '+':
                opRes = a + b;
                break;
            case '/':
                opRes = a / b;
                break;
            case '*':
                opRes = a * b;
                break;
        }
        nums.addLast(opRes);
    }
}

完全版，应对所有情况，即完整的计算器

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
class Solution {
    Map<Character, Integer> opsOrderMap = new HashMap<>() {
        {
            put('-', 1);
            put('+', 1);
            put('*', 2);
            put('/', 2);
            put('%', 2);
            put('^', 3);
        }
    };

    public int calculate(String s) {
        //分为两个Stack
        //一个存操作，一个存数字
        Deque<Character> ops = new ArrayDeque();
        Deque<Integer> nums = new ArrayDeque();
        //为了防止第一个就是负数
        nums.addLast(0);

        //去掉全部空格
        s = s.replaceAll(" ", "");
        char[] cs = s.toCharArray();
        int n = s.length();
        for (int i = 0; i < n; i++) {
            char c = cs[i];
            if (c == '(') {
                ops.addLast(c);
            } else if (c == ')') {
                //计算 ( ) 里的内容了
                while (!ops.isEmpty()) {
                    if (ops.peekLast() != '(') {
                        cal(nums, ops);
                    } else {
                        //为 ( 说明() 已经计算好了 弹出即可
                        ops.pollLast();
                        break;
                    }
                }
            } else {
                //转换数字
                if (isNumber(c)) {
                    // 19  char 转成 Integer
                    int number = 0;
                    int numIndex = i;
                    // while(numIndex < n&&isNumber(cs[numIndex])){
                    //     number = number*10 + (cs[numIndex] - '0');
                    //     numIndex++;
                    // }
                    while (numIndex < n && isNumber(cs[numIndex])) {
                        numIndex++;
                    }
                    nums.addLast(Integer.parseInt(s.substring(i, numIndex)));
                    i = numIndex - 1;
                } else {
                    // 1 - -2 → 1 - (0-2)
                    // 1 + +2 → 1 + (0+2)
                    // (+-3) → (0+0-3)
                    if (i > 0 && (cs[i - 1] == '(' || cs[i - 1] == '+' || cs[i - 1] == '-')) {
                        nums.addLast(0);
                    }
                    // 有一个新操作入栈时，先把能算的给算了 eg： 1+7-9 -：当前新操作
                    while (!ops.isEmpty() && ops.peekLast() != '(') {
                        char prev = ops.peekLast();
                        if (opsOrderMap.get(prev) >= opsOrderMap.get(c)) {
                            cal(nums, ops);
                        } else {
                            //没有就继续遍历 eg: 12+9*1 当前运算符为 * 
                            break;
                        }
                    }
                    ops.addLast(c);
                }

            }

        }
        while (!ops.isEmpty()) {
            cal(nums, ops);
        }
        return nums.peekLast();
    }

    public void cal(Deque<Integer> nums, Deque<Character> ops) {
        if (nums.isEmpty()) {
            return;
        }
        if (ops.isEmpty()) {
            return;
        }
        int b = nums.pollLast();
        int a = nums.pollLast();
        char op = ops.pollLast();
        int res = 0;
        switch (op) {
            case '+':
                res = a + b;
                break;
            case '-':
                res = a - b;
                break;
            case '*':
                res = a * b;
                break;
            case '/':
                res = a / b;
                break;
            case '^':
                res = a ^ b;
                break;
            case '%':
                res = a % b;
                break;
        }
        nums.addLast(res);
    }

    public boolean isNumber(char c) {
        return Character.isDigit(c);
    }
}

解码方法[42]

思路：

  1. dfs分隔
  2. 但单单dfs，就超时了
  3. 得进行记忆化操作
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
class Solution {
    int n;
    int res = 0;

    public int numDecodings(String s) {
        n = s.length();
        dfs(0, s);
        return res;
    }

    public void dfs(int startIndex, String s) {
        if (startIndex == n) {
            res++;
            return;
        }
        for (int i = 1; i <= 2; i++) {
            if (startIndex + i  > n) {
                return;
            }
            String s1 = s.substring(startIndex, startIndex + i);
            if (s1.charAt(0) == '0' && s1.length() >= 1) {
                return;
            }
            int num = Integer.parseInt(s1);
            if (num > 26) {
                return;
            }
            dfs(startIndex + i, s);

        }
    }
}

记忆化后

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
class Solution {
    int n;
    int res = 0;
    int[] memo; // 用于记忆化

    public int numDecodings(String s) {
        n = s.length();
        memo = new int[n];
        Arrays.fill(memo, -1); // -1 表示未计算
        dfs(0, s);
        return res;
    }

    public void dfs(int startIndex, String s) {
        if (startIndex == n) {
            res++;
            return;
        }

        // 如果当前索引的结果已经计算过，直接累加并返回
        if (memo[startIndex] != -1) {
            res += memo[startIndex];
            return;
        }

        int beforeRes = res; // 记录进入这个索引前的 res

        for (int i = 1; i <= 2; i++) {
            if (startIndex + i > n) return;

            String s1 = s.substring(startIndex, startIndex + i);
            if (s1.charAt(0) == '0') return; // 0 开头不合法

            int num = Integer.parseInt(s1);
            if (num < 1 || num > 26) {
                return;
            }
            dfs(startIndex + i, s);
        }

        // memo[startIndex] = 当前索引开始的新方案数
        memo[startIndex] = res - beforeRes;
    }
}

验证回文串

思路：

  1. 熟悉几个API的使用
  2. 双指针
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean isPalindrome(String s) {
        int i = 0, j = s.length() - 1;
        while(i <= j){
            while(i < j && !Character.isLetterOrDigit(s.charAt(i))) i++;
            while(i < j && !Character.isLetterOrDigit(s.charAt(j))) j--;
            if(Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) return false;
            i++; j--;
        }
        return true;
    }
}

正则表达式匹配

有效的括号字符串

思路：

  1. 双栈，存小标
  2. 最后判断一下下标是否合法 eg：(* or *(
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 boolean checkValidString(String s) {
        Stack<Integer> left = new Stack();
        Stack<Integer> stars = new Stack();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                left.add(i);
            } else if (c == '*') {
                stars.add(i);
            } else {
                if (!left.isEmpty()) {
                    left.pop();
                } else if (!stars.isEmpty()) {
                    stars.pop();
                } else
                    return false;
            }

        }
        //eg：( *
        while(!stars.isEmpty() && !left.isEmpty()){
            if(stars.pop() < left.pop()){
                return false;
            }
        }
        return left.isEmpty();
    }
}

字母异位词分组[12]

思路：

  1. 字符串字典排序，然后MAP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String,List<String>> slots = new HashMap<>();
        for(String s: strs){
            char []cs = s.toCharArray();
            Arrays.sort(cs);
            String newS = new String(cs);
            if( slots.get(newS) == null){
                List<String>  list = new ArrayList<>();
                list.add(s);
                slots.put(newS,list);
            }
            else slots.get(newS).add(s);
        }
        return new ArrayList<>(slots.values()); 
    }
}

交错字符串[27]

题目：

思路：

  1. dfs，困惑：有时候连dfs的函数都想不出来，真的逆天，没想清楚是字符串是怎么匹配的。还是得把回溯树给画出来
  2. 回溯时间复杂度为2^k（k为s3的长度），故得进行记忆化，来剪枝
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
class Solution {
    int[][] cache;

    public boolean isInterleave(String s1, String s2, String s3) {
        int n1 = s1.length();
        int n2 = s2.length();
        int n3 = s3.length();
        if (n1 + n2 != n3) {
            return false;
        }
        cache = new int[n1][n2];
        //查找字符串里是否包含s1 但可断续
        return dfs(s1, s2, s3, 0, 0, 0);
    }

    public boolean dfs(String s1, String s2, String s3, int i, int j, int k) {
        if (i == s1.length() && j == s2.length() && k == s3.length()) {
            return true;
        }
        if (i + j > s3.length()) {
            cache[i][j]= -1;
            return false;
        }
        if (i < s1.length() && j < s2.length()) {
            if (cache[i][j] == -1) {
                return false;
            }
            if (cache[i][j] == 1) {
                return true;
            }
        }
        if (i < s1.length()) {
            if (s1.charAt(i) == s3.charAt(k) && dfs(s1, s2, s3, i + 1, j, k + 1)) {
                if (i < s1.length() && j < s2.length())
                    cache[i][j] = 1;
                return true;
            }
        }
        if (j < s2.length()) {

            if (s2.charAt(j) == s3.charAt(k) && dfs(s1, s2, s3, i, j + 1, k + 1)) {
                if (i < s1.length() && j < s2.length())
                    cache[i][j] = 1;
                return true;
            }
        }
        if (i < s1.length() && j < s2.length())
            cache[i][j] = -1;
        return false;
    }

    public boolean canForm(String t, StringBuilder sb) {
        int i = 0;
        int j = 0;
        while (j < t.length() && i < sb.length()) {
            if (t.charAt(j) == sb.charAt(i)) {
                j++;
                sb.setCharAt(i, '#');
            }
            i++;
        }
        return j == t.length();
    }
}

补充题9. 36进制加法

思路：就是大数相加的扩展

1

去除重复字母

字符串解码[90]

思路

  1. 类似于 基本计算器，也是双栈
  2. 一个栈存数字，一个栈存字符。这里的 [ 就类似于 *
  3. 逻辑，遇到字符，遍历直到不是字符，遇到数字也是，遇到] 就 cal运算。
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
class Solution {
    public String decodeString(String s) {
        Stack<Integer> nums = new Stack();
        Stack<String> chars = new Stack();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int startIndex = i;
                while (startIndex < s.length() && Character.isDigit(s.charAt(startIndex))) {
                    startIndex++;
                }
                nums.add(Integer.parseInt(s.substring(i, startIndex)));
                i = startIndex - 1;
            } else if (c == ']') {
                cal(nums, chars);
            } else if (c == '[') {
                chars.add(c + "");
            } else {
                int startIndex = i;
                while (startIndex < s.length() && s.charAt(startIndex) >= 'a' && s.charAt(startIndex) <= 'z') {
                    startIndex++;
                }
                chars.add(s.substring(i, startIndex));
                i = startIndex - 1;
            }
        }
        //System.out.println(chars);

        StringBuilder res = new StringBuilder();
        List<String> list = new ArrayList();
        while (!chars.isEmpty()) {
            list.add(chars.pop());
        }
        for (int i = list.size() - 1; i >= 0; i--) {
            res.append(list.get(i));
        }
        return res.toString();
    }

    public void cal(Stack<Integer> nums, Stack<String> chars) {
        // 基础检查，如果栈为空则返回
        if (nums.isEmpty() || chars.isEmpty()) {
            return;
        }

        // 1. 获取重复因子
        int factor = nums.pop();

        // 2. 提取需要重复的字符串片段
        StringBuilder segment = new StringBuilder();
        while (!chars.isEmpty() && !chars.peek().equals("[")) {
            // 优化点 1: Pop and Prepend (弹出并前置)
            // 将弹出的片段插入到 StringBuilder 的开头 (index 0)
            // 这样可以避免额外的 List 存储和二次反转操作
            segment.insert(0, chars.pop());
        }

        // 3. 移除开头的左括号 '['
        if (!chars.isEmpty() && chars.peek().equals("[")) {
            chars.pop();
        }

        // 4. 重复片段并推回栈中
        String segmentStr = segment.toString();

        // 优化点 2: 使用 String.repeat() (推荐 Java 11+)
        String repeatedString = segmentStr.repeat(factor);

        chars.push(repeatedString);
    }
}

时间复杂度

发表于 更新于

每个标签前三十道

面试前API复习

发表于 更新于 分类于

TCP和UDP可以同时绑定相同的端口吗？

可以的，网络层会根据你IP包头的协议号就知道该数据包是TCP还是UDP，就确定发给哪一个模块处理

原因在于：操作系统内核管理 socket 的时候，区分的不是单纯的端口号，而是 (协议, 本地IP, 本地端口, 远

端IP, 远端端口) 这个五元组。

多个TCP服务进程可以绑定同一个端口吗？

如果多个TCP服务进程绑定的端口 IP地址和端口号相同，那就不行，执行bind()会报错

但如果那个Socket设置了SO_REUSEADDR，只要两个进程bind的IP不相同。那就是可以的

如何解决服务端进程重启时，报错“Address already in use”的问题？

当我们重启TCP服务进程的时候，意味着服务端发起了关闭连接操作。于是就是会经过四次挥手。而对于

主动关闭方，会在TIME_WAIT状态停留一段时间，这个时间大概是2MSL

当tcp服务进程重启时，服务端会出现TIME_WAIT状态的连接，TIME_WAIT状态的连接仍然没有释放ip+port

故执行bind()会报错，address already in use

要解决这个问题，我们可以对Socket 设置 so_reuseadd

这样即使存在一个和bind ip和port一样的TIME_WAIT状态的连接，那还是可以绑定成功，从而重启成功

客户端的端口可以重复使用吗？

确定唯一的连接是靠五元组（协议，源IP，源端口，目标IP，目标端口），只要其中一个不一样就表明是不同

的连接

内核是通过四元组信息来定位一个 TCP 连接的

客户端 TCP 连接 TIME_WAIT 状态过多，会导致端口资源耗尽而无法建立新的连接吗？

针对这个问题，那得看客户端连的是不是都是同一个服务器（ip,port相同）

如果不一样的话，端口是可以复用的。

一样的话，就会被端口的数量限制住

所以，如果客户端都是与不同的服务器建立连接，即使客户端端口资源只有几万个， 客户端发起百万级连接也是没问题的（当然这个过程还会受限于其他资源，比如文件描述符、内存、CPU 等）。

如何解决客户端TIME_WAIT连接过多，导致无法同时和同一个服务器建立连接的问题？

打开tcp_tw_reuse。你客户端调用connect()时，如果发现已经有链接占用ip和port，会检查原有连接是否是

TIME_WAIT状态，然后检查该链接是否存在超过了1s，如果是的话，那就复用它

不过这种方式比较激进，Linux2.4已经被废弃了

发表于 更新于 分类于 ，

服务端只bind了ip和端口，但是没有listen这个socket监听，客户端此时发起建立连接，会怎样？

服务端会返回RST，即把SYN丢掉

RST 报文是什么？

RST 报文是 TCP 中的一种“暴力”断开连接的方式。它的意思是 Reset，即“复位”。当接收方发送 RST 时，它是在告诉对方：“我无法建立这个连接，请立即终止！” 这和正常的四次挥手断开连接不同，RST 是一种不包含任何确认的、突然的连接终止。

不使用listen，可以建立tcp连接吗

可以的。tcp自连接（同一台机器内的不同进程连），也可以是两个客户端同时发起建立连接的请求（两个独

立的客户端之间，它们同时尝试与对方建立连接）。

这两种情况都不需要listen，但都可以建立连接

半连接和全连接队列都是在服务端listen时内核自动创建的，故客户端是没有这个东西的。

但内核有个全局hash表，用来存放sock的信息

在tcp自连接中，客户端在connec方法中，会将自己的连接信息放入这个全局hash表中

然后将信息发出，消息经过回环地址重新回答tcp传输层时，就会根据IP+端口信息去这个全局hash中取信息

于是握手一来一回，最后成功建立连接

在两个独立的客户端之间，同时尝试与对方建立连接时：

发表于 分类于 ，

半连接队列：是一个hash表，服务端第一次握手后，会将sock存于这个队列里，队列中的sock都处于SYN_RECV状态

全连接队列：是一个链表，在服务端收到三次握手后，就会将Sock从半连接队列中取出，然后放到全连接队列中

队列中。队列中的sock都处于一个established状态，等待服务端执行accept()后就可以取出了

可以的，建立连接根本就不需要 accept的参与，accept意义在于从全连接队列中取出一条连接

虽然都叫队列，但其实全连接队列（icsk_accept_queue）是个链表（accpet方便取出），而半连接队列（syn_table）是个哈希表（第三次握手来了方便找到是哪个socket）。

发表于 分类于 ，

建立连接时会丢包

如果对方全连接或者半连接满了，会拒绝建立请求的

流量控制时丢包

发送数据过快时，超过流控队列 即 内核里面控制数据流量大小的队列 的长度

网卡丢包

Ringbuffer过小会溢出，丢包

网卡处理不过来会丢包

超出对方内核接受缓冲区大小

两端之间网络传输丢包

对于这些丢包现象，采用tcp想协议栈可以解决吗

tcp保证的可靠性只是说保证发送方能可靠地把数据从已方的传输层发到对方的传输层

至于数据到了接收方的传输层后，能不能到应用层，tcp是不管的

假设我们现在用手机给朋友发送一条消息，走到传输层的tcp缓冲区，然后发出，不管中间有没有丢包

最后通过重传保证发到了对方的缓冲区，此时接受端就会回一个ack，然后发送端收到ack后就会把缓存

区里的这一条消息摘掉。到这里tcp的任务就结束了

tcp的任务是结束了，但聊天软件的任务还没结束

聊天软件还需要把消息从tcp缓冲区里读出来，如果在读的时候手机内存不足，程序直接杀死了

但这时候发送端是不可能回重传的

于是乎，消息就丢了么

这个问题其实在两个用户之间加一层服务器中转即可（PS：但有一说一，服务器也会挂 狗头）

对于发送方，只要定时跟服务端的内容对账一下，就知道哪条消息没发送成功，直接重发就好了。

如果接收方的聊天软件崩溃了，重启后跟服务器稍微通信一下就知道少了哪条数据，同步上来就是了，所以也不存在上面提到的丢包情况。

两端通信的时候也能对账，为什么还要引入第三端服务器？ 

- 第一，如果是两端通信，你聊天软件里有1000个好友，你就得建立1000个连接。但如果引入服务端，你只需要跟服务器建立1个连接就够了，聊天软件消耗的资源越少，手机就越省电。 
- 第二，就是安全问题，如果还是两端通信，随便一个人找你对账一下，你就把聊天记录给同步过去了，这并不合适吧。如果对方别有用心，信息就泄露了。引入第三方服务端就可以很方便的做各种鉴权校验。 
- 第三，是软件版本问题。软件装到用户手机之后，软件更不更新就是由用户说了算了。如果还是两端通信，且两端的软件版本跨度太大，很容易产生各种兼容性问题，但引入第三端服务器，就可以强制部分过低版本升级，否则不能使用软件。但对于大部分兼容性问题，给服务端加兼容逻辑就好了，不需要强制用户更新软件。

发表于 更新于 分类于 ，

序言

我们都知道，程序的数据一般都打到tcp的segement里，然后打到IP的packet，再到达以太网的frame(帧)

后发送到对端

:::color4

:::

tcp头格式

你需要注意这么几个事情

  • tcp是没有IP地址的，那是IP层的事情
  • tcp需要一个四元组来标明是一个连接（源端口，源IP，目标端口，目标IP）当然还需要一个协议
  • 四个重要的东西
    1.seq num：包的序号，用来解决乱序问题

2.ack num：用于确认收到，解决不丢包的问题
· 3.window 滑动窗口，用于解决流控

4.tcp flag 主要用来操控tcp的状态机的

tcp状态机

其实，网络上的传输是没有连接的，包括TCP也是一样的。而TCP所谓的“连接”，其实只不过是在通讯的双方维护一个“连接状态”，让它看上去好像有连接一样。所以，TCP的状态变换是非常重要的。

为什么建链接要3次握手？

syn即synchronize sequance number 同步序号么，后序传输数据都会基于这个序号，那么三次的话你来我往

的话才能知根知低

断链接需要4次挥手？

你仔细看其实只有两次，因为tcp是全双工通信，两条通道，所以，发送方和接收方都需要Fin和Ack

只不过，有一方是被动的，所以看上去就成了所谓的4次挥手。如果两边同时断连接，那就会就进入到

CLOSING状态，然后到达TIME_WAIT状态

  • 单工通信（Simplex）：只能单方向传输，比如电视广播，只能电视台发 → 用户收，用户不能回传。
  • 半双工通信（Half Duplex）：可以双向传输，但不能同时，要轮流，比如对讲机，“你说完我再说”。
  • 全双工通信（Full Duplex）：可以双向同时进行，比如电话、现代以太网。

多事

  • 建立连接时超时了。Client发出syn后，Server接受到了，发给SYN-ACK后但这时候Client下线了怎么办？

那么这个连接就处于一个中间状态，没成功也没失败。收不到Client的ack一段时间后在Linux下，Server默认会采用一个重试措施，默认重试次数为5次，重试的间隔时间从1s开始每次都翻售，5次的重试时间间隔为1s, 2s, 4s, 8s, 16s，总共31s，而第5次后得等32秒才能停止等待，故总共是63s，这个时候tcp才会断开

  • SYN Flood攻击。基于上述情况，就有人利用这种机制，恶意攻击你，发一个syn后，客户端下线，让你的syn连接的队列耗尽（syn队列就是存放那些半连接状态的连接的）。于是，Linux下给了一个叫tcp_syncookies的参数来应对这个事——当SYN队列满了后，TCP会通过源地址端口、目标地址端口和时间戳打造出一个特别的Sequence Number发回去（又叫cookie），如果是攻击者则不会有响应，如果是正常连接，则会把这个 SYN Cookie发回来，然后服务端可以通过cookie建连接（即使你不在SYN队列中）。请注意，请先千万别用tcp_syncookies来处理正常的大负载的连接的情况。因为，synccookies是妥协版的TCP协议，并不严谨。对于正常的请求，你应该调整三个TCP参数可供你选择，第一个是：tcp_synack_retries 可以用他来减少重试次数；第二个是：tcp_max_syn_backlog，可以增大SYN连接数；第三个是：tcp_abort_on_overflow 处理不过来干脆就直接拒绝连接了。
  • 关于Inital Sequence Number。并不是所有syn 的起始值都是一样的。如果是的话，那就乱套了。那是跟一个假时钟绑定的，每四微妙++，直到2的32次方，然后归0。这样，一个ISN的周期大约是4.55个小时。因为，我们假设我们的TCP Segment在网络上的存活时间不会超过Maximum Segment Lifetime（缩写为MSL – Wikipedia语条），所以，只要MSL的值小于4.55小时，那么，我们就不会重用到ISN，也就不会出错
  • 关于 MSL 和 TIME_WAIT。为什么关闭连接的时候要有Time_wait？而不是直接关闭？这主要是保证对端能接受到我这边发的ack，如果被动关闭的那方没有收到Ack，就会触发被动端重发Fin，一来一去正好2个MSL，2）以及有足够的时间让这个连接不会跟后面的连接混在一起（你要知道，有些自做主张的路由器会缓存IP数据包，如果连接被重用了，那么这些延迟收到的包就有可能会跟新连接混在一起）
  • 关于TIME_WAIT数量太多。这在主要体现在有大量短连接请求下（比如http1/2）。timewait太多是会占据掉大部分资源的。但你去网上搜相关教程，太多都会去教你去调两参数 tcp_tw_reuse,tcp_tw_recycle。这两个参数默认都是关闭的，两个参数涉及到的机制都比较激进。
  • 关于tcp_tw_reuse，tcp_tw_recycle，tcp_max_tw_buckets（对抗DDoS攻击的）参数

tcp_tw_resuse,tcp_tw_recycle因为这两个参数违反了TCP协议。

在 Linux 4.12 版本后被彻底移除

其实，TIME_WAIT表示的是你主动断连接，所以，这就是所谓的“不作死不会死”。试想，如果让对端断连接，那么这个破问题就是对方的了，呵呵。另外，如果你的服务器是于HTTP服务器，那么设置一个HTTP的KeepAlive有多重要（浏览器会重用一个TCP连接来处理多个HTTP请求），然后让客户端去断链接（你要小心，浏览器可能会非常贪婪，他们不到万不得已不会主动断连接）。

数据传输中的seq num

SeqNum的增加是和传输的字节数相关

上图中，三次握手后，来了两个Len:1440的包，而第二个包的SeqNum就成了1441。然后第一个ACK回的是

1441，表示第一个1440收到了。

tcp重传机制

tcp要保证包都到达接收方，就得有重传机制

接收端给发送端的Ack确认只会确认最后一个连续的包，即遵循累计确认原则

PS：ack = seq + 1

接收端收到了1 2 可以 回ack = 3

但接收端收到了1 2 4 这时候就不可以回 ack = 5。会再次发送 ack = 3

这时候发送端就知道得重传seq = 3的包

不这样的话，发送端就会以为之前的包都收到了

1. 累积确认是什么？

“接收端给发送端的 Ack 确认只会确认**最后一个连续的包”这句话解释了累积确认的精髓。**

*在 TCP 中，接收端发回的 ACK 报文（确认号）不是用来确认单个数据包，而是用来告诉发送端：“我收到了到这个序号为止的所有数据，你下次可以从这个序号开始发了。”*

  • 例子：
    • 发送端发送了数据包 1、2、3、4、5。
    • 接收端收到了 1 和 2。
    • 接收端会发送一个 ACK 报文，其确认号为 3。这表明它成功收到了序号 1 和 2 的数据，并期望收到序号为 3 的数据。

2. “收到了 4（注意此时 3 没收到），此时的 TCP 会怎么办？”

这是一个非常好的问题，它展示了 TCP 的乱序处理能力。

  • 接收端行为：
    • 收到数据包 1 和 2 后，它会发送 ACK 3。
    • 接着收到了数据包 4。因为它没有收到 3，所以 4 是一个乱序的数据包。
    • 此时，接收端不能发送 ACK 5（因为 3 没收到，确认不连续），它会**再次发送 ACK 3。**
  • 发送端行为：
    • 发送端一开始发送了 1、2、3、4、5。
    • 它收到了接收端发来的 ACK 3。这表示 1 和 2 已经到达，它可以继续发送更多数据了。
    • 但是，发送端很快又收到了**重复的 ACK 3。当它收到多个（通常是 3 个）重复的 ACK 报文时，它就知道序号为 3 的数据包很可能丢失了。**
    • 这时，TCP 会触发快速重传（Fast Retransmit）机制，立即重新发送数据包 3，而不需要等到超时后才重传。

超时重传机制

一种是如果发送方死等不回来 ack = 3。那么这时候就会触发超时重传，一旦接收方收到seq3，就会回ack=4

那么发送方就知道3和4都收到了

但是这种方式也有比较严重的问题，因为你要死等3,那么4,5的状态其实是不得知的。这时候tcp可能就会悲观

地认为它们都需要重传

对此有两种选择

1.只重传Timeout的包，即 3

2.重传timeout后的所有包，即 3 4 5

两种说好不好，第一种节省带宽，但费时，第二种可能会做无用工，两者都在等Timeout。PS：这个timeout

是tcp动态计算出来的

快速重传机制

为了解决timeout的问题，tcp就引入了一种快速重传算法，不以时间驱动，而是以数据驱动

也就是说如果包没有连续到达的话，就ack那个最后有可能丢失的包。如果发送发接受到了三次相同的ack，

就重传这个包。快速重传的好处就是 不用等待超时

比如：如果发送方发出了1，2，3，4，5份数据，第一份先到送了，于是就ack回2，结果2因为某些原因没收到，3到达了，于是还是ack回2，后面的4和5都到了，但是还是ack回2，因为2还是没有收到，于是发送端收到了三个ack=2的确认，知道了2还没有到，于是就马上重转2。然后，接收端收到了2，此时因为3，4，5都收到了，于是ack回6。示意图如下：

Fast Retransmit只解决了一个问题，就是timeout的问题，它依然面临一个艰难的选择，就是，是重传之前的一个还是重传所有的问题。对于上面的示例来说，是重传#2呢还是重传#2，#3，#4，#5呢？因为发送端并不清楚这连续的3个ack(2)是谁传回来的？也许发送端发了20份数据，是#6，#10，#20传来的呢。这样，发送端很有可能要重传从2到20的这堆数据（这就是某些TCP的实际的实现）。可见，这是一把双刃剑。

还是有弊端，就是发送发不清楚，后两次是谁发的，如果丢的不止一个包呢。

SACK机制

还有更好的方式，SACK

Selective Acknowledgment

这个需要再tcp头里添加一个字段，用来记录 收到的不连续包块

比如发送端只收到了 1 2 4 5 7 8 10

这样的话，发送端就知道哪些没到，哪些到了，那么这样就可以准确地重传那些没到了

当然这个协议需要两边都支持，在 Linux下，可以通过tcp_sack参数打开这个功能（Linux 2.4后默认打开）。

当这还是有问题，即接收方有权把已经报给发送端SACK里的数据给丢了，比如内存不够用了

所以，发送方也不能完全依赖SACK，还是要依赖ACK，并维护Time-Out，如果后续的ACK没有增长，那么还是要把SACK的东西重传，另外，接收端这边永远不能把SACK的包标记为Ack。

而且维护SACK是会耗发送发资源的，如果一个攻击者发送给发送方很多这种SACK，让发送方重发一堆东西

Duplicate SACK – 重复收到数据的问题

其主要使用了SACK来告诉发送方有哪些数据被重复接收了