- 不需要额外的空间是指的算法的空间复杂度为O(1)级别
- int result=2 就是不需要额外的空间
- int arr[n] 就是需要额外的空间
- 原地修改数组
for(int i=1;i<nums.size();i++){
if(nums[i]!=nums[i-1]){
nums[count]=nums[i-1];
nums[++count]=nums[i];
}
}
int [256];
memset(Hash,-1,sizeof(Hash));
- java
Integer.MAX_VALUE
Integer.MIN_VALUE
- c++
INT_MIN
INT_MAX
- 数组初始化 １. 错误姿势
int a[3] = {1};
等价于
int a[3] = {1,0,0};
２. 正确姿势
int Hash[256];
memset(Hash,-1,sizeof(Hash));// 不要memset(Hash,-1,２56);
- 26. 删除排序数组中的重复项
- 27. 移除元素（与26类似）
- 66. 加一
- 283. 移动零
- 485. 最大连续1的个数
- 448. 找到所有数组中消失的数字（set）
- 645. 错误的集合（set）
- 442. 数组中重复的数据
- 287. 寻找重复数
- 739. 每日温度
- 定义一个r*c的矩阵
vector<vector<int>> res(r, vector<int>(c));
- 每行和每列元素均按升序排序
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
1. matrix[0][0]是最小元素，matrix[m-1][n-1]是最大元素
2. matrix[i][j]向左，向上构成的矩阵中,matrix[i][j]为最大元素
3. 小于14的元素全在14的左边及上面（一个以14为结尾的小矩阵+11,12）
- 0 ^ a = a
- 0 ^ 1 = 1; 0 ^ 0 = 0; 1 ^ 1 = 0; 1 ^ 0 =1
- 交换律：a ^ b ^ c <=> a ^ c ^ b
int ans =11;
ans=ans ^ 12; // ans=7
- 35. 搜索插入位置
- 367. 有效的完全平方数
- 374. 猜数字大小
- 744. 寻找比目标字母大的最小字母
- 852. 山脉数组的峰顶索引
- 540. 有序数组中的单一元素
- 69. x 的平方根
- 278. 第一个错误的版本
- 153. 寻找旋转排序数组中的最小值
- 34. 在排序数组中查找元素的第一个和最后一个位置
- 167. 两数之和 II - 输入有序数组
- 345. 反转字符串中的元音字母
- 524. 通过删除字母匹配到字典里最长单词
- 633. 平方数之和
- 680. 验证回文字符串 Ⅱ
- 88. 合并两个有序数组
- 19. 删除链表的倒数第N个节点
- 15. 三数之和
- 238. 除自身以外数组的乘积
- 11. 盛最多水的容器
- 209. 长度最小的子数组(滑动窗口)
- 567. 字符串的排列(滑动窗口)
- 438. 找到字符串中所有字母异位词(滑动窗口)
- 674. 最长连续递增序列(滑动窗口)
- 187. 重复的DNA序列(滑动窗口)
- 202. 快乐数(快慢指针)
- 空指针异常
first.next报错 // first=null
first.next.next报错 // first.next.next=null
- 范例
// 24. 两两交换链表中的节点
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy=new ListNode(0);
dummy.next=head;
ListNode first=dummy;
// first.next=null表示剩余0个节点;first.next.next=null表示剩余1个节点，这两种情况不做处理
while(first.next!=null&&first.next.next!=null)
{
// 更新second,nextTmp位置,保证second,nextTmp不为空
ListNode second=first.next;
ListNode nextTmp=second.next;
// 节点交换
second.next=nextTmp.next;// 注意nextTmp.next为null时交换也在进行
first.next=nextTmp;
nextTmp.next=second;
// 更新first位置,first可能为空
first=nextTmp.next;
}
head=dummy.next;
return head;
}
}
- 141. 环形链表(快慢指针)
- 2. 两数相加
- 206. 反转链表
- 21. 合并两个有序链表
- 83. 删除排序链表中的重复元素
- 24. 两两交换链表中的节点
- 445. 两数相加 II
- 234. 回文链表
- 725. 分隔链表
- 328. 奇偶链表
- 只能从父节点到子节点/子树(437,)：可以用两次遍历
- 这条路径可以经过也可以不经过根节点(124,687,543)：将“求经过该根节点的，满足题目要求的路径”转化为“根节点的left单向路径+根节点的right单向路径=满足题目要求的路径”
- 注意两次遍历要求第二次遍历不能是有选择的，不确定的(比如337就不能用二次遍历)。而且两次遍历的效率是很低的，很暴力，没有优化。
path(root.left)
...
path(root.right)
- 先序遍历(二叉树路径/最大深度)：[1 2 4 8 9 5 10 11 3 6 7]
- 中序遍历(二叉搜索树中序遍历序列为升序数组)：[8 4 9 2 10 5 11 1 6 3 7]
- 后序遍历(平衡二叉树)：[8 9 4 10 11 5 2 6 7 3 1]
/**
* boolean类型的递归函数
*/
private boolean preorder(TreeNode p, TreeNode q){
if(p!=null&&q!=null)
{
if(p.val!=q.val)
return false;
else
return preorder(p.left,q.left)&&preorder(p.right,q.right);
}
else if((p!=null&&q==null)||(p==null&&q!=null))
return false;
else
return true;
}
class Solution {
public boolean bal=true;
public boolean isBalanced(TreeNode root) {
balance(root);
return bal;
}
/**
* 自下向上
*/
private int balance(TreeNode p){
if(p!=null&&bal){
int left_depth=balance(p.left);
int right_depth=balance(p.right);
if(Math.abs(left_depth-right_depth)>1){
bal=false;
return 0; // 这里return什么根本不重要
}
else
return Math.max(left_depth,right_depth)+1;
}
else
return 0;
}
}
class Solution {
// 返回类型为TreeNode的递归函数
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if(t1!=null&&t2!=null){
t1.val+=t2.val;
t1.left=merge(t1.left,t2.left);
t1.right=merge(t1.right,t2.right);
return t1; // 这一句会多次执行
}
else if(t1==null&&t2!=null){
return t2;
}
else
return t1;
}
}
- 104. 二叉树的最大深度(自上向下)
- 111. 二叉树的最小深度(自上向下)
- 101. 对称二叉树
- 226. 翻转二叉树(返回类型为TreeNode的递归函数)
- 938. 二叉搜索树的范围和
- 543. 二叉树的直径
- 112. 路径总和
- 437. 路径总和 III(两次遍历)
- 572. 另一个树的子树(两次遍历,与100相似)
- 563. 二叉树的坡度(两次遍历)
- 124. 二叉树中的最大路径和(两次遍历,与543类似)
- 110 平衡二叉树(两次遍历) )
- 404. 左叶子之和
- 687. 最长同值路径
- 671. 二叉树中第二小的节点
- 965. 单值二叉树
- 129. 求根到叶子节点数字之和
- 872. 叶子相似的树(java判断两个数组相同)
class Solution {
public TreeNode trimBST(TreeNode root, int L, int R) {
// 边界
if(root==null)
return null;
// 讨论root的取值,按照不同情形返回不同的值
if(root.val>=L&&root.val<=R){
root.left=trimBST(root.left,L,R);
root.right=trimBST(root.right,L,R);
return root;
}else if(root.val<L){
return trimBST(root.right,L,R);
}else{
return trimBST(root.left,L,R);
}
}
}
- 783. 二叉搜索树结点最小距离(中序遍历，记录序列相邻节点)
- 98. 验证二叉搜索树(中序遍历，记录序列相邻节点)
- 99. 恢复二叉搜索树(中序遍历，记录序列相邻节点)
- 700. 二叉搜索树中的搜索
- 中序遍历：结果一定为升序序列，运用详见230. 二叉搜索树中第K小的元素
- 前序遍历：结果序列的最后一个元素一定为树中最大元素
- 后序遍历：结果序列的第一个元素一定为树中最小元素
- 不连续
if(A[i]==B[j]){
dp[i][j]=dp[i-1][j-1]+1;
}
else{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
比如
对于
[2,6,7,4,1,8],
[4,3,2,7,5,4]
不连续:有dp[1][2]=max(dp[0][2],dp[1][1])=1;则dp[2][3]=dp[1][2]+1=2
连续:dp[2][3]=dp[1][2]+1=0+1=1
- 连续
if(A[i]==B[j]){
dp[i][j]=dp[i-1][j-1]+1;
}
-
- 最长回文子串
class Solution {
public:
string longestPalindrome(string s) {
int size = s.size();
if (size < 2) {
return s;
}
bool dp[size][size];
int maxLen = 1, start = 0;
// 这个双层遍历实现了查找原先字符串的所有子串,注意它做到了先判断dp[8][8],再判断dp[7][9]
for (int i = 0; i < size; ++i) {
dp[i][i] = true; //单个字符本身
for (int j = 0; j < i; ++j) {
if (s[i] == s[j] && (i - j == 1 || dp[j+1][i-1])) {
dp[j][i] = true;
if (i - j + 1 > maxLen) {
maxLen = i - j + 1;
start = j;
}
} else {
dp[j][i] = false;
}
}
}
return s.substr(start, maxLen);
}
};
- 300. 最长上升子序列(不连续)
- 53. 最大子序和(连续)
- 718. 最长重复子数组(连续)
- 70. 爬楼梯(斐波那切数列)
- 62. 不同路径
- 64. 最小路径和
- 198. 打家劫舍
- 213. 打家劫舍 II
- 303. 区域和检索 - 数组不可变
- 392. 判断子序列
- 9. 回文数
- 696. 计数二进制子串
- 整体观(337. 打家劫舍 III)
3
/ \
2 7
\ \
6 1
- 正确思路:看作(节点3+以2为根节点的左子树+以7为根节点的左子树 如果我们取3，那么左子树root.left 和 右子树root.right我们都不能取了；如果我们不取，那么最大值来自于左右子树的和，也就是3.left+3.right。但是对于左右子树来说，又涉及到了上面的问题，我们是取还是不取呢？这样循环递推下去，直到节点为null，我们直接返回0即可。那么我们对于每个节点，都要设计一个结构来描述取和不取这样的操作
- 错误思路:看作(节点3+节点2+节点7) 如果3取，则2，7不能取。然后呢?6,7要不要取呢?感觉好复杂
class Solution {
public int rob(TreeNode root) {
// 一开始是可以偷的，所以flag=1
return robCurrentNode(1, root);
}
public int robCurrentNode(int flag, TreeNode root) {
if (root == null) return 0;
// 如果当前节点可以偷,return 偷左右子树的情况下.max(不偷当前节点,偷当前节点)
if (flag == 1) return Math.max(robCurrentNode(1, root.left)+robCurrentNode(1, root.right), robCurrentNode(0, root.left)+robCurrentNode(0, root.right)+root.val);
// 如果当前节点不可以偷,return 偷左右子树.不偷当前节点
else return robCurrentNode(1, root.left)+robCurrentNode(1, root.right);
}
}
- 由"dog cat cat dog"得到["dog","cat","cat","dog"]
int len=str.size();
int pos=0;
vector<string> words;
while(pos!=-1){
pos=str.find_first_of(' ');
words.push_back(str.substr(0,pos));
str=str.substr(pos+1,len-pos-1);
}
int main() {
int Hash[256];
string str="aaa";
for(int i=0;i<3;i++){
Hash[str[i]]++;
}
cout<<Hash['a']; // 3
string str2="AAA";
for(int i=0;i<3;i++){
Hash[str2[i]]++;
}
cout<<Hash['a']; // 2326231
}
class Solution {
public:
int numJewelsInStones(string J, string S) {
int Hash[58]={0};
int count=0;
for(int i=0;i<J.size();i++){
Hash[J[i]-'A']++;
}
for(int i=0;i<S.size();i++){
if(Hash[S[i]-'A']==1)
count++;
}
return count;
}
};
void DFS(int x){
// 到达叶节点
if(x==len){
cnt++;
// 如果是第k个排列
if(cnt==seq){
for(int i=0;i<len;i++){
res+=a[i]+'0';
}
}
}
for(int i=0;i<len;i++){
if(vest[i]==false){
a[x]=nums[i];
vest[i]=true;
DFS(x+1);
vest[i]=false;
}
}
}
背包结果一定保证index有序，即不会得到 nums[8] nums[4] nums[1] nums[10] 这种结果
void DFS(int index,int cnt){
// 到达叶节点
if(index==maxSize){
// 一定要写在if(index==maxSize)里面
if(cnt==targetNum){
temp.clear();
for(int i=0;i<cnt;i++){
temp.push_back(a[i]);
}
res.push_back(temp);
}
return;
}
// 选
if(cnt<=targetNum-1){
a[cnt]=nums[index];
DFS(index+1,cnt+1);
}
// 不选
DFS(index+1,cnt);
}
- 指针的用法
#include<iostream>
using namespace std;