动态规划算法

发表于 2019-06-23 | Edited on 2019-07-24

动态规划（Dynamic programming，简称DP）

动态规划算法的基本思想与分治法类似，也是将求解的问题分解为若干字问题，按顺序求解子阶段，前一子问题的解，为后一子问题提供了有用的信息。在求解任意子问题，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解决。

阅读全文 »

分治算法

发表于 2019-06-22 | Edited on 2019-07-24

分治

分治法是建基于多项分支递归的一种算法范式，字面意思”分而治之“，把一个复杂的问题分为两个或者更多的相同或者相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

分治算法通常以数学归纳法来验证。而它的计算成本则多数以解递归关系式来判定。

优势

解决困难问题

分治算法是一个解决复杂问题的好工具，它可以把问题分解成若干个子问题，把子问题逐个解决，再组合到一起形成大问题的答案。比如，汉诺塔问题如果采用分治算法，可以把高度为n的塔的问题转换成高度为n-1的塔来解决，如此重复，直至问题化简到可以很容易的处理为止。

实现

循环递归

在每一层递归上都有三个步骤：

分解：将原问题分解为若干个规模较小，相对独立，与原问题形式相同的子问题。
解决：若子问题规模较小且易于解决时，则直接解。否则，递归地解决各子问题。
合并：将各子问题的解合并为原问题的解。

241.给表达式加括号

不同的二叉搜索树

链表

发表于 2019-06-18 | Edited on 2019-08-25 | 分类于数据结构

链表

与数组相似，链表也是一种线性数据结构

单链表

单链表中的每个结点不仅包含值，还包含链接到下一个结点的引用字段。通过这种方式，单链表将所有结点按顺序组织起来。

操作

与数组不同，无法在常量时间内访问单链表中的随机元素。如果想要获得第i个元素，必须从头结点逐个遍历。

添加操作-单链表

使用给定值初始化新结点cur
将cur的”next”字段链接到prev的下一个结点next
将prev中的”next”字段链到cur

与数组不同，不需要将所有元素移动到插入元素之后。因此，非常高效。

删除操作-单链表

想从单链表中删除现有结点cur，可以分两步完成：

找到cur的上一个结点prev及其下一结点next；
接下来链接prev到cur的下一个结点next

删除第一个结点

如果想要删除第一个结点，可以简单地将下一个结点分配给head。

双指针技巧

链表中的双指针

如果没有环，快指针将停在链表的末尾。
如果有环，快指针最终将与慢指针相遇。

环形链表

给定一个链表，判断链表中是否有环

通过使用具有不同速度的快、慢两个指针遍历链表，空间复杂度可以降低至1。慢指针每次移动一步，而快指针每次移动两步。
如果列表中不存在环，最终快指针将会最先到达尾部，此时我们可以返回false。

环形链表II

不允许修改给定的链表

用一个Set保存已经访问过的节点，可以遍历整个列表并返回第一个出现重复的节点。

算法：

首先，我们分配一个Set去保存所有的列表节点。我们逐一遍历列表，检查当前节点是否出现过，如果节点已经出现过，那么一定形成了环且它是环的入口。否则如果有其他点是环的入口，我们应该先访问到其他节点而不是这个节点。其他情况，没有成环则直接返回 null 。

算法会在遍历有限个节点后终止，这是因为输入列表会被分成两类：成环的和不成环的。一个不成欢的列表在遍历完所有节点后会到达 null - 即链表的最后一个元素后停止。一个成环列表可以想象成是一个不成环列表将最后一个null元素换成环的入口。

如果 while 循环终止，我们返回 null 因为我们已经将所有的节点遍历了一遍且没有遇到重复的节点，这种情况下，列表是不成环的。对于循环列表， while 循环永远不会停止，但在某个节点上， if 条件会被满足并导致函数的退出。

找出两个链表的交点

删除链表的倒数第N个节点

经典问题

反转链表

一种解决方案时按原始顺序迭代结点，并将它们逐个移动到列表的头部

移除链表元素

删除结点的步骤

找到该结点的前一个结点
进行删除操作

三种方式：

删除头结点时另作考虑（由于头结点没有前一个结点）
添加一个虚拟头结点，删除头结点就不用另做考虑
递归

奇偶链表

想法

将奇节点放在一个链表里，偶链表放到另一个链表里。然后把偶链表接在奇链表的尾部

小结

可以同时使用多个指针
有时，当你为链表问题设计算法时，可能需要同时跟踪多个结点。应该记住需要跟踪哪些结点，并且可以自由地使用几个不同的结点指针来同时跟踪这些结点。如果你使用多个指针，最好为它们指定适当的名称，以防将来必须调试或检查代码
在许多情况下，需要跟踪当前结点的前一结点
你无法追溯单链表中的前一结点。因此，你不仅要存储当前结点，还要存储前一个结点。这在双链表中是不同的。

双链表

双链表以类似的方式工作，但还有一个引用字段，称为prev字段。有了这个额外的字段，就能够知道当前结点的前一结点。

操作

可以与单链表相同的方式访问数据：

不能再常量级的时间访问随机位置。
必须从头部遍历才能得到我们想要的第一个结点
在最坏的情况下，时间复杂度是O(N)，其中N是链表的长度

添加操作-双链表

删除操作-双链表

从双链表中删除一个现有的结点cur，可以简单地将它的前一结点prev与下一个结点next链接起来。

小结-链表

在单链表中，它无法获取给定结点的前一结点，因此在删除给定结点之前必须花费O(N)时间来找出前一结点
在双链表中，这会更容易，可以使用prev引用字段获取前一结点。因此可以在O(1)时间内删除给定结点。

合并两个有序链表

两数相加

LeetCode题解

发表于 2018-04-06 | Edited on 2019-07-24 | 分类于算法

数组

只出现一次的数字

给定一个整数数组，除了某个元素外其余元素均出现两次。请找出这个只出现一次的元素

答题思路：一个数组中除了一个元素，其他元素都出现两次，所以可以使用位运算异或来实现，因为相同的元素进行异或其结果为0

class Solution {
    public int singleNumber(int[] nums) {
        int num = 0;
        for(int i = 0; i < nums.length; i++) {
            num ^= nums[i];
        }
        return num;
    }
}

从排序数组中删除重复项

给定一个有序数组，需要原地删除其中重复内容，使每个元素只出现一次，并返回新的长度
不要另外定义一个数组，必须通过O(1)额外内存原地修改输入的数组来做到这一点

class Solution {
    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        if (len <= 1) return len;
        int tail = 1;
        for (int i = 1; i <len; i++) {
            if(nums[i-1] != nums[i]) {
                nums[tail++] = nums[i];
            }
        }
        return tail;
    }
}

两数之和

给定一个整数数列，找出其中和为特定值的那两个数

示例：

1
2
3

给定nums = [2, 7, 11, 15], target = 9
因为nums[0] + nums[1] = 2 + 7 = 9
所以返回[0, 1]

答题思路：

第一次遍历数组先将所有元素和它的下标作为key-value对存入HashMap中，第二次遍历数组根据目标和与当前元素只差，在HashMap中找相应的差值
如果存在该差值，说明存在两个数之和是目标和。

class Solution {
   public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();

        for(int i = 0; i < nums.length; i++) {
            int com = target - nums[i];
            if (map.containsKey(com)) {
                return new int[] {map.get(com), i};
            }
            map.put(nums[i], i);
        }
        return new int[2];
    }
}

两个数组的交集

给定两个数组，写一个方法来计算它们的交集
例如：
给定nums1 = [1, 2, 2, 1], nums2 = [2, 2]，返回[2, 2]
注意：

输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致
可以不考虑输出结果的顺序

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
       HashMap<Integer, Integer> hash = new HashMap<>();

       for(int i = 0; i < nums1.lenght; i++) {
           hash.put(nums1[i], hash.getOrDefault(num, 0) + 1);
       }

       ArrayList<Integer> array = new ArrayList<>();
       for(int num: nums2) {
           if (hash.containKey(num) && hash.get(num) != 0) {
               array.add(num);
               hash.put(num, hash.get(num) - 1);
           }
       }
       int [] resultArray = new int[result.size()];
       int index = 0;
       for (int item : result) {
           resultArray[index++] = item;
       }
       return resultArray;
    }
}

加一

给定一个非负整数组成的非空数组，给整数加1
可以假设整数不包含任何前导零，除了数字0本身
最高位数字存放在列表的首位

class Solution {
    public int[] plusOne(int[] digits) {
        if (digits == null || digits.length == 0) {
            return digits;
        }
        int carry = 1;
        for (int i = digits.length -1; i >= 0; i--) {
            int digit = (digits[i] + carry) % 10;
            carry = (digits[i] + carry) / 10;
            digits[i] = digit;
            if (carry == 0) {
                return digits;
            }
            
        }
        int[] res = new int[digits.length + 1];
        res[0] = 1;
        return res;
    }
}

存在重复

给定一个整数数组，判断是否存在重复元素
如果任何值在数组中出现至少两次，函数应该返回true。如果每个元素都不相同，则返回false

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int n : nums) {
            if (map.containsKey(n)) {
                return true;
            }
            map.put(n, 0);
        }
        return false;
    }
}

字符串

反转字符串

编写一个函数，其功能是将输入的字符串反转过来

class Solution {
    fun reverseString(s: String): String {
        val byteArray = s.toCharArray()
        var result = ""
        for (i in byteArray.size-1 downTo 0) {
        result += byteArray[i]

        }
        return result
    }
}

颠倒整数

给定一个32位有符号整数，将整数中的数字进行反转
示例 1:

输入: 123
输出: 321
示例 2:

输入: -123
输出: -321
示例 3:

输入: 120
输出: 21
注意:

假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1]。根据这个假设，如果反转后的整数溢出，则返回 0。

class Solution {
    fun reverse(x: Int): Int {
        var x1: Long = x.toLong()
        var res = 0L

        while (x1 != 0L) {
        res = res * 10L + x1 % 10L
        x1 /= 10
        }

        return if (res > Integer.MAX_VALUE || res < Integer.MIN_VALUE) 0 else res.toInt()
    }
}

字符串中的第一个唯一字符

给定一个字符串，找到它的第一个不重复字符，并返回它的索引。如果不存在则返回-1
案例：

s = "leetcode"
返回 0.

s = "loveleetcode",
返回 2.

注意事项：您可以假定该字符串只包含小写字母。

class Solution {
    fun firstUniqChar(s: String): Int {
        val map = HashMap<Char, Int>()
        val list = ArrayList<Int>()

        for (i in 0 until s.length) {
        if (map.containsKey(s[i]))
            map[s[i]] = Int.MAX_VALUE
        else
            map[s[i]] = i
            list.add(i)

        }

        for (i in 0 until list.size) {
            if (map[s[list[i]]] != Int.MAX_VALUE) {
                return list[i]
            }
        }
        return -1
    }
}

最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀
如果不存在最长公共前缀，返回空字符串””

class Solution {
    fun longestCommonPrefix(strs: Array<String>) {
        val len = strs.size
        if (len == 0) {
            return ""
        }
        val minLen = 0x7fffffff
        for (str in strs) {
            minLen = Math.min(minLen, str.length)
        }

        for(j in 0 until minLen) {
            for(i in 0 until minlen) {
               if (strs[0][j] != strs[i][j]) {
                   return strs[0].subString(0, j)
               }
            }
        }
        return strs[0].subString(0, minLen)
    }
}

有效的字母异味词

给定两个字符串s和t，编写一个函数来判断t是否是s的一个字母异位词
s = “anagram”，t = “nagaram”，返回 true
s = “rat”，t = “car”，返回 false

注意:
假定字符串只包含小写字母。

提升难度:
输入的字符串包含 unicode 字符怎么办？你能能否调整你的解法来适应这种情况？

class Solution {
    fun isAnagram(s: String, t: String): Boolean {
        if (s.length != t.length) {
            return false
        }
        val t1 = StringBuilder(t)
        for (i in 0 until s.length) {
        var found = false
        for (j in 0 until t1.length) {
            if (s[i] == t1[j]) {
                t1[j] = '0'
                found = true
                break
            } else {
                found = false
            }
        }

        if (!found) {
            return false
        }


        }
        return true

    }
}

链表

删除链表的结点

编写一个函数，使其可以删除某个链表中给定的（非末尾的）节点，只被给予要求被删的节点
比如：假设该链表为1 -> 2 -> 3 -> 4，给定你的该链表值为3的第三个节点，那么在调用了您的函数之后，该链表则应变成1 -> 2 ->4

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

删除链表的倒数第N个节点

给定一个链表，删除链表的倒数第n个节点，并且返回链表的头结点
示例：

1 2	给定一个链表： 1->2->3->4->5，和n = 2 当删除了倒数第二个节点后，链表变为1->2->3->5

说明：
给定的n保证是有效的
进阶：
你能尝试使用一趟扫描实现吗？

/**
 *Definition for singly-linked list.
 * class ListNode(var `val`: Int = 0) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
        var localN = n
        var pre = head
        var afterPreN: ListNode? = head

        while (localN-- != 0) {
        afterPreN = afterPreN!!.next
        }
        if (afterPreN != null) {
        while (afterPreN!!.next != null) {
            pre = pre?.next
            afterPreN = afterPreN.next
        }
        pre?.next = pre?.next?.next
        } else {
        return head?.next
        }
        return head
    }
}

反转链表

反转一个单链表
进阶：
链表可以迭代或递归地反转。你能够两个都实现一遍

class Solution {
    fun reverseList(head: ListNode?): ListNode? {
        if (head == null) return head
        if (head.next == null) return head

        val newHead: ListNode? = reverseList2(head.next)

        head.next?.next = head


        head.next = null

        return newHead
    }
}

合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

class Solution {
    fun mergeTwoLists(l1: ListNode?, l2: ListNode?): ListNode? {
        var localL1 = l1
        var localL2 = l2
        val head = ListNode(0)
        var tmp: ListNode? = head
        while (localL1 != null && localL2 != null) {
        if (localL1.`val` < localL2.`val`) {
            tmp!!.next = localL1
            localL1 = localL1.next
        } else {
            tmp!!.next = localL2
            localL2 = localL2.next
        }
        tmp = tmp.next
        }
        tmp!!.next = if (localL1 == null) localL2 else localL1
        return head.next
    }
}

二叉树

发表于 2018-04-05 | Edited on 2019-07-24 | 分类于算法

二叉树

在计算机科学中，二叉树是每个节点最多有两个树的树结构。通常子树被称作“左子树(left subtree)”和“右子树(right subtree)”。

五种形态：

二叉树的每个节点至多只有两棵子树（不存在度大于2的节点），二叉树的子树有左右之分，次序不能颠倒。

二叉树的性质

二叉树的第i层至多有 $2^{i-1}$ “ />个节点(i>=1)。
深度为k的二叉树至多共有 $2^{i}-1$ 个节点。
对任何一颗二叉树T，如果其终端结点数为
对任何一棵二叉树T，如果其终端节点数为 $n_0$ ,度为2的节点数为 $n_2$ ，则 $n_0=n_2+1$
包含n个结点的二叉树的高度至少为 $log_{2}(n+1)$
如果对一个n个结点的完全二叉树(其深度为 $[log_{2}(n)] +1$ )的结点按层序编号（从第1层到第 $[log_{2}(n)] +1$ ）

一棵深度为k，且有$2^{k+1}-1$个节点，称为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的
满二叉树中，序号为1至n的节点对应时，称之为完全二叉树。

与树不同，树的节点个数至少为1，而二叉树的节点个数可以为0；树中节点的最大度数没有限制，而二叉树节点最大度数为2；
树的节点无左、右之分，而二叉树的节点有左、右之分。

二叉树的类型

二叉树是有个有根树，并且每个节点最多有2个子节点。非空的二叉树，若树叶总数为$n_0$,分支度为2的总数
$n_2$，则$n_0=n_2+1$ 一棵深度为k，且有$2^k-1$个节点的二叉树，称为满二叉树。这种树的特点是每一层上的节点数都是最大节点数。
而在一棵二叉树中，除最后一层或者是满的，或者在右边缺少连续若干节点，则此二叉树为完全二叉树。

博主

特别欢喜你