和《有重复数字的全排列》是一样的，有两种解法，第一种是使用选择和撤销，第二种是交换解法1: 选择和撤销每个位置的值都可以从所有的元素中选择，选择了当前位置的元素之后，再选下一个元素的，知道选完所有的值，得到一条结果然后撤销，让当前位置选下一个元素，如此循环，知道该位置选了不同的元素 import java.util.*; public class Solution { ArrayList<String> result = new ArrayList<String>(); public ArrayList<String> Permuta...

解题思路：访问节点，如果该节点是1，那么将岛屿数量加一，同时将与它相临的1找出来，mark为0，因为这么多相邻的1只算一个岛屿而第二步将相邻的1找出来mark为0有两种办法： 深度优先（depth first search)和广度优先（breadth-first-search）具体实现1 dfs: import java.util.*; public class Solution { /** * 判断岛屿数量 * @param grid char字符型二维数组 * @return int整型 */ public int solve ...

解题思路：最近访问的元素放在第一个，其他的往后挪，可以用双向链表LinkedList来实现需要实现两个方法：put和getget的时候需要调整优先级，要把当前访问的item移到第一个put需要实现更新/增加/替换的操作更新：key已经存在的情况，找到对应的item，更新value增加：key不存在，cache没有满，即cache size小于capacity，那么直接将它加到第一个替换：key不存在，cache满了，即cache size等于capacity，那么要将最后一个元素删除，然后将当前的item加入到第一个put和get都有查找findEntryByKey操作，时间复杂度是O(n)，...

解法：选择撤销和没有重复数字的全排列相比，选择的时候要多加一个条件如果本轮迭代中，相同的数字已经被选择了，那么就不要选，其他情况就还是一样的如果判断本轮迭代中相同的数字已经被选择首先看会出现相同数字的情况, 出现相同数字的时候：num[index] == num[index - 1]， 除此之外加一个index > 0防止数组越界，如果是在本轮迭代中，那么num[index-1]的visited标记已经被撤回了，也就是!visited[index - 1]所以两个条件加起来就能判断在同一个迭代中，相同的数字已经被选择具体可以看图示：时间复杂度：f(n) = n* f(n-1),可以推断出...

解法：定好第一位（递归）每个元素都可以作为第一个元素，当它作为第一个元素时，其他元素进行全排列，再把他们拼起来而数组不是很好操作，可以先转为列表，这样在删除某个元素的时候不需要移动数组后面的元素 import java.util.*; public class Solution { public ArrayList<ArrayList<Integer>> permute(int[] num) { ArrayList<Integer> allElements = toArrayList(num); return per...

解法1: 双指针交替指针odd和even相互只想对方的下一个节点以构造对应的链，最后可以得到odd链和even链，再让odd链的尾节点指向even链的头节点需要注意边界条件，也就是退出while循环的条件，可以分两个case来考虑： 链表节点为奇数时，链表节点为偶数时当链表节点为奇数时，even == null时退出：当链表节点为偶数时，even.next == null时退出：最后再让odd.next指向evenHead; import java.util.*; public class Solution { public ListNode oddEvenList (ListNode...

解法：归并排序归并排序需要将链表分成长度均等的左右两部分，分别对两部分进行排序之后再合并如何把两个链表分成长度均等的两部分？ 快慢指针 import java.util.*; public class Solution { /** * * @param head ListNode类 the head node * @return ListNode类 */ public ListNode sortInList (ListNode head) { if (head == null || head.next == null) ...

解法1:遍历然后删除所有的用一个临时变量conpared来存储当前需要比较的值如果发现这个值是重复的，那么就用while循环找到最后一个重复的节点，直接删除这一堆重复的点prev.next = current.next;如果没有发现重复的，那就prev继续往下去遍历每一轮结束都要重新让current指向prev的下一个节点 import java.util.*; public class Solution { public ListNode deleteDuplicates (ListNode head) { if (head == null || head.next...

解法1:遍历挨个遍历，同时保存上一个节点的值，如果当前节点的值等于上一个节点的值就删除，否则就继续遍历 import java.util.*; public class Solution { public ListNode deleteDuplicates (ListNode head) { if (head == null || head.next == null) { return head; } ListNode current = head; while (current != null &...

解法1:使用栈出栈后和原来的节点对比，注意比较的是val，而不是节点本身：if(reverse.val != original.val)时间复杂度：O(n)空间复杂度：O(n) import java.util.*; public class Solution { public boolean isPail (ListNode head) { if (head == null) { return false; } Stack<ListNode> reversedList = new Stack<...

解法1:栈用2个栈来存储链表1和2，链表3来表示加和的结果，一个临时变量保存进位carryOver需要注意的点是：当某个链表的长度较长的时候，将它放入结果是，也要记得处理carryOver的部分时间复杂度：O(m + n)空间复杂度：O(m + n) import java.util.*; public class Solution { public ListNode addInList (ListNode head1, ListNode head2) { if (head1 == null) { return head2; } ...

解法1:双指针遍历指针A先遍历链表1，结束了再遍历链表2指针B先遍历链表2， 结束了再遍历链表1相遇时：1.如果有公共节点假设链表1不在公共节点的部分长度为a1，在公共节点的长度为b，链表2不在公共节点的部分长度为a2，在公共节点的长度为bA和B走过了相同的节点数total，A在链表2上走过的节点数为x, B在链表2上走过的节点数为y,total = a1 + b + xtotal = a2 + b + y很容易得出：x = a2, y = a1也就是说，他们第二圈会走到第一个相同的节点相遇2.如果没有相同的节点那么它会走到链表末尾时等于null而相等 import java.util.*; ...

解法1:快慢指针先找到倒数第n+1个节点，然后删除倒数第n个节点如果这个节点是头节点，需要特殊处理一下 import java.util.*; public class Solution { public ListNode removeNthFromEnd (ListNode head, int n) { if (head == null || head.next == null) { return null; } int count = 1; // find the node before Nth...

解法1:快慢指针快指针先走K-1步慢指针再出发，当快指针到结尾的时候时候，慢指针就到了倒数第K个节点 import java.util.*; public class Solution { public ListNode FindKthToTail (ListNode pHead, int k) { if (pHead == null || k == 0) { return null; } if (pHead.next == null && k == 1) { return pHead; ...