头像

jasonlin


访客:5416

在线 



jasonlin
1小时前

题目描述

在行数等于3时,将字符串"PAYPALISHIRING“按”N”字形排列,如下所示:

P A H N
A P L S I I G
Y I R

此时我们按行读取,会得到"PAHNAPLSIIGYIR".

要求编写一个函数,输入一个字符串和一个整数(表示行数),输出转换后的字符串:

string convert(string text, int nRows);
例如 convert("PAYPALISHIRING", 3)会返回"PAHNAPLSIIGYIR".



算法

(模拟找规律) $O(n)$

找下标的规律

  • 首位两行为单一的等差数列
    • 公差为 2 * (numRows - 1) 首项为 i
  • 中间的行为交替的等差数列
    • 公差为 2 * (numRows - 1) 首项为 i2 * (numRows - 1)- i

为了方便 把 2 * (numRows - 1) 拎出来


c++ 代码

class Solution {
public:
    string convert(string s, int numRows) {
        string res;
        if(numRows == 1) return s;

        int inc = (numRows - 1) * 2;
        int n  = s.size();
        // 枚举每一行
        for(int j = 0 ; j < numRows; j ++)
        {
            // 首尾两行  
            if(j == 0 || j == numRows - 1)
            {
                for(int i = j ; i < n; i += inc)
                    res += s[i];
            }
            // 中间的行 交替的等差数量
            else
            {
                for(int k = j, i = inc - j; i < n || k < n; i += inc , k += inc)
                {
                    if(k < n)  res += s[k];
                    if(i < n)  res += s[i];
                }
            }
        }

        return res;

    }
};


活动打卡代码 AcWing 6. Z 字形变换

jasonlin
1小时前

模拟题

找下标的规律

  • 首位两行为单一的等差数列
    • 公差为 2 * (numRows - 1) 首项为 i
  • 中间的行为交替的等差数列
    • 公差为 2 * (numRows - 1) 首项为 i2 * (numRows - 1)- i

为了方便 把 2 * (numRows - 1) 拎出来

class Solution {
public:
    string convert(string s, int numRows) {
        string res;
        if(numRows == 1) return s;

        int inc = (numRows - 1) * 2;
        int n  = s.size();
        // 枚举每一行
        for(int j = 0 ; j < numRows; j ++)
        {
            // 首尾两行  
            if(j == 0 || j == numRows - 1)
            {
                for(int i = j ; i < n; i += inc)
                    res += s[i];
            }
            // 中间的行 交替的等差数量
            else
            {
                for(int k = j, i = inc - j;i < n || k < n;i += inc , k += inc)
                {
                    if(k < n)  res += s[k];
                    if(i < n)  res += s[i];
                }
            }
        }

        return res;

    }
};



jasonlin
2小时前
  • 滑动窗口双指针
  • 维护窗口内的每个字符出现的次数为1
// for while 双指针模板
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> hash;
        int res = 0;

        for(int i = 0, j = 0; i < s.size(); i ++)
        {
            hash[s[i]] ++;
            while(hash[s[i]] > 1) hash[s[j ++]] --;  //大于1 j给右边滑动 直到等于1
            res = max (res, i - j + 1);
        }

        return res;
    }
};

类似题目如 lc 76 最小覆盖子串 注意两者的联系与区别

哈希表存的是满足条件,该字符还需要的数量 < 0 说明不需要

class Solution {
public:
    string minWindow(string s, string t) {

        unordered_map<char, int> hash; 
        for(auto c: t) hash[c] ++;
        int cnt = hash.size();

        string res = "";   
        for(int i = 0, j = 0, c = 0; i < s.size(); i ++)
        {
            if(hash[s[i]] == 1) c ++;  // 字符类型够啦
            hash[s[i]] --;  // 找到一个 距离目标又近了一步

            //满足条件下  j能不能删掉?
            while( c == cnt && hash[s[j]] < 0 )  // < 0 说明不缺了
                hash[s[j ++]] ++; // 缺的数目 + 1

            if(c == cnt && (res.empty() || res.size() > i - j + 1) ) 
                res = s.substr(j, i - j + 1);
        }

        return res;

    }
};


活动打卡代码 LeetCode 1. 两数之和

jasonlin
12小时前

思路

  • 哈希表保存元素出现的下标
  • 枚举每个元素,看其对应差值是否之前存在过

复杂度

  • 时间复杂度 $o(n)$
  • 空间复杂度 $o(n)$

class Solution{
public :
    vector<int> twoSum(vector<int>& nums , int target){
        if(nums.size() == 0) return vector<int>();

        vector<int> res;
        unordered_map<int,int> hash;  

        for(int i = 0; i < nums.size(); i++){
            int temp = target - nums[i];
            if(hash.find(temp) != hash.end()) {
                res.push_back(hash[temp]);  
                res.push_back(i);
            }
            else
                hash[nums[i]] = i;
        }

        return res;
    } 
};


活动打卡代码 AcWing 5426. 重新规划路线

思路

  • 枚举每条根节点到叶子节点的路径
  • 判断路径上的结点是否需要改变方向
  • 不一定是二叉树,所以用邻接表来存

  • 有向边 -> 无向边 + 真实方向 -> 为了防止重复遍历,记录下其从哪里下来的

class Solution {
public:

    vector<vector<pair<int, int>>> g;

    int minReorder(int n, vector<vector<int>>& connections) {
        g = vector<vector<pair<int, int>>> (n);    // 保存每个节点的 边的方向 1 指向别人  0 被别人指
        for(auto e : connections)
        {
            int a = e[0], b = e[1];
            g[a].push_back({b, 1});  // a -> b
            g[b].push_back({a, 0});  // b 被 a 指
        }

        return dfs(0, -1);
    }

    int dfs(int u, int father)
    {
        int res = 0;
        for(auto e : g[u])
        {
            int ver = e.first, dir = e.second;
            if(ver == father) continue; // 无需改变方向
            res += dfs(ver, u) + dir;
        }
        return res;
    }
};



关键点 读懂题意

  • 相邻最大差值

收获

  • 强制转换不太熟悉
class Solution {
public:
    const int M = 1e9 + 7;
    int maxArea(int h, int w, vector<int>& hs, vector<int>& vs) {
        hs.push_back(0), hs.push_back(h);
        vs.push_back(0), vs.push_back(w);

        sort(hs.begin(), hs.end());
        sort(vs.begin(), vs.end());

        int x = 0, y = 0;
        for(int i = 1; i < hs.size(); i ++)  x = max(x, hs[i] - hs[i - 1]);
        for(int i = 1; i < vs.size(); i ++)  y = max(y, vs[i] - vs[i - 1]);

        return (long long) x * y %  M;
    }
};



  • 先排序
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        return (nums[n - 1] -1 )* (nums[n - 2] - 1);
    }
};
  • 暴力枚举
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int res = INT_MIN;
        for (int i = 0; i < nums.size(); i ++ )
            for (int j = 0; j < i; j ++ )
                res = max(res, (nums[i] - 1) * (nums[j] - 1));
        return res;
    }
};



class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        int n = nums.size();
        vector<int> res;
        for(int i = 0; i < n; i++)
        {
            int cnt = 0;
            for(int j = 0; j < n; j++)
                if(nums[i] > nums[j]) cnt ++;
            res.push_back(cnt);
        }
        return res;   
    }
};

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n);

        for(int i = 0; i < n; i++)
            for(auto x : nums)
                if(nums[i] > x) res[i] ++;

        return res;   
    }
};



题意理解

  • 凑数字的代价等于目标值,而且凑的数最大
    • 位数最大
    • 位数相同的时候,字典序最大

考察点

  • 如何转换成背包问题求具体方案
  • 有限的组合问题求最优解 -> 背包问题

思考步骤

360截图20200529194319974.jpg

  • 物品 9个数视作 物品,其”体积”为 cost[i] 目标体积 -> target
  • 价值 价值都是1
  • 限制 可以选无数次 完全背包 f(i, j) = max(f(i - 1, j), f(i, j - cost[i]) + 1)
  • 状态的定义i 个数字,成本为 j 时的所能得到的最大位数

1) 首先求出最大位数 f[9][target]
2)再求具体的方案 倒着求


代码

时间复杂度 $o(10 * target)$

class Solution {
public:
    string largestNumber(vector<int>& cost, int target) {
        vector<vector<int>> f(10, vector<int>(target + 1));
        // 前 `i` 个数字,成本为 `j` 时的所能得到的最大位数
        for(int i = 1; i <= target; i++) f[0][i] = -1e8; // 初始化
        for(int i = 1; i <= 9; i ++)
            for(int j = 0; j <= target; j ++)
            {
                f[i][j] = f[i - 1][j];
                if(j >= cost[i - 1]) f[i][j] = max(f[i][j], f[i][j - cost[i - 1]] + 1);
            }
        if(f[9][target] < 1) return "0";  // 无法得到任何整数,返回 "0" 。

        // 答案可能会很大,以字符串形式返回
        string res;   // 前面的数字越大越好  倒着遍历
        for(int i = 9, j = target; i; i--)
        {
            while(j >= cost[i - 1] && f[i][j] == f[i][j - cost[i - 1]] + 1)
            {
                res += to_string(i);
                j -= cost[i - 1];
            }
        }

        return res;
    }
};



考察点

  • 如何判断闰年
    • 1)能被4整除,但不能被100整除 或者 能被400整除。
  • 怎么把年月日从字符串中抠出来 c_str() - > 当前字符串的首字符地址
int year, month, day;
sscanf(date.c_str(),"%d-%d-%d", &year, &month, &day);

思路

换算成日,求差即可

  • 注意对闰年 闰月的判断
class Solution {
public:
    int daysBetweenDates(string date1, string date2) {
        return abs(get(date1) - get(date2));
    }

    bool is_leap(int year) // 判断是否为闰年
    {
        return year % 100 && year % 4 == 0 || year % 400 == 0; 
    }

    int m_days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

    int get(string date)
    {
        int year, month, day;
        sscanf(date.c_str(),"%d-%d-%d", &year, &month, &day);

        int days = 0;
        for(int i = 1971; i < year; i++)
            days += 365 + is_leap(i);

        for(int i = 1; i < month; i++)
        {
            if(i == 2) day += 28 + is_leap(year);  // 对2月特判
            else days += m_days[i];
        }

        return days + day;
    }
};