70、爬楼梯

这个题目最开始想的是找规律，从计算步骤中找到规律，发现这个规律不是很好总结，所以就改成了回溯，当n=35时就会超时，在回溯的for里面做了剪枝处理，结果也不尽如人意，因为那个for只是遍历1和2，重点还是调用回溯方法的那个for

最后没想到是道数学题，无语子、、、是一个斐波那契

class Solution {
    int count=0;
    public int climbStairs(int n) {
        if(n<=3) return n;
        int result=0;

        for (int i = n/2+1; i <= n - 1; i++) {
            backup(i,0,n,0);
            result+=count;
            count=0;
        }
        if(n%2==0){
            return result+2;
        }else {
            return result+1;
        }
    }

    public void backup(int length,int i,int n,int sum){
        if(i>length || sum>n) return;
        if(sum==n && i==length) count++;
        for (int j = 1; j <= 2; j++) {
            i++;
            sum+=j;
            backup(length,i,n,sum);
            i--;
            sum-=j;
            if(sum+j>=n) break;
        }

    }
}

斐波那契的代码:

class Solution {
    public int climbStairs(int n) {
        int a = 1, b = 1, sum;
        for(int i = 0; i < n - 1; i++){
            sum = a + b;
            a = b;
            b = sum;
        }
        return b;
    }
}

作者：Krahets
链接：https://leetcode.cn/problems/climbing-stairs/solutions/2361764/70-pa-lou-ti-dong-tai-gui-hua-qing-xi-tu-ruwa/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

69、x的平方根

这个题我昨天也在琢磨规律，但是，果不其然，从小奥数就不行的我果然也没搞出来

用了二分查找、、、我是个笨蛋吧

public class Solution {

    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        if (x == 1) {
            return 1;
        }

        int left = 1;
        int right = x / 2;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (mid > x / mid) {
                right = mid - 1;
            } else if (mid == x / mid) {
                // 由于本题特殊性，如果 mid == x / mid 就找到了答案，其它问题不一定可以这样
                return mid;
            } else {
                left = mid;
            }
        }
        return left;
    }
}

作者：liweiwei1419
链接：https://leetcode.cn/problems/sqrtx/solutions/7866/er-fen-cha-zhao-niu-dun-fa-python-dai-ma-by-liweiw/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

71、简化路径

代码是越写越轻车熟路了，问题就是，时间复杂度不行，我看了别人的代码，原本以为自己的思路不行，现在看来是自己写法
我的代码：

class Solution {
      public String simplifyPath(String path) {
        String[] split = path.split("/");
        Stack<String> stack=new Stack<>();
        for (String s : split) {
            if(!s.isEmpty()){
                if(s.equals(".")) continue;
                if(s.equals("..")){
                    if(stack.isEmpty()) continue;
                    stack.pop();
                }else {
                    stack.push(s);
                }
            }
        }
        if(stack.isEmpty()) return "/";
        String result = new String();
        for (String s : stack) {
            result=result+"/"+s;
        }
        return result;
    }
}

别人的：
他这个代码用的Deque,然后也没有用string的split()方法，是自己手写实现的，其次就是最后用的StringBuilder

class Solution {
    public String simplifyPath(String path) {
        int length = path.length();
        Deque<String> stack = new ArrayDeque<>();
        int i = 0;
        while (i < length) {
            int s;
            while (i < length && path.charAt(i) == '/') {
                i++;
            }
            s = i;
            while (i < length && path.charAt(i) != '/') {
                i++;
            }
            String dir = path.substring(s, i);
            if (dir.isEmpty() || ".".equals(dir)) {
                continue;
            }
            if ("..".equals(dir)) {
                stack.poll();
            } else {
                stack.push(dir);
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append('/').append(stack.pollLast());
        }
        return sb.length() == 0 ? "/" : sb.toString();
    }
}

项目和力扣算法真是相辅相成啊，继续努力吧~~
感觉现在写算法题目已经没有以前那么吃力了、、