20-5-9 LC（数组/链表）

标签：sqrt   归并   计算   rtl   实现   部分   就是   next   i++   

每日一题

实现?int sqrt(int x)?函数。
计算并返回?x?的平方根，其中?x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

思路

牛顿迭代 x=(x+a/x)
二分的初始区间取0-x/2，因为输入的x是整数。

牛顿迭代

class Solution {
    int a;
    public int mySqrt(int x) {
        if(x==0)return 0;
        a=x;
        return (int)sqrts(x);
    }
    double sqrts(double x){
        double ans=(x+a/x)/2;
        if(ans==x)return x;
        else return sqrts(ans);
    }
}

二分法

class Solution {
    public int mySqrt(int x) {
        long left=0,right=x/2;
        while(left

300. 最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。

解题思路

1.暴力

2.dp，dp[i]表示以第i个元素为结尾的最长子序列的值，j

3.二分，一次遍历，用一个dp[i]保存长度为i的子序列的最后一个元素，采用贪心的思想，每次保存的元素都要是最小的，如果nums[i]>nums[len]的话，
这里len代表当前最长子序列的长度，dp[len]就是最长子序列的最后一个元素，将len++，再把dp[len]=nums[i]。要是小于或者等于的话，我们就len不变，但是通过二分查找，把dp[1]-dp[len]中某个坐标为index的小于nums[i]的数给换掉。满足dp[index]4，数组变[0,2,4]，这样如果接下来来了个nums[i]=5，长度就能增加1，不然还是[0,2,6]的话答案就不正确了。

暴力

class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums==null||nums.length==0)return 0;
        int[] max=new int[nums.length];
        int ans=1;
        for(int i=nums.length-1;i>=0;i--){
            int t=0;
            for(int j=i+1;jnums[i]&&max[j]>t){
                    t=max[j];
                }
            }
            max[i]=t+1;
            ans=Math.max(ans,max[i]);
        }
        return ans;
    }
}

dp

class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums==null||nums.length==0)return 0;
        int ans=1;
        int[] dp=new int[nums.length];
        Arrays.fill(dp,1);
        for(int i=0;i

二分

class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums==null||nums.length==0)return 0;
        int[] dp=new int[nums.length+1];
        int len=1;
        dp[1]=nums[0];
        for(int i=1;idp[len]){
                len++;
                dp[len]=nums[i];
            }else{
                int l=1,r=len,pos=0;
                while(l

279. 完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

思路

此题因为完全平方可以取n种，所以不能采用贪心的思想，只能dp，枚举所有小于i的可能

class Solution {
    public int numSquares(int n) {
        if(n

148. 排序链表(归并排序)

递归法

class Solution {
    public ListNode sortList(ListNode head) {
        if(head==null||head.next==null)return head;       
        return mergeSort(head);
    }
    ListNode mergeSort(ListNode head){
        if(head==null)return null;
        if(head.next==null)return head;
        ListNode fast=head.next;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        ListNode head2=slow.next;
        slow.next=null;
        ListNode left=mergeSort(head);
        ListNode right=mergeSort(head2);
        return merge(left,right);
    }
    ListNode merge(ListNode l1,ListNode l2){
        if(l1==null||l2==null)return (l1==null)?l2:l1;
        ListNode pre=new ListNode(0);
        ListNode cur=pre;
        while(l1!=null&&l2!=null){
            if(l1.val

迭代

class Solution {
    public ListNode sortList(ListNode head) {
        if(head==null||head.next==null)return head;
        ListNode fast=head.next;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        ListNode head2=slow.next;
        slow.next=null;
        ListNode l1=sortList(head);
        ListNode l2=sortList(head2);
        if(l1==null||l2==null)return (l1==null)?l2:l1;
        ListNode pre=new ListNode(0);
        ListNode cur=pre;
        while(l1!=null&&l2!=null){
            if(l1.val

20-5-9 LC（数组/链表）

标签：sqrt   归并   计算   rtl   实现   部分   就是   next   i++   

原文地址：https://www.cnblogs.com/k-will/p/12860571.html