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

LeetCode腾讯精选50题

二叉搜索树的最近公共祖先

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 TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, 
    	TreeNode q) {
       return deep(root,p,q);
    }
    public TreeNode deep(TreeNode node,TreeNode p,TreeNode q)
    {
        if((node.val<=p.val&&node.val>=q.val)||(node.val>=p.val&&
        	node.val<=q.val))
            return node;
        else if(node.val<=p.val&&node.val<=q.val)
        {
            if(node.val==p.val||node.val==q.val)
                return node;
            else
            return deep(node.right,p,q);
        }
        else
        {
            if(node.val==p.val||node.val==q.val)
                return node;
            else
            return deep(node.left,p,q);
        } 
    }
}

多数元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int majorityElement(int[] nums) {
        int num=1;
        int n=nums[0];
        for(int i=1;i<nums.length;i++)
        {
            if(n!=nums[i])
            {
                num--;
                if(num<0){
                    num=0;
                    n=nums[i];
                }
            }
            else
                num++;
        }
        return n;
    }
}

合并两个有序链表

注意不能新建节点

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
class Solution {
  
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    	ListNode pre=new ListNode(0);
    	ListNode prehead=pre;
    	if(l1==null)
            return l2;
        else if(l2==null)
            return l1;
        else{
        	while(l1!=null&&l2!=null){
        	if(l1.val<=l2.val){
        		pre.next=l1;
        		l1=l1.next;
        	}
        	else{
        		pre.next=l2;
        		l2=l2.next;
        	}
        	pre=pre.next;
        }
        if(l1==null)
        	pre.next=l2;
        else
        	pre.next=l1;
       }
       return prehead.next;
    }
    //还要一种递归写法
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    	if(l1==null)
            return l2;
        else if(l2==null)
            return l1;
        else{
        	if(l1.val<=l2.val)
        		l1.next=mergeTwoLists(l1.next,l2);
        	else
        		l2.next=mergeTwoLists(l1,l2.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
34
35
36
class Solution {
    public boolean isPalindrome(int x) {
        if(x<0)
            return false;
        long sum=10;
        int num=1;
        while((x/sum)!=0)
        {
            sum*=10;
            num++;
        }
        int[] array=new int[num];
        int length=num;
        sum=10;
        num=1;
        for(int i=0;i<length;i++)
        {
            array[i]=(int)(x%sum)/num;
            sum*=10;
            num*=10;
        }
        int start=0;
        int end=length-1;
        while(start<end)
        {
            if(array[start]!=array[end])
                return false;
            else
            {
                start++;
                end--;
            }
        }
        return true;
    }
}

买股票的最佳时机

区间和可以转换成求差的问题，求差问题，也可以转换成区间和的问题

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int maxProfit(int[] prices) {
       int num=0;
       int profit=0;
       for(int i=0;i<prices.length-1;i++)
       {
           num=Math.max(0,num+prices[i+1]-prices[i]);
           profit=Math.max(num,profit);
       }
        return profit;
    }
}

相交链表

如果两个链表相交，那么相交点之后的长度是相同的
我们需要做的事情是，让两个链表从同距离末尾同等距离的位置开始遍历。
这个位置只能是较短链表的头结点位置。为此，我们必须消除两个链表的长度差

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode node1=headA;
        ListNode node2=headB;
        while(node1!=node2)
        {
            node1=node1==null?headB:node1.next;
            node2=node2==null?headA:node2.next;
        }
        return node1;
        
    }
}

最小栈

当push（x），x <= min 时先将min进栈，再将x进栈
也就是说在栈中的每一个min下面都存有前一个min（就是比当前min小的那个）

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
class MinStack {
    /** initialize your data structure here. */
    Stack<Integer> stack;
    int min;
    public MinStack() {
        stack=new Stack<>();
        min=Integer.MAX_VALUE;
    }
    
    public void push(int x) {
       if(min>=x)
       {
           stack.push(min);
           min=x;
       }
        stack.push(x);
    }
    
    public void pop() {
        if(stack.pop()==min)
            min=stack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return min;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

存在重复元素

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> set=new HashSet<>();
        for(int i=0;i<nums.length;i++)
        {
            if(set.contains(nums[i]))
                return true;
            else
                set.add(nums[i]);
        }
        return false;
    }
}

最大子序和

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

删除排序数组中的重复项

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 removeDuplicates(int[] nums) {
        if(nums.length==0)
            return 0;
        int index=0;
        int value=nums[0];
        for(int i=0;i<nums.length;i++)
        {
            if(nums[i]==value)
            {
                continue;
            }
            else
            {
                index++;
                nums[index]=nums[i];
                value=nums[i];
            }
        }
        return index+1;
    }
}

爬楼梯

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int climbStairs(int n) {
        int[] dp=new int[n+1];
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=n;i++)
        {
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
}

2的幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean isPowerOfTwo(int n) {
        if(n<=0)
            return false;
        while(true)
        {
            if(n==1)
                break;
            if(n%2==0)
            {
                n=n/2;
            }
            else
                return false;
        }
        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
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null)
            return false;
        ListNode node=head;
        ListNode first=head;
        ListNode second=head;
        while(true)
        {
            if(first.next!=null)
                first=first.next;
            else
                return false;
            if(second.next!=null)
            {
                if(second.next.next!=null)
                    second=second.next.next;
                else
                    return false;
            }
            else
                return false;
            if(first==second)
                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
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for(int i=m-1;i>=0;i--)
        {
            nums1[i+n]=nums1[i];
        }
        int index1=0;
        int index2=0;
        int index3=n;
        while(index3<m+n&&index2<n)
        {
            if(nums1[index3]<nums2[index2])
                nums1[index1++]=nums1[index3++];
            else
                nums1[index1++]=nums2[index2++];
        }
        while(index3<m+n)
            nums1[index1++]=nums1[index3++];
        while(index2<n)
            nums1[index1++]=nums2[index2++];
        
    }
}

有效的括号

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 boolean isValid(String s) {
        if(s.length()%2!=0)
            return false;
        Stack<Character> stack=new Stack<>();
        for(int i=0;i<s.length();i++)
        {
            char ch=s.charAt(i);
            if(ch=='(')
                stack.push(')');
            else if(ch=='{')
                stack.push('}');
            else if(ch=='[')
                stack.push(']');
            else
            {
                if(stack.size()==0)
                    return false;
                char cc=stack.pop();
                if(cc!=ch)
                    return false;
            }
        }
        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
class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length==0)
            return "";
        int length=strs[0].length();
        for(int i=1;i<strs.length;i++)
        {
            if(strs[i].length()<length)
                length=strs[i].length();
        }
        char[] array=new char[length];
        int index=0;
        boolean flag=true;
        for(int i=0;i<length;i++)
        {
            char ch=strs[0].charAt(i);
            for(int j=1;j<strs.length;j++)
            {
                if(strs[j].charAt(i)!=ch)
                {
                    flag=false;
                    break;
                }
            }
            if(flag==false)
                break;
            array[i]=ch;
            index++;
        }
        return new String(array,0,index);
    }
}

整数反转

这题有点麻烦

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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 /= 10;
        }
        return ans;
    }
}

子集

这题的思路非常巧妙，主要体现在遍历的设计上，先是添加空数组，然后将每一个
元素加入，十分巧妙，遍历时每遇到一个数就把该数加到所有子集中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>());
        for (int i = 0; i < nums.length; i++) {
           int all = res.size();
            for (int j = 0; j < all; j++) {
                List<Integer> tmp = new ArrayList<>(res.get(j));
                tmp.add(nums[i]);
                res.add(tmp);
            }
        }
        return res;
    }
}

螺旋矩阵II

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
class Solution {
    public int[][] generateMatrix(int n) {
      
        int[][] array=new int[n][n];
        for(int i=0;i<n;i++)
            array[i]=new int[n];
        int circlenum=0;
        if(n%2==0)
            circlenum=n/2;
        else 
            circlenum=n/2+1;
        int index=1;
        for(int i=0;i<circlenum;i++)
        {
            
            for(int j=i;j<n-i;j++)
            {
                array[i][j]=index++;
            }
            for(int j=i+1;j<n-i-1;j++)
            {
                array[j][n-1-i]=index++;
            }
            for(int j=n-i-1;j>=i;j--)
            {
                array[n-i-1][j]=index++;
            }
            for(int j=n-i-2;j>=i+1;j--)
            {
                array[j][i]=index++;
            }
           
        }
        if(n%2!=0)
            array[n/2][n/2]--;
        return array;
    }
}

全排列

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
class Solution {
    List<List<Integer>> list=new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        for(int i=0;i<nums.length;i++)
        {
            ArrayList<Integer> array=new ArrayList<>();
            array.add(nums[i]);
            cut(array,nums);
        }
        return list;
    }
    public void cut(ArrayList<Integer> array,int[] nums)
    {
        if(array.size()==nums.length)
        {
            list.add(new ArrayList<Integer>(array));
            return ;
        }
        for(int i=0;i<nums.length;i++)
        {
            if(!array.contains(nums[i]))
            {
                array.add(nums[i]);
                cut(array,nums);
                array.remove(array.size()-1);
            }
        }
    }
}

二叉搜索树中第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
class Solution {
    int index=0;
    public int kthSmallest(TreeNode root, int k) {
        int num=sum(root);
        int[] array=new int[num];
        search(root,array);
        return array[k-1];
    }
    public void search(TreeNode node,int[] array)
    {
        if(node==null)
            return ;
        search(node.left,array);
        array[index++]=node.val;
        search(node.right,array);
    }
    public int sum(TreeNode node)
    {
        if(node==null)
            return 0;
        else
            return sum(node.left)+sum(node.right)+1;
    }
}

除自身以外数组的乘积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] array=new int[nums.length];
        int help=1;
        for(int i=0;i<nums.length;i++)
        {
            array[i]=help;
            help*=nums[i];
        }
        help=1;
        for(int i=nums.length-1;i>=0;i--)
        {
            array[i]*=help;
            help*=nums[i];
        }
        return array;
    }
}

盛最多水的容器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maxArea(int[] height) {
        int left=0;
        int right=height.length-1;
        int min=height[right]<height[left]?height[right]:height[left];
        int max=(right-left)*min;
        while(left<right)
        {
            if(height[left]<height[right])
                left++;
            else
                right--;
            min=height[left]<height[right]?height[left]:height[right];
            if(max<min*(right-left))
                max=min*(right-left);
        }
        return max;
    }
}

数组中第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
class Solution {
    public int findKthLargest(int[] nums, int k) {
    for(int i=nums.length/2-1;i>=0;i--)
	  {
		sink(nums,i,nums.length);
	  }
	for(int i=nums.length-1;i>nums.length-1-k;i--)
	  {
		int temp=nums[i];
		nums[i]=nums[0];
		nums[0]=temp;
		sink(nums,0,i);
	  }
        return nums[nums.length-k];
        
    }
    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;
		}
	}
}
}

不同路径

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int uniquePaths(int m, int n) {
        int[][] array=new int[m][n];
        for(int i=0;i<m;i++)
        array[i][0]=1;
        for(int j=0;j<n;j++)
        array[0][j]=1;
        for(int i=1;i<m;i++)
            for(int j=1;j<n;j++)
             array[i][j]=array[i-1][j]+array[i][j-1];
        return array[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
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
74
75
76
77
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
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;
    }
}

寻找两个正序数组的中位数

这个题如果要求时间复杂度为O(m+n)其实很简单，就是直接通过遍历比
较找到中间位置，但是时间复杂度要求为O(log(m+n))，应该联想到用
二分思想，首先要分奇偶来求出中位数，参考力扣一个大牛的话(m+n+1)
和(m+n+2)取平均值可以消除奇偶的影响，首先考虑如何找到数组中第k
个元素，一种思路是双指针进行比较求得第k个元素，但是时间复杂度为
O(m+n)，如果利用二分查找，先分别在两个数组中找到第k/2个元素，
比较这两个元素比如nums1[k/2] < nums2[k/2]，那么nums1数组前k/2个
一定不存在第k个元素，此时删除nums1前k/2个元素，然后继续找，这个时
候实际找的是第k-k/2个元素，因为k/2个元素已经被除去了嘛，所以接下
来查找的范围就会越来越小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
  public double findMedianSortedArrays(int[] nums1, int[] nums2) {
      int m=nums1.length;
      int n=nums2.length;
      int left=(m+n+1)/2;
      int right=(m+n+2)/2;
      return (findk(nums1,0,nums2,0,left)+findk(nums1,0,nums2,0,right))/2.0;
  }
  public int findk(int[] nums1,int i,int[] nums2,int j,int k)
  {
      if(i>=nums1.length)
        return nums2[j+k-1];
      if(j>=nums2.length)
        return nums1[i+k-1];
      if(k==1)
        return Math.min(nums1[i],nums2[j]);
      int midindex1=(i+k/2-1<nums1.length)?nums1[i+k/2-1]:Integer.MAX_VALUE;
      int midindex2=(j+k/2-1<nums2.length)?nums2[j+k/2-1]:Integer.MAX_VALUE;
      if(midindex1<midindex2)
        return findk(nums1,i+k/2,nums2,j,k-k/2);
      else
        return findk(nums1,i,nums2,j+k/2,k-k/2);
  }
}

动态规划

比特位计数

这是一道典型的动态规划题，我一开始想找相邻两个数之间的关系结果不行，一个
大牛的解法就是对于一个二进制数来说，如果它的最低位为1（%2为1）,则它与
n/2的1个数相差1。如果它的最低位为0，则它与n/2的1个数相同。有些动态规划题
并不一定是相邻的数之间有关系也有可能有间隔

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int[] countBits(int num) {
        int[] array=new int[num+1];
        for(int i=0;i<=num/2;i++)
            {
                array[i*2]=array[i];
                if(i*2+1<=num)
                    array[i*2+1]=array[i]+1;
            }
        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 maxSatisfaction(int[] satisfaction) {
        Arrays.sort(satisfaction);
        int num=0;
        int max=0;
        int sum=0;
        for(int i=satisfaction.length-1;i>=0;i--)
        {
            if(num>=0)
            {       
                num=num+satisfaction[i]+sum;
                sum+=satisfaction[i];
                max=Math.max(num,max);
            }
            else
                break;
        }
        return max;
    }
}

除数博弈

这个题是真的有意思，我一开始一直想两个人都是最佳状态该怎么解决，
我想Alice先拿一个数然后Bob有好几种拿法，然后再次进行递归直到有
一个人拿不了，但是这个问题就是都处于最佳状态我就没法解决了，如
果题目改一下改为有没有赢的可能我的思路就是对的

1
2
3
4
5
class Solution {
    public boolean divisorGame(int N) {
        return N % 2 == 0;
    }
}

爬楼梯

直接递归会爆栈，动态规划的一大特点就是子问题的解具有记忆性，完全
可以非递归解

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int climbStairs(int n) {
        int[] array=new int[n+1];
        array[0]=1;
        array[1]=1;
        for(int i=2;i<=n;i++)
            array[i]=array[i-1]+array[i-2];
        return array[n];
    }
}

最长湍流子数组

核心就是找当前状态与前一个状态的关系，推导关系公式
dp[i]=dp[i-1]+1 满足条件时
dp[i]=1/2/dp[i] 分情况讨论即可

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 {
    public int maxTurbulenceSize(int[] A) {
        int[] dp=new int[A.length];
        dp[0]=1;
        int max=1;
        if(A.length>1)
        {
            if(A[1]==A[0])
                dp[1]=1;
            else
                {
                    dp[1]=2;
                    max=2;
                }
        }
        for(int i=2;i<A.length;i++)
        {
            int num1=A[i]-A[i-1];
            int num2=A[i-2]-A[i-1];
            if((num1>0&&num2>0)||(num1<0&&num2<0))
                dp[i]=dp[i-1]+1;
            else if((num1>0&&num2<0)||(num1<0&&num2>0))
                dp[i]=2;
            else
            {
                if(num1==0)
                    dp[i]=1;
                else
                    dp[i]=2;
            }
            max=Math.max(max,dp[i]);
        }
        return max;
    }
}

最小路径和

当前位置与上一个和左一个位置的关系

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 int minPathSum(int[][] grid) {
        int num=0;
        int[][] dp=new int[grid.length][grid[0].length];
        dp[0][0]=grid[0][0];
        for(int i=1;i<grid.length;i++)
        {
            dp[i][0]=grid[i][0]+dp[i-1][0];
        }
        for(int i=1;i<grid[0].length;i++)
        {
            dp[0][i]=grid[0][i]+dp[0][i-1];
        }
        for(int i=1;i<grid.length;i++)
        {
            for(int j=1;j<grid[0].length;j++)
            {
                dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[grid.length-1][grid[0].length-1];
    }
}

不同路径

同上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp=new int[m][n];
        dp[0][0]=1;
        for(int i=1;i<n;i++)
            dp[0][i]=1;
        for(int j=1;j<m;j++)
            dp[j][0]=1;
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
        }
        return dp[m-1][n-1];
    }
}

使用最小花费爬楼梯

核心就是找到当前状态与前一个和前两个之间的关系，先得到小问题
的解，小问题是最优解最后累积为大问题的解

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp=new int[cost.length+1];
        if(cost.length>2)
            dp[2]=cost[0]>cost[1]?cost[1]:cost[0];
        for(int i=3;i<=cost.length;i++)
            dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        return dp[cost.length];
    }
}

乘积最大子数组

核心思路就是以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 maxProduct(int[] nums) {
        int max=nums[0];
        int num=1;
        for(int i=0;i<nums.length;i++)
        {
            num*=nums[i];
            max=Math.max(num,max);
            if(nums[i]==0)
                num=1;
        }
        num=1;
        for(int i=nums.length-1;i>=0;i--)
        {
            num*=nums[i];
            max=Math.max(num,max);
            if(nums[i]==0)
                num=1;
        }
        return max;
    }
}

不同路径II

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
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int[][] dp=new int[obstacleGrid.length][obstacleGrid[0].length];
        int num=1;
        if(obstacleGrid[0][0]==0)
            dp[0][0]=1;
        else
            return 0;
        for(int i=1;i<obstacleGrid.length;i++)
        {
            if(obstacleGrid[i][0]==1)
                num=0;
            dp[i][0]=num;
        }
        num=1;
        for(int i=1;i<obstacleGrid[0].length;i++)
        {
            if(obstacleGrid[0][i]==1)
                num=0;
            dp[0][i]=num;
        }
        for(int i=1;i<obstacleGrid.length;i++)
        {
            for(int j=1;j<obstacleGrid[0].length;j++)
            {
                if(obstacleGrid[i][j]==1)
                    dp[i][j]=0;
                else
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[dp.length-1][dp[0].length-1];
    }
}

最大子序和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxSubArray(int[] nums) {
        int max=nums[0];
        int num=0;
        for(int i=0;i<nums.length;i++)
        {
            if(num>=0)
                num+=nums[i];
            else
                num=nums[i];
            max=Math.max(max,num);
        }
        return max;
    }
}

贪心算法

交换一次的先前排列

这道题应该从后往前找而不是从前往后找，注意是要小于原数组的最大数组，如果
从前往后就不满足条件

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
class Solution {
    public int[] prevPermOpt1(int[] A) {
      int len = A.length;
        if(len==1)
            return A;
        //1.从后往前找，如果是A[i]>=A[i-1]则继续
        //2. 碰到A[i]<A[i-1]记录下需要交换的位置
        //3. 找到比他小的再交换即可(需要找到位置最前的元素)
        for(int i = len-1;i > 0;i--){
            while(i>0&&A[i]>=A[i-1])
                i--;
            if(i==0)
                return A;
            for(int j = len-1;j >= i;j--){//注意此处的边界
                if(A[j]<A[i-1]){
                    //swap(A,i-1,j);
                    int tmp = j;
                    for(int k = j-1;k>=i;k--){
                        if(A[k]==A[j])
                            tmp = k;
                    }
                    swap(A,tmp,i-1);
                    return A;
                }
            }
        }
        return A;
    }
    public void swap(int[] A,int i,int j){
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }
}

跳跃游戏

这道题的核心就是说从倒数第二个位置开始向左遍历，如果这个位置能够到达
最后指定位置，继续向左遍历，既然要到最后一个位置，那么如果能够达到在
这之前的位置，一直不断放宽条件

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public boolean canJump(int[] nums) {
        int last=nums.length-1;
        for(int i=nums.length-1;i>=0;i--)
        {
            if(i+nums[i]>=last)
                last=i;
        }
        return last==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
32
33
34
35
class Solution {
    public int minDominoRotations(int[] A, int[] B) {
        int[] array1=new int[7];
        int[] array2=new int[7];
        for(int i=0;i<A.length;i++)
        {
            array1[A[i]]++;
            array2[B[i]]++;
        }
        boolean flag=false;
        for(int i=1;i<=6;i++)
        {
            flag=false;
            if(array1[i]+array2[i]>=A.length)
            {
                for(int j=0;j<A.length;j++)
                {
                    if(A[j]!=i&&B[j]!=i)
                        {
                            flag=true;
                            break;
                        }
                }
                if(flag)
                    break;
                else
                {
                    int min=Math.min(A.length-array1[i],A.length-array2[i]);
                    return min;
                }
            }
        }
        return -1;
    }
}

树

二叉树的最大深度

这道题使用递归比较清晰

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

二叉搜索树的最近公共祖先

利用二叉搜索树的性质，左子节点的值小于父节点值，父节点值小于右子节点值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, 
    	TreeNode q) {
        return search(root,p,q);
    }
    public TreeNode search(TreeNode node,TreeNode p,TreeNode q)
    {
        if((node.val>=p.val&&node.val<=q.val)||
        (node.val>=q.val&&node.val<=p.val))
            return node;
        else if(node.val<p.val&&node.val<q.val)
            return search(node.right,p,q);
        else 
            return search(node.left,p,q);
    }
}

二叉搜索树中第K小的元素

最简单的思路就是层次遍历得到所有节点值保存在数组，然后数据排序就可以
得到指定的值。看到一个大牛的思路很好，左子树的节点个数是leftN，如果
k<=leftN那么所查找的节点在左子树上，如果k=leftN+1那么这个节点就是
要查找的节点，如果k>leftN+1那么所查找的节点在右子树上，那么就继续
与k-leftN比较。官方的解法是利用中序遍历，因为中序遍历的结果就是一
个升序的序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        int num=sum(root.left);
        if(num+1==k)
            return root.val;
        else if(num>=k)
            return kthSmallest(root.left,k);
        else
            return kthSmallest(root.right,k-num-1);
    }
    public int sum(TreeNode node)
    {
        if(node==null)
            return 0;
        else
            return sum(node.left)+sum(node.right)+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
36
37
38
39
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length<=0)
            return null;
        TreeNode root=new TreeNode(preorder[0]);
        int index=-1;
        for(int i=0;i<inorder.length;i++)
           { if(preorder[0]==inorder[i])
            {
                index=i;
                break;
            }
           }
        root.left=sear(1,index,0,index-1,preorder,inorder);
        root.right=sear(index+1,preorder.length-1,index+1,
        	inorder.length-1,preorder,inorder);
        return root;
    }
    public TreeNode sear(int left1,int right1,int left2,int right2,
    int[] preorder,int[] inorder)
    {
        if(left1>right1||left2>right2)
            return null;
        TreeNode node=new TreeNode(preorder[left1]);
        int index=left1;
        for(int i=left2;i<=right2;i++)
            {if(preorder[left1]==inorder[i])
            {
                index=i;
                break;
            }
            }
        node.left=sear(left1+1,left1+index-left2,left2,index-1,preorder
        ,inorder);
        node.right=sear(left1+1+index-left2,right1,index+1,right2
        ,preorder,inorder);
        return 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
37
38
39
40
41
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder.length<=0)
            return null;
        TreeNode root=new TreeNode(postorder[postorder.length-1]);
        int index=-1;
        for(int i=0;i<inorder.length;i++)
        {
            if(postorder[postorder.length-1]==inorder[i])
            {
                index=i;
                break;
            }
        }
        root.left=sear(0,index-1,0,index-1,inorder,postorder);
        root.right=sear(index+1,inorder.length-1,index,inorder.length-2,
        inorder,postorder);
        return root;
    }
    public TreeNode sear(int left1,int right1,int left2,int right2,
    int[] inorder,int[] postorder)
    {
        if(left1>right1||left2>right2)
            return null;
        TreeNode node=new TreeNode(postorder[right2]);
        int index=left1;
        for(int i=left1;i<=right1;i++)
        {
            if(inorder[i]==postorder[right2])
            {
                index=i;
                break;
            }
        }
        node.left=sear(left1,index-1,left2,left2+index-1-left1,inorder,
        postorder);
        node.right=sear(index+1,right1,left2+index-left1,right2-1,
        inorder,postorder);
        return node;
    }
}
Author: 高明
Link: https://skysea-gaoming.github.io/2020/02/28/LeetCodeandnowcoder/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
DataStructure