0%

Posted on Edited on In

1. 题目描述

题目描述

  • 概述：

2. 我的解法

1
class Solution {
2
    public int lengthOfLongestSubstring(String s) {
3
        if(s==null||s.equals("")) return 0;
4
        int Max=1;
5
        for(int i=0;i<s.length();i++)
6
        {
7
            for(int j=i+1;j<s.length();j++)
8
            {
9
if(s.substring(i,j).indexOf(String.valueOf(s.charAt(j)))==-1) 
10
                    Max=(Max>=(j-i+1))?Max:(j-i)+1;
11
                else break;
12
            }
13
        }
14
        return Max;
15
    }
16
}

时间复杂度：最坏到达O($n^2$)

3 解法二

  1. 我的解法存在一点问题：每次第二层循环结束时j都回到i+1的位置。
  2. 改进：由于之前的探索可知i-j之间存在与j位重复的字符，那么下一次循环的时候，j的位置可以固定不动，移动i至重复字符的下一位即可。
1
class Solution {
2
    public int lengthOfLongestSubstring(String s) {
3
        if(s==null||s.equals("")) return 0;
4
        int Max=1 , n = s.length() , sub = 0;
5
        for(int i=0,j=i+1 ; i<n&&j<n ;j++)
6
        {//每次都探索新的j
7
            int reindex=s.substring(i,j).indexOf(s.charAt(j));
8
            if(reindex == -1) 
9
                Max=(Max>=(j-i+1))?Max:j-i+1;
10
            else
11
            {
12
                i = sub+reindex +1;//移到重复位置的下一位
13
                sub = i;//寻找i在s中移动的位置，reindex只是子字符串总的位置
14
            }
15
        }
16
        return Max;
17
    }
18
}
  • 时间复杂度：O(n)

4 解法四

巧用hashmap。
采用i跳跃的方式，维护hashmap中的键值对。

  • 如果没有重复字符，则向map中加入新的j位置的字符，value值为如果发生重复，i需要跳转到的位置。其实也是不断更新对应字符的下一次跳转位置。
  • 如果发生重复，i跳转的规则是取当前位置和重复字符所在位置的下一个位置的最大值。因为map在去字串时没有删除之前的字符。这样做的目的是为了防止，当前重复的字符其实并没有包含在当前字串中，而是之前遗留的字符，防止i倒退。
    1
    public class Solution {
    2
        public int lengthOfLongestSubstring(String s) {
    3
            int n = s.length(), ans = 0;
    4
            Map<Character, Integer> map = new HashMap<>(); 
    5
            for (int j = 0, i = 0; j < n; j++) {
    6
                if (map.containsKey(s.charAt(j))) {
    7
                    i = Math.max(map.get(s.charAt(j)), i); //采用i跳跃
    8
                }
    9
                ans = Math.max(ans, j - i + 1);
    10
                map.put(s.charAt(j), j + 1);//下标 + 1 代表 i 要移动的下个位置
    11
            }
    12
            return ans;
    13
        }
    14
    }
  • 时间复杂度：O(n)
  • 空间复杂度：O(m)

更多解法，看题解

5. 扩展

5.1 Java - String valueOf() Method

题目描述 Method .png)
这个方法的作用就是将其他的类型转化为string的形式，包括将boolean char char[] doubel float int long Object

5.2 Java String indexOf()

返回输入文本的在string中的下标

  1. 输入一个char，输出该char在字符串中对应的下标
    题目描述1.png)
  2. 输入插入和你strt值，从字符串的strt位置开始查找输入的字符第一次出现的下标
    题目描述2.png)
  3. 可以查找substring 对应的下标的方法
    题目描述3.png)
  4. 可以从指定位置开始查找substring，输出下标
    题目描述4.png)

Posted on Edited on In

1. 题目描述

题目描述

  • 概述：两个逆序存储的非零开头的数字链表，求两数之和，输出也是逆序的链表

  • leetcode 01 02两个题分别考察了列表在物理存储层面的两种表示方式：数组和链表 的加法

    2. 我的解法

    暴力：按顺序同时遍历两个链表，按照进位规则进行加法运算，同时需要注意两个数维数不等，以及结果可能维数增加的情况 我的问题是，代码太过复杂：
    • a. 在初始化L3时，由于不是控制，需要另外计算存储值。应该设立空的表头，放到循环中值。
    • b. 在循环之外，分别判断了当两个值不等长时的情况，可以归并到循环中，减少代码函数
      1
       /* Definition for singly-linked list.
      2
       * public class ListNode {
      3
       *     int val;
      4
       *     ListNode next;
      5
       *     ListNode(int x) { val = x; }
      6
       * }
      7
       */
      8
      class Solution {
      9
          public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
      10
              int num=l1.val+l2.val;
      11
              ListNode l3 =new ListNode(num%10); 
      12
              ListNode head=l3;
      13
              //同时遍历两个链表
      14
              while(l1.next!=null&&l2.next!=null)
      15
              {
      16
                  l1=l1.next;
      17
                  l2=l2.next;
      18
                  num=l1.val+l2.val+num/10;//加上进位
      19
                  l3.next=new ListNode(num%10);//超出10，求余
      20
                  l3=l3.next;
      21
              }
      22
              //如果两个链表不等长，即两个数位数不同，剩下的分别遍历
      23
              while(l1.next!=null)
      24
              {
      25
                  l1=l1.next;
      26
                  num=l1.val+num/10;
      27
                  l3.next=new ListNode(num%10);
      28
                  l3=l3.next;
      29
              }
      30
              while(l2.next!=null)
      31
              {
      32
                  l2=l2.next;
      33
                  num=l2.val+num/10;
      34
                  l3.next=new ListNode(num%10);
      35
                  l3=l3.next;
      36
              }
      37
              //最后如果相加多出一位，别忘了加上
      38
              if(num/10!=0)
      39
                  l3.next=new ListNode(num/10);
      40
              return head;
      41
          }
      42
      		}
  • 时间复杂度：O(max(m,n))
  • 空间复杂度： O(max(m,n))

    3. 解法二

    解决我的解法的问题
    1
    class ListNode {
    2
        int val;
    3
        ListNode next;
    4
        ListNode(int x) { val = x; }
    5
    }
    6
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    7
        ListNode dummyHead = new ListNode(0);//设置空的链表头
    8
        ListNode p = l1, q = l2, curr = dummyHead;
    9
        int carry = 0;
    10
        while (p != null || q != null) {
    11
            int x = (p != null) ? p.val : 0;//当不等长时，补充相应值0
    12
            int y = (q != null) ? q.val : 0;
    13
            int sum = carry + x + y;
    14
            carry = sum / 10;
    15
            curr.next = new ListNode(sum % 10);
    16
            curr = curr.next;
    17
            if (p != null) p = p.next;
    18
            if (q != null) q = q.next;
    19
        }
    20
        if (carry > 0) {
    21
            curr.next = new ListNode(carry);
    22
        }
    23
        return dummyHead.next;
    24
    }

  • 时空复杂度不变

    3. 扩展

    如果链表存储的顺序反过来怎么办？
    我首先想到的是链表先逆序计算，然后将结果再逆序呗，这就转换到我们之前的情况了。不知道还有没有其他的解法。

  • 3.1 下边是单链表逆序的代码。

1
//逆序
2
   	ListNode pre = null;
3
     ListNode head = node;
4
     while(head!=null)
5
     {
6
         ListNode next = head.next;//保留下一个节点，防丢失
7
         head.next =pre;//新head接上
8
         pre = head;//pre指针指向新head
9
         head = next;//原列表更换head
10
     }
  • 3.2 递归思路，单列表逆序
    1
    public ListNode reverseListRecursion(ListNode head) {
    2
            ListNode newHead;
    3
            if(head==null||head.next==null ){
    4
                return head;
    5
            }
    6
            newHead=reverseListRecursion(head.next); 
    7
            head.next.next=head; //目前的head.next指向newhead的最后一个节点
    8
            head.next=null;
    9
            return newHead;
    10
        }

    4. 参考列表

  1. 题解-wang

Posted on In

一、前言

在leetcode-01-两数之和的题目中，提到了hash table 在查找方面提高时间复杂度的表现。本片文章是对hashmap进行详细的学习。

二、java中其他数据结构在新增和查找方面的表现

  1. 数组：
    • 1.1 无序数组：
      • 查找：时间复杂度时O(n)
      • 新增：时间复杂度O(1)
    • 1..2 有序数组
      • 查找：使用二分查找，差值查找，斐波那契查找等方式，可将查找复杂度提高为O(logn)。但当实际需要插入删除操作时，由于涉及到数组元素的移动，平均时间复杂度为O(n)
  2. 线性链表：
    • 查找：O(n)
    • 新增: O(1) ,因为仅需引用变换，无序元素移动

  3. 二叉树：（本质：物理组织结构为链表）

    • 插入&查找&删除：O(logn)
  4. 哈希表：（本质：主干物理组织结构是数组）
    • 查找：O(1) 当不存在哈希冲突时

三、HashMap

  1. 哈希函数和哈希冲突

    • HashMap利用哈希函数：hash表使用了数组的形式，当涉及到查找的时候，通过哈希函数计算的hash值，可以快速得到值对应的数组下标，定位到相应元素，时间复杂度为O(1)

    • 解决哈希冲突：不可避免。哈希冲突的解决方案有多种:

      • 开放定址法（发生冲突，继续寻找下一块未被占用的存储地址）
      • 再散列函数法 ?
      • 链地址法 ?

      而HashMap即是采用了链地址法，也就是数组+链表的方式

  2. 数据+链表的HashMap结构图

hashmap数组加链表结构

数组是hashmap的主体，链表是为了解决哈希冲突。如果定位到的数组位置不含链表（当前entry的next指向null）,那么查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。

之后有介绍了hashmap在不同的构造器下，新增put和查找get的具体步骤,源码解析。目前还不需要了解这么深入。待进一步学习。

参考列表

  1. 深入浅出学Java——HashMap

Posted on Edited on In

1. 题目描述

题目描述

  • 概括：已知数组A和目标值T，在A中找到两个和为T的两个值。输出两个值的下标
  • 前提：数组中一定有解且有唯一解，不能重复利用数组元素。

2. 我的解法

暴力解法 ：双重循环，遍历数组nums，直到找到两个和为target的值，输出下标

1
class Solution {
2
    public int[] twoSum(int[] nums, int target) {
3
        for(int i=0;i<nums.length;i++)
4
            for(int j=i+1;j<nums.length;j++)
5
                if(nums[i]+nums[j]==target)
6
                {
7
                    return new int[]{i,j};//快速建立数组方法
8
                }
9
        return new int[]{0,0};//若没找到，就随便输出两个值，应该不可能有这种情况
10
        }
11
            
12
    }
  • 时间复杂度：O（ ）
  • 空间复杂度： O（1）

3. 解法二

充分利用hash table ：

  • 原解法：在我的解法的第二层循环主要是为了找到一个值，使两值相加为target。这个值可以理解为sub = target - nums[i]。第二层循环的时间复杂度为O(n)。

  • 新解法：利用哈希表可以避免循环，直接找到列表中某个值的特性，把数组的每个元素保存为 hash 的 key，下标保存为 hash 的 value ，这样只需判断 sub 在不在 hash 的 key 里就可以了。可使第二层时间复杂度将为O(1)。

    注意需判断哈希表找到的值是否和第一重循环找到的值相同，即 i = j

    1
    public int[] twoSum(int[] nums, int target) {
    2
      	//建立hash table
    3
        Map<Integer,Integer> map=new HashMap<>();
    4
        for(int i=0;i<nums.length;i++){
    5
            map.put(nums[i],i);
    6
        }
    7
      	//只需一重循环便可找到两个值
    8
        for(int i=0;i<nums.length;i++){
    9
            int sub=target-nums[i];
    10
          	//需判断找到的值是否是i
    11
            if(map.containsKey(sub)&&map.get(sub)!=i){
    12
                return new int[]{i,map.get(sub)};
    13
            }
    14
        }
    15
        throw new IllegalArgumentException("No two sum solution");
    16
    }
  • 时间复杂度：O(n)
  • 空间复杂度： O(n) 空间换时间

3. 解法三

算法二的简化版 ：不需要判断hash找到的值是否与第一个值相同。复杂度不变。相当于在一重循环中，不断往前找hash值

1
public int[] twoSum(int[] nums, int target) {
2
    Map<Integer,Integer> map=new HashMap<>();//hash无需提前加入
3
    for(int i=0;i<nums.length;i++){
4
        int sub=target-nums[i];
5
        if(map.containsKey(sub)){
6
            return new int[]{i,map.get(sub)};
7
        }
8
        map.put(nums[i], i);//无需判断重复，因判断时当前值还没加入
9
    }
10
    throw new IllegalArgumentException("No two sum solution");
11
}

总结

hash table 的利用，在一维列表中减少时间复杂度，直接查找某个值非常方便

扩展

HashMap

利用如下代码创建hashmap，自动根据建立相应key值的hash值。

1
Map<Integer,Integer> map=new HashMap<>()
2
map.put(nums[i],i)
3
//通过key值查找列表位置，隐藏了key值转换hash值，及hash对应的过程
4
map.containsKey(sub)//判断是否含有key值
5
map.get(sub)//去除该key值的索引号（下标）

hashmap的使用还待之后进一步总结

参考列表

  1. leetcode-两数之和
  2. 解决方案-wang
  3. 扩展-深入浅出学Java——HashMap

Posted on Edited on In

[TOC]

美剧推荐

  1. 《绝望主妇》 — 《致命女人》
  2. 摩登家族

一、程序员学长谈9月校招找工作制胜之道！全是拿分题哦！

1. 信息获取渠道

  • 1.1 牛客网
  • 1.2 百度，网易，bilibili官网网站

2. 技术学习（重要性按顺序）

  • 2.1 基础知识

    • 数据结构和算法——最重要
    • 一门编程语言——语言的细节和机制的原理
    • 计算机网络——协议的细节
    • 操作系统——只需了解基础原理和概念，如内存置换，线程调度，磁盘原理
    • 数据库——SQL，如索引的基本原理等等

  • 2.2 项目经验

  • 2.3 实习经验

3. 公司

  • 3.1 技术公司，BAT，等互联网公司
  • 3.2 银行，铁路，移动，国家机关和事业单位

4. 心态调整

- 4.1. 运气

二、github使用

1. 掌握git，使用git管理自己的代码，整理git的命令

三、视频演示如何玩转一个开源项目｜如何运行+如何读代码｜顺便讲讲IDEA和Springboot

  1. 首先讲解了几个java的开源项目
  2. 介绍在intelliJ IDEA 运行“目前最完美的博客”halo项目的运行，讲解IDEA的基本操作

四、学技术真有那么费劲？我的学习秘诀大公开！在职程序员聊聊该如何学习技术以及如何掌握一门新技术。

  1. 认知，了解（第一印象）。
    • 如springboot是干什么的，解决什么问题
    • 同类的技术有哪些，如Web后端常用技术框架为Spring Boot（java），beego（Go），flask、diango（python），thinkphp（PHP）
    • 了解该技术的重要组成部分，如Spring框架：IOC容器，AOP切面
    • 思考一下该技术为什么会出现
  2. 学语法，学用法
    在买书看之前做的事情：
    • 途径1: 视频教程
    • 途径2: 快速上手视频
    • 看别人写的入门博客
    • 买书看
    • 官方文档

      在这个过程中多思考，提炼，总结，写博客

  3. 局部的练习，小型实战，环境搭建
    如书中例子，官网示例，实战demo，如作者开源的一个github库有很多学习Springboot的小demo

    注意：遇到坑及时记录。多写博客

  4. 上手实际项目或开源项目。基础牢固，包括网络知识，数据结构。作者介绍了很多的Java，c和公众号中的python开源项目
  5. 造轮子，手撸源码

Posted on Edited on In

基本操作

  1. 用# ## ### 区分标题一共六级，[toc]做目录

  2. 为引用
    可以多集嵌套

  3. 斜体 ，加粗 删除线 双波浪实现

  4. 表情符号 :happy: :cry:

    —- 分割线

    表格

    | nishi | wo |
    | :—— | :—- |
    | 2 | 3 |

  5. 超链接

  6. 用 打出LaTex数学公式

  7. 1
    def functiong():
    2
    pass
    • nihao
    • wo

Posted on Edited on

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment