远景智能-秋招面试手撕代码题集锦
远景智能-秋招面试手撕代码
1.寻找重复数
class Solution {public int findDuplicate(int[] nums) {Arrays.sort(nums);for (int i = 1; i < nums.length; i++) {if (nums[i] == nums[i-1]) {return nums[i];}}return -1;}
}
时间复杂度：O(nlgn)
空间复杂度：O(1)(or O(n))，
class Solution {public int findDuplicate(int[] nums) {Set seen = new HashSet();for (int num : nums) {if (seen.contains(num)) {return num;}seen.add(num);}return -1;}
}
时间复杂度：O(n)
空间复杂度：O(n)
2.缺失数字
class Solution {public int missingNumber(int[] nums) {Arrays.sort(nums);// 判断 n 是否出现在末位if (nums[nums.length-1] != nums.length) {return nums.length;}// 判断 0 是否出现在首位else if (nums[0] != 0) {return 0;}for(int i=0;i时间复杂度：O(nlogn)
空间复杂度：O(1)/O(n)
class Solution {public int missingNumber(int[] nums) {int missing = nums.length;for (int i = 0; i < nums.length; i++) {missing ^= i ^ nums[i];}return missing;}
}
时间复杂度：O(n)
空间复杂度：O(1)
class Solution {public int missingNumber(int[] nums) {int expectedSum = nums.length*(nums.length + 1)/2;int actualSum = 0;for (int num : nums) actualSum += num;return expectedSum - actualSum;}
}
时间复杂度：O(n)
空间复杂度：O(1)
3.根据先序中序遍历重建二叉树
class Solution {public TreeNode reConstructBinaryTree(int [] pre,int [] in) {if (pre ==null||in==null) {return null;}if (pre.length == 0||in.length == 0) {return null;} if (pre.length != in.length) {return null;} TreeNode root= new TreeNode(pre[0]);for (int i = 0; i < pre.length; i++) {if (pre[0]==in[i]) {root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(in, 0, i));root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in, i+1,in.length));System.out.print(root.val+",");}} return root;}
}
4.两个有序数组求中位数
class Solution {public static double findMedianSortedArrays(int[] nums1, int[] nums2) {int n=nums1.length;int m=nums2.length;ArrayList list=new ArrayList();for (int i = 0; i < n; i++) {list.add(nums1[i]);}for (int i = 0; i < m; i++) {list.add(nums2[i]);}Collections.sort(list);int sum=list.size();double res=0.0;if (sum%2==0) {//偶数int k=sum/2;res=(double)(list.get(k)+list.get(k-1))/2;}else {//奇数res=list.get(sum/2);}return res;}
}
5.两个栈模拟队列
public class MyQueue{private Stack s1=new Stack();private Stack s2=new Stack();public sychronized void put(E e){s1.push(e);}public sychronized void pop(){if(s2.isEmpty()){while(!s1.isEmpty()){s2.push(s1.pop());}}return s2.pop();}public sychronized boolean empty(){return s1.isEmpty()&&s2.isEmpty();}
}
6.约瑟夫环
public static void yuesefu(int totalNum, int countNum) { // 初始化人数 List start = new ArrayList(); for (int i = 1; i <= totalNum; i++) { start.add(i); } //从第K个开始计数 int k = 0; while (start.size() >0) { k = k + countNum; //第m人的索引位置 k = k % (start.size()) - 1; // 判断是否到队尾 if (k < 0) { System.out.println(start.get(start.size()-1)); start.remove(start.size() - 1); k = 0; } else { System.out.println(start.get(k)); start.remove(k); } }
}
7.连续子数组的最大和
public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt();int[] nums = new int[N];for (int i = 0; i < N; i++) {nums[i] = sc.nextInt();}int[] sums = new int[N];sums[0] = nums[0];int max = sums[0];for (int i = 1; i < N; i++) {sums[i] = Math.max(nums[i], sums[i - 1] + nums[i]);max = Math.max(max, sums[i]);}System.out.println(max);}
8.二叉树的右视图
public List rightSideView(TreeNode root) {if (root == null) return new ArrayList<>();List res = new ArrayList<>();Queue queue = new LinkedList<>();queue.add(root);while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i 9.实心菱形
public static void print07() {for(int x = -5;x<=5;x++) {for(int y = -5;y<=5;y++) {if((x>0?x:-x)+(y>0?y:-y)<=5) {System.out.print("*");}else {System.out.print(" ");}}System.out.println();}
}
10.空心菱形
public static void main(String[] args) {int s=4;for(int i = 1;i<=s;i++) {//控制行数for(int k = 1;k<=s-i;k++) {//空格的个数System.out.print(" ");}for(int j = 1;j<=2*i-1;j++) {//控制星星个数的时候和行有关if(j==1||j==2*i-1) {System.out.print("*");}else {System.out.print(" ");}}System.out.println();}for(int i = s-1;i>=1;i--) {//控制行数for(int k = 1;k<=s-i;k++) {//空格的个数System.out.print(" ");}for(int j = 1;j<=2*i-1;j++) {//控制星星个数的时候和行有关if(j==1||j==2*i-1) {System.out.print("*");}else {System.out.print(" ");}}System.out.println();}
}
11.远景笔试第一题
public class Main {public static List findClosestElements(int[] arr, int k, int x) {int size = arr.length;int left = 0;int right = size - 1;int removeNums = size - k;while (removeNums > 0) {if (x - arr[left] <= arr[right] - x) {right--;} else {left++;}removeNums--;}List res = new ArrayList<>();for (int i = left; i < left + k; i++) {res.add(arr[i]);}return res;}public static void main(String[] args) {int[] arr = {0, 0, 1, 2, 3, 3, 4, 7, 7, 8};int k = 3;int x = 5;System.out.println(findClosestElements(arr, k, x));}
}
12.非递归调用二叉树
（1）前序遍历public List preorderTraversal(TreeNode root) {List res=new ArrayList<>();Stack stack=new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode node=stack.pop();if(node==null) continue;res.add(node.val);stack.push(node.right);//先右后左，保证左子树先进行遍历。stack.push(node.left);}return res;}
（2）后序遍历public List preorderTraversal(TreeNode root) {List res=new ArrayList<>();Stack stack=new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode node=stack.pop();if(node==null) continue;res.add(node.val);stack.push(node.left);stack.push(node.right);}Collections.reverse(res);return res;}（3）中序遍历public List inorderTraversal(TreeNode root) {List res=new ArrayList<>();Stack stack=new Stack<>();if(root==null)return res;TreeNode cur=root;while(cur!=null||!stack.isEmpty()){while(cur!=null){stack.push(cur);cur=cur.left;}TreeNode node=stack.pop();res.add(node.val);cur=node.right;}return res;}
13.层次遍历二叉树
public class Solution {public ArrayList PrintFromTopToBottom(TreeNode root) {ArrayList list = new ArrayList();if(root==null) return list;LinkedList queue = new LinkedList();queue.add(root);while(!queue.isEmpty()){TreeNode node = queue.poll();list.add(node.val);if(node.left!=null){queue.addLast(node.left);}if(node.right!=null){queue.addLast(node.right);}}return list ;}
}
14.层次遍历打印二叉树，每层打印一行
public List> levelOrder(TreeNode root) {if(root == null)return new ArrayList<>();List> res = new ArrayList<>();Queue queue = new LinkedList();queue.add(root);while(!queue.isEmpty()){int count = queue.size();List list = new ArrayList();while(count > 0){TreeNode node = queue.poll();list.add(node.val);if(node.left != null)queue.add(node.left);if(node.right != null)queue.add(node.right);count--;}res.add(list);}return res;}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！