Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.
Example 1:
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [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]
Example 2:
Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]
Constraints:
1 <= nums.length <= 10^5
2^31 <= nums[i] <= 2^31 - 1
0 <= k <= 10^5
Follow up:
O(1) extra space?這題寫了兩個解法出來，第一個是這次解題想的，印象中前幾篇文章有提到，它往後移動k個索引值等於後面k個元素移到前面，所以這邊就直接沿用當時的想法，用兩個陣列暫存前面size - k個元素以及後面k個元素，最後放進去原本的陣列。
Runtime: 1 ms (50.71%)
Memory Usage: 55.2 MB (78.78%)
class Solution {
public void rotate(int[] nums, int k) {
int size = nums.length;
k %= size;
if (k != 0) {
int[] frontTemp = new int[k];
int[] endTemp = new int[size - k];
int i;
for (i = 0; i < k; i++) {
frontTemp[i] = nums[size - k + i];
}
for (i = 0; i < size - k; i++) {
endTemp[i] = nums[i];
}
for (i = 0; i < k; i++) {
nums[i] = frontTemp[i];
}
for (i = 0; i < size - k; i++) {
nums[k + i] = endTemp[i];
}
}
}
}
第二個方法應該是以前上網查的，它總共就三個步驟，先整個陣列全部反轉，再來把0~k個元素反轉，最後把k~尾端的元素反轉就是答案了，這可能需要一點想像力...
Runtime: 0 ms (100%)
Memory Usage: 55.8 MB (46.44%)
class Solution {
public void rotate(int[] nums, int k) {
int len = nums.length;
k %= len;
reverse(nums, 0, len - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, len - 1);
}
private void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
}
Given an input string s, reverse the order of the words.
A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.
Return a string of the words in reverse order concatenated by a single space.
Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.
Example 1:
Input: s = "the sky is blue"
Output: "blue is sky the"
Example 2:
Input: s = " hello world "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.
Example 3:
Input: s = "a good example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.
Constraints:
1 <= s.length <= 10^4
s contains English letters (upper-case and lower-case), digits, and spaces ' '.s.Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?
這邊嘗試了兩種寫法，第一種是使用Java 內建的切割字串方法，切割完之後再從後面遍歷組裝字串。
Runtime: 5 ms (91.33%)
Memory Usage: 43.4 MB (53.8%)
class Solution {
public String reverseWords(String s) {
String[] split = s.split(" ");
StringBuilder sb = new StringBuilder();
for (int i = split.length - 1; i >= 0; i--) {
if (!"".equals(split[i])) {
sb.append(sb.isEmpty() ? "" : " ").append(split[i]);
}
}
return sb.toString();
}
}
第二種方法則是轉成char[]格式，反轉之後在取子字串再反轉，感覺可以再省略一些步驟，但效果還不錯就先暫時這樣了。
Runtime: 4 ms (95.17%)
Memory Usage: 42.1 MB (72.55%)
class Solution {
public String reverseWords(String s) {
char[] sChar = s.toCharArray();
int size = sChar.length, start = 0, end = size - 1;
char tempCh;
while (start < end) {
tempCh = sChar[start];
sChar[start++] = sChar[end];
sChar[end--] = tempCh;
}
StringBuilder sb = new StringBuilder();
StringBuilder tempSb = new StringBuilder();
for (int i = 0; i < size; i++) {
if (sChar[i] == ' ') {
if (tempSb.length() == 0) continue;
else {
sb.append(sb.length() == 0 ? "" : " ").append(tempSb.reverse());
tempSb = new StringBuilder();
}
} else {
tempSb.append(sChar[i]);
}
}
if (tempSb.length() != 0) {
sb.append(sb.length() == 0 ? "" : " ").append(tempSb.reverse());
}
return sb.toString();
}
}
Given a string s, reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.
Example 1:
Input: s = "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"
Example 2:
Input: s = "God Ding"
Output: "doG gniD"
Constraints:
1 <= s.length <= 5 * 10^4
s contains printable ASCII characters.s does not contain any leading or trailing spaces.s.s are separated by a single space.這題跟上一題的想法差不多，但效果卻差很多，有時間再來優化好了。
Runtime: 6 ms (60.96%)
Memory Usage: 44.1 MB (56.35%)
class Solution {
public String reverseWords(String s) {
char[] sChar = s.toCharArray();
int size = sChar.length;
StringBuilder sb = new StringBuilder();
StringBuilder temp = new StringBuilder();
for (int i = 0; i < size; i++) {
if (sChar[i] == ' ') {
if (temp.length() == 0) continue;
else {
sb.append(sb.length() == 0 ? "" : " ").append(temp.reverse());
temp = new StringBuilder();
}
} else {
temp.append(sChar[i]);
}
}
if (temp.length() != 0) sb.append(sb.length() == 0 ? "" : " ").append(temp.reverse());
return sb.toString();
}
}
第一題在年初的時候寫過一次，解法應該是有上網查過的，畢竟如果是自己想出來的應該會有印象，不過從那個解法也可以了解到，寫程式是需要有一點創意跟想像力的。
iThome鐵人賽
看影片追技術