孙云增的博客

题目合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。 示例：1234567输入:[ 1->4->5, 1->3->4, 2->6]输出: 1->1->2->3->4->4->5->6 思路 + 代码合并两个有序链表的翻版。 123456789101112131415161718192021222324252627282930313233343536373839/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public ListNode mergeKLists(ListNode[] lists) { if(lists==null ||...

题目给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。 示例：给定二叉树12345 1 / \ 2 3 / \ 4 5 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。 注意：两结点之间的路径长度是以它们之间边的数目表示。 思路 + 代码路径长度一定是以某个节点为根节点，左右子树的最大深度和。 与题目求二叉树的最大深度类似 1234567891011121314151617181920212223242526/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { private int sum...

题目给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。 示例1：12输入:nums = [1,1,1], k = 2输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。 说明： 数组的长度为 [1, 20,000]。 数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。 思路1先固定数组的左侧位置，然后依次移动右侧指针，如何数组和为 k，结果加一。 数组和置为零，更新左侧位置。 1234567891011121314class Solution { public int subarraySum(int[] nums, int k) { int res=0; for(int left=0; left<nums.length; left++){ int sum=0; for(int right = left; right<nums.length; right++){ ...

题目给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。 然而，两个相同种类的任务之间必须有长度为 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。 你需要计算完成所有任务所需要的最短时间。 示例1： 123输入: tasks = ["A","A","A","B","B","B"], n = 2输出: 8执行顺序: A -> B -> (待命) -> A -> B -> (待命) -> A -> B. 注: 121. 任务的总个数为 [1, 10000]。2. n 的取值范围为 [0, 100]。 思路 + 代码方法1规定 n + 1 个任务为一轮，这样的好处是同一轮中一个任务最...

题目给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。 你找到的子数组应是最短的，请输出它的长度。 示例1： 123输入: [2, 6, 4, 8, 10, 9, 15]输出: 5解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。 说明： 输入的数组长度范围在 [1, 10,000]。 输入的数组可能包含重复元素 ，所以升序的意思是<=。 思路 + 代码首先用左右两个指针分别探测左右各自逆序的起点。此时序列对应的数值是局部最小值与局部最大值。 然后在逆序序列(左边逆序开始与右边逆序开始位置之间)中寻找全局最小值与全局最大值。 然后从左边开始遍历寻找小于等于全局最小值的边界；从右边寻找大于等于全局最大值的边界。 左右边界构成数组的长度即为所求。 12345678910111213141516171819202122232425262728293031323334class Solution { public int findUnsortedSubarr...

插入排序每次遍历都将对应位置的数字插入到合适的位置，当前位置之前的数据保持排序。 代码12345678910111213141516public class InsertionSort { public static int[] sort(int[] arr){ int len = arr.length; int[] A = new int[len]; System.arraycopy(arr, 0, A, 0, len); int i,j; for (i = 1; i < len; i++) { int temp = A[i]; for (j = i; j > 0 && A[j - 1] > temp; j--) { A[j] = A[j-1]; } A[j] = temp; } ...

MySQL 简介MySQL是一个关系型数据库管理系统，由瑞典MySQL AB 公司开发，目前属于 Oracle 旗下产品。MySQL 是最流行的关系型数据库管理系统之一，在 WEB 应用方面，MySQL是最好的 RDBMS (Relational Database Management System，关系数据库管理系统) 应用软件之一。 MySQL具有以下优点：  成本——MySQL是开放源代码的，一般可以免费使用（甚至可以 免费修改）。  性能——MySQL执行很快（非常快）。  可信赖——某些非常重要和声望很高的公司、站点使用MySQL， 这些公司和站点都用MySQL来处理自己的重要数据。  简单——MySQL很容易安装和使用。 基础入门 启动服务 Windows： 1net start mysql ubuntu: 1sudo service mysql start 登录 12mysql -u root -p***** 查看已有数据库 1SHOW DATABASES; 创建数据库 1CREATE DATABASE; 使用数据库 1U...

题目给你一根长度为n的绳子，请把绳子剪成m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],…,k[m]。请问k[0]xk[1]x…xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。 （2 <= n <= 60） 思路 + 代码动态规划 可以分解子问题，即剪一刀，产生两段绳子，长度分别是 i 与 n-i, 在这两条绳子上可以继续剪： 1f(n) = max(f(i), f(n-i)) 123456789101112131415public class Solution { public int cutRope(int target) { int[] dp = new int[target+1]; dp[1] = 1; for(int i=2; i<=target; i++){ for(int j=1; j<i; j++){ ...

题目地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？ 思路 + 代码回溯方法，类似题目1、题目2 12345678910111213141516171819202122232425262728293031323334public class Solution { private int k; private int res; private int[][] next = new int[][]{{0,1},{0,-1},{1,0},{-1,0}}; public int movingCount(int threshold, int rows, int col...

题目给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。 思路 + 代码用一个最大堆维护中间的判断结果，每次只需对顶元素调整即可。 1234567891011121314151617181920import java.util.*;public class Solution { public ArrayList<Integer> maxInWindows(int [] num, int size) { ArrayList<Integer> res ...