算法笔记

发表于 | 分类于 | 评论数：
    字数统计: 6.7k(字) | 阅读次数：

笔记

1.链表和数组

数组

没啥可说的

链表

没啥可说的

练习

[1.翻转链表](https://leetcode.com/problems/reverse-linked-list)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}
public static ListNode reverseList(ListNode head) {
        ListNode p = null;
        ListNode next = null;
        while (head != null) {
            next = head.next;
            head.next = p;
            p = head;
            head = next;
        }
        return p;
   }
两个指针，`head`指向链表现在所处的位置，`p`代表翻转链表。

[2.链表两两节点反转](https://leetcode.com/problems/swap-nodes-in-pairs)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static ListNode swapPairs(ListNode head) {
        ListNode cur = new ListNode(-1);
        cur.next = head;
        ListNode p = cur;
        while (cur.next != null && cur.next.next != null) {
            ListNode a = cur.next;
            ListNode b = cur.next.next;
            cur.next = b;
            //下列两个等式不能反过来，否则链表会自身循环
            a.next = b.next;
            b.next = a;
            //不能用cur.next = a.next否则会改变原链表
            cur = a;
        }
        return p.next;
    }
这个想了好久好久，最后总结出如果首元节点改变的话，基本都要添加头指针，否则由于首元节点的改变，最后无法回到新的首元节点，我们需要三个指针分别存储cur.next，cur.next.next，以及cur（cur负责对链表进行遍历并进行相应操作）。为了防止链表的自身循环，一定要注意指令的执行顺序。思路很简单：就是在遍历的时候将指针进行翻转，之后cur.next指针后移两位。但是最后一步不能使用cur.next = a.next 或者 cur.next = b.next，因为使用了->next会使原本头指针发生指向错误（会牵制到p）。但是所幸leetcode结果还是不错：

[3.判断链表是否有环](https://leetcode.com/problems/linked-list-cycle)

  • 在leetcode时间允许范围内遍历链表，如果有Null节点，返回true，否则返回false（不推荐）

  • 运用set，判断set中是否存在对应节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    public static boolean hasCycle(ListNode head) {
            Set<ListNode> nodes = new HashSet<>();
            while (head != null) {
                if (nodes.contains(head))
                    return true;
                else {
                    nodes.add(head);
                    head = head.next;
                }
            }
            return false;
        }

  • 快慢指针法，若有环，迟早相遇

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    public static boolean hasCycle(ListNode head) {
            ListNode fast = head;
            ListNode slow = head;
            while (slow != null && fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
                if (slow == fast)
                    return true;
            }
            return false;
        }

    4.判断链表是否有环ii

  • 运用set，返回相应节点
1
2
3
4
5
6
7
8
9
10
11
12
public ListNode detectCycle(ListNode head) {
        Set<ListNode> nodes = new HashSet<>();
        while (head != null) {
            if (nodes.contains(head))
                return head;
            else {
                nodes.add(head);
                head = head.next;
            }
        }
        return null;
    }

  • 运用快慢指针，但是需要注意一点，两者相遇并不能确保是第一个开始循环的节点，网上的解法很巧妙，但是运用到了数学证明，所以…emmm。

    5.翻转链表ii

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static ListNode reverseKGroup(ListNode head, int k) {
        int n = 0;
        ListNode cur = head;
        while(cur != null){
            cur = cur.next;
            n++;
        }
        ListNode dmy = new ListNode(0);
        dmy.next = head;
        ListNode s = dmy, e = dmy.next; //s: start, e: end
        for(int i = n; i >= k; i -= k){
            for(int j = 1; j < k; j++){ // reverse group
                ListNode next = e.next;
                e.next = next.next;
                next.next = s.next;
                s.next = next;
            }
            s = e;
            e = s.next;
        }
        return dmy.next;
    }
自己没想出来，看得别人的提交，这个比较好理解，双重循环，里面的循环解决一组翻转，两个指针分别代表翻转开始时的头结点和准备翻转的节点。

2.堆栈和队列

堆栈

队列

优先队列（PriorityQueue）

  • 正常入、按照优先级出

  • 实现机制：

    1.heap（Binary（大根堆，小根堆），Binomial，Fibonacci）

    2.Binary Search Tree（二叉搜索树）

练习

1.判断字符串是否合法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static boolean isValid(String s) {
    	Map<Character, Character> mappings = new HashMap<>();
    	mappings.put('(', ')');
        mappings.put('[', ']');
        mappings.put('{', '}');
        Stack<Character> stack = new Stack<Character>();
        for (char c : s.toCharArray()) {
            if (mappings.containsKey(c)) {
                stack.push(mappings.get(c));
            } else if (mappings.containsValue(c)) {
                if (stack.empty() || stack.pop() != c) {
                    return false;
                }
            }
        }
        if (stack.empty()) {
            return true;
        }
        return false;
    }
这是之前做过的一道leetcode的题目，这个是别人的解法，代码很巧妙。运用了栈的思想，先将左括号压入栈，如果碰见右括号，如果该字符串有效的话，应该可以正好匹配栈顶的左括号，否则就无效，当扫描完字符串，栈不为空时，字符串也无效。我想起了这道题的一个变体，给你括号的对数，能输出几种有效的组合呢？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//char str = new char[2 * count]
public static void Out(int l,int r,char[] str,int count) {
		if(l < 0 || r < l)
			return;
		if(r == 0&&l == 0) {
			//num++;
			System.out.println(str);}
		else {
			if(l > 0) {
				str[count] = '(';
				Out(l -1 ,r,str,count+1);
			}
			if(r > l) {
				str[count] = ')';
				Out(l,r-1,str,count+1);
			}
		}
}

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
class MyQueue {
    private Stack<Integer> s1 = new Stack<>();
    private Stack<Integer> s2 = new Stack<>();
    private int front;
    /** Initialize your data structure here. */
    public MyQueue() {
       
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
         if (s1.empty())
        front = x;
        s1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if (s2.isEmpty()) {
        while (!s1.isEmpty())
            s2.push(s1.pop());
    }
    return s2.pop(); 
    }
    
    /** Get the front element. */
    public int peek() {
        if (!s2.isEmpty()) {
            return s2.peek();
        }
        return front;
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}

3.实时判断数据流最大元素

小根堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//优先队列
class KthLargest{
private int k;
    private PriorityQueue<Integer> q;
    public KthLargest(int k, int[] nums) {
        this.k = k;
        q = new PriorityQueue<>(k);
        for (int n: nums) {
            add(n);
        }
    }

    public int add(int val) {
        if (q.size() < k)
            q.offer(val);
        else if (q.peek() < val) {
            q.poll();
            q.offer(val);
        }
        return q.peek();
    }
}

java中PriorityQueue底层数据结构是平衡二叉堆，jdk1.8源码中对该数据结构的介绍：

1
2
3
4
5
6
7
8
/**
    * Priority queue represented as a balanced binary heap: the two
    * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
    * priority queue is ordered by comparator, or by the elements'
    * natural ordering, if comparator is null: For each node n in the
    * heap and each descendant d of n, n <= d.  The element with the
    * lowest value is in queue[0], assuming the queue is nonempty.
    */
大意就是说该堆的实现是由comparator决定的（大根堆、小根堆），如果没有实现该默认的方法则默认为小根堆。

4.返回滑动窗口最大值

解法1：利用大根堆（优先队列）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int[] maxSlidingWindow(int[] nums, int k) {
    	//linkedlist实现了Deque的接口
        List<Integer> res = new ArrayList<>();
        Queue<Integer> p = new PriorityQueue<>(Comparator.reverseOrder());
        for (int i = 0; i < nums.length; i++) {
            if (p.size() < k - 1) {
                p.add(nums[i]);
            } else {
                p.add(nums[i]);
                res.add(p.peek());
                p.remove(nums[i - k + 1]);
            }
        }
    	//lambda表达式
        int[] end = res.stream().mapToInt(Integer::valueOf).toArray();
        return end;
    }

解法2：利用双端队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int[] maxSlidingWindowii(int[] nums, int k) {
        LinkedList<Integer> window = new LinkedList<>();
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i ++) {
            if (i >= k && window.getFirst() <= i - k) {
                window.removeFirst();
            }
            while (window.size() > 0 && nums[i] >= nums[window.getLast()]) {
                window.removeLast();
            }
            window.add(i);
            if (i >= k - 1) {
                res.add(nums[window.getFirst()]);
            }
        }
        int[] end = res.stream().mapToInt(Integer::valueOf).toArray();
        return end;
    }
window记录下标，res记录结果。如果window记录数值的话，不好解决当窗口内元素为k时，窗口向前滑动的情况。

3.映射（Map）和集合（Set）

映射

key: value 形式

HashMap vs TreeMap （哈希表对二叉搜索树）

查询 O(1)      O(log<sub>2</sub>n)

无序              有序

集合

HashSet vs TreeSet     （哈希表对二叉搜索树）

查询 O(1)      O(log<sub>2</sub>n)

无序              有序

练习

1.有效字母异位词

排序

1
2
3
4
5
6
7
public static boolean isAnagram(String s, String t) {
       char[] ss = s.toCharArray();
       Arrays.sort(ss);
       char[] tt = t.toCharArray();
       Arrays.sort(tt);
       return Arrays.toString(tt).equals(Arrays.toString(ss));
   }

Map:计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static boolean isAnagramii(String s, String t) {
        HashMap ss = new HashMap<Character,Integer>();
        for (char c : s.toCharArray()) {
            if (ss.containsKey(c)) {
                Integer tmp = (int)ss.get(c) + 1;
                ss.put(c,tmp);
            } else {
                ss.put(c,1);
            }
        }
        HashMap tt = new HashMap<Character,Integer>();
        for (char c : t.toCharArray()) {
            if (tt.containsKey(c)) {
                Integer tmp = (int) tt.get(c) + 1;
                tt.put(c, tmp);
            } else {
                tt.put(c, 1);
            }
        }
        return tt.equals(ss);
    }

改善做法（map计数）

1
2
3
4
5
6
7
8
9
10
11
12
13
if (s.length() == 0 && t.length() == 0) return true;
        if (s.length() != t.length()) return false;
        int[] sMap = new int[26];
        for (char ch: s.toCharArray()) sMap[ch - 'a']++;
        for (char ch: t.toCharArray()) {
            if (sMap[ch - 'a'] > 0) {
                sMap[ch - 'a']--;
            } else return false;
        }
        for (int i = 0; i < 26; i++) {
            if (sMap[i] != 0) return false;
        }
        return true;
通过数组下标记录个数

2.两数之和

1
2
3
4
5
6
7
8
9
10
11
12
public static int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> flag = new HashMap();
        for (int i = 0; i < nums.length; i++) {
            int tmp = target - nums[i];
            if (flag.containsKey(tmp))
                return new int[]{flag.get(tmp), i};
            else {
                flag.put(nums[i], i);
            }
        }
        return null;
    }

使用Hashmap记录下标

3.三数之和

使用双重循环，将需要的数字放入set中，如果在遍历过程中发现这个数字就加入到结果集中

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
public static List<List<Integer>> threeSum(int[] nums) {
        //使用set为了防止全是0的情况
        Set<List<Integer>> res = new HashSet<>();
        //排序是为了防止出现重复情况
        Arrays.sort(nums);
        for (int i = 0;i < nums.length - 2;i ++) {
            //防止重复
            if (i >= 1 && nums[i] == nums[i - 1])
                continue;
            //防止重复，后面大于0的话没必要在进行下去了
            if (nums[i] >= 0 && nums[i + 1] > 0)
                break;
            //每一次外层循环要新建一个结果集
            Set<Integer> s = new HashSet<>();
            for (int j = i + 1;j < nums.length; j ++) {
                List<Integer> temp = new ArrayList<>();
                if (!s.contains(nums[j])) {
                    s.add(-(nums[i] + nums[j]));
                } else {
                    temp.add(nums[i]);
                    temp.add(nums[j]);
                    temp.add(-(nums[i] + nums[j]));
                    res.add(temp);
                }
            }
        }
        List<List<Integer>> end  = new ArrayList<>(res);
        return end;
    }

指针法 排序、遍历，如果三个数相加<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
public static List<List<Integer>> threeSumii(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i ++) {
            if (i >= 1 && nums[i] == nums[i-1])
                continue;
            int l = i + 1;
            int r = nums.length - 1;
            while(l < r){
                int sum = nums[i] + nums[r] + nums[l];
                if (sum < 0) l++;
                else if (sum > 0) r--;
                else {
                    List<Integer> temp = new ArrayList<>();
                    temp.add(nums[i]); temp.add(nums[l]); temp.add(nums[r]);
                    res.add(temp);
                    while (l < r && nums[l] == nums[l + 1])
                        l++;
                    while (l < r && nums[r] == nums[r - 1])
                        r--;
                    l++; r--;
                }
            }
        }
        return res;
    }

4.四数之和

反人类，不搞了

4.树和图

树

*二叉搜索树*

*二叉树遍历*：
  • pre-order：根左右
  • in-order：左根右
  • post-order：左右根

图

练习

1.验证是否是二叉搜索树

中序遍历（递增）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public  boolean isValidBST(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        order(root, list);
        for (int i = 0; i < list.size() - 1; i ++) {
            if (list.get(i) >= list.get(i+1))
                return false;
        }
        return true;
    }
    public void order (TreeNode root, ArrayList<Integer> res) {
        if (root != null){
            order(root.left, res);
            res.add(root.val);
            order(root.right, res);
        }
    }

递归判断 最大值最小值 牛皮

1
2
3
4
5
6
7
public  boolean isValid(TreeNode root, Integer min, Integer max) {
        if (root == null)
            return true;
        if (min != null && root.val <= min) return false;
        if (max != null && root.val >= max) return false;
        return isValid(root.left, min, root.val) && isValid(root.right,root.val, max);
    }

2.最近公共祖先

1
2
3
4
5
6
7
8
9
10
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
        int max = Math.max(p.val, q.val);
        int min = Math.min(p.val,q.val);
        if (min > root.val) {
            return lowestCommonAncestor(root.right,  p,  q);
        } else if (max < root.val) {
            return lowestCommonAncestor(root.left,  p,  q);
        } else {
            return root;}
}

这玩意思路很简单，但是做了好久，因为我忘写递归的return了，怎么写都错，我佛了

变体 

1
2
3
4
5
6
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        return left == null ? right : right == null ?  left : root;
    }

查看左子树和右子树，将结点保存到left、right结点

5.递归和分治

递归（Recrusion）

  • 终止条件
  • 递归体（业务逻辑、调用递归函数、做一些收尾工作（不必须））

分治（Divide&Conquer）

  • 一般不适用于有中间结果、或者重复计算

  • 一般使用递归

  • 步骤：

    1.终止条件

    2.拆分问题（准备数据）

    3.处理数据

    4.合并子结果

练习

1.求方

时间复杂度为o(n)的做法，由于我用的递归，但是会造成stackflowerror，就是说递归函数会占用太多的栈内存空间，所以递归太深就会报错。

改进版，时间复杂度为(logn)，从中对折。

1
2
3
4
5
6
7
8
9
10
11
12
public double myPow(double x, int n) {
    if(n == 0) return 1;
    if(n == Integer.MIN_VALUE){
        n = n/2;
    }
    if(n < 0) {
        n = -n;
        x = 1/x;
    }

    return (n%2 == 0) ? myPow(x * x, n/2) : x *  myPow(x * x, n/2);
}

使用mypow(x * x, n/ 2) 而不是mypow(x, n/2) * mypow(x, n/2)的原因是写法简单，因为nk * nk = n2的k次幂。为什么要判断Integer.MIN_VALUE，因为图片：

改进的非递归版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public double myPow(double x, int n) {
        if(n == Integer.MIN_VALUE){
            n = n/2;
        }
        if (n < 0) {
            x = 1 / x;
            n = -n;
        }
        double pow = 1;
        while (n > 0) {
            if ((n & 1) == 1){
                pow = pow * x;
            }
            x = x * x;
            n >>= 1;
        }
        return pow;
    }

用的位运算，实质上还是for循环，这样性能应该会好一些。还是运算了n次

2.求众数

暴力 O(n2)

map O(n)

排序 O(nlogn)

分治

1
2
3
4
public int majorityElement(int[] nums) {
      Arrays.sort(nums);
      return nums[nums.length/2];
  }

6.贪心算法

  • 在问题求解时，做出当前最优选择
  • 适用场景：问题可以分成子问题，而且子问题的最优解可以变成全局最优解。

练习

1.买卖股票最佳时机

贪心

1
2
3
4
5
6
7
8
public int maxProfit(int[] prices) {
        int profit = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            if (prices[i] < prices[i + 1])
                profit += (prices[i+1] - prices[i]);
        }
        return profit;
    }

动态规划

7.广度优先、深度优先遍历

广度优先：

深度优先：

思维类似于栈

练习

1.二叉树的层次遍历

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public List<List<Integer>> levelOrder(TreeNode root) {
      
        List<List<Integer>> res = new ArrayList<>();
        if (root == null)
            return res;
        //队列
        if (root == null)
            return new ArrayList<>();
        LinkedList<TreeNode> tmp = new LinkedList<>();
        //HashSet<TreeNode> visted = new HashSet<>();
        tmp.add(root);
        while (!tmp.isEmpty()){
            ArrayList<Integer> l = new ArrayList<>();
            int length = tmp.size();
            for (int i = 0; i < length; i++){
                TreeNode tn = tmp.removeFirst();
                l.add(tn.val);
                if (tn.left != null) tmp.add(tn.left);
                if (tn.right != null) tmp.add(tn.right);
            }
            res.add(l);
        }
        return res;
    }

通过使用for循环，将每一个层次的树节点输出

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public  List<List<Integer>> levelOrder(TreeNode root) {
       List<List<Integer>> res = new ArrayList<>();
       if (root == null)
           return res;
       DFS(res, root, 0);
       return res;
   }
   public void DFS(List<List<Integer>> res, TreeNode root, int level) {
       if (root == null)
           return;
       if (res.size() <= level)
           res.add(new ArrayList<>());
       res.get(level).add(root.val);
       DFS(res, root.left, level + 1);
       DFS(res, root.right,level + 1);
   }

注意存入每个节点应该属于的层次，通过深度遍历将值放入所属于的层次中。

2.二叉树的最大高度

DFS

1
2
3
4
5
6
7
8
9
public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);

        return Math.max(left, right) + 1;
    }

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int maxDepthii(TreeNode root) {
        int level = 0;
        if (root == null)
            return level;
        LinkedList<TreeNode> tmp = new LinkedList<>();
        tmp.add(root);
        while (!tmp.isEmpty()) {
            int length = tmp.size();
            level++;
            for (int i = 0; i < length; i++) {
                TreeNode tn = tmp.removeFirst();
                if (tn.right != null) tmp.add(tn.right);
                if (tn.left != null) tmp.add(tn.left);
            }
        }
        return level;
    }

3.二叉树的最小高度

DFS

1
2
3
4
5
6
7
public int minDepth(TreeNode root) {
        if (root == null)
            return 0;
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        return (left == 0 || right == 0)? left + right + 1 :Math.min(left,right) + 1;
    }

这个处理的很巧妙，我的方法就有点low了

1
2
3
4
5
6
7
public static int DFSii(TreeNode root, int level) {
        if (root == null)
            return Integer.MAX_VALUE;
        if (root.left == null && root.right == null)
            return level+1;
        return Math.min(DFSii(root.left, level + 1), DFSii(root.right, level + 1));
    }

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int minDepthii(TreeNode root) {
       int level = 0;
       if (root == null)
           return level;
       LinkedList<TreeNode> tmp = new LinkedList<>();
       tmp.add(root);
       while (!tmp.isEmpty()) {
           int length = tmp.size();
           level++;
           for (int i = 0; i < length; i++) {
               TreeNode tn = tmp.removeFirst();
               if (tn.right == null && tn.left == null)
                   return level;
               if (tn.right != null) tmp.add(tn.right);
               if (tn.left != null) tmp.add(tn.left);
           }
       }
       return level;
   }

4.生成括号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List generateParenthesis(int n) {
        ArrayList<String> res = new ArrayList<>();
        gen(0,0, n, res, "");
        return res;
    }
    public void gen(int left, int right, int max, ArrayList<String> res, String s) {
        if (left == max && right == max){
            res.add(s);
        return;}
        if (left < max)
            gen(left + 1, right, max, res, s + "(");
        if (right < left && right < max)
            gen(left, right + 1, max, res, s + ")");

    }

也可通过递归生成所有可能性，然后依次判断，麻烦！

8.剪枝

搜索的常用手段 ，把差的分支去掉(alpha go)

练习

1.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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public List<List<String>> solveNQueens(int n) {
      List<List<Integer>> res = new ArrayList<>();
    Set<Integer> cols = new HashSet<>();
    Set<Integer> pia = new HashSet<>();
    Set<Integer> na = new HashSet<>();
    List<Integer> cur_state = new ArrayList<>();
    DFS(n, 0, cur_state, res, cols, pia, na);
    List<List<String>> end = new ArrayList<>();
    StringBuffer ss = new StringBuffer();
    for (int k = 0; k < n; k++){
      ss.append(".");
    }
    for (int i = 0; i < res.size();i ++) {
      List<String> tmp = new ArrayList<>();
      for (int j = 0; j < res.get(i).size(); j ++) {
        StringBuffer kk = new StringBuffer(ss);
        kk.replace(res.get(i).get(j),res.get(i).get(j) + 1, "Q");
        tmp.add(kk.toString());
      }
      end.add(tmp);
    }
    return end;
    }
    public void DFS(int n, int row, List<Integer> cur_state, List<List<Integer>> res, Set<Integer> cols, Set<Integer> pie, Set<Integer> na) {
    if (row >= n) {
      if (cur_state.size() == n) {
        List<Integer> p = new ArrayList<>();
        p.addAll(cur_state);
        System.out.println(cur_state);
        res.add(p);
      }
      return;
    }
    for (int i = 0; i < n; i++) {
      if (cols.contains(i) || pie.contains(i + row) || na.contains(i - row)) {
        // 不符合条件的
        continue;
      }
      cols.add(i);
      pie.add(row + i);
      na.add(i - row);
      cur_state.add(i);
      DFS(n, row + 1, cur_state, res, cols, pie, na);
      cur_state.remove(cur_state.size() - 1);
      cols.remove(i);
      pie.remove(row + i);
      na.remove(i - row);
    }
  }

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
public boolean isValidSudoku(char[][] board) {
        boolean flag = true;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                flag = isValid(board,i,j,board[i][j]);
                if (flag == false) return false;
            }
        }
        return true;
    }
  public boolean isValid(char[][] board, int row, int col, char c) {
    for (int i = 0; i < board.length; i++) {
      if (board[i][col] != '.' && board[i][col] == c && row != i) return false;
      if (board[row][i] != '.' && board[row][i] == c && col != i) return false;
    }
    int m = (row / 3) * 3;
    int n = (col / 3) * 3;
    for (int k = 0; k < 3; k++) {
      for (int j = 0; j < 3; j++) {
        if (board[m + k][n + j] != '.' && board[m + k][n + j] == c && (m + k) != row && (n+j) !=col)
          return false;
      }
    }
    return true;
  }

2.数独问题ii

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
public void solveSudoku(char[][] board) {
        solve(board);
    }
    public boolean solve(char[][] board) {
    for (int i = 0; i < board.length; i++) {
      for (int j = 0; j < board.length; j++) {
        if (board[i][j] == '.') {
          for (char c = '1'; c <= '9'; c++) {
            if (isValid(board, i, j, c)) {
              board[i][j] = c;
              if (solve(board))
                return true;
              else
                //回退
                board[i][j] = '.';
            }
          }
          return false;
        }
      }
    }
    return true;
  }

  private boolean isValid(char[][] board, int row, int col, char c) {
    for (int i = 0; i < board.length; i++) {
      if (board[i][col] != '.' && board[i][col] == c) return false;
      if (board[row][i] != '.' && board[row][i] == c) return false;
    }
    int m = (row / 3) * 3;
    int n = (col / 3) * 3;
    for (int k = 0; k < 3; k++) {
      for (int j = 0; j < 3; j++) {
        if (board[m + k][n + j] != '.' && board[m + k][n + j] == c)
          return false;
      }
    }
    return true;
  }

9.二分查找

  • 有序
  • 数组形式
  • 有界

练习

1.平方根

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int mySqrt(int x) {
        if (x==1 || x==0) return x;
        int left = 1;
        int right = x;
        int res = 0;
    //注意等于号
        while (left <= right) {
            int mid = (left + right) / 2;
            if (mid * mid == x)
                return mid;
            else if (mid  > x / mid) {
                right = mid - 1;
            } else {
                left = mid + 1;
                res = mid;
            }
        }
        return res;
    }

10.字典树(Trie Tree)

实际应用

统计排序大量字符串，文本词频统计（搜索引擎）

基本结构

![](https://cxlsky.oss-cn-beijing.aliyuncs.com/blog/img/trie.png?x-oss-process=style/blogimg)

核心思想

空间换时间

基本性质：

  • 根节点不包含字符，除根节点外每一个节点都只包含一个字符
  • 每个节点所有子节点的字符都不同
  • 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串

练习

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
60
61
62
63
class TrieNode {
  public char val;
  public boolean isWord;
  public TrieNode[] children = new TrieNode[26];

  public TrieNode() {
  }

  public TrieNode(char c) {
    TrieNode node = new TrieNode();
    node.val = c;
  }
}

 class Trie {
  private TrieNode root;

  public Trie() {
    root = new TrieNode();
    root.val = ' ';
  }

  /**
   * Inserts a word into the trie.
   */
  public void insert(String word) {
    TrieNode ws = root;
    for (int i = 0; i < word.length(); i++) {
      char tmp = word.charAt(i);
      if (ws.children[tmp - 'a'] == null) {
        ws.children[tmp - 'a'] = new TrieNode(tmp);
      }
      ws = ws.children[tmp - 'a'];
    }
    ws.isWord = true;
  }

  /**
   * Returns if the word is in the trie.
   */
  public boolean search(String word) {
    TrieNode ws = root;
    for (int i = 0; i < word.length(); i++) {
      char tmp = word.charAt(i);
      if (ws.children[tmp - 'a'] == null) return false;
      ws = ws.children[tmp - 'a'];
    }
    return ws.isWord;
  }

  /**
   * Returns if there is any word in the trie that starts with the given prefix.
   */
  public boolean startsWith(String prefix) {
    TrieNode ws = root;
    for (int i = 0; i < prefix.length(); i++) {
      char tmp = prefix.charAt(i);
      if (ws.children[tmp - 'a'] == null) return false;
      ws = ws.children[tmp - 'a'];
    }
    return true;
  }
}

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
public List<String> findWords(char[][] board, String[] word) {
     Set<String> res = new HashSet<>();
   for (int o = 0; o < word.length; o++)
     for (int i = 0; i < board.length; i++) {
       for (int j = 0; j < board[0].length; j++) {
         if (exist(board, i, j, word[o], 0))
           res.add(word[o]);
       }
     }
   List<String> end = new ArrayList<>();
   end.addAll(res);
   return end;
   }
   private boolean exist(char[][] board, int i, int j, String word, int ind) {
   if (ind == word.length()) return true;
   if (i > board.length - 1 || i < 0 || j < 0 || j > board[0].length - 1 || board[i][j] != word.charAt(ind))
     return false;
   board[i][j] = '*';
   boolean result = exist(board, i - 1, j, word, ind + 1) ||
           exist(board, i, j - 1, word, ind + 1) ||
           exist(board, i, j + 1, word, ind + 1) ||
           exist(board, i + 1, j, word, ind + 1);
   board[i][j] = word.charAt(ind);
   return result;
 }

11.位运算

练习

1.二进制数字1的个数

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int sum = 0;
    while (n != 0) {
      n = n & (n - 1);
      sum++;
    }
    return sum;
    }
}

2.是否是2的指数

1
2
3
4
5
public boolean isPowerOfTwo(int n) {
        if (n <= 0) return false;
        n = n & (n - 1);
        return n == 0;
    }

3.计算1的个数

1
2
3
4
5
6
7
public int[] countBits(int num) {
        int[] arr = new int[num+1];
        for (int i = 1; i <= num; i++) {
            arr[i] = arr[i&(i-1)] + 1;
        }
        return arr;
    }

arr 记录1至n中1的个数 得到相关递推公式

4.n皇后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int totalNQueens(int n){
    List<Integer> res = new ArrayList<>();
    dfs(n,res,0,0,0,0);
    return res.size();
  }
  public static void dfs (int n, List res, int row, int col, int pia, int na) {
    if (row >= n) {
      res.add(1);
      return;
    }
    int bits = (~(col | pia | na) & (1 << n) - 1);
    while (bits > 0) {
      int p = bits & (- bits);
      dfs(n, res, row + 1, col | p, (pia | p) << 1, (na | p) >> 1);
      bits = bits & (bits - 1);
    }
  }

12.动态规划

图

练习

1.爬楼梯

1
2
3
4
5
6
7
8
9
10
11
12
public int climbStairs(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    int a = 1, b = 2;
    int sum = 0;
    for (int i = 2; i < n; i ++) {
      sum = a + b;
      a = b;
      b = sum;
    }
    return sum;
  }

2.三角形的最短路径和

1
2
3
4
5
6
7
8
9
10
11
public int minimumTotal(List<List<Integer>> triangle) {
   int[] res = new int[triangle.size()];
   for(int i = 0;i < triangle.size(); i++)
     res[i] = triangle.get(triangle.size() - 1).get(i);
   for (int i = triangle.size() - 2; i >= 0; i--) {
     for (int j = 0; j < triangle.get(i).size(); j++) {
       res[j] = triangle.get(i).get(j) + Math.min(res[j], res[j + 1]);
     }
   }
   return res[0];
 }

3.乘积最大子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int maxProduct(int[] nums) {
    int[][] res = new int[nums.length][2];
    // res[][0]当前代表最大值  res[][1]代表当前最小值
    for (int i = 0; i < nums.length; i++) {
      res[i][0] = nums[i];
      res[i][1] = nums[i];
    }
    int max = res[0][1];
    for (int i = 1; i < nums.length; i++) {
      if (nums[i] > 0) {
        res[i][0] = Math.max(nums[i] * res[i - 1][0], res[i][0]);
        res[i][1] = Math.min(nums[i] * res[i - 1][1], res[i][1]);
      } else {
        res[i][0] = Math.max(nums[i] * res[i - 1][1], res[i][0]);
        res[i][1] = Math.min(nums[i] * res[i - 1][0], res[i][1]);
      }
      max = Math.max(max, res[i][0]);
    }
    return max;
  }

4.股票买卖问题

121、122、123 、309、188、714

1
2


5.最长上升子序列

o(n²)

1
2
3
4
5
6
7
8
9
10
11
12
13
public static int lengthOfLIS(int[] nums) {
    int[] dp = new int[nums.length];
    int res = 1;
    for (int i = 0; i < dp.length; i++)
      dp[i] = 1;
    for (int i = 1; i < nums.length; i++) {
      for (int j= 0; j < i; j ++) {
        if (nums[i] > nums[j]) dp[i] = Math.max(dp[j] + 1, dp[i]);
      }
      res = Math.max(res, dp[i]);
    }
    return res;
  }

dp[i]代表在i位置的数字时，当前的最长子序列。

O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int len = 0;
        for (int num : nums) {
            int i = Arrays.binarySearch(dp, 0, len, num);
            if (i < 0) {
                i = -(i + 1);
            }
            dp[i] = num;
            if (i == len) {
                len++;
            }
        }
        return len;
    }

维护一个数组dp ，通过二分查找寻找插入的数（替换掉比其大的最小的数），最后返回长度

6.零钱兑换

1
2
3
4
5
6
7
8
9
10
11
12
13
public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    dp[0] = 0;
    for (int i = 1; i <= amount; i++)
      dp[i] = amount + 1;
    for (int i = 1; i <= amount; i++) {
      for (int coin : coins) {
        if (i - coin >= 0)
          dp[i] = Math.min(dp[i - coin] + 1, dp[i]);
      }
    }
    return dp[amount] > amount ? -1 : dp[amount];
  }

7.编辑距离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int minDistance(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++) {
      for (int j = 1;j <= n; j++) {
        if (word1.charAt(i - 1) == word2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
        else {
          dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j -1])) + 1;
        }
      }
    }
    return dp[m][n];
  }

13.并查集

练习

1.岛屿数量

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
if (grid.length == 0) return 0;
    int res = 0;
    int m = grid.length;
    int n = grid[0].length;
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        if (grid[i][j] == '1') {
          res++;
          DFS(i, j, grid);
        }
      }
    }
    return res;
  }

  public void DFS(int i, int j, char[][] grid) {
    if (i < 0 || j < 0 || i > grid.length - 1 || j > grid[0].length - 1 || grid[i][j] == '0') return;
    grid[i][j] = '0';
    DFS(i + 1, j, grid);
    DFS(i - 1, j, grid);
    DFS(i, j - 1, grid);
    DFS(i, j + 1, grid);
  }

染色法，将附近的小岛全部染色

并查集

1
比较麻烦，思路类似 最后数一数祖先数有多少

2.朋友圈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int findCircleNum(int[][] grid) {
        if (grid.length == 0) return 0;
    int res = 0;
    int m = grid.length;
    int n = grid[0].length;
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        if (grid[i][j] == 1) {
          res++;
          DFS(i, j, grid);
        }
      }
    }
    return res;
    }
    public void DFS(int i, int j, int[][] grid) {
    if (i < 0 || j < 0 || i > grid.length - 1 || j > grid[0].length - 1 || grid[i][j] == 0) return;
    grid[i][j] = 0;
    for (int m = 0; m < grid.length; m++)
        DFS(m, j, grid);
    for (int n = 0; n < grid.length; n++)
        DFS(i, n, grid);
  }

与孤岛问题略有不同

14.LRU Cache

Cache缓存：

  • 记忆
  • 钱包-储物柜 （容量小）
  • 代码模块

LRUCache:

  • 最近最少使用（least recently used）
  • Double LinkedList（双向链表）
  • O(1)查询（最前面）
  • O(1) （修改）

练习

1.实现一个LRU Cache

布隆过滤器

---------------- The End ----------------

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址: https://cpsky.github.io/2019/09/01/算法笔记/
转载请注明出处, 谢谢！

分享到: