算法思路汇总

发表于 更新于 分类于 阅读次数：

数组相关（双指针，对撞指针）

2 sum

注意的地方在于边放入元素，边进行元素是否在map中的判断。

1
2
3
4
5
6
7
8
9
10
for (int i = 0; i < nums.length; i++) {
    // 判断是否有匹配的
    Integer j = numIndexMap.get(target - nums[i]);
    if (j != null) {
        return new int[]{i, j};
    }
    // 添加到 numIndexMap 中
    numIndexMap.put(nums[i], i);

}

2 sum 改进版

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

使用对撞指针思想，当和大于预定值，右指针向左移动，同理，左指针向右移动。

1
2
3
4
5
6
7
8
9
10
11
12
int left = 0, right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{left + 1, right + 1};
            }
            if (sum > target) {
                right--;
            } else {
                left++；
            }
        }

设计getMin操作的栈

push()方法：

在压入操作时，判断stackMin是否为空，空则压入，如果不为空，与getMin()方法得到的值进行比较，小则压入。

stackData()一直压入。

getMin()方法

stackMin()不为空，则直接返回peek()。

pop()方法

stackData栈Pop出一个值，和stackMin的peek()值比较，等于则一起弹出，不等于则返回stackData栈Pop出的值。

两个栈组成的队列

关键在于一个栈作为压入栈，记为stack1，一个栈作为弹出栈，记为stack2，每次需要先判断stack2是否为空，只有当stack2为空时，才能将stack1中的所有元素压入stack2中。

1
2
3
4
5
if(stack2.isEmpty()){
    while(!stack1.isEmpty()){
        stack2.push(stack1.pop());
    }
}

递归操作逆序一个栈

先将栈stack的栈底元素返回并移除,然后依次再压入

在将栈的栈底元素返回并移除时，其中return result,最终的出栈元素被返回，没能被压入栈，此时的return更像是递归到底之后再向上回溯的过程。

1
2
3
4
5
6
7
if(stack.isEmpty()){
    return result;
}else{
    int last=递归调用;
    stack.push(result);
    return last;
}

一个栈实现实现另一个栈的逆序

其中如果是按照从顶到底的顺序是从大到小的顺序，可以先申请一个辅助栈，栈底是最大的元素，如果要放入的元素比辅助栈栈顶的元素大，就把辅助栈元素依次弹出，直到放入的元素此时小于栈顶元素，将元素压入。

最后再将元素从辅助栈中弹出，再压入到原来的栈。

生成窗口最大值数组

使用双端队列，遍历数组元素，如果队列不为空，且队列的末尾元素小于当前数组的值，则依次弹出队列的末尾元素，直至末尾元素大于数组值。记录数组元素的索引值，当队列头部的值==数组当前索引 - 窗口当前大小时，将队列头部的值弹出。

当数组当前索引 >= 窗口当前大小-1时，则将这些窗口最大值记录下来，即当前队列的头部元素的值。

单调栈

什么是单调栈？

单调栈分为单调递增栈和单调递减栈，单调递增栈即栈内元素保持单调递增的栈，同理单调递减栈即栈内元素保持单调递减的栈，跟单调队列差不多，但是只用到它的一端。

单调递增栈

1
2
3
4
5
6
for(int i = 0; i < T.size(); i++){
  while(! stk.empty() && stk.top() > T[i]){
    stk.pop();
  }
  stk.push(A[i]);
}

单调递减栈

1
2
3
4
5
6
for(int i = T.size() - 1; i >= 0; i--){
  while(! stk.empty() && T[i] >= stk.top()){
    stk.pop();
  }         
  stk.push(i);
}

单调栈的作用：

可以以 O(1) 的时间复杂度得知某个位置左右两侧比他大（或小）的数的位置，当你需要高效率获取某个位置左右两侧比他大（或小）的数的位置的的时候就可以用到单调栈。

求解数组中元素右边第一个比它小的元素的下标，从前往后，构造单调递增栈；

求解数组中元素右边第一个比它大的元素的下标，从前往后，构造单调递减栈；

求解数组中元素左边第一个比它小的元素的下标，从后往前，构造单调递减栈；

求解数组中元素左边第一个比它小的元素的下标，从后往前，构造单调递增栈。

打印两个有序链表的公共部分

注意在判断两个链表的值相同时，要继续遍历链表

1
2
3
4
if(node1.val==node2.val){
    node1=node1.next;
    node2=node2.next;
}

单链表和双链表删除倒数第K个节点

单链表删除

  • 快慢指针法 可以先让fast指针先走k步，再让fast和slow一起继续遍历，直至fast为空。需要设立虚拟头结点dummyhead

  • 先从头结点开始遍历链表，其中K值保持 K– ，遍历到链表尾部。若K小于0，再进行++K，当K等于0时，移动到的节点是待删除节点的前一个节点。若K=0,则直接返回头结点的下一个节点。

    1
    2
    3
    4
    5
    6
    7
    if(K<0){
        ListNode cyr=head;
        while(++K!=0){
            cur=cur.next;
        }
        cur.next=cur.next.next;
    }

双链表删除

和单链表删除过程基本一致，只是除了next指针外，还要先保存pre指针。

1
2
3
4
5
6
7
8
9
10
11
if(K<0){
    ListNode cyr=head;
    while(++K!=0){
        cur=cur.next;
    }
    ListNode pre=cur.next.next;
    cur.next=pre;
    if(pre!=null){
        pre.next=cur;
    }
}

前序、中序、后序遍历

在使用递归方式处理二叉树时，每个节点都会被访问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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List inorderTraversal(TreeNode root) {
        ArrayList list=new ArrayList<>();
        if(root!=null){
            Stack stack = new Stack<>();
            while(!stack.isEmpty() || root!=null){
                if(root!=null){
                    stack.push(root);
                    root=root.left;
                }else{
                    root=stack.pop();
                    list.add(root.val);
                    root=root.right;
                }
            }
        }
        return list;      
    }
}

如果都不为空，若根节点不为空，则将它的左子树的全部节点压入栈，若左子树到了底，则开始弹出节点并打印值，继续遍历右子树的节点。

递归

93 复原IP地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// cur : 当前答案，以 String List的形式，最后再join成String形式 例如 [[255],[255],[111],[35]] -> 255.255.111.35
    // pos, 当前扫描到的s的位置， ans最终答案
    private void backtracking(String s, int pos, List cur,  List ans) {
        if (cur.size() >= 4) {
            if (pos == s.length()) ans.add(String.join(".", cur));
            return;
        }
        // 分割得到ip地址的一段后，下一段只能在长度1-3范围内选择
        for (int i = 1; i <= 3; i++) {
            if (pos+i > s.length()) break;
            String segment = s.substring(pos, pos+i);
            // 剪枝条件：不能以0开头，不能大于255
            if (segment.startsWith("0") && segment.length() > 1 || (i == 3 && Integer.parseInt(segment) > 255)) continue;
            cur.add(segment);
            // 注意此处传的参数
            backtracking(s, pos+i, cur, ans);
            cur.remove(cur.size()-1);
        }
    }
    public List restoreIpAddresses(String s) {
        List ans = new ArrayList<>();
        backtracking(s, 0, new ArrayList<>(), ans);
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public List letterCombinations(String digits) {
       if(digits.length()!=0){
       dfs("", digits);
       }
       return result;
   }

   private void dfs(String combination, String digits) {
       if (digits.length() == 0) {
           result.add(combination);
       } else {
           String digit = digits.substring(0, 1);
           for (int i = 0; i < map1.get(digit).length(); i++) {
               String letter = map1.get(digit).substring(i, i + 1);
               dfs(combination + letter, digits.substring(1));
           }
       }
   }
0%