算法学习笔记-无题

//你可以新创建一个链表，也可以在原有的链表上操作，这里选新创建的链表
//(1)两数相加，最重要的就是考虑进位，每次赋值，记得加上进位；
//(2)最后一个数是否为1,取决于最高位是否有进位；
//(3)循环条件，只要有一个链表不为空就可以继续进行
//(4)代码如下：
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *head = new ListNode(-1), *p = head;//head为移动指针,p为固定指针
        int carry = 0, data = 0;
        while (l1 || l2){
            if (l1){
                data += l1->val;
                l1 = l1->next;
            }
            if (l2){
                data += l2->val;
                l2 = l2->next;
            }
            if (carry == 1){
                data ++;
            }
            head->next = new ListNode(data % 10);
            head = head->next;
            carry = data / 10;
            data = 0;
        }
        if (carry){
            head->next = new ListNode(1);
        }
        return p->next;
    }

//提前说好，这个题目直接使用pow(x, n)是直接能过的，但是这样就考察不到这个题的算法了，我们使用快速幂来解答
double quick(double base, long long n){
        double result = 1;
        while (n){
            if (n&1){
                result *= base;
            }
            base = base * base;
            n >>= 1;
        }
        return result;
    }
    double myPow(double x, int n) {
        long long N = n;
        return N >= 0 ? quick(x, N) : 1.0/quick(x, -N);
    }

//这题可以直接使用next_permutation()但是考察不到算法点：这题可以用dfs来解答
//next_permutation()
std::string getPermutation(int n, int k) {
        int num[n];
        for (int i = 1; i <= n; i ++){
            num[i - 1] = i;
        }
        int len = 0;
        std::string str = "";
        do{
            if (len == k){
                for (int i = 0; i < n; i ++){
                    str += std::to_string(num[i]);
                }
                break;
            }
        }while(std::next_permutation(num, num + n));
    }
//dfs
 vector <int> nums;
    int vis[10] = {0}, cnt = 0, flag = 0;
    string str = "";
    void getStr(){
        for (auto c : nums){
            str += to_string(c);
        }
    }
    void dfs (vector <int>& nums, int n, int k, int sum){
         if (sum >= n){
             cnt ++;
             if (cnt == k){
                 flag = 1;
                 getStr();
             }
             return;
         }
         for (int i = 1; i <= n; i ++){
             if (vis[i] == 0 && flag == 0){
                 nums.push_back(i);
                 vis[i] = 1;
                 dfs (nums, n, k, sum + 1);
                 nums.pop_back();
                 vis[i] = 0;
             }
         }
    }
    string getPermutation(int n, int k) {
       dfs (nums, n, k, 0);
       return str;
    }

//这题还是可以直接用sqrt()直接得到答案，但是得不到训练；
//sqrt
    int mySqrt(int x) {
        return std::sqrt(x);
    }
//牛顿迭代法x = (x + a / x) / 2;
    int mySqrt(int x){
        double a = x, res = x, tmp = 0;
        if (x == 0)return 0;
        while (true){
            res = (res + a / res) / 2; //牛顿迭代法，a一直不变,x一直迭代变化
            if ((int)tmp == (int)res)break;
            tmp = res;
        }
        return (int)res;
    }

    std::unordered_map <int, int> mapp;
    int judgeHappy(int n){
        int sum = 0;
        while (n){
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
    bool isHappy(int n) {
        while (n != 1){
            mapp[n] = 1;
            n = judgeHappy(n);
            if (mapp[n] == 1)return false;
        }
        return true;
    }

  
      int calculate(string s) {
        stack<int> st;
        unsigned int ans = 0, num = 0, op = 1;
        st.push(op);
        for (auto c : s){
            if (c == ' ')continue;
            if (c >= '0' && c <= '9'){
                num = num * 10 + c - '0';
            }else{
                ans += op * num;
                num = 0;
                if (c == '+') op = st.top();
                if (c == '-') op = -st.top();
                if (c == '(') st.push(op);
                if (c == ')') st.pop();
            }
        }
        // -22 + 1 + 23
        return ans + op * num;
    }

    bool isPowerOfTwo(int n) {
        if (n <= 0)return false;
        if (n & (n - 1)) //将最低位的一清0，如果为2的幂，那就一个1.清0会变为0
            return false;
        else
            return true;
    }

bool isUgly(int n) {
        for (int i = 0; pow (2, i) <= n; i ++){
            for (int j = 0; pow (3, j) <= n; j ++){
                for (int k = 0; pow (5, k) <= n; k ++){
                    if (pow(2, i) * pow(3, j) * pow(5, k) == n)
                        return true;
                }
            }
        }
        return false;
    }

    bool isPowerOfThree(int n)
    {
        if(n < 1)  return false;
        while(n % 3 == 0)
        {
            n = n / 3;
        }
        return n == 1;
    }

    long long maxn = 0, m;
    void dfs(long long s, long long sum, long long k, long long total){
        if (sum > m)return;
        if (sum == m && k > 1){
            maxn = max(maxn, total);
            return;
        }
        for (long long i = s; i <= m; i ++){
            dfs (i, sum + i, k + 1, total * i);
        }
    }
    int integerBreak(int n) {
        m = n;
        dfs (1, 0, 0, 1);
        return maxn;

    }

    int maximumProduct(vector<int>& nums) {
        decltype (nums.size()) len = nums.size(), sum = 1;
        sort (nums.begin(), nums.end(), [&](const int& a, const int& b){return a > b;});
        int a1 = nums[0] * nums[1] * nums[2];
        int a2 = nums[len - 1] * nums[len - 2] * nums[0];
        return max(a1, a2);
    }

//分析：
//(1)第一部分：dp[i] = dp[i - 1] * 10 + ...; dp[i - 1]为i - 1位数重复的数目，，对于i位：只需要再后面加0-9也
//必然重复
//(2)如果前i-1位不重复呢,比如12， 21什么的，只需要排列组合即可：第一位有9种放法,后面都是10种也就是9*pow(10, i-2)
//这个放法是包括了dp[i - 1]的所以减去，然后最后一位只要与前i-1种一个一样就行了。即乘以i-1
    //dp[i] = dp[i - 1] * 10 + (pow (10, i - 2) * 9 - dp[i - 1]) * (i - 1)
    int countNumbersWithUniqueDigits(int n) {
        vector <int> dp(n + 2);
        for (int i = 2; i <= n; i ++){
            dp[i] = dp[i - 1] * 10 + (pow (10, i - 2) * 9 - dp[i - 1]) * (i - 1);
        }
        int sum = 0;
        for (auto v : dp){
            sum += v;
        }
        return pow (10, n) - sum;//总的减去重复的就是答案，
    }

    vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {
           int fx[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}, t = 2,  pos = 0, cnt = 0;
           vector<vector<int>> ans;
           while(cnt < R * C){
               //遍历步长，每转两下就会增加一步
               for(int i = 0; i < t / 2; i ++){
                   if(r0 >= 0 && r0 < R && c0 >= 0 && c0 < C)
                       ans.push_back({r0, c0}), ++ cnt;
                   r0 += fx[pos][0];
                   c0 += fx[pos][1];
               }
               pos = (pos + 1) % 4;
               t ++;
           }
           return ans;
       }

    vector<int> diStringMatch(string s) {
        vector <int> vt;
        int maxLen = s.size(), minLen = 0;
        for (auto c : s){
            if (c == 'I'){
                vt.push_back(minLen);
                minLen ++;
            }else{
                vt.push_back(maxLen);
                maxLen --;
            }
        }
        vt.push_back(maxLen);
        return vt;
    }

    int largestPerimeter(vector<int>& nums) {
        sort(nums.begin(), nums.end(), [&](const int& a, const int& b){return a > b;});
        for (int i = 0; i < nums.size() - 2; i ++){
            if (nums[i + 1] + nums[i + 2] > nums[i])return nums[i] + nums[i + 1] + nums[i + 2];
        }
        return 0;
    }

 //对于1， 2， 3， 4， 5很不明显不能直接遍历每个子序列，肯定会超时
 //题目求宽度，也就是说：一个子序列中只有最大值和最小值有用，其他的都无用，，
 //那可以让各个数为最大值和最小值，比如：2为最小值是有多少种子序列？
 //那肯定是3，4， 5随机排列3， 4,5可以不选也可以选，，所以一共有 8种
 //2为最大值有2种，，然后把所有的最大值相加之后减去所有最小值的种数就是答案；   
    
    typedef long long ll;
    const ll MOD = 1e9 + 7;
   ll answer = 0;
    int sumSubseqWidths(vector<int>& A){
       vector <int> B;
       B.push_back(1LL);
       for (int i = 1; i < A.size(); i ++){
           B.push_back(B[B.size() - 1] * 2 % MOD);
       }
       sort(A.begin(), A.end());
       for (ll i = 0; i < A.size(); i ++){
           ll y = (B[i] - B[B.size() - i - 1] + MOD) % MOD;
           y = A[i] * y % MOD;
           answer = (answer + y) % MOD;
       }
       return (int)answer;
    }

//数字N如果是奇数，它的约数必然都是奇数；若为偶数，则其约数可奇可偶。
//无论N初始为多大的值，游戏最终只会进行到N=2时结束，那么谁轮到N=2时谁就会赢。
//因为爱丽丝先手，N初始若为偶数，爱丽丝则只需一直选1，使鲍勃一直面临N为奇数的情况，这样爱丽丝稳赢；
//N初始若为奇数，那么爱丽丝第一次选完之后N必为偶数，那么鲍勃只需一直选1就会稳赢

      bool divisorGame(int n) {
        return !(n & 1);
    }

class Solution {
    int ans = 0;
public:
    int numSquarefulPerms(vector<int>& A) {
        vector<bool> vis(A.size(), false);
        sort(A.begin(), A.end());
        dfs(A, 0, -1, vis);
        return ans;
    }
    void dfs(vector<int>& A, int count, int prev, vector<bool>& vis)
    {
        if(count == A.size())
        {
            ans++;
            return;
        }
        for(int i = 0; i < A.size(); ++i)
        {
            if(i > 0 && !vis[i-1] && A[i-1]==A[i])
                continue;// 剪枝
            if(!vis[i] && (prev == -1 || ok(prev, A[i])))
            {
                vis[i] = true;
                dfs(A, count+1, A[i], vis);
                vis[i] = false;
            }
        }
    }
    bool ok(int a, int b)
    {
        int num = sqrt(a+b);
        return num*num == a+b;
    }
};