Tag Archives: leetcode

[leetcode] 926. Flip string to monotone increasing problem solving report (Python)


personal blog: http://fuxuemingzhu.cn/

directory
Prefix calculates dynamic programming. The Prefix calculates dynamic programming
Reference Date

Title address: https://leetcode.com/problems/flip-string-to-monotone-increasing/description/
Topic describes
A string of '0's and '1's is monotone increasing if it consists of some number of '0's (possibly 0), followed by some number of '1's (also possibly 0.)
We are given a string S of '0's and '1's, and we may flip any '0' to a '1' or a '1' to a '0'.
Return the minimum number of flips to make S monotone increasing.
Example 1:

Input: "00110"
Output: 1
Explanation: We flip the last digit to get 00111.

Example 2:

Input: "010110"
Output: 2
Explanation: We flip to get 011111, or alternatively 000111.

Example 3:

Input: "00011000"
Output: 2
Explanation: We flip to get 00000000.

Note:

    1 < = S.length < = 20000S only strings of ‘0’ and ‘1’ characters.

Subject to
A string has a 0 and a 1. Ask at least how many characters to flip to make the string program a monotonically increasing string.
The problem solving method
The Prefix calculation
The second problem of the week, this problem is still a little difficult to think about.
As a general rule, we use the Prefix array to store how many 1s precede each location. Because our ultimate goal is to become a string with a 0 and a 1 in front of it, so we can go through the array, and we’re going to go through all the positions that we’re going through, and we’re going to have to count how many ones we have in front of each position plus how many zeros we have after each position. Because the first 1 has to be flipped to 0, and the second 0 has to be flipped to 1.
Anyway, you just have to figure out how many ones are in front of each position, and then, again, you have to minimize the sum of the ones in front of each position and the zeros after each position.
The P array is used to hold the first 1 of each position. So the number of zeros is going to be the total number of zeros (that is, the total number minus the total number of ones) minus the number of zeros (that is, the current position index minus the number of ones).
It’s order N in time, order N in space.

class Solution(object):
    def minFlipsMonoIncr(self, S):
        """
        :type S: str
        :rtype: int
        """
        N = len(S)
        P = [0] # how many ones
        res = float('inf')
        for s in S:
            P.append(P[-1] + int(s))
        return min(P[i] + (N - P[-1]) - (i - P[i]) for i in range(len(P)))

Dynamic programming
The master on the other side of the station came up with the method, I feel inferior ah, look for a long time to consult to be able to figure it out reluctantly.
This is a bit like buying and selling stocks, both using a two-dimensional dp array that holds the minimum number of times a string ending in 0 or 1 needs to be flipped.
For convenience, I’ve added a space to the DP array, which means that I don’t have to do any flipping before the first string has even started.
So, when we traverse to the I position of the string:

    if the character in this position is '0', then:

The current dp array ending in 0 is equal to the previous DP ending in 0, that is, there is no need to do any operation, at this time, the previous dp must end in 0; The current dp array ending in 1 is equal to Min(the previous dp + 1 ending in 0, the previous DP + 1). The idea here is that there’s a situation where you end up with the previous 0 and you flip the current 0 to 1; The other case is if the previous digit ends in a 1 and the current 0 is flipped to a 1. We need to minimize these two cases. You can end it with either a 0 or a 1.

    if the character in this position is '1', then:

The current dp array ending in 0 is equal to the previous DP ending in 0 + 1, that is, the current 1 is flipped to 0, at this time, the previous one can only end in 0; The current dp array ending in 1 is equal to Min(dp ending in 0, dp ending in 1). So what that means is how many times do I have to flip this position over to end in 1?Of course, it’s the minimum number of times you can flip a 0 or a 1, because you don’t have to flip the 1, but you can flip the 1 anyway. You can end it with either a 0 or a 1.
To sum up, it is important to understand that dp array is the number of states ending in this second dimension number. For example, DP [I][0] is the number of states that need to be flipped if the ith number ends in 0. And then, the thing to understand is that if we’re traversing this character there’s no limit to whether we’re going to flip it or not, so whether we flip it or not we have to take into account how the DP is going to update when this position becomes either 1 or 0. The way to update is to look at the previous state, the previous state to the current state, what you need to do, and how many flips you have.
It’s order N in time, order N in space.

class Solution(object):
    def minFlipsMonoIncr(self, S):
        """
        :type S: str
        :rtype: int
        """
        N = len(S)
        dp = [[0] * 2 for _ in range(N + 1)]
        for i in range(1, N + 1):
            if S[i - 1] == '0':
                dp[i][0] = dp[i - 1][0]
                dp[i][1] = min(dp[i - 1][1], dp[i - 1][0]) + 1
            else:
                dp[i][0] = dp[i - 1][0] + 1
                dp[i][1] = min(dp[i - 1][1], dp[i - 1][0])
        return min(dp[N][0], dp[N][1])

Obviously, in the above approach, each DP shift is only related to the previous state, so you can optimize the spatial complexity to O(1). The code is as follows:

class Solution(object):
    def minFlipsMonoIncr(self, S):
        """
        :type S: str
        :rtype: int
        """
        N = len(S)
        dp = [0] * 2
        for i in range(1, N + 1):
            if S[i - 1] == '0':
                dp[0] = dp[0]
                dp[1] = min(dp[1], dp[0]) + 1
            else:
                dp[1] = min(dp[1], dp[0])
                dp[0] = dp[0] + 1
        return min(dp[0], dp[1])

The resources
https://leetcode.com/problems/flip-string-to-monotone-increasing/discuss/183859/Java-DP-using-O(N)-time-and-O(1)-space
The date of
October 21, 2018 — This week’s race is a bit difficult

Leetcode: 7. Reverse Integer(JAVA)

【 Problem Description 】

Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321
click to show spoilers.

[thinking]
This problem seems simple, but there are more pits.
Integer inversion is a simple problem, but overflow needs to be dealt with.
Save the result as a long, returning 0 if it is greater than the integer maximum or less than the negative minimum
[code]

public class Solution {
    public int reverse(int x) {
		if (x == 0) {
			return 0;
		}

		int sign = 1;
		if (x < 0) {
			sign = -1;
		}
		long result = 0;
		long t = Math.abs((long) x);

		while (t != 0) {
			result = result * 10 + t % 10;
			;
			t /= 10;
		}

		if ((sign == 1 && result > Integer.MAX_VALUE)
				|| (sign == -1 && sign * result < Integer.MIN_VALUE)) {
			return 0;
		}
		return sign * (int) result;
    }
}

7. Reverse Integer [easy] (Python)

Topic link
https://leetcode.com/problems/reverse-integer/
The questions in the original

Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321

The title translation
Reverses the number in an integer.
example 1: given x=123, return 321; Example 2: Given x=-123, return -321.

If x is equal to 10 or x is equal to 100, then both returns 1. 2. What happens to overflow after the original integer is reversed?– For example, if x=1000000003, reverse overflow, then the specified overflow results will return 0.
Thinking method
Here, Python’s handling of integers doesn’t actively overflow and actually causes problems, requiring special handling.
Thinking a
Loop through the modulus of 10 to get the tail number, step by step multiply 10 to construct a new flipped integer. However, it is important to first judge the positive and negative of the original number, and finally judge whether the result is overflow.
code

class Solution(object):
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        flag = 1 if x >= 0 else -1
        new_x, x = 0, abs(x)
        while x:
            new_x = 10 * new_x + x % 10
            x /= 10
        new_x = flag * new_x
        return new_x if new_x < 2147483648 and new_x >= -2147483648 else 0

Idea 2
Python string reversal is used to reverse an integer, and the reversed string is converted back to an integer. As above, pay attention to positive and negative and overflow situations.
code

class Solution(object):
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        x = int(str(x)[::-1]) if x >= 0 else - int(str(-x)[::-1])
        return x if x < 2147483648 and x >= -2147483648 else 0

PS: The novice brush LeetCode, the new handwriting blog, write wrong or write unclear please help point out, thank you!
reprint please indicate the: http://blog.csdn.net/coder_orz/article/details/52039990

43. Implementation of the shortest code of multiply strings | Java

43.multiply Strings

[thinking]
The exact multiplication of large Numbers tests the bitwise operation of strings. The result is cached in an int array. The advantage of using an int array is that the value of each int can be greater than 10:

    public String multiply(String num1, String num2) {
        int len1 = num1.length(), len2 = num2.length(), len = len1 + len2, count = 0;
        int[] arr = new int[len];
        for (int i = len1 - 1; i >= 0; i--) {
            int bit1 = num1.charAt(i) - '0';
            for (int j = len2 - 1, k = j + i + 1; j >= 0; j--, k--) {
                int temp = bit1 * (num2.charAt(j) - '0') + arr[k];
                arr[k] = temp % 10;
                arr[k - 1] += temp/10;
            }
        }
        String s = "";
        for (int i = 0; i < arr.length; i++)
            s += arr[i];
        while(count < len && s.charAt(count++) == '0');
        return s.substring(count - 1);
    }

311/311
13 Ms Your Runtime beats 29.13 per cent of javasubmissions.

Of course, I laughed when I saw something simple and funny on the Internet:

    public String multiply(String num1, String num2) {
        return new BigInteger(num1).multiply(new BigInteger(num2)) + "";
    }

Of course, this method doesn’t work. It’s designed to make people laugh.

Welcome to optimize!

206. Reverse Linked List [easy] (Python)

Topic link
https://leetcode.com/problems/reverse-linked-list/
The questions in the original

Reverse a singly linked list.

The title translation
Flip a one-way linked list
Thinking method
This topic is relatively basic, and there are many solutions to it, and there are also many solutions to AC. Here, only part of the ideas are sorted out for reference.
Thinking a
Using the stack structure, the contents of the linked list can be pushed onto the stack in turn, and then ejected from the stack in turn to construct the reverse order. The following code emulates the stack with ordinary arrays.
code

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        p = head
        newList = []
        while p:
            newList.insert(0, p.val)
            p = p.next

        p = head
        for v in newList:
            p.val = v
            p = p.next
        return head

Idea 2
Similar to the idea of a stack, but directly in the original linked list operation, by iterating the node reorganization, the previous node moved to the back of the reorganized list. It’s actually an upside-down operation.
code

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        new_head = None
        while head:
            p = head
            head = head.next
            p.next = new_head
            new_head = p
        return new_head

Thought three
Recursion. Notice the termination condition
code

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head

        p = head.next
        n = self.reverseList(p)

        head.next = None
        p.next = head
        return n

PS: The novice brush LeetCode, the new handwriting blog, write wrong or write unclear please help point out, thank you!
reprint please indicate the: http://blog.csdn.net/coder_orz/article/details/51306170

ISO C++ forbids comparison between pointer and integer [-fpermissive]

Today, when using C++ to brush the problem, encountered this problem, blame their own carelessness.

When determining whether a character pointer points to the end of a string, the character ‘\0’ is written as a comparison error raised by ‘\0’, which in comparison represents the address of the string ‘\0’.
One thing to note from this is that string comparisons in C++ are best done with STRCMP.

error:control reaches end of non-void function [-Werror=return-type]

Description of problem scenario: Leetcode encountered this kind of error when scanning the question, the code was no problem, but the compilation failed, it was very suspicious of life.
problem solved: add a return statement at the end of the function, as long as the return data type pair! Remember, always return, even if you never need it.
although sometimes we have a return in the same program, but not at the end of the code, leetCode will not compile.
So we also have to return at the end of the function block. When this error occurs, LeetCode usually has a red highlight on the last line of the function block.
(Although I thought of adding the return value, I silently said to myself that it was clearly written in the middle, but there is no use in adding here…)
As shown in figure:

Common causes of Leetcode Runtime Error

The general reason is that it’s not initialized, it’s running as a random number;
Or it returns a wild pointer, which is common in test cases with empty sets and requires a pointer to be returned. Most of the time, it will be like this without attention:

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        TreeNode *result;
        if(preorder.size() == 0 && inorder.size() == 0)
            return result;
        else
            return sub_bT(0, preorder.size()-1, 0, inorder.size()-1, preorder, inorder); 

    }

At this time, we often think that a null pointer is returned, but in fact, it is not initialized. What is returned is a wild pointer, which does not know where to point to. However, when we Run Code, no error will be reported and the result is [], so we think that a null pointer is returned.

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        TreeNode *result(NULL);
        if(preorder.size() == 0 && inorder.size() == 0)
            return result;
        else
            return sub_bT(0, preorder.size()-1, 0, inorder.size()-1, preorder, inorder); 

    }

Leetcode 34 finds the first and last position of an element in the sorted array (medium)

given an ascending array of integers nums, and a target value target. Find the starting and ending positions in the array for the given target value.

your algorithm’s time complexity must be O(log n).

if there is no target value in the array, return [-1, -1].

example 1 :

enter : nums =,7,7,8,8,10 [5], target = 8
output: [3, 4]

sample 2 :

enter : nums =,7,7,8,8,10 [5], target = 6
output: [1, 1]

thought and code

O(log n) is the complexity of 

class Solution {
    public int[] searchRange(int[] nums, int target) {

        int[] res = new int[] {-1, -1};

        if (nums.length < 1) return res;

        int firstIndex = search(nums, target - 1);
        
        // 如果大于target-1 的第一个索引就超级界 或者 第一个索引的值不是target 那么就说明当前数组没有目标值
        if (firstIndex == nums.length || nums[firstIndex] != target) return res;
        else res[0] = firstIndex;
		
        res[1] = search(nums, target) - 1;

        return res;    
    }

    public int search(int[] nums, int target) {
        // 找到大于target值的第一个位置
        int l = 0, r = nums.length;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (target >= nums[m]) l = m + 1;
            else r = m;
        }
        return l;
    }
}

[leetcode] zigzag transformation

z-sorts a given string from top to bottom, left to right, based on the number of rows given. For example, if the input string is “LEETCODEISHIRING” and the number of lines is 3, list it like this:

L C I R
E T O E S I I G
E D H N

After

, your output needs to be read line by line from left to right to produce a new string, such as “LCIRETOESIIGEDHN”.
:
string convert(string s, int numRows);

  • example 1:
    input: s = “LEETCODEISHIRING”, numRows = 3
    output: “LCIRETOESIIGEDHN”

  • example 2:
    input: s = “LEETCODEISHIRING”, numRows = 4
    0 output: “LDREOEIIECIHNTSG”
    interpretation :
    LDR
    EOEII
    ECIHN
    TSG

Source:

button force (LeetCode)
link: https://leetcode-cn.com/problems/zigzag-conversion

train of thought (have a reference problem solution)

  • the first idea is to establish a two-dimensional array, violence will character in order fill in the
  • set a says going in the direction of variables, when the z glyph to the first line/change direction when the last line
  • dir represents a string array of rows, according to which line going to judge the next character is inserted into the
  • finally connect string array all, become a string

    code 

    class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows==1)
        {
            return s;
        }
        int n=s.length();
        vector<string> rows(min(n,numRows));
        
        int dir=0;
        bool going=false;
        for(char c : s)
        {
            rows[dir]+=c;
            if(dir==0 || dir==numRows-1) going=!going;
            dir+=going?1:-1;
        }

        string a;
        for(string x:rows) 
        {
            a+=x;
        }
        return a;
    }
};

    summary

    • get a new method of traversing strings, but also understand the string connection