刷题记录

数组问题

最长无重复子数组

给定一个数组arr,返回arr的最长无重复元素子数组的长度,无重复指的是所有数字都不相同。子数组是连续的,比如[1,3,5,7,9]的子数组有[1,3],[3,5,7]等等,但是[1,3,7]不是子数组

输入:
[1,2,3,1,2,3,2,2]
返回值:
3
复制
说明:
最长子数组为[1,2,3] 

方法一:

public class Solution {
    /**
     * 
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        if(arr.length <= 1) {
            return arr.length;
        } 
        // 无重复的起点
        int a = 0;
        // 当前无重复的最大长度
        int max = 1;
        // 1,2,3,1,4
        for(int b = 1; b < arr.length;b++) {
            // 寻找[a, b-1]是否存在于arr[b]相等的数, 如果存在则要更新a的值
            for(int i = b-1; i >= a; i--) {
                if(arr[i] == arr[b]) {
                    a = i + 1;
                    break;
                }
            }
            max = Math.max(max, b - a + 1);
        }
        return max;
    }
}

方法二:

public class Solution {
    /**
     * 
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        if(arr.length <= 1) {
            return arr.length;
        } 
        // 无重复的起点
        int a = 0;
        // 当前无重复的最大长度
        int max = 0;
        // 使用一个Map来保存已经遍历过的元素
        Map<Integer, Integer> map = new HashMap();
        // 1,2,3,1,4
        for(int b = 0; b < arr.length;b++) {
            if(map.containsKey(arr[b])) {
                // 每次的取值都要大于等于a, 防止a往前走
                a = Math.max(a, map.get(arr[b]) + 1);
            } 
            map.put(arr[b], b);
            max = Math.max(max, b - a + 1);
        }
        return max;
    }
}

方法三:

public class Solution {
    /**
     * 
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        if(arr.length <= 1) {
            return arr.length;
        } 
        int max = 0;
        // 使用一个队列来保存当前无重复的数据
        LinkedList<Integer> queue = new LinkedList();
        for(int i = 0; i < arr.length; i++) {
            // 遇到重复元素时,从头部一直出栈,知道无重复元素
            while(queue.contains(arr[i])) {
                queue.removeFirst();
            }
            queue.addLast(arr[i]);
            max = Math.max(max, queue.size());
        }
        return max;
    }
}

子数组的最大累加和问题

给定一个数组arr,返回子数组的最大累加和

例如,arr = [1, -2, 3, 5, -2, 6, -1],所有子数组中,[3, 5, -2, 6]可以累加出最大的和12,所以返回12.

题目保证没有全为负数的数据

[要求]

时间复杂度为O(n),空间复杂度为O(1)

输入:
[1, -2, 3, 5, -2, 6, -1]
返回值:
12

方法一:空间复杂度为O(n)

public class Solution {
    /**
     * 
     * 状态转移方程如下
     * dp[0] = arr[0];
     * dp[i - 1] > 0 ==> dp[i] = dp[i - 1] + arr[i];
     * dp[i - 1] <= 0 ==> dp[i] = arr[i];
     */
    public int maxsumofSubarray (int[] arr) {
        if(arr.length == 0) {
            return 0;
        }
        if(arr.length == 1) {
            return arr[0];
        }
        int[] dp = new int[arr.length];
        dp[0] = arr[0];
        int max = dp[0];
        for(int i = 1; i < arr.length; i++) {
            if(dp[i - 1] > 0) {
                dp[i] = dp[i - 1] + arr[i];
            } else {
                dp[i] = arr[i];
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

方法二:空间复杂度为O(1)

public class Solution {
    /**
     * 状态转移方程如下
     * dp[0] = arr[0];
     * dp[i - 1]  > 0 ==> dp[i] = dp[i - 1] + arr[i];
     * dp[i - 1] <= 0 ==> dp[i] = arr[i];
     */
    public int maxsumofSubarray (int[] arr) {
        if(arr.length == 0) {
            return 0;
        }
        if(arr.length == 1) {
            return arr[0];
        }
        int pre = arr[0];
        int max = pre;
        for(int i = 1; i < arr.length; i++) {
            if(pre > 0) {
                pre = pre + arr[i];
            } else {
                pre = arr[i];
            }
            max = Math.max(max, pre);
        }
        return max;
    }
}

链表问题

删除有序链表中重复的元素-II

给出一个升序排序的链表,删除链表中的所有重复出现的元素,只保留原链表中只出现一次的元素。
例如:
给出的链表为1→2→3→3→4→4→5, 返回1→2→5.
给出的链表为1→1→1→2→3, 返回2→3.

方法一:空间复杂度O(n)

过程:

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        // 设置一个伪节点,主要是为了方便处理
        ListNode result = new ListNode(0);
        ListNode resultTemp = result;

        ListNode h = head;

        while(h != null) {
            ListNode cur = h;
            ListNode node = cur.next;
            boolean flag = false;
            // 这里是为了找到当前节点是否存在重复元素
            while(node != null) {
                if(node.val == cur.val) {
                    flag = true;
                    // 这里主要是过滤掉重复的
                    node = node.next;
                } else {
                    break;
                }
            }
            if(!flag) {
                // 不存在重复元素,则新建一个元素
                resultTemp.next = new ListNode(cur.val);
                resultTemp = resultTemp.next;
            }
              // h指向node: 因为此时的node是指向一个与cur不相等的节点, 如果h直接指向node就行了
            h = node;
        }
        return result.next;
    }
}

方法二:空间复杂度O(1),直接在原链表上面操作

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        // 设置一个伪节点,主要是为了方便处理
        ListNode result = new ListNode(0);
        result.next = head;
        // 前指针
        ListNode pre = result;
        // 当前指针
        ListNode cur = head;
        // 每次都判断当前指针的下一个指针是否与当前指针的值相同
        // 如果相同, 则找到第一个与当前指针不相同的节点node, 然后将前指针的next指针指向node
        // 如果不相同, 则前指针和当前指针都指向下一个
        // 1 2 3 3 4 4 5
        while(cur != null) {
            if(cur.next != null && cur.next.val == cur.val) {
                // 存在相同值
                ListNode node = cur.next;
                // 这里主要是让node指向一个不与cur相同的节点
                while(node != null && node.val == cur.val) {
                    node = node.next;
                }
                // 直接将 pre.next 指向 node, 达到了删除相同元素的目的
                pre.next = node;
                cur = node;
            } else {
                // 不存在相同值, 都指向下一个指针
                pre = pre.next;
                cur = cur.next;
            }
        }
        return result.next;
    }
}

字符串问题

最长回文子串

对于一个字符串,请设计一个高效算法,计算其中最长回文子串的长度。

给定字符串A以及它的长度n,请返回最长回文子串的长度。

输入:"abc1234321ab",12
返回:7

方法一: 暴力法

public class Solution {
    public int getLongestPalindrome(String A, int n) {
        // write code here
        if(n <= 1) {
            return n;
        }
        int max = 1;
        char[] chars = A.toCharArray();
        // 两个for循环遍历所有可能的子串
        for(int i = 0; i < n; i++) {
            for(int j = i + 1; j < n; j++) {
                // 如果当前字符串长度大于 max 并且是回文
                if(j - i + 1 > max && isHuiwen(chars, i, j)) {
                    max = j - i + 1;
                }
            }
        }
        return max;
    }

    public boolean isHuiwen(char[] chars, int i, int j) {
        while(i < j) {
            if(chars[i] != chars[j]) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}

方法二: 动态规划

dp[left][right]代表[left, right]之间是否为回文
s.charAt(left) == s.charAt(right)
如果 right - left <= 2, dp[left][right] = true; 则字符长度为2或者3, 类似于这种: "aa""aba"
如果 right - left > 2, dp[left][right] = dp[left+1][right-1];
public class Solution {
    public int getLongestPalindrome(String A, int n) {
        if(n < 2) {
            return A.length();
        }
        boolean[][] dp = new boolean[n][n];
        int max = 1;
        char[] chars = A.toCharArray();
        for(int right = 1; right < n; right++) {
            for(int left = 0; left < right; left++) {
                // 如果不相同, 说明[left, right]肯定不是回文
                if(chars[left] != chars[right]) {
                    continue;
                }
                if(right - left <= 2){
                    // aa 或者 aba
                    dp[left][right] = true;
                } else {
                    dp[left][right] = dp[left + 1][right - 1];
                }
                if(dp[left][right]) {
                    max = Math.max(max, right - left + 1);
                }
            }
        }
        return max;
    }
}

二叉树

对称二叉树

public class Main {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(2);

        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);

        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(3);
        //
//        root.left.left.left = new Node(7);
//        root.left.left.right = new Node(8);
//        root.left.right.left = new Node(9);
//        root.left.right.right = new Node(10);

        System.out.println(isSymmetric2(root));;
    }
    /**
     * 递归法
     * 判断是否为对称二叉树
     * https://leetcode-cn.com/problems/symmetric-tree/
     */
    public static boolean isSymmetric(TreeNode root){
        if (root == null) {
            return true;
        }
        return compare(root.left, root.right);
    }
    /**
     *       1
     *    /     \
     *   2           2
     * /   \    /    \
     * 3    4    4    3
     *
     * 比较左子树跟右子树
     * 1. 空判断
     * 2.
     *  left.left  == right.right 外侧比较
     *  left.right == right.left  内测比较
     * @param left
     * @param right
     * @return
     */
    public static boolean compare(TreeNode left, TreeNode right){
        if (left == null && right == null) {
            return true;
        } else if (left == null && right != null) {
            return false;
        } else if (left != null && right == null) {
            return false;
        } else if (left.value != right.value) {
            return false;
        }
        // 比较外侧
        boolean outSide = compare(left.left, right.right);
        // 比较内侧
        boolean inSide = compare(left.right, right.left);
        return outSide && inSide;
    }

    /**
     * 非递归法
     * 判断是否为对称二叉树
     * https://leetcode-cn.com/problems/symmetric-tree/
     */
    public static boolean isSymmetric2(TreeNode root){
        if (root == null) {
            return true;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root.left);
        stack.push(root.right);
        while (!stack.isEmpty()) {
            // 出栈-拿出右树
            TreeNode right = stack.pop();
            // 出栈-拿出左树
            TreeNode left = stack.pop();
            if (right == null && left == null) {
                continue;
            } else if (right == null && left != null) {
                return false;
            } else if (right != null && left == null) {
                return false;
            } else if (right.value != left.value) {
                return false;
            }
            // 外侧
            stack.push(left.left);
            stack.push(right.right);
            // 内侧
            stack.push(left.right);
            stack.push(right.left);
        }
        return true;
    }
}

二叉树的最大深度

/**
     * 二叉树的最大深度
     * https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
     */
    public static int getMaxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = getMaxDepth(root.left);
        int right = getMaxDepth(root.right);
        return Math.max(left, right) + 1;
    }

二叉树的最小深度

/**
     * 111. 二叉树的最小深度
     * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
     * https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
     */
    public static int getMinDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = getMaxDepth(root.left);
        int right = getMaxDepth(root.right);
        // 左节点为空
        if (root.left == null && root.right != null) {
            return 1 + right;
        }
        // 右节点为空
        if (root.left != null && root.right == null) {
            return 1 + left;
        }
        return Math.min(left, right) + 1;
    }

计算二叉树的节点个数

/**
     * 计算二叉树的节点个数
     * 递归
     */
    public static int getNodeCount(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 计算左树节点个数
        int leftCount = getNodeCount(root.left);
        // 计算右树节点个数
        int rightCount = getNodeCount(root.right);
        // 加1是因为加上当前节点
        return leftCount + rightCount + 1;
    }
    /**
     * 计算二叉树的节点个数
     * 非递归-使用层次遍历
     */
    public static int getNodeCount2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        LinkedList<TreeNode> list = new LinkedList();
        list.addLast(root);
        int count = 0;
        while (!list.isEmpty()) {
            int size = list.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = list.removeFirst();
                if (node.left != null) {
                    list.addLast(node.left);
                }
                if (node.right != null) {
                    list.addLast(node.right);
                }
                count++;
            }
        }
        return count;
    }
本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!