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开始下一轮迭代。
迭代公式可化简为如下所示：
计算x = a的解,可以看成f(x) =x - a，a即为要求平方根
x= x -(x- a) / (2x) = (x+ a/x) / 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];
}
}
}
}