Leetcode brush the daily problem and the next problem of the daily problem notes 22/30

Writing in the front

This is the 22nd day of my participation in Gwen Challenge

About to graduate, only to find himself in the interview algorithm hanging hammer. There is no way to zero based identity and classmates to join the force buckle brush problem army. My classmates are very good, they are usually just modest, verbally said that they will not, and I really will not… Nuggets encourage new people to blog every day, I also join in a lively, record every day brush the first two questions, these two questions I do. I plan to brush five questions every day. For the other questions, I can only memorize the routine by force and will not post them in my blog.

I am really just a vegetable chicken, what do not want to solve the problem from my reference, coding habits also need to improve, if you want to find brush problem master ask questions, I think it is better to go to the palace water sanye brush problem diary this big guy. I try not to see the solution of the problem before I make it, so as not to collide with the content of the big guy.

In addition, I also hope to have the leisure of the big guy to provide some higher clear problem-solving ideas to me, welcome to discuss ha!

Good nonsense does not say to begin 22 days of the first two questions!

2021.6.22 One question of the day

The sword refers to Offer 38. Arrangement of strings

And the way you can learn from this problem is by backtracking, just trying to see if that’s right, no so let’s take a step back and look at the other possible branches. When you talk about backtracking, someone talks about depth-first search of a tree structure, and it’s the same thing.

Because we’re going to take a step back, we’re going to have to find a place where we can go back. Our goal is to find all permutations that do not repeat, so for repeated characters in the original string, one is to hash, and two is to specify backtracking conditions. Specifies that repeated characters are all traced back to one location. The rules implied in a word, these repetitive characters to put a piece of, or back when the will is a mess (back of the “try” this step must be to take element string in character in turn to try, if there are no into a repetition of characters, then back when can’t ensure that the repeated character all back to a position, can hand a push, In this case, backtracking is to go back to the second occurrence of the repeated character, the third occurrence, and the NTH occurrence, and then gradually backtrack to the first occurrence of the repeated character, which is not what I said. This reminds me of the recent Episode of Loki, in which the Time Management Bureau erases branches of the timeline. I want all the rocky disturbance caused by branch, want to find it out these branches in the first, don’t in time order sorting, but according to the time of trigger branch names in alphabetical order, a direct result of the rocky branch put together, the time line for his trouble for the first time back directly back to the direct cause of the branches, other branches will disappear naturally. (It may not be a good example, but if it has an emotional resonance, my purpose is achieved.)

So let’s write some code

class Solution {
public:
    vector<string> rec;
    vector<int> vis;
    void backtrack(const string& s, int i, int n, string& perm) {
        if (i == n) {
            rec.push_back(perm);
            return;
        }
        for (int j = 0; j < n; j++) {
            if (vis[j] || (j > 0 && !vis[j - 1] && s[j - 1] == s[j])) {
                continue;
            }
            vis[j] = true;
            perm.push_back(s[j]);
            backtrack(s, i + 1, n, perm);
            perm.pop_back(a); vis[j] =false; }}vector<string> permutation(string s) {
        int n = s.size(a); vis.resize(n);
        sort(s.begin(), s.end());
        string perm;
        backtrack(s, 0, n, perm);
        returnrec; }};Copy the code

In the code, REC records all non-repeating permutations and VIS records all traceable positions. Inside the processing technique of characters is sorted first, sort (s.b do v.begin (), s.e nd ()) the repeated characters together, don’t appear to repeat characters in back after the second third time n times back above, handling code is the if (vis) [j] | | (j > 0 &&! vis[j – 1] && s[j – 1] == s[j])) { continue; }, which means that this position j just saw, it can’t be said to be a point that can be traced back; Or j is somewhere in the middle, it can’t go back to the previous position, and then it repeats itself, so it can’t go back to the previous position.

After the repetitive character processing logic is written, the idea of depth-first search is to try it, and then backtrack.

Take a look at it in action:

There’s another very easy way to write this problem in C++ :

class Solution {
public:
    vector<string> permutation(string s) {
        sort(s.begin(), s.end());
        vector<string> ans;
        do ans.push_back(s);
        while (next_permutation(s.begin(), s.end()));
        returnans; }};Copy the code

One of the following questions per day

1608. Eigenvalues of a special array

What it does is it takes an array, it outputs a number x, and there are x numbers in the array that are greater than x. If you can’t find it, print -1.

Find the prefix sum, which I should call the suffix sum here, because I’m going backwards through the possible x’s, and the code is as follows

class Solution {
public:
    int specialArray(vector<int>& nums) {
        int n = nums.size(a);vector<int> cnt(n + 1);
        for (int num : nums)
            cnt[min(num, n)]++;
        for (int i = n; i >= 0; i--) {
            if (i < n)
                cnt[i] += cnt[i + 1];
            if (cnt[i] == i)
                return i;
        }
        return - 1; }};Copy the code

summary

The backtracking method is used to find all permutations, and the backtracking conditions should be stipulated to prevent repetition.

Suffix and find a special value for a special array.

Refer to the link

There is no