wordpress如何添加网站地图,有哪些公司建设网站,wordpress 返回主页,用什么系统程序做评测网站一、移动零
给定一个数组 nums#xff0c;编写一个函数将所有 0 移动到数组的末尾#xff0c;同时保持非零元素的相对顺序。
请注意 #xff0c;必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums [0,1,0,3,12]输出: [1,3,12,0,0]示例 2:
输入: nums …一、移动零
给定一个数组 nums编写一个函数将所有 0 移动到数组的末尾同时保持非零元素的相对顺序。
请注意 必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums [0,1,0,3,12]输出: [1,3,12,0,0]示例 2:
输入: nums [0]输出: [0]提示:
1 nums.length 10^4-2^31 nums[i] 2^31 - 1
进阶你能尽量减少完成的操作次数吗
解法一双指针法
在循环中右指针right向右移动如果当前元素不为0则将其与左指针指向的元素交换并且左指针向右移动。
class Solution {public void moveZeroes(int[] nums) {int i 0, j 0;while(j nums.length) {if(nums[j] ! 0) {// 如果当前元素不为0则将其与左指针指向的元素交换并且左指针向右移动int t nums[i];nums[i] nums[j];nums[j] t;i;}j;}}
} 二、两数之和Ⅱ - 输入有序数组
给你一个下标从 1 开始的整数数组 numbers 该数组已按 非递减顺序排列 请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] 则 1 index1 index2 numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例 1
输入numbers [2,7,11,15], target 9
输出[1,2]
解释2 与 7 之和等于目标数 9 。因此 index1 1, index2 2 。返回 [1, 2] 。
示例 2
输入numbers [2,3,4], target 6
输出[1,3]
解释2 与 4 之和等于目标数 6 。因此 index1 1, index2 3 。返回 [1, 3] 。
示例 3
输入numbers [-1,0], target -1
输出[1,2]
解释-1 与 0 之和等于目标数 -1 。因此 index1 1, index2 2 。返回 [1, 2] 。提示
2 numbers.length 3 * 10^4-1000 numbers[i] 1000numbers 按 非递减顺序 排列-1000 target 1000仅存在一个有效答案
解法一双指针法。执行耗时1ms
class Solution {public int[] twoSum(int[] numbers, int target) {int i 0, j numbers.length - 1;while (i j) {int sum numbers[i] numbers[j];if (sum target) {return new int[] { i 1, j 1 };} else if (sum target) {i;} else {j--;}}return new int[] {};}
} 三、三数之和
给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。
注意答案中不可以包含重复的三元组。
示例 1
输入nums [-1,0,1,2,-1,-4]
输出[[-1,-1,2],[-1,0,1]]
解释
nums[0] nums[1] nums[2] (-1) 0 1 0 。
nums[1] nums[2] nums[4] 0 1 (-1) 0 。
nums[0] nums[3] nums[4] (-1) 2 (-1) 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意输出的顺序和三元组的顺序并不重要。示例 2
输入nums [0,1,1]
输出[]
解释唯一可能的三元组和不为 0 。示例 3
输入nums [0,0,0]
输出[[0,0,0]]
解释唯一可能的三元组和为 0 。提示
3 nums.length 3000-105 nums[i] 105
解法一由三数之和转变为两数之和
class Solution {public ListListInteger threeSum(int[] nums) {ListListInteger result new ArrayList();Arrays.sort(nums);for (int i 0; i nums.length; i) {// 跳过重复元素if (i 0 nums[i] nums[i - 1]) {continue;}// 变为两数之和int target -nums[i];int left i 1;int right nums.length - 1;while (left right) {int sum nums[left] nums[right];if (sum target) {left;} else if (sum target) {right--;} else {ListInteger triplet new ArrayList();triplet.add(nums[i]);triplet.add(nums[left]);triplet.add(nums[right]);result.add(triplet);// 跳过重复的元素while (left right nums[left] nums[left 1]) {left;}while (left right nums[right] nums[right - 1]) {right--;}left;right--;}}}return result;}
}
或
class Solution {public ListListInteger threeSum(int[] nums) {Arrays.sort(nums);ListListInteger result new LinkedList();dfs(3, 0, nums.length - 1, 0, nums,new LinkedList(), result);return result;}static void dfs(int n, int i, int j, int target, int[] nums,LinkedListInteger stack,ListListInteger result) {if (n 2) {// 套用两数之和求解twoSum(i, j, nums, target, stack, result);return;}for (int k i; k j - (n - 2); k) {// 检查重复if (k i nums[k] nums[k - 1]) {continue;}// 固定一个数字再尝试 n-1 数字之和stack.push(nums[k]);dfs(n - 1, k 1, j, target - nums[k], nums, stack, result);stack.pop();}}static int count;static public void twoSum(int i, int j, int[] numbers, int target,LinkedListInteger stack,ListListInteger result) {count;while (i j) {int sum numbers[i] numbers[j];if (sum target) {i;} else if (sum target) {j--;} else { // 找到解ArrayListInteger list new ArrayList(stack);list.add(numbers[i]);list.add(numbers[j]);result.add(list);// 继续查找其它的解i;j--;while (i j numbers[i] numbers[i - 1]) {i;}while (i j numbers[j] numbers[j 1]) {j--;}}}}
} 四、四数之和
给你一个由 n 个整数组成的数组 nums 和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 若两个四元组元素一一对应则认为两个四元组重复
0 a, b, c, d na、b、c 和 d 互不相同nums[a] nums[b] nums[c] nums[d] target
你可以按 任意顺序 返回答案 。
示例 1
输入nums [1,0,-1,0,-2,2], target 0
输出[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]示例 2
输入nums [2,2,2,2,2], target 8
输出[[2,2,2,2]]提示
1 nums.length 200-109 nums[i] 109-109 target 109
解法一双指针法
class Solution {public ListListInteger fourSum(int[] nums, int target) {ListListInteger result new ArrayList();int n nums.length;if (n 4) {return result;}Arrays.sort(nums);for (int i 0; i n - 3; i) {if (i 0 nums[i] nums[i - 1]) {// 处理重复元素continue;}for (int j i 1; j n - 2; j) {if (j i 1 nums[j] nums[j - 1]) {continue;}int left j 1;int right n - 1;while (left right) {long sum (long) nums[i] nums[j] nums[left] nums[right];if (sum target) {left;} else if (sum target) {right--;} else {ListInteger quadruplet new ArrayList();quadruplet.add(nums[i]);quadruplet.add(nums[j]);quadruplet.add(nums[left]);quadruplet.add(nums[right]);result.add(quadruplet);// 处理重复元素while (left right nums[left] nums[left 1]) {left;}while (left right nums[right] nums[right - 1]) {right--;}left;right--;}}}}return result;}
} 五、盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明你不能倾斜容器。
示例 1 输入[1,8,6,2,5,4,8,3,7]
输出49
解释图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下容器能够容纳水表示为蓝色部分的最大值为 49。
示例 2
输入height [1,1]
输出1提示
n height.length2 n 10^50 height[i] 10^4
解法一双指针法
class Solution {public int maxArea(int[] height) {int left 0, right height.length - 1;int result 0;while (left right) {result Math.max(result, (right - left) * Math.min(height[left], height[right]));if (height[left] height[right]) {--right;} else {left;}}return result;}
} 六、反转字符数组
编写一个函数其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1
输入s [h,e,l,l,o]
输出[o,l,l,e,h]示例 2
输入s [H,a,n,n,a,h]
输出[h,a,n,n,a,H]提示
1 s.length 10^5s[i] 都是 ASCII 码表中的可打印字符
解法一双指针法
class Solution {public void reverseString(char[] s) {int i 0, j s.length - 1;while (i j) {swap(s, i, j);i;j--;}}private void swap(char[] s, int i, int j) {char t s[i];s[i] s[j];s[j] t;}
} 七、反转字符串Ⅱ
给定一个字符串 s 和一个整数 k从字符串开头算起每计数至 2k 个字符就反转这 2k 字符中的前 k 个字符。
如果剩余字符少于 k 个则将剩余字符全部反转。如果剩余字符小于 2k 但大于或等于 k 个则反转前 k 个字符其余字符保持原样。
示例 1
输入s abcdefg, k 2
输出bacdfeg示例 2
输入s abcd, k 2
输出bacd提示
1 s.length 10^4s 仅由小写英文组成1 k 10^4
解法一双指针法
class Solution {public String reverseStr(String s, int k) {int n s.length();char[] chars s.toCharArray();for (int i 0; i n; i 2 * k) {// 只反转前k个字符int start i;int end Math.min(i k - 1, n - 1);while (start end) {swap(chars, start, end);start;end--;}}return new String(chars);}private void swap(char[] s, int i, int j) {char t s[i];s[i] s[j];s[j] t;}
}
