刷题笔记
最近在准备面试，发现自己真的菜的不行，就计划接下来的时间把 leetcode 上面刷的 中等题 和 每日一题做个简书笔记。稍微记录一下，等保研时或许还有用。
- 旋转图像
题目：给定一个 n × n 的二维矩阵表示一个图像。将图像顺时针旋转 90 度。
说明：给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
思路：可以先沿着反对角线转一次，再从中间转一次。
class Solution {
//解题思路：先沿着对角线转一次，再沿着水平线转一次
public void rotate(int[][] matrix) {
for(int i = 0; i < matrix.length; i++){
for(int j = 0; j <matrix.length - i ; j++){
swap(matrix,i,j,matrix.length-1-j,matrix.length-1-i);
}
}
for(int i = 0; i < matrix.length/2; i++){
for(int j = 0; j <matrix.length; j++){
swap(matrix,i,j,matrix.length-1-i,j);
}
}
}
//swap element i and j
public void swap(int matrix[][],int ix,int iy,int jx,int jy){
int temp = matrix[ix][iy];
matrix[ix][iy] = matrix[jx][jy];
matrix[jx][jy] = temp;
}
}
- 有效的数独：
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
输出：true
思路：
- 可以遍历三次 9*9 数组，分别判断是否符合三个要求
- 可以只遍历一次，访问每一个元素时判断三个要求是否被违背：可以用二进制位来表示一列 / 一行 / 一个 3*3的 Grid 中的状态，使用位操作更新。
class Solution {
private final int VERTICAL = 0;
private final int HORIZONTAL = 1;
private final int GRID = 2;
public boolean isValidSudoku(char[][] board) {
int status[] = new int[27];//一列、一格、一行有九个状态，九个bit就够,总共27个。
for(int i = 0 ; i < 9; i ++){
for(int j = 0; j < 9; j ++){
if(board[i][j] !='.'){
int n = board[i][j] - '0';
if(!checkAndSet(status, VERTICAL ,i, n)){
return false;
}
if(!checkAndSet(status, HORIZONTAL, j,n)){
return false;
}
if(!checkAndSet(status, GRID, (i/3) * 3 + (j/3), n)){
return false;
}
}
}
}
return true;
}
/*
* @param type : VERTICAL(从上到下), HORIZONTAL(从左到右)，GRID(3*3)
* @param index : 这一类中的第 index 行/列/格子。
* @param num : 数字 1-9
*/
public boolean checkAndSet(int status[], int type, int index, int num){
int i = type * 9 + index;
if((status[i] & (1 << (num-1))) == 0 ){
status[i] = (status[i]^(1<<(num-1)));
return true;
}
return false;
}
}
这里使用了short，内存使用率为 9/16，可以换成int，会把内存使用率提高到 27/32。
- 跳跃游戏
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
思想：将数组中分成“好位置”和“坏位置”，可以从好位置跳到最后而坏位置不可以；动态规划，从后向前(反过来也行)一格一格的试探好位置，并记录目前最靠前的好位置
public boolean canJump(int[] nums) {
int last = nums.length-1;//数组的最后一个位置一定是“好位置”
for(int j = last-1; j >-1; --j){
if(last - j <= nums[j]){
last = j;
}
}
if(last == 0){
return true;
}
return false;
}
}
- 第k个排列
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列。
输入: n = 3, k = 3
输出: "213"
class Solution {
public String getPermutation(int n, int k) {
List<Integer> l = new ArrayList<>();
l.add(1);
int fac[] = new int[n];
fac[0] = 1;
for(int i = 1; i < n; i++){
fac[i] = fac[i-1] * i; //初始化到一个数组中，运用动态规划。
l.add(i+1);
}
StringBuilder builder = new StringBuilder("");
k--;
//观察序列，n = 3 的全排列，第一个数index是 (位置-1)/2 ,第二个数是(位置-1)/1,第三个数是(位置-1)/1，除数除了最后一项是1，符合n!,只需要维护一个数组，按照计算得到的idx从数组中取出并删除。
for(int i = n-1; i >= 0; --i){
int idx = k / fac[i];
k -= idx * fac[i];
builder.append((char)(l.get(idx)+'0'));//要先强制转型，否则append会把后面的树作为int处理，得到4950这样的
l.remove(idx);
}
return builder.toString();
}
}
- 多数元素
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
输入: [3,2,3]
输出: 3
我使用的解法是哈希映射的方法，太naive，不贴代码了，记录下官方十分强大的投票算法。
//如果我们把众数记为 +1+1，把其他数记为 -1−1，将它们全部加起来
//，显然和大于 0，从结果本身我们可以看出众数比其他数多。
class Solution {
public int majorityElement(int[] nums) {
int count = 0;
Integer candidate = null;
for (int num : nums) {
if (count == 0) {
candidate = num;
}
count += (num == candidate) ? 1 : -1;
}
return candidate;
}
}
//作者：LeetCode-Solution
//链接：https://leetcode-cn.com/problems/majority-element/solution/duo-shu-yuan-su-by-leetcode-solution/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
这里的candidate可能不是众数，但是没有关系，由于众数占多数，在数组中总是可能出现count=0的时候，这时会重新选择候选人，其他人投出去的选票，总是会被众数投出去的抵消掉。
- 旋转链表：
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
暴力的解法可以遍历列表k遍，每次将最后一个节点置于第一个，时间复杂度(k*n)。
更好的方法是：将首尾相连，将head相连，将head和last都向后挪动 n - k%n 位。
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head==null ){
return null;
}
ListNode l = head;
int n = 1;
while(l.next!=null){
l = l.next;
n++;
}
l.next = head;
for(int i = 0; i < n - k%n; i++){ //注意这里要%n，否则k>n时出问题。
head = head.next;
l = l.next;
}
l.next = null;
return head;
}
}
- 不同路径
- 一道很典型的动态规划题，方程很好找。
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
无障碍物版本：
class Solution {
// len(x,y) = len(x+1,y) + len (x,y+1);
// len (m, n-1) = 1;
public int uniquePaths(int m, int n) {
int res[][] = new int[m][n];
res[m-1][n-1] = 1;
for(int i = m -1 ; i >=0; --i){
for(int j = n-1; j >=0; --j){
if(j < n - 1){
res[i][j] += res[i][j+1];
}
if(i < m - 1){
res[i][j] += res[i+1][j];
}
}
}
return res[0][0];
}
}
障碍物版本
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int res[][] = new int[m][n];
if(obstacleGrid[m-1][n-1] == 0){
res[m-1][n-1] = 1;
}
for(int i = m - 1 ; i >=0; --i){
for(int j = n - 1; j >=0; --j){
if(obstacleGrid[i][j] == 0){
if(j < n - 1){
res[i][j] += res[i][j+1];
}
if(i < m - 1){
res[i][j] += res[i+1][j];
}
}
}
}
return res[0][0];
}
}
- 最短路径
class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int res[][] = new int[m][n];
res[m-1][n-1] = grid[m-1][n-1];
for(int i = m - 1 ; i >=0; --i){
for(int j = n - 1; j >=0; --j){
if(i == m-1 && j < n-1){
res[i][j] = res[i][j+1] +grid[i][j];
}
if(j == n-1 && i < m-1){
res[i][j] = res[i+1][j] + grid[i][j];
}
if(j < n - 1 && i < m-1){
res[i][j] = Math.min(res[i][j+1] ,res[i+1][j]) +grid[i][j];
}
}
}
return res[0][0];
}
}
- 简化路径
以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。
示例 1：
输入："/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。
示例 2：
输入："/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。
示例 3：
输入："/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
示例 4：输入："/a/./b/../../c/"
输出："/c"
示例 5：
输入："/a/../../b/../c//.//"
输出："/c"
示例 6：
输入："/a//b////c/d//././/.."
输出："/a/b/c"
思路：使用LinkedList 模拟栈来简化路径
class Solution {
LinkedList<String> list = new LinkedList<>();
public String simplifyPath(String path) {
String[] strs=path.split("/");
for(String str: strs){
if(str.equals("")||str.equals(".")){
continue;
}
if(str.equals("..")){
if(list.size()>0){
list.removeLast();
}
} else {
list.addLast(str);
}
}
StringBuilder sb= new StringBuilder("");
if(list.size() == 0){
return "/";
}
for(String str:list){
sb.append("/");
sb.append(str);
}
return sb.toString();
}
}
- 拼写单词
- 给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。
假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。
注意：每次拼写时，chars 中的每个字母都只能用一次。
提示：
1 <= words.length <= 1000
1 <= words[i].length, chars.length <= 100
所有字符串中都仅包含小写英文字母
思路：限制了只会出现小写字母(连续)，那么我们可以去统计单词中每个字母出现的次数存在数组中，如果A单词中的每个字母的出现次数都小于等于B单词中的出现次数，可以认为是“掌握了”
class Solution {
public int countCharacters(String[] words, String chars) {
int chs[] = new int[26];
for(char ch :chars.toCharArray()){
chs[ch-'a']++;
}
int res = 0;
for(String str:words){
int s[] = new int[26];
for(char ch : str.toCharArray()){
s[ch-'a']++;
}
boolean f = false;
for(int i = 0; i < 26; ++i){
if(s[i] > chs[i]){
f = true;
break;
}
}
if(!f){
res+=str.length();
}
}
return res;
}
}
- 搜索二维矩阵
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
输出: true
这个脑子就是得转一下，我死命想用两次二分法在两个维度上分别搜索，但是死活不行，看完力扣官方题解之后茅塞顿开。什么有序二维数组，从内存的角度上来看就是个有序的一维数组嘛！
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix.length==0){
return false;
}
int m = matrix.length;
int n = matrix[0].length;
int low = 0;
int high = m * n -1;
int mid = (low+high)/2;
while(low <= high){
int val = matrix[mid/n][mid%n];
if(val < target){
low = mid + 1;
} else if(val == target){
return true;
} else {
high = mid - 1;
}
mid = (low+high)/2;
}
return false;
}
}
- 颜色分类
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地**对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
进阶：
- 一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。 - 你能想出一个仅使用常数空间的一趟扫描算法吗？
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
思路，桶排序。
class Solution {
public void sortColors(int[] nums) {
int colors[] = new int[3];
for(int i =0; i< nums.length;++i){
colors[nums[i]]++;
}
int j = 0;
for(int i = 0; i < nums.length;++i){
while( j < 3 && colors[j] == 0){
j++;
}
if(j==3){
break;
}
nums[i] = j;
colors[j]--;
}
}
}
- 无重复最长子串
- 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
解题思路：使用动态规划，存放每一个字母最近出现的下标的下一位。使用一次扫描而结果就是在迭代过程中的 max(oldVal, 右指针-max(左指针,index[右指针所在字母]+1,)
class Solution {
public int lengthOfLongestSubstring(String s) {
int index[] = new int[256];//存放字母出现的下标的下一位，会随着扫描更新为最右的坐标，0表示还没出现过
int res = 0;
int i = 0;//左指针
for(int j = 0; j < s.length(); ++j){
i = Math.max(index[s.charAt(j)],i);//如果当前字母在i之后出现过，那么左指针就要更新到之前出现过位置的下一位，若没有出现，i不变。
res = Math.max(res, j-i+1);// 更新一下res
index[s.charAt(j)] = j+1;// 更新index
}
return res;
}
}
- 删除排序数组中的重复项
class Solution {
public int removeDuplicates(int[] nums) {
if(nums.length==0){
return 0;
}
int oldVal = nums[0];
int res = 1;
int j = 1;
for(int i = 1; i < nums.length; ++i){
if(oldVal!=nums[i]){
j = 1;
nums[res++] = nums[i];
oldVal = nums[i];
} else if(j < 2&&nums[i]==oldVal){
nums[res++] = nums[i];
j++;
}
}
return res;
}
}
- 最大子序和
考虑到有负数有正数，
- 极端情况，全是负数，那么就相当于找最小元素
- 如果只有一个正数，那么正数所在的大小为1的序列就是最大子序
可以考虑使用动态规划：- 记录一个大小为n的数组，记录包含当前元素为子序列最后一个元素时的最大子序和。
- 如果之前的子序和大于0，那么当前的最大子序列和等于之前最大子序列和加上当前元素，否则就是当前元素。在迭代的过程中记录最大的子序列和。
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length, maxSum = nums[0];
for(int i = 1; i < n; ++i) {
if (nums[i - 1] > 0) nums[i] += nums[i - 1];//原地修改
maxSum = Math.max(nums[i], maxSum);//记录最大子序列和
}
return maxSum;
}
}
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
1 <---
/
2 3 <---
\
5 4 <---
思路：使用队列辅助广度优先遍历，记录树的深度。有一个无意间发现的小技巧，我在开始写的时候按照正常思路从左向右遍历子树，发现得到的是 二叉树的左视图，变换遍历顺序之后，得到了二叉树的右视图。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
class Pair{
int depth;
TreeNode n;
Pair(TreeNode n, int depth){
this.n = n;
this.depth = depth;
}
}
public List<Integer> rightSideView(TreeNode root) {
if(root == null){
return new ArrayList<>();
}
LinkedList<Pair> q = new LinkedList<>();
q.addLast(new Pair(root,0));
List<Integer> l = new ArrayList<>();
int prevDepth = -1;
while(!q.isEmpty()){
Pair p = q.removeFirst();
if(p.depth!=prevDepth){
l.add(p.n.val);
}
if(p.n.right!=null){//先右子
q.addLast(new Pair(p.n.right,p.depth+1));
}
if(p.n.left!=null){//再左子
q.addLast(new Pair(p.n.left,p.depth+1));
}
prevDepth = p.depth;
}
return l;
}
}
给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2)。
图中子矩阵左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，该子矩形内元素的总和为 8。
image
给定 matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
]
sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
说明:
你可以假设矩阵不可变。
会多次调用 sumRegion 方法。
你可以假设 row1 ≤ row2 且 col1 ≤ col2。
- 思路：由于会调用多次sumRegion方法，一般的暴力解法会超时。
可以先计算所有(i,j)的 sumRegion(0,0,i,j) ，记为s(i, j), 则
class NumMatrix {
//注意这里的sumRegion会调用多次
int sum[][];
public NumMatrix(int[][] matrix) {
if(matrix.length==0){
return;
} else {
int m = matrix.length;
int n = matrix[0].length;
sum = new int[m+1][n+1];//sum下标从1开始，小 trick，
for(int i = 0; i < m; ++i){
for(int j= 0; j < n; ++j){
sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] + matrix[i][j] - sum[i][j];
}
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
return sum[row1][col1] + sum[row2+1][col2+1] - sum[row1][col2+1] - sum[row2+1][col1];
}
}
- 01矩阵
给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。给定的矩阵元素不超过10000个
两个相邻元素间的距离为 1 。
示例 1:
输入:
0 0 0
0 1 0
0 0 0
输出:
0 0 0
0 1 0
0 0 0
示例 2:
输入:
0 0 0
0 1 0
1 1 1
输出:
0 0 0
0 1 0
1 2 1
思路：两遍dp，一次从左上往右下，一次从右下往左上。
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
int row = matrix.size();
if(row == 0){
return matrix;
}
int col = matrix[0].size();
vector<vector<int>> distance(row,vector(col,INT_MAX - 10000));//-10000是因为
for(int i = 0; i < row; ++i){
for(int j = 0; j < col; ++j){
if(matrix[i][j]==0){//第一次扫描的时候看看标记出来0
distance[i][j] = 0;
} else {
if(i>0){//注意边界条件
distance[i][j] = min(distance[i-1][j]+1,distance[i][j]);
}
if(j>0){
distance[i][j] = min(distance[i][j-1]+1,distance[i][j]);
}
}
}
}
for(int i = row-1; i >=0; --i){
for(int j = col-1; j >=0; --j){
if(i<row-1){
distance[i][j] = min(distance[i+1][j]+1,distance[i][j]);
}
if(j<col-1){
distance[i][j] = min(distance[i][j+1]+1,distance[i][j]);
}
}
}
return distance;
}
};
感觉如果不知道起点在哪的时候：(0,0) 不一定是0，需要我们去搜索一下，可以用这种方式解决。这里使用了两次dp，正好cover了所有情况(向左，向右，向上，向下)
- 机器人的运动范围
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
思路：
把和的格子看成障碍物，直接以（0,0）作为起点，使用bfs搜索。
class Solution {
// 计算 x 的数位之和
int get(int x) {
int res=0;
for (; x; x /= 10) {
res += x % 10;
}
return res;
}
public:
int movingCount(int m, int n, int k) {
if (!k) return 1;
queue<pair<int,int> > Q;
// 向右和向下的方向数组
int dx[2] = {0, 1};
int dy[2] = {1, 0};
vector<vector<int> > vis(m, vector<int>(n, 0));
Q.push(make_pair(0, 0));
vis[0][0] = 1;
int ans = 1;
//需要证明，如果sum(m)+sum(n)<k,则一定有一条路径
while (!Q.empty()) {
auto [x, y] = Q.front();
Q.pop();
for (int i = 0; i < 2; ++i) {
int tx = dx[i] + x;
int ty = dy[i] + y;
if (tx < 0 || tx >= m || ty < 0 || ty >= n || vis[tx][ty] || get(tx) + get(ty) > k) continue;
Q.push(make_pair(tx, ty));
vis[tx][ty] = 1;
ans++;
}
}
return ans;
}
};
- 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例：
输入：n = 3
输出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
使用回溯法：
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> res;
generate(n*2,n,res,"",0);
return res;
}
void generate(int n,int l/*左括号剩余个数*/, vector<string>& v,string str,int m/*字符串中左括号比右括号多的个数*/){
if(n<1){
v.push_back(str);
return;
}
if(l > 0){
// str = str + '('; 别这么写，会影响下面的case！！！
generate(n-1,l-1,v,str+'(',m+1);
}
if(m > 0){
// str = str + ')';
generate(n-1,l,v,str+')',m-1);
}
}
};
- 二叉树插入
给定一个二叉树，根节点为第1层，深度为 1。在其第 d 层追加一行值为 v 的节点。
添加规则：给定一个深度值 d （正整数），针对深度为 d-1 层的每一非空节点 N，为 N 创建两个值为 v 的左子树和右子树。
将 N 原先的左子树，连接为新节点 v 的左子树；将 N 原先的右子树，连接为新节点 v 的右子树。
如果 d 的值为 1，深度 d - 1 不存在，则创建一个新的根节点 v，原先的整棵树将作为 v 的左子树。
输入:
二叉树如下所示:
4
/ \
2 6
/ \ /
3 1 5
且 v = 1 d = 2输出:
4
/ \
1 1
/ \
2 6
/ \ /
3 1 5
思路： 使用bfs获得第d-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:
TreeNode* addOneRow(TreeNode* root, int v, int d) {
if(root==nullptr){
return root;
}
if(d==1){
TreeNode* newRoot = new TreeNode(v);
newRoot->left = root;
return newRoot;
}
pair<TreeNode*,int> rootpair = make_pair(root,1);
queue<pair<TreeNode*,int>> q;//记录深度
q.push(rootpair);
while(!q.empty()){
auto [node, curDepth] = q.front();
if(curDepth==d-1){
break;
}
q.pop();
if(node->left!=nullptr){
q.push(make_pair(node->left,curDepth+1));
}
if(node->right!=nullptr){
q.push(make_pair(node->right,curDepth+1));
}
}
while(!q.empty()){
auto [node, curDepth] = q.front();
q.pop();
TreeNode* leftTemp = node->left;
TreeNode* rightTemp = node->right;
node -> left = new TreeNode(v);
node -> right = new TreeNode(v);
node -> left -> left = leftTemp;
node -> right -> right = rightTemp;
}
return root;
}
};
- 相同的树
给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(!p&&!q){
return true;
}
if((p&&!q)||(!p&&q)||p->val!=q->val){
return false;
}
queue<TreeNode*> pQ;
queue<TreeNode*> qQ;
pQ.push(p);
qQ.push(q);
while(!pQ.empty()){
TreeNode* ptmp = pQ.front();
TreeNode* qtmp = qQ.front();
pQ.pop();
qQ.pop();
if(qtmp->left||ptmp->left){
if(!qtmp->left || !ptmp->left || ptmp->left->val != qtmp->left->val){
return false;
}
pQ.push(ptmp->left);
qQ.push(qtmp->left);
}
if(qtmp->right||ptmp->right){
if(!qtmp->right || !ptmp->right || ptmp->right->val != qtmp->right->val){
return false;
}
pQ.push(ptmp->right);
qQ.push(qtmp->right);
}
}
return true;
}
};
衍生：对称二叉树：
给定一个二叉树，检查它是否是镜像对称的。
思路：一个树如果是对称的，那它左子和右子的值一定相等，左子的左子和右子的右子一定对称。
bool isSymmetric(TreeNode* root){
if(!root){
return true;
}
return isMirror(root->left,root->right);
// if(!root||(!root->left&&!root->right)){ return true;}
//wrong!
// if(root->left&&root->right){
// return isSymmetric(root->left)&&isSymmetric(root->right)&& root->left->val==root->right->val;
// } else {
// return false;
// }
}
bool isMirror(TreeNode* node1,TreeNode* node2){
if(!node1&&!node2){
return true;
}
if(!node1||!node2){
return false;
}
return (node1->val == node2 ->val)
&& isMirror(node1->left,node2->right)
&& isMirror(node1->right,node2->left);
}
- 二叉树展开为链表
给定一个二叉树，原地将它展开为链表。
TIM截图20200415101029.png
方案一，自顶向下搜索，将左子树挂在右子上，原有的右子树挂在现在最右节点的右边。
public:
void flatten(TreeNode* root){
while(root){
if(!root->left){
root = root->right;
} else {
TreeNode* r = root -> right;
root -> right = root -> left;
root -> left = nullptr;
TreeNode* tmp = root;
while(tmp->right){
tmp = tmp -> right;
}
tmp -> right = r;
root = root->right;
}
}
}
方案二，不难看出链表化后的二叉树是其前序遍历的版本，我们可以反其道而行之，使用后序遍历，头插到链表上。
TreeNode* pre;//当前链表
void flatten(TreeNode* root){//后序遍历
if(!root){
return;
}
flatten(root->right);
flatten(root->left);
//头插入链表
root->right = pre;
pre = root;
//记得把left置null
root->left = nullptr;
}
- 合并区间
给出一个区间的集合，请合并所有重叠的区间。
示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
思路：先对于intervals 按照左区间大小排序，从前向后遍历，步长为1，如果可以合并（R1 > L2），就合并
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if(intervals.size()==0){
return {};
}
sort(intervals.begin(),intervals.end());
vector<vector<int>> res;
for(int i = 0; i< intervals.size(); ++i){
int L = intervals[i][0],R = intervals[i][1];
if(res.empty()|| L >res.back()[1] ){
res.push_back({L,R});
} else {
res.back()[1] = max(res.back()[1],R);
}
}
return res;
}
};
- 反转链表 II
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
int i = 0;
ListNode* h = new ListNode(0);
h->next = head;
ListNode* prev = h;
for(int i = 0; i < m-1; ++i){
prev=prev->next;
}
ListNode* rStart = prev->next;//反转前第m个节点，
ListNode* end = rStart; //反转后的第n个节点
ListNode* rBetween = new ListNode(0);//反转的过程以头插法，插入这个列表
for(int i = m-1; i< n; ++i){
ListNode* tmp = rStart->next;
rStart->next = rBetween->next;
rBetween->next = rStart;
rStart = tmp;
}
prev->next = rBetween->next;
end->next = rStart;
return h->next;
}
};
- 反转链表
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
class Solution {
public:
//迭代版本
// ListNode* reverseList(ListNode* head) {
// ListNode* h = new ListNode(0);
// h->next = head;
// ListNode* res = new ListNode(0);
// while(h->next!=nullptr){
// h = h -> next;
// ListNode* tmp = res -> next;
// res->next = new ListNode(h->val);
// res->next -> next = tmp;
// }
// return res->next;
// }
//递归
ListNode* reverseList(ListNode* head){
if(!head||!head->next){
return head;
}
ListNode* res = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return res;
}
};
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
思路：根据平衡二叉搜索树定义，两个节点（2, 4）的最近公共祖先的值（2）一定大于等于较小节点（4）且小于等于较大节点（4），且最近公共祖先的父节点的值(6)一定同时大于两个节点或同时小于两个节点。
/**
* 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:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root||!p||!q){
return root;
}
TreeNode* res = root;
while(res){
if(res->val >= p->val && res->val >= q->val){//等于是
if(res->val == p->val || res->val ==q->val){//防止 2,4 都大于等于2，即示例 2
break;
}
res = res->left;
} else if(res->val <= p->val && res->val <= q->val){
if(res->val == p->val || res->val ==q->val){
break;
}
res = res->right;
} else {
break;
}
}
return res;
}
};
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:
输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
思路：动态规划
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if(n==0){
return 0;
}
int dp[n][3];
dp[0][0]=0;//当天不持股，且当天没卖出
dp[0][1]=-prices[0];//第i天持股
dp[0][2]=0;//当天不持股，股票是当天卖出的，第0天特殊情况，认为当天买入当天卖出
for(int i = 1; i< n ;i++){
dp[i][0] = max(dp[i-1][0],dp[i-1][2]); //
dp[i][1] = max(dp[i-1][0]-prices[i],dp[i-1][1]);
dp[i][2] = dp[i-1][1]+prices[i];
}
return max(dp[n-1][0],dp[n-1][2]);//
}
};
```
28. 超级丑数
超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。
> 示例:
输入: n = 12, primes = [2,7,13,19]
输出: 32
解释: 给定长度为 4 的质数列表 primes = [2,7,13,19]，前 12 个超级丑数序列为：
[1,2,4,7,8,13,14,16,19,26,28,32] 。
使用动态规划，观察一下规律：
* 开始时丑数序列dp为 $[1]$
* $dp[1] = min(dp[0] * prime[0],dp[0] * prime[1],dp[0] * prime[2],dp[0] * prime[3]) = dp[0]* prime[0] =2$
* $dp[2] = min(dp[1] * prime[0],dp[0] * prime[1],dp[0] * prime[2],dp[0] * prime[3]) = dp[1]* prime[0]=4$
* $dp[3] = min(dp[2] * prime[0],dp[0] * prime[1],dp[0] * prime[2],dp[0] * prime[3])= dp[0]* prime[1]=7$
* $dp[4] = min(dp[2] * prime[0],dp[1] * prime[1],dp[0] * prime[2],dp[0] * prime[3]) = dp[2]*prime[0]=8$
* $dp[5] = min(dp[3] * prime[0],dp[1] * prime[1],dp[0] * prime[2],dp[0] * prime[3]) = dp[0]*prime[2]=13$
* **! dp[6]中出现了 2 * 7 和 7 * 2 相等的情况，需要都考虑进来并去重。** $dp[6] = min(dp[3] * prime[0],dp[1] * prime[1],dp[1] * prime[2],dp[0] * prime[3]) = dp[3]*prime[0]= dp[1] * prime[1] =14$
根据上述规律，维护下两个数组：
* index数组：index[j] 是第j个prime当前在dp的下标
* dp：超级丑数序列。
```c++
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
if(n==0){
return 1;
}
int dp[n];
dp[0]=1;
int k = primes.size();
vector<int> index(k,0);
for(int i = 1; i < n; ++i){
int minVal = INT_MAX;
for(int j = 0; j < k; ++j){
if(dp[index[j]] * primes[j]<minVal){
minVal = dp[index[j]] * primes[j];
}
}
for(int j =0; j < k; ++j){//去重 2*7 和 7*2
if(dp[index[j]]* primes[j] == minVal){
++index[j];
}
}
dp[i]=minVal;
}
return dp[n-1];
}
};
- 硬币
给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)
示例1:
输入: n = 5
输出：2
解释: 有两种方式可以凑成总金额:
5=5
5=1+1+1+1+1
示例2:
输入: n = 10
输出：4
解释: 有四种方式可以凑成总金额:
10=10
10=5+5
10=5+1+1+1+1+1
10=1+1+1+1+1+1+1+1+1+1
思路：动态规划
-
一开始我想的是这样的一个方程，但是结果不对，原因是因为1+5和5+1会被认为是6的两种找零方式。
img_0835.png
-
修改后的方程：
TIM截图20200423182940.png
实现：
class Solution {
public:
int mod = 1000000007;
int coins[4] = {1,5,10,25};
int waysToChange(int n) {
if(n==0){
return 0;
}
int dp[n+1];
for(int i = 1; i<=n; ++i){
dp[i]=0;
}
dp[0]=1;
for(int i = 0; i <4; ++i){
int coin=coins[i];
for(int j = coin; j <= n; ++j){
dp[j] = (dp[j]+dp[j-coin])%mod;
}
}
return dp[n];
}
};
给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
示例:
输入: 3
输出: 5
解释: 给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
TIM截图20200424082620.png
class Solution {
public:
int numTrees(int n) {
if(n==0){
return 1;
}
int dp[n+1];//dp[i]表示有i个节点的组成树的个数
dp[0] = 1;
for(int i=1; i <= n; ++i){
int tmp = 0;
for(int j=0; j < i;++j){
tmp += dp[j]*dp[i-j-1];
}
dp[i] = tmp;
}
return dp[n];
}
};
- 螺旋矩阵
给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
示例 1:
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]
思路：使用4个变量{l, r, b, t}记录一个bounding box，按照螺旋的顺序，对box进行遍历：
- 如果矩阵的大小是{x, y}，一开始 {l,r,t,b} = {0, y-1, 0, x-1}
- 然后从左遍历box中的第一行，top 向下移动一个单位，如果 top 比 bottom还低（即 boundingbox中只剩一行）结束。
- 从上到下遍历最后一列，...
- 从右到左遍历最后一行，...
- 从下到上遍历第一列，...
- back to 1
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int len = matrix.size();
if(len==0){
return vector<int>();
}
int t = 0,l= 0,b=len,r=matrix[0].size();
vector<int> res;
while(true){
for(int i = l; i < r; ++i){
res.push_back(matrix[t][i]);
}
t++;
if(t==b){
break;
}
for(int i = t; i < b; ++i){
res.push_back(matrix[i][r]);
}
r--;
if(r==l){
break;
}
for(int i = r; i >= l; --i){
res.push_back(matrix[b][i]);
}
b--;
if(t==b){
break;
}
for(int i = b; i >= t; --i){
res.push_back(matrix[i][l]);
}
l++;
if(l==r){
break;
}
}
return res;
}
};
- 验证二叉搜索树
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
思路：一开始的时候没有注意到是整个左子树的节点都要小于，右子树都要大于。所以没有考虑到这种case
TIM截图20200425220044.png
需要在递归的时候加上一个上下界的判断。
bool isValidBST(TreeNode* root) {
if(!root){
return true;
}
return isValidBST(root,((long)INT_MIN)-1,((long)INT_MAX)+1);//long是需要考虑边界值的情况
}
bool isValidBST(TreeNode* root, long min, long max){
return root->val > min && root->val < max
&& (!root->left ||isValidBST(root->left,min,root->val))
&& (!root->right||isValidBST(root->right,root->val,max));
}
- 合并 k 个有序列表：
先实现有序列表的两两合并，再进行归并式的合并，分而治之。
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.size()==0){
return nullptr;
}
return merge(lists,0,lists.size()-1);
}
ListNode* merge(vector<ListNode*> v, int start,int end){
if(start == end){
return v[start];
}
int mid = start+end >> 1;
return merge2Lists(merge(v,start,mid),merge(v,mid+1,end));
}
ListNode* merge2Lists(ListNode* l1,ListNode* l2) {
ListNode* head = new ListNode(0);
ListNode* tmp = head;
while(l1 && l2){
if(l1->val < l2->val){
head -> next = l1;
l1 = l1 -> next;
} else {
head -> next = l2;
l2 = l2 ->next;
}
head = head-> next;
}
head -> next = l1? l1:l2 ;
return tmp->next;
}
};
-
数组中数字出现的次数
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
思路：先考虑一个简单一点的case，如果一个组中只有一个出现一次的数字，其他数字都出现了2次，那么我们可以将整个列表异或得到那个只出现一次的数据：
int ret = 0;
for(int n : nums)
ret ^= n;
那可以将上面的问题变成：
- 先将给定的数组分为两个 只有一个出现一次的数字，其他数字都出现了2次 的两个数组
- 分别对于两个数组进行异或，得到结果
问题就是在如何实现1上面，为了实现1，分到的数组有两个要求：
1）两个只出现一次的数字需要被分到两个组
2）任意一对大小相同的数字要被分到一个组
这个要求依旧可以巧妙的使用异或解决：
将整个数组全员异或得到一个值，由于一个数组中有两个只出现一次的树，所以
中肯定有一位是1，记录下这个1的位置，用这个bit位的值将数组一分为二。这个分组方法满足我们上面的要求：
- 由于在这个位置bit相同的数字会分到同一个数组，所以两个相同的数字会被分到同一组，满足1）
- 由于在
中这个位是1，证明只出现一次的两个数在这个位上的bit值不同，所以这两个只出现一次的数字不会出现在同一个组中，满足2）。
实现：
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
int ret = 0;
for(int n : nums)
ret ^= n;
int div = 1;
while((div & ret) == 0)
div <<= 1;
int a=0, b=0;
for(int n: nums)
if(n & div)
a ^= n;
else
b ^= n;
return vector<int>{a,b};
}
};
- 子集
- 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
思路：递归
实现：
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> subsets(vector<int>& nums) {
vector<int> list= {};
func(list,0,nums);//这里nums没排序也过了，不过要注意一下，如果题目没有明确是否有序还是要排一下
return res;
}
void func(vector<int>& list,int index, vector<int> nums){
if(index == nums.size()){
res.push_back(list);
return;
}
for(int i = index; i < nums.size();++i){
list.push_back(nums[i]);
func(list, i+1,nums);
list.pop_back();
}
func(list,nums.size(),nums);
}
};
- 子集
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
img_0836.png
可以看到两个重复的2，我们只保留了第一个，这样得到的子集集合就是答案：
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<int> list= {};
sort(nums.begin(),nums.end());
func(list,0,nums);
return res;
}
void func(vector<int>& list,int index, vector<int> nums){
if(index == nums.size()){
res.push_back(list);
return;
}
for(int i = index; i < nums.size();++i){
if(i > index && nums[i] == nums[i-1]){ /*注意 i > index 而不是 > 0 否则会错误的将[2,2]所在的枝子剪掉*/
continue;
}
list.push_back(nums[i]);
func(list, i+1,nums);
list.pop_back();
}
func(list,nums.size(),nums);
}
};
- 格雷编码
格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。
给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。即使有多个不同答案，你也只需要返回其中一种。
格雷编码序列必须以 0 开头。
是一道找规律的题：
0 -> [0]
1 -> [ 0, 1]
2 -> [ 00, 01, 11, 10]
3 -> [000,001,011,010,
110, 111,101,100]
2 中的 00,01可以认为是1中的[0,1]前面加了个0，也就是没变；而11,10可以认为是1中的[0,1]倒序过来再加个1。
class Solution {
public:
vector<int> grayCode(int n) {
vector<int> result(1,0);
for(int i = 0; i < n; i++){
int mask = 1 << i;
for(int j = result.size()-1; j>=0; --j){
result.push_back(mask^result[j]);
}
}
return result;
}
};
- 二叉树锯齿状层次遍历
要求：层次遍历的基础上，第一层从左到右遍历第二层从右到左，以此类推。
思路：如果使用BFS，需要对于在换层的时候对队列进行倒序，复杂度较高。如果使用BFS，可以用根据层数，直接使用insert(vec.begin(), val)和push_back(val)插入，效率更高。
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> res;
dfs(res,0,root);
return res;
}
void dfs(vector<vector<int>>& res, int level, TreeNode* root){
if(!root){
return;
}
if(level >= res.size()){
res.push_back(vector<int>());
}
if(!root->left){
dfs(res,level+1,root->left);
}
if(!root->right){
dfs(res,level+1,root->right);
}
if(level%2==0){
res[level].push_back(root->val);
} else {
res[level].insert(res[level].begin(),root->val);
}
}
38.目标和
给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例 1:
输入: nums: [1, 1, 1, 1, 1], S: 3
输出: 5
解释:
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
一共有5种方法让最终目标和为3。
注意:
数组非空，且长度不会超过20。
初始的数组的和不会超过1000。
保证返回的最终结果能被32位整数存下。
思路：
- 剪枝
搜索空间为2^n，可以排序后进行剪枝，即：如果现在剩余的数组和都已经小于当前sum和目标S之间差的绝对值，可以进行剪枝。剪枝之前可以进行一次倒序排序，使剪枝后的效率更高。
class Solution {
int res = 0;
vector<int> sum;
public:
int findTargetSumWays(vector<int>& nums, int S) {
int len = nums.size();
if(len==0){
return S==0?1:0;
}
sort(nums.rbegin(),nums.rend());
sum=vector(len,0);
sum[len-1]=nums[len-1];
for(int i = len-2; i >=0; --i){
sum[i] = sum[i+1] + nums[i];
}
findTargetSum(nums,0,0,S);
return res;
}
void findTargetSum(vector<int>&nums, int index, int s, int target){
if(index == nums.size()&&s==target){
res+=1;
return;
}
if(index >= nums.size()||(s < target && target-s > sum[index])||(s > target && s - target > sum[index])){
return;
}
findTargetSum(nums,index+1,s-nums[index],target);
findTargetSum(nums,index+1,s+nums[index],target);
}
};
2、动态规划
可以把这个问题考虑成为：我要把nums分成两个集合，一个集合是正，一个集合是负数，有集中分发可以让两个集合相加等于S。题中限制了 数组非空，且长度不会超过20。初始的数组的和不会超过1000。 我们可以整一个num.size() * 2001的数组，设dp[i][j]为数组前i个元素和为j的方法个数
可以使用元祖法来省空间
-
前K个高频单词
没什么好讲的思路，主要熟悉一下c++的api
值得注意的一点，iterator取出元素会做一个deep copy，修改它不会影响数组中的元素值。
class Solution {
public:typedef struct sfi{
string s;
int freq = 0;//出现次数
} comp;typedef pair<string,sfi> pss;
static bool cmp(pss i, pss j){
if (i.second.freq == j.second.freq){
return i.second.s < j.second.s;
} else {
return i.second.freq > j.second.freq;
}
}
vector<string> topKFrequent(vector<string>& words, int k) {
map<string,comp> v;
for(int i = 0; i < words.size(); ++i){
auto iter = v.find(words[i]);
if(iter == v.end()){
comp c;
c.s=words[i];
c.freq = 1;
v[words[i]]=c;
} else {
comp c = iter->second;//这里是一个deep copy!
c.freq++;
v[words[i]]=c;
}
}
vector<pss> vec;
for(auto mp=v.begin(); mp != v.end(); mp++){
vec.push_back(pss(mp->first, mp->second));
}
sort(vec.begin(),vec.end(),cmp);
vector<string> res;
for(int i = 0; i < k; ++i){
res.push_back(vec[i].first);
}
return res;
}
}; -
奇偶链表
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
code：
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
ListNode* odd = head;
if(!odd){
return head;
}
ListNode* even = head->next;
ListNode* tmp = even;
while(odd->next&&even->next){
odd->next = odd->next->next;
odd = odd ->next;
even->next = even->next->next;
even = even->next;
}
odd->next=tmp;
return head;
}
};
- 把二叉搜索树转化为累加树
使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
思路：二叉树反向中序遍历
class Solution {
public:
TreeNode* bstToGst(TreeNode* root) {
int s = 0;
sum(root, s);
return root;
}
void sum(TreeNode* root, int& s){
if(!root){
return;
}
sum(root->right, s);
s += root->val;
root -> val = s;
sum(root->left, s);
}
};
- 祖父节点值为偶数的节点和
给你一棵二叉树，请你返回满足以下条件的所有节点的值之和：
该节点的祖父节点的值为偶数。（一个节点的祖父节点是指该节点的父节点的父节点。）
如果不存在祖父节点值为偶数的节点，那么返回 0 。
*/
class Solution {
public:
int sumEvenGrandparent(TreeNode* root) {
if(!root){
return 0;
}
queue<TreeNode*> q;
q.push(root);
int res = 0;
while(!q.empty()){
TreeNode* t = q.front();
q.pop();
if(t->val%2==0){
res+=sumOfGrandChildren(t);
}
if(t->left){
q.push(t->left);
}
if(t->right){
q.push(t->right);
}
}
return res;
}
int sumOfGrandChildren(TreeNode* root){
TreeNode* leftChild = root->left;
TreeNode* rightChild = root -> right;
int res = 0;
if(leftChild){
res += leftChild->left? leftChild->left->val:0;
res += leftChild->right? leftChild->right->val:0;
}
if(rightChild){
res += rightChild -> left? rightChild->left->val : 0;
res += rightChild -> right? rightChild->right->val:0;
}
return res;
}
};
- 重复的DNA序列
所有 DNA 都由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。
编写一个函数来查找目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。
示例：
输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC", "CCCCCAAAAA"]
思路：
滑动窗口+HashMap
- string 版本
class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
int len = 10;
vector<string> res;
if(s.size() < len){
return res;
}
char strs[s.size()+1];
strcpy(strs, s.c_str());
map<string,int> m;
for(int i=0; i <= s.size()-len; ++i){
char* a = strs + i;
char* b = strs + i + len;
char tmp = *b;
*b = '\0';
auto iter = m.find(a);
if(iter!=m.end()){
m[a] = iter->second+1;
} else {
m[a] = 1;
}
*b = tmp;
}
for(auto i = m.begin(); i!=m.end(); ++i){
if(i->second>1){
res.push_back(i->first);
}
}
return res;
}
};
问题：string 计算hash时间太长，string是不可变对象，会大量new新的obj
2、改进版
使用0-3来表示四种字母，即使用两位来表示一个字母。key的计算也比较简单，可以使用位运算来更新key。
class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
int len = 10;
vector<string> res;
if(s.size() < len){
return res;
}
unordered_map<int,int> m;
int key = 0;
for(int i = 0; i < len-1; ++i){
key = (key << 2) + getVal(s[i]);
}
int mask = 0xFFFFF;
for(int i=len-1; i < s.size(); ++i){
key = ((key << 2)&mask) + getVal(s[i]);
auto iter = m.find(key);
if(iter!=m.end()){
m[key] = iter->second+1;
} else {
m[key] = 1;
}
}
for(auto i = m.begin(); i!=m.end(); ++i){
if(i->second>1){
res.push_back(decode(i->first,len));
}
}
return res;
}
string decode(int val,int len){
char dir[] = {'A','C','G','T'};
char res[len+1];
res[len] = '\0';
for(int i = 0 ; i < len; ++i){
res[len-i-1] = dir[val&0x3];
val >>= 2;
}
return string(res);
}
int getVal(char a){
if(a=='A') return 0;
if(a=='C') return 1;
if(a=='G') return 2;
if(a=='T') return 3;
return 0;
}
};
值得一提的是，这里使用unordered_map会比map快一倍（88ms vs 188ms）
- 只出现一次的元素
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,3,2]
输出: 3
示例 2:
输入: [0,1,0,1,0,1,99]
输出: 99
思路：异或，永远滴神！
class Solution {
public:
int singleNumber(vector<int>& nums) {
int seen_once=0, seen_twice = 0;
//使用异或的时候，可以把一个int当成一个int集合，异或一次，就是放进这个集合，再异或一次，就取出来。
for(int num:nums){
// 如果见到过0次，seen_twice 和 seen_once 两个集合里面就不会有这个数字，可认为是0.
// 如果见到过1次，seen_twice 是 0，seen_once 是 num
// 如果见到过2次，seen_twice 是 num
seen_once = ~seen_twice & (num ^ seen_once );
// 见过0次+1 ：~0 & (num ^ seen_once) = num^seen_once = num
// 见过1次+1 ：~0 & (num ^ seen_once) = num^seen_once = 0
// 见过2次+1 ：~num & (num ^ seen_once) = ~num & (num^0)= 0
seen_twice = ~seen_once & (num ^ seen_twice);
// 见过0次+1 ：~num(这里seen_once=num，因为上面的代码执行过了) & (num ^ seen_twice) = ~num & num = 0
// 见过1次+1 ：~0 & (num ^ seen_twice) = num ^ seen_twice = num;
// 见过2次+1 ：~0 & (num ^ seen_twice) = num ^ seen_twice = 0;
}
return seen_once;//最后seen_once剩下来的就是只出现了一个的
}
};
- 缺失的数字
给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
示例 1:
输入: [3,0,1]
输出: 2
示例 2:
输入: [9,6,4,2,3,5,7,0,1]
输出: 8
说明:
你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?
方案1 ：数学
根据求和公式，可以计算出原本的总和，减去数组中的元素就是缺失的元素，但是会有溢出风险，可以边加下标边减数组中的内容
int missingNumber(vector<int>& nums) {
int sum = 0;
for (int i = 1; i <= nums.size(); i++) {
sum += i;
sum -= nums[i - 1];
}
return sum;
}
方案2:异或
使用异或的场景是，只要有办法凑对找落单的，可以往异或方向去考虑：当我们遍历一个数组的时候，可以得到[0, len-1]的这些下标，再加上len，就是[0, len-1]，数组中的元素是[0, len]中少了一个，把所有的这些异或起来，成对的变成0，落单的就留了下来。
int missingNumber(vector<int>& nums) {
int len = nums.size();
int missing = 0;
for(int i = 0; i < len; ++i){
missing ^= i ^ nums[i];
}
return missing^len;
}
- 移除掉k位数字
给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
注意:
num 的长度小于 10002 且 ≥ k。
num 不会包含任何前导零。
思路：首先我们需要考虑怎么样可以使删除后的数字最小，高位的数字优先级高，所以需要从左向右扫描。我们希望从高位开始，尽可能的非单调递减。所以就要删除高位逆序对中的第一个数字。需要考虑到删完数字为0开头和删完为0的特殊情况。自己写的太啰嗦，借鉴力扣大神的一个写法。
class Solution {
public:
string removeKdigits(string num, int k) {
if(num.size() == k) return string(1, '0');
string stk;//string可以拿来当一个栈使用，下面算法保证这个栈内的元素单调非递减
int i = 0;
while(k > 0 && i < num.size()) // 将num中的字符按规则移动到栈中
{
if(stk.empty() || stk.back() <= num[i]) // 直接入栈，并转而遍历下一个元素
{
stk.push_back(num[i]);
++i;
}
else // stk.back() > num[i]
{
stk.pop_back();
--k;
}
}
// 1. 如果i == 0, 则 k 可能不等于0, 移除掉stk末尾k个元素.
// 2. 如果k == 0, 则 i 可能不等于0, 需要加上num中i之后的元素.
stk = stk.substr(0, stk.size() - k) + num.substr(i);
// 移除开头的0,在全0的情况下保证至少剩下一个0.
size_t beginIndex = 0;
while(beginIndex < stk.size() - 1 && stk[beginIndex] == '0') ++beginIndex;
return stk.substr(beginIndex);
}
};
- 快速幂
class Solution {
public:
double myPow(double x, int n) {
int neg = n < 0;
n=abs(n);
double res = 1;
double cur = x;
while(n > 0){
int m = n%2;
n/=2;
if(m){
res *=cur;
}
cur *=cur;
}
return neg? 1/res:res;
}
};
变体：超级次方
你的任务是计算 ab 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。
示例 1:
输入: a = 2, b = [3]
输出: 8
示例 2:
输入: a = 2, b = [1,0]
输出: 1024
思路：开始还头疼想着想着怎么把大数数组转成2进制，后来看了一个题解，可以十进制直接快速幂后对于10进制的那个个位数再进行一次二进制快速幂。
class Solution {
//(a*b)%c = (a%c)*(b%c);
public:
int superPow(int a, vector<int>& b) {
a= a%1337;
int res = 1;
int cur = a;
for(int i = 0; i < b.size(); ++i){
if(b[b.size()-1-i]>0){
res = (res *fastPow(cur,b[b.size()-1-i]))%1337;
}
cur = fastPow(cur,10);//dp中如果dp[i]可以只由固定个dp[i-x]递推出来，可以不用开数组，固定几个变量就好。
}
return res;
}
int fastPow(int a, int n){
int res = 1;
int cur = a%1337;
while(n>0){
if(n%2==1){
res*=cur;
}
cur=(cur*cur)%1337;
n/=2;
}
return res%1337;
}
};
示例:
A = [1, 2, 3, 4]
返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。
思路：统计所有的等差数组长度lens(>=3)，每个等差序列有(len-2)*(len-1)/2个len>3的子序列
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
if(A.size() < 3){
return 0;
}
int res = 0;
//思路：先找数组中等差数组的长度，再
int len = 2;//等差数组长度（要大于三）
int oldDiff = A[1]-A[0];
int cur = 2;
// vector<int> lens; //记录数组中非重叠等差数组们的长度 改-无需记录，循环的时候算就可以了
while(cur < A.size()){
int curDiff = A[cur]-A[cur-1];
if(curDiff != oldDiff ){
oldDiff = curDiff;
if(len > 2){
// lens.push_back(len);
res += (len-1)*(len-2)/2;
}
len = 2;
} else {
len++;
}
cur++;
}
if(len > 2){
res += (len-1)*(len-2)/2;
// lens.push_back(len);
}
// int res = 0;
// for(int num : lens){
// res += (num-1)*(num-2)/2;//
// }
return res;
}
};
思路2:动态规划，
- 查找和最小的k个数对
可以使用优先级队列/小顶堆来实现
Priority queues are a type of container adaptors, specifically designed such that** its first element is always the greatest of the elements it contains**, according to some strict weak ordering criterion.
// Priority queue
class Solution {
public:
struct cmp{
bool operator ()(pair<int,int> a, pair<int,int> b){
return a.first + a.second > b.first + b.second;
}
};
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
vector<vector<int>> res;
priority_queue<pair<int,int>, vector<pair<int,int> >,cmp> q;//priority_queue<Type, Container, Compare>
for(int i = 0; i < nums1.size(); ++i){
for(int j = 0; j < nums2.size(); ++j){
q.push(pair<int,int>(nums1[i],nums2[j]));
}
}
for(int i = 0; i < k && !q.empty();++i){
pair<int,int> p =q.top();
q.pop();
res.push_back({p.first,p.second});
}
return res;
}
};
- 旋转函数
给定一个长度为 n 的整数数组 A 。
假设 Bk 是数组 A 顺时针旋转 k 个位置后的数组，我们定义 A 的“旋转函数” F 为：
F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1]。
计算F(0), F(1), ..., F(n-1)中的最大值。
注意:
可以认为 n 的值小于 105。
示例:
A = [4, 3, 2, 6]
F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26
所以 F(0), F(1), F(2), F(3) 中的最大值是 F(3) = 26 。
思路：
F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (1 * 4) + (2 * 3) + (3 * 2) + (0 * 6) = 0 + 4 + 6 + 6 = 16
F(2) = (2 * 4) + (3 * 3) + (0 * 2) + (1 * 6) = 0 + 6 + 8 + 9 = 23
F(3) = (3 * 4) + (0 * 3) + (1 * 2) + (2 * 6) = 0 + 2 + 12 + 12 = 26
规律如下，如果数组nums的长度为len，总和为sum，F(i) = F(i-1) + sum - nums[len-1-i];
注意，在加和的过程中可能溢出
class Solution {
public:
int maxRotateFunction(vector<int>& A) {
long res=0;
int len=A.size();
long sum=0;
for(int i = 0; i < len; ++i){
res += A[i]*i;
sum += A[i];
}
long old = res;//注意会溢出
for(int i = 0; i<len-1; ++i){
old = old + sum - A[len-1-i]*(long)len;
res = max(res,old);
}
return (int)res;
}
};
