星期五啦，趕了一下課程作業(yè)，今天寫的題不多，明天加油！

69. x 的平方根

給你一個非負整數(shù) x ，計算并返回 x 的 算術(shù)平方根 。

 

由于返回類型是整數(shù)，結(jié)果只保留 整數(shù)部分 ，小數(shù)部分將被 舍去 。

 

注意：不允許使用任何內(nèi)置指數(shù)函數(shù)和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

 

 

 

來源：力扣（LeetCode）

鏈接：https://leetcode-cn.com/problems/sqrtx

示例 2：

輸入：x = 8輸出：2解釋：8 的算術(shù)平方根是 2.82842..., 由于返回類型是整數(shù)，小數(shù)部分將被舍去。

大早上看到這么道題我以為我沒睡醒，總之就是一行結(jié)束。

class Solution {

    public int mySqrt(int x) {

        int ans;

        return ans=(int)Math.sqrt(x);

    }

}

看了一眼大家的題解，謝謝java的MAth類！！嘿嘿我就說嘛，java還是比較智能的啦（變臉怪

 

70. 爬樓梯

假設(shè)你正在爬樓梯。需要 n 階你才能到達樓頂。

每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？

 示例 1：

輸入：n = 2輸出：2解釋：有兩種方法可以爬到樓頂。

1. 1 階 + 1 階

2. 2 階

在給出范例的基礎(chǔ)上我又多算了幾個，發(fā)現(xiàn)f(1)=1,f(2)=2,f(3)=3,f(4)=5,f(5)=8,f(6)=13.

可以明顯得出一個猜想，f(n)=f(n-1)+f(n-2).喚醒了很久以前的斐波那契數(shù)列記憶，很快寫出了如下代碼：

class Solution {

    public int climbStairs(int n) {

        return f(n);

    }

    public int f(int x){

        if(x==1) return 1;

        if(x==2) return 2;

        return f(x-1)+f(x-2);

    }

}

 

我依然記得遞歸的最大問題是時間太久，但我抱著試一試的心理提交了，果然超出時間限制了。仔細挖掘了一下記憶，當時為了解決這個問題是讓給我們將已經(jīng)算出的結(jié)果存入數(shù)組，后面直接調(diào)用。

于是有了如下時間直接0ms的解答：

class Solution {

    public int climbStairs(int n) {

        return f(n);

    }

    public int f(int x){

        int[] num=new int[45];

        int ans=0;

        num[0]=1;

        num[1]=2;

        for(int i=2;i<x;i++){

            num[i]=num[i-1]+num[i-2];

        }

        

        return num[x-1];

    }

}

其實有點意識到這是個動態(tài)規(guī)劃問題，但還是對這個概念比較模糊。。

3. 無重復字符的最長子串

給定一個字符串 s ，請你找出其中不含有重復字符的 最長子串 的長度。

示例 1:

輸入: s = "abcabcbb"

輸出: 3

解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3。

 

來源：力扣（LeetCode）

鏈接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

根據(jù)錯誤的地方小改了幾次，最后的思路為：遍歷字符串，設(shè)置答案字符串先為s[0]，記錄子串最大值的變量max為1，后經(jīng)歷遍歷在每一次的判斷中先用indexOf函數(shù)在ans字符串中查看是否有當前成員，若沒有則直接加上即可，若有，則取其index，將字符串在index處截斷，刪掉前面保留后面并加入當前成員進入ans字符串，在每次循環(huán)的最后比較當前ans的長度和現(xiàn)max的值，更新max。最后返回max即可。這次的思路其實是參考了之前一次的某個大佬的思路，也算融會貫通學到了點東西

代碼如下：

class Solution {

    public int lengthOfLongestSubstring(String s) {

        if(s.length()==0) return 0;

        String ans=String.valueOf(s.charAt(0));

        int max=1;

        for(int i=1;i<s.length();i++){

            if(ans.indexOf(s.charAt(i))==-1){

                ans=ans+String.valueOf(s.charAt(i));

            } else{

                int n=ans.indexOf(s.charAt(i));

                ans=ans.substring(n+1)+s.charAt(i);

            }

            max=Math.max(ans.length(),max);

        }

        return max;

    }

}