公司网站建设有用吗,网站开发设计框图,网站推广平台,wordpress 静态页面一丶哈希
1、两数之和#xff08;简单#xff09; 给定一个整数数组 n u m s nums nums 和一个整数目标值 t a r g e t target target#xff0c;请你在该数组中找出 和为目标值 t a r g e t target target 的那 两个 整数#xff0c;并返回它们的数组下标。 你可以假设…一丶哈希
1、两数之和简单 给定一个整数数组 n u m s nums nums 和一个整数目标值 t a r g e t target target请你在该数组中找出 和为目标值 t a r g e t target target 的那 两个 整数并返回它们的数组下标。 你可以假设每种输入只会对应一个答案并且你不能使用两次相同的元素。 你可以按任意顺序返回答案。
示例 1输入nums [2,7,11,15], target 9
输出[0,1]
解释因为 nums[0] nums[1] 9 返回 [0, 1] 。
示例 2输入nums [3,2,4], target 6
输出[1,2]
示例 3输入nums [3,3], target 6
输出[0,1]方法一自己想到暴力枚举两次循环遍历所有相加的情况
class Solution {public int[] twoSum(int[] nums, int target) {for(int i0;inums.length;i){for(int ji1;jnums.length;j){if(nums[i]nums[j]target){return new int[]{i,j};}}}return new int[0];}
}方法二想不到哈希表遍历数组查看哈希表中是否存在target-当前数组元素值的key如果存在返回当前数组索引和哈希表key的value不存在把当前的数组元素和下标记录到哈希表中
class Solution {public int[] twoSum(int[] nums, int target) {MapInteger,Integer mapnew HashMap();for(int i0;inums.length;i){if(map.containsKey(target-nums[i])){return new int[]{i,map.get(target-nums[i])};}map.put(nums[i],i);}return new int[0];}
}2、字母异位词分组中等 给你一个字符串数组请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:输入: strs [eat, tea, tan, ate, nat, bat]
输出: [[bat],[nat,tan],[ate,eat,tea]]
示例 2:输入: strs []
输出: [[]]
示例 3:输入: strs [a]
输出: [[a]]
方法一排序想不到 字母异位词经过排序都是相同的可以作为哈希表的键。然后同一个组的字母异位词组成的集合作为哈希表的值
class Solution {public ListListString groupAnagrams(String[] strs) {HashMapString,ListString mapnew HashMap();for (String s:strs) {char[] arrs.toCharArray();Arrays.sort(arr);String keynew String(arr);ListString listmap.getOrDefault(key,new ArrayList());list.add(s);map.put(key,list);}return new ArrayList(map.values());}
}方法二计数想不到 由于互为字母异位词的两个字符串包含的字母相同因此两个字符串中的相同字母出现的次数一定是相同的故可以将每个字母出现的次数使用字符串表示作为哈希表的键。例如eat可以表示为a1e1t1这样的形式。不过个人感觉实现起来不如方法一方便原理其实也差不多
class Solution {public ListListString groupAnagrams(String[] strs) {HashMapString,ListString mapnew HashMap();for (String s:strs) {int[] countnew int[26]; //只有小写字母for (int i 0; i s.length(); i) {count[s.charAt(i) - a];}StringBuffer sb new StringBuffer();for (int i 0; i 26; i) {if (count[i] ! 0) {sb.append((char) (a i));sb.append(count[i]);}}String key sb.toString();ListString list map.getOrDefault(key, new ArrayListString());list.add(s);map.put(key, list);}return new ArrayList(map.values());}
}3、最长连续序列中等 给定一个未排序的整数数组 nums 找出数字连续的最长序列不要求序列元素在原数组中连续的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1输入nums [100,4,200,1,3,2]
输出4
解释最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2输入nums [0,3,7,2,5,8,4,6,0,1]
输出9方法一想不到哈希表 先把数组的元素存在HashSet里面。然后遍历HashSet每当遍历到一个元素x判断x-1是否存在hash里面存在的话就可以直接跳过因为我们会从x-1开始寻找最长序列。如果不存在的话就循环去hash里找x1,x2直到找到所有的。
class Solution {public int longestConsecutive(int[] nums) {HashSetInteger setnew HashSet();for (int num:nums) {set.add(num);}int longlen0;for (int num:set) {if(!set.contains(num-1)){int currentnum;int maxlen1;while (set.contains(current1)){current;maxlen;}longlenMath.max(longlen,maxlen);}}return longlen;}
}二、双指针
1、 移动零简单 给定一个数组 nums编写一个函数将所有 0 移动到数组的末尾同时保持非零元素的相对顺序。 请注意 必须在不复制数组的情况下原地对数组进行操作。
示例 1:输入: nums [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:输入: nums [0]
输出: [0]方法一自己想到双指针一个指针指向0一个指针非0交换指针后然后继续查找下一个零元素和非零元素。
class Solution {public void moveZeroes(int[] nums) {int p10,p20; //p1指向0元素p2指向非0元素while (p1nums.lengthp2nums.length){while (p1nums.length){if(nums[p1]0){break;}p1;}p2p11;while (p2nums.length){if(nums[p2]!0){break;}p2;}if(p1!nums.lengthp2!nums.length){int tempnums[p1];nums[p1]nums[p2];nums[p2]temp;}}}
}方法二想不到 快慢指针如果数组没有0那么快慢指针始终指向同一个位置每个位置自己和自己交换如果数组有0快指针先走一步此时慢指针对应的就是0所以要交换。
class Solution {public void moveZeroes(int[] nums) {int n nums.length, left 0, right 0;while (right n) {if (nums[right] ! 0) {swap(nums, left, right);left;}right;}}public void swap(int[] nums, int left, int right) {int temp nums[left];nums[left] nums[right];nums[right] temp;}
}2、盛最多水的容器中等 给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明你不能倾斜容器。
输入[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方法一自己想到暴力。把所有情况能盛的水都列举出来最后选择一个最大的。这样做会超出时间限制
class Solution {public int maxArea(int[] height) {int maxWater0;for(int i0;iheight.length;i){for (int ji;jheight.length;j){if((j-i)*Math.min(height[i],height[j])maxWater){System.out.println(i-height[i]-height[j]-j);maxWater(j-i)*Math.min(height[i],height[j]);}}}return maxWater;}
}方法二双指针想不到 将左右指针分别指向数组两端。因为水容量两个指针指向的数字中较小值∗指针之间的距离。所以如果我们移动高的指针较小值肯定不会增加而指针距离减小水容量必定减少。所以我们只能移动低的指针距离减少了但有可能较小值增加。 public int maxArea(int[] height) {int maxWater0,left0,rightheight.length-1;while (leftright){if((right-left)*Math.min(height[left],height[right])maxWater){maxWater(right-left)*Math.min(height[left],height[right]);}if(height[left]height[right])right--;else left;}return maxWater;}3、三数之和中等 给你一个整数数组 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个数字。这里的排序和Set集合都是为了题目要求的去重。这样做会超出时间限制ON3
class Solution {public ListListInteger threeSum(int[] nums) {Arrays.sort(nums);HashSetString setnew HashSet();ListListInteger listnew ArrayList();for(int i0;inums.length-2;i){for(int ji1;j nums.length-1;j){for(int kj1;knums.length;k){if(nums[i]nums[j]nums[k]0){if(!set.contains(nums[i]-nums[j]-nums[k])){set.add(nums[i]-nums[j]-nums[k]);ListInteger list1new ArrayList();list1.add(nums[i]);list1.add(nums[j]);list1.add(nums[k]);list.add(list1);}}}}}return list;}
}方法二折半查找自己想到。因为数组已经被我排序了所以第三个循环可以改成二分查找这样做可以勉强通过测试O(N2logN)
class Solution {public ListListInteger threeSum(int[] nums) {Arrays.sort(nums);HashSetString setnew HashSet();ListListInteger listnew ArrayList();for(int i0;inums.length-2;i){for(int ji1;j nums.length-1;j){int kArrays.binarySearch(nums,j1,nums.length,-(nums[i]nums[j]));if(kjnums[i]nums[j]nums[k]0){if(!set.contains(nums[i]-nums[j]-nums[k])){set.add(nums[i]-nums[j]-nums[k]);ListInteger list1new ArrayList();list1.add(nums[i]);list1.add(nums[j]);list1.add(nums[k]);list.add(list1);}}}}return list;}
}方法三双指针想不到。数组排序后第一个循环不变第二个循环和第三个循环可以并行的。因为要abc0那么b增加c就要减少。 public static ListListInteger threeSum(int[] nums) {Arrays.sort(nums);HashSetString setnew HashSet();ListListInteger listnew ArrayList();for(int i0;inums.length-2;i) {int left i 1, right nums.length - 1;while (left right) {if (nums[i] nums[left] nums[right] 0) {if(!set.contains(nums[i]-nums[left]-nums[right])){set.add(nums[i]-nums[left]-nums[right]);ListInteger list1new ArrayList();list1.add(nums[i]);list1.add(nums[left]);list1.add(nums[right]);list.add(list1);}left;right--;} else if (nums[i] nums[left] nums[right] 0) {right--;}else {left;}}}return list;}三、滑动窗口
四、子串
五、普通数组
六、矩阵
七、链表
八丶二叉树
九、图论
十丶回溯
十一、二分查找
1、搜索插入位置简单 给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。
示例 1:输入: nums [1,3,5,6], target 5
输出: 2
示例 2:输入: nums [1,3,5,6], target 2
输出: 1
示例 3:输入: nums [1,3,5,6], target 7
输出: 4方法自己想到标准的二分查找题目多要求了一个返回没找到值的插入位置判断一下返回mid或者mid1就可以
class Solution {public int searchInsert(int[] nums, int target) {int low0,highnums.length-1,mid0;while(lowhigh){mid(lowhigh)/2;if(nums[mid]target)return mid;else if(nums[mid]target)highmid-1;else lowmid1;}if(nums[mid]target){return mid;}return mid1;}
}十二、栈
十三、堆
十四丶贪心算法
十五丶动态规划
十六丶多维动态规划
十七、技巧
1、只出现一次的数字(简单) 给你一个 非空 整数数组 nums 除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题且该算法只使用常量额外空间。
示例 1 输入nums [2,2,1]
输出1
示例 2 输入nums [4,1,2,1,2]
输出4
示例 3 输入nums [1]
输出1方法一这个就是记住这个异或运算符^的定理就好了任何数和0异或是本身任何数和自身异或是0
class Solution {public int singleNumber(int[] nums) {int sumnums[0];for(int i1;inums.length;i){sum^nums[i];}return sum;}
}2、多数元素简单 给定一个大小为 n 的数组 nums 返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的并且给定的数组总是存在多数元素。
示例 1输入nums [3,2,3]
输出3
示例 2输入nums [2,2,1,1,1,2,2]
输出2方法1自己想到用哈希表遍历数组把每个元素的数量存下来然后遍历哈希表找出数量大于数组一半的即可
class Solution {public int majorityElement(int[] nums) {HashMapInteger,Integer mapnew HashMap();for(int i0;inums.length;i){if(map.containsKey(nums[i])){map.put(nums[i],map.get(nums[i])1);}else {map.put(nums[i],1);}}for (Map.EntryInteger,Integer entry: map.entrySet()) {int keyentry.getKey();int valueentry.getValue();if(valuenums.length/2){return key;}}return nums[0];}
}方法2想不到Boyer-Moore 投票算法 如果我们把众数记为 1把其他数记为 −1将它们全部加起来显然和大于 0从结果本身我们可以看出众数比其他数多。
class Solution {public int majorityElement(int[] nums) {int count0,candidate0;for(int i0;inums.length;i){if(count0)candidatenums[i];if(nums[i]candidate)count;else count--;}return candidate;}
}
