网易实习面经中的算法题（java版本含注释）_网易 面试 算法

前言

该文章主要是收集牛客上面经被问到的高频算法
主要供个人参考以及理解

7. 整数反转（中等）

题目：题目：7. 整数反转

class Solution {
    public int reverse(int x) {

        int res=0;
        while(x!=0){
            if(res<Integer.MIN_VALUE/10||res>Integer.MAX_VALUE/10){
                return 0;
            }
            
            res=res*10+x%10;
            x=x/10;
        }

        return res;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

9. 回文数（简单）

题目：9. 回文数

class Solution {
    public boolean isPalindrome(int x) {
        // 特殊情况：
        // 如上所述，当 x < 0 时，x 不是回文数。
        // 同样地，如果数字的最后一位是 0，为了使该数字为回文，
        // 则其第一位数字也应该是 0
        // 只有 0 满足这一属性
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int cur = 0;
        while (x >cur) {
            cur = cur * 10 + x % 10;
            x /= 10;
        }

        // 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
        // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，
        // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
        return x == cur || x == cur / 10;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

14. 最长公共前缀（简单）

题目：leetcode：14. 最长公共前缀

class Solution {
    public String longestCommonPrefix(String[] strs) {

        //注意其中的区别，一个是字符数组，一个是里面的字符串
        int m=strs.length;
        int n=strs[0].length();

        //主体是列开始比较，每一列在外面
        for(int j=0;j<n;j++){
            for(int i=0;i<m;i++){
            
                if(strs[i].length()==j||strs[i].charAt(j)!=strs[0].charAt(j)){
                    return strs[0].substring(0,j);
                }
            }
        }
        return strs[0];

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

20. 有效的括号（简单）

题目：20. 有效的括号

class Solution {
    public boolean isValid(String s) {
        //临界条件 奇数个数排除
        if(s.length()%2!=0)return false;

        Stack<Character>stack=new Stack<>();
        //转换为字符数组，也可不用转换
        char []c=s.toCharArray();

        Map<Character,Character>map=new HashMap<>(){{
            put(')','(');
            put('}','{');
            put(']','[');
        }};

        for(int i=0;i<c.length;i++){
            //如果包含这个右括号，则要相应的把左括号去除
            if(map.containsKey(c[i])){
                //先判断是否和左括号相等，如果不等先返回false
                //而且即使有右括号，栈中也要有左括号这个值，不能为空。
                if(stack.isEmpty()||map.get(c[i])!=stack.peek()){
                    return false;
                }
                stack.pop();
            }else{
            //如果没有包含这个右括号，则要把左括号进栈，相对应的当前的符号  也就是左括号
                stack.push(c[i]);
            }
        }

        //如果stack还有东西，说明不是有效的括号
        return stack.isEmpty();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

23. 合并K个升序链表（困难）

题目：23. 合并K个升序链表

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {

        //使用优先队列，本身比较的类型为ListNode，所以要转换为值去比较
        //使用函数Comparator.comparingInt
        PriorityQueue<ListNode>pq=new PriorityQueue<>(Comparator.comparingInt(o->o.val));
        
        int n=lists.length;
        for(int i=0;i<n;i++){
            //此处添加对头元素的时候，要保证每个对头元素不为空
            if(lists[i]!=null) pq.offer(lists[i]);
           
        }

        //创建一个头节点
        ListNode head=new ListNode(-1);
        ListNode ans=head;
        //如果队列不为空，则进行移动位置
        while(!pq.isEmpty()){
            ListNode cur=pq.poll();
            ans.next=cur;
            ans=ans.next;
            //并且判断下一个值是否不为空，不为空则添加
            if(cur.next!=null){
                pq.offer(cur.next);
            }
        }

        return head.next;


    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

64. 最小路径和（中等）

题目：leetcode：64. 最小路径和

class Solution {
    public int minPathSum(int[][] grid) {
 
        if(grid==null||grid.length==0||grid[0].length==0)return 0;

        int m=grid.length;
        int n=grid[0].length;
        int [][]dp=new int [m][n];
        //初始化
        dp[0][0]=grid[0][0];
        for(int i=1;i<m;i++){
            dp[i][0]=dp[i-1][0]+grid[i][0];
        }
        for(int j=1;j<n;j++){
            dp[0][j]=dp[0][j-1]+grid[0][j];
        }

        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }

        return dp[m-1][n-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

单纯一个for循环：

class Solution {
    public int minPathSum(int[][] grid) {
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(i == 0 && j == 0) continue;
                else if(i == 0)  grid[i][j] = grid[i][j - 1] + grid[i][j];
                else if(j == 0)  grid[i][j] = grid[i - 1][j] + grid[i][j];
                else grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
            }
        }
        return grid[grid.length - 1][grid[0].length - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

103. 二叉树的锯齿形层序遍历（中等）

题目：leetcode：103. 二叉树的锯齿形层序遍历

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> list=new ArrayList<List<Integer>>();
        if(root==null)return list;
        

        Queue<TreeNode> que =new LinkedList<>();
        que.offer(root);
        boolean direction = true;
        while(!que.isEmpty()){
            List<Integer> sonlist=new ArrayList<>();
            int n=que.size();
            
            for(int i=0;i<n;i++){
                TreeNode node=que.poll();
                sonlist.add(node.val);
                
                if(node.left!=null)que.offer(node.left);
                if(node.right!=null)que.offer(node.right);
            }
            if(!direction){
                Collections.reverse(sonlist);
            }

            direction=!direction;
            list.add(sonlist);
            
        }

        return list;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

133. 克隆图（中等）*

题目：leetcode：133.克隆图

//借助哈希表记录被克隆过的节点来避免陷入死循环

//本体使用的是dfs，深度优先遍历，使用hashmap存储其访问的值有无被访问过
class Solution {
    //存储的key为node，value为克隆的value
    HashMap<Node,Node>map=new HashMap<>();
    public Node cloneGraph(Node node) {
        //如果为null，则返回本身
        if(node==null)return node;

        //每一个判断的都判断是否有被克隆，如果被克隆访问过了，则直接返回克隆的值
        if(map.containsKey(node)){
            return map.get(node);
        }

        //创建一个克隆的节点，new node（构造函数为值，边）
        Node clonenode=new Node(node.val,new ArrayList());
        //将其克隆进去map集合中
        map.put(node,clonenode);

        //遍历node的邻接节点，通过clone的邻接节点add添加（递归的下一个节点）
        for(Node adjacent:node.neighbors){
            clonenode.neighbors.add(cloneGraph(adjacent));
        }
        return clonenode;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) {
            return node;
        }

        HashMap<Node, Node> map = new HashMap();

        // 将题目给定的节点添加到队列
        LinkedList<Node> queue = new LinkedList<Node> ();
        queue.offer(node);
        
        // 克隆第一个节点并存储到哈希表中
        map.put(node, new Node(node.val, new ArrayList()));

        // 广度优先搜索
        while (!queue.isEmpty()) {
            // 取出队列的头节点
            Node n = queue.poll();
            // 遍历该节点的邻居
            for (Node neighbor: n.neighbors) {
                if (!map.containsKey(neighbor)) {
                    // 如果没有被访问过，就克隆并存储在哈希表中
                    map.put(neighbor, new Node(neighbor.val, new ArrayList()));
                    // 将邻居节点加入队列中
                    queue.offer(neighbor);
                }
                // 更新当前节点的邻居列表
                map.get(n).neighbors.add(map.get(neighbor));
            }
        }

        return map.get(node);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

141. 环形链表（简单）

题目：leetcode：141. 环形链表

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null||head.next==null) return false;
        ListNode p=head;
        ListNode q=head;
        while(q!=null&&q.next!=null){          
            p=p.next;
            q=q.next.next;
            if(p==q)return true;
        }
        return false;
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

142. 环形链表 II（中等）

题目：leetcode：142. 环形链表 II

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null && fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;           
               
            if(fast==slow){
                ListNode ans=head;
                while(ans!=slow){
                    ans=ans.next;
                    slow=slow.next;
                    
                }
                return ans;               
            }
                     
        }
        return null;
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

146. LRU 缓存（中等）*

题目：leetcode：146. LRU 缓存

public class LRUCache {
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int key, int value) {this.key = key; this.value = value;}
    }

    private Map<Integer, DLinkedNode> map = new HashMap<Integer, DLinkedNode>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        // 使用伪头部和伪尾部节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkedNode node= map.get(key);
        if(node==null) return -1 ;
        removeNode(node);
        addToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DLinkedNode node=map.get(key);
        if(node == null){
            DLinkedNode newnode=new DLinkedNode(key,value); 
            map.put(key,newnode);  
            addToHead(newnode);
            size++;
            if(size>capacity){
                DLinkedNode tail=removeTail();
                map.remove(tail.key);
                size--;
            }
        }
        else{
            node.value = value;
            removeNode(node);
            addToHead(node);
        }

      
    }

    private void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private DLinkedNode removeTail() {
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

160. 相交链表（简单）

题目：题目：160. 相交链表

可以对比一下上面的那个操作，多了一步而已

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null){
                    return null;
                }

        ListNode a=headA;
        ListNode b=headB;
        //判断的初始条件
        while(a!=b){
            //两者的判断条件一定要分开
            if(a!=null){
                a=a.next;
            }else{
                a=headB;
            }

            if(b!=null){
                b=b.next;
            }else{
                b=headA;
            }
        }
        return a;

        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

200. 岛屿数量（中等）

题目：leetcode：200. 岛屿数量

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int m=grid.length;
        int n=grid[0].length;
        
        int sum=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]=='1'){
                    sum++;
                    dfs(grid,i,j);
                }
            }
        }
        return sum;

    }
    public void dfs(char [][] grid,int i,int j){
        int m=grid.length;
        int n=grid[0].length;
        if(i<0||i>=m||j<0||j>=n||grid[i][j]=='0')return ;
        grid[i][j]='0';

        dfs(grid,i-1,j);
        dfs(grid,i+1,j);
        dfs(grid,i,j-1);
        dfs(grid,i,j+1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

206. 反转链表（简单）

题目：leetcode：206. 反转链表

class Solution {
    public ListNode reverseList(ListNode head) {
        
        //不用创建这个临时的头节点，因为不用保存这个值，而且反转的时候，会多一个0
        //ListNode prevhead=new ListNode(0);  
        //ListNode prev=prevhead;

        ListNode prev=null;
        ListNode cur=head;
        while(cur!=null){
            ListNode node=cur.next;
            cur.next=prev;
            prev=cur;
            cur=node;
        }
        return prev;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

如果使用递归的形式：

class Solution {
   public ListNode reverseList(ListNode head) {
    // 1. 递归终止条件
    if (head == null || head.next == null) {
        return head;
    }
    ListNode newhead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return newhead;
}
}
1
2
3
4
5
6
7
8
9
10
11
12

509. 斐波那契数（简单）

题目：leetcode：509. 斐波那契数

动态规划，非递归的实现

class Solution {
    public int fib(int n) {
        //当为0的时候 初始化为0
        if(n==0)return 0;
        //当为1 或者2的时候，a b为1
        int a=1;
        int b=1;
        //c用来计数
        int c=1;

        for(int i=3;i<=n;i++){
            //类似滑动窗口的移动
            c=a+b;
            a=b;
            b=c;
        }
        //最后返回c的值
        return c;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

如果使用递归地实现（耗时8ms）

class Solution {
    public int fib(int n) {

        if(n<2)return n;

        return fib(n-1)+fib(n-2);
        

    }
}
1
2
3
4
5
6
7
8
9
10

剑指 Offer 40. 最小的k个数（简单）

题目：leetcode：剑指 Offer 40. 最小的k个数

使用优先队列的方式

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        // 默认是小根堆，实现大根堆需要重写一下比较器。
        //要把大的数字不要了，只保留小的，所以大根堆要重写
        Queue<Integer> pq = new PriorityQueue<>((o1,o2)->(o2-o1));
        for (int num: arr) {
            if (pq.size() < k) {
                pq.offer(num);
            }else if(num<pq.peek()){
                pq.poll();
                pq.offer(num);
            }
        }
        
        // 返回堆中的元素
        int[] res = new int[pq.size()];
        int idx = 0;
        for(int num: pq) {
            res[idx++] = num;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

使用快排思想：

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        quicksort(arr,0,arr.length-1);
        return Arrays.copyOf(arr,k);

    }
    public void quicksort(int [] arr,int l,int r){
        if(l>=r)return;

        int left=l;
        int right=r;
        while(left<right){
            while(left<right&&arr[right]>=arr[l])right--;
            while(left<right&&arr[left]<=arr[l])left++;
            swap(arr,left,right);
        }
        swap(arr,left,l);
        quicksort(arr,l,left-1);
        quicksort(arr,left+1,r);
    }
    public void swap(int []arr,int left,int right){
        int temp=arr[left];
        arr[left]=arr[right];
        arr[right]=temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26