1.x的平方根
java
（1）直接使用函数
class Solution { public int mySqrt(int x) { int rs = 0; rs = (int)Math.sqrt(x); return rs; } }
（2）二分法
对于一个非负数n，它的平方根不会小于大于（n/2+1）。
在[0, n/2+1]这个范围内可以进行二分搜索，求出n的平方根。
class Solution { public int mySqrt(int x) { long left=1,right=x; while(left<right){ long mid = left+(right-left)/2; long sq = mid*mid; if(sq==x){ return (int)mid; }else if(sq<x){ left = mid+1; }else{ right = mid-1; } } if(left*left>x){ left--; } return (int)left; } }
（3）牛顿迭代法
牛顿法是一种在实数域和复数域上近似求解方程的方法。
方法使用函数 f(x)的泰勒级数的前面几项来寻找方程f(x)=0的根。
选择一个接近函数f(x)零点的x0,计算相应的f(x0)和切线斜率f'(x0)（这里f'表示函数f的导数)。
也就是求如下方程的解：
将新求得的点 x坐标命名为x1，通常x1会比x0更接近方程f(x)=0的解。因此可以利用x1开始下一轮迭代。
迭代公式可化简为如下所示：
计算x2 = a的解,可以看成f(x) =x2 - a，a即为要求平方根
xn+1 = xn -(xn2 - a) / (2xn) = (xn+ a/xn) / 2
class Solution { public int mySqrt(int x) { if(x==0) return 0; double last = 0; double res = 1; while(res!=last){ last = res; res =(res+x/res)/2; } return (int)res; } }
php
class Solution { /** * @param Integer $x * @return Integer */ function mySqrt($x) { $rs = sqrt($x); return floor($rs); } }
2.爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1： 输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶 示例 2： 输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
斐波那契数列：
设跳n个台阶有f(n)种方法，
爬1个：1种
爬2个：2种
爬n个：面临两种选择：
（1） 第一次爬1个，此时剩余n-1个台阶，有f(n-1)种方法
（2） 第一次爬2个，此时剩余n-2个台阶，有f(n-2)种方法
所以f(n) = f(n-1) + f(n-2)
java
class Solution { public int climbStairs(int n) { if(n<=2) return n; int num1 = 1; int num2 = 2; int numN = 0; for(int i =2;i<n;i++){ numN = num1+num2; num1 = num2; num2 = numN; } return numN; } }
php
class Solution { /** * @param Integer $n * @return Integer */ function climbStairs($n) { if($n<=2) return $n; $num1=1; $num2=2; $numN = 0; for($i=2;$i<$n;$i++){ $numN = $num1+$num2; $num1 = $num2; $num2 = $numN; } return $numN; } }
3.删除排序链表中的重复元素
java
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode deleteDuplicates(ListNode head) { if(head==null||head.next==null) return head; ListNode res = head; ListNode cur = head; ListNode next = head.next; while(next!=null){ if(next.val==cur.val){ cur.next = null; }else{ cur.next = next; cur = next; } next = next.next; } return res; } }
php
/** * Definition for a singly-linked list. * class ListNode { * public $val = 0; * public $next = null; * function __construct($val) { $this->val = $val; } * } */ class Solution { /** * @param ListNode $head * @return ListNode */ function deleteDuplicates($head) { if($head==null||$head->next==null) return $head; $res = $head; $cur = $head; $next = $head->next; while($next){ if($cur->val!=$next->val){ $cur->next = $next; $cur = $next; }else{ $cur->next = null; } $next = $next->next; } return $res; } }
4.合并两个有序数组
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
说明:
- 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
- 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例:
输入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 输出: [1,2,2,3,5,6]
java
class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { if(n==0) return; int len = m+n-1; while(m>0&&n>0){ if(nums1[m-1]>nums2[n-1]){ nums1[len--] = nums1[m-1]; m--; }else{ nums1[len--] = nums2[n-1]; n--; } } if(m==0){ for(int i = 0;i<n;i++){ nums1[i] = nums2[i]; } } } }
php
class Solution { /** * @param Integer[] $nums1 * @param Integer $m * @param Integer[] $nums2 * @param Integer $n * @return NULL */ function merge(&$nums1, $m, $nums2, $n) { $len = $m+$n-1; if($n==0) return; while($m>0&&$n>0){ if($nums1[$m-1]>$nums2[$n-1]){ $nums1[$len--] = $nums1[$m-1]; $m--; }else{ $nums1[$len--] = $nums2[$n-1]; $n--; } } if($m>=0){ for($i = 0;$i<$n;$i++){ $nums1[$i] = $nums2[$i]; } } } }