SkySea-GaoMing HomeArchivesTagsCategories
刷题2
|数据结构与算法|

数学

整数反转

这个题最简单的思路就是转换为反转字符串然后分析情况，但是实际考虑比较复
杂，另一个思路就是每次得到最后一位，不断从末尾累积得到反转的数，考虑溢
出的情况时要注意溢出条件 这张图是画手大鹏的图，灵魂画手

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int reverse(int x) {
        int ans=0;
        while(x!=0)
        {
            int pop=x%10;
            if(ans>Integer.MAX_VALUE/10||(ans==Integer.MAX_VALUE/10&&pop>7))
                return 0;
            if(ans<Integer.MIN_VALUE/10||(ans==Integer.MIN_VALUE/10&&pop<-8))
                return 0;
            ans=ans*10+pop;
            x=x/10;
        }
        return ans;
    }
}

回文数

这个题和整数反转很像，不用考虑溢出的情况，如果溢出一定不是回文数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean isPalindrome(int x) {
        if(x<0)
            return false;
        if(x<10)
            return true;
        int ans=0;
        int temp=x;
        while(x!=0)
        {
            int pop=x%10;
            ans=ans*10+pop;
            x=x/10;
        }
        if(ans==temp)
            return true;
        else
            return false;
    }
}

除数博弈

一个叫Asher的分析：如果N是奇数，因为奇数的所有因数都是奇数，因此
N进行一次N-x的操作结果一定是偶数，所以如果a拿到了一个奇数，那么
轮到b的时候，b拿到的肯定是偶数，这个时候b只要进行-1，还给a一个奇
数，那么这样子b就会一直拿到偶数，到最后b一定会拿到最小偶数2，a就
输了，这是一个纯数学问题，最好不要想复杂了

1
2
3
4
5
6
7
8
class Solution {
    public boolean divisorGame(int N) {
        if(N%2==0)
            return true;
        else
            return false;
    }
}

2的幂

只需要一直除2就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean isPowerOfTwo(int n) {
        if(n==1)
            return true;
        if(n<=0)
            return false;
        while(n%2==0)
        {
            n=n/2;
            if(n==1)
                return true;
        }
        return false;
    }
}

两数相加

注意进位

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
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode node=new ListNode(l1.val+l2.val);
        ListNode temp=node;
        boolean flag=false;
        if(temp.val>=10)
        {
            flag=true;
            temp.val-=10;
        }
        l1=l1.next;
        l2=l2.next;
        while(l1!=null&&l2!=null)
        {
           temp.next=new ListNode(l1.val+l2.val);
           if(flag)
           {
               temp.next.val++;
           }
           if(temp.next.val>=10)
           {
               flag=true;
               temp.next.val-=10;
           }
           else
               flag=false;
           l1=l1.next;
           l2=l2.next;
           temp=temp.next;
        }
        if(l1==null&&l2==null)
            {
                if(flag)
                   temp.next=new ListNode(1);
            }
        while(l1!=null)
        {

            temp.next=new ListNode(l1.val);
            if(flag)
                temp.next.val++;
            if(temp.next.val>=10)
                {
                    temp.next.val-=10;
                }
                else
                    flag=false;
            temp=temp.next;
            l1=l1.next;
        }
        while(l2!=null)
        {
            temp.next=new ListNode(l2.val);
             if(flag)
                temp.next.val++;
            if(temp.next.val>=10)
                {
                    temp.next.val-=10;
                }
                else
                    flag=false;
            temp=temp.next;
            l2=l2.next;
        }
        if(flag)
            temp.next=new ListNode(1);
        
        return node;
    }
}

平方数之和

这是一道考数学的题，如果没有相应的数学知识很难巧妙地解出来。根据费马
平方和定理，一个非负整数c能够表示为两个整数的平方和，当且仅当c的形
如4*k+3的质因子的幂次均为偶数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public boolean judgeSquareSum(int c) {
        for (int i = 2; i * i <= c; i++) {
            int count = 0;
            if (c % i == 0) {
                while (c % i == 0) {
                    count++;
                    c /= i;
                }
                if (i % 4 == 3 && count % 2 != 0)
                    return false;
            }
        }
        return c % 4 != 3;
    }
}

完美数

这个题最直接的思路就是遍历，但是会超出时间限制，实际上除了1和平方根
之外，正因子都是成对出现的，所以只需要遍历平方根之前的数就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean checkPerfectNumber(int num) {
        if(num == 1) {
            return false;
        }
        int sum = 1; // 正整数一定会有一个1，同时不用考虑自身，所以单独处理
        int i = 2;
        double sqrt = Math.sqrt(num);
        for(;i < sqrt;i++) {
            if(num % i == 0) {
                sum += i;
                sum += num / i;
            }
        }
        // 此处单独处理的原因在于只需要加1次i值，如果在循环中会加2次
        if(i * i == num) {
            sum += i;
        }
        return sum == num;
    }
}

三个数的最大乘积

如果不考虑负数的情况就是num1，如果存在负数的情况就要考虑num2

1
2
3
4
5
6
7
8
class Solution {
    public int maximumProduct(int[] nums) {
       Arrays.sort(nums);
        int num1=nums[nums.length-1]*nums[nums.length-2]*nums[nums.length-3];
        int num2=nums[0]*nums[1]*nums[nums.length-1];
        return num1>num2?num1:num2;
    }
}

卡牌分组

统计每个数出现的次数，然后求最大公约数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
   public boolean hasGroupsSizeX(int[] deck) {
        int[] count = new int[10000];
        for (int c: deck)
            count[c]++;
        int g = -1;
        for (int i = 0; i < 10000; ++i)
            if (count[i] > 0) {
                if (g == -1)
                    g = count[i];
                else
                    g = gcd(g, count[i]);
            }
        return g >= 2;
    }
    public int gcd(int x, int y) {
        return x == 0 ? y : gcd(y%x, x);
    }
}

三角形的最大周长

我的代码没有优化，不过思路比较清晰，通过分析可知这三个数一定是连续的

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
class Solution {
    public int largestPerimeter(int[] A) {
        Arrays.sort(A);
        int a=A[A.length-1];
        int b=A[A.length-2];
        int c=A[A.length-3];
        int i=A.length-3;
        int k=A.length-2;
        int j=A.length-1;
        int num=a+b+c;
        while(i>=0)
        {
            if(suit(a,b,c))
                return num;
            else{
                i--;
                j--;
                k--;
                if(i==-1)
                    return 0;
                a=A[i];
                b=A[k];
                c=A[j];
                num=a+b+c;
            }
        }
        return 0;
    }
    public boolean suit(int a,int b,int c)
    {
        if((a+b>c)&&(a+c>b)&&(b+c>a))
            return true;
        else
            return false;
    }
}

自除数

这道题比较简单

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
class Solution {
    public List<Integer> selfDividingNumbers(int left, int right) {
        List<Integer> list=new ArrayList<>();
        for(int i=left;i<=right;i++)
        {
            if(ischu(i))
                list.add(i);
        }
        return list;
    }
    public boolean ischu(int val)
    {
        int temp=val;
        while(val!=0)
        {
            int t=val%10;
            if(t==0)
                return false;
            if(temp%t!=0)
                return false;
            val=val/10;
        }
        return true;
    }
}

最大交换

这个题的思路就是从最高位开始找位数最大的进行交换

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
class Solution {
    public int maximumSwap(int num) {
        int length=0;
        int index=1;
        while(num/index!=0)
        {
            index*=10;
            length++;
        }
        int[] array=new int[length];
        int temp=num;
        int i=0;
        while(num!=0)
        {
            array[i]=num%10;
            num=num/10;
            i++;
        }
        int max=-1;
        int lo=-1;
        for(int k=1;k<=length;k++)
        {
            max=-1;
            lo=-1;
            for(int j=0;j<=length-k;j++)
            {
                if(array[j]>max)
                    {
                        max=array[j];
                        lo=j;
                    }
            }
            if(lo!=(length-k)&&(max!=array[length-k]))
            {
                int te=array[lo];
                array[lo]=array[length-k];
                array[length-k]=te;
                break;
            }
        }
        index=1;
        int sum=0;
        for(int j=0;j<length;j++)
        {
            sum=sum+array[j]*index;
            index*=10;
        }
        return sum;
    }
}

缺失数字

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int missingNumber(int[] nums) {
         int length=nums.length;
         int num=length*(length+1)/2;
         for(int i=0;i<length;i++)
         {
             num-=nums[i];
         }
         return num;
    }
}

春招精选50题

https://github.com/frankcbliu/Interview_Notes

二分查找

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
import java.util.*;
public class Solution {
    /**
     * 二分查找
     * @param n int整型 数组长度
     * @param v int整型 查找值
     * @param a int整型一维数组 有序数组
     * @return int整型
     */
    public int upper_bound_ (int n, int v, int[] a) {
        // write code here
        if(v<=a[0])
            return 1;
        if(v>a[n-1])
            return n+1;
        int index1=0;
        int index2=n-1;
        int mid=(index1+index2)/2;
        while(true)
        {
           if(a[mid]>v)
               index2=mid-1;
           else if(a[mid]<v)
               index1=mid+1;
           mid=(index1+index2)/2;
           if(index1>=index2)
               break;
           if(a[mid]==v)
               break;
        }
        if(a[mid]>=v)
        {
            while(a[mid]>=v)
                mid--;
            return mid+2;
        }
        else
        {
           while(a[mid]<v)
               mid++;
           return mid+1;
        }
        
    }
}

求平方根

这个题难受的地方是要考虑整数溢出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int mySqrt(int x) {
        if(x==0)
            return 0;
        long left=1;
        long right=x/2;
        while(left<right)
        {
            //这里要取右中位数
            long mid=(left+right+1)/2;
            long value=mid*mid;
            if(value>x)
                right=mid-1;
            else 
                left=mid;
           
        }
        return (int)left;
    }
}

滑动窗口的最大值

这道题我好像想简单了，先鸽着

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length==0)
            return new int[]{};
        int[] array=new int[nums.length-k+1];
        for(int i=0;i<=nums.length-k;i++)
        {
            int max=nums[i];
            for(int j=i;j<i+k;j++)
                max=max>nums[j]?max:nums[j];
            array[i]=max;
        }
        return array;
    }
}

最长不含重复字符的子字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int maxlength=0;
        for(int i=0;i<s.length();i++)
        {
            HashSet<Character> set=new HashSet<>();
            int length=0;
            for(int j=i;j<s.length();j++)
            {
                if(set.add(s.charAt(j)))
                    length++;
                else
                    break;
            }
            maxlength=maxlength>length?maxlength:length;
        }
        return maxlength;

    }
}

数组中出现超过一半的数

使用hash法，其实也可以不使用。可以使用一个count记录出现的次数，从第一个
数开始依次与下一个数比较，如果相同则count++，不同则count–，如果count
为0则从当前索引重新开始

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int majorityElement(int[] nums) {
        if(nums.length==1)
            return nums[0];
        HashMap<String,Integer> map=new HashMap<>();
        for(int i=0;i<nums.length;i++)
        {
            if(map.containsKey(nums[i]+""))
            {
                int val=map.get(nums[i]+"");
                map.put(nums[i]+"",val+1);
                if(val+1>nums.length/2)
                    return nums[i];
            }
            else
            {
                map.put(nums[i]+"",1);
            }
        }
        return 0;
    }
}

岛屿的最大面积

利用深度优先搜索

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
class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        if(grid.length==0)
            return 0;
        int max=0;
        for(int i=0;i<grid.length;i++)
        {
            for(int j=0;j<grid[0].length;j++)
            {
                if(grid[i][j]==1)
                {
                    int num=dfs(i,j,grid);
                    max=max>num?max:num;
                }
            }
        }
        return max;
    }
    public int dfs(int i,int j,int[][] grid)
    {
        if(i<0||j<0||i>=grid.length||j>=grid[0].length||grid[i][j]==0)
            return 0;
        int num=1;
        grid[i][j]=0;
        num+=dfs(i-1,j,grid);
        num+=dfs(i+1,j,grid);
        num+=dfs(i,j+1,grid);
        num+=dfs(i,j-1,grid);
        return num;
    }
}

接雨水

这道题的思路很明晰，两个柱子之间包含水，我一开始的思路就是从头开始
遍历一旦找到一个块就计算水，整个块减去黑色的部分就是水

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
class Solution {
    public int trap(int[] height) {
        int length=height.length;
        int high=0;
        int width=0;
        int num=0;
        int nnum=0;
        for(int i=0;i<length;i++)
        {
            if(height[i]==0&&high==0)
                continue;
            else if(height[i]!=0&&high==0)
            {
                high=height[i];
                width++;
                nnum+=height[i];
            }
            else
            {
                if(height[i]>=high)
                {
                    num=num+width*high-nnum;
                    nnum=height[i];
                    width=1;
                    high=height[i];
                }
                else
                {
                    width++;
                    nnum+=height[i];
                }
            }
        }
        return num;
    }
}

这个解法是有问题的，我找到块的条件是当前黑色部分的高度大于等于之前
初始的黑色高度就得到一个块，没有考虑就算比初始高度低也能得到块。看
一下大佬的解法

  1. 按行求 也就是一行行求水，这个思路就解决了我之前的问题，不需要
    考虑更低的部分，对于当前行只要遍历得到更高的黑色就是一个块，这个
    块的高度就是1
  2. 按列求 对于当前列来说只要找到当前左边最高的墙和右边最高的墙，
    如果较矮的墙比当前墙高那么一定有水，否则该列不会有水
  3. 动态规划 按列求的时候遍历的每一列都要算出左右的最高列，这样
    比较耗时，可以用两个数组分别保存当前列左边和右边的最高列
  • max_left [i] = Max(max_left [i-1],height[i-1])
  • max_right[i] = Max(max_right[i+1],height[i+1])
  1. 双指针 事实上可以不用两个数组，既然是从左向右遍历的那么左边
    这个数组就可以不用，每次遍历的时候就更新到当前左边最大值
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    public int trap(int[] height) {
        int sum = 0;
        int max_left = 0;
        int[] max_right = new int[height.length];
        for (int i = height.length - 2; i >= 0; i--) {
            max_right[i] = Math.max(max_right[i + 1], height[i + 1]);
        }
        for (int i = 1; i < height.length - 1; i++) {
            max_left = Math.max(max_left, height[i - 1]);
            int min = Math.min(max_left, max_right[i]);
            if (min > height[i]) {
                sum = sum + (min - height[i]);
            }
        }
        return sum;
    }

逆序对

一开始都能想到最简单的方法，可惜时间超限。还很容易想到从右往前遍历，
利用一个数组保存当前位置的逆序对，但是不能简单通过相邻两个元素值得
到逆序对，这个思路也不行。优化肯定是想降低时间复杂度，把O(n^2)
降到O(nlogn)，大佬提供了一种分治思想，实际上就是利用归并排序
求得所有逆序对，事实上归并排序的过程就是消除所有逆序对的过程

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
class Solution {
    public int reversePairs(int[] nums) {
        if(nums.length==0)
            return 0;
        //临时数组
        int[] array=new int[nums.length];
        //暂时保存值
        int[] temp=new int[nums.length];
        for(int i=0;i<nums.length;i++)
        {
            temp[i]=nums[i];
        }
        int num=reverse(nums,array,0,nums.length-1);
        //恢复原数组
        for(int i=0;i<nums.length;i++)
        {
            nums[i]=temp[i];
        }
        return num;
    }
    public int reverse(int[] nums,int[] array,int left,int right)
    {
        if(left==right)
            return 0;
        int mid=(left+right)/2;
        int numleft=reverse(nums,array,left,mid);
        int numright=reverse(nums,array,mid+1,right);
        //这里可以判断一下是否需要合并
        if(nums[mid]<=nums[mid+1])
            return numleft+numright;
        //合并操作
        int num=merge(nums,array,left,right,mid);
        return num+numleft+numright;
    }
    public int merge(int[] nums,int[] array,int left,int right,int mid)
    {
        //逆序对总数
        int count=0;
        int index=0;
        int i=left;
        int j=mid+1;
        while(i<=mid&&j<=right)
        {
            //注意这个地方必须有=，如果没有等号会多算逆序对
            if(nums[i]<=nums[j])
                array[index++]=nums[i++];
            else
            {
                /*
                    核心在这个地方，可以这样想，比如归并的时候第一个
                    是nums[j]归并到前面，那么说明左半部分的元素都比
                    这个nums[j]大，这就有mid-i+1个逆序对，以此就可以
                    得到所有逆序对，如果nums[i]在前那么对于i来说往后
                    就不存在逆序对了
                */
                count+=(mid-i+1);
                array[index++]=nums[j++];
            }
        }
        while(i<=mid)
            array[index++]=nums[i++];
        while(j<=right)
            array[index++]=nums[j++];
        index=0;
        while(left<=right)
        {
            nums[left++]=array[index++];
        }
        return count;

    }
}

k个一组反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0), prev = dummy, curr = head, next;
        dummy.next = head;
        int length = 0;
        while(head != null) {
            length++;
            head = head.next;
        }
        head = dummy.next;
        for(int i = 0; i < length / k; i++) {
            for(int j = 0; j < k - 1; j++) {
                next = curr.next;
                curr.next = next.next;
                next.next = prev.next;
                prev.next = next;
            }
            prev = curr;
            curr = prev.next;
        }
        return dummy.next;
    }
}

删除排序链表中的重复元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        HashSet<Integer> set=new HashSet<>();
        ListNode curr=head;
        ListNode pre=null;
        while(curr!=null)
        {
            if(!set.contains(curr.val))
            {
                set.add(curr.val);
                pre=curr;
            }
            else
            {
                pre.next=curr.next;
            }
            curr=curr.next;
           
        }
        return head;
    }
}

回文链表

可以使用快慢指针，流程分为5步

  1. 找到前半部分链表的尾节点 有两种办法，第一种直接遍历整个链表得
    到链表长度，然后再遍历找到中间位置。第二种方式是通过快慢指针获取
    链表的中间位置，慢指针每次走一步快指针一次走两步，当快指针到达
    末尾时慢指针刚好到终点
  2. 反转后半部分链表 之前有一个反转链表的题
  3. 判断是否回文
  4. 恢复链表
  5. 返回结果
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
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }
        // 找到前半部分链表的尾节点并反转后半部分链表
        ListNode firstHalfEnd = endOfFirstHalf(head);
        ListNode secondHalfStart = reverseList(firstHalfEnd.next);
        // 判断是否回文
        ListNode p1 = head;
        ListNode p2 = secondHalfStart;
        boolean result = true;
        while (result && p2 != null) {
            if (p1.val != p2.val) {
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }        
        // 还原链表并返回结果
        firstHalfEnd.next = reverseList(secondHalfStart);
        return result;
    }
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
    private ListNode endOfFirstHalf(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

复制带随机指针的链表

浅拷贝： 返回地址一样的链表。 深拷贝： 返回地址不一样，但关系一致的链
表。 所以不能直接简单粗暴的遍历复制， 这样出来的复制是一样的地址

二叉树的深度

只使用maxDepth也行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null)
            return 0;
        int height=Math.max(height(root.left),height(root.right))+1;
        return height;
    }
    public int height(TreeNode node)
    {
        if(node==null)
            return 0;
        return Math.max(height(node.left),height(node.right))+1;
    }
}

从上到下打印二叉树

可以用一个flag判断当前行是从左到右还是从右到左

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
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list=new ArrayList<>();
        LinkedList<TreeNode> linklist=new LinkedList<>();
        int length=0;
        if(root!=null)
            linklist.add(root);
        else
            return list;
        length=1;
        boolean flag=true;
        while(linklist.size()!=0){
                ArrayList<Integer> arraylist=new ArrayList<>();
                for(int i=length-1;i>=0;i--){
                    TreeNode temp=linklist.get(i);
                    arraylist.add(temp.val);
                    if(flag){
                    if(temp.left!=null)
                        linklist.add(temp.left);
                    if(temp.right!=null)
                        linklist.add(temp.right);
                    }else{
                        if(temp.right!=null)
                            linklist.add(temp.right);
                        if(temp.left!=null)
                            linklist.add(temp.left);
                    }
                }
                list.add(arraylist);
                int i=0;
                while(i<length)
                {
                    linklist.poll();
                    i++;
                }
                length=linklist.size();
                flag=!flag;
        }
        return list;    
    }
}

二叉树中第k大的节点

差点忘了中序遍历得到的序列就是有序的，稍微调整一下能够变成逆序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    int n;
    int res;
    public int kthLargest(TreeNode root, int k) {
        n=k;
        helper(root);
        return res;
    }
    public void helper(TreeNode node){
        if(node.right!=null&&n>0)
            helper(node.right);
        n--;
        if(n==0)
            { res=node.val;
                 return;
            }
        if(node.left!=null&&n>0)
         helper(node.left);
    }
}

二叉树中和为某一值的路径

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
public List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<List<Integer>> result = new ArrayList<>();
    dfs(root, sum, new ArrayList<>(), result);
    return result;
}

public void dfs(TreeNode root, int sum, List<Integer> list,
                List<List<Integer>> result) {
    //如果节点为空直接返回
    if (root == null)
        return;
    //把当前节点值加入到list中
    list.add(new Integer(root.val));
    //如果到达叶子节点，就不能往下走了，直接return
    if (root.left == null && root.right == null) {
        //如果到达叶子节点，并且sum等于叶子节点的值，说明我们找到了一组，
        //要把它放到result中
        if (sum == root.val)
        	//注意这里必须返回一个新对象，将一条路径上的值都赋值到新对象中
            result.add(new ArrayList(list));
        //注意别忘了把最后加入的结点值给移除掉，因为下一步直接return了，
        //不会再走最后一行的remove了，所以这里在rerurn之前提前把最后
        //一个结点的值给remove掉。
        list.remove(list.size() - 1);
        //到叶子节点之后直接返回，因为在往下就走不动了
        return;
    }
    //如果没到达叶子节点，就继续从他的左右两个子节点往下找，注意到
    //下一步的时候，sum值要减去当前节点的值
    dfs(root.left, sum - root.val, list, result);
    dfs(root.right, sum - root.val, list, result);
    //我们要理解递归的本质，当递归往下传递的时候他最后还是会往回走，
    //我们把这个值使用完之后还要把它给移除，这就是回溯
    list.remove(list.size() - 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
34
35
class Solution {
    private int maxValue = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxValue;
    }

    private int maxGain(TreeNode root){
        if (root.left == null && root.right == null){
            maxValue = root.val > maxValue ? root.val : maxValue;
            return root.val;
        }

        int leftGain = 0;
        int rightGain = 0;
        if (root.left != null)
            leftGain = maxGain(root.left);
        if (root.right != null)
            rightGain = maxGain(root.right);

        leftGain = Math.max(leftGain, 0); // 左子树的收益：若为负则取0
        rightGain = Math.max(rightGain, 0); // // 右子树的收益：若为负则取0

        // 左-中-右情况，不能向上递归
        maxValue = leftGain+rightGain+root.val > maxValue ? leftGain+rightGain
        +root.val : maxValue;

        int maxGain = root.val + Math.max(leftGain, rightGain);
        // 左-中或右-中情况
        maxValue = maxGain > maxValue ? maxGain : maxValue;

        return maxGain;
    }
}

二叉树的右视图

很容易想到层次遍历，但是注意只保留每层最后一个节点

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
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<TreeNode> list=new LinkedList<TreeNode>();
        List<Integer> list2=new LinkedList<>();
        TreeNode node=root;
        if(node==null)
            return list2;
        list.add(root);
        int temp=0;
        while(!list.isEmpty())
        {
            int num=list.size();
            while(num>0){
                node=list.remove(0);
                if(node.left!=null)
			        list.add(node.left);
		        if(node.right!=null)
			        list.add(node.right);
                num--;
                temp=node.val;
            }
            list2.add(temp);
        }
        return list2;

    }
}

最小的k个数

构建小顶堆

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
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int length=arr.length;
        for(int i=length/2-1;i>=0;i--)
	    {
		    sink(arr,i,length);
	    }
        int[] array=new int[k];
        int index=0;
        for(int i=length-1;i>length-1-k;i--)
        {
            array[index++]=arr[0];
            int temp=arr[i];
		    arr[i]=arr[0];
		    arr[0]=temp;
		    sink(arr,0,i);
        }
        return array;
    }
    public void sink(int[] array,int k,int length)
    {
	    for(int j=2*k+1;j<length;j=2*j+1)
	    {
		    //当前节点的子节点中较大的那个节点
		    if(j+1<length&&array[j]>array[j+1])
			    j++;
		    //当前节点与子节点进行比较交换
		    if(array[j]<array[k])
		    {
			    int temp=array[k];
			    array[k]=array[j];
			    array[j]=temp;
		    	k=j;
		    }
		    else
		    {
			    break;
		    }
	}
    }
}

两个栈实现队列

直接使用两个Stack，但是栈底的元素无法删除，所以一个添加栈用来添加
元素，当需要删除元素的时候，就把添加栈的元素转移到删除栈中，此时
元素就已经反转顺序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class CQueue {
    Stack<Integer> stack1,stack2;
    public CQueue() {
        stack1 = new Stack<Integer>();
        stack2 = new Stack<Integer>();
    }
    public void appendTail(int value) {
        stack1.push(value);
    }
    
    public int deleteHead() {
        if(stack1.empty() && stack2.empty()){
            return -1;
        }
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

LRU缓存机制

有时间好好研究一下LinkedHashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class LRUCache {
    int capacity;
    LinkedHashMap<Integer, Integer> cache;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return cache.size() > capacity;
            }
        };
    }
    public int get(int key) {
        return cache.getOrDefault(key, -1);
    }
    public void put(int key, int value) {
        cache.put(key, value);
    }
}
Author: 高明
Link: https://skysea-gaoming.github.io/2020/09/21/LeetCodeandnowcoder2/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
DataStructure