每日算法

Leetcode

两数相加(2021-11-26)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        //使用hashmap进行两数相加
        /**
            思想：主要就是map里面的核心方法containsKey，这个方法
            判断这个键是否存在，如果存在，那么就通过map的get方法获
            取值也就是下标，返回，否则就将数据存到map中，进行下一次
            查询判断
         */
         HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
         for(int i =0;i<nums.length;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];
    }
}

整数反转(2021-11-27)

class Solution {
    public int reverse(int x) {
        /**
            可以通过字符串进行，但是如果考虑性能问题
            还是选择对这个整数进行取余的操作
            思路：用取余的方式可以得到尾数，然后将这个
            尾数记录，如果下一次再次进入循环，那么将尾
            数进行移位并且加上取余的数
         */

        //标志位,long类型很重要，最后判断越界异常
         long  n =0;
         while(x !=0){
             //将每次得到的尾数进行记录
             n = n*10 +x %10;
             //每次都会减少一个尾数
             x = x/10;
         }
         //判断是否有越界
         return (int) n == n?(int)n:0;
    }
}

两数相加(2021-11-29)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
 /**
    核心思想：
        首先判断两个链表是否为空以及是否有进位标志，如果有那么就需要进行增加节点操作，
        增加节点首先判断两个链表当前是否有值，如果有则使用当前值，如果没有则使用0当做
        当前值，然后对当前两个链表的值相加，如果有进位那么将进位也一起想加，得到的
        值先进行除以10的操作，主要就是判断当前所得的值是否大于10，如果大于则记录当前
        进位，如果不大于则为0，然后将这个值进行取余操作，存入到链表中，然后更新链表
        指针，进行下一轮扫描执行操作

  */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //新建链表
        ListNode l3 = new ListNode(0);
        //建立一个指针操作链表
        ListNode root = l3;
        //进位标志
        int c = 0;
        while(l1!=null||l2!=null||c!=0){
            //记录当前两个链表的值
            int l1val = l1!=null?l1.val:0;
            int l2val = l2!=null?l2.val:0;
            //相加(注意添加进位标志)
            int sumval = l1val + l2val + c;
            //重新计算进位标志
            c = sumval/10;
            //将sumval添加到新建的链表中
            root.next = new ListNode(sumval%10);
            root = root.next;
            //然后判断链表是否为空，进行下一次循环
            if(l1!=null) l1 = l1.next;
            if(l2!=null) l2 = l2.next;
        }
        //返回结果
        return l3.next;
    }
}

无重复字符串的最长子串（2021-12-02）

class Solution {
    public int lengthOfLongestSubstring(String s) {
        /**
        核心思想：使用hashmap来解决此问题
            主要是将字符串存到map中，在扫描的过程中判断每次存的字符串是否重复，
            如果重复就将上一次出现这个值得位置+1，这样就能从新的位置开始扫描，

         */

        //创建一个新数组
         HashMap<Character,Integer> map = new HashMap<>();
        //初始化最大长度
        int max = 0;
        //初始化开始扫描的位置
        int start = 0;

        //通过循环将数据添加进map中，并且进行扫描
        for(int i = 0;i<s.length();i++){
            //将插入的值记录
            char c = s.charAt(i);
            //首先判断map中是否存在要插入的值
            if(map.containsKey(c)){
                //如果存在，那么就需要更新开始扫描的位置
                //将开始位置更新为当前重复元素的上一次出现位置的下一个位置
                start = Math.max(start,map.get(c)+1);
            }
            //更新max的值
            max = Math.max(max,i-start+1);
            //将数据添加进map中，注意这里如果key重复了，那么就会用最新的值覆盖之前的值
            map.put(c,i);
        }
        return max;
    }
}

用两个栈来实现队列（2021-12-8）

class CQueue {

    //初始化两个栈
    Stack<Integer> stack1;
    Stack<Integer> stack2;

    public CQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    /**
    阐述一下思想：
        使用两个栈实现队列，首先要知道的是栈是先进后出，而队列是先进先出的
        其次就是队列是队头移除，队尾插入
        
    如何实现？
        在入队的时候，就是普通的入栈操作，但是出队就需要将栈的顺序反过来，
        意思就是比如现在添加了几个元素1，2，3，4，5，在栈中的顺序是5，4，3，2，1
        现在进行队列的删除操作，也就是将对头的1进行移除，那么此时就需要
        借助第二个栈，将栈1的数据都弹出存到栈2，这样顺序就变成了1，2，3，4，5
        移除操作就是删除栈2的栈顶元素

     */
    
    public void appendTail(int value) {
        stack1.push(value);
    }
    
    public int deleteHead() {
        /**
            删除元素首先得判断栈2是否有元素，如果有就直接弹出
            如果没有就需要将栈1的数据压到栈2，如果栈1的数据是
            空,就返回-1，意思就是没有数据
         */
         if(!stack2.isEmpty()){
             return stack2.pop();
         }
         while(!stack1.isEmpty()){
             stack2.push(stack1.pop());
         }

         return stack2.isEmpty()?-1:stack2.pop();


    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

包含min函数的栈(2021-12-8)

class MinStack {

    /**
        思路：
            因为栈的底层数据结构可以是数组，也可以是链表，或者是其他的
            这里因为有最小函数的出现，所以采用链表比较好，因为在链表中
            可以开辟空间存储头部节点以及最小值节点
    
     */
     
     //初始化一个头结点
    private Node head;

    /** initialize your data structure here. */
    public MinStack() {
        
    }
    
    public void push(int x) {
        //判断头结点是否为空，如果为空就进行初始化
        if(head==null){
            head = new Node(x,x,null);
        }else{
            //不为空，那么就需要比较大小，记录最小值
           head = new Node(x,Math.min(x,head.min),head);
           
        }
    }
    
    public void pop() {
        head = head.next;

    }
    
    public int top() {
        return head.val;

    }
    
    public int min() {
        return head.min;

    }
}

//定义节点信息，包含最小值
class Node{
    int val;
    Node next;
    int min;
    public Node(int val,int min,Node next){
        this.val = val;
        this.next = next;
        this.min = min;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */

从尾到头打印链表（2021-12-9）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
 /**
    思路：
        1. 本来自己做的话想的是使用栈，然后取出用数组存储，但是这样
        就使用了额外的内存
        2. 借鉴思想，反正都是要循环两次解决问题，为什么要创建额外的
        空间存储呢？直接使用倒序插入数组就好了
 
  */
class Solution {
    public int[] reversePrint(ListNode head) {
        ListNode index = head;
         //记录链表的长度，以便创建新的数组长度来存储链表节点
         int size = 0;
         while(index!=null){
             //遍历链表，记录链表长度
             size++;
             index = index.next;
         }
         int [] array = new int[size];
         for(int i =size-1;i>=0;i--){
             array[i] = head.val;
             head = head.next;
         }
         return array;


    }
}

反转链表（2021-12-13）

使用迭代

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        /**
            使用迭代的方式将链表反转
            主要思想：因为节点连接的都是下一个节点，此时将next节点指向pre节点，即可完成链表反转

         */
        
        //记录前面的节点
        ListNode pre  = null;
        //记录当前节点
        ListNode cur = head;

        //遍历链表，并且将指向后面的节点改成指向前面节点，这样就完成倒序了
        while(cur!=null){
            //记录下一个节点
            ListNode next = cur.next;
            //将节点指向改变
            cur.next = pre;
            //指针更新
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

使用递归

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        /**
            使用递归的方式将链表反转
         */
        
        if(head==null||head.next==null){
            return head;
        }

        ListNode reverse = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return reverse;
    }
}

替换空格（2021-12-13）

class Solution {
    public String replaceSpace(String s) {
        /**
            因为涉及到String的拼接操作，这里考虑使用Stringbuilder进行操作
            如果判断到是空格，那么就进行替换操作
        
         */

        if(s==null){
            return null;
        }

        //存储字符串
         StringBuilder sb = new StringBuilder();

        for(int i = 0; i<s.length();i++){
            if(" ".equals(String.valueOf(s.charAt(i)))){
                sb.append("%20");
            }else{
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }
}

左旋转字符串（2021-12-13）

/*
	解题思路：主要就是使用substring这个函数进行字符串分割然后拼接
*/

class Solution {
    public String reverseLeftWords(String s, int n) {
        if(s==null)
        return null;
        return s.substring(n)+s.substring(0,n);
    }
}

数组中重复的数据（2021-12-13）

class Solution {
    public int findRepeatNumber(int[] nums) {
        /**
            解题思路：
                （一开始想的就是存储在map或者set里，这样只要检测到有重复的key那么直接，返回当前重复的值即可，但是效率太低了）
                根据大佬的思路，首先创建一个新数组，巧妙运用数组初始化时各个下标对应的值都是0
                因此我们可以通过将数组的值作为新数组的下标进行存储，并且这个下标对应的值+1
                那么下一次再遇到同样的下标，也就是重复的数据，我们可以通过这个下标对应的值
                来判断该数据是否重复（也就是如果此时下标对应的值大于1那么就是重复数据）
         */

         //创建一个新数据
         int [] array = new int[nums.length];

         for(int i =0;i<nums.length;i++){
             array[nums[i]]++;
             //判断如果大于1就是重复数据，直接返回即可
             if(array[nums[i]]>1)
             return nums[i];
         }
         return 0;
    }
}