算法

本文整理了常见算法题型与LeetCode题解，涵盖数组、字符串、哈希表、双指针、链表等数据结构，以及栈、队列、回溯、动态规划等核心算法。适合算法初学者及面试备考者，帮助掌握高频题目解题技巧，提升编码效率。

数组

数组是存放在连续内存空间上的相同类型数据的集合。

注意：

  • 数组下标都是从0开始的。
  • 数组内存空间的地址是连续的

正是因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。数组的元素是不能删的，只能覆盖。

第一题：704. 二分查找 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
//自己写的
public static int search(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target){
                return i;
            }
        }

        return -1;
    }
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
//做法二：二分查找。这道题目的前提是数组为有序数组，同时题目还强调数组中无重复元素
public int search(int[] nums, int target) {
    	// 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
    
    	//left right mid都是指数组的索引
        int left = 0;
        int right = nums.length - 1;
        int mid = (left + right) / 2;

        while (left <= right) {
            //目标元素在数组的右边
            if (target > nums[mid]) {
                left = mid + 1;
                mid = (left + right) / 2;
            }
            //目标元素在数组的左边
            if (target < nums[mid]) {
                right = mid - 1;
                mid = (left + right) / 2;
            }

            if (target == nums[mid]) {
                return mid;
            }
        }
        return -1;
    }

第二题：27. 移除元素 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//暴力
   public static int removeElement2(int[] nums, int val) {
       int size = nums.length;
       //外循环：遍历数组的
       for (int i = 0; i < size; i++) {
           if (nums[i] == val) {

               //内循环：更新数组
               for (int j = i + 1; j < size; j++) {
                   //将i后面的元素都往前移动一位，数组的长度--
                   nums[j - 1] = nums[j];

               }
               i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
               size--;
           }
       }
       return size;
   }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int removeElement(int[] nums, int val) {
        // 双指针：操作的是同一个数组
        int slowIndex = 0;  //慢指针：获取新数组的元素
        int fastIndex = 0;  //快指针：获取新数组中需要更新的位置

        for (fastIndex = 0; fastIndex < nums.length; fastIndex++) {
            //新数组中不应该有目标元素
            if (nums[fastIndex] != val) {
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;
    }

第三题：283. 移动零 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//两两交换：将 非0元素 与 第一个为0元素的索引 进行交换
public static void moveZeroes2(int[] nums) {
        if (nums == null) {
            return;
        }
        int i = 0;  //i 用于遍历数组中的每个元素
        int j = 0;  //j 用于跟踪最后一个非零元素的位置
        while (i < nums.length) {
            if (nums[i] != 0) {
                int tmp = nums[j];
                nums[j] = nums[i];
                nums[i] = tmp;
                j++;
            }
            i++;
        }
    }

第四题：844. 比较含退格的字符串 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean backspaceCompare(String s, String t) {
        StringBuilder ssb = new StringBuilder();
        StringBuilder tsb = new StringBuilder();

        // 分别处理两个字符串
        for (char c : s.toCharArray()) {
            if (c != '#') {
                ssb.append(c); // 模拟进栈的操作
            } else if (ssb.length() > 0) { // 栈非空才能弹出
                ssb.deleteCharAt(ssb.length() - 1); // 将栈顶元素弹出
            }
        }

        for (char c : t.toCharArray()) {
            if (c != '#') {
                tsb.append(c); // 模拟进栈的操作
            } else if (tsb.length() > 0) { // 栈非空才能弹出
                tsb.deleteCharAt(tsb.length() - 1); // 将栈顶元素弹出
            }
        }

        return ssb.toString().equals(tsb.toString());
    }

第五题：977. 有序数组的平方 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
//自己写的
public int[] sortedSquares(int[] nums) {
        int[] arr = new int[nums.length];
        
        for (int i = 0; i < nums.length; i++) {
            arr[i] = nums[i] * nums[i];
        }
        
        //对arr进行递增排序
        Arrays.sort(arr);
        
        return arr;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//双指针思路：
public int[] sortedSquares(int[] nums) {
        int right = nums.length - 1;
        int left = 0;
        int[] result = new int[nums.length];
        int index = result.length - 1;
        while (left <= right) {
            if (nums[left] * nums[left] > nums[right] * nums[right]) {
                // 正数的相对位置是不变的， 需要调整的是负数平方后的相对位置
                result[index--] = nums[left] * nums[left];
                ++left;
            } else {
                result[index--] = nums[right] * nums[right];
                --right;
            }
        }
        return result;
    }

第六题：209. 长度最小的子数组 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//暴力解法
public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }

        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum = sum + nums[j];
                if (sum >= target){
                    ans = Math.min(ans,j - i + 1);
                    break;
                }
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*滑动窗口（相当于双指针）
     窗口内是什么？
     如何移动窗口的起始位置？
     如何移动窗口的结束位置？
     */
 public static int minSubArrayLen2(int s, int[] nums) {
     int left = 0;
     int sum = 0;
     int result = Integer.MAX_VALUE;
     int subLength = 0;

     //循环表示：滑动窗口的终止位置
     for (int right = 0; right < nums.length; right++) {
         sum += nums[right];

         while (sum >= s) {  //窗口就要向前移动了（也就是该缩小了）
             subLength = right - left + 1;   // 取子序列的长度
             result = Math.min(result, subLength);
             sum -= nums[left++];
         }
     }

     return result == Integer.MAX_VALUE ? 0 : result;
 }

相关题目推荐

字符串

第一题：344. 反转字符串 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
//双指针交换首尾元素
public void reverseString(char[] s) {
        int j = s.length - 1;
        for (int i = 0; i < s.length / 2; i++) {
            char temp = s[i];
            s[i] = s[j];
            s[j] = temp;
            j--;
        }
    }

第二题：541. 反转字符串 II - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static String reverseStr(String s, int k) {
        char[] chs = s.toCharArray();

        for (int i = 0; i < chs.length; i += 2 * k) {
            int start = i;
            //判断尾数够不够k个，取决于end指针的位置
            int end = Math.min(chs.length - 1,start + k - 1);
            
            while (start <end){
                char temp = chs[start];
                chs[start] = chs[end];
                chs[end] = temp;
                start++;
                end--;
            }
        }
        return String.valueOf(chs);
    }

第三题：54. 替换数字（第八期模拟笔试） (kamacoder.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();

        StringBuilder sb = new StringBuilder(str);
        for (int i = 0; i < sb.length(); i++) {
            if (sb.charAt(i) >= '0' && sb.charAt(i) <= '9'){
                sb.deleteCharAt(i);
                sb.insert(i,"number");
                i = i + 5;
            }
        }

        System.out.println(String.valueOf(sb).toString());
    }
}

第四题：151. 反转字符串中的单词 - 力扣（LeetCode）（困难）

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
public static String reverseWords(String s) {
        // 1.去除首尾以及中间多余空格
        StringBuilder sb = removeSpace(s);
        //System.out.println(sb);

        // 2.反转单词.以空格为界限，进行反转
        String str = sb.toString();

        String[] split = str.split(" ");

        //双指针进行反转单词
        int j = split.length - 1;
        for (int i = 0; i < split.length / 2; i++, j--) {
            String temp = split[i];
            split[i] = split[j];
            split[j] = temp;
        }

        //System.out.println(Arrays.toString(split));
        StringBuilder s1 = new StringBuilder();
        for (int i = 0; i < split.length; i++) {
            if (i == split.length - 1){
                s1.append(split[i]);
            }else {
                s1.append(split[i]).append(" ");
            }
        }

        //将StringBuilder转为string
        String result = s1.toString();

        return result;
    }

    //双指针移除空格
    private static StringBuilder removeSpace(String s) {
        int start = 0;
        int end = s.length() - 1;

        //先移除首尾空格
        while (s.charAt(start) == ' '){
            start++;
        }
        while (s.charAt(end) == ' '){
            end--;
        }

        StringBuilder sb = new StringBuilder();

        while (start <= end){
            char c = s.charAt(start);
            if (c != ' ' || sb.charAt(sb.length() - 1) != ' '){ //本身不能为' ' 或者sb的最后一位不能是' '
                sb.append(c);
            }
            start++;
        }
        return sb;
    }

第五题：459. 重复的子字符串 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean repeatedSubstringPattern(String s) {
        StringBuilder sb = new StringBuilder();
        //将字符串翻倍
        sb.append(s).append(s);

        //掐头去尾
        String substring = sb.substring(1, sb.length() - 1);

        //判断原来的字符串是否包含在substring中
        boolean contains = substring.contains(s);

        return contains;
    }

哈希表

当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。牺牲了空间换取了时间

当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。

  • 数组
  • set（集合）
  • map（映射）

第一题：242. 有效的字母异位词 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//暴力
    public static boolean isAnagram2(String s, String t) {
        if (s.length() != t.length()){
            return false;
        }

        char[] ch_s = s.toCharArray();
        char[] ch_t = t.toCharArray();

        Arrays.sort(ch_s);
        Arrays.sort(ch_t);

        //统计s中有哪些字符
        for (int i = 0; i < ch_s.length; i++) {
            if (ch_s[i] != ch_t[i]){
                return false;
            }
        }

        return true;
    }
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
public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()){
            return false;
        }

        //遍历s，将s中含有的字符存储在一个数组中
        int[] arr = new int[26];

        char[] ch_s = s.toCharArray();
        char[] ch_t = t.toCharArray();

        for (int i = 0; i < ch_s.length; i++) {
            //将s字符存入数组中
            arr[ch_s[i] - 'a']++;
        }

        for (int i = 0; i < ch_t.length; i++) {
            //将t字符从数组中删去
            arr[ch_t[i] - 'a']--;
        }

        //只要数组中有一个不为0
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != 0){
                return false;
            }
        }
        
        return true;
    }

第二题：349. 两个数组的交集 - 力扣（LeetCode）

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
public int[] intersection(int[] nums1, int[] nums2) {
        //特殊情况
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return new int[0];
        }

        Set<Integer> set1 = new HashSet<>();
        Set<Integer> resSet = new HashSet<>();

        //遍历数组1：这也是一个去重的过程
        for (int i : nums1) {
            set1.add(i);
        }

        //遍历数组2的过程中判断哈希表中是否存在该元素
        for (int i : nums2) {
            if (set1.contains(i)) {
                resSet.add(i);
            }
        }

        //将Set转为数组
        int[] array = new int[resSet.size()];
        int j = 0;
        //遍历resSet，将resSet中的每一个元素存入array数组中
        for (int i : resSet) {
            array[j++] = i;
        }

        return array;
    }

第三题：202. 快乐数 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static boolean isHappy(int n) {
        // 记录已经计算过的数字，避免重复和无限循环
        Set<Integer> record = new HashSet<>();
        while (n != 1 && !record.contains(n)) {
            record.add(n);
            n = getNextNumber(n);
        }
        return n == 1;
    }

    private static int getNextNumber(int n) {
        int res = 0;
        while (n > 0) {
            int temp = n % 10;
            res += temp * temp;
            n = n / 10;
        }
        return res;
    }

第四题：1. 两数之和 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//暴力解法
public static int[] twoSum(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
            return res;
        }
    
        int[] res = new int[2];
        
        int sum = 0;
        //慢指针
        for (int i = 0; i < nums.length; i++) {
            //快指针
            for (int j = i + 1; j < nums.length; j++) {
                sum = nums[i] + nums[j];
                if (sum == target) {
                    res[0] = i;
                    res[1] = j;
                    return res;
                }
            }
        }

        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//Map解法
public int[] twoSum(int[] nums, int target) {
    int[] res = new int[2];
        if (nums == null || nums.length == 0) {
            return res;
        }
        Map<Integer, Integer> map = new HashMap<>();    //map:存储遍历过的元素 将元素作为key，数组下标作为value

        for (int i = 0; i < nums.length; i++) {
            int temp = target - nums[i];    //遍历当前元素，并在map中寻找是否有匹配的key
            if (map.containsKey(temp)) {
                res[1] = i;
                res[0] = map.get(temp);
                break;
            }
            map.put(nums[i], i);    //如果没找到匹配对，就把访问过的元素和下标加入到map中
        }
        return res;
}

第五题：454. 四数相加 II - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//暴力解法
    public static int fourSumCount1(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int count = 0;
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                for (int k = 0; k < nums3.length; k++) {
                    for (int g = 0; g < nums4.length; g++) {
                        if (nums1[i] + nums2[j] + nums3[k] + nums4[g] == 0) {
                            count++;
                        }
                    }
                }
            }
        }
        return count;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//哈希表：map解法
    public static int fourSumCount2(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int res = 0;

        Map<Integer, Integer> map = new HashMap<Integer, Integer>();

        //统计两个数组中的元素之和，同时统计出现的次数，放入map
        for (int i : nums1) {
            for (int j : nums2) {
                int sum = i + j;
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
        }

        //统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数
        for (int i : nums3) {
            for (int j : nums4) {
                int sum = i + j;
                res += map.getOrDefault(-sum, 0);
            }
        }
        return res;
    }

第六题：383. 赎金信 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//暴力：遍历这两个字符串，
public static boolean canConstruct(String ransomNote, String magazine) {
        char[] ch_r = ransomNote.toCharArray();
        char[] ch_m = magazine.toCharArray();

        for (int i = 0; i < ch_r.length; i++) {
            for (int j = 0; j < ch_m.length; j++) {
                //遍历：如果r中的字符串在m存在，则将r中这个字符赋值为'0'
                if (ch_r[i] == ch_m[j]){
                    ch_r[i] = '0';
                    ch_m[j] = '1';
                    break;
                }
            }
        }

        //遍历看这个ch_r是否都为'0'
        for (int i = 0; i < ch_r.length; i++) {
            if (ch_r[i] != '0'){
                return false;
            }
        }
        return true;
    }
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
//哈希解法
public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        // 定义一个哈希映射数组
        int[] record = new int[26];

        char[] ch_r = ransomNote.toCharArray();
        char[] ch_m = magazine.toCharArray();


        //遍历magazine记录magazine里各个字符出现的次数
        for (int i = 0; i < ch_m.length; i++) {
            record[ch_m[i] - 'a']++;
        }

        //遍历ransomNote,在record数组中对应的字符个数做--操作
        for (int i = 0; i < ch_r.length; i++) {
            record[ch_r[i] - 'a']--;
        }
        
        //如果小于0，则证明magazine中不完全包含ransomNote
        //如果大于0，则证明magazine中完全包含ransomNote，且还有多余的字母
        for (int i = 0; i < record.length; i++) {
            if (record[i] < 0){
                return false;
            }
        }


        return true;
    }

第七题：15. 三数之和 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//暴力
public static List<List<Integer>> threeSum(int[] nums) {
        HashSet<List<Integer>> set = new HashSet<>();

        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        //排序后存放在set中的集合能保证没有重复
                        List<Integer> list = Arrays.asList(nums[i], nums[j], nums[k]);
                        Collections.sort(list);
                        set.add(list);
                    }
                }
            }
        }
        return new ArrayList<>(set);
    }
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
44
45
46
47
48
49
//双指针思想
   public static List<List<Integer>> threeSum(int[] nums) {
       List<List<Integer>> result = new ArrayList<>();
       //先对数组进行排序
       Arrays.sort(nums);

       // 找出a + b + c = 0
       // a = nums[i], b = nums[left], c = nums[right]

       for (int i = 0; i < nums.length; i++) {
           //排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
           if (nums[i] > 0) {
               return result;
           }

           if (i > 0 && nums[i] == nums[i - 1]) {  //去重a
               continue;
           }

           int left = i + 1;
           int right = nums.length - 1;

           //不能相等，如果相等这就只剩下两个数字了，不满足三元组
           while (right > left) {
               int sum = nums[i] + nums[left] + nums[right];

               if (sum > 0) {  //和有点大，故将right往左移动
                   right--;
               }

               if (sum < 0) {  //和有点小，故将left往右移动
                   left++;
               }

               if (sum == 0){  //满足要求
                   result.add(Arrays.asList(nums[i], nums[left], nums[right]));

                   // 去重逻辑应该放在找到一个三元组之后，对 b 和 c 去重
                   while (right > left && nums[right] == nums[right - 1]) right--;
                   while (right > left && nums[left] == nums[left + 1]) left++;

                   right--;
                   left++;
               }
           }
       }
       return result;

   }

第八题：18. 四数之和 - 力扣（LeetCode）

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
44
45
46
47
48
49
50
51
//双指针思路
public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++) {
            // nums[i] > target 直接返回, 剪枝操作
            if (nums[i] > 0 && nums[i] > target) {
                return result;
            }

            if (i > 0 && nums[i - 1] == nums[i]) { // 对nums[i]去重
                continue;
            }

            for (int j = i + 1; j < nums.length; j++) {
                if (j > i + 1 && nums[j - 1] == nums[j]) { // 对nums[j]去重
                    continue;
                }

                int left = j + 1;
                int right = nums.length - 1;

                while (right > left) {
                    // nums[k] + nums[i] + nums[left] + nums[right] > target int会溢出
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];

                    if (sum > target) { // 和有点大，故将right往左移动
                        right--;
                    }

                    if (sum < target) { // 和有点小，故将left往右移动
                        left++;
                    }

                    if (sum == target) { // 满足要求
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        // 对nums[left]和nums[right]去重
                        while (right > left && nums[right] == nums[right - 1])
                            right--;
                        while (right > left && nums[left] == nums[left + 1])
                            left++;

                        left++;
                        right--;
                    }
                }
            }
        }
        return result;
    }

双指针

第一题：27. 移除元素 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int removeElement(int[] nums, int val) {
        //双指针思想
        //定义一个快指针：用来查找不是目标元素的索引
        //定义一个慢指针：用来将不是目标元素的数据放入一个数组中，知道快指针遍历完目标数组
        

        int i = 0;      //定义快指针
        int slow = 0;  //定义慢指针

        for (i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[slow] = nums[i];
                slow++;
            }
        }

        //System.out.println(Arrays.toString(arr));
        //System.out.println(Arrays.toString(nums));

        //此时这个j就相当于这个新数组的大小，也就是删除目标元素后数组的大小
        return slow;
    }

第二题：344. 反转字符串 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
public void reverseString(char[] s) {
        //双指针
        int j = s.length - 1;
        for (int i = 0; i < s.length / 2; i++) {
            char temp = s[i];
            s[i] = s[j];
            s[j] = temp;
            j--;
        }
    }

第三题：151. 反转字符串中的单词 - 力扣（LeetCode）

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
44
45
46
47
48
49
50
51
52
53
54
55
public String reverseWords(String s) {
        // 1.去除首尾以及中间多余空格
        StringBuilder sb = removeSpace(s);
        //System.out.println(sb);

        // 2.反转单词.以空格为界限，进行反转
        String str = sb.toString();

        String[] split = str.split(" ");

        //双指针进行反转单词
        int j = split.length - 1;
        for (int i = 0; i < split.length / 2; i++, j--) {
            String temp = split[i];
            split[i] = split[j];
            split[j] = temp;
        }

        //System.out.println(Arrays.toString(split));
        StringBuilder s1 = new StringBuilder();
        for (int i = 0; i < split.length; i++) {
            if (i == split.length - 1){
                s1.append(split[i]);
            }else {
                s1.append(split[i]).append(" ");
            }
        }

        //将StringBuilder转为string
        String result = s1.toString();

        return result;
    }

    private static StringBuilder removeSpace(String s) {
        int start = 0;
        int end = s.length() - 1;
        while (s.charAt(start) == ' '){
            start++;
        }
        while (s.charAt(end) == ' '){
            end--;
        }

        StringBuilder sb = new StringBuilder();

        while (start <= end){
            char c = s.charAt(start);
            if (c != ' ' || sb.charAt(sb.length() - 1) != ' '){
                sb.append(c);
            }
            start++;
        }
        return sb;
    }

第四题：206. 反转链表 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        ListNode temp = null;
        while (cur != null) {
            temp = cur.next;// 保存下一个节点
            cur.next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }

第五题：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;

        ListNode fastIndex = dummyNode;
        ListNode slowIndex = dummyNode;

        // 只要快慢指针相差 n 个结点即可
        for (int i = 0; i < n + 1; i++){
            fastIndex = fastIndex.next;
        }

        //同时移动，直到fast指向末尾
        while (fastIndex != null){
            fastIndex = fastIndex.next;
            slowIndex = slowIndex.next;
        }

        //此时 slowIndex 的位置就是待删除元素的前一个位置。
        slowIndex.next = slowIndex.next.next;
        return dummyNode.next;
    }

第六题：面试题 02.07. 链表相交 - 力扣（LeetCode）

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
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        int lenA = 0, lenB = 0;
        while (curA != null) { // 求链表A的长度
            lenA++;
            curA = curA.next;
        }
        while (curB != null) { // 求链表B的长度
            lenB++;
            curB = curB.next;
        }
        curA = headA;
        curB = headB;
        // 让curA为最长链表的头，lenA为其长度
        if (lenB > lenA) {
            // 1. swap (lenA, lenB);
            int tmpLen = lenA;
            lenA = lenB;
            lenB = tmpLen;
            // 2. swap (curA, curB);
            ListNode tmpNode = curA;
            curA = curB;
            curB = tmpNode;
        }
        // 求长度差
        int gap = lenA - lenB;
        // 让curA和curB在同一起点上（末尾位置对齐）
        while (gap-- > 0) {
            curA = curA.next;
        }
        // 遍历curA 和 curB，遇到相同则直接返回
        while (curA != null) {
            if (curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;

    }

第七题：142. 环形链表 II - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {// 有环
                ListNode index1 = fast;
                ListNode index2 = head;
                // 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }

第八题：15. 三数之和 - 力扣（LeetCode）

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
44
45
46
47
48
49
public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        // 先对数组进行排序
        Arrays.sort(nums);

        // 找出a + b + c = 0
        // a = nums[i], b = nums[left], c = nums[right]

        for (int i = 0; i < nums.length; i++) {
            // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
            if (nums[i] > 0) {
                return result;
            }

            if (i > 0 && nums[i] == nums[i - 1]) { // 去重a
                continue;
            }

            int left = i + 1;
            int right = nums.length - 1;

            // 不能相等，如果相等这就只剩下两个数字了，不满足三元组
            while (right > left) {
                int sum = nums[i] + nums[left] + nums[right];

                if (sum > 0) { // 和有点大，故将right往左移动
                    right--;
                }

                if (sum < 0) { // 和有点小，故将left往右移动
                    left++;
                }

                if (sum == 0) { // 满足要求
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    // 去重逻辑应该放在找到一个三元组之后，对 b 和 c 去重
                    while (right > left && nums[right] == nums[right - 1])
                        right--;
                    while (right > left && nums[left] == nums[left + 1])
                        left++;

                    right--;
                    left++;
                }
            }
        }
        return result;
    }

第九题：18. 四数之和 - 力扣（LeetCode）

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
44
45
46
47
48
49
50
public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++) {
            // nums[i] > target 直接返回, 剪枝操作
            if (nums[i] > 0 && nums[i] > target) {
                return result;
            }

            if (i > 0 && nums[i - 1] == nums[i]) { // 对nums[i]去重
                continue;
            }

            for (int j = i + 1; j < nums.length; j++) {
                if (j > i + 1 && nums[j - 1] == nums[j]) { // 对nums[j]去重
                    continue;
                }

                int left = j + 1;
                int right = nums.length - 1;

                while (right > left) {
                    // nums[k] + nums[i] + nums[left] + nums[right] > target int会溢出
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];

                    if (sum > target) { // 和有点大，故将right往左移动
                        right--;
                    }

                    if (sum < target) { // 和有点小，故将left往右移动
                        left++;
                    }

                    if (sum == target) { // 满足要求
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        // 对nums[left]和nums[right]去重
                        while (right > left && nums[right] == nums[right - 1])
                            right--;
                        while (right > left && nums[left] == nums[left + 1])
                            left++;

                        left++;
                        right--;
                    }
                }
            }
        }
        return result;
    }

链表

链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

链表分为单链表和双链表：

  • 单链表：每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针）。单链表中的指针域只能指向节点的下一个节点。
  • 双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。
  • 循环链表：顾名思义，就是链表首尾相连。

链表与数组的比较：

  • 定义数组时长度是固定的，链表的长度不固定。
  • 数组适合频繁的查询，链表适合频繁增删。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//链表的定义
private class ListNode {
    // 结点的值
    int val;

    // 下一个结点
    ListNode next;

    // 节点的构造函数(无参)
    public ListNode() {
    }

    // 节点的构造函数(有一个参数)
    public ListNode(int val) {
        this.val = val;
    }

    // 节点的构造函数(有两个参数)
    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

第一题：203. 移除链表元素 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//设置虚拟头节点
public ListNode removeElements(ListNode head, int val) {
        //一个空链表不需要任何操作
        if (head == null) {
            return head;
        }

        //因为删除可能涉及头节点，所以设置dummy节点，统一操作
        ListNode dummy = new ListNode(-1, head);    //是处理可能需要删除头节点的情况
        ListNode pre = dummy;   //记录当前节点的前一个节点
        ListNode cur = head;    //遍历链表


        while (cur != null) {   //空链表不需要任何操作
            if (cur.val == val) {
                pre.next = cur.next;    //pre的下一个节点指向cur的下一个节点
            } else {
                pre = cur;  //将pre更新为cur
            }
            cur = cur.next; //将cur更新为下一个节点
        }

        return dummy.next;  //返回dummy的下一个节点，这才是实际的头节点
    }

第二题：707. 设计链表 - 力扣（LeetCode）

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
class MyLinkedList {

    //手写一个单链表
    class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }
    }

    //size存储链表元素的个数
    int size;
    //虚拟头结点
    ListNode head;

    //初始化链表
    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);

    }

    //获取第index个节点的数值，注意index是从0开始的，第0个节点就是头结点
    public int get(int index) {
        //如果index非法，直接返回-1
        if (index < 0 || index > size - 1) {
            return -1;
        }
        ListNode currentNode = head;
        //包含一个虚拟节点，所以查找第index + 1 个节点
        for (int i = 0; i <= index; i++) {
            currentNode = currentNode.next;
        }

        return currentNode.val;

    }


    //在链表最前面插入一个节点，等价于在第0个元素前添加
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }

    //在链表的最后插入一个节点，等价于在(末尾+1)个元素前添加
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }

    // 在第 index 个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
    // 如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点
    // 如果 index 大于链表的长度，则返回空
    public void addAtIndex(int index, int val) {
        if (index > size) {
            return;
        }
        if (index < 0) {
            index = 0;
        }
        size++;

        //找到要插入节点的前驱
        ListNode pred = head;
        for (int i = 0; i < index; i++) {
            pred = pred.next;
        }

        ListNode toAdd = new ListNode(val);
        toAdd.next = pred.next;
        pred.next = toAdd;
    }


    //删除第index个节点
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        size--;
        if (index == 0) {
            head = head.next;
            return;
        }
        ListNode pred = head;
        for (int i = 0; i < index; i++) {
            pred = pred.next;
        }
        pred.next = pred.next.next;
    }
}

第三题：206. 反转链表 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
public ListNode reverseList(ListNode head) {
        ListNode prev = null;	//记录当前节点的前一个节点
        ListNode cur = head;	//遍历链表
        ListNode temp = null;	//用于交换链表
        while (cur != null) {
            temp = cur.next;// 保存下一个节点
            cur.next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }

第四题：24. 两两交换链表中的节点 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public ListNode swapPairs(ListNode head) {
        ListNode dumyhead = new ListNode(-1); // 设置一个虚拟头结点
        dumyhead.next = head; // 将虚拟头结点指向head，这样方便后面做删除操作
        ListNode cur = dumyhead;
        ListNode temp; // 临时节点，保存两个节点后面的节点
        ListNode firstnode; // 临时节点，保存两个节点之中的第一个节点
        ListNode secondnode; // 临时节点，保存两个节点之中的第二个节点

        while (cur.next != null && cur.next.next != null) {
            temp = cur.next.next.next;
            firstnode = cur.next;
            secondnode = cur.next.next;
            cur.next = secondnode;       // 步骤一
            secondnode.next = firstnode; // 步骤二
            firstnode.next = temp;      // 步骤三
            cur = firstnode; // cur移动，准备下一轮交换
        }
        return dumyhead.next;
    }

第五题：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;

        ListNode fastIndex = dummyNode;
        ListNode slowIndex = dummyNode;

        // 只要快慢指针相差 n 个结点即可
        for (int i = 0; i < n + 1; i++) {
            fastIndex = fastIndex.next;
        }

        //同时移动，直到fast指向末尾
        while (fastIndex != null) {
            fastIndex = fastIndex.next;
            slowIndex = slowIndex.next;
        }

        //此时 slowIndex 的位置就是待删除元素的前一个位置。
        slowIndex.next = slowIndex.next.next;
        return dummyNode.next;
    }

第六题：面试题 02.07. 链表相交 - 力扣（LeetCode）（困难）

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
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        int lenA = 0, lenB = 0;
        while (curA != null) { // 求链表A的长度
            lenA++;
            curA = curA.next;
        }
        while (curB != null) { // 求链表B的长度
            lenB++;
            curB = curB.next;
        }
        curA = headA;
        curB = headB;
        // 让curA为最长链表的头，lenA为其长度
        if (lenB > lenA) {
            // 1. swap (lenA, lenB);
            int tmpLen = lenA;
            lenA = lenB;
            lenB = tmpLen;
            // 2. swap (curA, curB);
            ListNode tmpNode = curA;
            curA = curB;
            curB = tmpNode;
        }
        // 求长度差
        int gap = lenA - lenB;
        // 让curA和curB在同一起点上（末尾位置对齐）
        while (gap-- > 0) {
            curA = curA.next;
        }
        // 遍历curA 和 curB，遇到相同则直接返回
        while (curA != null) {
            if (curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;

    }

第七题：142. 环形链表 II - 力扣（LeetCode）（困难）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;       //慢指针：一次走一个节点
            fast = fast.next.next;  //快指针：一次走两个节点

            if (slow == fast) {// 有环
                ListNode index1 = fast; //快慢指针相遇的点
                ListNode index2 = head; //头节点
                
                // 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }

栈和队列

队列是先进先出，栈是先进后出。

Stack方法摘要：

  • push()：把项压入堆栈顶部
  • pop()：移除堆栈顶部的对象，并作为此函数的值返回该对象
  • empty()：测试堆栈是否为空。
  • peek()：查看堆栈顶部的对象，但不从堆栈中移除它。
  • search()：返回对象在堆栈中的位置，以 1 为基数。返回值 -1 表示此对象不在堆栈中

Queue方法摘要：

  • add()：将指定的元素插入此队列。成功时返回 true，如果当前没有可用的空间，则抛出异常。
  • offer()：将指定的元素插入此队列。如果该元素已添加到此队列，则返回 true；否则返回 false
  • remove()：获取并移除此队列的头。此方法与 poll 唯一的不同在于：此队列为空时将抛出一个异常。
  • poll()：获取并移除此队列的头，如果此队列为空，则返回 null。
  • peek()：获取但不移除此队列的头；如果此队列为空，则返回 null。
  • element()：获取，但是不移除此队列的头。此方法与 peek 唯一的不同在于：此队列为空时将抛出一个异常。

第一题：232. 用栈实现队列 - 力扣（LeetCode）

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import java.util.Stack;

public class MyQueue {
    /*用栈实现队列 leetcode_232 */

    Stack<Integer> stackIn;
    Stack<Integer> stackOut;

    /**
     * 在这里初始化您的数据结构。
     */
    public MyQueue() {
        stackIn = new Stack<>(); // 负责进栈
        stackOut = new Stack<>(); // 负责出栈
    }

    /**
     * 将元素 x 推到队列的后面。
     */
    public void push(int x) {
        stackIn.push(x);
    }

    /**
     * 从队列前面移除元素并返回该元素。
     */
    public int pop() {
        dumpstackIn();
        return stackOut.pop();
    }

    /**
     * 得到前面的元素。
     */
    public int peek() {
        dumpstackIn();
        return stackOut.peek();
    }

    /**
     * 返回队列是否为空：只要进栈和出战同时为空，则队列为空
     */
    public boolean empty() {
        return stackIn.isEmpty() && stackOut.isEmpty();
    }


    /**
      * 如果stackOut为空，那么将stackIn中的元素全部放到stackOut中
     */
    private void dumpstackIn() {
        if (!stackOut.isEmpty()) return;
        while (!stackIn.isEmpty()) {
            stackOut.push(stackIn.pop());
        }
    }
}

第二题：225. 用队列实现栈 - 力扣（LeetCode）

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
import java.util.LinkedList;
import java.util.Queue;

public class MyStack {
    Queue<Integer> queue;

    public MyStack() {
        queue = new LinkedList<>();
    }

    public void push(int x) {
        queue.add(x);
    }

    //移除并返回栈顶元素
    public int pop() {
        rePosition();
        return queue.poll();
    }

    //返回栈顶的元素，注意并不移除
    public int top() {
        rePosition();   //实际上就是返回队列最后一个元素
        int result = queue.poll();
        queue.add(result);
        return result;
    }

    public boolean empty() {
        return queue.isEmpty();
    }

    //将队列中最后一个元素弹出，就要先将队列中最后一个元素的前面所有元素弹出再重新添加到队列中
    public void rePosition() {
        int size = queue.size();    //获取队列的大小
        size--;
        while (size-- > 0)
            queue.add(queue.poll());    //将队列中最后一个元素前面的所有元素弹出再重新添加到队列中
    }
}

第三题：20. 有效的括号 - 力扣（LeetCode）

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
public static boolean isValid(String s) {
        //剪枝操作
        if (s.length() % 2 != 0) {  //这个字符串的长度不为偶数，直接返回false
            return false;
        }

        //创建一个双端队列
        Deque<Character> deque = new LinkedList<>();
        char ch;

        for (int i = 0; i < s.length(); i++) {
            ch = s.charAt(i);
            //碰到左括号，就把相应的右括号入栈
            if (ch == '(') {
                deque.push(')');
            } else if (ch == '{') {
                deque.push('}');
            } else if (ch == '[') {
                deque.push(']');
            } else if (deque.isEmpty() || deque.peek() != ch) {
                return false;
            } else {//右括号判断和栈顶元素匹配
                deque.pop();
            }
        }
        //最后判断栈中元素是否匹配
        return deque.isEmpty();
    }

第四题：1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
//用栈操作
    public static String removeDuplicates1(String S) {
        //ArrayDeque会比LinkedList在除了删除元素这一点外会快一点
        ArrayDeque<Character> deque = new ArrayDeque<>();
        char ch;

        for (int i = 0; i < S.length(); i++) {
            ch = S.charAt(i);
            if (deque.isEmpty() || deque.peek() != ch) {
                deque.push(ch);
            } else {
                deque.pop();
            }
        }

        String str = "";
        //剩余的元素即为不重复的元素
        while (!deque.isEmpty()) {
            str = deque.pop() + str;
        }
        return str;
    }

    //用字符串代替栈
    public static String removeDuplicates2(String s) {
        // 将 res 当做栈
        // 也可以用 StringBuilder 来修改字符串，速度更快
        StringBuffer res = new StringBuffer();

        // top为 res 的长度
        int top = -1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (top >= 0 && res.charAt(top) == c) { //当 top > 0, 即栈中有字符时，当前字符如果和栈中字符相等，
                res.deleteCharAt(top);  //弹出栈顶字符，同时 top--
                top--;

            } else {    //否则，将该字符入栈，同时top++
                res.append(c);
                top++;
            }
        }
        return res.toString();
    }

    //双指针
    public static String removeDuplicates3(String s) {
        char[] ch = s.toCharArray();
        int fast = 0;
        int slow = 0;

        while (fast < s.length()) {
            // 直接用fast指针覆盖slow指针的值
            ch[slow] = ch[fast];
            // 遇到前后相同值的，就跳过，即slow指针后退一步，下次循环就可以直接被覆盖掉了
            if (slow > 0 && ch[slow] == ch[slow - 1]) {
                slow--;
            } else {
                slow++;
            }
            fast++;
        }
        return new String(ch, 0, slow);
    }

第五题：150. 逆波兰表达式求值 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//用栈来处理
    public static int evalRPN(String[] tokens) {
        Deque<Integer> stack = new LinkedList();

        for (String s : tokens) {
            if ("+".equals(s)) {        // leetcode 内置jdk的问题，不能使用==判断字符串是否相等
                stack.push(stack.pop() + stack.pop());      // 注意 - 和 / 需要特殊处理
            } else if ("-".equals(s)) {
                stack.push(-stack.pop() + stack.pop());
            } else if ("*".equals(s)) {
                stack.push(stack.pop() * stack.pop());
            } else if ("/".equals(s)) {
                int temp1 = stack.pop();
                int temp2 = stack.pop();
                stack.push(temp2 / temp1);
            } else {    //将数字存入栈中，不要忘记转为int再存入
                stack.push(Integer.valueOf(s));
            }
        }
        return stack.pop();
    }

第六题：239. 滑动窗口最大值 - 力扣（LeetCode）

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
//暴力：不能完全通过测试用例
public static int[] maxSlidingWindow(int[] nums, int k) {
        //剪枝操作
        if (k == 1) {
            return nums;
        }

        int[] res = new int[nums.length - k + 1];
        int max = Integer.MIN_VALUE;
        int index = 0;

        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < k + i; j++) {
                // 遍历小区间中的最大值
                while (j < k + i && j < nums.length) {

                    if (nums[j] > max) {
                        max = nums[j];
                        j++;
                    } else {
                        j++;
                    }
                }
                res[index] = max;
                max = Integer.MIN_VALUE;
                index++;
                if (index == nums.length - k + 1) {
                    return res;
                }
            }
        }
        return res;
    }

第七题：347. 前 K 个高频元素 - 力扣（LeetCode）

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
44
//通过map，list来实现的
public int[] topKFrequent(int[] nums, int k) {
        // key存放元素，value存放元素出现的次数
        Map<Integer, Integer> map = new HashMap<>();

        for (int num : nums) {
            // 当集合中有这个元素时，就使这个元素的value+1，当集合中没有这个元素时，就添加0 + 1
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        // 遍历map，将value从大到小排序，放入数组中
        List<Integer> list = new ArrayList<>();

        Set<Integer> keySet = map.keySet();
        for (Integer key : keySet) {
            Integer value = map.get(key);
            list.add(value);
        }

        // 排序(从大到小)
        list.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });

        // System.out.println(list);//[3, 2, 1]

        // 通过value获取对应的key，只取前k个value对应的key
        int[] res = new int[k];
        for (int i = 0; i < k;) {
            Integer value = list.get(i);
            // 遍历map
            for (Integer key : keySet) {
                Integer val = map.get(key);
                if (Objects.equals(value, val)) {
                    res[i] = key;
                    i++;
                }
            }
        }
        return res;
    }

二叉树

二叉树的分类

  • 满二叉树：如果一棵二叉树只有度为 0 的结点和度为 2 的结点，并且度为 0 的结点在同一层上，则这棵二叉树为满二叉树。
  • 完全二叉树
  • 二叉搜索树
  • 平衡二叉搜索树

回溯（递归）算法

提示：拿到一道题，先想暴力解法，发现有点不能确定几层循环后，想起回溯，回溯题目都可以抽象成一个树形结构

回溯算法的三部曲：

  1. 回溯函数模板返回值以及参数
  2. 回溯函数终止条件
  3. 回溯搜索的遍历过程

回溯法，一般可以解决如下几种问题：

  • 组合问题：N个数里面按一定规则找出k个数的集合
  • 切割问题：一个字符串按一定规则有几种切割方式
  • 子集问题：一个N个数的集合里有多少符合条件的子集
  • 排列问题：N个数按一定规则全排列，有几种排列方式
  • 棋盘问题：N皇后，解数独等等

回溯算法的模板：

1
2
3
4
5
6
7
8
9
10
11
12
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

组合第一题：77. 组合 - 力扣（LeetCode）

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
//回溯（未剪枝）
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }

    public void backtracking(int n, int k, int startIndex) {
        //确定终止条件
        if (path.size() == k) {
            result.add(new ArrayList<>(path));
            return;
        }
        //单层搜索的逻辑
        for (int i = startIndex; i <= n; i++) { //横向遍历
            path.add(i);
            backtracking(n, k, i + 1);  //递归纵向遍历
            path.removeLast();
        }
    }
}
//如何剪枝
//可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了：i <= n - (k - path.size()) + 1

组合第二题：216. 组合总和 III - 力扣（LeetCode）

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
class Solution {
    LinkedList<Integer> path = new LinkedList<>();
    List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {
        build(k, n, 1, 0);
        return ans;
    }

    private void build(int k, int n, int startIndex, int sum) {
        //确定终止条件

        if (sum > n) return;

        if (path.size() > k) return;

        if (sum == n && path.size() == k) {
            ans.add(new ArrayList<>(path));
            return;
        }

        //单层搜索的逻辑
        for (int i = startIndex; i <= 9; i++) {
            path.add(i);
            sum += i;
            build(k, n, i + 1, sum);
            sum -= i;
            path.removeLast();
        }
    }
}
//如何剪枝
//已选元素总和如果已经大于n了，那么往后遍历就没有意义，直接剪掉：i <= 9 - (k - path.size()) + 1

组合第三题：17. 电话号码的字母组合 - 力扣（LeetCode）

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
class Solution {
    // 设置全局列表存储最后的结果
    List<String> list = new ArrayList<>();

    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return list;
        }
        // 初始对应所有的数字，为了直接对应2-9，新增了两个无效的字符串""
        String[] numString = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
        // 迭代处理
        backTracking(digits, numString, 0);
        return list;

    }

    // 每次迭代获取一个字符串，所以会设计大量的字符串拼接，所以这里选择更为高效的 StringBuild
    StringBuilder temp = new StringBuilder();

    // 比如digits如果为"23",num 为0，则str表示2对应的 abc
    public void backTracking(String digits, String[] numString, int num) {
        // 遍历全部一次记录一次得到的字符串
        if (num == digits.length()) {
            list.add(temp.toString());
            return;
        }
        // str 表示当前num对应的字符串
        String str = numString[digits.charAt(num) - '0'];
        for (int i = 0; i < str.length(); i++) {
            temp.append(str.charAt(i));
            // c
            backTracking(digits, numString, num + 1);
            // 剔除末尾的继续尝试
            temp.deleteCharAt(temp.length() - 1);
        }
    }
}

组合第四题：39. 组合总和 - 力扣（LeetCode）

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
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates); // 先进行排序
        backtracking(res, new ArrayList<>(), candidates, target, 0, 0);
        return res;
    }

    public void backtracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum,
            int idx) {
        // 找到了数字和为 target 的组合
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = idx; i < candidates.length; i++) {
            // 如果 sum + candidates[i] > target 就终止遍历
            if (sum + candidates[i] > target)
                break;
            path.add(candidates[i]);
            backtracking(res, path, candidates, target, sum + candidates[i], i);
            path.remove(path.size() - 1); // 回溯，移除路径 path 最后一个元素
        }
    }
}

组合第五题：40. 组合总和 II - 力扣（LeetCode）

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
class Solution {
    LinkedList<Integer> path = new LinkedList<>();
    List<List<Integer>> ans = new ArrayList<>();
    boolean[] used;
    int sum = 0;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        used = new boolean[candidates.length];
        // 加标志数组，用来辅助判断同层节点是否已经遍历
        Arrays.fill(used, false);
        // 为了将重复的数字都放到一起，所以先进行排序
        Arrays.sort(candidates);
        backTracking(candidates, target, 0);
        return ans;
    }

    private void backTracking(int[] candidates, int target, int startIndex) {
        if (sum == target) {
            ans.add(new ArrayList(path));
        }
        for (int i = startIndex; i < candidates.length; i++) {
            if (sum + candidates[i] > target) {
                break;
            }
            // 出现重复节点，同层的第一个节点已经被访问过，所以直接跳过
            if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {
                continue;
            }
            used[i] = true;
            sum += candidates[i];
            path.add(candidates[i]);
            // 每个节点仅能选择一次，所以从下一位开始
            backTracking(candidates, target, i + 1);
            used[i] = false;
            sum -= candidates[i];
            path.removeLast();
        }
    }
}

切割第一题：131. 分割回文串 - 力扣（LeetCode）

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
class Solution {
    List<List<String>> lists = new ArrayList<>();
    Deque<String> deque = new LinkedList<>();

    public List<List<String>> partition(String s) {
        backTracking(s, 0);
        return lists;
    }

    private void backTracking(String s, int startIndex) {
        // 如果起始位置大于s的大小，说明找到了一组分割方案
        if (startIndex >= s.length()) {
            lists.add(new ArrayList(deque));
            return;
        }

        for (int i = startIndex; i < s.length(); i++) {
            // 如果是回文子串，则记录
            if (isPalindrome(s, startIndex, i)) {
                String str = s.substring(startIndex, i + 1);
                deque.addLast(str);
            } else {
                continue;
            }
            // 起始位置后移，保证不重复
            backTracking(s, i + 1);
            deque.removeLast();
        }
    }

    // 判断是否是回文串
    private boolean isPalindrome(String s, int startIndex, int end) {
        for (int i = startIndex, j = end; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }
}

切割第二题：93. 复原 IP 地址 - 力扣（LeetCode）

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
44
45
46
47
48
49
50
51
52
53
class Solution {
    List<String> result = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        if (s.length() > 12)
            return result; // 算是剪枝了
        backTrack(s, 0, 0);
        return result;
    }

    // startIndex: 搜索的起始位置， pointNum:添加逗点的数量
    private void backTrack(String s, int startIndex, int pointNum) {
        if (pointNum == 3) {// 逗点数量为3时，分隔结束
            // 判断第四段⼦字符串是否合法，如果合法就放进result中
            if (isValid(s, startIndex, s.length() - 1)) {
                result.add(s);
            }
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            if (isValid(s, startIndex, i)) {
                s = s.substring(0, i + 1) + "." + s.substring(i + 1); // 在str的后⾯插⼊⼀个逗点
                pointNum++;
                backTrack(s, i + 2, pointNum);// 插⼊逗点之后下⼀个⼦串的起始位置为i+2
                pointNum--;// 回溯
                s = s.substring(0, i + 1) + s.substring(i + 2);// 回溯删掉逗点
            } else {
                break;
            }
        }
    }

    // 判断字符串s在左闭⼜闭区间[start, end]所组成的数字是否合法
    private Boolean isValid(String s, int start, int end) {
        if (start > end) {
            return false;
        }
        if (s.charAt(start) == '0' && start != end) { // 0开头的数字不合法
            return false;
        }
        int num = 0;
        for (int i = start; i <= end; i++) {
            if (s.charAt(i) > '9' || s.charAt(i) < '0') { // 遇到⾮数字字符不合法
                return false;
            }
            num = num * 10 + (s.charAt(i) - '0');
            if (num > 255) { // 如果⼤于255了不合法
                return false;
            }
        }
        return true;
    }
}

子集第一题：78. 子集 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    List<List<Integer>> result = new ArrayList<>(); // 存放符合条件结果的集合
    LinkedList<Integer> path = new LinkedList<>(); // 用来存放符合条件结果

    public List<List<Integer>> subsets(int[] nums) {
        subsetsHelper(nums, 0);
        return result;
    }

    private void subsetsHelper(int[] nums, int startIndex) {
        result.add(new ArrayList<>(path)); // 「遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合」。
        if (startIndex >= nums.length) { // 终止条件可不加
            return;
        }
        for (int i = startIndex; i < nums.length; i++) {
            path.add(nums[i]);
            subsetsHelper(nums, i + 1);
            path.removeLast();
        }
    }
}

子集第二题：90. 子集 II - 力扣（LeetCode）

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
class Solution {
    List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
    LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
    boolean[] used;

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        if (nums.length == 0) {
            result.add(path);
            return result;
        }
        Arrays.sort(nums);
        used = new boolean[nums.length];
        subsetsWithDupHelper(nums, 0);
        return result;
    }

    private void subsetsWithDupHelper(int[] nums, int startIndex) {
        result.add(new ArrayList<>(path));
        if (startIndex >= nums.length) {
            return;
        }
        for (int i = startIndex; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            subsetsWithDupHelper(nums, i + 1);
            path.removeLast();
            used[i] = false;
        }
    }
}

排列第一题：491. 非递减子序列 - 力扣（LeetCode）

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
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> findSubsequences(int[] nums) {
        backTracking(nums, 0);
        return result;
    }

    private void backTracking(int[] nums, int startIndex) {
        if (path.size() >= 2)
            result.add(new ArrayList<>(path));

        HashSet<Integer> hs = new HashSet<>();

        for (int i = startIndex; i < nums.length; i++) {
            if (!path.isEmpty() && path.get(path.size() - 1) > nums[i] || hs.contains(nums[i]))
                continue;
            hs.add(nums[i]);
            path.add(nums[i]);
            backTracking(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

排列第二题：46. 全排列 - 力扣（LeetCode）

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
class Solution {
    List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
    LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
    boolean[] used;

    public List<List<Integer>> permute(int[] nums) {
        if (nums.length == 0) {
            return result;
        }
        used = new boolean[nums.length];
        permuteHelper(nums);
        return result;
    }

    private void permuteHelper(int[] nums) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            permuteHelper(nums);
            path.removeLast();
            used[i] = false;
        }
    }
}

排列第三题：47. 全排列 II - 力扣（LeetCode）

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
class Solution {
    // 存放结果
    List<List<Integer>> result = new ArrayList<>();
    // 暂存结果
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean[] used = new boolean[nums.length];
        Arrays.fill(used, false);
        Arrays.sort(nums);
        backTrack(nums, used);
        return result;
    }

    private void backTrack(int[] nums, boolean[] used) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            // used[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过
            // used[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过
            // 如果同⼀树层nums[i - 1]使⽤过则直接跳过
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            // 如果同⼀树⽀nums[i]没使⽤过开始处理
            if (used[i] == false) {
                used[i] = true;// 标记同⼀树⽀nums[i]使⽤过，防止同一树枝重复使用
                path.add(nums[i]);
                backTrack(nums, used);
                path.remove(path.size() - 1);// 回溯，说明同⼀树层nums[i]使⽤过，防止下一树层重复
                used[i] = false;// 回溯
            }
        }
    }
}

棋盘第一题：51. N 皇后 - 力扣（LeetCode）

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
    List<List<String>> res = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        char[][] chessboard = new char[n][n];
        for (char[] c : chessboard) {
            Arrays.fill(c, '.');
        }
        backTrack(n, 0, chessboard);
        return res;
    }

    public void backTrack(int n, int row, char[][] chessboard) {
        if (row == n) {
            res.add(Array2List(chessboard));
            return;
        }

        for (int col = 0; col < n; ++col) {
            if (isValid(row, col, n, chessboard)) {
                chessboard[row][col] = 'Q';
                backTrack(n, row + 1, chessboard);
                chessboard[row][col] = '.';
            }
        }

    }

    public List Array2List(char[][] chessboard) {
        List<String> list = new ArrayList<>();

        for (char[] c : chessboard) {
            list.add(String.copyValueOf(c));
        }
        return list;
    }

    public boolean isValid(int row, int col, int n, char[][] chessboard) {
        // 检查列
        for (int i = 0; i < row; ++i) { // 相当于剪枝
            if (chessboard[i][col] == 'Q') {
                return false;
            }
        }

        // 检查45度对角线
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }

        // 检查135度对角线
        for (int i = row - 1, j = col + 1; i >= 0 && j <= n - 1; i--, j++) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
}

贪心算法

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

动态规划

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的，

对于动态规划问题五步曲：

  1. 确定dp数组（dp table）以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

01背包暴力思路：每个物品只有取或者不取，用回溯算法枚举所有情况，筛选出装满背包的最大价值是多少。

1

01背包动态规划解法：

  • dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
  • 递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])