算法 - 开发工具分享

描述给一个01矩阵，求不同的岛屿的个数。 0代表海，1代表岛，如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。样例在矩阵： [ [1, 1, 0, 0, 0], [0, 1, 0, 0, 1], [0, 0, 0, 1, 1], [0, 0, 0, 0, 0], [0, 0, 0, 0, 1] ] 中有 3 个岛。代码 GitHub 的源代码，请访问下面的链接： https://github.com/cwiki-us/java-tutorial/blob/master/src/test/java/com/ossez/lang/tutorial/tests/lintcode/LintCode0433NumIslandsTest.java package com.ossez.lang.tutorial.tests.lintcode; import org.junit.Test; import org.slf4j.Logger; import org.slf4j.LoggerFactory; /** * * 433 * <ul> * <li>@see <a href= * "https://www.cwiki.us/display/ITCLASSIFICATION/Number+of+Islands">https://www.cwiki.us/display/ITCLASSIFICATION/Number+of+Islands</a> * <li>@see<a href="https://www.lintcode.com/problem/number-of-islands/">https://www.lintcode.com/problem/number-of-islands/</a> * </ul> * * * @author YuCheng * */ public class LintCode0433NumIslandsTest { private final static Logger logger = LoggerFactory.getLogger(LintCode0433NumIslandsTest.class); /** * */ @Test public void testMain() { logger.debug("BEGIN"); // INIT GRID boolean[][] grid = { { true, true, false, false, false }, { false, true, false, false, true }, { false, false, false, true, true }, { false, false, false, false, false }, { false, false, false, false, true } }; // NULL CHECK if (grid.length == 0 || grid[0].length == 0) { System.out.println("NULL"); // return 0; } // GET SIZE int n = grid.length; int m = grid[0].length; // ARRAY FOR VISITED LOG boolean[][] visited = new boolean[n][m]; int count = 0; // LOOP FOR GRID for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] && !visited[i][j]) { numIslandsDFS(grid, visited, i, j); count++; } } } System.out.println(count); } /** * * @param grid * @param visited * @param x * @param y */ public void numIslandsDFS(boolean[][] grid, boolean[][] visited, int x, int y) { if (x < 0 || x >= grid.length) { return; } if (y < 0 || y >=…

2018年12月16日 0Comments 909Browse 0Like Read more

描述给定一个链表，判断它是否有环。样例给出 -21->10->4->5, tail connects to node index 1，返回 true。这里解释下，题目的意思，在英文原题中，tail connects to node index 1 表示的是节点 5 还要链接回索引号为 1 的节点。一个典型的带环链表如下：挑战不要使用额外的空间代码 GitHub 的源代码，请访问下面的链接： https://github.com/cwiki-us/java-tutorial/blob/master/src/test/java/com/ossez/lang/tutorial/tests/lintcode/LintCode0102HasCycleTest.java package com.ossez.lang.tutorial.tests.lintcode; import org.junit.Test; import org.slf4j.Logger; import org.slf4j.LoggerFactory; import com.ossez.lang.tutorial.models.ListNode; /** * * 102 * <ul> * <li>@see <a href= * "https://www.cwiki.us/display/ITCLASSIFICATION/Linked+List+Cycle">https://www.cwiki.us/display/ITCLASSIFICATION/Linked+List+Cycle</a> * <li>@see<a href= "https://www.lintcode.com/problem/linked-list-cycle/">https://www.lintcode.com/problem/linked-list-cycle/</a> * </ul> * * * @author YuCheng * */ public class LintCode0102HasCycleTest { private final static Logger logger = LoggerFactory.getLogger(LintCode0102HasCycleTest.class); /** * */ @Test public void testMain() { logger.debug("BEGIN"); // INIT LINKED LIST ListNode head = new ListNode(1); head.next = new ListNode(2); head.next.next = new ListNode(3); head.next.next.next = new ListNode(4); // CREATE A LOOP head.next.next.next.next = head.next.next.next; boolean retResult = false; // LIKED LIST MAY NULL: if (!(head == null || head.next == null)) { ListNode s = head; ListNode f = head.next; while (f.next != null && f.next.next != null) { s = s.next; f = f.next.next; if (f == s) { retResult = true; break; } } } System.out.println(retResult); } } 点评链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。在计算机科学中，链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成，每个节点包含任意的实例数据（data fields）和一或两个用来指向上一个/或下一个节点的位置的链接（”links”）。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的访问往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接）。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。要判断一个链表中是否有循环，可以借助额外的存储空间，将链表插入到 HashSet 中。创建一个以节点ID为键的HashSet集合，用来存储曾经遍历过的节点。然后同样是从头节点开始，依次遍历单链表的每一个节点。每遍历到一个新节点，就用新节点和HashSet集合当中存储的节点作比较，如果发现HashSet当中存在相同节点ID，则说明链表有环，如果HashSet当中不存在相同的节点ID，就把这个新节点ID存入HashSet，之后进入下一节点，继续重复刚才的操作。这个方法在流程上和方法一类似，本质的区别是使用了HashSet作为额外的缓存。假设从链表头节点到入环点的距离是D，链表的环长是S。而每一次HashSet查找元素的时间复杂度是O(1), 所以总体的时间复杂度是1*(D+S)=D+S，可以简单理解为O(N)。而算法的空间复杂度还是D+S-1，可以简单地理解成O(N)。也可以采用指针的方式。首先创建两个指针1和2（在java里就是两个对象引用），同时指向这个链表的头节点。然后开始一个大循环，在循环体中，让指针1每次向下移动一个节点，让指针2每次向下移动两个节点，然后比较两个指针指向的节点是否相同。如果相同，则判断出链表有环，如果不同，则继续下一次循环。例如链表A->B->C->D->B->C->D，两个指针最初都指向节点A，进入第一轮循环，指针1移动到了节点B，指针2移动到了C。第二轮循环，指针1移动到了节点C，指针2移动到了节点B。第三轮循环，指针1移动到了节点D，指针2移动到了节点D，此时两指针指向同一节点，判断出链表有环。此方法也可以用一个更生动的例子来形容：在一个环形跑道上，两个运动员在同一地点起跑，一个运动员速度快，一个运动员速度慢。当两人跑了一段时间，速度快的运动员必然会从速度慢的运动员身后再次追上并超过，原因很简单，因为跑道是环形的。 https://www.cwiki.us/display/ITCLASSIFICATION/Linked+List+Cycle

2018年12月15日 0Comments 1138Browse 0Like Read more

描述给出两个数组，求它们的点积。(Wikipedia) 如果没有点积则返回-1 样例 Input:A = [1,1,1] B = [2,2,2] Output:6 代码请单击下面链接在 GitHub 上查看最新的源代码： https://github.com/cwiki-us/java-tutorial/blob/master/src/test/java/com/ossez/lang/tutorial/tests/lintcode/LintCode1480DotProductTest.java package com.ossez.lang.tutorial.tests.lintcode; import org.junit.Test; import org.slf4j.Logger; import org.slf4j.LoggerFactory; /** * * 1480 * <ul> * <li>@see * <a href= "https://www.cwiki.us/display/ITCLASSIFICATION/Dot+Product">https://www.cwiki.us/display/ITCLASSIFICATION/Dot+Product</a> * <li>@see<a href= "https://www.lintcode.com/problem/dot-product/">https://www.lintcode.com/problem/dot-product/</a> * </ul> * * * @author YuCheng * */ public class LintCode1480DotProductTest { private final static Logger logger = LoggerFactory.getLogger(LintCode1480DotProductTest.class); /** * */ @Test public void testMain() { logger.debug("BEGIN"); int[] A = { 1, 1, -1 }; int[] B = { 2147483647, 1, 3 }; int retStatus = 0; // LENGTH CHECK if (A.length == 0 || B.length == 0 || A.length != B.length) retStatus = -1; // ADDED if (retStatus != -1) { for (int i = 0; i < A.length; i++) { retStatus = retStatus + A[i] * B[i]; } } System.out.println(retStatus); } } 点评这个问题的关键是要了解点积是如何进行计算的。对输入的数组还需要进行 NULL 的校验和计算。摘录点积的计算方法如下：向量是由n个实数组成的一个n行1列（n*1）或一个1行n列（1*n）的有序数组；向量的点乘,也叫向量的内积、数量积，对两个向量执行点乘运算，就是对这两个向量对应位一一相乘之后求和的操作，点乘的结果是一个标量。点乘公式对于向量 a 和向量 b： a和b的点积公式为：要求一维向量 a 和向量 b 的行列数相同。因为要求向量 a 和 b 的行列数相同，因此在程序中需要先进行判断才可以。

2018年12月14日 0Comments 938Browse 0Like Read more

描述给一个整数数组，找到两个数使得他们的和等于一个给定的数 target。你需要实现的函数twoSum需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是 0 到 n-1。你可以假设只有一组答案。样例给出 numbers = [2, 7, 11, 15], target = 9, 返回 [0, 1]. 挑战 Either of the following solutions are acceptable: O(n) Space, O(nlogn) Time O(n) Space, O(n) Time 代码 /** * 56 https://www.lintcode.com/problem/two-sum/description */ @Test public void tesTwoSum() { int[] numbers = { 2, 7, 11, 15 }; int target = 9; int[] retArray = new int[2]; for (int i = 0; i < numbers.length; i++) { int intA = numbers[i]; int intB = 0; for (int j = 1 + i; j < numbers.length; j++) { intB = numbers[j]; // SUM CHECK if (target == intA + intB && i < j) { retArray[0] = i; retArray[1] = j; break; } } } System.out.println(Arrays.toString(retArray)); }

2018年12月13日 0Comments 906Browse 0Like Read more

描述原地翻转给出的数组 nums 原地意味着你不能使用额外空间样例给出 nums = [1,2,5] 返回 [5,2,1] 代码 /** * 767 https://www.lintcode.com/problem/reverse-array/description */ @Test public void testReverseArray() { int[] nums = { 1, 2, 3, 4, 5, 6, 7 }; for (int i = 0; i < nums.length / 2; i++) { int tmp = nums[i]; nums[i] = nums[nums.length - 1 - i]; nums[nums.length - 1 - i] = tmp; } System.out.println(Arrays.toString(nums)); }

2018年12月13日 0Comments 994Browse 1Like Read more

描述给定一个字符串，逐个翻转字符串中的每个单词。说明单词的构成：无空格字母构成一个单词输入字符串是否包括前导或者尾随空格？可以包括，但是反转后的字符不能包括如何处理两个单词间的多个空格？在反转字符串中间空格减少到只含一个样例给出s = "the sky is blue"，返回"blue is sky the" 代码 /** * 53 https://www.lintcode.com/problem/reverse-words-in-a-string/description */ @Test public void testReverseWords() { String s = " Life doesn't always give us the joys we want."; String retStr = ""; String[] inStr = s.split(" "); for (int i = inStr.length - 1; i >= 0; i--) { String cStr = inStr[i].trim(); if (!cStr.isEmpty()) { retStr = retStr + " " + cStr; } } retStr = retStr.trim(); System.out.println(retStr); // return retStr; }

2018年12月13日 0Comments 937Browse 0Like Read more

[LintCode] Number of Islands（岛屿个数）

[LintCode] Linked List Cycle（带环链表）

[LintCode] Dot Product（点积）

[LintCode] Two Sum（两数之和组）

[LintCode] Reverse Array（翻转数组）

[LintCode] Reverse Words in a String（翻转字符串中的单词）