发表更新LeetCode / 算法22 分钟读完 (大约3351个字)

LeetCode-25

[hard] 1377. T 秒后青蛙的位置

题目分析

题目强调为一颗无向树，每次访问未访问过的节点。也就是说，每秒若有子节点，则跳到子节点，否则呆在原地不动。

也就是根据题目构造一棵根节点为1的树，并按照层次遍历该树即可。但是题目输入的边并不一定以1为根节点。

代码

阅读更多
发表更新LeetCode / 算法11 分钟读完 (大约1601个字)

LeetCode-24

1616. 分割两个字符串得到回文串

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    bool checkPalindromeFormation(string a, string b) {
        int len = a.length();
        if(len == 1) return true;
        bool flaga = true, flagb = true;
        int i = 0;
        for(; i < len; i++) {
            if(a[i] == b[len-1-i]) {
            } else {
                break;
            }
        }
        for(int j = i; j < len-1-i; j++) {
            if(b[j] != b[len-1-j]) {
                flagb = false;
                break;
            }
        }
        for(int j = i; j < len-1-i; j++) {
            if(a[j] != a[len-1-j]) {
                flaga = false;
                break;
            }
        }
        if(flaga || flagb) return true;
        flaga = flagb = true;
        for(i = 0; i < len; i++) {
            if(a[len-1-i] == b[i]) {
            } else {
                break;
            }
        }
        for(int j = i; j < len-1-i; j++) {
            if(a[j] != a[len-1-j]) {
                flaga = false;
                break;
            }
        }
        for(int j = i; j < len-1-i; j++) {
            if(b[j] != b[len-1-j]) {
                flagb = false;
                break;
            }
        }
        return flaga || flagb;
    }
};

ab两个字符串在同一个位置分隔开，若 $ pre_a + suf_b $ 或 $ pre_b + suf_a $ 是回文串，则返回true，否则返回false
这个规则相当于ab截取相同且任意长的前缀并交换，看交换后是否存在回文
我的思路是先比较a的第i位与b的倒数第i位是否想等，找到第一次不相等的位置i，此时可以从第i位分割，判断b的剩余部分是否是回文，或者从len-i-1处分割，判断a的剩余部分是否是回文
若都不是，再比较b的第i位与a的倒数i位，找到第一个不满足的i，再比较a，b的剩余部分

优化行数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool checkPalindromeFormation(string a, string b) {
        int len = a.length();
        int paliA = len/2-1, paliB = len/2;
        while(paliA > 0 && a[paliA] == a[len-1-paliA]) paliA--;
        while(paliB > 0 && b[paliB] == b[len-1-paliB]) paliB--;
        int i, j;
        for(i = 0; i < len/2; i++) {
            if(a[i] != b[len-1-i]) {
                break;
            }
        }
        
        for(j = 0; j < len/2; j++) {
            if(b[j] != a[len-1-j]) {
                break;
            }
        }
        return min(paliA, paliB) < max(i, j);
    }
};
阅读更多
发表更新LeetCode / 算法12 分钟读完 (大约1759个字)

LeetCode-23

1144. 递减元素使数组呈锯齿状

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int movesToMakeZigzag(vector<int>& nums) {
        int odd2less, even2less;
        odd2less = even2less = 0;
        int n = nums.size();
        if(n <= 1) return 0;
        for(int i = 1; i < n - 1; i++) {
            if(i%2 == 0) {
                if(nums[i] >= min(nums[i-1], nums[i+1])) {
                    even2less += nums[i] - min(nums[i-1], nums[i+1]) + 1;
                }
            } else {
                if(nums[i] >= min(nums[i-1], nums[i+1])) {
                    odd2less += nums[i] - min(nums[i-1], nums[i+1]) + 1;
                }
            }
        }
        if(nums[0] >= nums[1]) {
            even2less += nums[0] - nums[1] + 1;
        }
        if(nums[n-1] >= nums[n-2]) {
            if((n-1)%2 == 0) {
                even2less += nums[n-1] - nums[n-2] + 1;
            } else {
                odd2less += nums[n-1] - nums[n-2] + 1;
            }
        }
        return min(even2less, odd2less);

    }
};

遍历所有奇数，使其小于两端，记录操作数1
遍历所有偶数，使其小于两端，记录操作数2
返回最小值

优化代码行数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int movesToMakeZigzag(vector<int>& nums) {
        int op[2] = {0}, n = nums.size();
        if(n <= 1) return 0;
        for(int i = 1; i < n - 1; i++) {
            if(nums[i] >= min(nums[i-1], nums[i+1]))
                op[i&1] += nums[i] - min(nums[i-1], nums[i+1]) + 1;
        }
        if(nums[0] >= nums[1]) {
            op[0] += nums[0] - nums[1] + 1;
        }
        if(nums[n-1] >= nums[n-2]) {
            op[(n-1)&1] += nums[n-1] - nums[n-2] + 1;
        } 
        return min(op[0], op[1]);
    }
};

2325. 解密消息

阅读更多
发表更新LeetCode / 算法26 分钟读完 (大约3955个字)

LeetCode-22

2347. 最好的扑克手牌

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    string bestHand(vector<int>& ranks, vector<char>& suits) {
        vector<int> rank_count(13, 0), suits_count(4, 0);
        for(int i = 0; i < 5; i++) {
            rank_count[ranks[i]-1]++;
            suits_count[suits[i] - 'a']++;
        }
        int count = 0;
        for(int i = 0; i < 4; i++) {
            count = max(count, suits_count[i]);
        }
        if(count == 5) return "Flush";
        count = 0;
        for(int i = 0; i < 13; i++) {
            count = max(count, rank_count[i]);
        }
        if(count >= 3) {
            return "Three of a Kind";
        } else if (count == 2) {
            return "Pair";
        }
        return "High Card";
    }
};

1604. 警告一小时内使用相同员工卡大于等于三次的人

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<string> alertNames(vector<string>& keyName, vector<string>& keyTime) {
        map<string, vector<int>> hour_count;
        int len = keyName.size();
        for(int i = 0; i < len; i++) {
            int h = (keyTime[i][0]-'0')*10 + keyTime[i][1] - '0', m = (keyTime[i][3] - '0') * 10 + keyTime[i][4] - '0';
            hour_count[keyName[i]].push_back(h*60+m);
        }
        vector<string> warning_list;
        for(auto ite = hour_count.begin(); ite != hour_count.end(); ite++) {
            bool warn = false;
            sort(ite->second.begin(), ite->second.end());
            int len = ite->second.size();
            for(int i = 0; i < len-2; i++) {
                if(ite->second[i+2] - ite->second[i] <= 60) {
                    warn = true;
                    break;
                }
            }
            if(warn) {
                warning_list.push_back(ite->first);
            }
        }
        return warning_list;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    vector<string> alertNames(vector<string>& keyName, vector<string>& keyTime) {
        map<string, priority_queue<int>> hour_count;
        int len = keyName.size();
        for(int i = 0; i < len; i++) {
            int h = (keyTime[i][0]-'0')*10 + keyTime[i][1] - '0', m = (keyTime[i][3] - '0') * 10 + keyTime[i][4] - '0';
            hour_count[keyName[i]].push(h*60+m);
        }
        vector<string> warning_list;
        for(auto ite = hour_count.begin(); ite != hour_count.end(); ite++) {
            int len = ite->second.size();
            if(len <= 2) continue;
            int a, b, c;
            a = ite->second.top();
            ite->second.pop();
            b = ite->second.top();
            ite->second.pop();
            c = ite->second.top();
            ite->second.pop();
            bool warn = a - c <= 60;
            while(!warn && !ite->second.empty()) {
                a = b;
                b = c;
                c = ite->second.top();
                ite->second.pop();
                warn = a - c <= 60;
            }
            if(warn) {
                warning_list.push_back(ite->first);
            }
        }
        return warning_list;
    }
};

2331. 计算布尔二叉树的值

阅读更多
发表更新LeetCode / 算法21 分钟读完 (大约3190个字)

LeetCode-21

1234. 替换子串得到平衡字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    bool isBalance(int* count, int avg) {
        return count['Q'] <= avg && count['R'] <= avg && count['E'] <= avg && count['W'] <= avg;
    }
    int balancedString(string s) {
        int count[128] = {0};
        for (char c : s) {
            count[c]++;
        }
        int len = s.length();
        int avg = len / 4;

        if (isBalance(count, avg)) {
            return 0;
        }
        int res = len;
        for (int l = 0, r = 0; l < len; l++) {
            while (r < len && !isBalance(count, avg)) {
                count[s[r]]--;
                r++;
            }
            if (!isBalance(count, avg)) {
                break;
            }
            res = min(res, r - l);
            count[s[l]]++;
        }
        return res;
    }
};

1138. 字母板上的路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    string alphabetBoardPath(string target) {
        int x = 0, y = 0;
        string res = "";
        for(char c : target) {
            int next_x = getX(c), next_y = getY(c);
            char step_x = 'L', step_y = 'U';
            int diff_x = x - next_x, diff_y = y - next_y;
            
            if(next_x > x) {
                step_x = 'R';
                diff_x = -diff_x;
            }
            if(next_y > y) {
                step_y = 'D';
                diff_y = - diff_y;
            }
            if(next_y == 5) {
                for(int i = 0; i < diff_x; i++) {
                    res += step_x;
                }
                for(int i = 0; i < diff_y; i++) {
                    res += step_y;
                }

            } else {
                for(int i = 0; i < diff_y; i++) {
                    res += step_y;
                }
                for(int i = 0; i < diff_x; i++) {
                    res += step_x;
                }
            }
            
            res += "!";
            x = next_x;
            y = next_y;
        }
        return res;
    }
    int getX(char c) {
        return (c - 'a') % 5;
    }
    int getY(char c) {
        return (c - 'a') / 5;
    }
};

如果默认先纵向走，再横向走，那么当从外部到z时，需要先横向走再纵向走
如果默认先横向走，再纵向走，那么当从z到外部时，需要先纵向走再横向走

2335. 装满杯子需要的最短总时长

阅读更多
发表更新LeetCode / 算法7 分钟读完 (大约1111个字)

LeetCode-20

1758. 生成交替二进制字符串的最少操作数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minOperations(string s) {
        int len = s.size();
        return min(cal(s, len, true), cal(s, len, false));
    }
    int cal(const string& s, int len, bool flag) {
        int count = 0;
        for(int i = 0; i < len; i++) {
            if(flag && s[i] == '0' || !flag && s[i] == '1') {
                count++;
            }
            flag = !flag;
        }
        return count;
    }
};

813. 最大平均值和的分组

超时暴搜

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int len = 0;
    vector<int> sum;
    double largestSumOfAverages(vector<int>& nums, int k) {
        len = nums.size();
        sum = vector<int>(len+1, 0);
        for(int i = 1; i <= len; i++) {
            sum[i] = nums[i-1] + sum[i-1];
        }
        return search(nums, k, 1, 1, 0, 0);
    }
    double search(vector<int>& nums, int k, int i, int K, double left_value, int last_j) {
        if(k == K || i == len) {
            return left_value + (sum[len] - sum[last_j] + 0.0) / (len - last_j);
        }
        return max(search(nums, k, i+1, K+1, left_value + (sum[i] - sum[last_j] + 0.0)/(i-last_j), i), search(nums, k,i+1, K, left_value, last_j));
    }

    double max(double a, double b) {
        return a > b ? a : b;
    }
};

昨天第一个思路是用排序，找出最大的m个数，这m个数恰好将数组分成k个部分，发现不可行。
然后暴力搜索，超时了，暴搜时考虑添加隔板，其中left_value表示当前搜索下标i之前的分组平均值

阅读更多
发表更新LeetCode / 算法3 分钟读完 (大约387个字)

LeetCode-19

1710. 卡车上的最大单元数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
        sort(boxTypes.begin(), boxTypes.end(), [](vector<int>& x, vector<int>& y)->bool {
            return x[1] > y[1];
        });
        int n = boxTypes.size();
        int ret = 0;
        for(int i = 0; i < n; i++) {
            if(truckSize) {
                ret += min(truckSize, boxTypes[i][0])*boxTypes[i][1];
                truckSize -= min(truckSize, boxTypes[i][0]);
            } else {
                break;
            }
        }
        return ret;
    }
};
// 50 + 27 + 14 = 91

简单题，排个序就行

775. 全局倒置与局部倒置

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool isIdealPermutation(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++) {
            if (abs(nums[i] - i) > 1) {
                return false;
            }
        }
        return true;
    }
};

最开始想复杂了，想用差分数组统计个数

阅读更多
发表更新LeetCode / 算法30 分钟读完 (大约4482个字)

LeetCode-dp

leetcode 101的动态规划专题

基本动态规划：一维

70. 爬楼梯

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int climbStairs(int n) {
        int a=1,b=2;
        if(n<2) return 1; 
        for(int i = 2; i <n ; i++) {
            int c = a+b;
            a=b;
            b=c;
        }
        return b;
    }
};

dp数组表示上n层楼有几种可能
转移方程是 $ dp[i] = dp[i-1] + dp[i-2] $
上到第i层有可能从第i-1层或i-2层上来，则上到i层的可能数目就是 $ dp[i-1] + dp[i-2] $
由于dp[i]只需要前两个数的数据，所以可以优化掉dp数组，用两个变量代替，节省数组空间

198. 打家劫舍

阅读更多
发表更新LeetCode / 算法23 分钟读完 (大约3439个字)

LeetCode-18

1668. 最大重复子字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    int maxRepeating(string sequence, string word) {
        int len1 = sequence.size();
        int len2 = word.size();
        int maxk = 0, k = 0;
        for(int i = 0; i < len1;) {
            bool flag = true;
            int next = i+1;
            bool flag1 = false;
            for(int j = 0; j < len2; j++) {
                if(sequence[i+j] != word[j]) {
                    flag = false;
                    break;
                }
                if(!flag1 && j != 0 && sequence[i+j] == word[0]) {
                    next = i+j;
                    flag1=true;
                }
            }
            // cout << i << " " << k << " " << maxk << endl;
            if(flag) {
                k++;
                i += len2;
            } else {
                maxk = max(k, maxk);
                if(k == 0) {
                    i+=1;
                } else {
                    i = i-len2+1;
                }
                k = 0;
            }
            // cout << i << endl;
        }
        return max(maxk, k);
    }
};

笨方法，从右向左找，适当回溯

754. 到达终点数字

解法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int reachNumber(int target) {
        target = abs(target);
        int n = (sqrt(8.0*target+1)-1)/2; //8.0,防止int溢出
        int sum = (n+1)*n/2;
        if(sum == target) {
            return n;
        }
        int diff = target-sum;
        if((n % 2 == 1 && diff % 2 == 0) || (n % 2 == 0 && diff % 2 == 1)) {
            n += 1;
        } else if(diff %2 == 1) {
            n += 2;
        } else {
            n += 3;
        }
        return n;
    }
};
阅读更多
发表更新LeetCode / 算法7 分钟读完 (大约1043个字)

LeetCode-17

1662. 检查两个字符串数组是否相等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {
        return join(move(word1)) == join(move(word2));
    }
    string join(vector<string>&& word) {
        string s;
        int len = word.size();
        if(len <= 0) return s;
        for(int i = 0; i < len-1; i++) {
            s += word[i];
        }
        s+=word[len-1];
        return s;
    }
};

实现一个join函数就好了

481. 神奇字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int magicalString(int n) {
        int bit = 3;
        int count = 1;
        bool q[100005] = {false};
        int queue_front = 0;
        int queue_rear = 0;
        bool cur=1;
        bool gen=0;
        while(bit < n) {
            bit += cur+1;
            q[queue_front++] = gen;
            if(cur) {
                q[queue_front++] = gen;
            }
            gen=1-gen;
            count+=gen?cur+gen:0;
            cur = q[queue_rear++];
        }
        return count -(bit>n && gen);
    }
};

关键在于想清楚如何生成这个神奇字符串，题目中说，s的前几个字符是12211
1生成1,s=1
2生成22，因为前一个1生成了1，这个2不能也生成1,s=122
2生成11，因为前一个2生成了2，这个2不能也生成2,s=12211
1生成2，前一个2生成了1，这个1就只能生成2了,s=122112
1生成1,s=1221121
2生成22,s=122112122

阅读更多
关注我

链接

分类

最新文章

归档

标签

6.8242
Android1
Android FrameWork1
Android 高级开发瓶颈突破系列课11
Android-官方文档1
Android-官方源码5
Android面试查漏补缺2
C/C++1
Flutter1
Java基础1
Kotlin-Android21
Kotlin-Android 实习25
LeetCode45
LeetCode 1013
LeetCode周赛1
Linux/UNIX系统编程手册38
OI KIWI2
OS4
PAT-(Advanced-Level)-Practice2
PAT-(Basic-Level)-Practice44
blockchain1
fedfab13
gallery1
geth1
git1
gradle1
hexo2
linux2
misc1
projects1
shell2
刷题2
动态规划1
多线程1
排序1
数据库2
牛客2
算法43
×