目录

前言第一天21. 合并两个有序链表(简单)3. 无重复字符的最长子串(中等)

第二天1. 两数之和(简单)199. 二叉树的右视图(中等)124. 二叉树中的最大路径和(困难)

第三天198. 打家劫舍(中等)15. 三数之和(中等)

第四天53. 最大子数组和(简单)7. 整数反转(中等)*33. 搜索旋转排序数组(中等)*

第五天41. 缺失的第一个正数20. 有效的括号(简单)*103. 二叉树的锯齿形层序遍历(中等)

第六天415. 字符串相加(简单)64. 最小路径和

第六天88. 合并两个有序数组(简单)

前言

将近两年前的学习笔记,由于一直放在草稿箱中,今天将他释放了~~

该学习计划链接如下: 招商银行信用卡的学习计划

以下为我的学习笔记以及汇总,也为了方便其他人更加快速的浏览

这里大部分的题目都是刷过的,本着尽职的态度再次模拟,多刷多刷(#.#)

个别题目太常见或者顺手就来,博主就不放详细题目,只放链接了

第一天

21. 合并两个有序链表(简单)

题目:leetcode:21. 合并两个有序链表

class Solution {

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

ListNode prehead=new ListNode(0);

ListNode pre=prehead;

while(list1!=null&&list2!=null){

if(list1.val>=list2.val){

pre.next=list2;

list2=list2.next;

}else {

pre.next=list1;

list1=list1.next;

}

pre=pre.next;

}

pre.next=list1==null?list2:list1;

return prehead.next;//可以直接用这个节点的next返回,不用再创建多一个节点保存了

}

}

3. 无重复字符的最长子串(中等)

题目:leetcode:3. 无重复字符的最长子串

class Solution {

public int lengthOfLongestSubstring(String s) {

Set set=new HashSet<>();

int rk=-1,sum=0;

for(int i=0;i

if(i!=0){

set.remove(s.charAt(i-1));

}

while(rk+1

set.add(s.charAt(rk+1));

rk++;

}

sum=Math.max(sum,rk-i+1);

}

return sum;

}

}

第二天

1. 两数之和(简单)

题目:leetcode:1. 两数之和

class Solution {

public int[] twoSum(int[] nums, int target) {

Mapmap=new HashMap<>();

for(int i=0;i

if(map.containsKey(target-nums[i])){

return new int[]{map.get(target-nums[i]),i};

}

map.put(nums[i],i);

}

return new int[0];

}

}

199. 二叉树的右视图(中等)

题目:leetcode:199. 二叉树的右视图

class Solution {

public List rightSideView(TreeNode root) {

Listlist=new ArrayList<>();

if(root==null) return list;

Queue que=new LinkedList<>();

que.offer(root);

while(!que.isEmpty()){

int n=que.size();

for(int i=0;i

TreeNode node=que.poll();

if(i==n-1)list.add(node.val);

if(node.left!=null)que.offer(node.left);

if(node.right!=null)que.offer(node.right);

}

}

return list;

}

}

124. 二叉树中的最大路径和(困难)

题目:leetcode:124. 二叉树中的最大路径和

要记住返回的值,所以使用后序递归是最合适的了

class Solution {

int max=Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {

dfs(root);

return max;

}

public int dfs(TreeNode root){

if(root ==null)return 0;

/*

int left=dfs(root.left);

int right=dfs(root.right);

*/

/*

之所以不用上面那个操作主要是,为了保证每一步都是大于0,如果小于0,直接返回0即可

*/

int left=Math.max(dfs(root.left),0);

int right=Math.max(dfs(root.right),0);

//计算左右边界的值,本身已经默认大于0了,所以max比较最大值,在主函数中,返回max比较即可。

//这和递归的条件不影响,递归只是返回单边最大的值而已,条件不能弄混

int sum=left+right+root.val;

max=Math.max(max,sum);

//确定递归回去的条件,只能返回单边值

return root.val+Math.max(left,right);

}

}

第三天

198. 打家劫舍(中等)

题目:leetcode:198. 打家劫舍

class Solution {

public int rob(int[] nums) {

//因为创建了dp数组,前面两个数组的个数要做一个判断比较

//为空或者长度为0,都返回为0

if (nums == null || nums.length == 0) {

return 0;

}

int n=nums.length;

//如果数组长为1,则返回第一个

if (n == 1) {

return nums[0];

}

int []dp=new int [n];

dp[0]=nums[0];

//返回最大的那个,初始条件如果只有两个房屋,返回最大的那个

dp[1]=Math.max(nums[0],nums[1]);

//通过动态规划的公式,相邻两间屋的最大值

for(int i=2;i

dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);

}

//输出动态规划数组的最后一个值,即可为最大

return dp[n-1];

}

}

15. 三数之和(中等)

题目:leetcode:15. 三数之和

class Solution {

public List> threeSum(int[] nums) {

List> list =new ArrayList>();

int n=nums.length;

Arrays.sort(nums);

for(int i=0;i

if(nums[i]>0)break;//大于0,则后面的数字也是大于零(排序后是递增的)

if(i!=0 && nums[i] == nums[i-1])continue;// 代表第一个值重复了,去重

int left=i+1;

int right=n-1;

while(left

int sum=nums[left]+nums[right]+nums[i];

if(sum==0){

//创建一个空的列表

/*

Listsonlist=new ArrayList<>();

sonlist.add(nums[i]);

sonlist.add(nums[left]);

sonlist.add(nums[right]);

list.add(sonlist);

*/

// 将其数组转换为列表,二者选择其一,跟上面的代码

list.add(new ArrayList<>(Arrays.asList(nums[i],nums[left],nums[right])));

while(left

while(left

}else if(sum<0){

while(left

}else if(sum>0){

while(left

}

}

}

return list;

}

}

第四天

53. 最大子数组和(简单)

题目:leetcode:53. 最大子数组和

class Solution {

public int maxSubArray(int[] nums) {

int n=nums.length;

int pre=0;

int max=Integer.MIN_VALUE;

// 或者使用 int max=nums[0];

for(int i=0;i

pre=Math.max(pre+nums[i],nums[i]);

max=Math.max(pre,max);

}

return max;

}

}

7. 整数反转(中等)*

题目:leetcode:7. 整数反转

大致题目意思是: 给你一个 32 位的有符号整数 x ,返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ,就返回 0。

假设环境不允许存储 64 位整数(有符号或无符号)。

核心代码主要是这一块:

// 弹出 x 的末尾数字 rev

rev = x % 10;

x /= 10;

// 将数字 rev 推入 res 末尾

res = res * 10 + rev;

最主要是数字会溢出,所以数字的判断条件比较关键:

class Solution {

public int reverse(int x) {

//返回最后的总数

int res=0;

while(x!=0){

//因为反转的时候res会慢慢开始越界,所以在此处进行判断 倒数第二个数

if(res>Integer.MAX_VALUE/10 || res

//求余判断条件

int rev=x%10;

//除数判断的条件

x=x/10;

res=res*10+rev;

}

return res;

}

}

33. 搜索旋转排序数组(中等)*

题目:leetcode:33. 搜索旋转排序数组

class Solution {

public int search(int[] nums, int target) {

int n=nums.length;

int left=0,right=nums.length-1;

//等于号不要漏掉

while(left<=right){

int mid=left+(right-left)/2;

//不要少掉这个条件

if(nums[mid]==target)return mid;

//注意初值条件,左边界此处都是等于号,而且和nums【mid】作比较,target嵌入其中

if(nums[0]<=nums[mid]){

if(nums[0]<=target && target

right=mid-1;

}else {

left=mid+1;

}

}else {

//此处的等于号是在nums【n-1】作比较,

if(nums[mid]

left=mid+1;

}else {

right=mid-1;

}

}

}

//如果循环结束后条件不满足 则返回-1

return -1;

}

}

第五天

41. 缺失的第一个正数

题目:leetcode:41. 缺失的第一个正数

class Solution {

public int firstMissingPositive(int[] nums) {

int n=nums.length;

//将其小于等于0的数都变为n+1,因为之后用不到

for(int i=0;i

if(nums[i]<=0)nums[i]=n+1;

}

// 再一次遍历,类似哈希,将其元素标记在数组下标中

// 置为负值,为了不让负变正,每次都是取绝对值,在变负,解决上面的疑惑

for(int i=0;i

int num=Math.abs(nums[i]);

//此处判断的数字都是小于等于n的,也就是【1,n】

if(num<=n)nums[num-1]=-Math.abs(nums[num-1]);

}

//如果遇到正数,说明其下标还未被标记,所以是i+1

for(int i=0;i

if(nums[i]>0)return i+1;

}

//如果没有被标记到,则将其n+1

return n+1;

}

}

置换的做法:

class Solution {

public int firstMissingPositive(int[] nums) {

int n=nums.length;

//将其数组值对应放到数组下标中

for(int i=0;i

//无限在这里置换 只有不等的时候才需要操作置换

while(nums[i]>0 && nums[i]<=n && nums[nums[i]-1]!=nums[i]){

int temp=nums[nums[i]-1];

nums[nums[i]-1]=nums[i];

nums[i]=temp;

}

}

//类似哈希的存储,如果不等于i+1的时候 就返回第一个正数

for(int i=0;i

if(nums[i]!=i+1)return i+1;

}

return n+1;

}

}

20. 有效的括号(简单)*

题目:leetcode:20. 有效的括号

class Solution {

public boolean isValid(String s) {

//临界条件 奇数个数排除

if(s.length()%2!=0)return false;

int n=s.length();

Mapmap=new HashMap<>(){

{

//注意此处为put而不是map.put函数

put(')','(');

put(']','[');

put('}','{');

}

};

Stackstack=new Stack<>();

for(int i=0;i

//此处的条件是如果包含了这个key,也就是可能栈中有左括号

if(map.containsKey(s.charAt(i))){

//判断栈如果为空或者是获取这个节点对应的value中不是等于peek值,说明为false

//之所以判断false条件是 因为如果不是可以直接返回结果

if(stack.isEmpty() || map.get(s.charAt(i))!=stack.peek()){

return false;

}

stack.pop();

}else{

//如果没有包含则进栈

stack.push(s.charAt(i));

}

}

//最后的返回条件是栈是否为空

return stack.isEmpty();

}

}

103. 二叉树的锯齿形层序遍历(中等)

题目:leetcode:103. 二叉树的锯齿形层序遍历

class Solution {

public List> zigzagLevelOrder(TreeNode root) {

List> list=new ArrayList>();

if(root==null) return list;

Queue que=new LinkedList<>();

que.offer(root);

int ans=0;

while(!que.isEmpty()){

int n=que.size();

Listsonlist=new ArrayList<>();

for(int i=0;i

TreeNode node=que.poll();

sonlist.add(node.val);

if(node.left!=null)que.offer(node.left);

if(node.right!=null)que.offer(node.right);

}

ans++;

if(ans%2==0)Collections.reverse(sonlist);

list.add(sonlist);

}

return list;

}

}

第六天

415. 字符串相加(简单)

题目:leetcode:415. 字符串相加

class Solution {

public String addStrings(String num1, String num2) {

int l1=num1.length()-1;

int l2=num2.length()-1;

int add=0;

StringBuilder sb=new StringBuilder();

while(l1>=0||l2>=0|add!=0){

//判断格式是这样的

int x=l1>=0?num1.charAt(l1)-'0':0;

int y=l2>=0?num2.charAt(l2)-'0':0;

int sum=x+y+add;

sb.append(sum%10);

add=sum/10;

l1--;

l2--;

}

sb.reverse();

return sb.toString();

}

}

64. 最小路径和

题目:leetcode:64. 最小路径和

class Solution {

public int minPathSum(int[][] grid) {

//初始值判断

if (grid == null || grid.length == 0||grid[0].length==0) {

return 0;

}

int m=grid.length;

int n=grid[0].length;

int [][]dp=new int [m][n];

//赋值一个值,主要用来求边界想加点

dp[0][0]=grid[0][0];

//边界处理

for(int i=1;i

dp[i][0]=dp[i-1][0]+grid[i][0];

}

for(int i=1;i

dp[0][i]=dp[0][i-1]+grid[0][i];

}

for(int i=1;i

for(int j=1;j

//需求最小的边界,而且是邻接边

dp[i][j]=Math.min(dp[i][j-1],dp[i-1][j])+grid[i][j];

}

}

return dp[m-1][n-1];

}

}

第六天

88. 合并两个有序数组(简单)

题目:leetcode:88. 合并两个有序数组

class Solution {

public void merge(int[] nums1, int m, int[] nums2, int n) {

//逆序存放主要是不会被覆盖

//a b都是有效数组下标开始

int a = m - 1, b = n - 1;

int tail = m + n - 1;

//有效数组的个数大于等于0开始

while(a>=0 ||b>=0) {

//如果数组下标等于-1,既越界,直接tail--存放b数组或者对应的a数组

if (a == -1) {

nums1[tail--] = nums2[b--];

} else if (b == -1) {

nums1[tail--] = nums1[a--];

} else if (nums1[a] > nums2[b]) {

nums1[tail--] = nums1[a--];

} else {

nums1[tail--] = nums2[b--];

}

}

}

}

推荐阅读

评论可见,请评论后查看内容,谢谢!!!评论后请刷新页面。