IT大学渣-CSDN博客

原创 leetcode--trapping_rain_water

题意：给定n个由非负整数表示的正视图，每一个块的宽度是1，计算可以放多少水。举例：给定一个数组[0， 1， 0， 2， 1， 0 ， 1， 3， 2， 1， 2， 1]，返回6，图示如下：分析：本题的标注是栈，我一开始也是往栈的方向去想，虽然可以实现，但是比较繁琐。做完之后参考其他算法大牛的做法，发现可以使用时间复杂度是O(n)，空间复杂度是O(1)的方法，更加高效。算法思想是：先遍历

2016-12-05 09:47:26 153

原创 leetcode--jump_game&&jump_game_II

jump_game_II题意：给定一个由非负整数组成的数组，初始位置在数组中的第一个元素处，数组中每一个元素的值表示你从当前位置最多可以跳的长度。要求使用最少的条数到达最后一个位置。举例： A =[2,3,1,1,4], 最少的条数是2. 分析：本题当然可以使用动态规划来求解，只是还有更简单的方法，那就是贪心。我们用到的贪心策略思想是：扫描所有能到达的点，选择跳到在该点处能跳到的最远处。假

2016-12-04 23:30:44 191

原创 leetcode--remove_element

题意：给定一个数组和一个值，从数组中删除和该值相同的元素，要求不引入额外的空间，返回新的数组长度，元素的顺序可以调换。分析：如果直接删除的话，需要将后面的值往前面移动，这是非常耗费时间的，最坏时间复杂度可以到O(n2)O(n^2) ，我们添加一个int类型的数count，表示总共有多少个重复的数，初始值为0。在找到一个相同的元素时，直接和A.length - count - 1的调换即可。代

2016-12-04 22:49:35 183

原创 leetcode--merge_sorted_array

题意：给定两个排好序的数组A和B，将B合并到A中作为一个排好序的数组。注意：假设A有足够的空间来盛放A和B中合并的结果，初始时A和B中的元素个数分别是m和n。分析：因为数组对插入和删除操作非常不友好，因为需要移动后面的元素，相信大家都了解，因此我们在设计算法时都要避免直接对原数组的增删操作。我想到的方法是：因为我们事先已经直到A和B的大小分别是m和n，则合并后一定是m+n个元素，可以从

2016-12-04 22:09:36 181

原创 leetcode--remove_cuplicates_rfom_sorted_array

题意：给定一个排好序的数组，从中删除重复的值，并返回新数组的大小。条件：不能额外的申请空间，使用常数空间复杂度。举例：给定一个数组A=[1, 1, 2]，程序返回结果为2，此时新数组为[1, 2] 分析：我们额外的添加一个整数count，表示不重复值的个数，初始值为1，因为A[0]肯定不会和前面的重复。当i位置的值和(i - 1)值不同时，则令A[count] = A[i]即可，如

2016-12-04 21:53:19 235

原创 leetcode--path_sum

题意：给定一棵二叉树和一个整数值sum，判断树中是否有一个从根到叶子节点的路径，使得路径上所有值相加等于这个数sum，如果有的话，返回true,否则返回false。树的结构定义如下： public class TreeNode { int val; TreeNode left; TreeNode righ

2016-12-04 21:32:51 180

原创 leetcode--n_queens&&n_queens_II

题意：给定n个皇后和一个n*n的棋盘，找到有多少种相容的放置方法。条件：相容的意思是皇后相互之间不能攻击，根据国际象棋规定，皇后可以攻击它所在位置的行、列和斜对角线中所有的棋子，所以要能够实现相容，每一个皇后与前面的所有皇后不能在同一行、同一列、同一对角线。举例下图是8皇后问题的一个可行解。分析：解决n皇后问题，用到的方法即为回溯。回溯是五大常用算法之一，其余四个分别为

2016-11-22 20:09:08 202

原创 leetcode--search_in_rotated_sorted_array

题意：假设有一个排好序的数组，在某个你不知道的地方进行了旋转。给定一个需要查找的目标值，如果能找到就返回它的索引，否则返回-1。该数组中没有重复的值。举例数组(0, 1, 2, 4, 5, 6, 7)旋转后变成(4, 5, 6, 7, 0, 1, 2)。查找5，返回1; 查找1，返回5; 查找3，返回-1; 分析：首先最简单的，遍历一趟整个数组，查找目标值，时间复杂

2016-11-22 17:50:58 210

原创 leetcode--construct_binary_tree_from_preorder_and_inorder_traversal

题意：给定一颗二叉树前序和中序遍历，要去构建出这颗二叉树。假设这个二叉树中没有重复的值。树结构： public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; }

2016-11-19 23:31:26 224

原创 leetcode--minimum_path_sum

题意：给定一个由非负整数填满的m×n的网格，查找一条从左上方到右下方的路径，使得这条路径中所有数之和最小，只能向有或者向下走。分析：本题有点类似于这道题，只是需要修改下递推公式。设i, j为二维数组的坐标。 minPathSum(i,j)=⎧⎩⎨⎪⎪min(minPathSum(i+1,j)minPathSum(i,j+1))+grid(i,j)minPathSum(i+1,j)+grid

2016-11-19 23:12:49 221

原创 leetcode--spiral_matrix_II

题意：给定一个整数n，生成一个方阵，该方阵用1到n2n^2 以螺旋顺序填满。举例： [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ] 分析：本题先完成外圈再实现内圈，比如上例中[1，2，3，4，5，7，8]构成外圈，9是内圈。本题总体来说不难。代码public int[][] generateMatrix(in

2016-11-19 22:48:02 229

原创 leetcode--search_insert_position

题意：给定一个排好序的数组以及一个目标值，如果找到该值就返回它在数组中的索引，如果没找到，返回这个值应该被插入位置的索引。数组中没有重复值。例子： [1,3,5,6], 5 → 2 [1,3,5,6], 2 → 1 [1,3,5,6], 7 → 4 [1,3,5,6], 0 → 0 分析：本题使用二分搜索，如果能找到该值，就返回索引;如果没找到该值，则比较当前位置的

2016-11-19 22:11:08 145

原创 leetcode--single_number&&single_number_II

single_number题意：给定一个整数类型数组，除了一个元素之外其他所有元素均出现两次，找出这个唯一的元素。条件：要求线性时间复杂度，并且不适用额外空间分析：本题非常经典，在《剑指offer》中也出现过，用到的方法是位运算中的异或操作。记录每一bit出现的次数。由于两个相同的整数做异或一定是0，所以数组中重复的整数异或之后也是0，遍历数组时两两异或，最后异或后的结果就是那个唯一

2016-11-19 21:52:40 176

原创 leetcode--sort_colors

题意：给定一个数组，其中只含有0，1，2，对该数组排序。条件：一趟遍历完成排序，不使用额外的空间，不能使用编程语言自带的排序方法。引言：这道题正常的方法可以使用计数排序，计数排序统计数组中每个不同值出现的次数，并从小到大排列这些值，再根据计数结果重构出排序后的数组。但是本题只能遍历一趟，而且不能使用额外的空间。分析：本题采用的思想是将0移到数组的前面，2移到数组的后面，为此增加两

2016-11-19 00:22:22 175

原创 leetcode--valide-sudoku

题意：根据给定的数独规则判断一个数独是否有效。数独规则如下每一行中1-9各出现一次。每一列中1-9各出现一次。每一个3×3的子方格中1-9各出现一次。条件：本题给的数独框不一定全部填满，空白的部分用字符 ‘.’填充，要判断现有的数独框是否有效而不是判断现有的数独框是否有解。分析：本题主要还是根据数独的规则来做，需要判断是否满足这三个条件。一个数独框可以分割成9个3×3的子方格，所以我创

2016-11-14 22:22:38 150

原创 leetcode--binary_tree_inorder/preorder_traversal

题意：给定一棵二叉树，中序输出结果分析：本题考察递归中序遍历二叉树，比较基础，直接贴代码。public ArrayList<Integer> inorderTraversal(TreeNode root) { if(root == null){return list;} else{ if(root.left != null) i

2016-11-09 22:45:03 235

原创 leetcode--binary-tree-level-order-traversal

题意：给定一棵二叉树，返回节点value的层次遍历顺序(从左到右，按层显示)。举例：给定一颗二叉树{3，9，20，#，#，15，7} 3 / \ 9 20 / \ 15 7 返回层测顺序遍历 [ [3], [9,20],

2016-11-09 15:15:12 194

原创 leetcode--merge-two-sorted-lists

题意：合并两个排好序的数组。分析：本题没有什么特别的技巧，考察对链表编程的熟练程度，注意一些特殊值或者边界情况吧。我是将第二个表l2l2全部插入到第一个表l1l1中。如果l2l2中当前值present2present2大于l1l1 当前值，向后遍历l1l1 直到值大于present2present2 ，将present2present2 插入到l1中; 如果present2present2

2016-11-09 11:51:09 151

原创 leetcode--balanced-binary-tree

题意：给定一棵二叉树，判断它是否为高度上平衡的。高度上平衡定义为每一个节点的左右子树的深度相差均不超过1。分析：本题主要考察二叉树的递归操作。递归得到每个节点左右子数的深度(叶子节点深度为1)，判断左右子树相差是否超过1，如果超过1，将该节点深度设为-1，并向父亲节点返回结果，父亲节点得到左孩子或右孩子有深度为-1的，直接设置深度为-1。最终只需要判断root节点是否为正数，如果是则平衡，反

2016-11-08 11:46:14 199

原创 leetcode--maximum-subarray

题意：从一个数组中找到一个连续的子数组，使和最大。举例：给定一个数组[-2, 1, -3, 4, -1, 2, 1, -5, 4]，连续的子数组[4, -1, 2, 1]有最大的和为6。分析：本题采用贪心求解，设置变量sumsum和maxmax, sumsum表示子数组和，初始值为0; maxmax表示最大的和，初始值为array[0]array[0]。从位置0开始，遍历到i位置，如果s

2016-11-04 16:58:02 273

原创 leetcode--remove_duplicates_from_sorted_list

leetcode–remove_duplicates_from_sorted_list题意：给定一个排序的链表，从中删除所有重复的元素。链表的结构如图 public class ListNode { int val; ListNode next; ListNo

2016-11-04 15:37:18 238

原创 leetcode--set_matrix_zeroes

leetcode–set_matrix_zeroes题意：给定一个m×n的二维数组，如果有一个元素是0就将该元素所在的行和列全部设置成0。条件：要求就地转换，不使用额外空间。分析：首先这道题的难点就是不引入额外空间，如果可以引入O(m+n)O(m+n) 的空间，那么就可以使用两个集合分别存横坐标和纵坐标，如果某个元素是0，就将该行所在的横坐标和纵坐标分别添加到集合当中。因为集合中不能有

2016-11-04 15:22:19 372

原创 leetcode--rotate_image

leetcode–rotate_image题意：给定一个n×n的二维矩阵，将它沿顺时针方向旋转90度条件：不引入额外的空间分析：本题考察二维数组索引的操作，采用的基本思想是先转置外圈，后转置内圈，从外向内转置，把问题简化。红颜色的是外圈，绿颜色的是内圈，先将外圈全部转置完。(0,0)放到(0,

2016-10-30 15:50:27 260

原创 leetcode--linked_list_cycle

leetcode–linked_list_cycle题意：判断一个链表是否有环条件：不能创建额外空间分析：如果只用一个指针，无法判断什么时候终止，一定不能求解此题。不过本题其实不是很难，需要用到一个小技巧，设置两个快慢指针，快指针一次走两步，慢指针一次走一步，当快指针遇到NULL时，返回false(无环);而如果链表有环，则快指针最后一定会和慢指针相遇，相遇之后返回true即可。代码pub

2016-10-29 23:57:09 154

原创 leetcode--populating_next_right_pointers_in_each_node

leetcode–populating_next_right_pointers_in_each_node题意：给定一个二叉树结构,public class TreeLinkNode { int val; TreeLinkNode left, right, next; TreeLinkNode(int x) { val = x; } }每一个节点添加一个指针next(如上)，

2016-10-28 20:51:51 189

原创 leetcode--climbing_stairs

leetcode–climbing_stairs题意：有一个n阶的台阶，一次可以跨1步或者或者2步，问总共有多少种不同的方法到达台阶顶端分析：本题不是很难，也比较容易想到用动态规划来求解该题。设x[i]表示上i阶台阶有多少种方法，则递推公式为：x[i]=⎧⎩⎨⎪⎪⎪⎪112x[i−1]+x[i−2]i = 0i = 1i = 2i > 2 x[i]=\begin{cases}

2016-10-28 19:59:36 291

原创 leetcode--unique_paths

leetcode–unique_paths题意：给定一个m×n的网格，一个机器人从网格最左上角到网格最右下角，它只能往右或者往下走，总共有多少种唯一的路径。下图为一个简单的示例图，从start走到finish的位置，总共有多少种唯一的路径。分析：本题采用动态规划求解。我们从简单的情况开始考虑，假设是1×1的网格，则只有唯一的一条路径，如果是m×1的网格（m为任意值）

2016-10-27 21:56:30 197

原创 leetcode--integer_to_roman && roman_to_integer

leetcode–integer_to_roman题意：给定一个integer，把它转化成罗马数字（本题integer的取值范围是[1, 3999]） tips 罗马数字一共由7个字符构成，分别是I(1)，V(5)，X(10)，L(50)，C(100)，D(500)，M(1000)，能够表示的范围刚好就是[1, 3999]。本题求解需要首先了解罗马数字的构成，如1到12分别表示为：Ⅰ、Ⅱ、Ⅲ、

2016-10-27 20:36:06 180

原创 leetcode--container_with_most_water

leetcode–container_with_most_water题意：给定n个非负整数a1，a2，…，an，其中每个表示在坐标（i，ai）的一个点。有n条垂直绘制的线，使得线的两个端点i是在（i，ai）和（i，0）。找到两条线，其与X轴一起形成了一个容器，使得所述容器包含最多的水。分析：本题比较简单，采用动态规划方法求解，递推公式为x(i)=max(x(i−1),max(min(aj,ai

2016-10-24 12:38:54 264

原创 leetcode--reverse_integer

leetcode–reverse_integer题意：将一个int类型的数反转举例：x=123，return 321; x=-123, return -321; warning：如果integer最后一位是0，该怎么输出; 反转后的integer有可能越界，如1000000003，该如何处理这种情况（可以抛出异常，但本题不允许抛异常处理）。本题比较简单，不做分析，直接贴代码pub

2016-10-24 11:28:39 124

原创 leetcode--unique_binary_search_trees问题

unique_binary_search_trees问题描述：给定一个数n，问可以构成多少个结构上唯一的二叉树。举例，给定n=3，一共有5个唯一的二叉树如下：　1 　　 3 　　3 　　2 　　1 　\ 　　/ 　　/ 　　/ \ 　　　\ 　3 　2

2016-10-13 11:23:20 160

转载 leetcode--best_time_to_buy_and_sell_stock

best_time_to_buy_and_sell_stock_i题意：用一个数组表示股票每天的价格，数组的第i个数表示股票在第i天的价格。如果只允许进行一次交易，也就是说只允许买一支股票并卖掉，求最大的收益。分析：动态规划法。从前向后遍历数组，记录当前出现过的最低价格，作为买入价格，并计算以当天价格出售的收益，作为可能的最大收益，整个遍历过程中，出现过的最大收益就是所求。代码：时间O(n)，空间

2016-09-15 16:34:50 196

原创 LeetCode -- palindrome_number问题

LeetCode – palindrome_number问题2016-09-13问题描述：判断一个int类型的整数是否是回文的。要求：不申请额外的空间。思路：第一反应是将int转化成一个String类型，然后利用String类提供的方法判断该String是否为回文字符串，从而可以判断出该int整数是否为回文的。但是，题目要求不能申请额外的空间，创建一个String会在堆空间中new一个

2016-09-13 16:10:50 239

原创 leetcode--two_sum问题

leetcode–two_sum问题2016-09-12问题描述：给定一个排好序的整数数组，使得两数相加等于一个特定的值。要求：返回两个数在数组中的索引，第一个数的索引必须小于第二个；数组的起始下标不是从0开始的。 Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2解题思路假设数组为numbers[]，设置

2016-09-12 23:01:53 261

haizeiwangdianxia的博客