W.Fly's Blog

常用算法

2019/10/03 算法

常用算法

无重复数组全排列

class Solution {
    List<List<Integer>> resList = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        if(nums == null || nums.length == 0) {
            return resList;
        }
        LinkedList<Integer> trace = new LinkedList<>();
        backTrace(nums, trace);
        return resList;
    }
    public void backTrace(int[] nums, LinkedList<Integer> trace) {
        // 终止条件
        if(trace.size() == nums.length) {
            resList.add(new LinkedList<Integer>(trace));
            return;
        }
        for(int i = 0; i < nums.length; i++) {
            // 去除不满足条件元素
            if(trace.contains(nums[i])) {
                continue;
            }
            // 做选择
            trace.add(nums[i]);
            // 进入下一层
            backTrace(nums, trace);
            // 撤销选择
            trace.removeLast();
        }
    }
}

生成有效括号

class Solution {
    public List<String> res = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        if(n <= 0) {
            return res;
        }
        parenthesis("", n, n);
        return res;
    }

    public void parenthesis(String str, int left, int right) {
        if(left == 0 && right == 0) {
            res.add(str);
            return;
        }
        if(left == right) {
            parenthesis(str + "(", left - 1, right);
        } else if (left < right) {
            if(left > 0) {
                parenthesis(str + "(", left - 1, right);
            }
            parenthesis(str + ")", left, right - 1);
        }
    }
}

整数翻转

/**
* 整数翻转
*/
class Solurion {
    public int reverse01(int x) {
        int rev = 0;
        while (x != 0) {
            if (rev < Integer.MIN_VALUE / 10 || rev > Integer.MAX_VALUE / 10) {
                return 0;
            }
            // 对 10 取余
            int digit = x % 10;
            // 对 10 取整
            x /= 10;
            rev = rev * 10 + digit;
        }
        return rev;
    }
}

数组组成的最大值

class Solution {
    public String largestNumber(int[] nums) {
        // compareTo 返回前后两个字符串的asc码的差值
        PriorityQueue<String> queue = new PriorityQueue<>((x, y) -> (y + x).compareTo(x + y));
        for (int num : nums) {
            queue.offer(String.valueOf(num));
        }
        String res = "";
        while (queue.size() > 0) {
            res += queue.poll();
        }
        if (res.charAt(0) == '0') {
            return "0";
        }
        return res;
    }
}

public class Solution01 {
    /**
     * 最大数
     * @param nums int整型一维数组 
     * @return string字符串
     */
    public String solve(int[] nums) {
        // 边界值
        if (nums == null || nums.length == 0) return "";
        // 快速排序
        quickSort(nums, 0, nums.length - 1);
        // 换完之后，结果是能组成最大的数都在前面，所以转化为一个String返回即可
        String res = "";
        for (int i = 0; i < nums.length; ++i) {
            res += (nums[i] + "");
        }
        if (res.charAt(0) == '0') {
            return "0";
        }
        return res;
    }

    //快速排序
    public void quickSort(int[] arr, int start, int end) {
        if (start < end) {
            //把数组中的第0个数字做为标准数
            int stard = arr[start];
            //记录需要排序的下标
            int low = start;
            int high = end;
            //循环找比标准数大的数和比标准数小的数
            while (low < high) {
                //右边的数字比标准数大
                while (low < high && compare(stard, arr[high])) {
                    high--;
                }
                //使用右边的数字替换左边的数
                arr[low] = arr[high];
                //如果左边的数字比标准数小
                while (low < high && compare(arr[low], stard)) {
                    low++;
                }
                arr[high] = arr[low];
            }
            //把标准数赋给低所在的位置的元素
            arr[low] = stard;
            //处理所有的小的数字
            quickSort(arr, start, low);
            //处理所有的大的数字
            quickSort(arr, low + 1, end);
        }
    }

    // 比较ab，ba大小 ，sum1是  ab ,sum2 是ba
    public boolean compare(int num1, int num2) {
        String s12 = "" + num1 + num2;
        String s21 = "" + num2 + num1;
        int a = Integer.parseInt(s12), b = Integer.parseInt(s21);
        return a >= b ? true : false;
    }
}

二叉树

二叉树的深度

public class Solution {
    //递归
    public int TreeDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            return Math.max(TreeDepth(root.left), TreeDepth(root.right)) + 1;
        }
    }
}

public class TreeNode {
    public TreeNode left;
    public TreeNode right;
}

二叉树镜像

public class Solution {

    /**
     * 递归
     *
     * @param root
     */
    public TreeNode Mirror(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode temp = root.left;
        root.left = Mirror(root.right);
        root.right = Mirror(temp);
        return root;
    }
    
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode next;

    public TreeNode(int val) {
        this.val = val;
    }
}

二叉树打印成多行

import java.util.*;
/**
 * 时间复杂度：O(N)
 * 空间复杂度：O(N)
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> resList = new ArrayList<ArrayList<Integer>>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        if(pRoot == null) {
            return resList;
        }
        queue.offer(pRoot);
	int count = 1;
	int size = 0;
        while(!queue.isEmpty()) {
            ArrayList<Integer> list = new ArrayList<Integer>();
            size = queue.size();
            while(size-- > 0) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left != null) {
                    queue.offer(node.left);
                }
                if(node.right != null) {
                    queue.offer(node.right);
                }
            }
	    // 之字形打印开放这几行代码
//          if (count % 2 == 0) {
//              Collections.reverse(list);
//          }
//          count++;
            resList.add(list);
        }
        return resList;
    }
}

二叉树层序打印

import java.util.*;
/**
 * 时间复杂度：O(N)
 * 空间复杂度：O(N)
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root == null) {
            return new int[0];
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<Integer> list = new ArrayList<Integer>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            list.add(cur.val);
            if(cur.left != null) {
                queue.offer(cur.left);
            }
            if(cur.right != null) {
                queue.offer(cur.right);
            }
        }
        int len = list.size();
        int[] nums = new int[len];
        for(int i = 0; i < len; i++) {
            nums[i] = list.get(i);
        }
        return nums;
    }
}

数组实现栈

/**
 * 实现栈
 *
 * @author: wangfei
 * @date: 2020/3/9 21:17
 */
public class StackOfIntegers {
    private int[] elements;

    //记录个数
    private int elementSize;

    public StackOfIntegers(int capacity) {
        elements = new int[capacity];
    }

    //进栈
    public void Push(int value) {
        //扩容
        if (elementSize > elements.length) {
            int[] temp = new int[elementSize * 2];
//            System.arraycopy(elements, 0, temp, 0, elements.length);
            for (int i = 0; i < elements.length; i++) {
                temp[i] = elements[i];
            }
            elements = temp;
        }
        //放入元素
        elements[elementSize++] = value;
    }

    //出栈
    public int Pop() {
        return elements[--elementSize];
    }

    //判断栈是否为空
    public boolean Isempty() {
        return elementSize == 0;
    }

    //获取栈顶元素
    public int Peek() {
        return elements[elementSize - 1];
    }

    public static void main(String[] args) {
        StackOfIntegers stackOfIntegers = new StackOfIntegers(15);
        int[] nums = new int[15];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = i;
        }
        for (int i = 0; i < nums.length; i++) {
            stackOfIntegers.Push(nums[i]);
        }
        while (!stackOfIntegers.Isempty()) {
            System.out.println(stackOfIntegers.Pop() + "");
        }
    }
}

密码强度检验

import java.util.Scanner;

/**
 * 强密码长度至少为8个字符，最多为20个字符，至少有一个大写、一个小写、一个数字，
 * 每种不能连续超过3个，给定一个字符串，判断是否为强密码
 * @author: wangfei
 * @date: 2020/2/26 18:13
 */
public class Main {
    public static boolean func(String s) {
        //continue_num的十位记录哪种类型，各位记录每一类的数量
        int continue_num = 0;
        int f_big = 0, f_smal = 0, f_num = 0;
        if (s.length() < 8 || s.length() > 20)
            return false;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) >= 'A' && s.charAt(i) <= 'Z') {
                f_big = 1;
                if (continue_num / 10 != 1) {
                    continue_num = 10;
                }
            } else if (s.charAt(i) >= 'a' && s.charAt(i) <= 'z') {
                f_smal = 1;
                if (continue_num / 10 != 2) {
                    continue_num = 20;
                }
            } else if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                f_num = 1;
                if (continue_num / 10 != 3) {
                    continue_num = 30;
                }
            }
            continue_num++;
            //每种类型连续出现超过三次返回false
            if (continue_num % 10 > 3) {
                return false;
            }
        }
        //每种类型至少出现一次
        if (f_big + f_smal + f_num == 3)
            return true;
        return false;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String t = sc.nextLine();
        System.out.println(func(t));
    }
}

数组中出现次数超过一半的数字

/**
 * 数组中出现次数超过一半的数字
 * <p>
 * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。
 * 由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0
 *
 * @author: wangfei
 * @date: 2019/5/4 23:33
 */
public class Solution {

    /**
     * 多数投票问题，可以利用 Boyer-Moore Majority Vote Algorithm 来解决这个问题，使得时间复杂度为 O(N)。
     * <p>
     * 使用 count 来统计一个元素出现的次数，当遍历到的元素和统计元素相等时，令 count++，否则令 count--。如果前面查找了 i 个元素，
     * 且 count == 0，说明前 i 个元素没有 majority，或者有 majority，但是出现的次数少于 i / 2 ，因为如果多于 i / 2 的话
     * count 就一定不会为 0 。此时剩下的 n - i 个元素中，majority 的数目依然多于 (n - i) / 2，因此继续查找就能找出 majority。
     *
     * @param array
     * @return
     */
    public static int MoreThanHalfNumSolution(int[] array) {
        int majority = array[0];
        //确定出现次数最多的数字
        for (int i = 1, count = 1; i < array.length; i++) {
            count = array[i] == majority ? count + 1 : count - 1;
            if (count == 0) {
                majority = array[i];
                count = 1;
            }
        }
        //计算数字出现的次数
        int res = 0;
        for (int arr : array) {
            if (arr == majority) {
                res++;
            }
        }
        return res > array.length / 2 ? majority : 0;
    }

删除公共字符串

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * @author: wangfei
 * @date: 2020/2/20 19:21
 */
public class Java {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str1 = sc.nextLine();
        String str2 = sc.nextLine();
        StringBuffer newStr = new StringBuffer();
        Map<Integer, Character> map = new HashMap<>();
        for (int i = 0; i < str2.length(); i++) {
            map.put(i, str2.charAt(i));
        }
        for (int i = 0; i < str1.length(); i++) {
            if (!map.containsValue(str1.charAt(i))) {
                newStr.append(str1.charAt(i));
            }
        }
        System.out.println(newStr.toString());
    }
}



import java.util.Scanner;
public class Main1 {
    public static void main(String[] args)  {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String s1 = sc.nextLine();
            String s2 = sc.nextLine();
            String pattern = "[" + s2 + "]";
            String result = s1.replaceAll(pattern, "");
            System.out.println(result);
        }
    }
}

返回IP地址

import java.util.ArrayList;
import java.util.Scanner;

/**
 * 给一串数字，返回所有可能的IP地址
 *
 * @author: wangfei
 * @date: 2019/11/14 10:17
 */
public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int len = s.length();
        ArrayList<String> res = new ArrayList<>();
        for (int i = 1; i < 4 && i < len - 2; i++) {
            for (int j = i + 1; j < i + 4 && j < len - 1; j++) {
                for (int k = j + 1; k < j + 4 && k < len; k++) {
                    if (len - k < 4) {
                        int a = Integer.parseInt(s.substring(0, i));
                        int b = Integer.parseInt(s.substring(i, j));
                        int c = Integer.parseInt(s.substring(j, k));
                        int d = Integer.parseInt(s.substring(k));
                        if (a <= 255 && b <= 255 && c <= 255 && d <= 255) {
                            String ip = a + "." + b + "." + c + "." + d;
                            if (ip.length() == len + 3) {
                                res.add(ip);
                            }
                        }
                    }
                }
            }
        }
        System.out.println(res);
    }
}

最长回文子串

public class Solution{
/**
     * 最长回文子串
     * 我们枚举所有的「回文中心」并尝试「扩展」，直到无法扩展为止，此时的回文串长度即为此「回文中心」
     * 下的最长回文串长度。我们对所有的长度求出最大值，即可得到最终的答案。
     *
     * @param s
     * @param n
     * @return
     */
    public int getLongestPalindrome(String s, int n) {
        if(s.length() < 1 || s == null) {
            return 0;
        }
        int len1, len2, len = 0;
        for (int i = 0; i < n; i++) {
           len1 = compare(s, i, i);
           len2 = compare(s, i, i+1);
           len = Math.max(len, len1);
	   len = Math.max(len, len2);
        }
        return len;
    }

    public int compare(String s, int l, int r) {
        while (l >= 0 && r < s.length() && (s.charAt(l) == s.charAt(r))) {
            --l;
            ++r;
        }
        return r - l - 1;
    }
}

最长上升子序列

import java.util.Arrays;
/**
 * 最长上升子序列
 * <p>
 * 给定一个未排序的整数数组，求其最长递增子序列的长度。
 * 注意:可能有多个LIS组合，只需要返回长度即可。
 * 您的算法应该在O(n2)复杂度下运行。
 */
public class Solution {
    /**
     * DP
     * 时间复杂度：O(N^2)
     */
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0)
            return 0;
        // memo[i] 表示以 nums[i] 为结尾的最长上升子序列的长度
        int[] memo = new int[nums.length];
        Arrays.fill(memo, 1);
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    memo[i] = Math.max(memo[i], 1 + memo[j]);
                }
            }
        }
        int res = 1;
        for (int i = 0; i < nums.length; i++) {
            res = Math.max(res, memo[i]);
        }
        return res;
    }

    /**
     * 双指针
     * 时间复杂度：O(nlogn)
     */
    public int lengthOfLIS2(int[] nums) {
        int[] memo = new int[nums.length];
        int size = 0;
        for (int num : nums) {
            int i = 0, j = size;
            while (i != j) {
                int mid = i + (j - i) / 2;
                if (memo[mid] < num) {
                    i = mid + 1;
                } else {
                    j = mid;
                }
            }
            memo[i] = num;
            if (i == size) {
                ++size;
            }
        }
        return size;
    }
}

最长公共子串

public class Solution {
    public int LCS(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        if (m == 0 || n == 0)
            return 0;
        int[][] res = new int[n + 1][m + 1];
        int max = -1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (s1.charAt(i) != s2.charAt(j)) {
                    res[j + 1][i + 1] = 0;
                } else {
                    res[j + 1][i + 1] = res[j][i] + 1;
                }
                max = Math.max(max, res[j + 1][i + 1]);
            }
        }
        return max;
    }
}

最长公共子序列

public class Solution {
    public int LCS(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        if (m == 0 || n == 0)
            return 0;
        int[][] memo = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (s1.charAt(i) == s2.charAt(j)) {
                    memo[i + 1][j + 1] = memo[i][j] + 1;
                } else {
                    memo[i + 1][j + 1] = Math.max(memo[i][j + 1], memo[i + 1][j]);
                }
            }
        }
        return memo[m][n];
    }
}

删除链表重复元素

public class Solution {
    /**
     * 给出链表为1->2->3->3->4->4->5,返回1->2->5
     */
    public ListNode deleteDuplicates (ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode realHead = new ListNode(Integer.MIN_VALUE);
        realHead.next = head;
        ListNode pre = realHead;
        ListNode cur = realHead.next;
        int count = 0;
        while(cur != null){
            //标记是否为重复元素
            count = 0;
            while(cur.next != null && cur.val == cur.next.val){
                cur = cur.next;
                count++;
            }
            if(count != 0){
                pre.next = cur.next;
                cur = cur.next;
            }else{
                pre = cur;
                cur = cur.next;
            }
        }
        return realHead.next;
    }
}

重排链表

/**
 * 将给定链表L：L0->L1->...->Ln-1->Ln
 * 重新排序为L0->Ln->L1->Ln-1->L2->Ln-2->...
 */
public class Solution {
    public void reorderList(ListNode head) {
        if(head == null || head.next == null) {
            return;
        }
        ListNode fast = head;
        ListNode slow = head;
	// 快慢指针找中点
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        fast = reverse(slow.next);
        slow.next = null;
        slow = head;
        ListNode Next = null;
        while(slow != null && fast != null) {
            Next = slow.next;
            slow.next = fast;
            slow = fast;
            fast = Next;
        }
    }
    
    // 反转单链表
    private ListNode reverse(ListNode head) {
        ListNode res = null;
        ListNode Next = new ListNode(-1);
        while(head != null) {
            Next = head.next;
            head.next = res;
            res = head;
            head = Next;
        }
        return res;
    }
}

链表倒数第k个节点

public class Soultion {
    // 双指针，时间复杂度为 O(N)
    public ListNode FindKthToTail(ListNode head, int k) {
        if (head == null || k == 0)
            return null;
        ListNode slow = head;
        ListNode fast = head;
        int count = 1;
        while (fast.nxet != null) {
            fast = fast.next;
            ++count;
            if (count > k) {
                slow = slow.next;
            }
        }
         return count < k ? null : slow;
    }

    public ListNode FindKthToTail2(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;
        for(int i = 0; i < k; i++) {
            fast = fast.next;
        }
        while(fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

public class TreeNode {
    public int val;
    public ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
}

链表删除倒数第n个节点

public class Soultion {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head == null) {
            return head;
        }
        ListNode pre = new ListNode(-1);
        pre.next = head;
        ListNode fast = pre;
        ListNode slow = pre;
        int count = 0;
        // 遍历前n个结点
        for(int i = 0; i < n; i++) {
            fast = fast.next;
        }
        // 快慢指针同时移动
        while(fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        // 跳过被删除结点
        ListNode Next = slow.next;
        slow.next = Next.next;
        return pre.next;
    }
}

public class TreeNode {
    public int val;
    public ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
}

单链表排序

public ListNode sortInList (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 = sortInList(head);
	// 后半段链表排序
	ListNode right = sortInList(temp);
	ListNode pre = new ListNode(-1);
	ListNode cur = pre;
	while(left != null && right != null) {
		if(left.val <= right.val) {
			cur.next = left;
			left = left.next;
		} else {
			cur.next = right;
			right = right.next;
		}
		cur = cur.next;
	}
	cur.next = left != null ? left : right;
	return pre.next;
}

判断回文链表

public boolean isPail (ListNode head) {
	if(head == null || head.next == null) {
		return true;
	}
	ListNode fast = head, slow = head;
	while(fast != null && fast.next != null) {
		fast = fast.next.next;
		slow = slow.next;
	}
	if(fast != null) {
		slow = slow.next;
	}
	slow = reverse(slow);
	fast = head;
	while(slow != null) {
		if(slow.val != fast.val) {
			return false;
		}
		fast = fast.next;
		slow = slow.next;
	}
	return true;
}

public ListNode reverse(ListNode head) {
	ListNode pre = null;
	ListNode cur = head;
	while(cur != null) {
		ListNode next = cur.next;
		cur.next = pre;
		pre = cur;
		cur = next;
	}
	return pre;
}

链表奇偶排序

public ListNode oddEvenList (ListNode head) {
	if(head == null || head.next == null) {
		return head;
	}
	ListNode odd = head, even = head.next;
	ListNode cur = even;
	while(cur != null && cur.next != null) {
		// 奇数链
		odd.next = cur.next;
		odd = odd.next;
		// 偶数链
		cur.next = odd.next;
		cur = cur.next;
	}
	// 奇数链和偶数链拼接
	odd.next = even;
	return head;
}

归并排序

public class MergeSort {

    public void mergeSort(int[] arr, int l, int h) {
        int mid = l + (h - l) / 2;
        if (l < h) {
            //处理左边
            mergeSort(arr, l, mid);
            //处理右边
            mergeSort(arr, mid + 1, h);
            //归并
            merge(arr, l, mid, h);
        }
    }

    public void merge(int[] arr, int l, int mid, int h) {
        //用于存储归并后的临时数组
        int[] res = new int[h - l + 1];
        //分别记录第一个数组、第二个数组、临时数组的下标
        int i = l, j = mid + 1, index = 0;
        //遍历两个数组取出小的元素放入临时数组
        while (i <= mid && j <= h) {
            if (arr[i] <= arr[j]) {
                res[index] = arr[i];
                i++;
            } else {
                res[index] = arr[j];
                j++;
            }
            index++;
        }
        //处理多余数据
        while (i <= mid) {
            res[index] = arr[i];
            i++;
            index++;
        }
        while (j <= h) {
            res[index] = arr[j];
            j++;
            index++:
        }
        //把临时数组中的元素重新存入原数组
        for (int k = 0; k < res.length; k++) {
            arr[k + l] = res[k];
        }
    }
}

有序数组合并(参考归并排序)

public void merge(int[] nums1, int nums2, int m, int n) {
    int index1 = m - 1, index2 = n - 1, mergeIndex = m + n - 1;
    while (index1 >= 0 || index2 >= 0) {
        if (index1 < 0) {
            nums1[mergeIndex--] = nums2[index2--];
        } else if (index2 < 0) {
            nums1[mergeIndex--] = nums1[index1--];
        } else if (nums1[index1] > nums2[index2]) {
            nums1[mergeIndex--] = nums1[index1--];
        } else {
            nums1[mergeIndex--] = nums2[index2--];
        }
    }
}

快速排序

public class QuickSort {
    //两路快排
    public int[] quickSort(int[] arr, int start, int end) {
        if (start < end) {
            //将数组的第0个元素作为标准数
            int stard = arr[start];
            //记录需要排序的下标
            int l = start;
            int h = end;
            while (l < h) {
                //循环查找比标准数大的数
                while (l < h && stard <= arr[h]) {
                    h--;
                }
                arr[l] = arr[h];
                //循环查找比标准数小的数
                while (l < h && stard >= arr[l]) {
                    l++;
                }
                arr[h] = arr[l];
            }
            //把标准数赋值给l位置的元素
            arr[l] = stard;
            //处理所有小的数
            quickSort(arr, start, l);
            //处理所有大的数
            quickSort(arr, l + 1, end);
        }
        return arr;
    }

    //三路快排
    public int[] quickSort3Ways(int[] arr, int start, int end) {
        if (start < end) {
            int stard = arr[start];
            int lt = start;
            int gt = end + 1;
            int i = start + 1;
            while (i < gt) {
                if (arr[i] < stard) {
                    swap(arr, i, lt + 1);
                    lt++;
                    i++;
                } else if (arr[i] > stard) {
                    swap(arr, i, gt - 1);
                    gt--;
                } else {
                    i++;
                }
            }
            swap(arr, start, lt);
            quickSort3Ways(arr, start, lt - 1);
            quickSort3Ways(arr, gt, end);
        }
        return arr;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

二叉树转双向链表

public class Solution {
    // 递归
    //返回的第一个指针，即为最小值，先定为null
    public TreeNode head = null;
    //中序遍历当前值的上一位，初值为最小值，先定为null
    public TreeNode pre = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null)
            //中序递归，叶子为空则返回
            return null;
        //首先递归到最左最小值
        Convert(pRootOfTree.left);
        //找到最小值，初始化head与pre
        if (pre == null) {
            head = pRootOfTree;
            pre = pRootOfTree;
        }
        //当前节点与上一节点建立连接，将pre设置为当前值
        else {
            pre.right = pRootOfTree;
            pRootOfTree.left = pre;
            pre = pRootOfTree;
        }
        Convert(pRootOfTree.right);
        return head;
    }
}

// 非递归（栈）
public TreeNode Convert(TreeNode pRootOfTree) {
	if (pRootOfTree == null)
		return null;
	//设置栈用于遍历
	Stack<TreeNode> s = new Stack<TreeNode>();
	TreeNode head = null;
	TreeNode pre = null;
	//确认第一个遍历到最左，即为首位
	boolean isFirst = true;
	while(pRootOfTree != null || !s.isEmpty()){
		//直到没有左节点
		while(pRootOfTree != null){ 
			s.push(pRootOfTree);
			pRootOfTree = pRootOfTree.left;
		}
		pRootOfTree = s.pop();
		//最左元素即表头
		if(isFirst){ 
			head = pRootOfTree;
			pre = head;
			isFirst = false;
		//当前节点与上一节点建立连接，将pre设置为当前值
		}else{ 
			pre.right = pRootOfTree;
			pRootOfTree.left = pre;
			pre = pRootOfTree;
		}
		pRootOfTree = pRootOfTree.right;
	}
	return head;
}

public class TreeNode {
    public TreeNode right;
    public TreeNode left;
}

二叉树的最近公共祖先

public class Solution {
    public TreeNode LCA(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == root || q == root) {
            return root;
        }
        TreeNode left = LCA(root.left, p, q);
        TreeNode right = LCA(root.right, p, q);
        if (left == null)
            return right;
        if (right == null)
            return left;
        return root;
    }
}

public class TreeNode {
    public TreeNode right;
    public TreeNode left;
}

二叉搜索树的最近公共祖先

/**
* 二叉搜索树特性：根节点大于左节点且小于右节点n
*/
public class Solution {
    public TreeNode LCAS(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null)
            return root;
        if (p.val > root.val && q.val > root.val)
            return LCAS(root.right, p, q);
        if (p.val < root.val && q.val < root.val)
            return LCAS(root.left, p, q);
        return root;
    }
}

public class TreeNode {
    public TreeNode left;
    public TreeNode right;
    public int val;

    public TreeNode(int val) {
        this.val = val;
    }
}

排序链表定位到中位数（求值）

public class Solution {
    //快慢指针
    public double middle(ListNode head) {
        if (head == null)
            return 0;
        ListNode duy = new ListNode(0);
        duy.next = head;
        ListNode slow = duy;
        ListNode fast = duy;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        double res = 0;
        if (fast == null) {
            res = slow.val;
        } else {
            if (fast.next == null)
                res = (double) (slow.val + slow.next.val) / 2;
        }
        return res;
    }
}

public class ListNode {
    public int val;
    public ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
}

三个数求和问题

import java.util.*;

public class Solution {
    //暴力解法
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Set<List<Integer>> set = new HsahSet<>();
        if (nums.length < 3)
            return res;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[k]);
                        //元素去重
                        set.add(list);
                    }
                }
            }
            res.addAll(set);
            return res;
        }
    }

    // 三数之和为 0
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> resList = new ArrayList<>();
        if (num == null || num.length == 0) return resList;
        // 排序去重
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            // 剪枝
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int start = i + 1, end = nums.length - 1;
            while (start < end) {
                if (nums[i] + nums[start] + nums[end] > 0) end--;
                else if (nums[i] + nums[start] + nums[end] < 0) start++;
                else {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[start]);
                    list.add(nums[end]);
		    resList.add(list);
                    // 内层去重
                    while (start < end && nums[start] == nums[start + 1]) start++;
                    while (start < end && nums[end] == nums[end - 1]) end--;
                    // 更新直到不重复
                    start++;
                    end--;
                }
            }
        }
        return resList;
    }
}

单例模式

//懒汉式-线程不安全
public class Singleton {
    private static Singleton uniqueInstance;

    private Singleton() {
    }

    public static Singleton getUniqueInstance() {
        if (uniqueInstance == null) {
            uniqueInstance = new Singleton();
        }
        return uniqueInstance;
    }
}

//饿汉式-线程安全
public class Singleton {
    private static Singleton uniqueInstance;

    private Singleton() {
    }

    public static synchronized Singleton getUniqueInstance() {
        if (uniqueInstance == null) {
            uniqueInstance = new Singleton();
        }
        return uniqueInstance;
    }
}

//双重校验锁-线程安全
public class Singleton {
    private volatile static Singleton uniqueInstance;

    private Singleton() {
    }

    public static Singleton getUniqueInstance() {
        if (uniqueInstance == null) {
            synchronized (Singleton.class) {
                if (uniqueInstance == null) {
                    uniqueInstance = new Singleton();
                }
            }
        }
        return uniqueInstance;
    }
}

死锁

// 模拟转账操作
public class Tranfer implements Runnable {
    private final Account from;
    private final Account to;
    private final int money;

    public Tranfer(Account from, Account to, int money) {
        this.from = from;
        this.to = to;
        this.money = money;
    }

    @Override
    public void run() {
        synchronized (from) {
            from.money = from.money - money;
            to.money = to.money + money;
        }
    }

    public class Account {
        int money;
    }
}

// 测试
public class DeadLock {
    public static void main(String[] args) {
        Account a1 = new Account();
        Account a2 = new Account();
        Thread t1 = new Thread(new Tranfer(a1, a2, 10));
        Thread t2 = new Thread(new Tranfer(a2, a1, 10));
        t1.start;
        t2.start;
    }
}

    // 避免死锁
    @Override
    public void run() {
        synchronized (Accout.class) {
            from.money = from.money - money;
            to.money = to.money + money;
        }
    }

文本中出现的 Top K 字符串

  1. 如果文档能够全部存入内存，则通过 HashMap 来统计各个 word 出现的频率
  2. 如果文档不能存入内存，则用分治来解决：将这个文档通过hash(word) % n，hash 到 n 个不同的小文件中，n 根据文档的大小以及内存空间而定，hash 后，所有相同的 word 肯定会在同一个文件中，然后分别对这 n 个文件分别利用 HashMap 来统计其中 word 的频率，分别求出 topk，最后进行合并求总的 topk。
  3. 将 HashMap 中的所有实例都转为一个 Node 实例，Node 中包含 {word, times} 然后利用小顶堆来统计
  4. 堆没满，直接将 Node 放入堆，根据 times 来调整堆
  5. 堆满了，说明已经选出了 Top K，堆顶元素自然是词频最小的那个，这时如果 Node 的 tiems 大于堆顶元素，则放入堆中，并移除堆顶使得堆一直保持 K 个元素，如果 Node 的 times 大于堆顶元素，则不放入堆中
  6. 时间复杂度：遍历建 HashMap 是 O(N)，更新堆的时间复杂度为 O(NlogK)，总计 O(N) + O(NLogK)

两个栈实现队列

import iava.util.Stack;

public class MyQueue {

    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    /** Initialize your data structure here. */
    public MyQueue() {

    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        stack1.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

    /** Get the front element. */
    public int peek() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.isEmpty() ? 0 : stack2.peek();
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}

两个对列实现栈

import java.util.LinkedList;
import java.util.Queue;

/**
 * 时间复杂度：入栈操作 O(n)O(n)，其余操作都是 O(1)O(1)。
 * 空间复杂度：O(n)O(n)，其中 nn 是栈内的元素。需要使用两个队列存储栈内的元素。
 */
public class MyStack {

    Queue<Integer> queue1;
    Queue<Integer> queue2;

    /**
     * Initialize your data structure here.
     */
    public MyStack() {
        queue1 = new LinkedList<Integer>();
        queue2 = new LinkedList<Integer>();
    }

    /**
     * Push element x onto stack.
     */
    public void push(int x) {
        // 元素添加到队列 2 中
        queue2.offer(x);
        // 将队列 1 中的的元素依次添加到队列 2 中
        while (!queue1.isEmpty()) {
            queue2.offer(queue1.poll());
        }
        // 交换队列，保证元素都在 1 中，2 始终为空
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }

    /**
     * Removes the element on top of the stack and returns that element.
     */
    public int pop() {
        return queue1.poll();
    }

    /**
     * Get the top element.
     */
    public int top() {
        return queue1.peek();
    }

    /**
     * Returns whether the stack is empty.
     */
    public boolean empty() {
        return queue1.isEmpty();
    }
}

两个链表的第一个公共结点（两个链表是否相交）

public class Solution {
    /**
     * 设 A 的长度为 a + c，B 的长度为 b + c，其中 c 为尾部公共部分长度，可知 a + c +
     * b = b + c + a。
     * 当访问链表 A 的指针访问到链表尾部时，令它从链表 B 的头部重新开始访问链表 B；同样
     * 地，当访问链表 B 的指针访问到链表尾部时，令它从链表 A 的头部重新开始访问链表 A。这
     * 样就能控制访问 A 和 B 两个链表的指针能同时访问到交点。
     */
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode l1 = pHead1;
        ListNode l2 = pHead2;
        while (l1 != l2) {
            l1 = (l1 == null) ? pHead2 : l1.next;
            l2 = (l2 == null) ? pHead1 : l2.next;
        }
        return l1;
    }
}

public class ListNode {
    public ListNode next;
}

反转单链表

public class Solution {
    //非递归
    public ListNode ReverseList(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            ListNode Next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = Next;
        }
        return pre;
    }

    //递归
    public ListNode ReverseList2(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode second = head.next;
        ListNode reverseHead = ReverseList2(second);
        second.next = head;
        head.next = null;
        return reverseHead;
    }
}

public class ListNode {
    public ListNode next;
}

链表内指定区间反转

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        //设置虚拟头节点
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;
        //1.走left-1步到left的前一个节点
        for(int i = 0; i < m - 1; i++){
            pre = pre.next;
        }
        //2.走roght-left+1步到right节点
        ListNode rigthNode = pre;
        for(int i = 0; i < n - m + 1; i++){
            rigthNode = rigthNode.next;
        }
        //3.截取出一个子链表
        ListNode leftNode = pre.next;
        ListNode cur = rigthNode.next;
        //4.切断链接
        pre.next = null;
        rigthNode.next = null;
        //5.反转局部链表
        reverse(leftNode);
        //6.接回原来的链表
        pre.next = rigthNode;
        leftNode.next = cur;
        return dummyNode.next;
    }
    
    private ListNode reverse(ListNode head) {
        if(head == null) {
            return head;
        }
        ListNode res = null;
        ListNode cur = head;
        ListNode Next = new ListNode(-1);
        while(cur != null) {
            Next=  cur.next;
            cur.next = res;
            res = cur;
            cur = Next;
        }
        return res;
    }
}

public class Solution2 {
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        //设置虚拟头节点
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;
        for(int i = 0; i < m - 1; i++){
            pre = pre.next;
        }
 
        ListNode cur = pre.next;
        ListNode Cur_next ;
        for(int i = 0; i < n - m; i++){
            Cur_next = cur.next;
            cur.next = Cur_next.next;
            Cur_next .next = pre.next;
            pre.next = Cur_next ;
        }
        return dummyNode.next;
    }
}

判断环形链表

// 判断是否有环
public class Solution {
    //快慢指针
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast)
                return true;
        }
        return false;
    }
}

// 链表中环的入口节点
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        //快慢指针
        ListNode fast = pHead;
        ListNode slow = pHead;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast) {
                fast = pHead;
                while(fast != slow) {
                    fast = fast.next;
                    slow = slow.next;
                }
                return fast;
            }
        }
        return null;
    }
}

有序链表插入元素

/**
 * 有序链表插入元素
 *
 * @author: wangfei
 * @date: 2020/3/10 16:35
 */
public class Solution {
    public static ListNode insertListNode(ListNode head, int num) {
        if (head == null) {
            head = new ListNode(num);
        }
        if (head.val > num) {
            ListNode Next = head.next;
            ListNode node = new ListNode(head.val);
            head = new ListNode(num);
            head.next = node;
            node.next = Next;
        }
        ListNode duy = new ListNode(0);
        duy.next = head;
        while (duy.next != null && duy.next.val < num) {
            duy = duy.next;
        }
        ListNode Next = duy.next;
        ListNode node = new ListNode(num);
        duy.next = node;
        node.next = Next;
        return head;
    }

}

public class ListNode {
	public ListNode val;
	public ListNode next;
	public ListNode(int val) {
		this.val = val;
	} 
}

归并两个有序链表

public class Solution {

    //递归
    public ListNode Merge(ListNode list1, ListNode list2) {
        if (list1 == null)
            return list2;
        if (list2 == null)
            return list1;
        if (list1.val <= list2.val) {
            list1.next = Merge(list1.next, list2);
            return list1;
        } else {
            list2.next = Merge(list2.next, list1);
            return list2;
        }
    }

    //非递归
    public ListNode Merge2(ListNode list1, ListNode list2) {
        ListNode res = new ListNode(-1);
        ListNode cur = res;
        while (list1 != null && list2 != null) {
            int val1 = list1.val;
            int val2 = list2.val;
            if (val1 <= val2) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        if (list1 != null)
            cur.next = list1;
        if (list2 != null)
            cur.next = list2;
        return res.next;
    }
}

public class ListNode {
    public ListNode val;
    public ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
}

合并K个升序链表

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int l, int r) {
        if (l == r) {
            return lists[l];
        }
        if (l > r) {
            return null;
        }
        int mid = l + (r - l) / 2;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }


    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode cur = new ListNode(-1);
        ListNode res = cur;
        while(l1 != null && l2 != null) {
            if(l1.val <= l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        if(l1 == null) {
            cur.next = l2;
        }
        if(l2 == null){
            cur.next = l1;
        }
        return res.next;
    }
}

工厂模式

简单工厂

// 创建一个可以绘制不同形状的绘图工具，可以绘制长方形、正方形、圆形，每个图形都有一个 draw() 用于绘图
// 图形接口
public interface Shape {public void draw();}
// 长方形
public class Rectangle implements Shape {
    public Rectangle() { System.out.printle("长方形");}
    @Override
    public void draw() { System.out.printle("长方形 + draw");}
}
// 正方形
public class Square implements Shape() {
    public Square() { System.out.printle("正方形");}
    @Override
    public void draw() { System.out.printle("长方形 + draw");}
}
// 圆形
public class Circle implements Shape() {
    public Circle() { System.out.printle("圆形");}
    @Override
    public viod draw() { System.out.printle("圆形 + draw");}
}
// 工厂类
public class ShapeFactory {
    public static getShape (String shapeType) {
        if (shapeType == null)	return null;
        if (shapeType.equals("RECTANGLE"))	return new Rectangle();
        if (shapeType.equals("SQUARE"))	return new Square();
        if (shapeType.equals("CIRCLE"))	return new Circle();
    }
}
// 测试
public class test {
    public static void main(String[] srgs) {
        Shape rectangle = ShapeFactory.getShape("RECTANGLE");
        rectangle.draw();
    }
}

工厂方法

// 简单工厂中是需要提供一个统一的工厂来创建所有的对象，因此对象增加后需要修改这个统一的工厂
// 工厂方法中不再提供统一的工厂，而是针对不同的对象创建不同的工厂，也就是说用户无须知道具体的产品类型，只要知道创建产品的工厂类就行
// 前面定义的接口和圆形、正方形、长方形三种类型不变，去掉统一的工厂类 ShapeFactory
// 1、增加工厂接口
public interface Factory { public Shape getShape();}
// 2、增加圆形、长方形、正方形三种工厂类
public class RectangleFactory implements Factory {
    @Override
    public Shape getShape()	{ return new Rectangle();}
}
// ... 省略部分代码
// 测试
public class test {
    public static void main (String[] args) {
        Factory rectangleFactory = new RectangleFactory();
        Shape rectangle = rectangleFactory.getShape();
        rectangle.draw();
    }
}

抽象工厂

// 工厂方法是生产的都是同一类产品
// 抽象工厂生产一组产品，同时生产正方形和正方体、长方形和长方体、圆形和球体
// 前面定义的接口和圆形、正方形、长方形三种类型不变
// 1、三维图形接口
public interface Three { public void drawThree();}
// 2、增加三维图形
public class threeRectangle implements Three {
    public threeRectangle() { System.out.printle("长方体");}
    @Override 
    public void drawThree() { System.out.printle("长方体 + drawThree");}
}
// ... 省略部分代码
// 3、工厂接口
public interface Factory {
    public Shape getShpe();
    public Three getThhree();
}
// 4、具体工厂（生产长方形和长方体）
public class RectangleFactory implements Factory {
    @Override
    public Shape getShape()	{ return new Rectangle();}
    @Override
    public Three getThree() { return new threeRectangle();}
}
// ... 省略部分代码
// 5、测试
public class test {
    public static void main(String[] args) {
        Factory factory;
        Shape shape;
        Three three;
        factory = new RectangleFactory();
        shape = factory.getShape();
        three = factory.getThree();
        shape.draw();
        three.drawThree();
    }
}

原地旋转字符串【Offer 原题】

public String ReverseSentence(String str) {
    if (str == null || str.length() == 0) return "";
    char[] chars = str.toCharArray();
    int index = 0;
    while (index < str.length()) {
        int start = index, end = index;
        while (chars[end] != ' ' && end != str.length() - 1) end++;
        if (end < str.length() - 1) {
            rever(chars, start, end - 1);
            index = end + 1;
        } else {
            rever(chars, start, end);
            break;
        }
    }
    rever(chars, 0, str.length() - 1);
    return String.valueOf(chars);
}

private void rever(chars[] char, int start, int end) {
    if (start > end) return;
    while (start < end) swap(chars, start++, end--);
}

private void swap(char[] chars, int i, int j) {
    char temp = chars[i];
    chars[i] = chars[j];
    chars[j] = temp;
}

买股票

买股票的最佳时机

public int maxProfit(int[] prices) {
    // 局部最优
    int sum = 0;
    for (int i = 1; i < prices.length; i++) {
        if (prices[i] - prices[i - 1] > 0) {
            sum += (prices[i] - prices[i - 1]);
        }
    }
    return sum;
}

只能买卖一次股票 / 股票最长增长区间

public int maxProfit(int[] prices) {
    int sum = 0;
    int buy = prices[0];
    for (int i = 0; i < prices.length; i++) {
        if (buy > prices[i]) {
            buy = prices[i];
        } else {
            sum = Math.max(sum, prices[i] - buy);
        }
    }
    return sum;
}

求开方，精度为 1e-7

public double sqrt(double t, double precise) {
    double left = 0, right = t;
    while (right - left > precise) {
        double mid = (left + right) / 2;
        double sqrt = mid * mid;
        if (sqrt > t) {
            right = mid;
        } else {
            left = mid;
        }
    }
    return (left + right) / 2;
}

小偷投东西

一排不能连着偷

public int rob(int[] nums) {
  int pre2 = 0, pre1 = 0;
  for (int i = 0; i < nums.length; i++) {
    int cur = Math.max(pre2 + nums[i], pre1);
    pre2 = pre1;
    pre1 = cur;
 }
  return pre1;
}

环形不能连着偷

public  int rob(int[] nums) {
  if (nums == null || nums.length == 0) {
    return 0;
 }
  int n = nums.length;
  if (n == 1) {
    return nums[0];
 }
  return Math.max(rob(nums, 0, n - 2), rob(nums, 1, n - 1));
}
private  int rob(int[] nums, int first, int last) {
  int pre2 = 0, pre1 = 0;
  for (int i = first; i <= last; i++) {
    int cur = Math.max(pre1, pre2 + nums[i]);
    pre2 = pre1;
    pre1 = cur;
 }
  return pre1;
}

Search

    Table of Contents