一个乱序的数组，删除其中的两个数，请找出删除的是哪两个数？

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;


int main(){

    // 删除2和5
    vector<int> nums{-1, 6,7,8,1,3,4,10,9};

    nums.push_back(-1);
    nums.push_back(-1);

    int n = nums.size()-1;
    for(int i=1;i<=n-2;i++){
        int x = nums[i];
        swap(nums[x], nums[i]);
    }
    for(int i=1;i<=n-2;i++){
        int x = nums[i];
        swap(nums[x], nums[i]);
    }
    for(int i=1;i<=n;i++){
        if(nums[i] == -1) cout<<i<<" ";
    }
    cout<<endl;


    return 0;
}

/*
 * 快速排序
 * 值分界点
 * 调整区间<=x >=x
 * 递归
 *
 */
#include <iostream>
#include <vector>

using namespace std;

void quick_sort(vector<int> &nums, int l, int r) {
    if (l >= r) return;

    // 值分界点
    int x = nums[(l + r) / 2];
    // 调整区间，双指针，分别从头尾相向而行，交换不满足区间要求的数
    // 区间：<x >x
    int i = l - 1, j = r + 1;
    while (i < j) {
        do i++; while (nums[i] < x);
        do j--; while (nums[j] > x);
        if (i < j) swap(nums[i], nums[j]);
    }
    // 递归
    quick_sort(nums, l, j);
    quick_sort(nums, j + 1, r);
}

/*
 * 终止条件
 * 分界点 mid = (l+r)/2
 * 分段递归
 * 归并（需要额外的数组,i,j,k）
 */
void merge_sort(vector<int> &nums, int l, int r) {
    // 终止条件
    if (l >= r) return;
    // 分界点
    int mid = (l + r) / 2;
    // 分段递归
    merge_sort(nums, l, mid);
    merge_sort(nums, mid + 1, r);

    // 归并
    vector<int> tmp(r - l + 1); // 缓冲区
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (nums[i] <= nums[j]) tmp[k++] = nums[i++];
        else tmp[k++] = nums[j++];
    }

    // 剩余的数
    while (i <= mid) tmp[k++] = nums[i++];
    while (j <= r) tmp[k++] = nums[j++];

    // 拷贝回原数组
    for (int i = l, k = 0; i <= r; i++, k++) nums[i] = tmp[k];
}

int main() {

    vector<int> nums{8, 2, 4, 6, 2, 9, 1};

//    quick_sort(nums, 0, nums.size()-1);
    merge_sort(nums, 0, nums.size() - 1);

    for (int x: nums) cout << x << " ";
    cout << endl;

    return 0;
}

/*
 * 两个指针i,j，分别从末端向前走
 * sum = i+j+bit
 * rest 求解除去进位的和
 * bit 求解进位
 *
 * 注意对剩余子串的相加
 * 对bit的相加
 */

#include <iostream>
#include <vector>
using namespace std;
/*
 * i,j分别从两个字符串末尾开始前进
 * i+bit能够减去j，直接减（注意-'0'）
 * i+bit无法减去j，加10再减，维护bit = -1
 *
 * 第一个字符串剩余部分，bit剩余部分
 *
 *
 */


string stringSub(string &num1, string &num2) {
    int n = num1.size();
    int m = num2.size();

    // i,j分别从两个字符串末尾开始前进
    int i = n-1, j = m-1;
    int bit = 0;
    string res;
    while(i>=0 && j>=0){
        int t = num1[i]-'0' + bit - (num2[j]-'0');
        // 无法减，借位
        if(t<0){
            t = num1[i]-'0' + bit - (num2[j]-'0') + 10;
            bit = -1;
        }
        res = to_string(t) + res;
        i --, j--;
    }
    // 剩余的字符串和进位
    while(i>=0){
        int t = num1[i]-'0' + bit;
        // 无法减，借位
        if(t<0){
            t = num1[i]-'0' + bit + 10;
            bit = -1;
        }
        res = to_string(t) + res;
        i --;
    }
    return res;

}

int main() {

    string num1 = "456";
    string nums2 = "77";

    cout<<stringSub(num1, nums2)<<endl;

    return 0;
}

需要处理进位
需要处理字符串1剩余部分
需要处理字符串2剩余部分
需要处理最后的进位

/*
 * 两个指针i,j，分别从末端向前走
 * sum = i+j+bit
 * rest 求解除去进位的和
 * bit 求解进位
 *
 * 注意对剩余子串的相加
 * 对bit的相加
 */

#include <iostream>
#include <vector>
using namespace std;

string stringAdd(string &num1, string &num2) {
    int n = num1.size();
    int m = num2.size();

    // 两个指针i,j，分别从末端向前走
    int i = n - 1, j = m - 1;
    bool bit = 0;
    string res;
    while (i >= 0 && j >= 0) {
        // 求和
        int sum = num1[i] - '0' + num2[j] - '0' + bit;
        // 除去进位
        int rest = sum % 10;
        // 进位
        bit = sum / 10;

        res = to_string(rest) + res;

        i--, j--;
    }

    // num1还剩余
    while (i >= 0) {
        // 求和
        int sum = num1[i] - '0' + bit;
        // 除去进位
        int rest = sum % 10;
        // 进位
        bit = sum / 10;

        res = to_string(rest) + res;

        i--;
    }
    // num2还剩余
    while (j >= 0) {
        // 求和
        int sum = num2[j] - '0' + bit;
        // 除去进位
        int rest = sum % 10;
        // 进位
        bit = sum / 10;

        res = to_string(rest) + res;

        j--;
    }
    // 最后剩下进位
    if(bit) res = "1" + res;
    return res;
}

int main() {

    string num1 = "0";
    string nums2 = "0";

    cout<<stringAdd(num1, nums2)<<endl;

    return 0;
}

/*
 * DFS
 */

#include <iostream>
#include <vector>

using namespace std;

struct Node {
    int val;
    Node *left;
    Node *right;

    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

/*
 * 每次比较两棵子树
 *
 */

bool dfs(Node *l, Node *r) {
    // 两个节点都为空
    if (!l && !r) return true;
    // 其中一个节点为空
    if (!l || !r) return false;

    // 值不相同
    if (l->val != r->val) return false;
    // 值相同
    return dfs(l->left, r->right) && dfs(l->right, r->left);
}

bool isSymmetry(Node *root) {
    return dfs(root->left, root->right);
}


Node *buildTree(vector<int> &nums) {
    // 为非空节点分配内存
    int n = nums.size();
    vector<Node *> nodes(n);
    for (int i = 0; i < n; i++) {
        if (nums[i] != INT_MAX) nodes[i] = new Node(nums[i]);
    }

    // 为非空节点关联左右节点
    for (int i = 0; i < n; i++) {
        if (nodes[i]) {
            if (2 * i + 1 < n) nodes[i]->left = nodes[2 * i + 1];
            if (2 * i + 2 < n) nodes[i]->right = nodes[2 * i + 2];
        }
    }
    return nodes[0];
}

int main() {

    // 建立二叉树
    vector<int> nums{1, 2, 2, INT_MAX, 3, INT_MAX, 3};
    Node *root = buildTree(nums);

    cout << isSymmetry(root) << endl;

    return 0;
}

/*
 * DFS
 */

#include <iostream>
#include <vector>

using namespace std;

struct Node {
    int val;
    Node *left;
    Node *right;

    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

Node *dfs(Node *root, int p, int q) {
    if (!root) return nullptr;

    bool flag = false;
    if (root->val == p || root->val == q) flag = true;

    Node *l = dfs(root->left, p, q);
    Node *r = dfs(root->right, p, q);

    // 作为祖先节点
    // 左右子树各自存在p,q
    if (l && r) return root;
    // 左子树存在，本节点存在
    if (l && flag) return root;
    // 右子树存在，本节点存在
    if (r && flag) return root;

    // 不是祖先节点，但是含有p或者q
    if (flag) return root;
    if (!flag && l) return l;
    if (!flag && r) return r;

    return nullptr;
}

Node *nearestCommonAncestor(Node *root, int p, int q) {
    return dfs(root, p, q);
}

Node *buildTree(vector<int> &nums) {
    // 为非空节点分配内存
    int n = nums.size();
    vector<Node *> nodes(n);
    for (int i = 0; i < n; i++) {
        if (nums[i] != INT_MAX) nodes[i] = new Node(nums[i]);
    }

    // 为非空节点关联左右节点
    for (int i = 0; i < n; i++) {
        if (nodes[i]) {
            if (2 * i + 1 < n) nodes[i]->left = nodes[2 * i + 1];
            if (2 * i + 2 < n) nodes[i]->right = nodes[2 * i + 2];
        }
    }
    return nodes[0];
}

int main() {

    // 建立二叉树
    vector<int> nums{3, 5, 1, 6, 2, 0, 8, INT_MAX, INT_MAX, 7, 4};
    Node *root = buildTree(nums);

    int p = 5, q = 4;
    Node *res = nearestCommonAncestor(root, p, q);

    // 打印祖先节点
    if (res)
        cout << res->val << endl;

    return 0;
}

代码有几个用例过不了，不知道为什么

/*
 * 二分算法
 * 两次二分
 * 先通过二分，找出旋转后的分界点
 * 然后比较target的值，在左区间或者右区间再次进行二分
 *
 */

#include <iostream>
#include <vector>
using namespace std;

int searchNum(vector<int>& nums, int target){

    if(nums.size() == 0) return -1;
    if(nums.size() == 1){
        if(nums[0] == target) return 0;
        else return -1;
    }


    int index = 0; // target的索引

    // 先通过二分，找出旋转后的分界点(右分界点)
    // [>=x, <x]
    int n = nums.size();
    int x = nums[0];
    int l = 0, r = n-1;
    while(l<r){
        int mid = (l+r)/2;
        if(nums[mid]<x) r = mid; // [l, mid][mid+1, r]
        else l = mid+1;
    }
    // 右分界点
    int p = l;

    // target在左区间中，[0, p-1]
    if(target >= x){
        int l = 0, r = p-1;
        // [<target][>=target]
        while(l<r){
            int mid = (l+r)/2;
            if(nums[mid]>=target) r = mid; // [l, mid][mid+1, r]
            else l = mid+1;
        }
        index = r;
    }
    // target在右区间中，[p, n-1]
    else{
        // [<<target][>=target]
        int l = p, r = n-1;
        while(l<r){
            int mid = (l+r)/2;
            if(nums[mid]>=target) r = mid; // [l, mid][mid+1, r]
            else l = mid+1;
        }
        index = r;
    }
    if(nums[index] == target) return index;
    else return -1;
}


int main(){

    vector<int> nums{1,3};
    int target = 3;

    cout<<searchNum(nums, target)<<endl;

    return 0;
}

这道题用lowbit是最好的，不要用右移，因为对于负数，右移后头部添加的数字为1

/*
 * 对于正数，只需要把x - lowbit(x)，然后递增计数即可
 * lowbit的实现，return x & -x;
 *
 */
#include <iostream>

using namespace std;

int lowbit(int x){
    return x & -x;
}

int onesCnt(long long x){
    int n = 0;
    while(x){
        x = x - lowbit(x);
        n ++;
    }
    return n;
}

int main(){

    long long x = -100;
    cout<<onesCnt(x)<<endl;
    cout<<__builtin_popcount(x)<<endl;

    return 0;
}

/*
 * dummy
 * 遍历所有节点t
 * p = t->next, q = p->next, q开始往下走，直到值与p不同
 * 如果p = q, t变为p
 * 如果p != q, 删除[p, q]节点
 */
#include <iostream>
#include <vector>
using namespace std;

struct Node{
    int val;
    Node* next;
    Node(int x = -1): val(x), next(nullptr) {}
};

Node* deleteRepeatedNode(Node* head){
    // 为了避免边界问题，在链表前边接一个空节点
    Node* dummy = new Node;
    dummy->next = head;
    Node* h = dummy;

    // 遍历所有结点
    while(h->next){
        Node* p = h->next; // 下一个节点
        Node* q = p->next; // 下下个节点
        // 遍历从q开始所有与p值相同的节点
        while(q && q->val == p->val) q = q->next;

        // 不存在重复节点
        if(p->next == q) h = p;
        // 存在重复节点
        else h->next = q;
    }
    return dummy->next;
}

int main(){

    // 构建链表
    vector<int> nums{1,1,1,2,3};
    Node* dummy = new Node;
    Node* p = dummy;
    for(int x : nums){
        p->next = new Node(x);
        p = p->next;
    }
    Node* head = dummy->next;
    delete dummy;


    Node* res = deleteRepeatedNode(head);
//    Node* res = head;

    // 打印
    p = res;
    while(p){
        cout<<p->val<<" ";
        p = p->next;
    }
    cout<<endl;

    return 0;
}

/*
 * 遍历每个节点
 * 如果值和上一个节点一样，删除该节点
 * 需要存储上一个值，存储上一个指针
 */
#include <iostream>
#include <vector>
using namespace std;

struct Node{
    int val;
    Node* next;
    Node(int _val = -1): val(_val), next(nullptr){}
};

Node* deleteRepeatedNode(Node* head){
    Node* p = head;
    Node* q = head;

    int last = INT_MAX;
    // 遍历每个节点
    while(p){
        // 和上一个节点的值相同，删除本节点
        if(p->val == last){
            q->next = p->next;
            delete p;
            p = q->next;
            continue;
        }
        // 若值不相同
        last = p->val;
        q = p;
        p = p->next;
    }
    return head;
}

int main(){

    // 构造链表
    vector<int> nums{1,1,2};
    Node* dummy = new Node;
    Node* p = dummy;
    for(int x : nums){
        p->next = new Node(x);
        p = p->next;
    }
    Node* head = dummy->next;
    delete dummy;

    Node* res = deleteRepeatedNode(head);

    // 打印
    p = res;
    while(p){
        cout<<p->val<<" ";
        p = p->next;
    }
    cout<<endl;

    return 0;
}