背包问题

描述
在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);
        
    }
};