LeetCode上几道和字符串有关的动态规划问题

Word Break

题意

给出一个字符串s和一个词典,判断字符串s是否可以被空格切分成一个或多个出现在字典中的单词。 给出

s = “leetcode”,dict = [“leet”,”code”],返回 true 因为“leetcode”可以被空格切分成“leet code”

思路

凡是和字符串有关的题,在应用动态规划方法时主要有两种思路:

  • dp[i][j]表示子串s[i,j]满足某一要求
  • dp[i]表示子串s[0,i]满足某一要求

继续阅读LeetCode上几道和字符串有关的动态规划问题

LeetCode上几道经典的回溯法题目

把相同类型的题目放在一起总结,可以便于整理思路,理解异同。下面是LeetCode上几道比较经典的可以使用回溯法来解决的题目,也是笔试面试时常考常问的。

在找实习时我就被问了两次Subsets这道题。因此熟练掌握这几道题,面试时遇到类似的题目即使是不能一下子写出正确的代码,至少也能按照正确的思路去思考。 继续阅读LeetCode上几道经典的回溯法题目

LeetCode 上几道经典的排列组合题

LeetCode 上有几道题都和排列组合有关,非常经典,值得放在一起总结一下。这几道题分别是:

  • Permutations。给定一组各不相同的数字,求这些数字的所有排列。
  • Permutations II。给定一组数字,这些数字中可能有重复的,求这些数字的所有不重复的排列。
  • Next Permutation。给定一组数字的全排列中的一个排列,求这个排列的下一个排列。
  • Permutation Sequence。给定一组数字和一个数字 K,求这组数字的全排列中,按照字典序顺序排序的第 K 个排列。

继续阅读LeetCode 上几道经典的排列组合题

shared_ptr 的实现

智能指针

shared_ptr 是C++11后引入的智能指针。智能指针的出现大大简化了C++程序员进行内存管理的逻辑,同时也避免了低级C++程序员可能写出的各种bug。陈硕老师在《Linux多线程服务器端编程》中总结道:

C++里可能出现的内存问题大致有这么几个:
1. 缓冲区溢出。
2. 空悬指针/悬挂指针
3. 重复释放
4. 内存泄漏
5. 不配对的new[]/delete
6. 内存碎片

正确使用智能指针能很轻易地解决前面5个问题。

shared_ptr 是智能指针中比较典型的一个。下面我们将从源代码的角度来进行分析,看看它是怎么实现的。源代码可以从GNU 处进行下载。 继续阅读shared_ptr 的实现

在其他数字都出现K次的数组中找到只出现M次的数字

在其他数字都出现偶数次的数组中找到只出现奇数次的1个数字

题目描述

给定一个数组 arr,其中只有一个数字出现了奇数次,其他数字都出现了偶数次,找出这个数字。

思路

使用异或运算符。我们可以声明一个变量 x,用它去和数组中的每个元素做异或运算,由于 n ^ n = 0, n ^ 0 = n,那么那些出现偶数次的数字和自身异或,结果为0。最后x中存的就是数组中只出现奇数次次的数字。 继续阅读在其他数字都出现K次的数组中找到只出现M次的数字

LeetCode-437-Path Sum Ⅲ

Path SumPath Sum Ⅱ之后,Path Sum 大家庭又迎来了第三位成员。那么这个新成员又提出了什么样的要求呢?

题意是这样的:给出一棵二叉树和一个数值 sum,计算这棵树上的节点之和等于sum 的所有路径的条数。和之前不同的是,这道题中路径可以从树中的任何一个节点开始。 继续阅读LeetCode-437-Path Sum Ⅲ

LeetCode-646-Maxinum Length of Pair Chain

题意:给出 n 组数,每组有两个数,第一个数总是比第二个数字小。如果两组数 (a,b) 和 (c,d) 之间,有 b < c,那么就称 (a,b)和 (c,d) 之间形成了一个chain。求出这 n 组数中能形成的最长的 chain 的长度。

例子:输入[[1,2], [2,3], [3,4]],因为[1,2] -> [3,4],所以返回2。 继续阅读LeetCode-646-Maxinum Length of Pair Chain

LeetCode-494-Target Sum

这个题也是一道动态规划题目。题意是:给出一系列数和一个目标数,使用+-来使这些数字的和等于给定的目标数,求总共可行的方法数。

例子:输入[1, 1, 1, 1, 1]target = 3,那么:

所以最后的输出结果是:5 继续阅读LeetCode-494-Target Sum