算法集锦
背包问题
描述
在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A[i]
动态规划之背包问题系列
dp[i][j]
前i件物品在承重j内，最多能装多少重量
dp[i][j] = max(dp[i-1][j], dp[i-1][j-A[i]] + A[i])
public int backPack(int m, int[] A) {
// write your code here
int size = sizeof(A);
vector<int>dp(m+1, 0);
for(int i = 1; i <=m;i++) {
for(int j = 0; j < i;j++) {
if(i-A[j]>= 0) {
dp[i] = max(dp[i - A[j]]+1, dp[i]);
}
}
}
return dp[m];
}
动态规划-完全背包问题
动态规划-完全背包问题
前i件物品在承重j内，最多能装多少重量
dp[i][j] = max(dp[i-1][j], dp[i][j-A[i]] + V[i])
第二个max是dp[i][j-A[i]]不是dp[i-1][j-A[i]]，是因为物体无数个
image.png
木材加工
https://www.lintcode.com/problem/wood-cut
给定长度为n的数组，每个元素代表一个木头的长度，木头可以任意截断，从这堆木头中截出至少k个相同长度为m的木块。已知k，求max(m)。
使用二分查找，对木头最大长度做二分，mid做为截断长度，遍历每个木头来计算一个临时k，临时k比k小，证明截断长度需要更小，r=mid-1,否者l = mid + 1
剑指 Offer 07. 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
利用前序遍历的数组第一个是跟节点，在用这个根节点在中序遍历的数组找到左子树和右子树的序列，然后递归重建
/**
* 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:
unordered_map<int, int>rootMap;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
for(int i = 0;i < inorder.size();i++) {
rootMap[inorder[i]] = i;
}
TreeNode *root = build(preorder, inorder, 0, preorder.size()-1, 0, preorder.size()-1);
return root;
}
TreeNode *build(vector<int>& preorder, vector<int>& inorder, int preorderL,int preorderR, int inorderL, int inorderR) {
if(preorderL>preorderR) {
return NULL;
}
int rootValue = preorder[preorderL];
TreeNode *root = new TreeNode(rootValue);
int mid = rootMap[rootValue];
int midToLeftLength = mid - inorderL;
TreeNode *left = build(preorder, inorder, preorderL+1,preorderL+ midToLeftLength,inorderL, mid - 1);
TreeNode *right = build(preorder, inorder, preorderL+1+ midToLeftLength,preorderR,mid + 1, inorderR);
root->left = left;
root->right = right;
return root;
}
};
剑指 Offer 11. 旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
二分查找，难点在numbers[mid] > numbers[high]时为什么时mid+1，因为此时可以确定numbers[mid]不是最小
class Solution {
public:
int minArray(vector<int>& numbers) {
int low = 0;
int high = numbers.size()-1;
while(low < high) {
int mid = (low + high) / 2;
if(numbers[mid] > numbers[high]) {
low = mid + 1;
} else if (numbers[mid] < numbers[high]) {
high = mid;
} else {
high -=1;
}
}
return numbers[low];
}
};
剑指 Offer 12. 矩阵中的路径
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。
[["a","b","c","e"],
["s","f","c","s"],
["a","d","e","e"]]
但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。
暴力回溯，每个节点都往四个方向走，完全匹配最后返回true，递归层层传递 用 ‘ ’标记走过的节点来标记走过的节点，递归结束后再恢复
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
for(int i = 0; i < board.size();i++) {
vector<char>row = board[i];
for(int j = 0; j < row.size();j++) {
if(dfs(board, word, i,j,0)) {
return true;
}
}
}
return false;
}
bool dfs(vector<vector<char>>& board, string word, int i, int j, int k) {
if(i >= board.size() || j >= board[0].size() || board[i][j] != word[k]) {
return false;
}
if (k == word.size()-1){
return true;
}
board[i][j] = ' ';
bool vaild = dfs(board, word, i,j+1,k+1) || dfs(board, word, i,j-1,k+1) || dfs(board, word, i-1,j,k+1) || dfs(board, word, i+1,j,k+1) ;
board[i][j] = word[k];
return vaild;
}
};
剑指 Offer 13. 机器人的运动范围
地上有一个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。请问该机器人能够到达多少个格子？
1.dfs 2.机器人只能往右走 3.visited📝走过没有
class Solution {
public:
int movingCount(int m, int n, int k) {
vector<vector<bool>> visited(m, vector<bool>(n, 0));
return dfs(m,n,0,0,k,visited);
}
int sum(int n) {
int sum = 0;
while(n) {
sum+= n %10;
n /= 10;
}
return sum;
}
int dfs(int m, int n,int i, int j, int k, vector<vector<bool>> &visited) {
if(i >=m || j >= n || (sum(i) + sum(j)) > k || visited[i][j]) {
return 0;
}
visited[i][j] = true;
return 1 + dfs(m,n,i+1, j, k, visited) + dfs(m,n,i,j+1,k,visited);
}
};
剑指 Offer 14- I. 剪绳子
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]k[1]...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
(i-j) * j是对应3,5的情况 ,5的时候切两段更好，同时，这个问题可以转化为完全背包问题，转为物品1，2，3...n在最大载重n下，乘积最多是多少
https://leetcode-cn.com/problems/jian-sheng-zi-lcof/solution/xu-lie-xing-dong-tai-gui-hua-by-muyids-2/
class Solution {
public:
int cuttingRope(int n) {
vector<int>dp(n+1, 0);
dp[0]= 0;
dp[1] = 1;
for(int i = 2; i <=n;i++) {
for(int j = 1; j < i;j++) {
dp[i] = max(dp[i], max(dp[i-j] *j, (i-j) * j));
}
}
return dp[n];
}
};
剑指 Offer 16. 数值的整数次方
实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。
快速幂，其实是个数学问题，如x的10次方可以写出 x的(1010)b次方
class Solution {
public:
double myPow(double x, int n) {
if(n == 0) {
return 1;
}
if(x == 0) {
return 0;
}
long b = n;
double res = 1;
if(n < 0) {
b = -b;
x = 1 / x;
}
while(b > 0) {
if (b & 1) {
res *= x;
}
x = x*x;
b = b >> 1;
}
return res;
}
};
剑指 Offer 19. 正则表达式匹配
请实现一个函数用来匹配包含'. '和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但与"aa.a"和"ab*a"均不匹配。
这题状态方程
p[j] == *
dp[i][j] = dp[i][j-2],抛弃和p[j-1]
dp[i][j] != dp[i][j] | dp[i-1][j] ,baaaa和ba匹配这种情况，
2.p[j] != * ,dp[i][j] = s[i] == p[j] || p[j] == .
然后把dp数组输出化为多一个长度，便于处理空字符串情况，例如， ""和""匹配， ""和a*匹配，都应该为true
class Solution {
public:
bool isMatch(string s, string p) {
int sLength = s.size();
int pLength = p.size();
vector<vector<bool>> dp(sLength+1, vector<bool>(pLength+1, false));
dp[0][0] = true;
for(int i = 0; i <= sLength ; i++) {
for(int j = 1; j <= pLength; j++ ) {
if (p[j-1] == '*') {
if(j>=2) {
dp[i][j] = dp[i][j-2];
}
if(i>=1 && j>=2 && (s[i-1] == p[j-2] || p[j-2] == '.')) {
dp[i][j] = dp[i-1][j] | dp[i][j];
}
} else {
if(i>0&&(s[i-1] == p[j-1] || p[j-1] == '.')) {
if(i >= 1 && j >=1) {
dp[i][j] = dp[i-1][j-1];
}
} else {
dp[i][j] = false;
}
}
}
}
return dp[sLength][pLength];
}
};
剑指 Offer 31. 栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
先遍历押入顺序，放进辅助栈，遍历过程再循环辅助栈的栈顶与当前弹出位置是否一致，一致的话弹出到不一致为止
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
stack<int>tempStack;
int popIndex = 0;
for(int i = 0; i < pushed.size();i++) {
int temp = pushed[i];
tempStack.push(temp);
while(!tempStack.empty() && tempStack.top() == popped[popIndex]) {
tempStack.pop();
popIndex++;
}
}
return tempStack.empty();
}
};
剑指 Offer 36. 二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
先思考中序遍历打印的调用顺序，然后用全局变量来存储上一个打印的节点，根据这思路去连接当前节点和上一个节点
class Solution {
public:
Node *pre;
Node *head;
Node* treeToDoublyList(Node* root) {
if(!root) {
return root;
}
dfs(root);
pre->right = head;
head->left = pre;
return head;
}
void dfs(Node *cur) {
if(!cur) {
return;
}
dfs(cur->left);
if(pre != NULL) {
pre->right = cur;
} else {
head = cur;
}
cur->left = pre;
pre = cur;
dfs(cur->right);
}
};
剑指 Offer 38. 字符串的排列
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例:
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
1.固定第一个字符，然后遍历dfs 2.重复字符用set来区分，然后跳过 3.递归前后注意恢复字符串
class Solution {
public:
vector<string>result;
vector<string> permutation(string s) {
if(s.size() == 0) {
return result;
}
recur(s, 0);
return result;
}
void recur(string s, int head) {
if(head == s.size()-1) {
result.push_back(s);
return;
}
unordered_set<int>set;
for(int i = head;i < s.size();i++) {
if(set.find(s[i]) != set.end()) {
continue;
}
set.insert(s[i]);
swap(s[i],s[head]);
recur(s, head+1);
swap(s[head],s[i]);
}
}
};
剑指 Offer 40. 最小的k个数
注意，递归结束调节不能是l>=r,是l>r,不同于快排，等于的时候也要让她走下去，因为当递归剩下到一个数时，也是要进结果的
class Solution {
public:
vector<int>result;
vector<int> getLeastNumbers(vector<int>& arr, int k) {
quickSort(arr,k, 0, arr.size()-1);
return result;
}
void quickSort(vector<int>& arr, int k, int l, int r) {
if(l > r) {
return;
}
int pov = arr[l];
int i = l;
int j = r;
while(i < j) {
while(arr[j] >= pov && i < j) {
j--;
}
while(arr[i] <= pov && i < j) {
i++;
}
swap(arr[i], arr[j]);
}
swap(arr[l], arr[i]);
int length = i - l + 1;
if(length == k) {
for(int a = l; a <= i;a++) {
result.push_back(arr[a]);
}
} else if(k < length) {
quickSort(arr, k, l, i-1);
} else {
for(int a = l; a <= i;a++) {
result.push_back(arr[a]);
}
quickSort(arr, k - length, i + 1, r);
}
}
};
剑指 Offer 41. 数据流中的中位数
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
用最大堆和最小堆，最大堆顶为最大值，最小堆堆顶为最小值
C++里最大堆： priority_queue<int, vector<int>, less<int>> maxHeap;
C++里最小堆： priority_queue<int, vector<int>, greater<int>> minHeap;
class MedianFinder {
public:
/** initialize your data structure here. */
// 最大堆，存储左边一半的数据，堆顶为最大值
priority_queue<int, vector<int>, less<int>> maxHeap;
// 最小堆， 存储右边一半的数据，堆顶为最小值
priority_queue<int, vector<int>, greater<int>> minHeap;
MedianFinder() {
}
void addNum(int num) {
if(maxHeap.size() == minHeap.size()) {
minHeap.push(num);
maxHeap.push(minHeap.top());
minHeap.pop();
} else {
maxHeap.push(num);
minHeap.push(maxHeap.top());
maxHeap.pop();
}
}
double findMedian() {
return maxHeap.size() == minHeap.size() ? (minHeap.top()+maxHeap.top()) / 2.0 : maxHeap.top();
}
};
剑指 Offer 43. 1～n 整数中 1 出现的次数
输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
1. 固定一个位置，当这个位置为0，1或者其他这三种情况，这个位置能为1的次数 ，类似于滚动密码锁，注意，当当前位置为0时，高位变小，此位置就能为1了！，比如 2302，固定十位为0时，2212，十位还是有一，注意这点
class Solution {
public:
int countDigitOne(int n) {
int digit = 1;
int hight = n / 10;
int cur = n % 10;
int low = 0;
int res = 0;
while(hight != 0 || cur != 0) {
if(cur == 0) {
res += hight * digit;
} else if (cur == 1) {
res += hight * digit + low + 1;
} else {
res += hight *digit + digit;
}
low = cur * digit + low;
cur = hight % 10;
digit *= 10;
hight = hight / 10;
}
return res;
}
};
剑指 Offer 45. 把数组排成最小的数
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
输入: [10,2]
输出: "102"
这题实际上是个排序题x + y > y + x, x > y
class Solution {
public:
string minNumber(vector<int>& nums) {
vector<string>numStrings;
for(auto num : nums) {
numStrings.push_back(to_string(num));
}
quickSort(numStrings, 0, numStrings.size() - 1);
string res;
for(string s : numStrings)
res.append(s);
return res;
}
void quickSort(vector<string>& nums, int l, int r) {
if(l >= r) return;
int i = l;
int j = r;
string p = nums[l];
while(i < j) {
while(nums[j] + p >= p + nums[j] && i < j) j--;
while(nums[i] + p <= p + nums[i] && i < j) i++;
swap(nums[i],nums[j]);
}
swap(nums[i],nums[l]);
quickSort(nums, l, i-1);
quickSort(nums, i+1, r);
}
};
剑指 Offer 47. 礼物的最大价值
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
不能用dfs！会超时，用dp就好了dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + a[i][j]
class Solution {
public:
int maxVale = 0;
int maxValue(vector<vector<int>>& grid) {
if(grid.size() == 0) {
return 0;
}
int row = grid.size();
int colum = grid[0].size();
vector<vector<int>>dp(row, vector<int>(colum, 0));
dp[0][0] = grid[0][0];
for(int i = 0; i < row;i++) {
for(int j = 0; j < colum;j++ ) {
if(i == 0) {
if(j >= 1) {
dp[i][j] = dp[i][j-1] + grid[i][j];
}
} else if (j == 0) {
if(i >= 1) {
dp[i][j] = dp[i-1][j] + grid[i][j];
}
} else {
dp[i][j] = max(dp[i-1][j] , dp[i][j-1]) + grid[i][j];
}
}
}
return dp[row-1][colum-1];
}
};
剑指 Offer 48. 最长不含重复字符的子字符串
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
也是用dp dp[j] = i - j, i-j<=dp[j-1],i为j左边第一个相同的字母 dp[j] = dp[j-1] + 1, i-j>dp[j-1]
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.size() == 0) {
return 0;
}
vector<int>dp(s.size(), 0);
dp[0] = 1;
for(int j = 1;j < s.size();j++) {
int i = j - 1;
bool same = false;
for(; i >= 0;i--) {
if(s[i] == s[j]) {
same = true;
break;
}
}
if(j - i <= dp[j-1]) {
dp[j] = j - i;
} else {
dp[j] = dp[j-1] + 1;
}
}
int maxL = 0;
for(auto num : dp) {
maxL = max(num, maxL);
}
return maxL;
}
};
剑指 Offer 49. 丑数
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
一个丑数肯定是由前面任意个数乘 2，3，5得出来的
class Solution {
public:
int nthUglyNumber(int n) {
if(n == 0) {
return 0;
}
int a = 0;
int b = 0;
int c = 0;
vector<int>dp(n, 0);
dp[0] = 1;
for(int i = 1; i <n;i++) {
dp[i] = min(dp[a] * 2, min(dp[b] * 3, dp[c] * 5));
if(dp[i] == dp[a] * 2) a++;
if(dp[i] == dp[b] * 3) b++;
if(dp[i] == dp[c] * 5) c++;
}
return dp[n-1];
}
};
剑指 Offer 51. 数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
分治，归并排序，先找子序列的逆序对数，再递归回来找父序列的逆序对，这样找是对的。
class Solution {
public:
int sum;
int reversePairs(vector<int>& nums) {
vector<int>temp(nums.size(),0);
mergeSort(nums,0, nums.size()-1,temp);
return sum;
}
void mergeSort(vector<int>& nums, int l, int r, vector<int>&temp) {
if(l>=r) {
return;
}
int mid = (l + r) / 2;
mergeSort(nums, l, mid, temp);
mergeSort(nums, mid+1, r, temp);
vector<int>seq;
int i = l;
int j = mid+1;
for(int k=l;k<=r;k++){
temp[k] = nums[k];
}
for(int k=l;k<=r;k++) {
if(i == mid+1) {
nums[k] = temp[j];
j++;
} else if (j == r+1) {
nums[k] = temp[i];
i++;
} else if(temp[i] <= temp[j]) {
nums[k] = temp[i];
i++;
} else {
sum += mid-i+1;
nums[k] = temp[j];
j++;
}
}
}
};
剑指 Offer 52. 两个链表的第一个公共节点
a链a节点走完再走 b链，b链b节点走完再走a链，相等时即相遇
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *a = headA;
ListNode *b = headB;
while(a != b) {
a = a == NULL ? headB : a->next;
b = b == NULL ? headA : b->next;
}
return a;
}
};
剑指 Offer 54. 二叉搜索树的第k大节点
给定一棵二叉搜索树，请找出其中第k大的节点。
示例 1:
输入: root = [3,1,4,null,2], k = 1
3
/
1 4
2
输出: 4
中序遍历改良，先遍历右边就是从大到小
class Solution {
public:
int idx = 0;
int v = 0;
int kthLargest(TreeNode* root, int k) {
travel(root, k);
return v;
}
void travel(TreeNode* root, int k) {
if(root == NULL) {
return;
}
travel(root->right,k);
idx++;
if(idx == k) {
v = root->val;
return;
}
travel(root->left,k);
}
};
剑指 Offer 55 - II. 平衡二叉树
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
后续遍历，得到左右两个子节点的高度，比较，大于2返回-1，注意，子节点dfs后如果得到-1，需要特别判断然后返回-1
class Solution {
public:
bool isBalanced(TreeNode* root) {
return dfs(root) != -1;
}
int dfs(TreeNode* root) {
if(!root){
return 0;
}
int left = dfs(root->left);
if(left == -1) return -1;
int right = dfs(root->right);
if(right==-1) return -1;
return (abs(left - right) >= 2 ? -1: ((max(left, right)) + 1));
}
};
剑指 Offer 56 - I. 数组中数字出现的次数
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
1.两个相同的数抑或等于 0
2. 0和1抑或等于1，用这个性质来分组
下面可以更简单
https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/solution/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-by-leetcode/
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
int ret = 0;
for(auto num: nums) {
ret ^= num;
}
int n = 0;
while(ret > 0) {
if(ret & 1) {
break;
}
ret = ret >> 1;
n++;
}
vector<int>first;
vector<int>second;
for(auto num: nums) {
if((num >> n) & 1) {
first.push_back(num);
} else {
second.push_back(num);
}
}
int firstRet = 0;
int secondRet = 0;
for(auto num: first) {
firstRet ^= num;
}
for(auto num: second) {
secondRet ^= num;
}
vector<int>r;
r.push_back(firstRet);
r.push_back(secondRet);
return r;
}
};
剑指 Offer 56 - II. 数组中数字出现的次数 II
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
1. 出现三次的数，他们二进制某一位为1时，加起来这些1肯定是3的倍数，如不不是，就是那个出现一次的数造成的
class Solution {
public:
int singleNumber(vector<int>& nums) {
vector<long>bitSums(32, 0);
for(long i = 0;i < nums.size();i++) {
long num = nums[i];
long mask = 1;
long bit = 0;
while(bit < 32) {
if(mask & num) {
bitSums[bit] += 1;
}
mask = mask << 1;
bit ++;
}
}
long res = 0;
long mask = 1;
for(long i = 0 ;i < bitSums.size();i++) {
long sum = bitSums[i];
if(sum %3 != 0) {
res |= mask;
}
mask = mask << 1;
}
return res;
}
};
剑指 Offer 57. 和为s的两个数字
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
头尾双指针，头尾之和与目标s比较，小于s，头前进，大于s，尾前进
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int l = 0;
int r = nums.size() - 1;
while(l<r) {
int sum = nums[l] + nums[r];
if(sum > target) {
r--;
} else if(sum < target) {
l++;
} else {
return vector<int>{nums[l], nums[r]};
}
}
return vector<int>();
}
};
剑指 Offer 57 - II. 和为s的连续正数序列
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
滑动窗口，当sum大于target，left++, sum小于target，right++,等于的时候left++,整个窗口往右边移动
class Solution {
public:
vector<vector<int>> findContinuousSequence(int target) {
int l = 1;
int r = 1;
int sum = 0;
vector<vector<int>>result;
while(l <= target / 2) {
if(sum < target) {
sum+=r;
r++;
} else if(sum > target) {
sum-=l;
l++;
} else {
vector<int>temp;
for(int i = l;i < r;i++) {
temp.push_back(i);
}
result.push_back(temp);
sum-=l;
l++;
}
}
return result;
}
};
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。
中间多余空格消除是难点，判断前后都为空格时，删除当前位置的空格
class Solution {
public:
string reverseWords(string s) {
trim(s);
int i = s.length() - 1;
int j = s.length() - 1;
string result;
reverse(s,0, s.length() - 1);
while(i >= 0) {
while(i>=0&&s[i] != ' ') {
char a = s[i];
i--;
}
reverse(s, i+1,j);
while(i>=0&&s[i]==' ') {
i--;
//消除中间多余空格
if(s[i+1] == ' ' && s[i] == ' ') {
s.erase(i, 1);
}
}
j = i;
}
return s;
}
void reverse(string &s, int l, int r) {
if(l < 0) {
return;
}
if(s.size() == 0 || l >= r) {
return;
}
int i = l;
int j = r;
while(i < j) {
swap(s[i], s[j]);
i++;
j--;
}
}
void trim(string &s) {
while(s.length() > 0 && s[0] == ' ') {
s.erase(0, 1);
}
while(s.length() > 0 && s[s.size()-1] == ' ') {
s.erase(s.size()-1, 1);
}
}
};
剑指 Offer 59 - I. 滑动窗口的最大值
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
滑动窗口，用双端队列，当窗口右移，1.判断队列头部与i-1位置的大小，相等这干掉队列头部的最大值 2.n[j]与队列所有比较，小于（不能等于）它的将被干掉 3.最后把n[j]加到末尾
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int i = 1-k;
int j = 0;
deque<int>q;
vector<int>res;
for (;i <=0;) {
int num = nums[j];
while(!q.empty() && num >= q.back()) {
q.pop_back();
}
q.push_back(num);
i++;
j++;
}
if(!q.empty()) {
res.push_back(q.front());
}
while(j < nums.size()) {
int num = nums[j];
if(nums[i-1] == q.front()) {
q.pop_front();
}
while(!q.empty() && num > q.back()) {
q.pop_back();
}
q.push_back(num);
res.push_back(q.front());
i++;
j++;
}
return res;
}
};
剑指 Offer 59 - II. 队列的最大值
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
难点是用双端队列去存最大值
class MaxQueue {
public:
queue<int>q;
deque<int>q2;
MaxQueue() {
}
int max_value() {
if(!q2.empty()) {
return q2.front();
}
return -1;
}
void push_back(int value) {
q.push(value);
while(!q2.empty() && q2.back()<value) {
q2.pop_back();
}
q2.push_back(value);
}
int pop_front() {
if(q2.empty()) {
return -1;
}
int v = q.front();
q.pop();
while(!q2.empty() && q2.front() == v) {
q2.pop_front();
}
return v;
}
};
/**
* Your MaxQueue object will be instantiated and called as such:
* MaxQueue* obj = new MaxQueue();
* int param_1 = obj->max_value();
* obj->push_back(value);
* int param_3 = obj->pop_front();
*/
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
其实就是二分搜索，比pq小就递归left，比pq大就递归right
/**
* 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 == NULL) {
return NULL;
}
if(p->val < root->val && q->val < root->val) {
return lowestCommonAncestor(root->left, p, q);
} else if (p->val > root->val && q->val > root->val) {
return lowestCommonAncestor(root->right, p, q);
}
return root;
}
};
第k大
注意是第k大，不是第k小
class Solution {
public:
int findKth(vector<int> a, int n, int K) {
quicksort(a, K, 0, n-1);
return kValue;
}
int kValue = 0;
int partition(vector<int> &a, int l, int r) {
int randIndex = rand() % (r - l + 1) + l;
swap(a[randIndex], a[l]);
int qvot = a[l];
int i = l;
int j = r;
while(i < j) {
while(a[j] >= qvot && i < j) j--;
while(a[i] <= qvot && i < j) i++;
swap(a[i], a[j]);
}
swap(a[i], a[l]);
return i;
}
void quicksort(vector<int> &a, int K, int l, int r) {
if(l > r) {
return;
}
int i = partition(a, l, r);
int kIndex = r - K + 1;
if(kIndex == i) {
kValue = a[i];
} else if (kIndex < i) {
quicksort(a, i - kIndex, l, i-1);
} else {
quicksort(a,K, i+1, r);
}
}
};
43. 字符串相乘
让乘数短一点，可以减少相乘的次数，降低时间复杂度
result[i+j] = t[i] * t[j];
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param s string字符串 第一个整数
* @param t string字符串 第二个整数
* @return string字符串
*/
string solve(string s, string t) {
// write code here
if(t.size() > s.size()){
swap(s,t);
}
int sLength = s.size();
int tLength = t.size();
int resultLength = sLength + tLength;
vector<int> result(resultLength, 0);
for(int i = tLength-1; i >= 0;i--) {
int temp = t[i] - '0';
for(int j = 0; j < s.size();j++) {
result[i+j+1] += temp * (s[j] - '0');
}
}
int d = 0;
for(int i = resultLength - 1; i >= 0;i--) {
int value = result[i] + d;
d = value / 10;
result[i] = value % 10;
}
string strResult = "";
int index = result[0] == 0 ? 1 : 0;
while(index < resultLength) {
strResult += (result[index] + '0');
index++;
}
return strResult;
}
};
面试题 16.25. LRU 缓存
双链表，加哈希表，被操作就把节点挪到前面，超出缓存数目就删除尾部的节点
struct DLinkNode {
int key;
int value;
DLinkNode *next;
DLinkNode *pre;
};
class LRUCache {
public:
unordered_map<int, DLinkNode*>cache;
DLinkNode *head = nullptr;
DLinkNode *tail = nullptr;
int capacity_ = 0;
int size = 0;
LRUCache(int capacity) {
capacity_ = capacity;
head = (DLinkNode *)malloc(sizeof(DLinkNode));
tail = (DLinkNode *)malloc(sizeof(DLinkNode));
tail->next = head;
head->pre = tail;
}
int get(int key) {
DLinkNode *node = cache[key];
if(node == nullptr) {
return -1;
}
moveToHead(node);
return node->value;
}
void put(int key, int value) {
DLinkNode *node = cache[key];
if(node) {
node->value = value;
moveToHead(node);
} else {
if(size == capacity_) {
DLinkNode *node = removeTail();
cache.erase(node->key);
free(node);
size--;
}
size++;
DLinkNode *node = pushHead(key, value);
cache[key] = node;
}
}
DLinkNode* removeTail() {
DLinkNode *node = tail->next;
removeNode(node);Z
return node;
}
DLinkNode* pushHead(int key, int value) {
DLinkNode *node = (DLinkNode *)malloc(sizeof(DLinkNode));
node->key = key;
node->value = value;
addToHead(node);
return node;
}
void removeNode(DLinkNode *node){
node->pre->next = node->next;
node->next->pre = node->pre;
}
void addToHead(DLinkNode *node) {
node->pre = head->pre;
head->pre->next = node;
head->pre = node;
node->next = head;
}
void moveToHead(DLinkNode *node) {
removeNode(node);
addToHead(node);
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
最长公共子串
dp[i][j] = dp[i-1][j-1] + 1 s1[i] ==s2[j]
dp[i][j] = 0 s1[i] !=s2[j]
class Solution {
public:
/**
* longest common substring
* @param str1 string字符串 the string
* @param str2 string字符串 the string
* @return string字符串
*/
string LCS(string str1, string str2) {
// write code here
int m = str1.length();
int n = str2.length();
int dp[m+1][n+1];
for(int i = 0; i < m;i++) {
dp[i][0] = 0;
}
for(int i = 0; i < n;i++) {
dp[0][i] = 0;
}
int max = 0;
int end = 0;
for(int i = 1; i <= m;i++) {
for(int j = 1;j <= n;j++) {
if(str1[i-1] == str2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = 0;
}
if(dp[i][j] > max) {
end = i-1;
max = dp[i][j];
}
}
}
if(max == 0) return "-1";
return str1.substr(end - max + 1, max);
}
};
