面试算法：
2021-02-07 本文已影响0人
书虫大王X
第一题：
一个机器人在m×n大小的地图的左上角（起点）。
机器人每次向下或向右移动。机器人要到达地图的右下角（终点）。
可以有多少种不同的路径从起点走到终点？
示例：
输入：（2,1）
返回：1
输入：（2，2）
返回：2
public int uniquePaths (int m, int n) {
// 动态规划，三行代码。
// 建立坐标系为起点(1, 1)，终点(m, n)。
// 到达m，n的路径是到达(m-1, n)的路径之和加上到达(m, n-1)的路径之和，当m或n为1时，
// 说明到达了边界，只有一条路径。
if(m == 1 || n == 1)
return 1;
return uniquePaths(m-1, n) + uniquePaths(m, n-1);
}
第二题：进制转化
- 给定一个十进制数M，以及需要转换的进制数N。将十进制数M转化为N进制数：
- 知识点：
1、栈：Stack<Integer> s = new Stack();
push、pop、peek
2、StringBuilder ：StringBuilder str = new StringBuilder();
str.append(字符串）；
3、数据转化为字符串：String.valueOf(数据)；
public String solve (int M, int N) {
// write code here
Stack<Integer> s = new Stack();
if(M == 0 || N == 10){
return String.valueOf(M);
}
StringBuilder str = new StringBuilder();
if(M < 0){
str.append("-");
M = Math.abs(M);
}
while(M != 0){
s.push(M % N);
M = M / N;
}
int n = s.size();
for(int i = 0; i < n; i++){
if(s.peek() > 9){
str.append((char)(s.pop()-10+'A'));
}else{
str.append(s.pop());
}
}
return String.valueOf(str);
}
第三题：青蛙跳台阶
- 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
public int JumpFloor(int target) {
int a = 1;
int b = 1;
for(int i = 1; i < target; i++){
a = a + b;
b = a - b;
}
return a;
}
第四题：判断链表是否是回文结构
- 给定一个链表，请判断该链表是否为回文结构
- 知识点：
ArrayList:
ArrayList<Integer> list = new ArrayList();
list.add(数据);
list.get(数组的下标)
比较链表的两个节点是否相等：node1.equals(node2)
public boolean isPail2 (ListNode head) {
// write code here
ArrayList<Integer> list = new ArrayList();
while(head != null){
list.add(head.val);
head = head.next;
}
int l = 0;
int h = list.size() -1;
while(l < h){
if(! list.get(l++).equals(list.get(h--))){
return false;
}
}
return true;
}
// 仅供参考，不能通过全部用例（创建一个反转链表，将其与原数组进行比较）
public boolean isPail (ListNode head){
ListNode yk = resover(head);
while(head != null){
if(!yk.equals(head)){
return false;
}
yk = yk.next;
head = head.next;
}
return true;
}
public ListNode resover(ListNode head){
if(head == null){
return head;
}
ListNode current = head;
ListNode previous = null;
while(current != null){
ListNode temp = current.next;
current.next = previous;
previous = current;
current = temp;
}
return previous;
}
第五题：判断链表是否有环
- 知识点：判断两个节点是否相同： head == head.next;
public boolean hasCycle(ListNode head) {
if(head == null || head.next == null){
return false;
}
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(slow == fast){
return true;
}
}
return false;
}
第六题：树节点的和
-
根节点到叶子节点的所有路径表示的数字之和，例如下图，求得结果25（12 + 13 = 25）：
public int sumNumbers(TreeNode root) {
if(root == null){
return 0;
}
return sumOfTree(root,root.val);
}
public int sumOfTree(TreeNode root,int sum){
if(root.left == null && root.right == null){
return sum;
}
int yk = 0;
if(root.left != null){
yk += sumOfTree(root.left,sum * 10 + root.left.val);
}
if(root.right != null){
yk += sumOfTree(root.right,sum * 10 + root.right.val);
}
return yk;
}
第七题：树路径的最大值
- 一棵树，每个节点都有不同的赋值，计算各叶子节点到根节点的数值相加的最大值。
- 思路：递归算法在栈中的实现是倒过来的，最开始的递归调用被压到栈底，而越晚调用的方法越靠近栈顶，越先被调用。所以树在递归方法中总是叶子节点对应的递归方法被先执行。
- 递归：判断当前节点是否有左右孩子，如果有，则将左右孩子的值与当前节点的值分别相加，然后取大的一直最为返回值。
public int sumNumbers (TreeNode root) {
if(root == null){
return 0;
}
if(root.left == null && root.right == null){
return root.val;
}
return Math.max(sumNumbers(root.right),sumNumbers(root.left)) + root.val;
}
第八题:树路径的和
- 给定一个二叉树和一个值sum，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径
public boolean hasPathSum (TreeNode root, int sum) {
// write code here
if(root==null){
return false;
}
//处理叶子节点
if(root.left==null && root.right==null){
if(root.val==sum){
return true;
}else{
return false;
}
}
boolean leftHas=hasPathSum(root.left,sum-root.val);
boolean rightHas=hasPathSum(root.right,sum-root.val);
boolean cur=leftHas||rightHas;
return cur;
}
- 给定一个二叉树和一个值 sum，请找出所有的根节点到叶子节点的节点值之和等于sum 的路径：
ArrayList<ArrayList<Integer>> AllList = new ArrayList<>();
public ArrayList<ArrayList<Integer>> pathSum (TreeNode root, int sum) {
// 树空
if(root==null){
return AllList;
}
//1.初始当前的列表
ArrayList<Integer> path = new ArrayList<>();
//2.深度优先遍历
dfs(AllList,path,root,sum);
//3.返回路径集合
return AllList;
}
//一、对root进行深度优先遍历
//result:所有路径和为sum的结果集 list：当前路径结点集 root：当前根节点 sum：当前所需的路径和
public void dfs(ArrayList<ArrayList<Integer>> result,ArrayList<Integer> list,TreeNode root,int sum){
if(root==null){
return;
}
if(root.left==null && root.right==null){//为叶子节点
if(sum-root.val==0){//加上该结点后，满足路径和sum
list.add(root.val);//将当前结点加入list
result.add(new ArrayList<>(list));//将当前路径 加入 结果集
list.remove(list.size()-1); //去掉当前结点，继续下面的遍历
}
return;
}
list.add(root.val);
dfs(result,list,root.left,sum-root.val);
dfs(result,list,root.right,sum-root.val);
list.remove(list.size()-1);
}
第八题：合并二叉树
- 已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替：
public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
if(t1 == null){
return t2;
}
if(t2 == null){
return t1;
}
t1.val = t1.val + t2.val;
t1.left = mergeTrees(t1.left,t2.left);
t1.right = mergeTrees(t1.right,t2.right);
return t1;
}
第九题:两个线程交替执行
- 两个线程交替打印0到100的奇偶数：
public static void main(String[] args) {
new Thread(new Runnable() {
@Override
public void run() {
while (count < 100) {
synchronized (lock) {
if ((count & 1) == 0) {
System.out.println(Thread.currentThread().getName() + ":" + count++);
}
}
}
}
}, "偶数线程").start();
new Thread(new Runnable() {
@Override
public void run() {
while (count < 100){
synchronized (lock){
if ((count & 1) == 1){
System.out.println(Thread.currentThread().getName() + ":" + count++);
}
}
}
}
},"奇数线程").start();
}
- 方法二：
private static class ThreadTest implements Runnable{
@Override
public void run() {
while (count < 100){
synchronized (lock){
System.out.println(Thread.currentThread().getName() + ":" + count++);
lock.notify();
if (count < 100){
try {
lock.wait();
}catch ( InterruptedException e){
e.printStackTrace();
}
}
}
}
}
}
public static void main(String[] args) {
new Thread(new ThreadTest(),"偶数线程").start();
new Thread(new ThreadTest(),"奇数线程").start();
}
第十题：
- 将string转化为charArray： string.toCharArray()
- 将其他类型的数据转为字符串：String.valueOf(数据)
第十一题：逆波兰表达式求值
在反向波兰表示法中计算算术表达式的值,遇到操作符就计算前两个数值，例 ["2", "1", "+", "3", "*"] -> (2 + 1) * 3 -> 9
public int evalRPN(String[] tokens) {
Stack<Integer> s = new Stack<Integer>();
String operators = "+-*/";
for (String token : tokens) {
if (!operators.contains(token)) {
s.push(Integer.valueOf(token));
continue;
}
int a = s.pop();
int b = s.pop();
if (token.equals("+")) {
s.push(b + a);
} else if(token.equals("-")) {
s.push(b - a);
} else if(token.equals("*")) {
s.push(b * a);
} else {
s.push(b / a);
}
}
return s.pop();
}
第十二题：返回一个数组的前X个大的数
- 知识点:
PriorityQueue默认是一个小顶堆，然而可以通过传入自定义的Comparator函数来实现大顶堆。
public int[] topk(int[] nums, int k) {
int[] result = new int[k];
if (nums == null || nums.length < k) {
return result;
}
Queue<Integer> pq = new PriorityQueue<>();
for (int num : nums) {
pq.add(num);
if (pq.size() > k) {
pq.poll();
}
}
for (int i = k - 1; i >= 0; i--) {
result[i] = pq.poll();
}
return result;
}
十三题：判断一棵树是否是二叉搜索树：
public boolean isValidBST(TreeNode root) {
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean isValidBST(TreeNode root, long min, long max){
if (root == null) {
return true;
}
if (root.val <= min || root.val >= max){
return false;
}
return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
}
十四题：寻找二叉树第K小的值：
- 前提：树是二叉树
public int kthSmallest(TreeNode root, int k) {
if (root == null) {
return 0;
}
// 获取左边节点的个数
int leftCount = getCount(root.left);
// 进入左循环
if (leftCount >= k) {
return kthSmallest(root.left, k);
} else if (leftCount + 1 == k) {
// 就是当前节点
return root.val;
} else {
// 进入右循环
return kthSmallest(root.right, k - leftCount - 1);
}
}
private int getCount(TreeNode root) {
if (root == null) {
return 0;
}
return getCount(root.left) + getCount(root.right) + 1;
}
十五题：数组加一
-
给定一个非负数，表示一个数字数组，在该数的基础上+1，返回一个新的数组。该数字按照数位高低进行排列，最高位的数在列表的最前面。
public int[] plusOne(int[] digits) {
int carries = 1;
for(int i = digits.length - 1; i >= 0 && carries > 0; i--){
int sum = digits[i] + carries;
digits[i] = sum % 10;
carries = sum / 10;
}
if(carries == 0) {
return digits;
}
int[] rst = new int[digits.length + 1];
rst[0] = 1;
for(int i = 1; i < rst.length; i++){
rst[i] = digits[i - 1];
}
return rst;
}
十六题：数组删重复值
- 给定一个数组和一个值，在原地删除与值相同的数字，返回新数组的长度。
public int removeElement(int[] A, int elem) {
if (A == null || A.length == 0) {
return 0;
}
int index = 0;
for (int i = 0; i < A.length; i++) {
if (A[i] != elem) {
A[index++] = A[i];
}
}
return index;
}
十七题：数组删值
- 在原数组中“删除”重复出现的数字，使得每个元素只出现一次，并且返回“新”数组的长度。
public int removeDuplicates(int[] A) {
if (A == null || A.length == 0) {
return 0;
}
int size = 0;
for (int i = 0; i < A.length; i++) {
if (A[i] != A[size]) {
A[++size] = A[i];
}
}
return size + 1;
}
十九题：给一个无序链表排序：
public ListNode sortInList (ListNode head) {
// write code here
if(head == null || head.next == null)
return head;
ArrayList<Integer> list = new ArrayList<>();
ListNode tmp = head;
while(tmp != null){
list.add(tmp.val);
tmp = tmp.next;
}
// 将list升序排序
list.sort(Comparator.naturalOrder());
ListNode temp = head;
int i = 0;
while(temp != null){
temp.val = list.get(i++);
temp = temp.next;
}
return head;
}
二十题：数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
public int FindGreatestSumOfSubArray(int[] array) {
int max = array[0];
for(int i = 1; i < array.length; i++){
max = Math.max(arr[i] + max, 0);
}
return max;
}
二十一题：判断一个数字是否是回文结构：
public boolean isPalindrome (int x) {
if(x < 0){
return false;
}
int temp = 0;
int y = x;
while(y != 0){
temp = temp * 10 + y % 10;
y = y / 10;
}
return temp == x;
}
二十二题：
- 取出字符串指定位置的字符：char a = str.charAt(i)；
- 在数值上，小写字母比大写字母打32；所以小写字母转大写字母：'A' = (char) ('a' - 32);
- 将字符串按照指定格式划分为数组，例：String[] a = str.split(" ");
二十三题：用一个升序数组创建平衡二叉树：
public TreeNode sortedArrayToBST (int[] num) {
if(num == null){
return null;
}
return createTree(num, 0, num.length - 1);
}
private TreeNode createTree(int[] num, int left, int right){
if(left > right){
return null;
}
int mid = left + (right - left + 1) / 2;
TreeNode lNode = createTree(num, left, mid - 1);
TreeNode rNode = createTree(num, mid + 1, right);
TreeNode node = new TreeNode(num[mid]);
if(lNode != null) node.left = lNode;
if(rNode != null) node.right = rNode;
return node;
}
二十四题：根据一颗二叉树的前序和中序遍历，创建二叉树：
- 知识点：Arrays.copyOfRange方法，在使用前必须导入 import java.util.Arrays; 使用方法：参数一输入原数组，参数二开始复制的下标，参数三结束复制的下标
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if (pre.length == 0 || in.length == 0) {
return null;
}
TreeNode root = new TreeNode(pre[0]);
// 在中序中找到前序的根
for (int i = 0; i < in.length; i++) {
if (in[i] == pre[0]) {
// 左子树，注意 copyOfRange 函数，左闭右开
root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1),
Arrays.copyOfRange(in, 0, i));
// 右子树，注意 copyOfRange 函数，左闭右开
root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length),
Arrays.copyOfRange(in, i + 1, in.length));
break;
}
}
return root;
}
最长回文子串：
// 字符串的最长回文子串
public static int maxHuiwen(String str){
int maxLength = 0;
for (int i = 0; i < str.length() - 1; i ++){
int len1 = huiWenLength(str,i, i);
int len2 = huiWenLength(str,i, i + 1);
maxLength = Math.max(maxLength,len1);
maxLength = Math.max(maxLength,len2);
}
return maxLength;
}
public static int huiWenLength(String str, int left, int right){
while (left > 0 && right < str.length() - 1){
if (str.charAt(left) == str.charAt(right)){
left --;
right ++;
}else {
break;
}
}
return right - left - 2 + 1;
}
