leetCode进阶算法题+解析（四）
两两交换链表中的节点
题目：给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:思路：什么叫实际进行节点交换？有点看不懂啊。反正这个题又是一道实现不难，按照条件实现不知道。我先按照我自己的理解去试试吧。
给定 1->2->3->4, 你应该返回 2->1->4->3.
我感觉我是思路对了，没直接交换值，都是节点来回来去赋值。并且一次通过性能超过百分之百，直接贴代码了：
/**
* Definition for singly-linked list.
* public class ListNode {
*int val;
*ListNode next;
*ListNode(int x) { val = x;
}
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode temp = new ListNode(0);
ListNode n = temp;
while(head!=null && head.next!=null ){
n.next = head.next;
n = n.next;
head.next = head.next.next;
n.next = head;
n = n.next;
head = head.next;
}
if(head!=null) n.next = head;
return temp.next;
}
}
首先我是新建一个链表然后一节一节挂数据。两个交换的挂。最后如果剩个单则挂上，不剩单说明正好两个一组。直接返回就行了。
这个题其实比较简单，但是我看了别人的代码，这个题大多数人选择了递归的方法实现。其实确实是这样，我上面的代码也不过是把递归转化成循环而已。
说到这顺便说点别的：递归
其实刷算法以来递归是一种常用的“套路”。我这里用套路来形容递归。
以前也多多少少提过，递归就是隐式的栈，栈是显式的递归。
但是我们仔细寻思寻思递归是什么？
- 递归就是一遍遍的重复调用自身。直到不满足递归的条件。
- 循环就是重复同一段代码，直到不满足循环的条件。
所以这道题可以递归解决是很正常的。但是要和我说递归会比循环性能好多少我是不信的。因为其实本质一样，区别只不过是代码的表现形式而已。顺便立个flag，我打算什么时候有时间了专门写一篇关于递归的理解和使用的文章。
言归正传，说这个题如何用递归实现：
/**
* Definition for singly-linked list.
* public class ListNode {
*int val;
*ListNode next;
*ListNode(int x) { val = x;
}
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
if(head==null || head.next==null ){
return head;
}
ListNode cur = head.next;
head.next = swapPairs(cur.next);
cur.next =head;
return cur;
}
}
【leetCode进阶算法题+解析（四）】其实这个递归展开就是循环的代码。然后这道题就这样了，下一题吧。关于递归我会有时间单独整理的。
两数相除
题目：给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。返回被除数 dividend 除以除数 divisor 得到的商。
示例 1:
输入: dividend = 10, divisor = 3
输出: 3
示例 2:
输入: dividend = 7, divisor = -3
输出: -2
说明:
被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [?231,231 ? 1]。本题中，如果除法结果溢出，则返回 231 ? 1。
思路：不使用除法，乘法，和取模运算。。。实在不行我用减法？这要是int最大值除1我还得减二十多亿次？有点过分了吧。。
好了，看了题解知道这个题的思路了，但是！！！我不服！！
右移1左移1就是乘二除二。所以只要不直接出现*/%符号就是ok的是么?这个题也太奇葩了吧。
然后就是如下代码：
class Solution {
public int divide(int dividend, int divisor) {
if (dividend == 0) {
return 0;
}
if (dividend == Integer.MIN_VALUE && divisor == -1) {
return Integer.MAX_VALUE;
}
boolean negative;
negative = (dividend ^ divisor) <0;
//用异或来计算是否符号相异
long t = Math.abs((long) dividend);
long d= Math.abs((long) divisor);
int result = 0;
for (int i=31;
i>=0;
i--) {
if ((t>>i)>=d) {//找出足够大的数2^n*divisor
result+=1<首先这个被除数是0直接得0，其次这个-1和最小值才会出现溢出，直接返回int最大值。
这两个特殊情况写完了正常逻辑判断。逻辑判断就是d除2的31次方（右移是除法，而且最大值除2的32次方都不是1、所以从31次方开始算）。如果还大于除数，则可以开始正常计算倍数了如果不大于则被除数除2的30次方。直到除某数后还大于除数，开始计算倍数。
然后这道题就这样了，下一题吧。
下一个排序
题目：实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。思路：这道题好像又做过，不知道是不是我理解错了。首先降序数组变成升序数组这个很明确。接下来就难了，我做了好多demo才明白这个题啥意思。比如1 2 3三个数组合，123是最小的，找到第二小的组合数字。1 2 3 还可以组成 321，132。但是我们要第二小的，所以只能选132。同理如下图，65342可以组成好多种数字。这个65342不是最大的，所以要拼成仅大于65342且最小的数。咱们先说可以的选项：65432.65423.这里65423最小，所以选择65423。这个题就是这样的意思（ps：吐槽一下出题人的语文表达能力。）
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
文章图片
image.png
既然知道了题意开始说思路：首先分两步：
- 如果已经是最大了则直接翻转。
- 如果不是最大的则选择变成稍大。这个变成稍大稍微麻烦点。我是打算从后往前判断。首先前面的能不动就不动，因为前面位数大，变动肯定也大。自己看那个65342的例子其实能看出一些东西。
首先要直到末位某元素后面有比这个元素更大的元素为止。其次更大的那个放在这个元素为止上，然后后面的要从小到大拜访。
思路就是这么个思路，接下来我去代码实现了。
这个题多次过了（面向测试案例编程，一点点改bug）。但是性能超过百分之九十九的人，所以我自己挺满意的，直接贴代码:
class Solution {
public void nextPermutation(int[] nums) {
int len = nums.length-1;
if(len==0) return;
for(int i=0;
i=0;
i--){
if(max>nums[i]){//后面有比前面大的元素了.
max = nums[i];
idx = i;
break;
}
max = Math.max(max,nums[i]);
}
//从第idx个到最后重排序，重排序的标准是比idx值大的最小元素放最前，然后从小到大放
int min = nums[idx];
//大于第idx最小的元素
int min1 = 2000000000;
//大于idx最小元素的下标
int idx1 = -1;
for(int i = idx+1;
imin && min1>nums[i]){
min1 = nums[i];
idx1 = i;
}
}
int t = nums[idx];
nums[idx] = nums[idx1];
nums[idx1] = t;
int n = idx+1;
while(nnums[i]){
idx2 = i;
tm = nums[i];
}
}
if(idx2!=n){
int tp = nums[n];
nums[n] = nums[idx2];
nums[idx2] = tp;
}
n++;
}
}
}
代码的逻辑步骤就是按照上面的思路，写的墨迹点但是起码手动实现性能还行。这道题其实不难，就是复杂，墨迹。
首先判断是不是降序数组，然后判断后面有较大值的元素下标idx。然后判断仅大于idx值的数和下标，然后交换。然后后面的升序排列。
整个逻辑就是这样，现在理得很清楚了，所以这道题过。
搜索旋转数组
题目：假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。你可以假设数组中不存在重复的元素。你的算法时间复杂度必须是 O(log n) 级别。
示例 1:思路：感觉这道题的难点是时间复杂度O（logn）。不然简单遍历绝对是ok的。我记得二分法就是logn的时间复杂度，其实这有个很好的判断。判断第一个元素和target大小和target与最后的元素的大小。如果大于最后的小于第一的则直接-1.剩下的二分判断，我先尝试去实现。
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1
这道题终于做完了，各种if-else。。写的都要晕了。然后用的二分法，我先贴代码再一点点说，对了，速度超过百分之九十的人，将将及格！还是很开心的：
class Solution {
public int search(int[] nums, int target) {
int len = nums.length-1;
if(len<0) return -1;
if(target>nums[len] && targetnums[0]? true:false;
while(ltarget){
r = mid;
}else if(nums[mid]nums[0]){
l = mid+1;
}else{//说明mid到了后段
r = mid;
}
}else{
return mid;
}
}else{
if(nums[mid]target){
if(nums[mid]>nums[len]){//这是前半段，要往后半段凑
l = mid+1;
}else{
r = mid;
}
}else{
return mid;
}
}
}
return -1;
}
}
哈哈，看着就眼晕是不是。首先判断这个数是在前半个升序列里还是后半个里。
然后二分法判断，这个判断1，大小判断。2，这个数属于前半段列里还是后半段。
刚刚看了性能第一的代码，差不多思路，就是具体的写法略有不同，然后我复制粘贴提交。。。到我手里也是1ms，还是超过百分之九十的人。。反正贴出来分享下：
class Solution {
public int search(int[] nums, int target) {
int len = nums.length;
int left = 0, right = len-1;
while(left <= right){
int mid = (left + right) / 2;
if(nums[mid] == target)
return mid;
else if(nums[mid] < nums[right]){
if(nums[mid] < target && target <= nums[right])
left = mid+1;
else
right = mid-1;
}
else{
if(nums[left] <= target && target < nums[mid])
right = mid-1;
else
left = mid+1;
}
}
return -1;
}
}
明天就要回家过年了，而且手头现在有一个多租户的概念打算整理写下，还有一个递归的理解使用打算整理一下。。。然后每天三道保底题是为了leetcode的20积分，最近可能算法只刷保底了~感觉时间真的飞快，从一个完全的小白到简单的算法都能做出来，感觉自己有进步呦！哈哈
然后今天的笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注呦！也祝大家工作顺顺利利！
推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- leetcode|leetcode 92. 反转链表 II
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 推荐系统论文进阶|CTR预估 论文精读(十一)--Deep Interest Evolution Network(DIEN)
- 《算法》-图[有向图]
- 二叉树路径节点关键值和等于目标值（LeetCode--112&LeetCode--113）
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）