对于非负整数 X 而言，X 的数组形式是每位数字按从左到右的顺序形成的数组。例如，如果 X = 1231，那么其数组形式为 [1,2,3,1]。
| 示例： |
|---|
| 输入：A = [1,2,0,0], K = 34 |
| 输出：[1,2,3,4] |
| 解释：1200 + 34 = 1234 |
class Solution {
public:
vector<int> addToArrayForm(vector<int>& A, int K) {
vector<int> list;
for(int i = A.size()-1; i >= 0; i--){
int r = A[i] + K;
list.push_back(r % 10);
K = r / 10;
}
for(;K;K /= 10) list.push_back(K%10);
reverse(list.begin(),list.end());
return list;
}
};
K先与个位相加，与10取余后得到结果的个位数；
K整除10，舍弃个位，进行十位计算；
循环i次（即使过程中K为0，也不影响计算）
最后再附上K的单循环，防止K过大，为计算完。
实现获取下一个队列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列。（即升序排列）
| 示例： |
|---|
| 输入：arr1 = [1,2,3] |
| 输出：[1,3,2] |
C
void swap(int *a, int *b) { //互换函数（指针思想）
int t = *a;
*a = *b, *b = t;
}
void reverse(int *nums, int left, int right) { //区间倒序
while (left < right) {
swap(nums + left, nums + right);
left++, right--;
}
}
void nextPermutation(int *nums, int numsSize) {
int i = numsSize - 2; //指代倒数第二个数据
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--; //找到“较小数”
}
if (i >= 0) { //小于0则表示整个序列已经都是倒序状态
int j = numsSize - 1; //指代最后一个数据
while (j >= 0 && nums[i] >= nums[j]) {
j--; //找到“较大数”
}
swap(nums + i, nums + j); //先将“较小数”和“较大数”交换
}
reverse(nums, i + 1, numsSize - 1); //将“i+1”到最后一个数之间的区间进行倒序
}
C++
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int i = nums.size() - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i >= 0) {
int j = nums.size() - 1;
while (j >= 0 && nums[i] >= nums[j]) {
j--;
}
swap(nums[i], nums[j]);
}
reverse(nums.begin() + i + 1, nums.end());
}
};
给定两个数组，arr1和arr2
对arr1中的元素进行排序，使arr1中项的相对顺序和arr2中的相对顺序相同。未在arr2中出现过的元素需要按照升序放在arr1的末端。
| 示例： |
|---|
| 输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6] |
| 输出：[2,2,2,1,4,3,3,9,6,7,19] |
int* relativeSortArray(int* arr1, int arr1Size, int* arr2, int arr2Size, int* returnSize){
int nums[1001] = {0};
int *res = (int*)malloc(sizeof(int) * arr1Size);
int i;
int j = 0;
/* 统计数字出现的次数 */
for (i = 0; i < arr1Size; i++) {
nums[arr1[i]]++;
}
/* 先取出arr2中出现的数字 */
for (i = 0; i < arr2Size; i++) {
while (nums[arr2[i]] > 0) {
res[j++] = arr2[i];
nums[arr2[i]]--;
}
}
/* 将剩余数字升序排列 */
for (i = 0; i < 1001; i++) {
while (nums[i] != 0) {
res[j++] = i;
nums[i]--;
}
}
*returnSize = j;
return res;
}
C++
vector<int> SortArray(vector<int> arr1, vector<int> arr2) {
unordered_map<int,int> hashtable;
vector<int> res;
int j = 0;
for (int i = 0; i < arr1.size(); i++){
hashtable[arr1[i]]++;
}
for (int i = 0; i < arr2.size(); i++) {
while (hashtable[arr2[i]] > 0) {
res.push_back(arr2[i]); //这里必须用push_back
hashtable[arr2[i]]--;
}
}
for (int i = 0; i < 1001; i++) {
while (hashtable[i] != 0) {
res.push_back(i);
hashtable[i]--;
}
}
return res;
}
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
| 示例： |
|---|
| 输入：l1 = [1,2,4], l2 = [1,3,4] |
| 输出：[1,1,2,3,4,4] |
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == nullptr) {
return l2;
} else if (l2 == nullptr) {
return l1;
} else if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
};
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。（不是单纯改变链表内部的值，而是需要实际的进行节点交换。）
| 示例： |
|---|
| 输入：head = [1,2,3,4] |
| 输出：[2,1,4,3] |
struct ListNode* swapPairs(struct ListNode* head){
struct ListNode *p,*p1,*p2;
int n = 0;
p = head;
//确保链表不是全空
while (p != NULL){
//链表只有奇数元素时break
if(p->next == NULL)
break;
//元素二赋值给p1
p1 = p->next;
//如果是前两个元素，则p1为链表头
if(n == 0){
head = p1;
n = 1;
}
//否则p1为第三个元素
else
p2->next = p1;
//p p1 p2链表交换
p->next = p1->next;
p1->next = p;
p2 = p;
//p最终赋值为第三个元素
p = p->next;
}
return head;
}
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪next指针再次到达，则链表中存在环。
为了表示给定链表中的环，我们使用整数pos来表示链表尾连接到链表中的位置（索引从0开始），如果pos是-1，则在该链表中没有环。（注：pos不作为参数进行传递，仅为了标识链表的实际情况）
如果链表中存在环，则返回true；否则，返回false。
| 示例： |
|---|
| 输入：head = [3,2,0,-4], pos = 1 |
| 输出：true |
| 解释：链表中有一个环，其尾部连接到第二个节点 |
bool hasCycle(struct ListNode *head) {
struct ListNode *fast,*slow;
fast = head;
slow = head;
while(fast != NULL && fast->next != NULL){
fast = fast->next->next;
slow = slow->next;
if(slow == fast)
return true;
}
return false;
}
上述程序应用了快慢链表的思想
fast链表每次步进两个元素
slow链表每次步进一个元素
有环的话fast链表会追上slow链表，进而两个链表元素相等，返回true；否则跳出循环，返回false。
还有程序应用hash set思想，还没看到。
给定两个非空二叉树s和t，检验s中是否包含和t具有相同结构和节点值的子树。s的一个子树包括s的一个节点的所有子孙。s也可以看做它自身的一颗子树。
给定的树s
给定的树t
返回True
给定的树s
给定的树t
返回False
class Solution {
public:
//基本的树检测函数
bool check(TreeNode *s, TreeNode *t) {
if (!s && !t) {
return true;
}
if ((s && !t) || (!s && t) || (s->val != t->val)) {
return false;
}
return check(s->left, t->left) && check(s->right, t->right);
}
//DFS逻辑函数
bool dfs(TreeNode *s, TreeNode *t) {
if (!s) {
return false;
}
return check(s, t) || dfs(s->left, t) || dfs(s->right, t);
}
//调用DFS
bool isSubtree(TreeNode *s, TreeNode *t) {
return dfs(s, t);
}
};
使用DFS枚举s中的每一个子节点，判断这个点的子树和t是否相等。
方式是让两个指针一开始先指向该节点和t的根，然后同步移动两根指针来同步遍历这两颗树。
请设计一个算法来实现二叉树的序列化和反序列化。（不限序列化和反序列化的执行逻辑，只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构）
| 示例： |
|---|
| 输入：root = [1,2,NULL,NULL,3,4,NULL,NULL,5,NULL,NULL] |
| 输出：[1,2,NULL,NULL,3,4,NULL,NULL,5,NULL,NULL] |
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if(root == NULL)
return "NULL,"; //检测到空树，返回NULL
string res = to_string(root->val) + ","; //不是空节点，则将元素转为字符串类型，并加上该节点元素
res += serialize(root->left); //左孩子递归
res += serialize(root->right); //左孩子递归结束，自下而上继续右孩子递归
return res;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
std::stringstream ss(data); //队列相关可参考https://www.cnblogs.com/john1015/p/12956593.html
std::string item;
queue<string> q;
while (std::getline(ss, item, ‘,‘)) //常用分隔","方式
q.push(item); //至此得到完整的队列q（包含所有树数据）
return helper(q);
}
TreeNode* helper(queue<string>& q) //还原二叉树
{
string val = q.front(); //获取队列最前端元素
q.pop(); //获取后即弹出该元素
if (val == "NULL")
return NULL;
TreeNode* head = new TreeNode(stoi(val)); //stoi()为带范围检查的string转int的函数 参考https://blog.csdn.net/qq_33221533/article/details/82119031 atoi才是char转int
head->left = helper(q);
head->right = helper(q);
return head;
}
};
给一个二叉树的根节点root，树中每个节点都存放有一个0-9之间的数字，每条从根节点到叶节点的路径都代表一个数字：
例如，从根节点到叶节点的路径为1->2->3，表示数字123。
计算从根节点到叶节点生成的所有数字之和。
（叶节点是指没有子节点的节点）
| 示例： |
|---|
| 输入：root = [1,2,3] |
| 输出：25 |
| 解释：12+13 |
int dfs(struct TreeNode* root, int prevSum) {
if (root == NULL) { //空节点，则返回0
return 0;
}
int sum = prevSum * 10 + root->val; //只要不是空节点，就累加
if (root->left == NULL && root->right == NULL) {
return sum; //表明已经到达叶节点
} else {
return dfs(root->left, sum) + dfs(root->right, sum); //否则继续搜索
}
}
int sumNumbers(struct TreeNode* root) {
return dfs(root, 0);
}
深度优先搜索，带参数的累加（将过去累加值作为参数）
给定一个整数数组nums和一个整数目标值target，请在该数组中找出“和为目标值”的那两个整数，并返回它们的数组下标。（假定每种输入只会对应一个答案，但是数组中同一元素在答案里不能重复出现。）
| 示例： |
|---|
| 输入：nums= [2,7,11,15], target = 9 |
| 输出：[0,1] |
| 解释：nums[0]+nums[1]=9 |
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
for(int i = 0;i < numsSize-1;i++){
for (int j = i+1;j<numsSize;j++){
if (nums[i]+nums[j]==target){
int* res = malloc(sizeof(int) * 2);
res[0] = i;
res[1] = j;
*returnSize = 2;
return res;
}
}
}
*returnSize = 0;
return NULL;
}
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hashtable;
for (int i = 0; i < nums.size(); ++i) {
auto it = hashtable.find(target - nums[i]);
if (it != hashtable.end()) {
return {it->second, i};
}
hashtable[nums[i]] = i;//先找后加入表，防止查到自己（元素5，target=10）
}
return {};
}
};
给定一个经过编码的字符串，返回它解码的字符串。
编码规则为：k[string]，k表示string重复了k次，k为正整数。
| 示例： |
|---|
| 输入：s = "3[a]2[bc]" |
| 输出："aaabcbc" |
| 解释：3次a+2次bc |
class Solution {
public:
pair<string,int> solver(const string&s, int i){
int multiplier = 0;
string mul = "";
string ans = "";
while(i < s.length()){
if(s[i] >= ‘0‘&&s[i] <= ‘9‘){ //检测到是数字，则将数字累加（字符串形式）
mul = mul + s[i];//这里没有把之前的数据位清除
//multiplier = multiplier*10 +s[i] - ‘0‘; //这里通过直接将字符串解算成int
}else if (s[i] == ‘[‘){ //检测到左括号，进行递归，再检测，再递归，直至检测到‘]‘
auto sub_ans = solver(s,i+1);
i = sub_ans.second;
multiplier = stoi(mul); //字符串类型转为int
while(multiplier > 0){
ans += sub_ans.first; //字符串重复
multiplier--;
}
mul = ""; //清空mul
}else if (s[i] == ‘]‘){ //检测到‘]‘，返回数据对
return pair(ans,i);
}else { //检测到字母，则字符串ans++
ans += s[i];
}
i++; //进行下一次检测
}
return pair(ans,i); //返回总的数据对
}
string decodeString(string s) {
return solver(s,0).first;
}
};
class Solution {
public:
string getDigits(string &s, size_t &ptr) { //获取数字子函数
string ret = "";
while (isdigit(s[ptr])) { //此处while循环是为了获取二位数及以上的倍数
ret.push_back(s[ptr++]); //此处已经将ptr++
}
return ret;
}
string getString(vector <string> &v) { //为了将string数组v中的字符串全部导出为单独的字符串
string ret;
for (const auto &s: v) {
ret += s;
}
return ret;
}
string decodeString(string s) {
vector <string> stk;
size_t ptr = 0;
while (ptr < s.size()) {
char cur = s[ptr];
if (isdigit(cur)) {
// 获取一个数字并进栈
string digits = getDigits(s, ptr); //该函数内已经将ptr++
stk.push_back(digits);
} else if (isalpha(cur) || cur == ‘[‘) {
// 获取一个字母并进栈
stk.push_back(string(1, s[ptr++]));
} else { //检测到右括号，开始出栈
++ptr;
vector <string> sub; //子字符串数组
while (stk.back() != "[") {
sub.push_back(stk.back());
stk.pop_back();
}
reverse(sub.begin(), sub.end());
// 左括号出栈
stk.pop_back();
// 此时栈顶为当前 sub 对应的字符串应该出现的次数
int repTime = stoi(stk.back());
stk.pop_back();
string t, o = getString(sub);
// 构造字符串
while (repTime--) t += o;
// 将构造好的字符串入栈
stk.push_back(t);
}
}
return getString(stk);
}
};
主循环
子函数
getdigits，获取倍数
isdigit(char)，判断char是否为数字
getstring，将字符串类型数组转为字符串
isalpha(char)，判断char是否为字符串
根据每日气温列表，重新生成一个列表，对应位置的数据为“想要观测到更高的气温，至少需要等待的天数”
如果该日气温后续不再上升，则对应位置数据置0
| 示例： |
|---|
| 输入：temperatures = [73,74,75,71,69,72] |
| 输出：[1,1,0,2,1,0] |
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& T) {
int n = T.size();
vector<int> ans(n);
stack<int> s;
for (int i = 0; i < n; ++i) {
while (!s.empty() && T[i] > T[s.top()]) { //栈非空，且当前数据大于栈顶数据
int previousIndex = s.top();
ans[previousIndex] = i - previousIndex;
s.pop();
}
s.push(i);
}
return ans;
}
};
中位数是有序列表中间的数，如果列表长度是偶数，中位数是中间两个数的平均值。
设计一个支持以下两种操作的数据结构：
| 示例： |
|---|
| 输入：addNum(1) addNum(2) findMedian() addNum(3) findMedian() |
| 输出：[null, null, null, 1.5, null, 2.0] |
class MedianFinder {
vector<double> store;
public:
// Adds a number into the data structure.
void addNum(int num)
{
store.push_back(num); //数组中加入元素
}
// Returns the median of current data stream
double findMedian()
{
sort(store.begin(), store.end()); //将数组中数据按从小到大的顺序放置
int n = store.size();
return (n & 1 ? store[n / 2] : (store[n / 2 - 1] + store[n / 2]) * 0.5); //返回中位数
}
};
但这样写会超时！！！
n&1指的是n的最低位与1想与，若为奇数，则返回1；若为偶数，则返回0.
class MedianFinder {
vector<int> store; // resize-able container
public:
// Adds a number into the data structure.
void addNum(int num)
{
if (store.empty()) //空矩阵则直接将数据存入
store.push_back(num);
else //否则通过insert插入，insert的键值由lower_bound获取
store.insert(lower_bound(store.begin(), store.end(), num), num); // binary search and insertion combined
}
// Returns the median of current data stream
double findMedian()
{
int n = store.size(); //接下来直接同暴力法相同
return n & 1 ? store[n / 2] : (store[n / 2 - 1] + store[n / 2]) * 0.5;
}
};
中心思想与暴力法一致，先获取排序好的数组store，然后再return中位数
AddNum函数：
如果Store为空，则直接将数据压入矩阵；
否则通过insert插入数据，insert的键由lower_bound函数获取
lower_bound(First,Last,num)指搜索(First,Last)之间第一个不小于num的数的键；
insert(key,num)指在key处插入num
findMedian()同暴力法，直接返回中位数
class MedianFinder {
priority_queue<int> lo; // max heap
priority_queue<int, vector<int>, greater<int>> hi; // min heap
public:
// Adds a number into the data structure.
void addNum(int num)
{
lo.push(num); // Add to max heap
hi.push(lo.top()); // balancing step
lo.pop();
if (lo.size() < hi.size()) { // maintain size property
lo.push(hi.top());
hi.pop();
}
}
// Returns the median of current data stream
double findMedian()
{
return lo.size() > hi.size() ? (double) lo.top() : (lo.top() + hi.top()) * 0.5;
}
};
解释：
通过构建并平衡两个大顶堆和小顶堆，来获取最中间的数字（一个/两个）；
定义一个大顶堆和一个小顶堆，即“priority_queue”格式
优先队列（priority_queue）用法：
定义格式：
priority_queue<int, vector
priority_queue<int, vector
AddNum函数
以上两步可以保证二者相互平衡或接近。
findMedian函数
判断大顶堆和小顶堆数据是否相等，来确定是单数数据还是双数，并return对应中位数。
给一个包含n个整数的数组nums，判断nums中是否存在三个元素a，b，c，使得a+b+c=0？
请找出所有和为0且不重复的三元组。
| 示例1： |
|---|
| 输入：nums = [-1,0,1,2,-1,-4] |
| 输出：[[-1,-1,2],[-1,0,1]] |
| 示例2： |
|---|
| 输入：nums = [] |
| 输出：[] |
class Solution {
public:
vector<vector<int>> twoSum(vector<int>& nums, int start, int end, int target, int value){
vector<vector<int>> answer;
while(start < end){
int sum = nums[start] + nums[end];
if(sum == target){ //找到目标和
vector<int>result; //定义结果子数组
result.push_back(value); //第一个数组元素
result.push_back(nums[start]); //第二个数组元素
result.push_back(nums[end]); //第三个数组元素
answer.push_back(result); //压入结果数组
while(start < end && nums[start] == nums[start+1]){ //防止重复，移动指针
start++;
}
start++; //继续搜索下一组
while(start < end && nums[end] == nums[end-1]){ //防止重复，移动指针
end--;
}
end--; //继续搜索下一组
}else if(sum < target){
start++; //如果和小于目标值，则后移前向指针
}else{
end--; //如果和大于目标值，则前移后向指针
}
}
return answer; //返回结果数组(仅对应一个解的数组)
}
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> answer; //好家伙，原来是这样定义的
sort(nums.begin(), nums.end()); //方便执行双指针，对数组进行排序
int size = nums.size();
for(int i = 0;i < size;i++){
if(i>0&&nums[i] == nums[i-1]){
continue; //如果两个数组元素相等，则跳过，不再执行twoSum
}
auto result = twoSum(nums,i+1,size-1,-nums[i],nums[i]); //result即为子函数的answer
answer.insert(answer.end(),result.begin(),result.end()); //在anwer.end处插入数组
}
return answer;
}
};
将数组元素排序，依次遍历一遍，将三数之和问题转变为两数之和问题；
排序的目的是为了方便执行双指针算法，从两侧依次逼近target；
twoSum函数
定义结果子数组：vector<vector
第一个指针start指向输入元素的后一个元素，第二个指针end，即剩余元素的最小值和最大值，sum等于二者之和；
当sum大于target值时，end指针前移；当sum小于target值时，start指针后移；
当sum等于target时，先将当前元素包装起来（即先赋值到一个临时数组中），再将包装后的元素赋值到answer数组中；
同时start指针后移，end指针前移，继续搜索有无其他成立的数组元素。
threeSum函数
给定两个数组，编写一个函数来计算它们的交集。
（输出元素出现的次数等于两个数组元素出现次数的最小值）
| 示例1： |
|---|
| 输入：nums1 = [1,2,2,1], nums2 = [2,2] |
| 输出：[2,2] |
| 示例2： |
|---|
| 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] |
| 输出：[4,9] |
(将每个元素视为独立个体，即检测独立个体的出现次数)
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
if (nums1.size() > nums2.size()) { //始终确保nums1为较短的数组
return intersect(nums2, nums1);
}
unordered_map <int, int> m;
for (int num : nums1) {
++m[num]; //构建哈希表
}
vector<int> intersection;
for (int num : nums2) { //遍历nums2数组
if (m.count(num)) { //返回哈希表m中含有“num”键的数量
intersection.push_back(num); //向结果数组中压入num
--m[num]; //num数量减一
if (m[num] == 0) { //num数量为0时，哈希表m删除该元素
m.erase(num);
}
}
}
return intersection; //返回结果数组
}
};
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end()); //将数组1和数组2进行排序
int length1 = nums1.size(), length2 = nums2.size();
vector<int> intersection;
int index1 = 0, index2 = 0;
while (index1 < length1 && index2 < length2) { //当指针均未超出数组长度
if (nums1[index1] < nums2[index2]) {
index1++; //数组1元素小于数组2，则数组1指针后移
} else if (nums1[index1] > nums2[index2]) {
index2++; //数组1元素大于数组2，则数组2指针后移
} else { //数组1和数组2元素相等时
intersection.push_back(nums1[index1]); //数据压入结果数组
index1++;
index2++; //两个指针同时后移
}
}
return intersection;
}
};
给定一个整数数组arr和一个目标值target，请返回一个整数value，使得将数组中所有大于value的变成value后，数组的和最接近target（最接近表示两者之差的绝对值最小）
如果有多种使得和最接近target的方案，请返回这些整数中的最小值。
答案不一定是arr中的数字。
| 示例1： |
|---|
| 输入：arr = [4,9,3], target = 10 |
| 输出：3 |
| 解释：当选择value为3时，数组变为[3,3,3]，和为9，差值为1；当选择value为4时，数组变为[3,4,4]，和为11，差值为1。但3比4小，所以输出3。 |
class Solution {
public:
int Sum_Vector(vector<int> arr, int res) { //计算数组和
int ret = 0;
for (auto num : arr)
ret += num >= res ? res : num;
return ret;
}
int findBestValue(vector<int>& arr, int target) {
sort(arr.begin(),arr.end());
int n = arr.size();
vector<int> presum(n + 1);
for (int i = 1; i <= n; i++) //获取前缀和
presum[i] = presum[i-1] + arr[i - 1];
int value;
int min = 0, max = *max_element(arr.begin(), arr.end()); //二分查找的范围，即val的范围
while (min <= max) {
int mid = (min + max) / 2;
auto iter = lower_bound(arr.begin(), arr.end(), mid); //返回不小于mid的第一个值的正向迭代器
int cur = presum[iter - arr.begin()] + (arr.end() - iter)*mid; //计算当前数组和
if (cur <= target) {
value = mid;
min = mid + 1;
}
else
max = mid - 1;
}
return (abs(Sum_Vector(arr, value) - target) <= abs(Sum_Vector(arr, value + 1) - target) ? value : value + 1);
}
};
原文：https://www.cnblogs.com/eesaltedfish/p/14710879.html