牛客网——单链表反转

朴灿烈づ我的快乐病毒、 2023-09-28 22:02 17阅读 0赞

![在这里插入图片描述][59695ff5471e433bb0d41964fe2a339e.gif_pic_center]

>  个人主页：[熬夜磕代码丶][Link 1]  
>  作品专栏: [java se][]  
>  我变秃了，也变强了  
> 给大家介绍一款程序员必备刷题平台——牛客网  
> [点击注册一起刷题收获大厂offer吧][offer]  
> ![在这里插入图片描述][2fc6befcb7244979b598903074b23ffa.png]

#### 文章目录 ####

*  一、单链表反转
 *  二、两数之和
 *  三、顺时针旋转矩阵
 *  四、不用加减乘除做加法

## 一、单链表反转 ##

将一个给定的单链表反转，例：1-2-3-4-5，反转为5-4-3-2-1  
![在这里插入图片描述][5ad6ac37583f4ab5ac8c1d7cf3deb8d4.png]  
![在这里插入图片描述][84f28470b37d42e7992f7b5268ad44a4.png]

public ListNode reverseList (ListNode head) {
        
            ListNode pre = null;
            ListNode next = null;
            while(head != null) {
        
                next = head.next;
                head.next = pre;
                pre = head;
                head = next;
            }
            return pre;
        }

![在这里插入图片描述][d17d3f61be5844eea93571c34a923e5c.png]

## 二、两数之和 ##

给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。  
（注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）  
![在这里插入图片描述][ea07427522744dcaacc3fbde2aadfd6a.png]  
![在这里插入图片描述][75345d505c3e4150aa168962ef31d79f.png]  
**方法1：暴力求解**

public int[] twoSum1 (int[] numbers, int target) {
        
            //两数之和
            for(int i = 0;i < numbers.length;i++) {
        
                for(int j = i + 1;j < numbers.length;j++) {
        
                    if(numbers[i] + numbers[j] == target) {
        
                        return new int[]{
        i+1,j+1};
                    }
                }
            }
            return new int[2];
        }

**方法2：哈希**

public int[] twoSum (int[] numbers, int target) {
        
            HashMap<Integer,Integer> map = new HashMap<>();
            for (int i = 0; i < numbers.length; i++) {
        
                if(map.containsKey(target - numbers[i])) {
        
                    return new int[]{
        map.get(target - numbers[i]),i};
                }
                map.put(numbers[i],i);
            }
            return new int[2];
        }

![在这里插入图片描述][6f342dc57f0c46e89a51433fcc1374fd.png]

## 三、顺时针旋转矩阵 ##

有一个nxn整数矩阵，请编写一个算法，将矩阵顺时针旋转90度。  
给定一个nxn的矩阵，和矩阵的阶数n,请返回旋转后的nxn矩阵。  
![在这里插入图片描述][ba2e7aeae4fc40b6a28615dfe7f3541a.png]

public int[][] rotateMatrix(int[][] mat, int n) {
        
            int[][] arr = new int[n][n];
            for (int i = 0; i < mat.length; i++) {
        
                for (int j = 0; j < mat[i].length; j++) {
        
                    arr[j][n-i-1] = mat[i][j];
                }
            }
            return arr;
        }

![在这里插入图片描述][3cfd8e7ed13341f19417630d9491dac9.png]

## 四、不用加减乘除做加法 ##

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、\*、/四则运算符号  
![在这里插入图片描述][6c2ba7d87db14a1e82fb66ff86429e10.png]  
![在这里插入图片描述][ffff578d50f5451f9b6d11cdb0af1deb.png]

import java.util.*;
    public class Solution {
        
        public int Add(int num1,int num2) {
        
            int ans = 0;
            if(num2 == 0) {
        
                return num1;
            }
            while(num2 != 0) {
        
                ans = num1 ^ num2;
                num2 = (num1 & num2) << 1;
                num1 = ans;
            }
            return ans;
        }
    }

![在这里插入图片描述][a5a070c679814469952cc1257395a036.png]

[59695ff5471e433bb0d41964fe2a339e.gif_pic_center]: https://img-blog.csdnimg.cn/59695ff5471e433bb0d41964fe2a339e.gif#pic_center
[Link 1]: https://blog.csdn.net/buhuisuanfa?spm=1018.2226.3001.5343
[java se]: https://blog.csdn.net/buhuisuanfa/category_11932688.html?spm=1001.2014.3001.5482
[offer]: https://www.nowcoder.com/link/pc_csdncpt_bhsf_jzsf
[2fc6befcb7244979b598903074b23ffa.png]: https://img-blog.csdnimg.cn/2fc6befcb7244979b598903074b23ffa.png
[5ad6ac37583f4ab5ac8c1d7cf3deb8d4.png]: https://img-blog.csdnimg.cn/5ad6ac37583f4ab5ac8c1d7cf3deb8d4.png
[84f28470b37d42e7992f7b5268ad44a4.png]: https://img-blog.csdnimg.cn/84f28470b37d42e7992f7b5268ad44a4.png
[d17d3f61be5844eea93571c34a923e5c.png]: https://img-blog.csdnimg.cn/d17d3f61be5844eea93571c34a923e5c.png
[ea07427522744dcaacc3fbde2aadfd6a.png]: https://img-blog.csdnimg.cn/ea07427522744dcaacc3fbde2aadfd6a.png
[75345d505c3e4150aa168962ef31d79f.png]: https://img-blog.csdnimg.cn/75345d505c3e4150aa168962ef31d79f.png
[6f342dc57f0c46e89a51433fcc1374fd.png]: https://img-blog.csdnimg.cn/6f342dc57f0c46e89a51433fcc1374fd.png
[ba2e7aeae4fc40b6a28615dfe7f3541a.png]: https://img-blog.csdnimg.cn/ba2e7aeae4fc40b6a28615dfe7f3541a.png
[3cfd8e7ed13341f19417630d9491dac9.png]: https://img-blog.csdnimg.cn/3cfd8e7ed13341f19417630d9491dac9.png
[6c2ba7d87db14a1e82fb66ff86429e10.png]: https://img-blog.csdnimg.cn/6c2ba7d87db14a1e82fb66ff86429e10.png
[ffff578d50f5451f9b6d11cdb0af1deb.png]: https://img-blog.csdnimg.cn/ffff578d50f5451f9b6d11cdb0af1deb.png
[a5a070c679814469952cc1257395a036.png]: https://img-blog.csdnimg.cn/a5a070c679814469952cc1257395a036.png