2021-07-07算法题

1. x的平方根（*）

   
   
   image.png
   
   

   思路：由于x的平方根的整数部分是满足k^2≤x 的最大k值，因此我们可以对 k 进行二分查找，从而得到答案。使用二分法，不断缩小范围

class Solution {
    public int mySqrt(int x) {
        int l = 0, r = x, ans = -1;
        while (l <= r) {
            int mid = (r + l) / 2;
            if ((long) mid * mid <= x) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
}

2. 爬楼梯

   
   
   image.png
   
   

   思路：

3. 删除排序链表中的重复元素（*）

   
   
   image.png
   
   

   思路：当L结点与其下一个结点的值相同时，将L的next链接到L的next的next，否则L=L.next（注意：while循环中要判断L.next是否为nul）

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode l = head;
        while (l!= null) {
            if(l.next==null){
                return head;
            }
            if (l.val == l.next.val) {
                l.next = l.next.next;
            } else {
                l = l.next;
            }
        }
        return head;
    }
}