在计算机科学中，分治法是构建基于多项分支递归的一种很重要的算法范式。字面上的解释是「分而治之」，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
分治算法的步骤：
1、分：将一个问题切分为两个或两个以上的子问题。
2、治：处理每一个子问题。
2、并：汇总合并所有子问题的结果得出最终的答案。
这个技巧是很多高效算法的基础，如排序算法（快速排序、归并排序）、傅立叶变换（快速傅立叶变换）、汉诺塔问题。
剑指 Offer 25. 合并两个排序的链表
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
示例1：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
题解：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
/**
* 思路：
* 创建一个新头节点preNode，比较l1和l2，preNode指向小的节点
* 然后将小的节点往后移动一个，将preNode往后移动一个，继续比较l1和l2
* 直到l1或者l2某一个为null，那么一种一个合并完，然后将preNode指向另一个非空节点
* @param l1
* @param l2
* @return
*/
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode preNode = new ListNode(-1);
ListNode head = preNode;
while (l1!=null && l2!=null) {
if (l1.val <= l2.val) {
//取l1的节点作为新节点的首节点
preNode.next = l1;
//往后移动节点
l1 = l1.next;
} else {
//取l2的节点作为新节点的首节点
preNode.next = l2;
//往后移动节点
l2 = l2.next;
}
//preNode往后移以用来保存新的节点
preNode = preNode.next;
}
//当某个链表为空，非空链表剩下节点拼接在head链表的末尾
preNode.next = l1==null?l2:l1;
return head.next;
}
}
169. 多数元素
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [3,2,3]
输出: 3
题解：
class Solution {
public int majorityElement(int[] nums) {
Map<Integer, Integer> table = new HashMap<>();
for (int num : nums) {
//将当前数字出现次数+1
if (!table.containsKey(num)) {
table.put(num, 1);
} else {
table.put(num, table.get(num) + 1);
}
}
Set<Map.Entry<Integer, Integer>> entries = table.entrySet();
for (Map.Entry<Integer, Integer> entry : entries) {
if (entry.getValue() * 2 > nums.length) {
//满足条件
return entry.getKey();
}
}
return 0;
}
}
53. 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
题解：
class Solution {
/**
* 思路：
* 状态定义： 设动态规划列表dp ，dp[i]代表以元素nums[i]为结尾的连续子数组最大和。
*
* 我们发现dp[i]就是以数组下标为i的数做为结尾的最大子序列和，
* 注意是以i为结尾，比如说现在有一个数组{6,-3,-2,7,-15,1,2,2}，为了不搞，我们就下标以1开始，dp[3]就是以-2为结尾的，
* 那么显然dp[3]的最大值就是1咯（6，-3，-2），dp[4]要以7结尾那么以7结尾的子序列最大和就是8（6，-3，-2，7）。
*
* 知道dp[i]是啥后，现在我们开始细细品一下上面这个递推式，求dp[i]的时候是不是有两种可能，
* 要么就是像上面的dp[4]一样，dp[3]求出来是1了，再加上自己array[4]是最大的，那么还有一种可能就是说如果dp[3]我求出来是-100，
* 那如果我也是dp[3]+array[4]的话是-93，这时候dp[3]反而是累赘，最大就是自己（因为前面定义了必须以i为结尾，也就说必须以7结尾）。
*
* @param nums
* @return
*/
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = nums[0];
int max = dp[0];
for (int i=1;i<nums.length;i++) {
//如果i前一个数的子数组和小于0，就不要加上前面的累赘了，否则就加上
dp[i] = nums[i] + Math.max(dp[i-1], 0);
//遍历的同时获取dp数组中的最大值
if (dp[i] > max) {
max = dp[i];
}
}
return max;
}
}
网友评论