LeetCode

LeetCode: Dynamic Programming (3) Originally published in Chinese on 2019-07-01; this English edition preserves the original scope and technical context. Title 6. String related 712 Minimum ASCII delete sum for two strings Given two strings, calculate the minimum sum of the ASCII values of the characters that need to be removed to make the two strings identical. For the characters s1[i] and s2[j] in the two strings, if s1[i] == s2[j], then neither character needs to be deleted, so dp[i][j] = dp[i - 1][j - 1], otherwise at least one should be deleted, taking the minimum of the two, the state transition equation is dp[i][j] = min(dp[i - 1][j] + s1[i], dp[i][j - 1] + s2[j]). The time complexity is O(m * n) and the space complexity is O(m * n). ...

LeetCode: Dynamic Programming (2) Originally published in Chinese on 2019-06-28; this English edition preserves the original scope and technical context. Title 3. Array related 300 Longest Increasing Subsequence Find the length of the longest ascending subsequence in an unordered array. Use an array dp[i] to represent the longest rising subsequence up to the i-th number, and traverse each number j before i each time. If nums[i] > nums[j], then j and i can form a rising subsequence, and let dp[i] = max(dp[i], dp[j] + 1) to get the longest rising subsequence. ...

LeetCode: Dynamic Programming (1) Originally published in Chinese on 2019-06-26; this English edition preserves the original scope and technical context. Title 1. Number related 263 ugly number Determine whether a number num is an ugly number. The general method is to find the first number greater than or equal to num from bottom to top to determine whether num is an ugly number. But this question has already given the number num, and the result can be obtained directly through modular operation. ...

LeetCode: Binary Search Originally published in Chinese on 2019-06-23; this English edition preserves the original scope and technical context. Binary search can find qualified values in an ordered array with high efficiency. The time complexity is O(logN) and the space complexity is O(1). Easy to make mistakes How to calculate the intermediate value k = i + (j - i) / 2 k = (i + j) / 2 The second method will generally cause integer data to overflow, so only the first method is used. ...

LeetCode: Bit Manipulation Originally published in Chinese on 2019-06-19; this English edition preserves the original scope and technical context. Bit operations include: with & or | XOR ^ Negation ~ Move left « Move right » Tips Shift operation x « 1: arithmetic left shift All bits in the binary representation of a number are shifted one position to the left, which is equivalent to multiplying by 2 pad 0 on the right x » 1: arithmetic right shift All bits in the binary representation of a number are shifted one position to the right, which is equivalent to dividing by 2 Complement the sign bit on the left, that is, complement 0 for positive numbers, and complement 1 for negative numbers (based on the two’s complement code) negative shift Negative numbers are stored in the form of two’s complement. When a negative number is shifted to the right, it needs to be inverted and converted into its complement, plus one to convert it into its complement, then moved to the right one bit to get a new complement, then subtracted by one to get a new one’s complement, and then inverted and converted into the original code to get the result. For example, the binary representation of -7 is 10000111 (because 32 bits are too long, so an 8-bit int is used here), its complement is 11111000, and its complement is 11111001. Moving one position to the right is 11111100, and subtracting one gets the new complement 11111011. The original code is 10000100, that is -4; shifting the complement one bit to the left is 11110010, subtracting one to get the new complement 11110001, the original code is 10001110, which is -14 A simpler way to understand is to multiply left shift by 2 and right shift by 2. For example -7 » 1 = -7 / 2 = -4, -7 « 1 = -14 Title 1. Single number 693 alternating bits binary number Checks whether two adjacent digits of a binary number are not equal. ...