一刷 记录
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。
代码：
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
int len = nums.length;
int[] res = new int[2];
for (int i = 0; i < len; i++) {// 先判断后放(对)和先放后判断(错)
int key = target - nums[i];
if (map.containsKey(key)) {
res[0] = i;
res[1] = map.get(key);
return res;
}
map.put(nums[i], i);
}
return res;
}
}给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
代码：
class Solution {// 找出由相同字母组成的单词，且每个单词内的每种字母的个数相同
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> list = new ArrayList<>();// 存放最终结果
Map<String, List<String>> map = new HashMap<>();
for (int i = 0; i < strs.length; i++) {
char[] arr = strs[i].toCharArray();
// Arrays.sort()方法可以对字符数组进行排序
Arrays.sort(arr);// 排序，好确定key："ate"->aet,"eat"->aet
String str = String.valueOf(arr);
if (!map.containsKey(str)) {
map.put(str, new ArrayList<>());
}
map.get(str).add(strs[i]);
}
// entrySet:Java中键值对的集合
for(Map.Entry<String,List<String>> entry:map.entrySet()){
list.add(entry.getValue());
}
return list;
}
}给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
代码：
class Solution {
public int longestConsecutive(int[] nums) {
int len = nums.length;
if (len == 0)
return 0;
int res = 1;// 初始化长度为0
// Arrays.sort(nums);
Set<Integer> set = new HashSet<>();
for (int i : nums) {
set.add(i);
}
for (int i : set) {// 遍历set节约时间
if (set.contains(i - 1))
continue;
int temp = 1;
while (set.contains(i + temp)) {
temp++;
}
res = res > temp ? res : temp;
}
return res;
}
}给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
代码：
class Solution {
public void moveZeroes(int[] nums) {
// index记录非0的个数，将非0数放置数组前index位上，后面补充0（这里使用了两个指针，一个是i指针用于遍历数组元素，另一个是index指针用于记录非零元素应该放置的位置）
// int index = 0;
// for (int i : nums) {
// if (i != 0)
// index++;
// }
// int start = 0;
// for (int i : nums) {
// if (i != 0) {
// nums[start++] = i;
// }
// if (start == index) {
// for (int j = index; j < nums.length; j++) {
// nums[j] = 0;
// }
// break;
// }
// }
//空间复杂度太大了，减少开辟空间次数
// int index=0;
// for(int i=0;i<nums.length;i++){
// if(nums[i]!=0){
// nums[index]=nums[i];
// //防止在同一个下标上操作两次
// if(index!=i){
// nums[i]=0;
// }
// index++;
// }
// }
//快慢指针(双指针)
//一个是fastIndex指针用于遍历数组元素，另一个是slowIndex指针用于记录非零元素应该放置的位置
int fastIndex=0,slowIndex=0;int temp=0;
for(;fastIndex<nums.length;fastIndex++){
if(nums[fastIndex]!=0){
temp=nums[fastIndex];
nums[fastIndex]=0;
nums[slowIndex++]=temp;//如果slow==fast也可以覆盖0
}
}
}
}给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。说明：你不能倾斜容器。
代码：
class Solution {
public int maxArea(int[] height) {
//双指针法，每次移动最短的边
int l=0;
int r=height.length-1;
int maxArea=0;
int curArea=0;
int minHeight=0;
while(l<r){//注意循环的内容和i无关，用for循环
// maxArea=Math.max(maxArea,Math.min(height[l],height[r])*(r-l));
// if(height[l]>=height[r]) r--;
// else l++;
minHeight=Math.min(height[l],height[r]);
curArea=minHeight*(r-l);
maxArea=Math.max(maxArea,curArea);
//优化 快速跳过
while(height[l]<=minHeight&&l<r){
l++;
}
while(height[r]<=minHeight&&l<r){
r--;
}
}
return maxArea;
}
}给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
代码：
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
// 用双指针，使用Map的化去重逻辑较复杂
List<List<Integer>> res = new ArrayList<>();
int len = nums.length;
int left,right;
Arrays.sort(nums);// 排序后才能通过指针的移动求得结果
for (int i = 0; i < len; i++) {// 注意i要初始化为0
if (nums[i] > 0) return res;
left = i + 1;
right = len - 1;
// 排序后，如果上一个遍历过的元素和后面形成了集合，这时下一次循环往前看，已经有过这个开头了就去掉(去重)
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
} else {
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum > 0) {
right--;
} else if (sum < 0) {
left++;
} else {// 再次去重,这里的if判断注意要有left<right(涉及到指针的移动都要注意)
// 返回一个指定大小的列表
List list = Arrays.asList(nums[i], nums[left], nums[right]);
res.add(list);
while (left < right && nums[right] == nums[right - 1])
right--;
while (left < right && nums[left] == nums[left + 1])
left++;
// 找到合适的一组结果，left，right要分别移动一位
left++;
right--;
}
}
}
}
return res;
}
}给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
代码：
方法一：双指针
class Solution {//按列取比较好理解
public int trap(int[] height) {
int len=height.length;
int res=0;
int[] maxL=new int[len];
int[] maxR=new int[len];
maxL[0]=height[0];
maxR[len-1]=height[len-1];
for(int i=1;i<len;i++){
maxL[i]=Math.max(height[i],maxL[i-1]);
}
for(int j=len-2;j>=0;j--){
maxR[j]=Math.max(height[j],maxR[j+1]);
}
for(int i=0;i<len;i++){
if(i==0&&i==len-1) continue;//第一列或最后一列不存水
int h=Math.min(maxL[i],maxR[i])-height[i];
if(h>0)
res+=h;
}
return res;
}
}方法二：单调栈
class Solution {
public int trap(int[] height) {
int len = height.length;
int v = 0;
Deque<Integer> stack = new LinkedList<>();
stack.push(0);
for (int i = 1; i < len; i++) {
if (height[i] < height[stack.peek()]) {
stack.push(i);
} else if (height[i] == height[stack.peek()]) {
stack.pop();
stack.push(i);
} else {
while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
int j = stack.pop();
if (!stack.isEmpty()) {
int h = Math.min(height[i], height[stack.peek()]) - height[j];
int w = i - stack.peek() - 1;
v += h * w;
}
}
stack.push(i);
}
}
return v;
}
}给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。（子字符串 是字符串中连续的 非空 字符序列）
代码：
class Solution {// 用map来检测里否遍历过字符
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0)
return 0;
Map<Character, Integer> map = new HashMap<>();
int len = 0;
int res = 0;
char[] arr = s.toCharArray();
for (int l = 0, r = 0; r < arr.length; r++) {
if (map.containsKey(arr[r])) {
//更新有效字段的左边界
l=Math.max(l,map.get(arr[r])+1);//abba
}
res = Math.max(res, r-l+1);
map.put(arr[r], r);// 无论是否有重复都要put当前遍历的字符（如果重复哪下标更新为r）
}
return res;
}
}给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
代码：
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int slen=s.length();
int plen=p.length();
List<Integer> res=new ArrayList<>();
if(slen<plen) return res;
int[] s1=new int[26];
int[] p1=new int[26];
for(int i=0;i<plen;i++){
s1[s.charAt(i)-'a']++;
p1[p.charAt(i)-'a']++;
}
if(Arrays.equals(s1,p1)){
res.add(0);
}
for(int i=0;i<slen-plen;i++){//滑动窗口遍历s1
--s1[s.charAt(i)-'a'];
++s1[s.charAt(i+plen)-'a'];
if(Arrays.equals(s1,p1)){
res.add(i+1);
}
}
return res;
}
}给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
代码：
class Solution {//前缀和
//前缀和是指一个数组中从第一个元素开始到当前位置的所有元素的和
public int subarraySum(int[] nums, int k) {
Map<Integer,Integer> map=new HashMap<>();//key:前缀和 value:次数
map.put(0,1);
int sum=0;
int count=0;
for(int i=0;i<nums.length;i++){
sum+=nums[i];
//前i项和sum，前j项和为sum-k
//前i项的和-前j项的和为k
if(map.containsKey(sum-k)){
count+=map.get(sum-k);
}
map.put(sum,map.getOrDefault(sum,0)+1);
}
return count;
}
}给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。
代码：
class Solution {
//自定义数组
class MyQueue {
Deque<Integer> deque = new LinkedList<>();
//弹出元素时，比较当前要弹出的数值是否等于队列出口的数值，如果相等则弹出
//同时判断队列当前是否为空
void poll(int val) {
if (!deque.isEmpty() && val == deque.peek()) {
deque.poll();
}
}
//添加元素时，如果要添加的元素大于入口处的元素，就将入口元素弹出
//保证队列元素单调递减
//比如此时队列元素3,1，2将要入队，比1大，所以1弹出，此时队列：3,2
void add(int val) {
while (!deque.isEmpty() && val > deque.getLast()) {
deque.removeLast();
}
deque.add(val);
}
//队列队顶元素始终为最大值
int peek() {
return deque.peek();
}
}
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length == 1) {
return nums;
}
int len = nums.length - k + 1;
//存放结果元素的数组
int[] res = new int[len];
int num = 0;
//自定义队列
MyQueue myQueue = new MyQueue();
//先将前k的元素放入队列
for (int i = 0; i < k; i++) {
myQueue.add(nums[i]);
}
res[num++] = myQueue.peek();
for (int i = k; i < nums.length; i++) {
//滑动窗口移除最前面的元素，移除是判断该元素是否放入队列
myQueue.poll(nums[i - k]);
//滑动窗口加入最后面的元素
myQueue.add(nums[i]);
//记录对应的最大值
res[num++] = myQueue.peek();
}
return res;
}
}给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
代码：
class Solution {//滑动窗口
public String minWindow(String s, String t) {
if(s==null||s.length()==0||t==null||t.length()==0){
return "";
}
int sLen=s.length();
int tLen=t.length();
int left=0;
int right=0;
int start=0;
int count=0;
int minLen=sLen+1;
char[] sArr=s.toCharArray();
char[] tArr=t.toCharArray();
int[] have=new int[128];
int[] need=new int[128];
for(int i=0;i<tLen;i++){
need[tArr[i]]++;
}
while(right<sLen){
char r=sArr[right];
if(need[r]==0){
right++;
continue;
}
if(have[r]<need[r]){
count++;
}
have[r]++;//遍历完该字符,窗口要移动了
right++;
//如果这时符合条件
while(count==tLen){
if(right-left<minLen){
minLen=right-left;
start=left;
}
char l=sArr[left];
if(need[l]==0){
left++;
continue;
}
//达到临界点
if(have[l]==need[l]){
count--;//跳出while循环
}
//移动后要减少
have[l]--;
left++;
}
}
if(minLen==sLen+1) return "";
return s.substring(start,start+minLen);
}
}给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。(是数组中的一个连续部分)
代码：
class Solution {
public int maxSubArray(int[] nums) {
int res=Integer.MIN_VALUE;
int count=0;
for(int i=0;i<nums.length;i++){
count+=nums[i];
res=Math.max(res,count);
if(count<0) count=0;
}
return res;
}
}class Solution {
public int maxSubArray(int[] nums) {
int len=nums.length;
int[] dp=new int[len];//dp[i]：下标为i连续子数组的最大和
dp[0]=nums[0];
int count=nums[0]>0?nums[0]:0;
for(int i=1;i<len;i++){
count+=nums[i];
dp[i]=Math.max(dp[i-1],count);
if(count<0) count=0;
}
return dp[len-1];
}
}以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
代码：
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
int len = intervals.length;
List<int[]> list = new ArrayList<>();
list.add(intervals[0]);
int[] temp =intervals[0];//中介
for (int i = 1; i < len; i++) {
temp=list.get(list.size() - 1);
if (intervals[i][0] <= temp[1]) {
temp[1] = Math.max(temp[1],intervals[i][1]);
list.set(list.size() - 1, temp);
} else {
list.add(intervals[i]);
}
}
return list.toArray(new int[list.size()][]);// 注意第一个框内的参数
}
}给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
代码：
方法一：使用额外的数组
class Solution {
public void rotate(int[] nums, int k) {
int len=nums.length;
int [] temp=new int[len];
for(int i=0;i<len;i++){
temp[(i+k)%len]=nums[i];
}
for(int i=0;i<len;i++){
nums[i]=temp[i];
}
}
}方法二：数组翻转
class Solution {//怕k太大溢出
public void rotate(int[] nums, int k) {
int len=nums.length;
k=k%len;
//旋转三次
reverse(nums,0,len-1);
reverse(nums,0,k-1);
reverse(nums,k,len-1);
}
//左闭右闭
public void reverse(int[] nums,int start,int end){
int l=start;
int r=end;
while(l<r){
int temp=nums[l];
nums[l]=nums[r];
nums[r]=temp;
l++;
r--;
}
}
}给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请不要使用除法，且在 O(n) 时间复杂度内完成此题。
代码：
方法一：
class Solution {//用两个数组存放左右的结果，避免重复计算
public int[] productExceptSelf(int[] nums) {
int len=nums.length;
int[] left=new int[len];//前缀积 left[i]:表示i之前的前缀积
int[] right=new int[len];//后缀积
left[0]=1;
for(int i=1;i<len;i++){
left[i]=nums[i-1]*left[i-1];
}
right[len-1]=1;
for(int j=len-2;j>=0;j--){
right[j]=right[j+1]*nums[j+1];
}
int[] ans=new int[len];
for(int i=0;i<len;i++){
ans[i]=left[i]*right[i];
}
return ans;
}
}方法二：
class Solution {
public int[] productExceptSelf(int[] nums) {
int len=nums.length;
int[] ans=new int[len];
ans[0]=1;
int rightSum=1;
for(int i=1;i<len;i++){
ans[i]=nums[i-1]*ans[i-1];
}
for(int j=len-1;j>=0;j--){
ans[j]*=rightSum;
rightSum*=nums[j];
}
return ans;
}
}方法三：
class Solution {
public int[] productExceptSelf(int[] nums) {
int len=nums.length;
int [] ans=new int[len];
Arrays.fill(ans,1);
//双指针
int L=1;
int R=1;
for(int i=0,j=len-1;i<len;i++,j--){
ans[i]*=L;
ans[j]*=R;
L*=nums[i];
R*=nums[j];
}
return ans;
}
}给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
代码：
class Solution {//原地哈希(第一次遍历把1放在下标0，2放在下标1...，第二次遍历如果num[i]!=i+1就为缺失的正整数)
public int firstMissingPositive(int[] nums) {
int len=nums.length;
for(int i=0;i<len;i++){
//确保交换后i上的数组是正确的(i上为负数就不换了)
while(nums[i]>0&&nums[i]<=len&&nums[nums[i]-1]!=nums[i]){
swap(nums,i,nums[i]-1);
}
}
for(int i=0;i<len;i++){
if(nums[i]!=i+1){
return i+1;
}
}
// 都正确则返回数组长度 + 1
return len+1;
}
public void swap(int[] nums,int i,int j){
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
}给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
代码：
方法一：
class Solution {
public void setZeroes(int[][] matrix) {
int l = matrix.length;
int w = matrix[0].length;
int count = 0;
List<int[]> list = new ArrayList<>();
int[] arr=new int[2];
for (int i = 0; i < l; i++) {
for (int j = 0; j < w; j++) {
if (matrix[i][j] == 0) {
//创建一个新的数组对象需要使用new int[]{i, j}的语法
list.add(new int[]{i,j});
}
}
}
for(int[] nums:list.toArray(new int[list.size()][])){
int i=nums[0];
int j=nums[1];
beZero(matrix,i,j);
}
}
public void beZero(int[][] matrix, int i, int j) {
int l = matrix.length;
int w = matrix[0].length;
for (int x = 0; x < w; x++) {
matrix[i][x] = 0;
}
for (int y = 0; y < l; y++) {
matrix[y][j] = 0;
}
}
}方法二：使用标记数组
class Solution {
public void setZeroes(int[][] matrix) {
int m=matrix.length;//行
int n=matrix[0].length;//列
boolean[] row=new boolean[m];
boolean[] col=new boolean[n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(matrix[i][j]==0){
row[i]=true;
col[j]=true;
}
}
}
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(row[i]||col[j]){
matrix[i][j]=0;
}
}
}
}
}给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
代码：
//四个指针转圈圈
//从左到右，顶部一层遍历完往下移一位，top++；
//从上到下，遍历完右侧往左移一位，right--；
//从右到左，判断top <= bottom，即是否上下都走完了。遍历完底部上移，bottom--；
//从下到上，判断left <= right，遍历完左侧右移，left++；
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> ans = new ArrayList<>();
int m = matrix.length, n = matrix[0].length;
int left = 0, right = n - 1, top = 0, bottom = m - 1;
while (left <= right && top <= bottom) {
// 从左到右
for (int i = left; i <= right; i++) {
ans.add(matrix[top][i]);
}
top++;
// 从上到下
for (int i = top; i <= bottom; i++) {
ans.add(matrix[i][right]);
}
right--;
// 从右到左
if (top <= bottom) {
for (int i = right; i >= left; i--) {
ans.add(matrix[bottom][i]);
}
}
bottom--;
// 从下到上
if (left <= right) {
for (int i = bottom; i >= top; i--) {
ans.add(matrix[i][left]);
}
}
left++;
}
return ans;
}
}给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
代码：
class因篇幅问题不能全部显示，请点此查看更多更全内容