一、链表问题
链表问题一定要进行举例画图，辅助思考！
使用快慢指针遍历链表。因为链表无法得知长度，所以尝试用这种方法来达到某种效果（链表中点，检测环等）。
警惕指针丢失。可以使用一些临时变量来存储next指针，在链表插入节点时应先连接后边节点，避免断链表造成指针丢失。
设置虚拟节点（哨兵），简化实现难度。对于插入和删除等操作，往往需要一个额外的指针来记录其前面的节点（前驱节点）。
单链表递归实现。对一些依赖于后面节点才可以完成的操作，使用递归的方式来解决。
注意留意常见的边界条件处理：链表为空，链表有一个或者两个节点，头结点（例如旋转链表）和尾节点。
环问题
1、141判断链表有环：【快慢指针】
2、环的长度：【快慢指针判断有还，并记录相交的点，再遍历计数计算环入口/环长度】
3、142环的入口节点：【快慢指针，再从头遍历链表】
4、287寻找重复数：弗洛伊德算法找环入口
重构链表
1、206反转链表：【迭代 递归】【1->2->3->∅】 --->> 【∅<-1<-2<-3】
链表反转.jpg
链表反转(递归实现).jpg
2、92反转链表II：
3、24交换链表中的相邻节点
4、143重排链表
5、61旋转链表
拆分/组合
1、86分隔链表：
2、21归并两个有序链表：
3、链表求和
4、两链表的交点
5、排序链表：【147插入、148归并、快速】
删除类型
1、83删除已排好序链表的重复元素
2、203删除链表元素
func removeElements(head *ListNode, val int) *ListNode {
if head == nil {
return nil
}
dummnyhead := &ListNode{
Val:-1,
Next:head, // 创建一个指向head的虚拟头节点
} // 否则，第一个节点的删除会有问题
curr := dummnyhead
for curr.Next != nil {
if curr.Next.Val == val {
curr.Next = curr.Next.Next
} else {
curr = curr.Next
}
}
return dummnyhead.Next
}
3、19删除链表的倒数第 n 个节点
二、dp动态规划
动态规划，无非就是利用历史记录，来避免我们的重复计算。而这些历史记录，我们得需要一些变量来保存，一般是用一维数组或者二维数组来保存。下面我们先来讲下做动态规划题很重要的三个步骤，
第一步骤：定义数组元素的含义，上面说了，我们会用一个数组，来保存历史数组，假设用一维数组 dp[] 吧。这个时候有一个非常非常重要的点，就是规定你这个数组元素的含义，例如你的 dp[i] 是代表什么意思？
第二步骤：找出数组元素之间的关系式，我觉得动态规划，还是有一点类似于我们高中学习时的归纳法的，当我们要计算 dp[n] 时，是可以利用 dp[n-1]，dp[n-2].....dp[1]，来推出 dp[n] 的，也就是可以利用历史数据来推出新的元素值，所以我们要找出数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，这个就是他们的关系式了。而这一步，也是最难的一步，后面我会讲几种类型的题来说。
最优子结构，把大的问题拆分成小的问题。
第三步骤：找出初始值。学过数学归纳法的都知道，虽然我们知道了数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，我们可以通过 dp[n-1] 和 dp[n-2] 来计算 dp[n]，但是，我们得知道初始值啊，例如一直推下去的话，会由 dp[3] = dp[2] + dp[1]。而 dp[2] 和 dp[1] 是不能再分解的了，所以我们必须要能够直接获得 dp[2] 和 dp[1] 的值，而这，就是所谓的初始值。
由了初始值，并且有了数组元素之间的关系式，那么我们就可以得到 dp[n] 的值了，而 dp[n] 的含义是由你来定义的，你想求什么，就定义它是什么，这样，这道题也就解出来了。
二、直接上leetcode真题
-
LC2、无重复字符的最长子串
int lengthOfLongestSubstring(string s) { int start = 0; // 1、当前处理的子串，看看子串，是否有重复的字符 int max = 0; unordered_map<char, int> hash; //用来记录 当前字符的 下标位置。 for (int end = 0; end < s.size(); end++) { char tmp = s[end]; // 2、从start 到 end 子串 如果有重复字符，需要更新start if ( hash.find(tmp) != hash.end() && hash[tmp] >= start) { start = hash[tmp] + 1; } hash[tmp] = end; // 3、查看最大长度，是否更新. start 到 end if(end - start + 1 > max) { max = end - start + 1; } } return max; } -
LC5、最长回文子串
string longestPalindrome(string s) { int len = s.size(); if (len == 0) return s; bool dp[len][len]; //定义一个二维数组bool dp[len-1][len-1]来记录遍历字符串所得的状态， // dp[left][right]为true表示"从left到right的子串为回文串"，false表示不是回文串 int start = 0, end = 0; //初始化二维数组，单个字符为回文串，所以定义dp[i][i] = true for (int i = 0; i <len; i++) dp[i][i] = true; for (int right = 1; right < len; right++) for (int left = 0; left < right; left++) if (s[right]==s[left] && (right-left==1 || dp[left+1][right-1])) { //dp[left][right] = //(s[right]==s[left] && (right-left==1 || dp[left+1][right-1])) ? // true : false // s[right]==s[left] && (right-left==1) 情况一：bb 这种 // s[right]==s[left] && dp[left+1][right-1] 情况二：bab // 如果我们已经知道 “bab” 是回文，那么很明显，“ababa” 一定是回文， // 因为它的左首字母和右尾字母是相同的。 dp[left][right] = true; if (right-left > end-start) { start = left; end = right; } continue; } else { dp[left][right] = false; } return s.substr(start, end-start+1); } -
LC53、连续子串和最大
int maxSubArray(int* nums, int numsSize){ //1、定义dp[i] 以第i个数字结尾的连续子串的和。作为状态 int *dp = NULL; dp = (int *)malloc(sizeof(int) * numsSize); memset(dp, 0, sizeof(int) * numsSize); //2、初始化零界值 dp[0] = nums[0]; for(int i = 1; i < numsSize; i++){ dp[i] = (dp[i-1] + nums[i] > nums[i]) ? (dp[i-1] + nums[i]) : nums[i]; // max(dp[i-1] + nums[i], nums[i]); } int maxNum = dp[0]; for(int j = 0; j < numsSize; j++){ if(dp[j] > maxNum) maxNum = dp[j]; } return maxNum; }int maxNum(int a, int b){ if (a >= b) return a; else return b; } int maxSubArray(vector<int>& nums) { int sum = 0x80000001; //最小的32位整数 int max = 0; for (int i = 0; i < nums.size(); i++) { max = maxNum(max + nums[i], nums[i]); if (max > sum) { sum = max; } } return sum; } -
LC64、编辑距离
/* 对一个单词进行如下三种操作：插入一个字符\删除一个字符\替换一个字符 将 word1 转换成 word2 所使用的最少操作数 。 case: 输入：word1 = "intention", word2 = "execution" 输出：5 解释： intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u') */ int minDistance(string word1, string word2) { int size1 = word1.size(); int size2 = word2.size(); // int dp[i][j] 表示字符串 word1 的长度为 i，字符串 word2 的长度为 j 时， // 将 word1 转化为 word2 所使用的最少操作次数为 dp[i] [j]。 //1、插入一个字符 //2、删除一个字符 //3、替换一个字符 int dp[size1+1][size2+1] = {0}; for(int i = 1; i <= size1; i++){ dp[i][0] = i; } for(int j = 1; j <= size2; j++){ dp[0][j] = j; } for(int i = 1; i <= size1; i++){ for(int j = 1; j <= size2; j++){ // // 关系一： // if(word1[i] == word2[j]){ // dp[i][j] = dp[i-1][j-1]; // }else{ // 关系二: dp[i][j-1]表示在word1尾部插入一个字母， // dp[i-1][j]表示在word1尾部删除一个字母,(相当于在word2尾部插入一个字母)， // dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1; // } // // 关系一： dp[i][j] = min(dp[i][j-1], dp[i-1][j])+1; //插入 删除 时 dp[i][j] = min(dp[i][j], dp[i-1][j-1] + (word1[i-1]==word2[j-1] ? 0:1)); //替换时 } } return dp[size1][size2]; } -
LC152、乘积最大子序列
int maxProduct(vector<int>& nums) { // 1、dp[i] : 表示以以下标i结束的子序列，的最大值和最小值。 vector<int> dpMax(nums.size(), 0); vector<int> dpMin(nums.size(), 0); //2、初始化边界 dpMax[0] = nums[0]; dpMin[0] = nums[0]; int ans = nums[0]; for(int i = 1; i < nums.size(); i++){ dpMax[i] = (dpMax[i-1] * nums[i] >= dpMin[i-1] * nums[i]) ? dpMax[i-1] * nums[i] : dpMin[i-1] * nums[i]; dpMax[i] = dpMax[i] >= nums[i] ? dpMax[i] : nums[i]; dpMin[i] = (dpMax[i-1] * nums[i] < dpMin[i-1] * nums[i]) ? dpMax[i-1] * nums[i] : dpMin[i-1] * nums[i]; dpMin[i] = dpMin[i] < nums[i] ? dpMin[i] : nums[i]; if(ans < dpMax[i]){ ans = dpMax[i]; } } return ans; } -
LC673、最长递增子序列的个数
int findNumberOfLIS(vector<int>& nums) { int n = nums.size(); if(n == 0){ return 0; } int LIS = 1; vector<pair<int, int> > dp(n, {1, 1}); for (int i = 1; i < n; ++i) { for (int j = 0; j < i; ++j) { if (nums[i] > nums[j]) { if (dp[i].first < dp[j].first + 1) { dp[i] = {dp[j].first + 1, dp[j].second}; } else if (dp[i].first == dp[j].first + 1) { dp[i].second += dp[j].second; } } } if(LIS < dp[i].first){ LIS = dp[i].first; } } int res = 0; for (int i = 0; i < n; ++i) { if (dp[i].first == LIS) { res += dp[i].second; } } return res; } -
LC300、最长递增子序列<<给你一个整数数组
nums，找到其中最长严格递增子序列的长度>>。int lengthOfLIS(vector<int>& nums) { int size = nums.size(); if(size < 2){ return size; } int maxLen = 1; vector<int> dp(size, 1); //1、 DP[i] 定义以i为结尾的最长上升子序列的长度 // 2、从第二个元素开始处理 for(int i = 1; i < size; i++){ for(int j = 0; j < i; j++){ if(nums[i] > nums[j] && dp[i] < dp[j] + 1){ dp[i] = dp[j] + 1; } } if(maxLen < dp[i]){ maxLen = dp[i]; } } return maxLen; } -
LC120、三角形最小路径和
/* 输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] 输出：11 解释：如下面简图所示： 2 3 4 6 5 7 4 1 8 3 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。 */ int minimumTotal(vector<vector<int>>& triangle) { int m = triangle.size(); if(m == 0) { return 0; } int dp[m] = {0}; //1. 动态规划：构造一个三角形 dp记录当前行从上往下的和 //每个元素只能走到它的下方或者右下方 //也就是每个元素只能来自它的上方或者左上方 //注意特殊情况：左腰上的元素，只能来自它的上方；右腰只能从左上方来。 dp[0] = triangle[0][0]; // 2. 边界处理 for(int i = 1; i < m; i++){ // 依次处理每一行， dp[i] = triangle[i][i] + dp[i-1]; // 每一行的第一个元素。 for(int j = i - 1; j > 0; j--) //为了避免数据覆盖，从后往前填充 dp[j] = triangle[i][j] + min(dp[j-1], dp[j]); dp[0] += triangle[i][0]; } int ans = dp[0]; for(int i = 1; i < m; i++) ans = min(dp[i], ans); return ans; } -
LC121、卖买股票的最佳时机
/* 输入：[7,1,5,3,6,4] 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入， 在第 5 天（股票价格 = 6）的时候卖出， 最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。 */ /* 思路还是挺清晰的，还是DP思想： 记录【今天之前买入的最小值】 计算【今天之前最小值买入，今天卖出的获利】，也即【今天卖出的最大获利】 比较【每天的最大获利】，取最大值即可 */ int maxProfit(vector<int>& prices) { int dayNum = prices.size(); if(dayNum <= 0){ return 0; } int buyIn = prices[0]; // 定义一个最值，做为买入股票的最佳时机。 int max = 0; // 定义为最大的收益 for(int i = 1; i < dayNum; i++){ if(buyIn > prices[i - 1]){ // 买入价如果不是最大值的话，要更新买入价 buyIn = prices[i - 1]; } if(prices[i] - buyIn > max){ // 收入最大化 max = prices[i] - buyIn; } } return max; } -
LC128 最长连续序列
/* 输入：nums = [100,4,200,1,3,2] 输出：4 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。 */ int longestConsecutive(vector<int>& nums) { if (nums.size() < 2) { return nums.size(); } sort(nums.begin(), nums.end()); // 先排序 nums.erase(unique(nums.begin(), nums.end()), nums.end()); // 去掉重复元素 int res = 1; int n = nums.size(); vector<int> dp(n, 1); // dp 问题： dp[i] 表示以当前元素结尾的连续序列的长度。 for (int i = 1; i < n; i++) { if (nums[i-1] + 1 == nums[i]) { dp[i] = dp[i-1] + 1; } res = max(res, dp[i]); } return res; }
// 最终结果
var result [][]int
// 回溯核心
// nums: 原始列表
// pathNums: 路径上的数字
// used: 是否访问过
func backtrack(nums, pathNums []int, used[]bool) {
// 结束条件：走完了，也就是路径上的数字总数等于原始列表总数
if len(nums) == len(pathNums) {
tmp := make([]int, len(nums))
// 切片底层公用数据，所以要copy
copy(tmp, pathNums)
// 把本次结果追加到最终结果上
result = append(result, tmp)
return
}
// 开始遍历原始数组的每个数字
for i:=0; i<len(nums); i++ {
// 检查是否访问过
if !used[i] {
// 没有访问过就选择它，然后标记成已访问过的
used[i] = true
// 做选择：将这个数字加入到路径的尾部，这里用数组模拟链表
pathNums = append(pathNums, nums[i])
backtrack(nums,pathNums,used)
// 撤销刚才的选择，也就是恢复操作
pathNums = pathNums[:len(pathNums) -1]
// 标记成未使用
used[i] = false
}
}
}
func permute(nums []int) [][]int {
var pathNums []int
var used = make([]bool, len(nums))
// 清空全局数组（leetcode多次执行全局变量不会消失）
result = [][]int{}
backtrack(nums, pathNums, used)
return result
}
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
backtrack(nums, result, 0); //从第一个开始处理
return result;
}
void backtrack(vector<int> & nums, vector<vector<int>> & result, int loc){
if (loc == nums.size()) {
result.push_back(nums); //所有数据都处理完成，退出
return;
}
// 从下标位置0 开始处理到 size - 1 loc下标是nums的指针
// i 下标零时一个排列的下标
for (int i = loc; i < nums.size(); i++) {
if (loc != i) {
swap(nums[i], nums[loc]); //使用交换的话，就不用标记这个元素使用过了
}
backtrack(nums, result, loc + 1);
if (loc != i) {
swap(nums[loc], nums[i]);
}
}
}
};
判断一颗树是否是平衡二叉树
题思路
后续遍历+DFS
dfs计算思路：
对于空结点，深度为0
当前深度是左右子树深度的最大值+1， 有效情况直接返回深度
一旦发现左右子树的深度差异超过1，则认为无效，返回-1
一旦发现返回是-1， 直接返回-1
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isBalanced(TreeNode* root) {
return dfs(root) != -1;
}
int dfs(TreeNode* node)
{
if (node != nullptr)
{
int left = dfs(node->left);
if (left == -1)
{
return -1;
}
int right = dfs(node->right);
if (right == -1)
{
return -1;
}
return abs(left-right) > 1 ? -1 : max(left, right) + 1;
}
else
{
return 0;
}
}
};
网友评论