牛客网字节面试算法刷题记录

NC78 反转链表

public ListNode ReverseList (ListNode head) {if(head==null) return head;ListNode p=head.next,q,tail=head;tail.next = null;while(p!=null){q = p.next;p.next = tail;tail = p;p = q;}return tail;}

NC140 排序

冒泡排序

public int[] MySort (int[] arr) {for(int i=0;i<arr.length-1;i++){for(int j=0;j<arr.length-i-1;j++){int temp = arr[j];if(arr[j]>arr[j+1]){arr[j] = arr[j+1];arr[j+1] = temp;}}}return arr;}

快排

public int[] MySort (int[] arr) {quickSort(arr, 0, arr.length - 1);return arr;}public void quickSort(int[] arr, int low, int high) {if (low >= high) {return;}int base = findBase(arr, low, high);quickSort(arr, low, base - 1);quickSort(arr, base + 1, high);}public int findBase(int[] arr, int low, int high) {int base = arr[low];int start = low;int end = high;while (low < high) {while (low < high && arr[high] > base) {high--;}while (low < high && arr[low] <= base) {low++;}if (low < high) {int temp = arr[low];arr[low] = arr[high];arr[high] = temp;}}arr[start] = arr[high];arr[high] = base;return high;}

NC93 设计LRU缓存结构

初始简单思路：每次放新值、取某个值时候，都把它放队列最后面，这样就能把最久未用的挤到队头，这样可以保证每次超过队列容量时，删除值和放新值时间复杂度都是O(1)，因此选用一个双端队列。

进一步细化：每次set一个重复值或是get一个值时，都需要将原来的某个节点给他移动到队尾，我们都知道如果是数组类型的话，这个时间复杂度是O(n-i)，如何保证这个时间复杂度也是O（1）呢。因此可以使用循环链表保存前序指针和后继指针，为了方便在队首和队尾插入元素，需要两个指针来指明队首和队尾。如何判断这个值存在不存在，肯定要hashmap了，就需要把每次新产生的节点存到hashmap里面，所以需要自己定义一个类型，hashmap key为key，值为自己定义的这个类型。

还需要一个值表明容量剩余。

那么详细来说思路就是：

set函数：1.首先要判断这个key是否已经存在，如果已经存在，那么将map里的值替换掉，并将该key对应的节点从原来位置删掉，再把该节点插入到队尾。

删除逻辑又分成三种：（1）如果是普通节点，就让node.pre.next=node.next,node.next.pre=node.pre,node.pre=null,node.next=null（2）如果该节点本身就是尾节点，说明不需要移动、不做处理；（3）如果是头结点，那么node.pre就是null，如果采用上面的逻辑就会出现空指针异常，此时只能让head=node.next  node.next.pre=null node.next=null。

2.如果不存在，也分为两种情况：（1）队伍满了，需要删除队首，并将该值从hashmap删除，再生成新节点插入队尾，容量不变，仍然为0。（2）队伍还有位置，直接生成新节点插入队尾，容量减1。两种逻辑都不要忘记将新节点的key、value存入到hashmap。

get函数：1.如果存在，找到该节点，将对应节点从原来位置删除，再将该节点插入队尾。（和set部分逻辑一样，可以考虑将删除节点、将某个节点插入到队尾这两段逻辑单独拎出来作为两个函数） 2.如果不存在，返回-1。

import java.util.*;public class Solution {
//标志队首Node head;
//标志队尾Node tail;class Node {public int key;public int value;public Node pre;public Node next;public Node(int key, int value, Node pre, Node next) {this.value = value;this.key = key;this.pre = pre;this.next = next;}}HashMap<Integer, Node> map = new HashMap<>();int count = 0;int maxCap = 0;public Solution(int capacity) {maxCap = capacity;}public void print(Node n) {Node p = n;while (p != null) {System.out.print("-" + p.value);p = p.next;}System.out.println();}public int get(int key) {
//如果存在该元素，将该元素节点移动到队尾，原位置删除if (map.containsKey(key)) {Node delNode = map.get(key);Node preNode = delNode.pre;Node nextNode = delNode.next;//在原位置删除该元素//该元素本来就是队尾，直接返回无需换位置if (count == 1 || nextNode == null) return delNode.value;//如果原来是队首，删除逻辑单独处理if (preNode == null) {head = nextNode;nextNode.pre = null;delNode.next = null;} else {preNode.next = delNode.next;delNode.next.pre = preNode;}//将元素加到队尾tail.next = delNode;delNode.next = null;delNode.pre = tail;tail = delNode;// System.out.println("----get:-----");// print(head);// map.forEach((k, v)->System.out.println("k:" + k + "v:" + v.value));// System.out.println("输出：" + delNode.value);return delNode.value;} else {//如果不存在返回-1// System.out.println("----get:-----");// print(head);// map.forEach((k, v)->System.out.println("k:" + k + "v:" + v.value));// System.out.println("输出：-1");return -1;}}public void set(int key, int value) {//插入时判断是否已经有该key，有的话需要替换，并将该元素移到队尾if (map.containsKey(key)) {Node dulNode = map.get(key);dulNode.value = value;map.put(key, dulNode);//在原位置删除该元素//该元素本来就是队尾，直接返回无需换位置if (count == 1 || dulNode.next == null) return;//如果原来是队首，删除逻辑单独处理if (dulNode.pre == null) {head = dulNode.next;dulNode.next.pre = null;dulNode.next = null;} else {dulNode.pre.next = dulNode.next;dulNode.next.pre = dulNode.pre;}//将元素加到队尾tail.next = dulNode;dulNode.next = null;dulNode.pre = tail;tail = dulNode;// System.out.println("----set:-----");// print(head);// map.forEach((k, v)->System.out.println("k:" + k + "v:" + v.value));// System.out.println("输出：null");} else {// 插入时判断数量+1是否大于容量if (maxCap <= 0) return;if (count + 1 > maxCap) {//大于容量队首元素出队map.remove(head.key);Node tempNode = head.next;head.next = null;head = tempNode;head.pre = null;count--;}//新元素入队尾Node newNode = new Node(key, value, null, null);newNode.pre = tail;if (tail != null) {tail.next = newNode;} else {tail = newNode;head = newNode;head.pre = null;tail.pre = null;head.next = null;tail.next = null;}tail = newNode;count++;map.put(key, newNode);// System.out.println("----set:-----");// print(head);// map.forEach((k, v)->System.out.println("k:" + k + "v:" + v.value));// System.out.println("输出：null");}}
}/*** Your Solution object will be instantiated and called as such:* Solution solution = new Solution(capacity);* int output = solution.get(key);* solution.set(key,value);*/

NC102 在二叉树中找到两个节点的最近公共祖先

 public int lowestCommonAncestor (TreeNode root, int o1, int o2) {HashMap<Integer,Integer> hashMap = new HashMap<>();List<TreeNode> list = new ArrayList<>();list.add(root);hashMap.put(root.val,null);while(!list.isEmpty()){TreeNode node = list.get(0);if(node.left!=null){list.add(node.left);hashMap.put(node.left.val,node.val);}if(node.right!=null){list.add(node.right);hashMap.put(node.right.val,node.val);} list.remove(0);}List<Integer> pathO1 = new ArrayList<>();pathO1.add(o1);List<Integer> pathO2 = new ArrayList<>();pathO2.add(o2);findPath(hashMap,o1,pathO1);findPath(hashMap,o2,pathO2);pathO1.forEach(p->System.out.print(p+" "));System.out.println();pathO2.forEach(p->System.out.print(p+" "));int index1=pathO1.size()-1;int index2=pathO2.size()-1;while(index1>=0 && index2>=0 && pathO1.get(index1).equals(pathO2.get(index2))){index1--;index2--;}if(index1>=0 && index2>=0){return pathO1.get(index1+1);}if(index1<0){return pathO1.get(0);}if(index2<0){return pathO2.get(0);}return 0;}public void findPath(HashMap<Integer,Integer> hashMap,Integer o,List<Integer> list){while(o!=null){if(hashMap.get(o)!=null)list.add(hashMap.get(o));o = hashMap.get(o);}}

NC19 连续子数组的最大和

描述

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。

数据范围:

1<=n<=2×105

−100<=a[i]<=100

要求:时间复杂度为O(n)，空间复杂度为 O(n)

进阶:时间复杂度为 O(n)，空间复杂度为 O(1)

输入[1,-2,3,10,-4,7,2,-5]，返回值：18，经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18

思路

用一个动态规划数组，每个位置上的人都有两种选择，加入前面的或者不加入，每个位置上的人努力做到自己这和最大，所以会比对上一位的和加上自己的比自己本身手里的大吗，如果打不过就加入，如果加入还不如自己单干就不加入，全程将最大值记录下来，最后就可以得到最优解。

 public int FindGreatestSumOfSubArray (int[] array) {int[] dp = new int[array.length];dp[0] = array[0];int max = dp[0];for(int i=1;i<array.length;i++){dp[i] = Math.max(dp[i-1]+array[i],array[i]);if(dp[i]>max) max = dp[i];}return max;}

NC1 大数加法

这道题注意别超时，不要切割字符串转成int数组，不要用string保存结果再反转，用一个char数组保存。

 public String solve (String s, String t) {if (s.length() <= 0)return t;if (t.length() <= 0)return s;char[] res = new char[Math.max(s.length(),t.length())];int high = 0;int index1 = s.length() - 1;int index2 = t.length() - 1;while (index1 >= 0 && index2 >= 0) {int add = s.charAt(index1) - '0' + t.charAt(index2) - '0' + high;res[index2] = (char)( add % 10 + '0');if (add >= 10) high = 1;else high = 0;index1--;index2--;}while (index1 >= 0) {int add =  s.charAt(index1) - '0' + high;res[index1] = (char)( add % 10 + '0');if (add >= 10) high = 1;else high = 0;index1--;}while (index2 >= 0) {int add = t.charAt(index2) - '0' + high;res[index2] = (char)( add % 10 + '0');if (add >= 10) high = 1;else high = 0;index2--;}String result = String.valueOf(res);if (high == 1) result = "1" + result;return result;}

NC41 最长无重复子数组

这题直接暴力法，第一层遍历用i从头到尾，第二层遍历用index从i到尾，如果遍历过程中遇到的map里没有就length加一，加入map，如果遇到重复的，比较length是否大于max，大于则替换，将mao清空，break退出此次。

public int maxLength (int[] arr) {int max = -1;int length = 0;HashMap<Integer, Boolean> hashMap = new HashMap<>();for (int i = 0; i < arr.length; i++) {for (int index = i; index < arr.length; index++) {if (!hashMap.containsKey(arr[index])) {hashMap.put(arr[index], true);length++;if (length > max) max = length;} else {hashMap.clear();length = 0;break;}}}return max;}

NC38 螺旋矩阵

描述

给定一个m x n大小的矩阵（m行，n列），按螺旋的顺序返回矩阵中的所有元素。

数据范围：0≤n,m≤10，矩阵中任意元素都满足 0∣val∣≤100

要求：空间复杂度 O(nm) ，时间复杂度 O(nm)

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

思路

递归函数，设置上top下down左left右right四个值作为四个方向的边界，先从左向右输出（j=left,j<right避免和下一个方向的输出重复），再从上往下输出(i=top,i<down)，从右往左输出(j=right,j>left)，从下往上输出(i=down,i>top)，然后将top++,down--,left++,right--传入递归

递归出口为left>right或者top>down

需要处理的一个特殊情况是当left==right或者top==down时说明是单列、单行，此时要将此列、行单独输出后返回。

代码

 public ArrayList<Integer> spiralOrder (int[][] matrix) {int m = matrix.length;ArrayList<Integer> res = new ArrayList<>();if(m==0) return res;int n = matrix[0].length;circle(matrix, 0, n-1, 0, m-1, res);return res;}public void circle(int[][] matrix, int left, int right, int top, int down,ArrayList<Integer> res) {if(left>right || top>down) return;if(left==right){//只有一列按列遍历for(int i=top;i<=down;i++){res.add(matrix[i][left]);}return;}if(top==down){//只有一行按行遍历for(int j=left;j<=right;j++){res.add(matrix[down][j]);}return;}for(int j=left;j<right;j++){res.add(matrix[top][j]);}for(int i=top;i<down;i++){res.add(matrix[i][right]);}for(int j=right;j>left;j--){res.add(matrix[down][j]);}for(int i=down;i>top;i--){res.add(matrix[i][left]);}circle(matrix,left+1,right-1,top+1,down-1,res);}

NC17 最长回文子串

描述

对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。

数据范围： 1≤n≤1000

要求：空间复杂度 O(1)，时间复杂度 O(n2)

进阶:  空间复杂度O(n)，时间复杂度 O(n)

思路

暴力：i遍历字符串,index遍历从i到字符串尾，对每个子串s.subString(i,index+1)，如果是回文串，记录长度，如果大于最大值覆盖。

另外需要一个判断是否为回文串的函数。

时间复杂度为O(N^2)+O(n)

代码

ublic int getLongestPalindrome (String A) {int maxLength = 1;int length = 1;for (int i = 0; i < A.length(); i++) {int index = i;length = 1;for (; index < A.length(); index++) {if (isPalindrome(A.substring(i, index+1))) {length = A.substring(i, index+1).length();if (length > maxLength) {maxLength = length;}}}}return maxLength;}public boolean isPalindrome(String A) {int length = A.length();Stack<Character> stack = new Stack<>();for (int i = 0; i < length; i++) {if (length % 2 != 0) {if (i < length / 2) {stack.add(A.charAt(i));} else if (i > length / 2) {if (stack.isEmpty() || !stack.pop().equals(A.charAt(i))) {return false;}}} else {if (i < length / 2) {stack.add(A.charAt(i));} else if (i >= length / 2) {if (stack.isEmpty() || !stack.pop().equals(A.charAt(i))) {return false;}}}}if (!stack.isEmpty()) return false;return true;}

NC54 三数之和

描述

给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。

数据范围：0≤n≤1000，数组中各个元素值满足 ∣val∣≤100

空间复杂度：O(n2)，时间复杂度 O(n2)

注意：

1. 三元组（a、b、c）中的元素必须按非降序排列。（即a≤b≤c）
2. 解集中不能包含重复的三元组。

例如，给定的数组 S = {-10 0 10 20 -10 -40},解集为(-10, -10, 20),(-10, 0, 10) 

思路

先将数组排序（时间复杂度O（logn）），用i遍历数组。对每一个i进行循环：i右侧的第一个元素下标赋值给low,最后一个元素下标赋值给high，如果low和high所在位置数字相加等于-arr[i]将这三个元素加入到结果，同时low++,high--来继续寻找，如果小于则low++，如果大于则high--。该循环结束条件应为low不超过右边界（长度-1）,high不超过左边界(0)，且low<high。

除此之外要考虑去重的问题，可能有两种情况出现重复，

第一种是元素重复被选中：假设输入为[-40,-10,-10,0,10,20]的情况下，如果i遍历到第一个-10，下面去遍历会找到[-10,20][0,10]，等到i遍历到第二个-10一样会得到相同的结果，这样就会产生重复。对这种重复的解决办法是，如果arr[i]==arr[i-1]就跳过（所以i需要从1开始）

第二种是进行双指针查找的区间里出现重复值：假设输入为[-10,-10,0,0,10,]，i遍历到-10，找到[0,10],[0,10]两个重复。对这种的处理方式是如果arr[low]==arr[low-1]则跳过arr[low]，如果arr[high]==arr[high+1]则跳过arr[high]。

为了防止数据越界，此处需要限制high<=arr.length-1，本来也应该限制low>=0，但是low的左边界是i不是0，所以此处应该是限制low>i+1(如果low取i+1,那么也会将arr[i]和arr[i+1]进行比较，arr[i]是我们选中的数，他允许和查找范围内的重复，所以显然不能取此值)

代码

public ArrayList<ArrayList<Integer>> threeSum (int[] num) {//先排序Arrays.sort(num);ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();for (int i = 0; i < num.length; i++) {if (i >= 1 && num[i] == num[i - 1]) {continue;}int low = i + 1;int high = num.length - 1;while (low <= num.length - 1 && high >= 1 && low < high) {if (low > i+1 && num[low] == num[low - 1]) {low++;continue;}if (high + 1 <= num.length - 1 && num[high] == num[high + 1]) {high--;continue;}if (num[low] + num[high] == 0 - num[i]) {ArrayList<Integer> tempList = new ArrayList<Integer>();tempList.add(num[i]);tempList.add(num[low]);tempList.add(num[high]);result.add(new ArrayList<Integer>(tempList));low++;high--;} else if (num[low] + num[high] < 0 - num[i]) {low++;} else {high--;}}}return result;}

NC32 求平方根

描述

实现函数 int sqrt(int x).

计算并返回 x 的平方根（向下取整）

数据范围： 0<=x<231−1

要求：空间复杂度 O(1)，时间复杂度 O(logx)

代码

public int sqrt (int x) {int low = 1;int high = x;if (x == 1) return 1;while (low <= high) {int mid = (low + high) / 2;if (x / mid >= mid && x / (mid + 1) <= mid) {return mid;} else if (x / mid >= mid) {low = mid + 1;} else {high = mid - 1;}}return 0;}