Henry ’Blog
0%

<剑指offer> 剑指offer 16、18

发表于 更新于 分类于 Valine：

摘要：
16 数值的整数次方
18 删除链表的节点

面试题16 数值的整数次方

题目：

实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public double myPow(double x, int n) {
        if(x==0) return 0;
        double res=1;
        //Java 代码中 int32 变量 n \in [-2147483648, 2147483647]n∈[−2147483648,2147483647] ，
        //因此当 n = -2147483648n=−2147483648 时执行 n = -nn=−n 会因越界而赋值出错。
        //解决方法是先将 nn 存入 long 变量 bb ，后面用 bb 操作即可。
        long b=n;
        if(b<0){
            x=1/x;
            b=-b;
        }
        while(b>0){
            if(b%2==1){
                res=res*x;
            }
            x=x*x;
            b=b/2;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def myPow(self, x: float, n: int) -> float:
        if not x: return 0
        res=1
        if n<0:
            x=1/x
            n=-n
        while n>0:
            if n%2==1:
                res=res*x
            x=x**2
            n//=2
        return res

面试题18 删除链表的节点

题目：

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if(head.val==val) return head.next;
        ListNode pre=head;
        ListNode cur=head.next;
        while(cur!=null&&cur.val!=val){
            pre=cur;
            cur=cur.next;
        }
        if(cur!=null){
            pre.next=cur.next;
        }
        return head;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        if head.val==val: return head.next
        pre=head
        cur=head.next
        while cur and cur.val!=val:
            pre=cur
            cur=cur.next
        if cur:
            pre.next=cur.next
        return head