ARTS Week 1
Algorithm
This week’s LeetCode problem is 189. Rotating Arrays
Problem Description
Given an array, rotate the array to the right by k steps, where k is non-negative. The example is as follows.
Input array [1,2,3,4,5,6,7], k = 3
Output array: [5,6,7,1,2,3,4]
Explanation:
Rotate 1 steps to the right: [7,1,2,3,4,5,6]
Rotate 2 steps to the right: [6,7,1,2,3,4,5]
Rotate 3 steps to the right: [5,6,7,1,2,3,4]Solution 1: My own idea
Create a new array to store the result. Because I found that now nums[i] = original nums[i + nums.length - k % nums.length] after rotating and moving. Taking the modulu because when k is greater than nums.length, there is no difference between moving nums.length and without moving it. The code that accepted is as follows.
class Solution {
public void rotate(int[] nums, int k) {
if (nums.length <= 1) {
return ;
} int start = nums.length - k % nums.length;
if (start == nums.length) {
return ;
} int[] temp = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
temp[i] = nums[i];
}
for (int i = 0; i < nums.length; i++) {
nums[i] = temp[start];
start = (start + 1) % nums.length;
}
}
}
But my own code is not concise, there are some improvements.
- the first two judgments are a bit redundant and could be removed.
- the array copy is a circular assignment, after understanding the system can be called with the function.
- I used to find the rule from 0, and the
nums[0]after the change is equal to something, but it is more complicated to express.
Solution 2: From the official solution 1
Same idea as the above code, the difference is that
- when looking for a pattern, think backwards about what the original
nums[0]would be now. - use
System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)to copy the array.
class Solution {
public void rotate(int[] nums, int k) {
int[] ans = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
ans[(i+k) % nums.length] = nums[i];
}
System.arraycopy(ans, 0, nums, 0, nums.length);
}
}Solution 3: From the official solution 3
By flipping the array, firstly flipping the whole array, and then flipping [0, k%nums.length - 1] and [k, nums.length] respectively. Using the example given in the problem example, it is as follows.
operation result The original array [1,2,3,4,5,6,7] flip all [7,6,5,4,3,2,1] Flip [0, 3] [5,6,7,4,3,2,1] flip [4, 7] [5,6,7,1,2,3,4]
class Solution {
private void reverse(int[] nums, int start, int end) {
int temp = 0;
while (start < end) {
temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
} public void rotate(int[] nums, int k) {
reverse(nums, 0, nums.length-1);
reverse(nums, 0, k % nums.length -1);
reverse(nums, k % nums.length, nums.length-1);
}
}
Review
The English article in this week’s Review is: Happy birthday, Linux: From a bedroom project to billions of devices in 30 years
The article is an interview Greg Kroah-Hartman gave to The Register to celebrate the 30th anniversary of Linux (Greg Kroah-Hartman is represented by GK-H below). Here’s a quick recap of the interview.
First, a brief introduction to the Linux kernel. GK-H was then asked about the biggest challenge in developing the Linux kernel, then he thought that is the development scheme because of large number of developers and users for Linux kernel. Currently the Linux kernel is using a time-based distribution model.
GK-H describes the integration of the Linux kernel into Rust, which can be done through this summary for updates. The current attitude of Linux kernel development towards Rust is, “just write new code in Rust if at all possible. But that’s not to say that once support would be merged, that replacing existing C code would not be possible, only that it is not the original goal here at all.”.
GK-H was then asked if there would be a competitor to the Linux kernel, like the browser, and GK-H said I would love some real competition in operating system kernels. Before the BSD developers went to Apple, there was a lot of collaboration between them, and now there is a lot of interaction with the developers of Google’s Fuchsia.
In addition, GK-H says he doesn’t plan for the future, but rather takes one step at a time and adjusts accordingly to the new architecture. He won’t get involved in discussions about why Linux is successful or whether it will be affected by geopolitics/nationalism, but will focus on code and projects. Finally, GK-H describes how the Linux kernel has given him the benefits of working, traveling around the world, meeting more people, and more.
Tip
Each basic type in Java has its corresponding wrapper class. For example, int and Integer. When creating Integer, there are two methods.
Integer n = new Integer(100);
2: Integer n = Integer.valueOf(100);
Method 2 is superior to method 1 because method 1 always creates a new instance of Integer, while method 2 leaves its internal optimization to the implementor of Integer.
We generally refer to Integer.valueOf() as a static factory method that returns cached instances whenever possible to save memory. In Java 8, if the value range is between -128 and 127, the cache will be used to reduce the time (related JavaDoc link).
Share
ARTS has been offline for over a year and a half, and now I’m picking it up again. I deleted all my previous posts before updating, to forget about the past and start over. The last three months at the beginning of each month in the circle of friends to summarize their own exercise, reading and output of the previous month, to monitor themselves. When the self-exposure, they will drive themselves and will discipline themselves to reach/approach a certain goal, it’s like when no one is paying attention, a person may be more unable to discipline themselves and more likely to expose some bad aspects of themselves because no one notices anyway.
The next plan is to make sure to update one ARTS article per week along with another article, maybe technology related, maybe reading related, etc.
