【CodeTop x LeetCode】Page 3 : 41-60面试高频算法题题解

2021-11-03T15:50:00
更多答案也可以关注我的GitHub算法仓库——Algorithm

(大家可以根据我每道题打的星来衡量这道题的难易,星越少越难)

[scode type="green"]所有代码都是在力扣上提交通过的,保证代码的正确无误[/scode]

基础数据结构:

class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode() {}
       TreeNode(int val) { this.val = val; }
       TreeNode(int val, TreeNode left, TreeNode right) {
           this.val = val;
           this.left = left;
           this.right = right;
       }
    }

8.字符串转换整数 (atoi)

自动机
我的代码就是根据题意一步一步判断的,所以非常臃肿,但是根据官方给的自动机解法暂时还没看懂

public int myAtoi(String s) {
    int j = 0;
    for (; j < s.length();) {
        if (s.charAt(j) == ' ') {
            j++;
        }else {
            break;
        }
    }
    s = s.substring(j);
    if (s.length() <= 0) {
        return 0;
    }
    boolean isNegative = false;
    int i = 0, res = 0;
    if (s.charAt(0) == '-' || s.charAt(0) == '+') {
        if (s.charAt(0) == '-') {
            isNegative = true;
        }
        i = 1;
    }
    for (; i < s.length();) {
        if (s.charAt(i) == '0') {
            i++;
        }else {
            break;
        }
    }
    StringBuilder sb = new StringBuilder("");
    for (; i < s.length(); i++) {
        if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
            sb.append(s.charAt(i));
        }else {
            break;
        }
    }
    String str = sb.toString();
    if (str.length() != 0) {
        if (str.length() > 10) {
            if (isNegative) {
                return Integer.MIN_VALUE;
            }
            return Integer.MAX_VALUE;
        }else {
            long l = Long.valueOf(str);
            if (l > Integer.MAX_VALUE) {
                if (isNegative) {
                    return Integer.MIN_VALUE;
                }
                return Integer.MAX_VALUE;
            }else {
                if (isNegative) {
                    return -1*Integer.valueOf(str);
                }
                return Integer.valueOf(str);
            }
        }
    }
    return res;
}

2.两数相加

话说真快被链表题搞懵了呀,这个我也是按照纯模拟加法的思路写的,先去判断哪个链表长,然后哦就把短的依次加到长的上面,还要注意进位问题。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode cul1 = l1;
    ListNode cul2 = l2;
    int l1_len = 0;
    int l2_len = 0;
    while (cul1 != null || cul2 != null) {
        if (cul1 != null) {
            l1_len++;
            cul1 = cul1.next;
        }
        if (cul2 != null) {
            l2_len++;
            cul2 = cul2.next;
        }
    }
    ListNode lon = l1;
    ListNode shor = l2;
    if (l2_len > l1_len) {
        lon = l2;
        shor = l1;
    }
    int yu = 0;
    while (shor != null) {
        lon.val += (shor.val+yu);
        if (lon.val >= 10) {
            yu = 1;
            lon.val -=10;
        }else {
            yu = 0;
        }
        shor = shor.next;
        if (lon.next == null && yu == 1) {
            lon.next = new ListNode(0);
        }
        lon = lon.next;
    }
    while (yu == 1) {
        lon.val += 1;
        if (lon.val >= 10) {
            yu = 1;
            lon.val -= 10;
            if (lon.next == null) {
                lon.next = new ListNode(0);
            }
            lon = lon.next;
        }else {
            yu = 0;
        }
    }
    if (l2_len > l1_len) {
        return l2;
    }
    return l1;
}

82.删除排序链表中的重复元素 II

判断当前节点的下一个节点与下下一个节点的值,相等则不断调整当前节点的next,不相等则向后移动;这里引入头节点方便对首元节点的操作。

public ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode fake = new ListNode();
    fake.next = head;
    ListNode cur = fake;
    while (cur.next != null && cur.next.next != null) {
        if (cur.next.val == cur.next.next.val) {
            int x = cur.next.val;
            while (cur.next != null && cur.next.val == x) {
                cur.next = cur.next.next;
            }
        }else {
            cur = cur.next;
        }
    }
    return fake.next;
}

144.二叉树的前序遍历

class Solution {
    List<Integer> list = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        dfs(root);
        return list;
    }
    public void dfs (TreeNode root) {
        if (root != null) {
            list.add(root.val);
            dfs(root.left);
            dfs(root.right);
        }
    }
}

148.排序链表

这道题思路是归并,但是有两个归并思路:

  • 递归着归并,先找中点(使用快慢指针),一次分一半,递归,一次分一半,递归....然后两两合并并返回
  • 先设归并长度为1,第一波归并完再把归并长度乘2,再归并,以此类推

(本体采用自顶向下的递归方式)

class Solution {

    public ListNode sortList(ListNode head) {
        return sort(head, null);
    }

    private ListNode sort(ListNode start, ListNode end) {
        if (start == end) {
            return start;
        }
        ListNode fast = start, slow = start;
        while (fast != end && fast.next != end) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode l2 = sort(slow.next, end);
        slow.next = null;
        ListNode l1 = sort(start, slow);
        return mergeTwoLists(l1, l2);
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return l1 == null ? l2 : l1;
        }
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }else {
            l2.next = mergeTwoLists(l2.next, l1);
            return l2;
        }
    }
}

31.下一个排列

  • 倒着遍历第一次找到第一个值变小的,记录坐标为i
  • 倒着遍历第二次找到刚好比nums[i]大的坐标j
  • 交换i,j并翻转i+1到结尾的数字
class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i+1]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            while (j > i && nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j);
        }
        for (int x = i+1, y = nums.length-1; x < y;) {
            swap(nums, x, y);
            x++;
            y--;
        }
    }

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

76.最小覆盖子串

思路:滑动窗口(左右指针l,r),用两个常量数组判断当前字符串是否包含模式串('a'~'Z'可以用长度60存下)

  • 不包含,r++;包含,l++,并更新结果
    (这道题虽然是困难,但是思路还是比较容易懂的)
public String minWindow(String s, String t) {
    String res = "";
    int[] sarr = new int[60];
    int[] tarr = new int[60];
    for (int i = 0; i < t.length(); i++) {
        tarr[t.charAt(i) - 'A']++;
    }
    int l = 0, r = 0;
    while (l <= r) {
        boolean isHave = true;
        for (int j = 0; j < 60; j++) {
            if (sarr[j] < tarr[j]) {
                isHave = false;
                break;
            }
        }
        if (isHave) {
            String temp = s.substring(l, r);
            if (res.length() == 0) {
                res = temp;
            }else {
                res = temp.length() < res.length() ? temp:res;
            }
            sarr[s.charAt(l) - 'A']--;
            l++;
        }else if (r < s.length()) {
            sarr[s.charAt(r) - 'A']++;
            r++;
        }else {
            break;
        }
    }
    return res;
}

151.翻转字符串里的单词

常规字符串算法题,比较简单,借助java的trim()split()函数,使用StringBuilder快速追加

public String reverseWords(String s) {
    StringBuilder sb = new StringBuilder("");
    s = s.trim();
    String[] arr = s.split(" ");
    for (int i = arr.length - 1; i > 0; i--) {
        if (arr[i].length() != 0) {
            sb.append(arr[i] + " ");
        }
    }
    sb.append(arr[0]);
    return sb.toString();
}

72. 编辑距离

这里提供了两种方法:自底向上的递归和自顶向下的动规,但是递归会超时,动规就是记录了子问题的结果避免重复计算。

  • dp[i][j]的意思是word1.subString(0, i)变为word2.subString(0, j)所需的步数
  • 根据题目中给的三种操作我们可以推出核心的动态转移方程为:
    dp[i+1][j+1] = 1 + Math.min(Math.min(dp[i][j+1], dp[i+1][j]), dp[i][j]);
    这里由于下标从1开始到length,避免数组越界所以使下一个用当前的值
    这是一道经典的动态规划题目,值得反复练习
class Solution {
    public int minDistance(String word1, String word2) {
        int l1 = word1.length();
        int l2 = word2.length();
        int[][] dp = new int[l1 + 1][l2 + 1];
        for (int i = 0; i < l1 + 1; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i < l2 + 1; i++) {
            dp[0][i] = i;
        }
        for (int i = 0; i < l1; i++) {
            for (int j = 0; j < l2; j++) {
                if (word1.charAt(i) == word2.charAt(j)) {
                    dp[i+1][j+1] = dp[i][j]; //一样则无需多余操作步数
                }else {
                    dp[i+1][j+1] = 1 + Math.min(Math.min(dp[i][j+1], dp[i+1][j]), dp[i][j]);
                }
            }
        }
        return dp[l1][l2];
    }
    //递归(超时)
    public int minDistance_recursion(String word1, String word2) {
        if (word1.length() == 0 || word2.length() == 0) {
            return Math.max(word1.length(), word2.length());
        }
        if (word1.charAt(word1.length()-1) == word2.charAt(word2.length()-1)) {
            return minDistance_recursion(word1.substring(0, word1.length()-1),
                    word2.substring(0, word2.length()-1));
        }
        return 1 + Math.min(Math.min(minDistance_recursion(word1, word2.substring(0, word2.length()-1)),
                minDistance_recursion(word1.substring(0, word1.length()-1), word2)),
                minDistance_recursion(word1.substring(0, word1.length()-1),word2.substring(0, word2.length()-1)));
    }
}

4.寻找两个正序数组的中位数

这道题目有两个思路:

  • 合并两个有序数组,再直接输出中位数,时间复杂度O(m+n),空间复杂度O(m+n)
  • 划分数组+推导,时间复杂度O(logmin(m,n))),空间复杂度O(1),但是这个暂时还没搞懂
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int l1 = nums1.length;
        int l2 = nums2.length;
        int l3 = l1+l2;
        int[] arr = new int[l3];
        for (int i = 0; i < l1; i++) {
            arr[i] = nums1[i];
        }
        merge(arr, l1, nums2, l2);
        if (l3 % 2 == 1) {
            return arr[l3/2];
        }
        return ((float)(arr[l3/2-1]+arr[l3/2]))/2;
    }

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int n1 = m -1;
        int n2 = n -1;
        while (n2 >= 0) {
            if (n1 >= 0 && nums1[n1] >= nums2[n2]) {
                nums1[n1+n2+1] = nums1[n1];
                n1--;
            }else {
                nums1[n1+n2+1] = nums2[n2];
                n2--;
            }
        }
    }
}

129.求根节点到叶节点数字之和

深度优先搜索,使用StringBuilder记录路径上节点的值,再判断左右孩子为空时,将其转换成Integer。递归返回前去除 StringBuilder的最后一个字符

class Solution {
    private StringBuilder sb = new StringBuilder();
    private int res = 0;
    public int sumNumbers(TreeNode root) {
        if (root != null) {
            sb.append(root.val);
            if (root.left == null && root.right == null) {
                res += Integer.valueOf(sb.toString());
            }else {
                sumNumbers(root.left);
                sumNumbers(root.right);
            }
            sb.deleteCharAt(sb.length()-1);
        }
        return res;
    }
}

104.二叉树的最大深度

二叉树必需掌握的题,数据结构教材上的原题

public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    } else {
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

105.从前序与中序遍历序列构造二叉树

前序遍历和中序遍历的概念这里就不说了,其实推的时候很容易发现是一个递归的过程,有关于递归下标的计算如图:

class Solution {

    private HashMap<Integer, Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return buildTree(preorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }

    public TreeNode buildTree(int[] preorder, int preLeft, int preRight, int inLeft, int inRight) {
        if (preLeft > preRight || inLeft > inRight) {
            return null;
        }
        int val = preorder[preLeft];
        TreeNode node = new TreeNode(val);
        int pIndex = map.get(val);
        node.left = buildTree(preorder, preLeft+1, pIndex - inLeft + preLeft, inLeft, pIndex - 1);
        node.right = buildTree(preorder, pIndex - inLeft + preLeft + 1, preRight, pIndex + 1, inRight);
        return node;
    }
}

239.滑动窗口最大值

这道题一开始很容易想到使用优先队列来解决,但是写完检测却发现超时了,看题解是使用的单调队列(递增、递减的队列)

  • 定义一个双端队列,存储数组下标,那么队首的值就是nums[queue.peekFirst()],存下标主要就是为了方便判断队列队首元素是否已经在滑动窗口外:queue.peekFirst() < left,队首元素对应数组值最大,依次递减。
  • 定义右指针right从 0 到nums.length()-1,就很容易计算窗口的左指针leftright - k + 1
  • 如果一个元素入队(入队都是从队尾入),则说明它在窗口内,那么队列内比该值小的则永远不会加入到最终答案res内,直到该元素出窗口,所以我们把队列内比该元素小的值出队。保证队列的一个单调递减。
  • 最后一个right + 1 >= k是因为这时最初的窗口才刚刚形成,满足长度为k,才能添加。
    class Solution {
        //单调队列
        public int[] maxSlidingWindow(int[] nums, int k) {
            int[] res = new int[nums.length-k+1];
            ArrayDeque<Integer> queue = new ArrayDeque<>();
            for (int right = 0; right < nums.length; right++) {
                while (queue.size() > 0 && nums[right] > nums[queue.peekLast()]) {
                    queue.pollLast();
                }
                queue.offerLast(right);
                int left = right - k + 1;
                if (left > queue.peekFirst()) {
                    queue.pollFirst();
                }
                if (right + 1 >= k) {
                    res[left] = nums[queue.peekFirst()];
                }
            }
            return res;
        }
        //优先队列(超时)
        public int[] maxSlidingWindow_PriorityQueue(int[] nums, int k) {
            PriorityQueue<Integer> queue = new PriorityQueue<>((a,b)-> b-a);
            int[] res = new int[nums.length-k+1];
            for (int i = 0; i < k; i++) {
                queue.offer(nums[i]);
            }
            res[0] = queue.peek();
            for (int i = k, j = 0; i < nums.length; i++,j++) {
                queue.offer(nums[i]);
                queue.remove(nums[j]);
                res[j+1] = queue.peek();
            }
            return res;
        }
    }

93.复原 IP 地址

一个字符串,分成四部分,我就懒省事直接暴力dfs了,枚举出来所有分割情况再做判断

class Solution {
    private List<String> res = new ArrayList<>();
    private String param;
    public List<String> restoreIpAddresses(String s) {
        param = s;
        dfs("", 0, 1);
        return res;
    }
    public void dfs (String s, int index, int count) {
        if (count >= 4) {
            if (judge(index, param.length())) {
                res.add(s + param.substring(index));
            }
        }else {
            for (int i = 1; i <= 3; i++) {
                if ((index + i) <= param.length() && judge(index, index+i)) {
                    dfs(s+param.substring(index, index+i)+".", index+i, count + 1);
                }
            }
        }
    }
    public boolean judge (int start, int end) {
        String temp = param.substring(start, end);
        if (temp.length() <= 3 && temp.length() != 0) {
            int val = Integer.valueOf(temp);
            if (String.valueOf(val).length() == temp.length() && val <= 255) {
                return true;
            }
        }
        return false;
    }
}

113.路径总和 II

这道题和前面的 129.求根节点到叶节点数字之和 基本一致,都是dfs+回溯即可

class Solution {
    private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> cur = new ArrayList<>();
    private int sum = 0;
    private int target = 0;

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        target = targetSum;
        dfs(root);
        return res;
    }

    public void dfs (TreeNode root) {
        if (root != null) {
            sum += root.val;
            cur.add(root.val);
            if (root.left == null && root.right == null) {
                if (sum == target) {
                    List<Integer> temp = new ArrayList<>();
                    for (int i = 0; i < cur.size(); i++) {
                        temp.add(cur.get(i));
                    }
                    res.add(temp);
                }
            }else {
                dfs(root.left);
                dfs(root.right);
            }
            sum -= root.val;
            cur.remove(cur.size()-1);
        }
    }
}

110.平衡二叉树

平衡二叉树的定义本身就是一个递归的定义:左右子树深度只差的绝对值不超过1,并且左右子树也是平衡的

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root != null) {
            return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
        return true;
    }

    public int height (TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            return Math.max(height(root.left), height(root.right)) + 1;
        }
    }
}

1143.最长公共子序列

典型的二维动规,dp[i][j]代表text[0...i]text[0...j]的最长公共子序列,所以可以推导出动态转移方程为:


其实到这里我们可以发现有关于两个字符串之间的动态规划题目,基本都是一个二维数组dp,两个for循环里面一个状态转移方程,更新数组,最后返回数组的最后一个值,这就是动规模板。

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length()+1][text2.length()+1];
        for (int i = 1; i <= text1.length(); i++) {
            for (int j = 1; j <= text2.length(); j++) {
                if (text1.charAt(i-1) == text2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1]+1;
                }else {
                    dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }
        return dp[text1.length()][text2.length()];
    }
}

470.用 Rand7() 实现 Rand10()

古典概型

  • 第一次rand7限定[1,2],判断奇偶性,概率是1/2,其实first的作用就是生成概率为1/2的奇偶。
    (我们还可以通过限定[1,3],再取模3进行概率为1/3的操作)
  • 第二次rand7限定[1,5],概率是1/5,加上5为[6,10],概率也是1/5
  • 二者结合可以得出10种概率相同的结果

借助这个思路我们也可以构造出其他的

/**
 * The rand7() API is already defined in the parent class SolBase.
 * public int rand7();
 * @return a random integer in the range 1 to 7
 */
class Solution extends SolBase {
    public int rand10() {
        int first,second;
        while ((first = rand7()) > 2);
        while ((second = rand7()) > 5);
        return first%2 == 0 ? second : second+5;
    }
}

543.二叉树的直径

这道题跟计算二叉树的深度还不太一样,是求任意两个节点的最大路径,可以不过根节点。递归的同时对结果更新要注意:

class Solution {
    private int res = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        height(root);
        return res-1;
    }
    public int height (TreeNode root) {
        if (root != null) {
            int l = height(root.left);
            int r = height(root.right);
            res = Math.max(res, l+r+1);
            return Math.max(l,r)+1;
        }
        return 0;
    }
}
当前页面是本站的「Baidu MIP」版。发表评论请点击:完整版 »