头像

小呆呆

九歌粉丝团


访客:39294

离线:9小时前



小呆呆
15小时前

算法分析

题目意思:

  • 1、day:找到第一个和第二个字符串中,第一对相同的大写字母且在['A','G']范围内的字母对应的星期几(只有7天可以选)
  • 2、hour:找到第一个和第二个字符串中,第一对相同字符且在['A','N']或者['0','9']范围内的字符对应的小时(只有023小时可以选)
  • 3、min:找到第三个和第四个字符串中,第一对相同的英文字符的位置

时间复杂度 $O(n)$

参考文献

pat

C++ 代码

#include <iostream>

using namespace std;

string days[7] = {"MON","TUE","WED","THU","FRI","SAT","SUN"};
int main()
{
    string s1,s2,s3,s4;
    cin >> s1 >> s2 >> s3 >> s4;

    //找第一个相同的大写字母
    string day;
    int hour;
    for(int i = 0;i < s1.size() && i < s2.size();i ++)
    {
        if(s1[i] >= 'A' && s1[i] <= 'G' && s1[i] == s2[i]) 
        {
            day = days[s1[i] - 'A'];
            for(int j = i + 1;j < s1.size() && j < s2.size();j ++)
            {
                if((s1[j] >= 'A' && s1[j] <= 'N' || s1[j] >= '0' && s1[j] <= '9') && s1[j] == s2[j]) 
                {
                    if(s1[j] >= '0' && s1[j] <= '9') hour = s1[j] - '0';
                    else hour = s1[j] - 'A' + 10;

                    break;
                }
            }

            break;
        }
    }
    //找第一对相同的英文字符的位置
    int idx ;
    for(int i = 0;i < s3.size() && i < s4.size();i ++)
    {
        if((s3[i] >= 'A' && s3[i] <= 'Z' || s3[i] >= 'a' && s3[i] <= 'z') && s3[i] == s4[i])
        {
            idx = i;
            break;
        }
    }
    cout << day << " " ;
    if(hour >= 10) cout << hour << ":";
    else cout << "0" << hour << ":";

    if(idx >= 10) cout << idx << endl;
    else cout << "0" << idx << endl;
    return 0;
}



小呆呆
17小时前

算法分析

哈希表

  • 1、通过指针扫描的方式将每个单词存入到哈希表中,并注意切换成小写
  • 2、枚举哈希表找出最常用词word以及其出现次数res(若次数相同,找字典序最小)

时间复杂度 $O(n)$

参考文献

pat

C++ 代码

#include <iostream>
#include <unordered_map>

using namespace std;

unordered_map<string, int> map;

bool check(char c)
{
    if(c >= 'A' && c <= 'Z') return true;
    if(c >= 'a' && c <= 'z') return true;
    if(c >= '0' && c <= '9') return true;
    return false;
}
char get(char c)
{
    if(c >= 'A' && c <= 'Z') return c + 32;
    return c;
}
int main()
{
    string s;
    getline(cin, s);

    for(int i = 0; i < s.size(); i ++ )
    {
        if(check(s[i]))
        {
            string word;
            int j = i;
            while(j < s.size() && check(s[j])) word += get(s[j ++]);

            map[word] ++;

            i = j;
        }
    }
    string word;
    int res = 0;
    for(auto item : map)
    {
        if(item.second > res || (item.second == res && item.first < word))
        {
            word = item.first;
            res = item.second;
        }
    }
    cout << word << " " << res << endl;

    return 0;
}



题目描述

桌面上有 2n 个颜色不完全相同的球,球上的颜色共有 k 种。给你一个大小为 k 的整数数组 balls ,其中 balls[i] 是颜色为 i 的球的数量。

所有的球都已经 随机打乱顺序 ,前 n 个球放入第一个盒子,后 n 个球放入另一个盒子(请认真阅读示例 2 的解释部分)。

注意:这两个盒子是不同的。例如,两个球颜色分别为 ab,盒子分别为 [](),那么 [a] (b)[b] (a) 这两种分配方式是不同的(请认真阅读示例 1 的解释部分)。

请计算「两个盒子中球的颜色数相同」的情况的概率。

样例

输入:balls = [1,1]
输出:1.00000
解释:球平均分配的方式只有两种:
- 颜色为 1 的球放入第一个盒子,颜色为 2 的球放入第二个盒子
- 颜色为 2 的球放入第一个盒子,颜色为 1 的球放入第二个盒子
这两种分配,两个盒子中球的颜色数都相同。所以概率为 2/2 = 1 。
输入:balls = [2,1,1]
输出:0.66667
解释:球的列表为 [1, 1, 2, 3]
随机打乱,得到 12 种等概率的不同打乱方案,每种方案概率为 1/12 :
[1,1 / 2,3], [1,1 / 3,2], [1,2 / 1,3], [1,2 / 3,1], [1,3 / 1,2], [1,3 / 2,1], 
[2,1 / 1,3], [2,1 / 3,1], [2,3 / 1,1], [3,1 / 1,2], [3,1 / 2,1], [3,2 / 1,1]
然后,我们将前两个球放入第一个盒子,后两个球放入第二个盒子。
这 12 种可能的随机打乱方式中的 8 种满足「两个盒子中球的颜色数相同」。
概率 = 8/12 = 0.66667
输入:balls = [1,2,1,2]
输出:0.60000
解释:球的列表为 [1, 2, 2, 3, 4, 4]。要想显示所有 180 种随机打乱方案是很难的,
但只检查「两个盒子中球的颜色数相同」的 108 种情况是比较容易的。
概率 = 108 / 180 = 0.6 。
输入:balls = [3,2,1]
输出:0.30000
解释:球的列表为 [1, 1, 1, 2, 2, 3]。要想显示所有 60 种随机打乱方案是很难的,
但只检查「两个盒子中球的颜色数相同」的 18 种情况是比较容易的。
概率 = 18 / 60 = 0.3 。
输入:balls = [6,6,6,6,6,6]
输出:0.90327

提示:

  • 1 <= balls.length <= 8
  • 1 <= balls[i] <= 6
  • sum(balls) 是偶数
  • 答案与真实值误差在 10^-5 以内,则被视为正确答案

算法分析

题目意思:给定2n个球,有k种颜色,每种颜色有balls[i]个球,随机打乱,前n个和后n个分开放在不同的两个盒子,问两个盒子中颜色数量相同(n个球x种颜色)的求占总情况的概率是多少?

可重复全排列的方案数 $\frac{S!}{a_1! a_2! … a_k!}$,其中$S = a_1 + a_2 + … + a_k$

  • 总方案数down:用上面的公式算出总方案数,S是总球数,$a_i$是i号颜色的球数
  • 合法的方案数up:由于左边的盒子每种颜色选定的球固定时,右边盒子中各颜色的球也随之固定,通过dfs枚举出左边盒子中(left[]数组)k种颜色的球各选多少个,

    • 且当选出的个数是恰好是n个时,算出左边盒子的颜色个数和右边盒子的颜色个数
    • 且当两个盒子的颜色个数相同时,可以通过上面的公式算出左边盒子的方案数x和右边盒子的方案数y,更新up = up + x * y
  • 结果:up / down

时间复杂度

Java 代码

class Solution {
    static int N = 10;
    static double[] fac = new double[50];
    static int[] balls;
    static int n,sum;
    static int[] left = new int[N];
    static int[] right = new int[N];
    static double up,down;// up表示满足要求的方案数,down表示总方案数
    static void init()
    {
        fac[0] = 1;
        for(int i = 1;i < 50;i ++) fac[i] = fac[i - 1] * i;
    }
    static double get(int[] s)
    {
        int sum = 0;
        for(int i = 0;i < n;i ++) sum += s[i];

        double res = fac[sum];
        for(int i = 0;i < n;i ++) res /= fac[s[i]];

        return res;
    }
    static void dfs(int u,int cnt)
    {
        if(u == n)
        {
            //若枚举到当前的球数是总的一半
            if(cnt == sum / 2)
            {
                //算出左边的颜色个数和右边的颜色个数
                int l = 0,r = 0;
                for(int i = 0;i < n;i ++)
                {
                    if(left[i] != 0) l ++;
                    if(right[i] != 0) r++;
                }
                if(l == r) up += get(left) * get(right);
            }
            return ;
        }
        //当前颜色的球选多少个
        for(int i = 0;i <= balls[u];i ++)
        {
            left[u] = i;
            right[u] = balls[u] - i;
            dfs(u + 1,cnt + i);
        }
    }
    public double getProbability(int[] balls) {
        n = balls.length;
        this.balls = balls;
        up = 0;
        down = 0;

        Arrays.fill(left,0);
        Arrays.fill(right,0);
        //算出总球数
        sum = 0;
        for(int i = 0;i < balls.length;i ++) sum += balls[i];
        //预处理阶乘
        init();

        dfs(0,0);

        down = get(balls);
        return up / down;
    }
}



题目描述

n 座城市,从 0n-1 编号,其间共有 n-1 条路线。因此,要想在两座不同城市之间旅行只有唯一一条路线可供选择(路线网形成一颗树)。去年,交通运输部决定重新规划路线,以改变交通拥堵的状况。

路线用 connections 表示,其中 connections[i] = [a, b] 表示从城市 ab 的一条有向路线。

今年,城市 0 将会举办一场大型比赛,很多游客都想前往城市 0

请你帮助重新规划路线方向,使每个城市都可以访问城市 0 。返回需要变更方向的最小路线数。

题目数据 保证 每个城市在重新规划路线方向后都能到达城市 0

样例

sample_1_1819.png

输入:n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
输出:3
解释:更改以红色显示的路线的方向,使每个城市都可以到达城市 0 。

sample_2_1819.png

输入:n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]
输出:2
解释:更改以红色显示的路线的方向,使每个城市都可以到达城市 0 。
输入:n = 3, connections = [[1,0],[2,0]]
输出:0

提示:

  • 2 <= n <= 5 * 10^4
  • connections.length == n-1
  • connections[i].length == 2
  • 0 <= connections[i][0], connections[i][1] <= n-1
  • connections[i][0] != connections[i][1]

算法分析

图论

题目:给定n个点,n - 1条有向边,因此两个之间只有一条有向边,为了令所有点均能达到0号点,因此需要将某些有向边a -> b,变成b -> a,问需要边多少条

  • 1、建图,建图过程中,将两个点之间建双向边,若a -> b,需要通过edge[]数组记录下来,表示该边是题目给定的
  • 2、从 0 结点开始深度遍历,枚举到u点时,u点是通过i边指向j点,若i边在edge[]数组中存在,则表示题目中u点到j点存在有向边,需要对该边调整过来,使得j -> u(因为是从0点反着走)

时间复杂度 $O(n)$

Java 代码

class Solution {
    static int N = 50010,M = 2 * N;
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int idx = 0;
    static int ans ;
    static boolean[] edge = new boolean[M];
    static void add(int a,int b)
    {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    static void dfs(int u,int father)
    {
        for(int i = h[u];i != -1;i = ne[i])
        {
            int j = e[i];
            if(j == father) continue;
            if(edge[i]) ans ++;
            dfs(j,u);
        }
    }
    public int minReorder(int n, int[][] connections) {
        Arrays.fill(h,-1);
        idx = 0;
        for(int i = 0;i < n - 1;i ++)
        {
            int a = connections[i][0];
            int b = connections[i][1];
            edge[idx] = true;
            add(a,b);
            add(b,a);
        }
        ans = 0;
        dfs(0,-1);

        return ans;
    }
}



题目描述

矩形蛋糕的高度为 h 且宽度为 w,给你两个整数数组 horizontalCutsverticalCuts,其中 horizontalCuts[i] 是从矩形蛋糕顶部到第  i 个水平切口的距离,类似地, verticalCuts[j] 是从矩形蛋糕的左侧到第 j 个竖直切口的距离。

请你按数组 horizontalCutsverticalCuts 中提供的水平和竖直位置切割后,请你找出 面积最大 的那份蛋糕,并返回其 面积 。由于答案可能是一个很大的数字,因此需要将结果对 10^9 + 7 取余后返回。

样例

leetcode_max_area_2.png

输入:h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]
输出:4 
解释:上图所示的矩阵蛋糕中,红色线表示水平和竖直方向上的切口。切割蛋糕后,绿色的那份蛋糕面积最大。

leetcode_max_area_3.png

输入:h = 5, w = 4, horizontalCuts = [3,1], verticalCuts = [1]
输出:6
解释:上图所示的矩阵蛋糕中,红色线表示水平和竖直方向上的切口。切割蛋糕后,绿色和黄色的两份蛋糕面积最大。
输入:h = 5, w = 4, horizontalCuts = [3], verticalCuts = [3]
输出:9

提示:

  • 2 <= h, w <= 10^9
  • 1 <= horizontalCuts.length < min(h, 10^5)
  • 1 <= verticalCuts.length < min(w, 10^5)
  • 1 <= horizontalCuts[i] < h
  • 1 <= verticalCuts[i] < w
  • 题目数据保证 horizontalCuts 中的所有元素各不相同
  • 题目数据保证 verticalCuts 中的所有元素各不相同

算法分析

排序 + 差分

  • 1、题目给定很多行,很多列,顺序不规则,算出某两行和某两列围成的面积的最大值
  • 2、需要将最高行(第n行)和最高列(第m列)分别加入到数组中
  • 3、对两个数组进行从小到大排序
  • 4、做差分,算出每相邻两行的距离
  • 5、对差分后的距离再一次从小到大排序,找到两数组的最大差分值a[n],b[m]
  • 6、a[n] * b[m]为答案所求

时间复杂度 $O(nlogn)$

Java 代码

class Solution {
    public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
        int n = horizontalCuts.length;
        int m = verticalCuts.length;
        int[] a = new int[n + 1];
        int[] b = new int[m + 1];
        for(int i = 0;i < n;i ++) a[i] = horizontalCuts[i];
        for(int i = 0;i < m;i ++) b[i] = verticalCuts[i];
        a[n] = h ;
        b[m] = w ;

        Arrays.sort(a);
        Arrays.sort(b);
        for(int i = n;i >= 1;i --)
        {
            a[i] = a[i] - a[i - 1];
        }
        for(int i = m;i >= 1;i --)
        {
            b[i] = b[i] - b[i - 1];
        }
        Arrays.sort(a);
        Arrays.sort(b);
        long ans = (long)a[n] * b[m] % 1000000007;
        return (int)ans;
    }
}



题目描述

给你一个整数数组 nums,请你选择数组的两个不同下标 ij,使 (nums[i]-1)*(nums[j]-1) 取得最大值。

请你计算并返回该式的最大值。

样例

输入:nums = [3,4,5,2]
输出:12 
解释:如果选择下标 i=1 和 j=2(下标从 0 开始),则可以获得最大值,
(nums[1]-1) * (nums[2]-1) = (4-1) * (5-1) = 3 * 4 = 12 。 
输入:nums = [1,5,4,5]
输出:16
解释:选择下标 i=1 和 j=3(下标从 0 开始),则可以获得最大值 (5-1)*(5-1) = 16 。
输入:nums = [3,7]
输出:12

提示:

  • 2 <= nums.length <= 500
  • 1 <= nums[i] <= 10^3

算法分析

排序

  • 通过排序找到最大和第二大,算出结果

时间复杂度 $O(nlogn)$

Java 代码

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        return (nums[n - 1] - 1) * (nums[n - 2] - 1);
    }
}



题目描述

给你一个 rows x cols 的矩阵 grid 来表示一块樱桃地。 grid 中每个格子的数字表示你能获得的樱桃数目。

你有两个机器人帮你收集樱桃,机器人 1 从左上角格子 (0,0) 出发,机器人 2 从右上角格子 (0, cols-1) 出发。

请你按照如下规则,返回两个机器人能收集的最多樱桃数目:

  • 从格子 (i,j) 出发,机器人可以移动到格子 (i+1, j-1)(i+1, j) 或者 (i+1, j+1) 。
  • 当一个机器人经过某个格子时,它会把该格子内所有的樱桃都摘走,然后这个位置会变成空格子,即没有樱桃的格子。
  • 当两个机器人同时到达同一个格子时,它们中只有一个可以摘到樱桃。
  • 两个机器人在任意时刻都不能移动到 grid 外面。
  • 两个机器人最后都要到达 grid 最底下一行。

样例

sample_1_1802.png

输入:grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
输出:24
解释:机器人 1 和机器人 2 的路径在上图中分别用绿色和蓝色表示。
机器人 1 摘的樱桃数目为 (3 + 2 + 5 + 2) = 12 。
机器人 2 摘的樱桃数目为 (1 + 5 + 5 + 1) = 12 。
樱桃总数为: 12 + 12 = 24 。

sample_2_1802.png

输入:grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
输出:28
解释:机器人 1 和机器人 2 的路径在上图中分别用绿色和蓝色表示。
机器人 1 摘的樱桃数目为 (1 + 9 + 5 + 2) = 17 。
机器人 2 摘的樱桃数目为 (1 + 3 + 4 + 3) = 11 。
樱桃总数为: 17 + 11 = 28 。
输入:grid = [[1,0,0,3],[0,0,0,3],[0,0,3,3],[9,0,3,3]]
输出:22
输入:grid = [[1,1],[1,1]]
输出:4

提示:

  • rows == grid.length
  • cols == grid[i].length
  • 2 <= rows, cols <= 70
  • 0 <= grid[i][j] <= 100

算法分析

状态表示:

f[i,j1,j2]:两个机器人从各自起点分别到达(i,j1),(i,j2)时获得的樱桃数目的最大值

状态计算:

  • 当机器人1到达(i,j1)点时,可以从(i - 1,j1 - 1),(i - 1,j1),(i - 1,j1 + 1)点走过来
  • 当机器人2到达(i,j2)点时,可以从(i - 1,j2 - 1),(i - 1,j2),(i - 1,j2 + 1)点走过来
  • 因此 f[i,j1,j2] 可以从 f[i - 1,x1,x2] 转移过来,j1 - 1<= x1 <= j1 + 1,j2 - 1<= x2 <= j2 + 1
  • 转移过程中
    • j1 == j2,表示在落在同一个地方,f[i,j1,j2] = f[i - 1,x1,x2] + grid[i,j1]
    • j1 != j2,表示在落在不同地方,f[i,j1,j2] = f[i - 1,x1,x2] + grid[i,j1] + grid[i,j2]

初始化:第0层获得的数目是一定的,即f[0][0][m - 1] = grid[0][0] + grid[0][m - 1],为了避免其他点从无效状态转移过来,若按0处理,容易造成比最优情况值还要大,导致错误,因此需要将无效状态全部赋值为负无穷大

最终值:枚举两个机器人分别落在最后一行的全部位置,算出最大值

时间复杂度 $O(9nm^2)$

Java 代码

class Solution {
    public int cherryPickup(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int[][][] f = new int[75][75][75];
        for(int i = 0;i < m;i ++)
            for(int j = 0;j < m;j ++)
                Arrays.fill(f[i][j],-0x3f3f3f3f);

        f[0][0][m - 1] = grid[0][0] + grid[0][m - 1];
        for(int i = 1;i < n;i ++)
            for(int j1 = 0;j1 < m;j1 ++)
                for(int j2 = 0;j2 < m;j2 ++)
                {
                    for(int t1 = -1;t1 <= 1;t1 ++)
                        for(int t2 = -1;t2 <= 1;t2 ++)
                        {
                            if(j1 + t1 < 0 || j1 + t1 >= m || j2 + t2 < 0 || j2 + t2 >= m) continue;
                            int value = grid[i][j1];
                            if(j1 != j2) value += grid[i][j2];
                            f[i][j1][j2] = Math.max(f[i][j1][j2],f[i - 1][j1 + t1][j2 + t2] + value);
                        }
                }

        int res = 0;
        for(int j1 = 0;j1 < m;j1 ++)
            for(int j2 = 0;j2 < m;j2 ++)
                res = Math.max(res,f[n - 1][j1][j2]);
        return res;
    }
}



题目描述

你总共需要上 n 门课,课程编号依次为 0 到 n-1 。

有的课会有直接的先修课程,比如如果想上课程 0 ,你必须先上课程 1 ,那么会以 [1,0] 数对的形式给出先修课程数对。

给你课程总数 n 和一个直接先修课程数对列表 prerequisite 和一个查询对列表 queries 。

对于每个查询对 queries[i] ,请判断 queries[i][0] 是否是 queries[i][1] 的先修课程。

请返回一个布尔值列表,列表中每个元素依次分别对应 queries 每个查询对的判断结果。

注意:如果课程 a 是课程 b 的先修课程且课程 b 是课程 c 的先修课程,那么课程 a 也是课程 c 的先修课程。

样例

graph.png

输入:n = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
输出:[false,true]
解释:课程 0 不是课程 1 的先修课程,但课程 1 是课程 0 的先修课程。
输入:n = 2, prerequisites = [], queries = [[1,0],[0,1]]
输出:[false,false]
解释:没有先修课程对,所以每门课程之间是独立的。

graph-1.png

输入:n = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
输出:[true,true]
输入:n = 3, prerequisites = [[1,0],[2,0]], queries = [[0,1],[2,0]]
输出:[false,true]
输入:n = 5, prerequisites = [[0,1],[1,2],[2,3],[3,4]], queries = [[0,4],[4,0],[1,3],[3,0]]
输出:[true,false,true,false]

提示:

  • 2 <= n <= 100
  • 0 <= prerequisite.length <= (n * (n - 1) / 2)
  • 0 <= prerequisite[i][0], prerequisite[i][1] < n
  • prerequisite[i][0] != prerequisite[i][1]
  • 先修课程图中没有环。
  • 先修课程图中没有重复的边。
  • 1 <= queries.length <= 10^4
  • queries[i][0] != queries[i][1]

算法分析

floyd解决传递闭包问题,核心思想:i --> kk --> j,则i -- > j

  • 1、对课与课之间关系的二维数组跑一遍floyd,得到每个课与其他课的先后顺序
  • 2、枚举queries数组,判断 a = queries[i][0] 是否是 b = queries[i][1] 的先修课程,若dist[a][b] == 1则表示是,否则表示不是

时间复杂度 $O(n^3)$

Java 代码

class Solution {
    public List<Boolean> checkIfPrerequisite(int n, int[][] prerequisites, int[][] queries) {
        List<Boolean> ans = new ArrayList<Boolean>();
        int[][] dist = new int[110][110];
        for(int i = 0;i < prerequisites.length;i ++)
        {
            int x = prerequisites[i][0];
            int y = prerequisites[i][1];
            dist[x][y] = 1;
        }
        for(int k = 0;k < n;k ++)
            for(int i = 0;i < n;i ++)
                for(int j = 0;j < n;j ++)
                    if(dist[i][k] == 1 && dist[k][j] == 1)
                        dist[i][j] = 1;

        for(int i = 0;i < queries.length;i ++)
        {
            int x = queries[i][0];
            int y = queries[i][1];
            ans.add(dist[x][y] == 1);
        }
        return ans;
    }
}



题目描述

给你一个二进制字符串 s 和一个整数 k

如果所有长度为 k 的二进制字符串都是 s 的子串,请返回 True ,否则请返回 False

样例

输入:s = "00110110", k = 2
输出:true
解释:长度为 2 的二进制串包括 "00","01","10" 和 "11"。
它们分别是 s 中下标为 0,1,3,2 开始的长度为 2 的子串。
输入:s = "00110", k = 2
输出:true
输入:s = "0110", k = 1
输出:true
解释:长度为 1 的二进制串包括 "0" 和 "1",显然它们都是 s 的子串。
输入:s = "0110", k = 2
输出:false
解释:长度为 2 的二进制串 "00" 没有出现在 s 中。
输入:s = "0000000001011100", k = 4
输出:false

提示:

  • 1 <= s.length <= 5 * 10^5
  • s 中只含 01
  • 1 <= k <= 20

算法分析

  • 1、将字符串中长度是 k 的字符段对应的十进制整数存在Set
  • 2、从 0 枚举到 1 << k 的整数,即长度为 K 的二进制子串,判断是否所有整数都在Set中存在过,若均存在返回true,否则返回false

时间复杂度 $O(n + 2^k)$

n表示字符串长度,k表示二进制子串长度

Java 代码

class Solution {
    static int get(String t)
    {
        int res = 0;
        int k = 1;
        for(int i = t.length() - 1;i >= 0;i --)
        {
            if(t.charAt(i) == '1') res += k;
            k <<= 1; 
        }
        return res;
    }
    public boolean hasAllCodes(String s, int k) {
        HashSet<Integer> set = new HashSet<Integer>();
        for(int i = 0;i + k <= s.length();i ++)
        {
            String t = s.substring(i,i + k);
            set.add(get(t));
        }
        for(int i = 0;i < 1 << k;i ++)
        {
            if(!set.contains(i)) return false;
        }
        return true;
    }
}



题目描述

给你两个长度相同的整数数组 target 和 arr 。

每一步中,你可以选择 arr 的任意 非空子数组 并将它翻转。你可以执行此过程任意次。

如果你能让 arr 变得与 target 相同,返回 True;否则,返回 False 。

样例

输入:target = [1,2,3,4], arr = [2,4,1,3]
输出:true
解释:你可以按照如下步骤使 arr 变成 target:
1- 翻转子数组 [2,4,1] ,arr 变成 [1,4,2,3]
2- 翻转子数组 [4,2] ,arr 变成 [1,2,4,3]
3- 翻转子数组 [4,3] ,arr 变成 [1,2,3,4]
上述方法并不是唯一的,还存在多种将 arr 变成 target 的方法。
输入:target = [7], arr = [7]
输出:true
解释:arr 不需要做任何翻转已经与 target 相等。
输入:target = [1,12], arr = [12,1]
输出:true
输入:target = [3,7,9], arr = [3,7,11]
输出:false
解释:arr 没有数字 9 ,所以无论如何也无法变成 target 。
输入:target = [1,1,1,1,1], arr = [1,1,1,1,1]
输出:true

提示:

  • target.length == arr.length
  • 1 <= target.length <= 1000
  • 1 <= target[i] <= 1000
  • 1 <= arr[i] <= 1000

算法分析

排序

  • 可以多次将任意非空子数组进行翻转 等价于 在数组中可以多次任意交换两个数的位置,将原数组变成目标数组 等价于 判断两个数组所有的元素对应的个数是否都相同

将两个数组从小到大排序,从左到右枚举每个数,若所有元素都相等,则返回true,否则返回false

时间复杂度 $O(nlogn)$

Java 代码

class Solution {
    public boolean canBeEqual(int[] target, int[] arr) {
        Arrays.sort(target);
        Arrays.sort(arr);
        for(int i = 0;i < target.length;i ++)
        {
            if(target[i] != arr[i]) return false; 
        }
        return true;
    }
}