leetcode java算法编程的一些技巧_leetcode java代码语法

前言

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

1、数组

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

• 如何获取数组长度？

int h = height.length
1

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

• 新建数组

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

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

此代码里用到里内部类，就不需要写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
2
3
4
5
6
7

技巧汇总

• 1、利用math 函数

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

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

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

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

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

• 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];
1
2
3
4
5

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

• 4、数组排序

        Arrays.sort(nums);


1
2
3

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(); 
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

回溯的理解，我们可以通过递归来轻松达到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);
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

比如我们一个数组有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;
            }
            
        }
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

栈 stack

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

1
2

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

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

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

队列 queue

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

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

常用的方法有：

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

博弈论问题

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

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

所以，先后手用一个class对象来存储，所以一个数组的子集表示为：$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 来填充数组

int[] a = new int[4];
Arrays.fill(a,-10);
1
2