rhb_blog

rao的博客

0%

发表于 更新于 分类于 ，

滑动窗口主要用来处理连续问题。比如题目求解“连续子串 xxxx”，“连续子数组 xxxx”，就应该可以想到滑动窗口。能不能解决另说，但是这种敏感性还是要有的。

从类型上说主要有：

  • 固定窗口大小
  • 窗口大小不固定，求解最大的满足条件的窗口
  • 窗口大小不固定，求解最小的满足条件的窗口（上面的 209 题就属于这种）

后面两种我们统称为可变窗口。当然不管是哪种类型基本的思路都是一样的，不一样的仅仅是代码细节。

固定窗口大小

对于固定窗口，我们只需要固定初始化左右指针 l 和 r，分别表示的窗口的左右顶点，并且保证：

  1. l 初始化为 0
  2. 初始化 r，使得 r - l + 1 等于窗口大小
  3. 同时移动 l 和 r
  4. 判断窗口内的连续元素是否满足题目限定的条件
    • 4.1 如果满足，再判断是否需要更新最优解，如果需要则更新最优解
    • 4.2 如果不满足，则继续。

可变窗口大小

对于可变窗口，我们同样固定初始化左右指针 l 和 r，分别表示的窗口的左右顶点。后面有所不同，我们需要保证：

  1. l 和 r 都初始化为 0
  2. r 指针移动一步
  3. 判断窗口内的连续元素是否满足题目限定的条件
    • 3.1 如果满足，再判断是否需要更新最优解，如果需要则更新最优解。并尝试通过移动 l 指针缩小窗口大小。循环执行 3.1
    • 3.2 如果不满足，则继续。

形象地来看的话，就是 r 指针不停向右移动，l 指针仅仅在窗口满足条件之后才会移动，起到窗口收缩的效果。

Leetcode 3.无重复字符的最长子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int r = 0;
        int l = 0;
        int max =0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        for(r = 0;r<s.length();r++)//右边的窗口是一直往前走的
        {
            if(map.containsKey(s.charAt(r)))//当不符合条件时，左边窗口移动
                l = Math.max(l,map.get(s.charAt(r)) + 1);//只有右边加进窗口的元素是重复的，左边才会移动，所以要移动到重复元素后面一位
            map.put(s.charAt(r),r);
            max = Math.max(max,r-l+1);
        }
        return max;
        }
    }

Leetcode 76.最小覆盖子串

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 minWindow(String s, String t) {
        if (s == null || s == "" || t == null || t == "" || s.length() < t.length()) {
            return "";
        }
        int t_length=t.length();
        char[] chars = s.toCharArray(), chart = t.toCharArray();
        int[] hold = new int[128];//记录窗口中的元素和其个数
        //记录t中的所有元素和元素出现的个数
        for(int i = 0;i<t_length;i++)
        {
            char temp=chart[i];
            hold[temp]--;
        }
        String output="";
        int right=0;
        int left=0;
        int count=0;//窗口中含有t字符串的元素个数
        for(right=0;right<s.length();right++)
        {
            hold[chars[right]]++;
            if(hold[chars[right]]<=0)count++;//表示右边框进来的是t中的元素
            //当窗口元素达到要求后，此时的目标是找到最小的窗口
            //情况一：左边的元素是不需要的，直接进行左窗口移位
            //情况二：左边的元素是需要的，但是此时右边寻找到了一样的元素，为了进行最小窗口的迭代，将左窗口移位
            while(count==t_length&&hold[chars[left]]>0)
            {
                hold[chars[left]]--;
                left++;
            }
            //进行最小子串的迭代
            if(count==t_length)
            if(output==""||output.length()>right-left+1)
                output=s.substring(left,right+1);
        }
        return output;
    }
}

Leetcode 209.长度最小的子数组

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 minSubArrayLen(int target, int[] nums) {
        int right=0;
        int left=0;
        int num=0;//记录子数组和
        int count=0;//记录子数组个数
        for(right=0;right<nums.length;right++)
        {
            num+=nums[right];
            while(num>=target)
            {
                //最小子数组迭代
                if(count==0||count>right-left+1)
                    count=right-left+1;
                //在满足要求的基础上寻找最小子数组
                //此时不断压缩左边窗口，可以遍历出所有满足要求的窗口
                num-=nums[left];
                left++;
            }
        }
        return count;
    }
}

发表于 更新于 分类于 ，

树的遍历——颜色标记法

我们知道垃圾回收算法中，有一种算法叫三色标记法。 即：

  • 用白色表示尚未访问
  • 灰色表示尚未完全访问子节点
  • 黑色表示子节点全部访问

那么我们可以模仿其思想，使用双色标记法来统一三种遍历。

其核心思想如下：

  • 使用颜色标记节点的状态，新节点为白色，已访问的节点为灰色。
  • 如果遇到的节点为白色，则将其标记为灰色，然后将其右子节点、自身、左子节点依次入栈。
  • 如果遇到的节点为灰色，则将节点的值输出。

剑指 Offer 34.二叉树中和为某一定值

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 
{
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<Integer> node = new ArrayList<Integer>();
        bfs(root,0,node,sum);
        return list;
    }
    public void bfs(TreeNode root,int all,List node,int sum)
    {
        if(root==null)return;
        node.add(root.val);
        all+=root.val;
        if(sum==all)//从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
        {
            list.add(new ArrayList<>(node));
            //return;如果加了return 会得不到正确的结果。因为代码提前return，导致后面的remove没有执行，影响回溯了。
        }
        bfs(root.left,all,node,sum);
        bfs(root.right,all,node,sum);
        node.remove(node.size()-1);
    }
}

发表于 更新于 分类于 ，

链表

链表的注意点

  • 出现了环，导致了死循环
  • 分不清楚边界，导致边界出错
  • 搞不清递归

环

  • 判断是否有环，以及环的位置————快慢指针算法

边界

  • 当题目中的头节点需要进行操作时，可能会被移除时，要考虑使用虚拟节点，也就是头节点。这样操作就会避免对第一个节点的讨论

前后序

相较于树，在链表中只有一个后续指针，只有前序和后序，没有中序遍历。

如果是前序遍历，那么你可以想象前面的链表都处理好了，怎么处理的不用管。相应地如果是后序遍历，那么你可以想象后面的链表都处理好了，怎么处理的不用管。

  1. e.g.前序遍历
1
2
3
4
5
6
7
8
def dfs(head,pre):
    if not head return pre//递归的结束条件
    next=head.next
    ##此处添加主逻辑
    head.next = pre
    dfs(next,head)

dfs(head,None)

一些技巧

头结点————虚拟结点

头结点不需要参与运算，不需要特殊判断

快慢指针

判断链表是否有环以及环的入口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null||head.next==null)return false;
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast!=null&&fast.next!=null)//考虑了链表的长度可能为奇数也可能是偶数的情况
        {//快慢指针相遇即表示为存在一个环
            if(fast==slow)return true;
            fast=fast.next.next;
            slow=slow.next;
        }
        return false;
    }
}

leetcode题目

Leetcode 61.旋转链表

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 ListNode rotateRight(ListNode head, int k) {
        if(head==null)return head;
        ListNode pre_newHead = new ListNode();//
        ListNode temp = new ListNode();
        pre_newHead = head;
        temp=head;
        for(int i=0;i<k;i++)
        {
            if(temp.next!=null)
                temp=temp.next;
            else
            {
                temp=head;//转回去了
            }
        }
        while(temp.next!=null)
        {
            pre_newHead = pre_newHead.next;
            temp = temp.next;
        }
        temp.next = head;//首位相连构成循环链表
        head=pre_newHead.next;
        pre_newHead.next=null;
        return head;   
    }
}

Leetcode 82.删除排序链表中的重复元素

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 ListNode deleteDuplicates(ListNode head) {
        
        if(head==null)return null;
        if(head.next==null)return head;
        ListNode dummyhead = new ListNode(0,head);//头指针
        ListNode q = new ListNode();
        ListNode pre = new ListNode();
        pre=dummyhead;
        q=head;
        while(q!=null)
        {
            if(q.next!=null&&q.val==q.next.val){
                while(q.next!=null&&q.val==q.next.val)//遇到重复的节点
                {
                    q=q.next;//遍历到重复节点的末端
                }            
                pre.next=q.next;
            }
            else
            {
                pre = q;//pre往后移动
            }
            q=q.next;
        }
        return dummyhead.next;
    }
}

此题最为巧妙的是运用了头指针，这样可以减少对第一个元素的讨论。

Leetcode .反转链表

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 ListNode reverseList(ListNode head) {
        ListNode cur = head;
        ListNode pre=null;
        while(cur!=null)
        {
            ListNode nextTemp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nextTemp;
        }
        return pre;
    }
}
//递归
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }
}

Leetcode 92.反转链表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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
            if(head==null)return null;
            ListNode pre = new ListNode(0,head);//防止m=1的情况
            ListNode dummy =pre;
            ListNode cur = head;
            //移动到待反转的位置上
            while(m>1)
            {
                pre=cur;
                cur=cur.next;
                m--;
                n--;
            }
            ListNode change_begin_pre =pre;
            ListNode change_begin=cur;
            ListNode temp=null;
        //对链表进行反转
            while(n>0)
            {
                temp = cur.next;
                cur.next=pre;
                pre=cur;
                cur=temp;
                n--;
            }
            change_begin_pre.next=pre;
            change_begin.next=cur;
            return dummy.next;
    }
}

Leetcode 142.环形链表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
//还是使用左右指针
 /*概括一下：
假设慢指针走了s步，则快指针走了2s步
f=2s （快指针每次2步，路程刚好2倍）
f = s + nb (相遇时，刚好多走了n圈）
推出：s = nb
从head结点走到入环点需要走 ： a + nb， 而slow已经走了nb，那么slow再走a步就是入环点了。
如何知道slow刚好走了a步？ 从head开始，和slow指针一起走，相遇时刚好就是a步
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(true)
        {
            if(fast==null||fast.next==null)return null;
            slow=slow.next;
            fast=fast.next.next;
            if(fast==slow)break;
        }
        fast=head;
        while(fast!=slow)
        {
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
}

Leetcode 234.回文链表

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 {
    private ListNode frontPointer;//正方向进行迭代

    private boolean recursivelyCheck(ListNode currentNode) 
    {
        if (currentNode != null) {
            //currentNode指针是先到尾节点，由于递归的特性再从后往前进行比较
            if (!recursivelyCheck(currentNode.next)) {
                return false;
            }
            if (currentNode.val != frontPointer.val) {
                return false;
            }
            frontPointer = frontPointer.next;
        }
        return true;
    }
    public boolean isPalindrome(ListNode head) {
        frontPointer = head;
        return recursivelyCheck(head);
    }
}

Leetcode 143.重排链表

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
class Solution {
    public void reorderList(ListNode head) {
        if(head==null)return ;
        if(head.next==null)return ;
        ListNode slow = head;
        ListNode fast = head.next;
        while(true)
        {
            if((fast!=null&&fast.next==null)||fast==null)
            {
                break;
            }
            slow=slow.next;
            fast=fast.next.next;
        }
        //无论链表的长度是奇数还是偶数，都是从slow指针的next结点进行比较
        ListNode temp = slow.next;
        slow.next=null;//前半截的链表进行截断
        temp = reverseList(temp);
       mergeList(head,temp);
    }
    //进行反转
     private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
    //链表进行合并
     public void mergeList(ListNode l1, ListNode l2) {
        ListNode l1_tmp;
        ListNode l2_tmp;
        while (l1 != null && l2 != null) {
            l1_tmp = l1.next;
            l2_tmp = l2.next;

            l1.next = l2;
            l1 = l1_tmp;

            l2.next = l1;
            l2 = l2_tmp;
        }
    }
}

Leetcode 148.排序链表

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
/* 知识点1：归并排序的整体思想
 * 知识点2：找到一个链表的中间节点的方法
 * 知识点3：合并两个已排好序的链表为一个新的有序链表
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode fast = head.next, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode temp = slow.next;//找到中间结点
        slow.next=null;
        ListNode left = sortList(head); //递归排序前一段链表
        ListNode right = sortList(temp); //递归排序后一段链表
        return merge(left,right);
    }
     public ListNode merge(ListNode h1,ListNode h2){ //合并两个有序链表
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        while(h1!=null && h2!=null){
            if(h1.val < h2.val){
                p.next = h1;
                h1 = h1.next;
            }else{
                p.next = h2;
                h2 = h2.next;
            }
            p = p.next;
        }
        if(h1!=null)    p.next = h1;
        else if(h2!=null) p.next = h2;
        return dummy.next;

    }
}
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
//迭代
class Solution {
    public ListNode sortList(ListNode head) {
        int length = getLength(head);
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
       
        for(int step = 1; step < length; step*=2){ //依次将链表分成1块，2块，4块...
       /*第一轮合并时intv = 1，即将整个链表切分为多个长度为1的单元，并按顺序两两排序合并，合并完成的已排序单元长度为2。
第二轮合并时intv = 2，即将整个链表切分为多个长度为2的单元，并按顺序两两排序合并，合并完成已排序单元长度为4。
以此类推，直到单元长度intv >= 链表长度，代表已经排序完成。
*/
            //每次变换步长，pre指针和cur指针都初始化在链表头
            ListNode pre = dummy; 
            ListNode cur = dummy.next;
            while(cur!=null){
                ListNode h1 = cur; //第一部分头 （第二次循环之后，cur为剩余部分头，不断往后把链表按照步长step分成一块一块...）
                ListNode h2 = split(h1,step);  //第二部分头
                cur = split(h2,step); //剩余部分的头
                ListNode temp = merge(h1,h2); //将一二部分排序合并
                pre.next = temp; //将前面的部分与排序好的部分连接
                while(pre.next!=null){
                    pre = pre.next; //把pre指针移动到排序好的部分的末尾
                }
            }
        }
        return dummy.next;
    }
    public int getLength(ListNode head){
    //获取链表长度
        int count = 0;
        while(head!=null){
            count++;
            head=head.next;
        }
        return count;
    }
    public ListNode split(ListNode head,int step){
        //断链操作 返回第二部分链表头
        if(head==null)  return null;
        ListNode cur = head;
        for(int i=1; i<step && cur.next!=null; i++){
            cur = cur.next;
        }
        ListNode right = cur.next;
        cur.next = null; //切断连接
        return right;
    }
    public ListNode merge(ListNode h1, ListNode h2){
    //合并两个有序链表
        ListNode head = new ListNode(-1);
        ListNode p = head;
        while(h1!=null && h2!=null){
            if(h1.val < h2.val){
                p.next = h1;
                h1 = h1.next;
            }
            else{
                p.next = h2;
                h2 = h2.next;
            }
            p = p.next;           
        }
        if(h1!=null)    p.next = h1;
        if(h2!=null)    p.next = h2;

        return head.next;     
    }
}

作者：cherry-n1
链接：https://leetcode-cn.com/problems/sort-list/solution/pai-xu-lian-biao-di-gui-die-dai-xiang-jie-by-cherr/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

发表于 更新于 分类于 ，

回溯

回溯法思路的简单描述是：把问题的解空间转化成了图或者树的结构表示，然后使用深度优先搜索策略进行遍历，遍历的过程中记录和寻找所有可行解或者最优解。

回溯法的基本行为是搜索，搜索过程使用剪枝函数来为了避免无效的搜索。剪枝函数包括两类：1. 使用约束函数，剪去不满足约束条件的路径；2.使用限界函数，剪去不能得到最优解的路径。

回溯法实现————递归和迭代

leetcode 40.组合总和

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
/*
输入：candidates = [2,3,5], target = 8,
所求解集为：
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]
*/
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        List<Integer> node = new ArrayList<Integer>();
        dfs(candidates,target,0,node,list);
        return list;
    }
    public void dfs(int[] candidates,int target,int i,List<Integer>node,List<List<Integer>>list)
    {
        int length=candidates.length;
        if(i==length)return;
        if(target==0)
        {
            list.add(new ArrayList<Integer>(node));
            return;
        }
        dfs(candidates,target,i+1,node,list);
        if(target-candidates[i]>=0)
        {
            node.add(candidates[i]);
            target-=candidates[i];
            dfs(candidates,target,i,node,list);
            node.remove(node.size()-1);
        }
    }
}

leetcode 46.全排列

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
/*
输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]
*/
class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        List<Integer> node = new ArrayList<Integer>();
        boolean[] visited = new boolean[nums.length];//判断该数有没有被选择
        dfs(node,nums,visited);
        return list;
    }
    public void dfs(List<Integer> node,int[]nums,boolean[]visited)
    {
        if(node.size()==nums.length)//递归结束条件
        {
            list.add(new ArrayList<>(node));
            return;
        }
        for(int i = 0;i<nums.length;i++)//在递归中使用for循环可以依次取nums中的每个元素当头。然后进入递归后可以构造出经过所有每一元素路径的遍历树
        {
            if(!visited[i])
            {
                node.add(nums[i]);
                visited[i]=true;
                dfs(node,nums,visited);
// 注意：下面这两行代码发生 「回溯」，回溯发生在从 深层结点 回到 浅层结点 的过程，代码在形式上和递归之前是对称的
                visited[i]=false;
                node.remove(node.size()-1);
            }
        }
        
    }
}

leetcode 47.全排列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
//全排列的两道题目和组合总和的两道题目本质上是差不多的，在存在重复数字的时候，这里采用的的方法是：
//将数组中的元素进行排列，然后针对重复的部分进行剪枝：遍历数组中每个元素当头时，当前后两个元素相同的时候跳过
class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<Integer> node = new ArrayList<Integer>();
        boolean visited[] = new boolean[nums.length];
        Arrays.sort(nums);
        dfs(node,nums,visited);
        
        return list;
    }
    public void dfs(List node,int[]nums,boolean[]visited)
    {
        if(node.size()==nums.length)
        {
            list.add(new ArrayList<>(node));
            return;
        }
        for(int i =0;i<nums.length;i++)
        {
            if(!visited[i])
            {
                //此处剪枝
                //i>0&&nums[i]==nums[i-1]的含义是当前后两个元素相同时，跳过后一个元素当头。
                //!visited[i-1]针对的是后续排列的时候当前面元素已被选择，跳过后面和他相同的元素
                if(i>0&&nums[i]==nums[i-1]&&!visited[i-1])continue;
                node.add(nums[i]);visited[i]=true;
                dfs(node,nums,visited);
                visited[i]=false;
                node.remove(node.size()-1);
            }
        }
    }
}

leetcode 77.组合

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 {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        List<Integer> node = new ArrayList<>();

        dfs(node,n,k,1);
        return list;
    }
    public void dfs(List node,int n,int k,int start)
    {
        if(node.size()==k)
        {
            list.add(new ArrayList<>(node));
            return;
        }
        for(int i=start;i<=n;i++,start++)
            //start++表示的意思是递减剩下待取的元素
           //算法优化：i<=n-k+node.size()+1
            //优化将循环的次数减少到待取元素的大小
        {
                node.add(i);
                dfs(node,n,k,start+1);
                node.remove(node.size()-1);
        }

    }
}

leetcode 78.子集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        List<Integer>node = new ArrayList<>();
        if(nums.length==0)return list;
        for(int i=0;i<=nums.length;i++)
        dfs(node,nums,i,0);
        return list;
    }
    public void dfs(List<Integer> node,int[]nums,int number,int start)
    {
        if(node.size()==number)
        {
            list.add(new ArrayList<>(node));return;
        }
        for(int i =start;i<nums.length;i++)
        {
            node.add(nums[i]);
                    //这里的i+1避免了元素重复
            dfs(node,nums,number,i+1);
            node.remove(node.size()-1);
        }
    }
}

leetcode 90.子集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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/*
    方法：回溯搜索算法 + 数组排序 + 同层剪枝
    思路：使用回溯算法遍历决策树，穷举所有解，决策树的每个节点维护当前已选路径track/path和选择列表等信息
          相比t078-子集（不包含重复元素），本题可能包含重复元素，若不进行剪枝处理，子集可能出现重复。
          （1）数组排序：对原始数组进行排序，保证重复元素必相邻，方便后续剪枝
          （2）同层剪枝：当决策树由【当前层】向【下一层】递归时，依次向路径中添加1个数组元素；
                        同一层中，若向不同路径添加重复元素（排序后重复元素相邻），该枝干出现重复，需进行剪枝 → 跳过当次循环。
    时间复杂度：
    空间复杂度：
    类似题目：t046-全排列、t077-组合、t078-子集（不包含重复元素）
             【t040-组合总和II】（数组元素可能有重复，每个元素仅能选一次）
    优化点：路径track/path可使用栈Stack，可方便使用压栈push()和出栈操作pop()。
*/

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    //结果集
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        //特判
        if(nums.length == 0) return res;
        //对数组元素进行排序，保证重复元素必相邻，方便后续剪枝
        Arrays.sort(nums);

        //记录已作选择（路径）
        List<Integer> track = new ArrayList<>();
        //调用回溯函数
        backtrack(nums, 0, track);
        return res;
    }

    //回溯函数
    //路径：已作出的选择-track已包含的数组元素
    //选择列表：当前可选择的数组元素（数组nums中start索引及之后的元素）
    //结束条件：正向遍历至数组的末尾时
    private void backtrack(int[] nums, int start, List<Integer> track) {
        //结果集中包含已选路径（部分子集），需对引用track进行拷贝
        res.add(new ArrayList<>(track));

        //遍历数组
        //结束条件：i == nums.length时终止，遍历完全部数组元素
        for(int i = start; i < nums.length; i++){
            //同层剪枝：同一层的两条不同路径中加入的元素出现重复时（数组已排序） → 跳过当次循环
            if(i > start && nums[i] == nums[i - 1]){  // i-1元素的索引必须在start索引及之后位置，即i >= start + 1;
                continue;
            }
            //作出选择
            track.add(nums[i]);
            //递归调用回溯函数 → 进入决策树的下一层（第i + 1个数组元素）
            backtrack(nums, i + 1, track);
            //撤销选择
            track.remove(track.size()-1);
        }
    }
}

发表于 更新于 分类于 ，

KMP算法

主要的关键点在于NEXT数组————最长公共前后缀

寻找前后缀的方法：

  • 找前缀时，要找除了最后一个字符的所有子串
  • 找后缀时，要找除了第一个字符的所有子串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Getnext(int next[],String t)
{
   int j=0,k=-1;
   next[0]=-1;
   while(j<t.length-1)
   {
      if(k == -1 || t[j] == t[k])
      {
         j++;k++;
         next[j] = k;//next[j] = k，表示当T[i] != P[j]时，j指针的下一个位置
      }
      else k = next[k];
   }
}

当P[k] == P[j]时，

有next[j+1] == next[j] + 1

发表于 更新于 分类于

SLAM（同步定位与建图）

SLAM研究体系分类

SLAM研究体系分类

SLAM通常包括如下几个部分，特征提取，数据关联，状态估计，状态更新以及特征更新等。

SLAM的一般过程

SLAM的核心是EKF。EKF用于结合上述信息估计机器人准确位置。上述选取的特征一般称作地标。EKF将持续不断的对上述机器人位置和周围环境中地标位置进行估计。

ekf，扩展卡尔曼滤波简称,太偏向物理方面了

特征提取

  • slam的第一步需要通过测距单元获取机器人周围环境的信息。
    • 具体的方式可以通过激光测距，或者在仿真的时候直接给出
  • 机器人自身运动模型：机器人自身位置数据通过对机器人轮胎运行圈数的估计可以得到机器人自身位置的一个估计，其可以被看作EKF的初始估计数据
    • 需要注意需要保证机器人自身位置数据与测距单元数据的同步性。为了保证其同步性，一般采用插值的方法对数据进行前处理
  • 特征（即是地标）
    • 地标是环境中易于观测和区分的特征
      • 地标应该可以从不同的位置和角度观察得到
      • 地标应该是独一无二的，从而可以很容易的将底边从其他物体中分辨出来

数据关联

是将不同时刻位置传感器提取到的地标信息进行关联的过程，也成为重观察过程。

  • 此处在仿真的时候，可以选择依赖或者不依赖先验知识，直接从图像序列中检测到运动目标，然后进行目标识别

路径规划

所谓机器人的最优路径规划问题就是根据某个或某些优化准则，如工作代价最小，行走路径最短，行走时间最短等准则，在其工作空间中找到一条从起始点到目标点的能避开障碍物的最优路径。

需要解决的问题分为下面三点：

  • 始于初始点止于目标点
  • 避开障碍
  • 尽可能优化路径

常见的路径规划

基于采样的方法、基于节点的方法、基于数学模型的算法、基于生物启发式的算法、和多融合算法。此处重点关注的是基于节点的方法。————可以采用学过的Dijkstra法、A*法

A*法的介绍：也称为栅格法。

  1. 通过下面这个函数来计算每个节点的优先级。
    $$
    f(n)=g(n)+h(n)
    $$
    其中：

    • f(n)是节点n的综合优先级。当我们选择下一个要遍历的节点时，我们总会选取综合优先级最高（值最小）的节点。
    • g(n) 是节点n距离起点的代价。
    • h(n)是节点n距离终点的预计代价，这也就是A*算法的启发函数。关于启发函数我们在下面详细讲解。

  2. A*算法在运算过程中，每次从优先队列中选取f(n)值最小（优先级最高）的节点作为下一个待遍历的节点。

  3. A*算法使用两个集合来表示待遍历的节点，与已经遍历过的节点，这通常称之为open_set和close_set。

  4. ```

    • 初始化open_set和close_set；
    • 将起点加入open_set中，并设置优先级为0（优先级最高）；
    • 如果open_set不为空，则从open_set中选取优先级最高的节点n：
      • 如果节点n为终点，则：
        • 从终点开始逐步追踪parent节点，一直达到起点；
        • 返回找到的结果路径，算法结束；
      • 如果节点n不是终点，则：
        • 将节点n从open_set中删除，并加入close_set中；
        • 遍历节点n所有的邻近节点：
          • 如果邻近节点m在close_set中，则：
            • 跳过，选取下一个邻近节点
          • 如果邻近节点m也不在open_set中，则：
            • 设置节点m的parent为节点n
            • 计算节点m的优先级
            • 将节点m加入open_set中
              1
              2
              3
              4
              5
              6
              7
              8
              9
              10
              11
              12

              5. 启发函数

                 - Dijkstra算法就是启发函数h(n)=0时的A*算法
                 - 如果h(n)始终小于等于节点n到终点的代价，则A*算法保证一定能够找到最短路径。但是当h(n)的值越小，算法将遍历越多的节点，也就导致算法越慢。
                 - 如果h(n)完全等于节点n到终点的代价，则A*算法将找到最佳路径，并且速度很快。
                 - 如果h(n)的值比节点n到终点的代价要大，则A*算法不能保证找到最短路径，不过此时会很快。

                 在一些情况，我们可能未必需要最短路径，而是希望能够尽快找到一个路径即可

                 这里我们的启发函数采用欧几里得距离：两个节点之间的直线距离

              function heuristic(node) =
              dx = abs(node.x - goal.x)
              dy = abs(node.y - goal.y)
              return D * sqrt(dx * dx + dy * dy)
              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

                 

              A\*算法的变种：ARA*、D*、Field D*

              ## A*算法的优化

              ### 估值函数的改进h(n)

              ![](https://i.loli.net/2021/01/21/bne26cT41qAd7fZ.png)

              ### 估值函数中引入惩罚函数

              ## 基于DWA的局部路径规划算法

              当移动机器人遇到动态的障碍物时，需要针对突然出现的物体有自主避障的能力--因此需要局部路径规划

              ### DWA介绍

              [参考文章](https://blog.csdn.net/weixin_37835423/article/details/89683302)

              ————动态窗口法

              其算法过程主要分为仿真获取机器人的运动轨迹、对轨迹进行评价选择最优轨迹两个主要过程，动态窗口表达的是仿真的运动轨迹数量有限，主要是因为机器人在较短的控制周期内只能达到一定的速度。

              #### 获取移动机器人速度样本

              对移动机器人的速度空间（v,w）[v表示的是线速度，w表示的是角速度]进行采用，通过建模对采样的速度进行轨迹预测，通过评价函数对预估的轨迹进行评价

              #### 生成运动轨迹

              根据速度样本确定运动轨迹，是简单运行学知识，主要注意的是用的仿真时间产生的样本还是仿真周期产生的样本。

              #### 针对轨迹进行评价并选取最优轨迹

              oscillation_costs_ //振荡代价函数，一旦速度发生振荡，直接丢弃速度样本
              obstacle_costs_ //障碍物代价函数，当轨迹进入障碍物区，直接丢弃当前轨迹样本
              goal_costs_ //目标代价函数，优先选择距离局部目标点近的轨迹
              path_costs_ //路径代价函数，优先选择贴近全局路径的轨迹

```

  • 通过仿真轨迹将机器人轮廓映射到全局坐标系下，并对轮廓边上的代价值进行分析，选择最大的代价值作为障碍物代价，从而确定机器人是否会撞到障碍物
  • 首先根据全局路径与局部代价地图的边界确定局部目标点，然后依据局部目标点生成栅格地图，每个栅格处的值代表当前栅格到目标点的距离，对于障碍物栅格，直接置为到目标点的距离无穷远。最后再根据轨迹末端点处栅格的位置，直接通过索引在地图中获取该位置距目标点的距离，作为距目标点的代价。因此，目标代价函数的主要任务是生成栅格地图。
  • 该代价函数的实现原理与目标代价函数类似，只是该函数是以局部路径上的所有点作为起点向外膨胀来构建栅格地图，并且是以仿真轨迹上的所有点的距离值的和的平均值作为轨迹的代价值。

RRT算法