leetcode java算法编程的一些技巧

快来打我* 2023-06-29 12:00 7阅读 0赞

### 前言 ###

虽然我们平时用Java 用的比较多，做技术做的也比较不错，但完全要你用语言来写一些东西，你还是会懵逼，因为我们平时都是用IDEA智能提示，可能一个提示，代码就自动写完了，所以，当你用Java 来写一些算法题的实现，有可能你记不起一些语法来。本文来帮你加强编写代码的能力。

### 1、数组 ###

数组的特性就是直接根据下标来获取数据，在算法题中很多输入都是数组，那么：

*  如何获取数组长度？

int h = height.length

不带括号哦，记不住就很晕

*  新建数组

int[] tmp = new int[arr.length];    //新建一个临时数组存放

### 2、链表 ###

*  不需要按照写项目代码那样按部就班

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode first = head;
            ListNode last = head;
            for (int i=0;i<n;i++) {
                last = last.next;
            }
            while(last!=null && last.next!= null){
                last = last.next;
                first = first.next;
            }
    
            if (first == head && last == null) {
                return head.next;
            }
            ListNode thr = first.next;
            first.next = thr.next;
            thr.next = null;
            return head;
        }
    }

此代码里用到里内部类，就不需要写get、set方法，直接访问内部变量。

### 3、字符串 ###

*  （1）字符串长度  
    s.length()
 *  （2）根据坐标 获得字符  
    s.charAt(i) ， i 是坐标
 *  （3）根据坐标截断 字符  
    s.substring(sta,end) ：不包括end 坐标字符
 *  （4）char 转数字  
    int num = (int)ch - (int)(‘0’);  
    int num = cha - ‘0’  
    直接与字符“0”相减也可以得到。

### 4、输入输出 ###

我们经常会碰到输入一个数字，然后输出一个数组，代码如下：

Scanner sc = new Scanner(System.in);
           int n = sc.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = sc.nextInt();
            }

### 技巧汇总 ###

*  1、利用math 函数

Math.min(a,b)
    Math.max(a,b)

虽然三目运算符可以替代这个效果，但是代码可读性不好。

*  2、链表头节点问题  
    一般给的都是1 -> 2 -> 3 -> 4 ，这样的顺序没有头节点，写代码的时候如果你需要头节点，就给他一个头节点，比如：

ListNode dummy = new ListNode(0);   //  生成一个新节点
    dummy.next = head;     //  头节点指向下一个节点

这样放方便你避免一些异常情况。

*  3、交换操作踩坑

private void swap(int[] arr, int i, int j) {
            if (i==j) {return;}
            arr[i] =arr[i] ^arr[j];
            arr[j] = arr[i]^arr[j];
            arr[i] = arr[i]^arr[j];

如果是两个变量，上面交换逻辑没问题，如果是通过坐标来访问指针，必须判断两者是否相等，否则出错。

*  4、数组排序

Arrays.sort(nums);

### dfs bFs 遍历 ###

这两种遍历可以证连贯性，虽然是树的遍历方式，但是在数组中，可以利用这两种遍历方式来回达到连贯性的遍历手段，很不错的方式，但要借助一个二维数组来控制访问的位置，标明那些位置已经被访问了。

### 回溯模板 ###

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就 “回溯” 返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为 “回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。

回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。所以这里主要包括两个步骤，一个是进、一个是退，额外需要一个数组来存储这个访问的路径。

*  访问的路径  
    用一个容器来存储访问的路径上的节点。List 和 Queue
 *  进  
    访问这个节点，再选择其他节点来继续访问，了解能不能满足条件。
 *  退  
    去除这个访问的节点，选择其他节点访问。

class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            Arrays.sort(candidates);
            List<List<Integer>> resList = new ArrayList<>();
            Deque<Integer> numS = new ArrayDeque<>();
            dfs(candidates,target,candidates[candidates.length-1],numS,resList);
            return resList;
        }
    
        public void dfs(int[] candidates, int target,int max, Deque<Integer> numS,List<List<Integer>> resList){
            if(target==0){
                resList.add(new ArrayList<>(numS));
                return;
            }
            for(int i=candidates.length-1;i>=0;i--){
                if(candidates[i]>target || candidates[i] > max){
                    continue;
                }
                if(candidates[i]<=target){
                    numS.add(candidates[i]);
                    dfs(candidates,target-candidates[i],candidates[i],numS,resList);
                    numS.removeLast(); 
                }
            }
        }
    }

回溯的理解，我们可以通过递归来轻松达到for循环的目的，比如我们有内容为1-10的数组，通过递归来深度访问10这个数字，然后从10-1的顺序来反过来循环数组，这也是特别有意思的内容，并且通过此思想来达到回溯方法。  
比如：

public void dfs(int pos, int rest) {
            if (rest == 0) {
                ans.add(new ArrayList<Integer>(sequence));
                return;
            }
            if (pos == freq.size() || rest < freq.get(pos)[0]) {
                return;
            }		
            // 这一步递归 就是访问数组的最后一个位置
            dfs(pos + 1, rest);
    		// 然后从当前pos，一直到最后一个pos位置
            int most = Math.min(rest / freq.get(pos)[0], freq.get(pos)[1]);
            for (int i = 1; i <= most; ++i) {
                sequence.add(freq.get(pos)[0]);
                dfs(pos + 1, rest - i * freq.get(pos)[0]);
            }
            // 回溯
            for (int i = 1; i <= most; ++i) {
                sequence.remove(sequence.size() - 1);
            }
        }

比如我们一个数组有10个元素，就是1-10，上述递归的过程就类似：

*  10  
    先是抵达数组最后一个pos=9，也就是元素10，再递归回溯
 *  9-10  
    递归10之后，返回到上一个dfs，也就是pos=8的位置，这个元素是9，在此基础上在dfs到10.
 *  8-10  
    同上
 *  7-10  
    同上

当然上述是两个过程，不过很巧的是这两个过程结合起来效果很好。  
如果有人要看具体的内容，可以参考：https://leetcode-cn.com/problems/combination-sum-ii/solution/zu-he-zong-he-ii-by-leetcode-solution/ 这个链接看看完整的问题和代码，从而更深的体会。

### 回溯不重复的问题 ###

经典的带有重复数字的数组排列组合问题，数组中有重复的数字，要求数组中的数字排列组合，这些组合不能有重复的组合，这是排列的进阶版，解决方法就是对数组里的数字排序，这样让排序后的数字，同一个位置不能重复出现，排列组合其实就是数字的位置问题，比如：\[1,2,2,3,3\]，最容易咋成的重复组合则是：\[2,1,2,3,3\]，两个2可以互换位置，所以当我们回溯2这个所在的位置，下一个重复的2就不能在选了。

class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            Arrays.sort(nums);
            int n = nums.length;
            int pre = Integer.MIN_VALUE;
            List<List<Integer>> res = new ArrayList<>();
            for(int i=0;i<n;i++){
                if(nums[i]!=pre){
                    int[] flags = new int[n];
                    List<Integer> one = new ArrayList<>();
                    flags[i]=1;
                    one.add(nums[i]);
                    get(nums,res,one,flags);
                    pre = nums[i];
                }
            }
            return res;
        }
    
    
        public void get(int[] nums,List<List<Integer>> res,List<Integer> re,int[] flags){
            if (re.size() == nums.length){
                res.add(re);
                return;
            }
            int n = nums.length;
            int pre = Integer.MIN_VALUE;
            for(int i=0;i<n;i++){
            // pre 就是上一个数
                if(nums[i]!=pre && flags[i]==0){
                    List<Integer> one = new ArrayList<>(re);
                    one.add(nums[i]);
                    flags[i]=1;
                    get(nums,res,one,flags);
                    pre = nums[i];
                    flags[i]=0;
                }
                
            }
        }
    }

### 栈 stack ###

Stack<Integer> st = new Stack<Integer>();

经常用的方法有：empty()，push()，pop()

Queue<String> queue = new LinkedList<String>();

这个也可以实现栈，因为继承了抽象类。

### 队列 queue ###

LinkedList既是普通容器，也实现了队列。

Queue<String> queue = new LinkedList<String>();

常用的方法有：

*  offer(E e)  
    添加一个元素，在队列头部
 *  poll()  
    移除一个元素，获取并移除此队列的头，如果此队列为空，则返回 null。

### 博弈论问题 ###

博弈论问题的一个经典就是捡石头，给你一个数组，数组里每一个元素的数值表示这一堆石头数量，你和一个朋友一起捡石头，可以从左边或者右边依次交替捡石头，问你先手捡石头和后手捡石头，石头的最大值是多少，这里说明一下你和朋友都绝顶聪明，都不会乱选石头，这个问题的本质其实就是数组选数值，数组的子集的解也是这个大数组的解，也是一个可以动态规划问题，只不过问题在于交替选，那么如何建模？

*  数组有前后坐标  
    i表示数组第一堆石头，j表示第二堆石头。
 *  数组有先后手  
    先手得到的石头数量，后手得到的石头数量，

所以，先后手用一个class对象来存储，所以一个数组的子集表示为： d p \[ i \] \[ j \] = s t o n e dp\[i\]\[j\] = stone dp\[i\]\[j\]=stone，stone有两个字段，一个是fir：表示先手，一个sec ：表示后手。

子集的逻辑：

*  先手  
    数组子集选左边一个数、右边一个数，那个更大，  
    dp\[i\]\[j\] =max(nums\[i\] +dp\[i+1\]\[j\].sec,nums\[j\]+dp\[i\]\[j-1\].sec)  
    这里选择的是：dp\[i+1\]\[j\].sec 后手，因为在i+1到j这个子集里，是另一个人先手。
 *  后手  
    这个就看先手怎么选择了，就是取\[i+1\]\[j\].fir 或者 \[i\]\[j-1\].fir

可以采取递归或者数组倾斜遍历来实现。

### 位运算 ###

位运算主要有几个技巧点：

##### 数字异或运算 #####

相同的数字异或运算等于0:  
10&10=0

##### 异或运算交换两个数字 #####

a ^=b;  
b=a^b;  
a=b^a;

##### 字母大小写转换 #####

字母编码从 65开始：A 表示 65，26个大写英文字母，到90，小写a从 97开始，这里注意空格是32，"\_"是95，

*  大写、小写转小写：(‘A’ | ’ ')=A，(‘a’ | ’ ')=A ，跟空格 取 或运算
 *  小写、大写转大写：(‘a’ & ’ \_ ')=a，(‘A’ & ’ \_ ')=a，跟下划线取与运算
 *  大写转小写，小写转大写 ，(‘a’ ^ ’ ')= A

##### 填充数组 #####

用 -10 来填充数组