三道简单算法题——java 解答

发布时间:2023年12月18日

三个谷歌算法题的Java解答,并配以图解说明。

1. 反转链表

题目描述:

给定一个单链表的头节点 head,编写一个函数来反转链表,并返回新的头节点。

Java 解答:
public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}
图解:
  1. 初始化两个指针:prev(初始为 null)和 curr(指向头节点 head)。
  2. 遍历链表,每次迭代中,将 currnext 指针指向 prev
  3. 更新 prevcurr,直到 currnull
  4. 返回新的头节点,即 prev

2. 二叉树的最大深度

题目描述:

给定一个二叉树,找出其最大深度。

Java 解答:
public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    } else {
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return Math.max(leftDepth, rightDepth) + 1;
    }
}
图解:
  1. 如果根节点为 null,返回深度 0
  2. 递归计算左子树和右子树的最大深度。
  3. 返回左右子树深度的最大值加 1(当前节点的深度)。

3. 有效的括号

题目描述:

给定一个只包括 '('')''{''}''['']' 的字符串,判断字符串是否有效。

Java 解答:
public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) return false;
            char top = stack.pop();
            if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}
图解:
  1. 使用栈来存储开括号。
  2. 遍历字符串中的每个字符:
    • 如果是开括号,压入栈中。
    • 如果是闭括号,检查栈顶元素是否与之匹配。如果不匹配或栈为空,则返回 false
  3. 遍历完成后,如果栈为空,则字符串有效,否则无效。

在这里插入图片描述

文章来源:https://blog.csdn.net/weixin_45594172/article/details/135059645
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。