21xrx.com
2024-11-08 20:22:40 Friday
登录
文章检索 我的文章 写文章
Java面试必备技能之数据结构与算法
2023-06-14 23:41:08 深夜i     --     --
Java 面试 数据结构 算法 代码实现

在Java开发领域，数据结构和算法是面试中最重要的一部分。很多公司将其作为考核员工技能的关键指标。因此，为了在面试中有更好的表现，必须掌握基本的数据结构和算法知识，同时也要学会如何应用它们来解决实际问题。

下面是几个常见的数据结构和算法问题。我们将以Java代码的形式演示如何实现它们。在掌握这些问题之后，相信你在Java开发领域的面试表现将更加出色。

1. 树的深度优先遍历

public void DFS(TreeNode root) { 

  if(root == null)  

   return; 

  System.out.println(root.val); 

  DFS(root.left); 

  DFS(root.right); 

}

2. 链表的快速排序

public static ListNode quickSortList(ListNode head) { 

  if(head == null || head.next == null)  

   return head; 

  ListNode low = new ListNode(-1), high = new ListNode(-1), mid = head; 

  head = head.next; 

  while(head != null) { 

   ListNode next = head.next; 

   if(head.val < mid.val)  

    head.next = low.next; 

    low.next = head; 

   else if(head.val > mid.val)  

    head.next = high.next; 

    high.next = head; 

   else  

    head.next = mid.next; 

    mid.next = head; 

   head = next; 

  } 

  low.next = quickSortList(low.next); 

  high.next = quickSortList(high.next); 

  mid.next = quickSortList(mid.next); 

  ListNode res = low.next; 

  while(res.next != null)  

   res = res.next; 

  res.next = mid.next; 

  while(mid.next != null)  

   mid = mid.next; 

  mid.next = high.next; 

  return low.next; 

}

3. 求两个有序数组的中位数

public static double findMedianSortedArrays(int[] nums1, int[] nums2) { 

  int n = nums1.length, m = nums2.length; 

  int l = (n + m + 1) / 2, r = (n + m + 2) / 2; 

  return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, l) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, r)) * 0.5; 

} 

private static int getKth(int[] nums1, int l1, int r1, int[] nums2, int l2, int r2, int k) { 

  int len1 = r1 - l1 + 1; 

  int len2 = r2 - l2 + 1; 

  if (len1 > len2) { 

   return getKth(nums2, l2, r2, nums1, l1, r1, k); 

  } 

  if (len1 == 0) { 

   return nums2[l2 + k - 1]; 

  } 

  if (k == 1) { 

   return Math.min(nums1[l1], nums2[l2]); 

  } 

  int i = l1 + Math.min(len1, k / 2) - 1; 

  int j = l2 + Math.min(len2, k / 2) - 1; 

  if (nums1[i] > nums2[j]) { 

   return getKth(nums1, l1, r1, nums2, j + 1, r2, k - (j - l2 + 1)); 

  } else { 

   return getKth(nums1, i + 1, r1, nums2, l2, r2, k - (i - l1 + 1)); 

  } 

}

以上是三个常见的数据结构和算法问题，我们在Java中实现了它们，并给出了解题思路。在面试中，面试官往往会对候选人的解题思路和代码实现进行细致的评估。因此，在学习数据结构和算法时，需要注重理解其本质，尝试用自己的话解释清楚每个问题的解法，这样不仅有利于记忆，还有利于在面试中更好地表现自己。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复