Shawni's Blog

2、二分法二分法是一种能极大节省查找时间复杂度的算法，使用条件： 数组为有序数组 数组中没有重复元素 2.1 Leetcode 例题二分查找 二分查找此类题目 关键点在于找对区间，找好临界值点，可分为两种情况 1. 区间为左闭右闭类型此时 ``while left <= right`` 需要取等，因为此时相等时的mid值有意义可以取到，当``nums[mid]>target``时·，``right = mid-1``，因为此时mid下标所指的值一定不等于target所以可以往前再移一位。 1234567891011121314151617181920212223class Solution { public int search(int[] nums, int target) { int left = 0; int right = nums.length-1; while(left <= right) { int mid = (left + right) / 2; ...

环形链表环形链表 此题解题思路分为两部分 1. 判断链表中是否有环可以使用快慢指针法，slow 每次往前走一格，fast 每次往前走两格。这样每次 fast 会比 slow 多走一格，相当于往前去追 slow ，若存在环，则 slow 和 fast 一定会相遇，定义其相遇的节点为 相遇节点 index1。 可设距离如下图所示，则 slow 走过的距离为 $x+y$ , fast 走过的距离为 $x+y+n(y+z)$，而 fast 走过的距离应该是为 slow 的两倍，所以有 $2*(x+y) = x+y+n(y+z)$ 最后可得 $$x+y = n(y+z)$$ 要寻找的节点是起始节点，也就是要寻找 $x$ 的值，化简上述式子可得 $$x = (n-1)(y+z)+z$$ 当 $n=1$ 时，有 $x = z$，由此可得，我们寻找环起始节点的方法。 2. 寻找环起始节点判断链表存在环后，需要寻找环的起始节点。此处也是使用双指针法，一个从相遇节点处开始往前移动，一个从head处往前移动，这样到最后两指针相遇位置就会是环的起始节点

链表相交链表相交 1. O(n) 解法首先计算出两个链表的长度差，使最长的链表先移动到两链表相同长度之处，再同时往后移动，边移动边比较。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if(headA == null || headB == null) return null; ListNode curA = headA; ListNode curB = headB; int cntA =0, cntB=0; while(curA != null){ cntA++; curA=curA.next; } ...

删除链表的倒数第n个元素删除链表的倒数第n个元素 双指针的经典应用 fast指针先走 n+1 步（n+1 是使slow指针能指向删除节点的前一个节点），再使fast指针和slow指针同时往前走 直至 fast 指针为 null。(当fast指针为空时，即fast走到了链表末尾，此时两指针距离 n+1 ，即为倒数第n个元素的前一元素) 12345678910111213141516171819202122class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { // 创建一个虚拟头节点 ListNode cur = new ListNode(0); cur.next = head; ListNode slow = cur,fast=cur; // fast 先走 n+1 步 for(int i=0;i<=n;i++){ fast = fast.next; } ...

两两交换链表中的元素两两交换链表中的元素 采用模拟的方式，添加一个虚拟头节点，进行交换。 1234567891011121314151617181920212223class Solution { public ListNode swapPairs(ListNode head) { ListNode ans = new ListNode(0); ans.next = head; ListNode cur = ans; ListNode first,temp,second; while(cur != null && cur.next!=null && cur.next.next!=null){ first = cur.next; //存储第一个节点 second = cur.next.next; //存储第二个节点 temp = cur.next.next.next; // 存储第三个节点 ...

翻转链表翻转链表 此题难点在于怎么在原链表基础上，不使用额外空间将链表进行翻转。 解题思路： 采用两个指针，一个遍历数组，一个指向前一个指针的前一项，每次改变前一个指针的指向，用temp存储，以便遍历。 123456789101112class Solution { public ListNode reverseList(ListNode head) { ListNode pre=null , cur=head; while(cur!=null){ ListNode temp = cur.next; cur.next = pre; pre = cur; cur = temp; } return pre; }}

设计链表设计链表 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465class Node { int val; Node next; Node(){} Node(int val){ this.val = val; }}class MyLinkedList { int size; //存储节点个数 Node head; public MyLinkedList() { size = 0; head = new Node(0); } public int get(int index) { if(index < 0 || index >= size) return -1; Node cur = head; for(int ...

移除链表中的元素移除链表中的元素移除元素的主要操作是将 找到待移除节点的前一个节点node 将 node 的指针域指向其下下个节点，即 待移除节点的下一个节点 注意事项： 有头节点，移除头节点时，需单独分析 删除重复的值时 使用while循环。 1234567891011121314151617181920212223242526272829303132333435/** * 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; } * } */class Solution { public ListNode removeElements(ListNode h ...

Github OAuth 认证登录1. Introduction在完成项目时，可能会使用到第三方登录的情况，例如：WeChat、QQ，而Github OAuth 也是其中的一种。 Github OAuth 是一种基于授权码的认证模式，由github服务器完成授权码的认证和用户信息的传输。其登录模式大致可列为以下几个步骤 用户点击登录，网站 A 让用户跳转到 GitHub。 GitHub 要求用户登录，然后询问”A 网站要求获得 xx 权限，你是否同意？” 用户同意，GitHub 就会重定向回 A 网站，同时发回一个授权码。 A 网站使用授权码，向 GitHub 请求令牌。 GitHub 返回令牌. A 网站使用令牌，向 GitHub 请求用户数据。 本文旨在介绍Github OAuth的一种简单用法，无需自己搭建服务器，简单调用API，用于自己的项目之中。 2. 前置准备在正式在项目中使用OAuth API 前，我们需要先创建一个OAuth Application,访问网址 https://github.com/settings/applications/new 在开发环境中，可如 ...

1.IOC–容器1.1 应用场景 IOC – 用于集中封装、组织、管理对象，该技术用于在开发中，降低代码的耦合度，使更新替换的效率更高。 IOC思想：将开发者主动new 生成对象模式 -> 由IOC工厂统一提供对象的模式 DI：依赖注入，对于IOC工厂中不同的Bean之间绑定依赖关系 1.2 实现方式 通过配置文件的形式实现 Bean的注册 1234567<?xml version="1.0" encoding="UTF-8"?> <beans xmlns="http://www.springframework.org/schema/beans" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.springframework.org/schema/beans http://www.springframework.org/schema/beans/spring-beans.xsd"> ...