Java面试题集

1、表示数值的字符串

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100"、“5e2”、"-123"、“3.1416”、"-1E-16"、“0123"都表示数值，但"12e”、“1a3.14”、“1.2.3”、"±5"及"12e+5.4"都不是。

class Solution { public boolean isNumber(String s) { int i = 0, j = s.length() - 1; while (i <= j && s.charAt(i) == ' ') i++; while (i <= j && s.charAt(j) == ' ') j--; if (i > j) return false; s = s.substring(i, j+1); if (s.charAt(0) == '+' || s.charAt(0) == '-') s = s.substring(1); if (s.length() == 0 || (s.charAt(0) == '.' && s.length() == 1)) return false; // 去掉+、-、. int dot = 0, e = 0; //记录.和e的个数 for (int index = 0; index < s.length(); index++) { if (s.charAt(index) >= '0' && s.charAt(index) <= '9') {} else if (s.charAt(index) == '.') { dot++; if (dot > 1 || e != 0) { //多于1个.或者.前面存在e，因为e后面不允许有小数 return false; } } else if (s.charAt(index) == 'e' || s.charAt(index) == 'E') { e++; if (index == 0 || index + 1 == s.length() || e > 1 || (s.charAt(index-1) == '.' && index == 1)) { return false; } if (s.charAt(index+1) == '+' || s.charAt(index+1) == '-') { if (index+2 == s.length()) return false; index++; } } else { return false; } } return true; } } 

2、调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

class Solution { public int[] exchange(int[] nums) { //类似于快速排序中交换的策略 int i = 0, j = nums.length - 1; while (i < j) { while (i < j && nums[i] % 2 == 1) i++; while (i < j && nums[j] % 2 == 0) j--; if (i < j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } } return nums; } } 

3、链表中倒数第K个节点

输入一个链表，输出该链表中倒数第k个节点。

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5. 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */ class Solution { public ListNode getKthFromEnd(ListNode head, int k) { int n = 0; for (ListNode cur = head; cur != null; cur = cur.next) { n++; } if (k > n) return null; ListNode cur = head; //倒数第k个节点，为正数第n-k+1个节点，所以我们只要移动n-k次 for (int i = 0; i < n - k; i++) { cur = cur.next; } return cur; } } 

4、反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */ class Solution { public ListNode reverseList(ListNode head) { //设置一个前驱节点 ListNode pre = null, cur = head; while (cur != null) { ListNode next = cur.next; cur.next = pre; pre = cur; cur = next; } return pre; } } 

5、合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */ class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { //归并算法 ListNode dummy = new ListNode(-1); ListNode p = l1, q = l2, cur = dummy; while (p != null && q != null) { if (p.val < q.val) { cur.next = p; p = p.next; } else { cur.next = q; q = q.next; } cur = cur.next; } cur.next = (p == null) ? q : p; return dummy.next; } } 

6、树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */ class Solution { public boolean isSubStructure(TreeNode p, TreeNode q) { //先序遍历 ※  (这道题其实是字符串的匹配) if (p == null || q == null) return false; if (isPart(p, q)) return true; return isSubStructure(p.left, q) || isSubStructure(p.right, q); } public boolean isPart(TreeNode p, TreeNode q) { if (q == null) return true; if (p == null || p.val != q.val) return false; return isPart(p.left, q.left) && isPart(p.right, q.right); } } 

7、二叉树的镜像

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */ class Solution { public TreeNode mirrorTree(TreeNode root) { if (root == null) return root; mirrorTree(root.left); mirrorTree(root.right); TreeNode tmp = root.left; root.left = root.right; root.right = tmp; return root; } } 

8、对称的二叉树

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */ class Solution { public boolean isSymmetric(TreeNode root) { if (root == null) return true; return dfs(root.left, root.right); } public boolean dfs(TreeNode p, TreeNode q) { if (p == null || q == null) return p == null && q == null; if (p.val != q.val) return false; return dfs(p.left, q.right) && dfs(q.left, p.right); } } 

9、顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5] 

class Solution { public int[] spiralOrder(int[][] matrix) { int m = matrix.length; if(m == 0) return new int[]{}; int n = matrix[0].length; boolean[][] visited = new boolean[m][n]; int[] dx = new int[]{-1, 0, 1, 0}, dy = new int[]{0, 1, 0, -1}; //按照上 右 下 左的顺序 int x = 0, y = 0, d = 1; //d=1代表初始方向是向右 int index = 0; int[] res = new int[m*n]; for (int i = 0; i < m * n; i++) { res[index++] = matrix[x][y]; visited[x][y] = true; int a = x + dx[d], b = y + dy[d]; if (a < 0 || a >= m || b < 0 || b >= n || visited[a][b]) { d = (d + 1) % 4; a = x + dx[d]; b = y + dy[d]; } x = a; y = b; } return res; } } 

10、包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

class MinStack { //维护一个单调递减的辅助栈 public Stack<Integer> stack; public Stack<Integer> minStack; /** initialize your data structure here. */ public MinStack() { stack = new Stack<>(); minStack = new Stack<>(); } public void push(int x) { stack.push(x); if (minStack.empty() || minStack.peek() >= x) { minStack.push(x); } } public void pop() { if (!stack.empty()) { if (stack.peek().equals(minStack.peek())) { //这里不要使用==判断 minStack.pop(); } stack.pop(); } } public int top() { if (!stack.empty()) { return stack.peek(); } return 0; } public int min() { if (!minStack.empty()) { return minStack.peek(); } return 0; } } /**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */ 

11、栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

class Solution { public boolean validateStackSequences(int[] pushed, int[] popped) { //使用一个新栈来模拟push操作 if (pushed == null || popped == null || pushed.length != popped.length) return false; Stack<Integer> stack = new Stack<>(); int popId = 0; for (int pushId = 0; pushId < pushed.length; pushId++) { stack.push(pushed[pushId]); while (!stack.empty() && stack.peek() == popped[popId]) { stack.pop(); popId++; } } if (stack.empty()) return true; return false; } }