著书三年倦写字，如今翻书不识志，若知倦书悔前程 ，无如渔樵未识时
你的任务是计算 ab 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。
示例 1：
输入：a = 2, b = [3] 输出：8
示例 2：
输入：a = 2, b = [1,0] 输出：1024
示例 3：
输入：a = 1, b = [4,3,3,8,5,2] 输出：1
示例 4：
输入：a = 2147483647, b = [2,0,0] 输出：1198
提示：
1 <= a <= 231 - 11 <= b.length <= 20000 <= b[i] <= 9b 不含前导 0快速幂使用，注意识别中途取余的情况
先了解下快速幂相关的知识，可以尝试下做下剑指 Offer 16. 数值的整数次方
另外一个知识点同底数幂相乘,底数不变,指数相加即 a^m * a^n = a^(m+n)
所以当我们面对int[] b次幂的时候，即等同于
a^(b[0] * 100...0) * ... * a^(b[i])
举个栗子假设int[] b为[2,3,4]
那么结果即为a^200 * a^30 * a^4 等同于a^(100+100) * a^(10+10+10) * a^4a^100 * a^100 * a^10 * a^10 * a^10 * a^1 * a^1 * a^1 * a^1
最终我们可以得到(a^100)^2 * (a^10)^3 * (a^1)^4
这样我们从末位开始往前遍历，中间可以重复利用 a^(10^n)的结果
自定义快速幂函数pow(int a, int b)中注意处理各种要取模的情况
class Solution {
int mod = 1337;
public int superPow(int a, int[] b) {
int ans = 1;
for (int i = b.length - 1; i >= 0; i--) {
ans *= pow(a,b[i]);
ans %= mod;
a = pow(a,10);
}
return ans;
}
public int pow(int a, int b){
if (b==0) return 1;
if (b==1) return a%mod;
int ans = pow(a,b/2);
return ((ans * ans)%mod) * pow(a,b%2) % mod;
}
}输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
示例 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7]
示例 2:
Input: preorder = [-1], inorder = [-1] Output: [-1]
限制：
0 <= 节点个数 <= 5000
注意：本题与主站 105 题重复：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/ Related Topics
👍 830👎 0
学二叉树入门必做题
关键信息
前中后序遍历
左右两个子节点的顺序不变都是先左子节点，后右子节点，区别就在于根节点是先遍历，还是中间，还是最后
这分别就是前中后序遍历
相关特性
现有如图这个一对前序遍历和中序遍历结果
根据相关特效，前序遍历的第一个就是根节点，所以我们知道了，根节点为3
又中序遍历中左侧只有一个，所以左子树只有一个节点9，右子树部分暂时不知道只知道剩下部分为右侧的前序和中序遍历结果，二叉树如下
再接下来，我们把右子树部分的按照同样的逻辑处理
我们知道了右子树的根节点为20，20的左子树只有一个节点15，右子树只有一个节点7
这样我们就重新构建完成了整棵二叉树
class Solution {
int[] preorder;
int[] inorder;
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
this.inorder = inorder;
int len = preorder.length-1;
return buildTree(0,len,0,len);
}
public TreeNode buildTree( int preL, int preR, int inL, int inR){
if (preL > preR){
return null;
}
TreeNode node = new TreeNode(preorder[preL]);
int len = 0;
for (int i = inL; i <= inR; i++) {
if (inorder[i] == preorder[preL]){
len = i - inL;
}
}
node.left = buildTree(preL+1,preL+len,inL,inL+len-1);
node.right = buildTree(preL+len+1,preR,inL+len+1,inR);
return node;
}
}输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例 1：
输入：arr = [3,2,1], k = 2 输出：[1,2] 或者 [2,1]
示例 2：
输入：arr = [0,1,2,1], k = 1 输出：[0]
限制：
0 <= k <= arr.length <= 100000 <= arr[i] <= 10000堆排序
此处撰写解题思路
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if (k == 0){
return new int[0];
}
PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
for (int i : arr) {
if (queue.size() < k){
queue.offer(i);
}else if(i < queue.peek()){
queue.poll();
queue.offer(i);
}
}
int[] res = new int[k];
for (int i = 0; i < res.length; i++) {
res[i] = queue.poll();
}
return res;
}
}给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6
示例 2：
输入：lists = [] 输出：[]
示例 3：
输入：lists = [[]] 输出：[]
提示：
k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i] 按 升序 排列lists[i].length 的总和不超过 10^4JAVA 分治归并 其实挺简单的
K/2个链表了，对剩下的链表继续两两合并//对应为k个链表在入参数组中的下标
1 [0,1],[2,3],[4,5],[6,7],[8]
2 [0,2],[4,6],[8]
4 [0,4],[8]
8 [0,8]
- 第一次 `[0,1],[2,3],[4,5],[6,7]`互相合并，结果留在第一个链表位置， `[8]`单独拉下了没关系先留着
- 第二次 `[0,2],[4,6]` 互相合并，结果存在0 , 4 位置，8继续留着，`[8]`没关系
- 第三次 再次合并`[0,4]`，`[8]`继续留着
- 最后一次合并`[0,8]`结束收工class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 1){
return lists[0];
}
if (lists.length == 0){
return null;
}
int dis = 1;
while (dis < lists.length){
//1 [0,1],[2,3],[4,5],[6,7],[8]
//2 [0,2],[4,6],[8]
//4 [0,4],[8]
//8 [0,8]
for (int i = 0; i + dis < lists.length; i += dis*2) {
//合并两个有序链表 剑指Offer25题
lists[i] = mergeTwoLists(lists[i],lists[i+dis]);
lists[i+dis] = null;
}
dis *=2;
}
return lists[0];
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2){
ListNode head = new ListNode();
ListNode cur = head;
while ( l1 != null || l2 != null ){
if (l1 == null || l2 == null){
cur.next = l1==null?l2:l1;
break;
}
if (l1.val < l2.val){
cur.next = l1;
l1 = l1.next;
}else{
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
return head.next;
}
}输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
提示：
1 <= arr.length <= 10^5-100 <= arr[i] <= 100注意：本题与主站 53 题相同：https://leetcode-cn.com/problems/maximum-subarray/
动态规划，简单理解DP数组的意义和转移方程来源
class Solution {
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length];
int max = nums[0];
dp[0] = nums[0];
int idx = 0;
while (++idx < nums.length){
dp[idx] = Math.max(nums[idx],dp[idx-1]+nums[idx]);
max = Math.max(max,dp[idx]);
}
return max;
}
}
直接看代码说话，动态规划需要明白的最重要的就是你的dp[]数组表达的意义是什么？
这里我们的int[] dp 需要表达的意义是
以原 int[] nums 数组中的每一位结尾的子序列能组成的最大子序列合这很重要，当求dp[i]的时候，我们有两种情况
这两个来源对应的值分别是 dp[i-1] 和 nums[i]
要求子序列合最大，那么我们就可以得到以下转移方程
dp[i] = MAX ( nums[i] , dp[i-1]+nums[i] )
或者也可以这样
dp[i] = MAX ( 0 , dp[i-1] ) + nums[i]
都一样的，代码就是上面那样了，当然也可以再简化的用一个变量代替下dp[]数组来操作
class Solution {
public int maxSubArray(int[] nums) {
int max = nums[0];
int pre = nums[0];
int idx = 0;
while (++idx < nums.length){
pre = Math.max(0 ,pre) + nums[idx];
max = Math.max(max,pre);
}
return max;
}
}
emmm，测试用例的问题么？单个变量的内存消耗甚至比数组大
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4] 输出: 5
限制：
0 <= 数组长度 <= 50000
归并，基本思路李姐
归并过程可以把代码的注释打开看下，以实际数据来解释说明下
归并数组： [7, 6, 5, 4, 3] [32, 11, 8, 2, 1]
idxL:0
idxR:3
2
idxL:1
idxR:3
2
idxL:2
idxR:3
2
idxL:3
idxR:3
2
idxL:4
idxR:3
2
归并结果： [32, 11, 8, 7, 6, 5, 4, 3, 2, 1]
-----
以上数组A[7, 6, 5, 4, 3]、B[32, 11, 8, 2, 1]
7小于B的第0个32，结果第一位插入32，第二位11同样，第三位8同样7大于B下标3的数字2，此时7和后面的[2, 1]形成逆序对，逆序对个数加26同样和后面的[2, 1]形成逆序对，逆序对个数加2[5, 4, 3]也一样，逆序对分别加2 归并数组： [7] [5]
idxL:0
idxR:0
1
归并结果： [7, 5]
-----
以及归并数组： [7, 5] [6]和归并数组： [4] [3]，再将这两个合并归并数组： [7, 6, 5] [4, 3]，得到结果[7, 6, 5, 4, 3]，在这个过程中已经计算过了
class Solution {
int count = 0;
public int reversePairs(int[] nums) {
sort(nums);
return count;
}
public int[] sort(int[] nums){
if (nums.length<2){
return nums;
}
int[] right = new int[nums.length/2];
int[] left = new int[nums.length - right.length];
System.arraycopy(nums,0,left,0,left.length);
System.arraycopy(nums,left.length,right,0,right.length);
left = sort(left);
right = sort(right);
return mergeArray(left,right);
}
public int[] mergeArray(int[] left, int[] right) {
if (right.length==0){
return left;
}
// System.out.println("归并数组： "+Arrays.toString(left) +" "+ Arrays.toString(right));
int[] arr = new int[left.length + right.length];
int idx = -1;
int idxL = 0;
int idxR = 0;
while (++idx < arr.length){
if (idxL<left.length && (idxR>= right.length || left[idxL] > right[idxR])){
arr[idx] = left[idxL];
idxL++;
count += right.length-idxR;
// System.out.println(right.length-idxR);
}else{
arr[idx] = right[idxR];
idxR++;
}
}
// System.out.println("归并结果： "+Arrays.toString(arr));
// System.out.println("-----");
return arr;
}
}