最新消息:热烈庆祝IT小记上线!

面试笔试杂项积累-leetcode 236-240

236.236-Lowest Common Ancestor of a Binary Tree-Difficulty: Medium

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

思路

235题的加强版,这回是一个普通的二叉树而不是二叉搜索树了

使用两个栈来递归遍历,一个栈存根到一个目标节点的路径,一个存另一个

存完了之后就找最近的两个栈都包含的节点就行了

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    TreeNode fin = null;
        Stack<TreeNode> ps = new Stack<TreeNode>();
        Stack<TreeNode> qs = new Stack<TreeNode>();
        if (FindPath(root, p, ps) && FindPath(root, q, qs))
        {
            TreeNode temp;// = qs.Pop();
            while (qs.Count > 0)
            {
                temp = qs.Pop();
                if (ps.Contains(temp))
                    fin = temp;
            }
        }
        return fin;
    }
    bool FindPath(TreeNode root, TreeNode target, Stack<TreeNode> stack)
    {
        if (root == null)
            return false;
        if (root == target)
        {
            stack.Push(root);
            return true;
        }
        if (FindPath(root.left, target, stack) || FindPath(root.right, target, stack))
        {
            stack.Push(root);
            return true;
        }
        return false;
    }
}

237.237-Delete Node in a Linked List-Difficulty: Easy

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

思路

删除链表中的指定节点

很简单,存下next的值,.next=.next.next。再把当前值覆盖为存下的next的值即可

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void DeleteNode(ListNode node) {
        if (node == null)
            return;
        int temp = node.next.val;
        node.next = node.next.next;
        node.val = temp;
    }
}

238.238-Product of Array Except Self-Difficulty: Medium

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

思路

求出本身之外的数组之积

如果每个都重头遍历乘积的话太耗费时间了

先遍历一遍求出所有的积,再除当前值即可

要注意0存在的可能性,

用一个list存下0存在的位置,如果0的数目大于等于2则所有结果都是0,直接返回。如果只有一个是0,则楚辞之外其他位置都是0,把哪个位置赋上所有乘积即可


public class Solution {
    public int[] ProductExceptSelf(int[] nums) {//求出本身之外的数组之积
        IList<int> zero = new List<int>();
        int[] fin = new int[nums.Length];
        int all = 1;
        for (int i = 0; i < nums.Length; i++)
        {
            if (nums[i] == 0)
            {
                zero.Add(i);
                if (zero.Count >= 2)
                    return fin;
                 continue;
            }
            all *= nums[i];
        }
        if (zero.Count <= 0)
        {
            for (int i = 0; i < nums.Length; i++)
                fin[i] = all / nums[i];
        }
        else
            fin[zero[0]] = all;
        return fin;
    }
}

240.240-Search a 2D Matrix II-Difficulty: Medium

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted in ascending from left to right.
  • Integers in each column are sorted in ascending from top to bottom.

For example,

Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.

Given target = 20, return false.

思路

与之前的74题不同的是,每行大小并不是全都小于下一行大小,之前的判断每行首个字母就能定下在哪一行,这次不行了。现在这种情况,需要所有行都比对一下,就可以了

public class Solution {
    public bool SearchMatrix(int[,] matrix, int target) {
                 int row = matrix.GetLength(0);
        int col = matrix.GetLength(1);
        for (int i = 0; i < row; i++)
        {

            if (matrix[i, 0] < target && matrix[i, col - 1] > target)
            {
                for (int j = 1; j < col - 1; j++)
                {
                    if (matrix[i, j] == target)
                        return true;
                    else if (matrix[i, j] > target)
                        break;
                }
            }
            else if (matrix[i, 0] == target || matrix[i, col - 1] == target)
                return true;
        }
        return false;
    }
}







猜您喜欢

备案号:苏ICP备12016861号-4