欢迎
首页 标签 归档 友链 Page

Algorithm多次写的

2022-06-12

Algorithm多次写的

一些代码有关的问题

关于排序的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
①①Queue<Integer> queue = new PriorityQueue<>((aa, bb) -> aa - bb);
①②Queue<Integer> queue1 = new PriorityQueue<>(new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return 0;
    }
});
②②TreeMap<Integer, Integer> treeMap = new TreeMap<>(new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return 0;
    }
});
③①TreeSet<Integer> treeSet = new TreeSet<>((aa, bb) -> aa - bb);


// 注意，用这个的一定是封装类型的，所以比如int[]这个就很麻烦，要么数组封装成Integer[]，要么自己写个排序算法呗，或者排好后
// 但是对int[][]排序的时候是可以的。
public class MyComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return 0;
    }
}

// 注意此处只能用Integer[]的数组，所以要先吧int[]转成Integer[]
Integer[] aa = new Integer[];
Arrays.sort(aa,new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return (int)(o2-o1);
    }
});

// 此处由于不是封装类型，所以直接先升序排序然后翻转，其他的封装类型还有之后的int[][]就是可以直接在Arrays.sort中去写Comparator了。
int[] temp = queue.pollFirst();
Arrays.sort(temp);
for (int i = 0; i < temp.length / 2; i++) {
    int tempTemp = temp[i];
    temp[i] = temp[temp.length - i - 1];
    temp[temp.length - i - 1] = tempTemp;
}

// List的数组就没什么问题了
List<Integer> list = new ArrayList<>();
Collections.sort(list, new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return 0;
    }
});




// 注意，由于都是int，所以从小到大只要a - b，从大到小只要b - a，如果是小数呢
// 就是说，如果要小于，那么整数a - b，也就是a < b时返回复数；大于，整数b - a，也就是a < b时返回整正数即可，不过确实是需要比较器的，此时稍微省略的写法了
Queue<Double> queue = new PriorityQueue<>((a, b) -> {
                                    if (a.equals(b)) { return 0;}
                                    else if (b > a) { return 1;}   // return正数代表
                                    return -1;
                                  });

关于TreeSet和TreeMap

java集合方法之TreeSet.floor()和TreeSet.ceiling()

floor(E e) 方法返回在这个集合中小于或者等于给定元素的最大元素，如果不存在这样的元素,返回null.
ceiling(E e) 方法返回在这个集合中大于或者等于给定元素的最小元素，如果不存在这样的元素,返回null.

lower、floor、ceiling 和 higher 分别返回小于、小于等于、大于等于、大于给定元素的元素，如果不存在这样的元素，则返回 null。

注意：

1 声明的时候要用TreeSet，而不能用Set

2 取结果的时候用包装类型取，因为如果返回null，那么拆箱失败会nullpointexception

1
2
TreeSet<Integer> set = new TreeSet<>();
set.ceiling(23);

TreeSet的first()和last()

TreeMap中的floorKey()和ceilingKey()

ceilingKey(K key), 返回大于或等于给定键的最小键，如果没有这样的键，则null

floorKey(K key), 返回小于或等于给定键的最大键，如果没有这样的键，则null

注意：

1 声明的时候需要使用TreeMap，而不能只是Map

2 取结果的时候用包装类型取，因为如果返回null，那么拆箱失败会nullpointexception

1
2
3
TreeMap<Integer, Integer> map = new TreeMap<>();
map.ceilingKey(213);
Map.Entry<Integer, Integer> integerIntegerEntry = map.ceilingEntry(123);

关于Scanner的next()和nextLine()的问题

  • next()，一定要读取到有效字符后才可以结束输入，对输入有效字符之前遇到的空格键、Tab键或Enter键等结束符，next（）方法会自动将其去掉，只有在输入有效字符之后，next（）方法才将其后输入的空格键、Tab键或Enter键等视为分隔符或结束符。完整标记的前后是与分隔模式匹配的输入信息所以next()不能得到带空格的字符串。

  • nextLine()，遇到回车是才结束，所以可以得到带空格的字符串。

  • 在输入一个int类型的数字之后，如果后边采用nextLine的话，最后打印结果发现会少一个字符，原因是在你使用nextInt的时候后边有一个换行符，没有接受，前边的int变量只是接受了你输入的数值，所以在你继续输入nextLine之后，会自动读取还未读取的换行，所以会导致后边的结果有一列为空，所以此时你需要多输入一个NextLine把未接受的换行符接收到。

所以以后最好统一使用nextLine，但是如果前面nextInt读取了一个数字，那么需要先nextLine一下将换行符读取掉，然后在nextLine读取这一行字符串。

5
RBBRB

1
2
3
4
5
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();

sc.nextLine();   // 注意此处需要先读取换行符
String str = sc.nextLine();

但是如果要根据空格读取，那还是得用next()函数的

关于拷贝

1
2
3
4
5
6
7
8
9
char[] temp = Arrays.copyOfRange(chars, curIndex, i + 1);
Arrays.copyOf(chars, 2); // 表示chars中的0，1字符数组
curAns.add(new String(temp));  // cha[]转String，用String.value也可以

Arrays.fill(temp, '9');
Arrays.fill(temp, 0, 2, '9'); // temp中的0， 1变成'9'

String s = "132";
String substring = s.substring(0, 2);

问题

1、Deque<int[]>中存放两次temp的，深浅拷贝问题

2、java中集合存储的元素，是对象的引用。

3、int[]这个数组也是对象的，所以说前面的Comparator的时候对int[]是不能排序的，对int[][]可以排序的，因为Comparator的时候里面的每一个元素是iny[]，那么也就是对象了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//（1）如果是基本数据类型，则是value
//（2） 如果是复合数据类型，则是引用的地址；String b="a"; lists.add(b); b="bbb";最后输出还是a，
//      原因是存放的不是b，而是b第一次指向的地址，修改b=”bbb”后只是修改了b指向的地址。这里因为直接更换了b指向的地址了。
//      比如里面存放temp数组，然后temp数组的第一个值改变了，那么集合里存放的也会改变。但是如何此时temp = new int[n]，那么temp这个东西，与集合里面的那个再也没有关系了。

// 所以我一开始将int[]存放进去，然后改这个数组的时候不想影响到集合里面的那个元素，那么存放的时候就是需要放queue.offerLast(temp.clone());

Deque<List<Integer>> deque = new ArrayDeque<>();
List<Integer> list = new ArrayList<>();
list.add(2);
deque.add(list);
list.set(0, 123);
System.out.println(deque.peekFirst().get(0));
// 无可厚非，这里面输出的是123还是改变的

// 这里重新new ArrayList(list)就可以了。  注意与int[]的区别，一个是clone，另外一个是new一个新的。
Deque<List<Integer>> deque = new ArrayDeque<>();
List<Integer> list = new ArrayList<>();
list.add(2);
deque.add(new ArrayList<>(list));
list.set(0, 123);
System.out.println(deque.peekFirst().get(0));

二叉树根节点到叶子所有路径

dfs + 回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.util.*;

public class 二叉树根到节点所有路径 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.right = new TreeNode(6);
        root.left.right = new TreeNode(234);
        root.right.left = new TreeNode(12);
        root.right.right = new TreeNode(2);

        new 二叉树根到节点所有路径().new Solution().solve(root);
    }

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    public class Solution {
        public void solve(TreeNode root) {
            List<List<Integer>> ans = new ArrayList<>();
            dfsTrace(root, new ArrayList<>(), ans);

            for (List<Integer> path : ans) {
                for (Integer e : path) {
                    System.out.print(e + " ");
                }
                System.out.println();
            }
        }

        public void dfsTrace(TreeNode node, List<Integer> path, List<List<Integer>> ans) {
            if (node.left == null && node.right == null) {
                path.add(node.val);
                ans.add(new ArrayList<>(path));
                path.remove(path.size() - 1);
                return;
            }

            path.add(node.val);

            if (node.left != null) {
                dfsTrace(node.left, path, ans);
            }
            if (node.right != null) {
                dfsTrace(node.right, path, ans);
            }
            path.remove(path.size() - 1);
        }
    }
}

Java快速排序

链表排序

归并排序

反转M～N

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == right) {
            return head;
        }

        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;

        ListNode pre = dummyNode;
        int count = 1;
        while (count != left) {
            pre = pre.next;
            count += 1;
        }

        ListNode leftNode = pre.next;

        ListNode curNode = pre.next;
        ListNode nextNode = curNode.next;
        // 开始反转
        while (count != right) {
            ListNode nextnextNode = nextNode.next;
            nextNode.next = curNode;
            curNode = nextNode;
            nextNode = nextnextNode;

            count += 1;
        }

        pre.next = curNode;
        leftNode.next = nextNode;

        return dummyNode.next;
    }
}

剑指 Offer 24. 反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;

        ListNode curNode = head;
        
        while (curNode != null) {
            ListNode next = curNode.next;
            curNode.next = prev;

            prev = curNode;
            curNode = next;
        }9-

        return prev;
    }
}

202. 快乐数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int getNext(int num) {
        int ans = 0;

        while (num != 0) {
            int temp = num % 10;
            ans += temp * temp;
            num /= 10;
        }

        return ans;
    }

    public boolean isHappy(int n) {
        int slow = n, fast = getNext(n);

        while (fast != 1 && slow != fast) {
            slow = getNext(slow);

            fast = getNext(getNext(fast));
        }

        if (fast == 1) {
            return true;
        }

        return false;
    }
}

300. 最长递增子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;

        int[] dp = new int[n];

        // 边界
        Arrays.fill(dp, 1);
      
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
        }

        return Arrays.stream(dp).max().getAsInt();
    }
}

// O(nlogn)
class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;

        // 以i结尾的最长序列
        int[] dp = new int[n];
        // 保存长度为i的序列中的尾数最小的
        int[] g = new int[n+1];
        int ans = 1;

        // 边界
        Arrays.fill(dp, 1);
        g[1] = nums[0];

        for (int i = 1; i < n; i++) {
            int left = 1, right = ans;

            // 找出当前nums[i]在g中的位置
            while (left <= right) {
                int mid = left + (right - left >> 1);

                if (g[mid] == nums[i]) {
                    // 如果相等，那么不能加，所以此处用right-1平衡下面的+1
                    right = mid - 1;
                    break;
                } else if (g[mid] > nums[i]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            
            ans = Math.max(ans, right + 1);
            g[right + 1] = nums[i];
        }

        return ans;
    }
}

148. 排序链表

使用归并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        return sortList(head, null);
    }

    // 归并排序，此处需要找到中点，然后分治，不包括尾
    public ListNode sortList(ListNode head, ListNode tail) {
        if (head == null) {
            return head;
        }
        if (head.next == tail) {
            head.next = null;
            return head;
        }

        // 找到中点，使用快慢指针
        // 注意，此处最后一个肯定是tail，所以不需要判断空了
      	// 其实感觉这个slow最后不是中点，会有问题
      	// 直接在while(fast!= tail && fast.next!= tail)就像了。
        ListNode slow = head, fast = head;
        while (fast != tail) {
            fast = fast.next;
            slow = slow.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }

        // 分治
        ListNode left = sortList(head, slow);
        ListNode right = sortList(slow, tail);

        // 合并
        return merge(left, right);
    }

    public ListNode merge(ListNode node1, ListNode node2) {
        ListNode dummyNode = new ListNode(-1);
        ListNode node = dummyNode;

        while (node1 != null && node2 != null) {
            if (node1.val < node2.val) {
                node.next = node1;
                node1 = node1.next;
            } else {
                node.next = node2;
                node2 = node2.next;
            }

            node = node.next;
        }

        if (node1 != null) {
            node.next = node1;
        }
        if (node2 != null) {
            node.next = node2;
        }

        return dummyNode.next;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        return sortList(head, null);
    }

    // 归并排序，不包含right
    public ListNode sortList(ListNode head, ListNode tail) {
        if (head == null) {
            return null;
        }
        if (head.next == tail) {
            head.next = null;
            return head;
        }

        // 找到中间点
        ListNode slow = head, fast = head;
      	// 注意是不等于tail
        while (fast != tail && fast.next != tail) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode leftHead = sortList(head, slow);
        ListNode rightHead = sortList(slow, tail);

        return merge(leftHead, rightHead);
    }

    public ListNode merge(ListNode node1, ListNode node2) {
        ListNode dummyNode = new ListNode(-1);
        ListNode node = dummyNode;

        while (node1 != null && node2 != null) {
            if (node1.val < node2.val) {
                node.next = node1;
                node1 = node1.next;
            } else {
                node.next = node2;
                node2 = node2.next;
            }

            node = node.next;
        }

        if (node1 != null) {
            node.next = node1;
        }
        if (node2 != null) {
            node.next = node2;
        }

        return dummyNode.next;
    }
}

LRU缓存 最近最久未使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
class LRUCache {
    // 打算使用双端链表和哈希表实现
    // 双端链表尾部放最新的，头部就是最旧的
    // 哈希表存的键存放key，值存放类

    // 双端的
    class LRULinkedNode {
        int key;
        int val;
        LRULinkedNode pre;
        LRULinkedNode next;

        public LRULinkedNode() {}
        public LRULinkedNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    LRULinkedNode head, tail;
    int capacity;
    Map<Integer, LRULinkedNode> map = new HashMap<>();

    public LRUCache(int capacity) {
        this.capacity = capacity;

        head = new LRULinkedNode();
        tail = new LRULinkedNode();

        head.next = tail;
        tail.pre = head;
    }
    
    public int get(int key) {
        if (map.containsKey(key)) {
            LRULinkedNode node = map.get(key);
            moveToTail(node);
            return node.val;
        }

        return -1;
    }
    
    public void put(int key, int value) {
        if (map.containsKey(key)) { // 若已经存在，那么更改值，然后放到最后，使其最新
            LRULinkedNode node = map.get(key);
            node.val = value;
            moveToTail(node);
        } else {
            LRULinkedNode newNode = new LRULinkedNode(key, value);
            map.put(key, newNode);
            addToTail(newNode);
        }

        if (capacity < map.size()) { // 需要去除最头部的
            removeHead();
        }
    }

    // 删除最旧的
    public void removeHead() {
        LRULinkedNode del = head.next;

        head.next = head.next.next;
        head.next.pre = head;

        map.remove(del.key);
    }

    // 尾部是最新的
    public void addToTail(LRULinkedNode newNode) {
        LRULinkedNode pre = tail.pre;
        pre.next = newNode;
        newNode.pre = pre;
        tail.pre = newNode;
        newNode.next = tail;
    }

    // 已经存在，移动到最新的
    public void moveToTail(LRULinkedNode node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;

        addToTail(node);
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

912. 排序数组

【C++】十大排序（冒泡、选择、插入、希尔、归并、快排、堆、计数、桶、基数）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// 快速
class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length-1);

        return nums;
    }

  	// 快速，填坑，包括end
    public void quickSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }

        // 增加随机
        int randomLeft = new Random().nextInt(end - start + 1) + start;
        swap(nums, start, randomLeft);

        int base = nums[start];
        int left = start, right = end;
        while (left < right) {
            // 先开始右边
            while (right > left && nums[right] >= base) {
                right -= 1;
            }
            nums[left] = nums[right];

            while (right > left && nums[left] <= base) {
                left += 1;
            }
            nums[right] = nums[left];
        }
      	// 最后的那个坑，留给base
        nums[left] = base;

        quickSort(nums, start, left - 1);
        quickSort(nums, right + 1, end);
    }

    public void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

141. 环形链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 // 1. 使用哈希表判断是否访问过
 // 2. 使用floyd判圈，快慢指针，一开始是head和head.next
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }

        ListNode slow = head;
        ListNode fast = head.next;

        while (fast != slow) {
            // 注意此处的判断条件是fast和fast.next，因为slow只是走过了fast走过的路
            if (fast == null || fast.next == null) {
                return false;
            }

            slow = slow.next;
            fast = fast.next.next;
        }

        return true;
    }
}

142. 环形链表 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

        ListNode slow = head, fast = head;
        while (true) {
            if (fast == null || fast.next == null) {
                // fast到末尾了，没有环
                return null;
            }
            
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                // 有环
                break;
            }
        }

        // fast变成head，再次相遇的就是第一个环点
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }
}

二叉树的遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// 前序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) {
            return new ArrayList<Integer>();
        }
        List<Integer> ans = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();

        stack.offerLast(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pollLast();
            ans.add(node.val);
            
            if (node.right != null) {
                stack.offerLast(node.right);
            }
            if (node.left != null) {
                stack.offerLast(node.left);
            }
        }

        return ans;
    }
}

// 中序遍历
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<Integer> ans = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();

        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.offerLast(root);
                root = root.left;
            }

            root = stack.pollLast();
            ans.add(root.val);
            root = root.right;
        }

        return ans;
    }
}

// 后序遍历
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }

        List<Integer> ans = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode pre = null;

        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.offerLast(root);
                root = root.left;
            }

            root = stack.pollLast();
            if (root.right == null || root.right == pre) {
                ans.add(root.val);
                pre = root;
                root = null;
            } else {
                stack.offerLast(root);
                root = root.right;
            }
        }

        return ans;
    }
}

50. Pow(x, n)

KPX2Br

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    public double myPow(double x, int n) {
        double ans = 1.0;
        double con = x;
        boolean flag = false;
        long N = n; // 非常注意此处的N，因为n负数可以存的更多一点，到时候加个负号还是负数
        if (N < 0) {
            flag = true;
            N = -N;
        }
        
        
        while (N > 0) {
            // 如果n的最后一位是奇数，那么有贡献2的i次方，乘进去
            if (N % 2 == 1) {
                ans *= con;
            }

            con *= con;
            N /= 2;
        }
        return !flag ? ans : 1.0 / ans;
    }
}

// class Solution {
//     public double myPow(double x, int n) {
//         long N = n;
//         return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
//     }

//     public double quickMul(double x, long N) {
//         double ans = 1.0;
//         // 贡献的初始值为 x
//         double x_contribute = x;
//         // 在对 N 进行二进制拆分的同时计算答案
//         while (N > 0) {
//             if (N % 2 == 1) {
//                 // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
//                 ans *= x_contribute;
//             }
//             // 将贡献不断地平方
//             x_contribute *= x_contribute;
//             // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
//             N /= 2;
//         }
//         return ans;
//     }
// }

Author: Jcwang

Permalink: http://example.com/2022/06/12/Algorithm%E5%A4%9A%E6%AC%A1%E5%86%99%E7%9A%84/

updated at 2022-10-15

Previous Post
AlgorithmLeetcodeShijuan
Next Post
AlgorithmClassfication4