数据结构与算法：

算法篇:

大数相加：

两数之和:

image-20220403000437885

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
/**
 * 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 addTwoNumbers(ListNode l1, ListNode l2) {    
    ListNode head = null;
    ListNode tail = null;
    // 设置进位值
    int carry=0;
    // 不用判断下一个结点，判断当前结点是不是空的值
    while(l1!=null||l2!=null){
        // 如果当前结点不为空
        int val1 =  l1 != null ? l1.val : 0 ;
        int val2 = l2 != null ? l2.val : 0;
        // 计算总数
        int sum = val1+ val2 + carry;
        // 需要记录头节点
        if(head ==null){
            // 需要记录首次的结点数
            head = tail = new ListNode(sum%10);
        }
        // 当下一次不为首结点的时候，在进行下一步操作
        else{
            // 进行下一步操作
        tail.next = new ListNode(sum%10);
        // 尾结点往后移
        tail= tail.next;
        }
        // 相加后计算进位
        carry = sum/10;
        // 当前值不是空的值
        if(l1!=null){
            // 下移一位
            l1= l1.next;
        }
        if(l2!=null){
            l2=l2.next;
        }
        // 将下一次的进位创建
    }  
    // 
    if(carry>0){
      tail.next= new ListNode(carry);
  }
return head;
    }
}

需要注意的是结点循环开始是当前结点是不是空，最后，如果当前结点不为空，那么就进行添加到尾结点

image-20220403002451439

回溯：

求子集与求组和不同的是，子集进行横向遍历的时候不需要将之前使用的值参加组合，组合每次横向都是从0开始，然后使用userd记录值是否已经使用过，子集每次从上一次结束偏移一个单位。

image-20220404112417507

子集（元素无重不可复选）

image-20220403003337255

迭代法：

复制上一次的结果集，加入新的元素，并将新增的元素加入到结果集中

image-20220403003425107

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 List<List<Integer>> subsets(int[] nums) {
//    每一次遍历都将上次的数组元素进行复制，添加到新的数组当中

  List<List<Integer>> result = new ArrayList<>();
//   添加空的集合
result.add(new ArrayList<Integer>());
  for(int num : nums){
    List<List<Integer> > newSubsets = new ArrayList<>();
    // 每次都将新的值插入到数组中
    for(List<Integer> subsets: result){
          List<Integer> subset = new ArrayList<>(subsets);
        //   取出结果集中的元素，添加一个数
   subset.add(num);
//     所有的都添加后,加入到结果集中
   newSubsets.add(subset);
    }
    // 传入一个List
    result.addAll(newSubsets);
  }
  return result;
    }
}

回溯方式：

image-20220404103658325

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
class Solution {

    //保存结果集
        List<List<Integer>> res= new LinkedList<>();
        //保存每一层的路径
        LinkedList<Integer> trace= new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) {
            backTrack(nums,0);
     return res;
    }

    public void backTrack(int[] nums,int start){
//    前序遍历，每次结点都是一次子集
      res.add(new LinkedList<>(trace));
        //    进行每一层横向遍历
   for(int i =start;i<nums.length;i++){

       trace.addLast(nums[i]);
     //进入下一层遍历
        backTrack(nums,i+1);
      //移除最后一个元素
        trace.removeLast();
   }
    }
}

全排列问题

image-20220404000020636

递归进行深度遍历，循环进行横向遍历，使用一个链表进行路径保存，一个数组进行元素使用标记，递归结束的条件就是遍历到树的底部时候路径长度是否与给定的长度一致。

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
class Solution {

    List<List<Integer>> res = new LinkedList<>();

    public List<List<Integer>> permute(int[] nums) {
            // 记录路径中的元素
            LinkedList<Integer> track = new LinkedList<>();
            // 记录标记的元素
            boolean used[] = new boolean[nums.length];
            backTrack(nums,track,used);
            return res;
    }
    // 路径：记录在 track 中
// 选择列表：nums 中不存在于 track 的那些元素（used[i] 为 false）
// 结束条件：nums 中的元素全都在 track 中出现
    public void backTrack(int nums[],LinkedList<Integer> track,boolean used[]){
            // 结束条件
            if(track.size()==nums.length){
                res.add(new LinkedList(track));
                return ;
            }
            // 横向对数组进行遍历
            for(int i =0;i<nums.length;i++){
                //判断是否被使用，如果被使用跳出
                if(used[i]){
                    continue;
                }
                track.add(nums[i]);
                //将已经使用的进行标记
                used[i]=true;
                //进入下一层
            backTrack(nums,track,used);
            // 进行回退上一个元素
             track.removeLast();
                used[i]=false;
            }
    }
}
result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

子集Ⅱ

image-20220404005501921

相当于从第一个元素开始

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 {
   List<List<Integer>> res = new LinkedList<>();
   LinkedList<Integer> track = new LinkedList<>(); 
   
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        //   需要记录每一层的元素值
        baskTrack(nums,0);
        return res;
    }

    public void baskTrack(int[] nums,int start){
            // 前序位置，每一个结点都是一个元素
            res.add(new LinkedList<>(track));
            for(int i=start;i<nums.length;i++){
                // 进行剪枝操作,与上一个一个元素相同
                if(i>start&&nums[i]==nums[i-1]){
                    continue;
                }
                track.addLast(nums[i]);
            baskTrack(nums,i+1);
            track.removeLast();
            }
    }
}

组合（元素无重不可复选）：

image-20220404105535051

就是把所有的组合数目求解出来，在添加进数组中我们限制添加进去的条件，判断子集是否是所需要的长度

遍历方式和求解子集的元素是一样的。一个集合记录最后 的元素的值，一个记录当前的路径，在递归中进行横向遍历，进入下一层，去除当前元素，进入递归后，从trace退出一个元素，进行横向遍历。

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
class Solution {
    //当前序遍历的时候，只需要计算添加时候的长度是不是我要的
    List<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer>  track = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        int[] nums = new int[n] ;
        for(int i=0;i<n;i++){
            nums[i]=i+1;
        }
          backTrack(nums,0,k);
          return res;
    }

    public void backTrack(int[] nums,int start,int k){
        //添加限制条件
            if(track.size()==k){
                res.add(new LinkedList<>(track));
                  return;
            }
for(int i=start;i<nums.length;i++){
track.addLast(nums[i]);
backTrack(nums,i+1,k);
track.removeLast();
}
}
}

*全排列 II*

image-20220404144348457

需要进行剪枝操作

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
class Solution {

    List<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> track = new LinkedList<>();
    boolean []used;
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        used = new boolean[nums.length];
        backTrack(nums);
     return  res;

    }

    public void backTrack(int[]nums){
    if(track.size()==nums.length){
        // 添加到结果集元素中
        res.add(new LinkedList<>(track));
        return;
    }
   for(int i=0;i<nums.length;i++){
    //    判断是否是已经参与过排列
       if(used[i]){
        continue;
       }
    //    添加剪枝操作,两个元素必须是相同的，并且在使用数组中已经存在过
   if(i>0&&nums[i]==nums[i-1]&&!used[i-1]){
       continue;
   }
     track.addLast(nums[i]);
     used[i]=true;
     backTrack(nums);
    track.removeLast();
    used[i]=false;
   }
    }
}

排序

动态规划：

*斐波那契数列*

image-20220406070805323

使用递归(超时)：

1
2
3
4
5
6
7
8
9
10
11
12

public int fib(int n) {
         final int MOD = 1000000007;
  if(n==0){
      return 0;
  }
  if(n==1){
      return 1;
  }
     int sum = (fib(n-1)+fib(n-2))%MOD;
  return sum;
}

因为使用递归带有大量的重复计算，所以预先将已经计算好的存储在HashMap中。

image-20220406071908098

带记忆的递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Map<Integer,Integer> map = new HashMap();
public int fib(int n) {
 final int MOD = 1000000007;
  if(n<2){
      return n;
  }

 if(map.containsKey(n)){
    return map.get(n);
  }
  int sum = (fib(n-1)+fib(n-2))%MOD;
  map.put(n,sum);
  return sum;
}

使用动态规划：

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

    public int fib(int n) {
      Integer num = 1000000007;
      if(n<2){
          return n;
      }
      int dp[] = new int[n+1];
      dp[0]=0;
      dp[1]=1;

      for(int i=2;i<=n;i++){
            int sum =dp[i-1]+dp[i-2];
            dp[i] =sum %num;
      }
      return dp[n];
    }
}

优化空间之后的动态规划

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

    public int fib(int n) {
      Integer num = 1000000007;
      if(n<2){
          return n;
      }
      int sum = 0;
     int  a=0;
     int  b=1;
//  2是指的当前数，实际上是数组的第三个数
      for(int i=2;i<=n;i++){
         sum =(a+b)%num;
            a= b;
            b= sum;
 
      }
      return sum;
    }
}

爬楼梯问题

// 倒推思想，我走到第四个台阶，有几种走法，可以从第三走一个，可以从第二走两个，依次往下，可以知道，

f(n)=f(n-1)+f(n-2)

image-20220406191618804

利用hash表存储，计算过的数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    
    Map<Integer,Integer> memo= new HashMap<>(128); 
    final Integer num = 1000000007;
    public int numWays(int n) {
        if(n<=1){
            return 1;
        }
        if(memo.containsKey(n) ){
            return memo.get(n);
        }
        int a = numWays(n-1)%num;
        memo.put(n-1,a);
        int b= numWays(n-2)%num;
        memo.put(n-2,b);
        // 倒推思想，我走到第四个台阶，有几种走法，可以从第三走一个，可以从第二走两个
         int sum =  (a+b)%num;
        memo.put(n-2,sum);
        return  sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int numWays(int n) {
  final  int nums = 1000000007;
   if(n<=1){
       return 1;
   }
   int a =1;
   int b= 1;
  int sum =0;
 for(int i=2;i<=n;i++){
     //每次进行相加时后进行取模
     sum = (a+b)%nums;
    a= b;
    b= sum;

 }
    return  sum;
}

image-20220407213719502

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            ListNode res = new ListNode(0);
            ListNode cur= res;
            res.next=null;
            ListNode temp ;
        //从第一个结点开始，不是下一个不能开始判断l1.next，开头不用判断下一个说名除了移动      l1=l1.next; 其他不能了l1.next 
        //否则会出现空指针，因为没有判断是否为空
         while(l1!=null&&l2!=null){
          if(l1.val<=l2.val){
       
             res.next=l1;
             l1=l1.next;
          }else{
        
              res.next=l2;
              l2=l2.next;
          }
         res=res.next;
         }
        //不用了l1.next 是因为最后已经指向了最后一个
           if(l1==null && l2!=null){
               res.next = l2;
           }

           if(l1!=null && l2==null){
               res.next = l1;
           }
        
        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
//        prev.next = l1 == null ? l2 : l1;


    
return cur.next;
    }
    
}

优先级队列（PriorityQueue）

(40条消息) Java基本数据结构——优先级队列（堆）_1485Lucifer的博客-CSDN博客

(40条消息) 【Java每日一题】Java笔试100题（1）_1485Lucifer的博客-CSDN博客_java每日一题

树的遍历：

589. N 叉树的前序遍历 - 力扣（LeetCode）

image-20220712093731987

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> res = new ArrayList<>();
        helper(root,res);
        return res;
    }
    
    public  void helper(Node root,List<Integer> res){
        if(root ==null){
            return ;
        }
        res.add(root.val);
        for(Node ch:root.children){
            helper(ch,res);
        }
        
    }
}

429. N 叉树的层序遍历 - 力扣（LeetCode）

image-20220712094832438

image-20220712095208803

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
/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
         public List<List<Integer>> levelOrder(Node root) {
        if (root == null) {
            return new ArrayList<List<Integer>>();
        }

        List<List<Integer>> ans = new ArrayList<List<Integer>>();
             //队列先进先出
        Queue<Node> queue = new ArrayDeque<Node>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int cnt = queue.size();
            List<Integer> level = new ArrayList<Integer>();
            for (int i = 0; i < cnt; ++i) {
               //移除一个元素并返回头节点
                Node cur = queue.poll();
                level.add(cur.val);
                for (Node child : cur.children) {
                    //插入元素获取下一层的子节点
                    queue.offer(child);
                }
            }
            ans.add(level);
        }

        return ans;
    }

}

双指针：

双指针技巧秒杀七道数组题目 :: labuladong 的算法小抄

26. 删除有序数组中的重复项 - 力扣（LeetCode）

可以使用双指针：右指针 right 指向当前将要处理的元素，左指针 left 指向下一个将要赋值的位置

image-20220921085138426

image-20220921085149190

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

//    慢指针 slow 走在后面，快指针 fast 走在前面探路，找到一个不重复的元素就赋值给 //slow让 slow 前进一步。

public int removeDuplicates(int[] nums) {
    //每次记录的都是最后遍历的元素
    int slow = 0;
    
    int fast = 0;
    while (fast < nums.length) {
        if (nums[slow]!=nums[fast]) {
            //++是为了要交换元素
            slow++;
            nums[slow] = nums[fast];
        }
        fast++;
    }
    
    return slow + 1;
}

img

83. 删除排序链表中的重复元素 - 力扣（LeetCode）

image-20220921092030510

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

/**
 * 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 deleteDuplicates(ListNode head) {
//      记得加上头节点为空的情况
        if(head==null){
            return null;
        }
        ListNode slow = head;
 
        ListNode fast = head;
//        循环终止的条件是头指针遍历到末尾
        while(fast!=null){
//             如果出现两个不相同的元素，说明是不同的元素，交换
            if(slow.val!=fast.val){

//     先将不同的结点添加到后面，相当于重构链表
                slow.next = fast;
                slow=slow.next;
            }
            
                fast=fast.next;            
        }
        
    // 记得最后面要将重复的去掉
        slow.next=null;
        return head;
        
    }
}

img

27. 移除元素 - 力扣（LeetCode）

image-20220921095138592

关于 slow++ 时机：

如果使用 slow 先 ++，那么当第一个元素是所需要的元素是，会筛选不掉

错误代码

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 removeElement(int[] nums, int val) {
//   进行交换的条件就是
        int slow =0;
        int fast =0;
        while(fast<nums.length){
//      遍历到相同的元素就跳过   
        if(nums[fast]!=val){
//             先进行复制，再加加
             slow++;
           nums[slow]=nums[fast];
           
            
        }    
            fast++;
        }
        return slow+1;
        
        
    }
}

image-20220921094831953

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 removeElement(int[] nums, int val) {
//   进行交换的条件就是
        int slow =0;
        int fast =0;
        while(fast<nums.length){
//      遍历到相同的元素就跳过   
        if(nums[fast]!=val){
//             先进行复制，再加加
             
           nums[slow]=nums[fast];
           
            slow++;
        }    
            fast++;
        }
        return slow;
        
        
    }
}

二分查找:

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

class Solution {
    public int search(int[] nums, int target) {
    int left =0;
    int right = nums.length-1;

     while(left<=right){
//       防止整型溢出
   int   mid =left+(right-left)/2;
         if(nums[mid]<target){
             left = mid+1;
         }else if(nums[mid]>target){
             right = mid -1;
         }else{
        return  mid;      
         }
         
     }
  return -1;
    }
}

前者相当于两端都闭区间 [left, right]，后者相当于左闭右开区间 [left, right)，因为索引大小为 nums.length 是越界的。
那什么时候应该停止，？就是搜索为空的时候，

while (left <= right) 的终止条件是 left == right + 1，写成区间的形式就是 [right + 1, right]，或者带个具体的数字进去 [3, 2]，可见这时候区间为空，因为没有数字既大于等于 3 又小于等于 2 的吧。所以这时候 while 循环终止是正确的，直接返回 -1 即可。

while (left < right) 的终止条件是 left == right，写成区间的形式就是 [right, right]，或者带个具体的数字进去 [2, 2]，这时候区间非空，还有一个数 2，但此时 while 循环终止了。也就是说这区间 [2, 2] 被漏掉了，索引 2 没有被搜索，如果这时候直接返回 -1 就是错误的。

day06 - 二分查找 - 力扣（LeetCode）

在排序数组中查找数字 I

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

统计一个数字在排序数组中出现的次数。
JAVA
class Solution {

    public int search(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        int firstPosition = left_bound(nums, target);
        if (firstPosition == -1) {
            return 0;
        }
//        找到数组的最后一个元素
        int lastPosition = right_bound(nums, target);
        return lastPosition - firstPosition +1;
    }
    int left_bound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                // 别返回，锁定左侧边界
                right = mid - 1;
            }
        }
        // 判断 target 是否存在于 nums 中
        // 此时 target 比所有数都大，返回 -1
        if (left == nums.length) return -1;
        // 判断一下 nums[left] 是不是 target
        return nums[left] == target ? left : -1;
    }

    int right_bound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                // 别返回，锁定右侧边界
                left = mid + 1;
            }
        }
        // 此时 left - 1 索引越界
        if (left - 1 < 0) return -1;
        // 判断一下 nums[left] 是不是 target
        return nums[left - 1] == target ? (left - 1) : -1;
    }



}

我写了首诗，让你闭着眼睛也能写对二分搜索 :: labuladong 的算法小抄