Linux系统管理命令

发表于 2018-03-01 | 分类于 Linux

进程查看命令ps

$ ps [选项]
# -a：显示一个终端的所有进程，除了会话引线
# -u：显示进程的归属用户及内存使用情况
# -x：显示没有控制终端的进程
# -l：长格式显示，显示各加详细的信息
# -e：显示所有进程
$ ps aux	
# 查看系统中所有进程，没有'-'，使用BSD操作系统格式
$ ps -le
# 查看系统中所有进程，使用Linux标准命令格式

参数

VSZ 虚拟内存 kb
RSS 真实内存 kb
TTY 终端
STAT 进程状态
START 进程启动时间
TIME 进程耗费的CPU运算时间
COMMAND 进程名字

1
2
3

- 字符终端 tty1 - tty6
- 图形终端 tty7
- 远程虚拟终端 pts/0 - 255

- R 运行
- S 睡眠
- Z 僵死
- T 停止状态
- s 包含子进程
- + 位于后台
- < 高优先级 对其他用户不利

1
2
3

$ pstree [选项] 
# -p：增加显示进程的PID
# -u：增加显示进程的所属用户

进程查看命令top

$ top [选项]
# -d 秒数：top更新的间隔
# -b：使用批处理模式输出，一般和'-n'选项合用
# -n：次数：指定top命令执行的次数，一般和'-b'选项合用
$ top -d 10 -n 3 -b > aaa.log
# top命令每隔10秒执行，一共执行3次，每次将结果输入到aaa.log

查看系统健康状态

可以按shift+x在交互模式下执行进程排序
shift+p：以CPU使用率排序，默认
shift+m：以内存使用率排序
shift+n：以PID排序
q：退出top

top - 08:18:14 up 10 min,  1 user,  load average: 0.34, 0.52, 0.38
Tasks: 177 total,   1 running, 176 sleeping,   0 stopped,   0 zombie
%Cpu(s):  1.2 us,  0.7 sy,  0.0 ni, 97.4 id,  0.1 wa,  0.0 hi,  0.6 si,  0.0 st
KiB Mem :  3456512 total,  1211904 free,   940964 used,  1303644 buff/cache
KiB Swap: 18811900 total, 18811900 free,        0 used.  2207300 avail Mem

1 2	load average: 1分钟，5分钟，15分钟CPU的平均负载 %Cpu(s): 用户占比，系统占比，改变过优先级的用户进程占比，空闲占比

1 2	bufferrs：缓冲，加速写入 caches：缓存，加速读取

1 2	$ ps aux \| grep httpd # 查看进程名字为httpd的进程状态

ps、pstree和top

ps一般用于查看所有进程
pstree一般用于查看所有进程数
top一般用于查看系统的健康状态

杀死进程命令

1
2
3

$ kill -1 pid
# 信号1 SIGHUP 该信号让进程立刻关闭，并重新读取配置文件后重启
# 信号9 SIGKILL 该信号不能被阻塞、处理和忽略，一般用于强制终止进程。

$ killall [选项] [信号] 进程名
# 按照进程名杀死进程（存在一个进程名，有多个进程id）
# -i：交互式
# -I：忽略进程名的大小写

查看后台的工作

把进程放在后台运行

tar -zcf xx.tar /tmp &
把命令放在后台，并在后台执行
tar -zcf xx.tar /tmp
按下Ctrl+z，放在后台暂停

1 2	$ jobs -l # 查看后台进行的进程

$ fg %工作号
# 将后台暂停的工作恢复到前台执行
$ bg %工作号
# 将后台暂停的工作恢复到后台执行	
# 工作号诸如,[1],[2]...注意不是pid

后台命令脱离终端

即使终端关闭了，进程也不关闭

1 2	$ nohup 进程 & # nohuo /root/aProcess.sh &

系统定时任务

一次性定时任务at

1	at [选项] [时间]

循环定时任务crontab

贪心算法

发表于 2018-02-28 | 分类于 Catalina

455. Assign Cookies

Example:

Input: [1,2,3], [1,1]
Output: 1
Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. 
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.
Input: [1,2], [1,2,3]
Output: 2
Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. 
You have 3 cookies and their sizes are big enough to gratify all of the children, 
You need to output 2.

 class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        
        int gi = g.length-1;
        int si = s.length-1;
        int res = 0;
        
        while(gi >= 0 && si >= 0){
            if(g[gi] <= s[si]){
                ++res;
                --gi;
                --si;
            }
            else{
                --gi;
            }
        }
        
        return res;
    }
}

392. Is Subsequence

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ace” is a subsequence of “abcde” while “aec” is not).

Example:

s = "abc", t = "ahbgdc"
Return true.
s = "axc", t = "ahbgdc"
Return false.

class Solution {
    public boolean isSubsequence(String s, String t) { 
        int sLen = s.length();
        int tLen = t.length();
        
        if(sLen > tLen){
            return false;
        }
        
        int si = 0;
        int ti = 0;
        while(si < s.length() && ti < t.length()){
            if(s.charAt(si) == t.charAt(ti)){
                ++si;
                ++ti;
            }
            else{
                ++ti;
            }
        }
        
        return si == sLen;
    }
}

435. Non-overlapping Intervals

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note:

You may assume the interval’s end point is always bigger than its start point.
Intervals like [1,2] and [2,3] have borders “touching” but they don’t overlap each other.

Example:

Input: [ [1,2], [2,3], [3,4], [1,3] ]
Output: 1
Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.
Input: [ [1,2], [1,2], [1,2] ]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.
Input: [ [1,2], [2,3] ]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

解题思路:

动态规划之最长上升子序列
贪心算法：按照区间的结尾排序，每次选择结尾最早的，且和前一个区间不重叠的区间，这样留给后面的空间才能最大

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    
    class MyComparator implements Comparator<Interval>{
        @Override
        public int compare(Interval o1, Interval o2){
            if(o1.end != o2.end){
                return o1.end - o2.end;
            }
            else{
                return o1.start - o2.start;
            }
        }
    }
    
    public int eraseOverlapIntervals(Interval[] intervals) {
        
        if(intervals.length == 0){
            return 0;
        }
        
        Arrays.sort(intervals, new MyComparator());
        
        int cnt = 1;
        int pre = 0;
        for(int i = 1; i < intervals.length; ++i){
            if(intervals[i].start >= intervals[pre].end){
                ++cnt;
                pre = i;
            }
            
        }
        
        return intervals.length - cnt;
    }
}

Linux搜索命令

发表于 2018-02-27 | 分类于 Linux

文件搜索命令locate

优点：搜索速度快，耗费资源少；
缺点：只能按照文件名搜索

1 2	$ locate 文件名 # 在后台数据库按文件名搜索

1 2	/var/lib/mlocate # locate 命令所搜索的后台数据库

1
2
3

$ updatedb
# 更新数据库，如果没有执行此命令，新创建的文件可能不会搜索到
# 一般是24h更新一次

/etc/updatedb.conf
以下为被locate命令禁止搜索的 文件类、文件路径和文件系统
# PRUNE_BIND_MOUNTS="yes"
# PRUNENAMES=".git .bzr .hg .svn"
# PRUNEPATHS="/tmp /var/spool /media /home/.ecryptfs /var/lib/schroot"
# PRUNEFS="NFS nfs nfs4 rpc_pipefs afs binfmt_misc proc smbfs autofs iso9660 n    cpfs coda devpts ftpfs devfs mfs shfs sysfs cifs lustre tmpfs usbfs udf fuse    .glusterfs fuse.sshfs curlftpfs ecryptfs fusesmb devtmpfs"

命令搜索命令whereis和which

$ whereis 命令名
# 搜索命令所在路径及帮助文档所在位置选项
# -b 只查找可执行文件
# -m 只查找帮助文件

1 2	$ which 命令名 # 查看命令的位置如果命令有别名也会显示

Shell或者系统自带的命令如pwd和cd是不能通过以上两个命令查看

# PATH环境变量：定义的是系统搜索命令的路径
$ echo $PATH
# /home/ackerman/bin:/home/ackerman/.local/bin:/usr/java/jdk1.8.0_144/bin:/usr/java/apache-maven-3.3.3/bin:/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/games:/usr/local/games:/snap/bin

文件搜索命令find

1
2
3

$ find  [搜索范围]  [搜索条件] 
# 搜索文件
# 应该避免大范围的搜索文件，耗费系统资源严重

$ find / -name aaaa.txt
# -iname 不区分大小写
# 文件名搜索是完全匹配
# 常用通配符 ? [] *  文件名最好加双引号，否则可能失效
# $ find / -name "aa[abc]aa.txt"

$ find / -user root
# 按照文件所有者搜索
$ find / -nouser root
# 常用命令，搜索非系统所有者产生的文件
# 比如根目录下的 目录proc 和 sys，内核可能在这两个目录产生交互
# 或者是没有所有者的外来数据，U盘啊，光盘啊

$ find /var/log/ -mtime +10
# atime 文件访问的时间
# ctime 改变文件属性的时间
# mtime 改变文件内容的时间
# +10 10天前修改的文件
# -10 10天内修改的文件
#  10 刚好10天那个24小时内的修改的文件

$ find /etc -size +20k -a -size -5M -exec ls -lh {}  \;
# 查找/etc/目录下，大于20k且小于5M的文件
# -a and 逻辑与
# -o or  逻辑或
# -exec xxx {}  \; 对搜索结果执行xxx操作

搜索字符串命令grep

$ grep [选项] 字符串 文件名
# 在文件中匹配符合条件的字符串
# 选项  -i 忽略大小写
#	   -v 排除指定的字符串
# $ grep -i "catalina" xxx.md

find和grep的区别

find命令：在系统目录当中搜索符合条件的文件名，如果需要匹配，使用通配符匹配，通配符是完全匹配
grep命令：在文件当中搜索条件符合的字符串，如果需要匹配，使用正则表达式匹配，正则表达式是包含匹配

dp

发表于 2018-02-26

Leetcode

70. Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output:  2
Explanation:  There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3
Output:  3
Explanation:  There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

递归版本

class Solution {
    public int climbStairs(int n) {
        if(n == 0 || n == 1){
            return 1;
        }
        
        return climbStairs(n-1) + climbStairs(n-2);
    }
}

dp版本

class Solution {
        
    public int climbStairs(int n) {
        
        int []A = new int[n+1];
        A[0] = 1;
        A[1] = 1;
        
        for(int i = 2; i <= n; ++i){
            A[i] = A[i-1] + A[i-2];    
        }
        
        return A[n];
    }
}

120. Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

Example:

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

解题思路:

自底向上的搜索并记录最小的路径

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int []A = new int[triangle.size()+1];
        
        for(int i = triangle.size()-1; i >= 0; --i){
            List<Integer> row = triangle.get(i);
            
            for(int j = 0; j < row.size(); ++j){
                A[j] = Math.min(A[j], A[j+1]) + row.get(j);
            }
        }
        
        return A[0];
    }
}

64. Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note:

You can only move either down or right at any point in time.

Example:

[
 [1,3,1],
 [1,5,1],
 [4,2,1]
]
 Given the above grid map, return 7. Because the path 1→3→1→1→1 minimizes the sum.

解题思路:

在2X2数组中，从1到4的最小路径只有一条，1 -> 2 -> 4
在1+2+4和1+3+4的比较之后选取的最小值可得
[
	[1, 2],
	[3, 4]
]
依次可类推，除了第一行和第一列之后
所有待处理的元素，都是从上和左中选择最小的元素
直到元素[m-1, n-1]，每次选择的都是最小元素累加得到的

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(i != 0 && j != 0){
                    grid[i][j] = Math.min(grid[i][j-1], grid[i-1][j]) + grid[i][j];
                }
                else if(i == 0 && j != 0){
                    grid[i][j] = grid[i][j-1] + grid[i][j];
                }
                else if(i != 0 && j == 0){
                    grid[i][j] = grid[i-1][j] + grid[i][j];
                }
            }
        }
        
        return grid[m-1][n-1];
    }
}

343. Integer Break

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

Example:

given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

Note:

You may assume that n is not less than 2 and not larger than 58.

递归版本

class Solution {
    private int max3(int x, int y, int z){
        return Math.max(x, Math.max(y, z));
    }
    
    private int breakHelper(int n){
        if(n == 1){
            return 1;
        }
        
        int res = 0;
        for(int i = 1; i < n; ++i){
            res = max3(res, i * (n-i), i * breakHelper(n-i));
        }
        
        return res;
    }
    
    public int integerBreak(int n) {
        return breakHelper(n);
    }
}

自顶向下的记忆化搜索

class Solution {
    private int[] memo;
    
    private int max3(int x, int y, int z){
        return Math.max(x, Math.max(y, z));
    }
    
    private int breakHelper(int n){
        if(n == 1){
            return 1;
        }
        
        if(memo[n] != 0){
            return memo[n];
        }
        
        int res = 0;
        for(int i = 1; i < n; ++i){
            //重叠的子问题 存在memo数组中了,
            //一旦break的元素发现已经被处理，直接取出来
            res = max3(res, i * (n-i), i * breakHelper(n-i));
        }
        
        memo[n] = res;
        
        return res;
    }
    
    public int integerBreak(int n) {
        memo = new int[n+1];
        
        return breakHelper(n);
    }
}

dp版本

class Solution {
    private int max3(int x, int y, int z){
        return Math.max(x, Math.max(y, z));
    }
    
    public int integerBreak(int n) {
        int []memo = new int[n+1];
            
        for(int i = 2; i <= n; ++i){
            for(int j = 1; j < i; ++j){
                //memo[i-j]相当于记忆化搜索时，进入子结构breakHelper()
                memo[i] = max3(memo[i], j * (i-j), j * memo[i-j]);
            }
        }
        
        return memo[n];
    }
}

279. Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

状态转移方程

//      0 1 2 3 4 5 6 7 8 9 10 11
//  1   0 1 2 3 4 5 6 7 8 9 10 11
//  4   0 0 0 0 1 2 3 4 2 3 4  5
//  9   0 0 0 0 0 0 0 0 0 1 2  3
F(i, c) = min{ F(i-1, c), F(i-1, c-v[i]) }

class Solution {
    public int numSquares(int n) {
        int C = n;
        int []memo = new int[C+1];
        Arrays.fill(memo, Integer.MAX_VALUE);
        memo[0] = 0;
        for(int i = 1; i <= C; ++i){
            for(int j = 1; j * j<= i; ++j){
                memo[i] = Math.min(memo[i], 1 + memo[i-j*j]);
            }
        }
        return memo[C];
    }
}

91. Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

Given an encoded message containing digits, determine the total number of ways to decode it.

Example:

Given encoded message “12”, it could be decoded as “AB” (1 2) or “L” (12).

The number of ways decoding “12” is 2.

解题思路:

自右往左

1
2

62. Unique Paths

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

点击加载

解题思路:

对于第一行和第一列，每个元素的可到达路径只有1种
对于其他元素，每个元素可到达的路径都是由上和左两个元素的和

class Solution {
    public int uniquePaths(int m, int n) {
        int [][]memo = new int[m][n];
        memo[0][0] = 1;
        
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(i != 0 && j != 0){
                    memo[i][j] = memo[i][j-1] + memo[i-1][j];
                }
                else{
                    memo[i][j] = 1;
                }
            }
        }
        return memo[m-1][n-1];
    }
}

63. Unique Paths II

Follow up for “Unique Paths”:

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Example:

There is one obstacle in the middle of a 3x3 grid as illustrated below.
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
The total number of unique paths is 2.

解题思路:

若当前元素是1，会干扰到后续元素的判断，
因为它不知道这是障碍或者是路径1
所以开辟新空间给新数组

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;        
        int [][]A = new int[m][n];
        
        if(obstacleGrid[0][0] == 1){
            return 0;
        }
        else{
            A[0][0] = 1;
        }
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(obstacleGrid[i][j] == 1){
                    A[i][j] = 0;
                }
                else if(i != 0 && j != 0){
                    A[i][j] = A[i-1][j] + A[i][j-1];
                }
                else if(i != 0){
                    A[i][j] = A[i-1][j];
                }
                else if(j != 0){
                    A[i][j] = A[i][j-1];
                }
            }
        }
        return A[m-1][n-1];
    }
}

198. House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

解题思路:

1 2	状态转移函数考虑偷取[x...n-1]范围里的房子 f(0) = max{ v(0) + f(2), v(1) + f(3), .... , v(n-3) + f(n-1), v(n-2), v(n-1) }

暴力搜索法

class Solution {
    public int tryRob(int []nums, int index){
        if(index >= nums.length){
            return 0;
        }
        
        int res = 0;
        for(int i = index; i < nums.length; ++i){
            res = Math.max(res, nums[i] + tryRob(nums, i+2));
        }
        
        return res;
    }
    
    public int rob(int[] nums) {
        
        return tryRob(nums, 0);
    }
}

记忆化搜索:

class Solution {
    
    private int[]memo;
    
    public int tryRob(int []nums, int index){
        if(index >= nums.length){
            return 0;
        }
        
        if(memo[index] != -1){
            return memo[index];
        }
        
        int res = 0;
        for(int i = index; i < nums.length; ++i){
            res = Math.max(res, nums[i] + tryRob(nums, i+2));
        }
        memo[index] = res;
        
        return res;
    }
    
    public int rob(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        memo = new int[nums.length];
        for(int i = 0; i < nums.length; ++i){
            memo[i] = -1;
        }
            
        return tryRob(nums, 0);
        
    }
}

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if(n == 0){
            return 0;
        }
        
        int []memo = new int[n];
        memo[n-1] = nums[n-1];
        
        for(int i = n-2; i >= 0; --i){
            for(int j = i; j < n; ++j){
                memo[i] = Math.max(memo[i], nums[j] + (j+2 < n ? memo[j+2] : 0));
            }
        }
        
        return memo[0];
    }
}

121. Best Time to Buy and Sell Stock

Say you have an array for which the Ith element is the price of a given stock on day i.

Example:

Input: [7, 1, 5, 3, 6, 4]
Output: 5
max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
Input: [7, 6, 4, 3, 1]
Output: 0
In this case, no transaction is done, i.e. max profit = 0.

状态转移方程

1	F(i) = max{ maxProfit, F(i+1)}

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length < 2){
            return 0;
        }
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        
        for(int i = 0; i < prices.length; ++i){
            minPrice = Math.min(minPrice, prices[i]);
            maxProfit = Math.max(maxProfit, prices[i] - minPrice);
        }
        
        return maxProfit;
    }
}

0-1背包问题

有一个背包，它的容量为C(capacity)。现在有n种不同的物品，编号为0到n-1，其中每一个物品的重量为W(i)，价值为V(i)，问可以在这个背包中放哪些东西，使得在不超过C的基础上，物品的总价值最大。

1
2
3

F(n, C)考虑将n个物品放入容量为C的背包，使得价值最大
状态转移方程：
F(i, c) = max{ F(i-1, c), v(i) + F(i-1, c-w(i))}

Example:

//记忆化搜索
public class QKnapsack {
    private int [][]memo;
    //用[0 ... index]的物品, 填充容积为C的背包的最大价值
    //index 物品的编号  w[index] 物品的重量
    //                v[index] 物品的价值
    private int bestValue(int []w, int []v, int index, int c){
        if(index < 0 || c <= 0){
            return 0;
        }
        if(memo[index][c] != -1){
            return memo[index][c];
        }
        int res = bestValue(w, v, index-1, c);
        if(c >= w[index]){
            res = Math.max(res, v[index] + bestValue(w, v, index-1, c-w[index]));
        }
        memo[index][c] = res;
        return res;
    }
    public int knapsack01(int []w, int []v, int C){
        int n = w.length;
        memo = new int[n][C+1];
        for(int[] A : memo){
            for(int i = 0; i < A.length; ++i){
                A[i] = -1;
            }
        }
        return bestValue(w, v, n-1, C);
    }
}

//动态规划
    public int knapsack01_1(int []w, int []v, int C){
        assert (w.length == v.length);
        int n = w.length;
        if(n == 0){
            return 0;
        }
        
        int [][] memo = new int[n][C+1];
        for(int []A : memo){
            for(int i = 0; i < A.length; ++i){
                A[i] = -1;
            }
        }
        
        //编号0的物品, 尝试放入背包内
        for(int k = 0; k <= C; ++k){
            memo[0][k] = (k >= w[0]) ? v[0] : 0;
        }
        
        for(int i = 1; i < n; ++i){
            for(int j = 0; j <= C; ++j){
                memo[i][j] = memo[i-1][j];  //当前物品i不放入背包的情况
                //背包空间足够
                if(j >= w[i]){  
                    //memo[i-1][j-w[i]] 当存入物品i-1的时,并且空间只有j-w[i]的情况下
                    memo[i][j] = Math.max(memo[i][j], v[i]+memo[i-1][j-w[i]]);
                }
            }
        }
        
        return memo[n-1][C];
    }

dp优化

空间优化
第i行元素只依赖于第i-1行元素，理论上只需要保持两行元素
空间复杂度 O(2*C) = O(C)

public int knapsack01_2(int []w, int v, int C){
     
    ...
    int [][] memo = new int[2][C+1];    //只创建两行背包
    ...
    for(int i = 1; i < n; ++i){
        for(int j = 0; j <= C; ++j){
            memo[i%2][j] = memo[(i-1)%2][j];  //当前物品i不放入背包的情况
            //背包空间足够
            if(j >= w[i]){
                //memo[i-1][j-w[i]] 当存入物品i-1的时,并且空间只有j-w[i]的情况下
                memo[i%2][j] = Math.max(memo[i%2][j], v[i]+memo[(i-1)%2][j-w[i]]);
            }
        }
    }
    
    return memo[(n-1)%2][C];
}

空间和时间的同时优化

public int knapsack01_3(int []w, int []v, int C){
    int n = w.length;
    
    int []memo = new int[C+1];
    for(int i = 0; i < memo.length; ++i){
        memo[i] = -1;
    }
    
    for(int k = 0; k <= C; ++k){
        memo[k] = (k >= w[0]) ? v[0] : 0;
    }
    
    for(int i = 1; i < n; ++i){
        for(int j = C; j >= w[i]; --j){
            //现在只有一行空间，memo索引考虑的是背包的容量
            memo[j] = Math.max(memo[j], v[i]+memo[j-w[i]]);
        }
    }
    
    return memo[C];
}

416. Partition Equal Subset Sum

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Example:

Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

Note:

Each of the array element will not exceed 100.
The array size will not exceed 200.

解题思路:

F(n, C)考虑将n个物品填满容量为C的背包

1
2
3

F(i, c) = F(i-1, c) || F(i-1, c - w(i))
时间复杂度 O(n * sum/2) = 100 * 100*200/2 = 100万

//记忆化搜索
class Solution {
    //memo[index][c] 表示使用索引index为[0...index]的这些元素
    //是否可以完全填充一个容量为C的背包
    //-1表示未计算，0表示不可以，1表示可以
    private int [][]memo;
    
    //使用nums[0...index]，是否可以完全填充一个容量为c的背包
    private boolean tryPartition(int []nums, int index, int c){
        if(c == 0){
            return true;
        }
        
        if(index < 0 || c < 0){
            return false;
        }
        
        if(memo[index][c] != -1){
            return memo[index][c] == 1;
        }
        
        memo[index][c] = (tryPartition(nums, index-1, c) ||
                tryPartition(nums, index-1, c-nums[index])) ? 1 : 0;
        
        return memo[index][c] == 1;
    }
    
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int a : nums){
            sum += a;
        }
        
        if(sum % 2 == 1){
            return false;
        }
        
        int C = sum/2;
        int n = nums.length;
        memo = new int[n][C+1];
        for(int []A : memo){
            for(int i = 0; i < A.length; ++i){
                A[i] = -1;
            }
        }
        
        return tryPartition(nums, n-1, C);
    }
}

//动态规划
class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int a : nums){
            sum += a;
        }
        
        if(sum % 2 == 1){
            return false;
        }
        
        int C = sum/2;
        int n = nums.length;
        boolean [][]memo = new boolean[n][C+1];
        for(int k = 0; k <= C; ++k){
            memo[0][k] = (k == nums[0]);    //当只有索引0元素的时候，背包容量为k的是否刚好被完全填充
        }
        
        for(int i = 1; i < n; ++i){
            for(int j = 0; j <= C; ++j){
                memo[i][j] = memo[i-1][j];  //索引i不加入背包 ---1
                //此时背包容量j足够填充nums[i]
                if(j >= nums[i]){
                    //当加入索引i,背包容量剩余j-nums[i]
                    //此时索引i-1在容量为j-nums[i]的情况下是否能够满足，与情况1取或运算
                    memo[i][j] = memo[i][j] || memo[i-1][j-nums[i]];
                }
            }
        }
        
        return memo[n-1][C];
    }
}

dp优化

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int a : nums){
            sum += a;
        }
        
        if(sum%2 == 1){
            return false;
        }
        int C = sum/2;
        int n = nums.length;
        boolean []memo = new boolean[C+1];
        for(int k = 0; k < memo.length; ++k){
            memo[k] = (k == nums[0]) ;
        }
        
        for(int i = 1; i < n; ++i){
            for(int j = C; j >= nums[i]; --j){
                memo[j] = memo[j] || memo[j-nums[i]];
            }
        }
        
        return memo[C];
    }
}

322. Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example:

coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)
coins = [2], amount = 3
return -1.

Note: 完全背包问题

1	You may assume that you have an infinite number of each kind of coin.

状态转移方程

1	F(i, c) = min{ F(i-1, c), F(i-1, c-v[1])+1, F(i-1, c-v[2])+1, ..., F(i-1, c-v[x])+1 }

class Solution {
    
    public int coinChange(int[] coins, int amount) {
        int C = amount;
        int n = coins.length;
        int []memo = new int[C+1];
        Arrays.fill(memo, C+1);
        
        memo[0] = 0;
        
        for(int i = 1; i <= C; ++i){
            for(int j = 0; j < n; ++j){
                if(coins[j] <= i){
                    memo[i] = Math.min(memo[i], memo[i-coins[j]]+1);
                }
            }
        }
        
        return memo[C] > C ? -1 : memo[C];
    }
}

139. Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.

Example:

given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".

状态转移方程

1	F(i, s) = F(i-1, s-word) && F(i, word)

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int C = s.length();
        boolean []memo = new boolean[C+1];
        memo[0] = true;
        for(int i = 1; i <= C; ++i){
            for(int j = 0; j < i; ++j){
                memo[i] = memo[j] && wordDict.contains(s.substring(j, i));
                if(memo[i]){
                    break;
                }
            }
        }
        
        return memo[C];
    }
}

377. Combination Sum IV

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.
Therefore the output is 7.

状态转移方程

1	F(i, c) = F(i-1) + F(c-v[i])

n\C - 1 2 3 4	1 2 3 4		1 2 3 4		1 2 3 4
------------------------------------------------------
1   - 1 0 0 0	1 1 0 0		1 1 1 0		1 1 1 1
2   - 0 0 0 0	0 2 0 0		0 2 3 0		0 2 3 5
3   - 0 0 0 0	0 0 0 0		0 0 4 0		0 0 4 7

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int C = target;
        int n = nums.length;
        int memo[] = new int[C+1];
        memo[0] = 1;
        for(int i = 1; i <= C; ++i){
            for(int j = 0; j < n; ++j){
                if(nums[j] <= i){
                    memo[i] += memo[i-nums[j]];
                }
            }
        }
        return memo[C];
    }
}

最长上升子序列

300. Longest Increasing Subsequence

LIS(i) 表示以第i个数字为结尾的最长上升子序列的长度
即[0, …, i]的范围内，选择数字nums[i]可以获得的最长上升子序列的长度

1	LIS(i) = max(1 + LIS(j) if(nums[i] > nums[j])), 任意i > j

class Solution {
    public int lengthOfLIS(int[] nums) {
        
        int n = nums.length;
        int []memo = new int[n];
        Arrays.fill(memo, 1);
        
        for(int i = 1; i < n; ++i){
            for(int j = 0; j < i; ++j){
                if(nums[i] > nums[j]){
                    memo[i] = Math.max(memo[i], memo[j]+1);
                }
            }
        }
        
        int res = 0;
        for(int i = 0; i < n; ++i){
            res = Math.max(res, memo[i]);
        }
        
        return res;
    }
}

300-1. Print LIS

376. Wiggle Subsequence

状态转移方程

i = j+1
if nums[i] > nums[j]:
	up = down +1
else nums[i] < nums[j]:
	down = up+1

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        
        int n = nums.length;
        int []up = new int[n];
        int []down = new int[n];
        
        up[0] = 1;
        down[0] = 1;
        
        for(int i = 1; i < n; ++i){
            if(nums[i-1] < nums[i]){
                up[i] = down[i-1] + 1;
                down[i] = down[i-1];
            }
            else if(nums[i-1] > nums[i]){
                up[i] = up[i-1];
                down[i] = up[i-1]+1;
            }
            else{
                up[i] = up[i-1];
                down[i] = down[i-1];
            }
        }
        
        return Math.max(up[n-1], down[n-1]);
    }
}

优化版本

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        
        int up = 1;
        int down = 1;
        for(int i = 1; i < nums.length; ++i){
            if(nums[i-1] < nums[i]){
                up = down+1;
            }
            else if(nums[i-1] > nums[i]){
                down = up + 1;
            }
        }
        
        return Math.max(down, up);
    }
}

最长公共子序列

(Lintcode)77. Longest Common Subsequence

状态转移方程

LCS(m,n ) S1[0 ... m]和S2[0 .. n ]的最长公共子序列
if S1[m] == S2[n]:
	LCS(m, n) = 1 + LCS(m-1, n-1);
else:
	LCS(m, n) = max{ LCS(m-1, n), LCS(m, n-1) }

public int longestCommonSubsequence(String A, String B) {
    int m = A.length();
    int n = B.length();
    int [][]memo = new int[m+1][n+1];
    for(int i = 1; i <= m; ++i){
        for(int j = 1; j <= n; ++j){
            if(A.charAt(i-1) == B.charAt(j-1)){
                memo[i][j] = 1 + memo[i-1][j-1];
            }
            else{
                memo[i][j] = Math.max(memo[i-1][j], memo[i][j-1]);
            }
        }
    }
    return memo[m][n];
}

回溯

发表于 2018-02-22

Leetcode

17. Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

2 - abc
3 - def
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Although the above answer is in lexicographical order, your answer could be in any order you want.

class Solution {
    
    private String []letterMap = new String[]{
        " ",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz"
    };
    
    private List<String> res = new ArrayList<String>();
    
    private void helper(String digits, int index, String s){
        if(index == digits.length()){
            res.add(s);
            return;
        }
        char c = digits.charAt(index);
        String letter = letterMap[c - '0'];
        for(int i = 0; i < letter.length(); ++i){
            helper(digits, index + 1, s + String.valueOf(letter.charAt(i)));
        }
    }
    
    public List<String> letterCombinations(String digits) {
        if(digits == null || digits.equals("")){
            return res;
        }        
        
        helper(digits, 0, "");
        
        return res;
    }
}

93. Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:

1
2
3

Given "25525511135",
return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

class Solution {
    
    private Set<String> set = new HashSet<>();
    private boolean isValid(String str){
        String []S = str.split("\\.");
        int []A = new int[4];
        for(int i = 0; i < S.length; ++i){
            A[i] = Integer.valueOf(S[i]);
            if(A[i] > 255 || A[i] < 0 || (S[i].charAt(0) == '0' && S[i].length() != 1)){
                return;
            }
            S[i] = String.valueOf(A[i]);
        }
        set.add(String.join(".", S));
    }
    private void helper(char []chars, int index, StringBuilder sb){
        if(sb.length() == chars.length + 3){
            isValid(sb.toString());
            return;
        }
        for(int i = index; i < sb.length()-1; ++i){
            StringBuilder sb2 = new StringBuilder(sb);
            sb2.insert(i+1, '.');
            helper(chars, i+2, sb2);
        }
    }
    public List<String> restoreIpAddresses(String s) {
        if(s == null || s.length() == 0 || s.length() >= 13){
            return new ArrayList<>();
        }
        helper(s.toCharArray(), 0, new StringBuilder(s));
        return new ArrayList<>(set);
    }
}

131. Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

given s = “aab”, return

 [
  ["aa","b"],
  ["a","a","b"]
]

class Solution {
    private  List<List<String>> list2;
    private boolean isPalindrome(String s, int lo, int hi){
        if(lo == hi){
            return true;
        }
        while(lo < hi ) {
            if(s.charAt(lo++) != s.charAt(hi--)){
                return false;
            }
        }
        return true;
    }
    private void helper(String s, int index, Stack<String> stack){
        if(!stack.isEmpty() && index == s.length()){
            list2.add(new ArrayList<>(stack));
            return ;
        }
        for(int i = index; i < s.length(); ++i){
            if(isPalindrome(s, index, i)){
                stack.push(s.substring(index, i+1));
                helper(s, i+1, stack);
                stack.pop();
            }
        }
    }
    public List<List<String>> partition(String s) {
        list2 = new ArrayList<List<String>>();
        if(s == null || s.length() == 0){
            return list2;
        }
        helper(s, 0, new Stack<String>());
        return list2;
    }
}

46. Permutations

Given a collection of distinct numbers, return all possible permutations.

Example:

[1,2,3] have the following permutations:

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

class Solution {
    private List<List<Integer>> list2;
    private boolean []visited;
    
    private void helper(int []A, int index, Stack<Integer> stack){
        if(index == A.length){
            list2.add(new ArrayList<Integer>(stack));
            return;
        }        
        
        for(int i = 0; i < A.length; ++i){
            if(!visited[i]){
                visited[i] = true;
                stack.push(A[i]);
                
                helper(A, index+1, stack);
                
                stack.pop();
                visited[i] = false;
            }
        }
        
    } 
    
    public List<List<Integer>> permute(int[] nums) {
        list2 = new ArrayList<List<Integer>>();
        if(nums == null || nums.length == 0 ){
            return list2;
        }
        
        visited = new boolean[nums.length];
        
        helper(nums, 0, new Stack<Integer>());
        
        return list2;
    }
}

47. Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

[1,1,2] have the following unique permutations:

[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

class Solution {
    private List<List<Integer>> list2 = new ArrayList<List<Integer>>();
    private boolean []visited;
    
    private void helper(int []A, int cnt, Stack<Integer> stack){
        if(cnt == A.length){
            list2.add(new ArrayList<Integer>(stack));
            return;
        }
        
        for(int i = 0; i < A.length; ++i){
            //元素X只能在某次递归中使用一次
            if(i != 0 && A[i-1] == A[i] && visited[i-1]){
                continue;
            }
            
            if(!visited[i]){
                visited[i] = true;
                stack.push(A[i]);
                
                helper(A, cnt+1, stack);
                
                stack.pop();
                visited[i] = false;
            }
        }
    }
    
    public List<List<Integer>> permuteUnique(int[] nums) {
        if(nums == null || nums.length == 0){
            return list2;
        }
        
        Arrays.sort(nums);
        visited = new boolean[nums.length];
            
        helper(nums, 0, new Stack<Integer>());
        
        return list2;
    }
}

77. Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

Example:

If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

//组合问题
class Solution {
    private List<List<Integer>> list2;
    
    private void helper(int n, int k, int index, List<Integer> list){
        if(k == list.size()){
            list2.add(list.clone());
            return;
        }
        
        for(int i = index; i <= n; ++i){
            list.add(i);
            helper(n, k, i+1, list);
            list.remove(list.size()-1);
        }
    }
    
    public List<List<Integer>> combine(int n, int k) {
        list2 = new ArrayList<List<Integer>>();
        
        if(n <= 0 || k <= 0 || n < k){
            return list2;
        }
        
        helper(n, k, 1, new ArrayList<Integer>());
        
        return list2;
    }
}

回溯剪枝

//list还需求 k - list.size()个元素
//[i, n]中至少要有 k - list.size()个元素
//i最多为为 n - (k-list.size()) + 1 个元素
for(int i = index; i <= n-(k-list.size())+1; ++i)

39. Combination Sum

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

Example:

given candidate set [2, 3, 6, 7] and target 7,
A solution set is:

[
  [7],
  [2, 2, 3]
]

class Solution {
    private List<List<Integer>> list2;
    private boolean []visited;
    
    private void helper(int []A, int target, int sum, Stack<Integer> stack, int index){
        if(target == sum){
            list2.add(new ArrayList<Integer>(stack));
            return;
        }
        else if(target < sum){
            return;
        }
        
        // [2, 2, 3] , [2, 3, 2] 是不行的
        for(int i = index; i < A.length; ++i){
            if(!stack.isEmpty() && stack.peek() > A[i]){
                continue;
            }
            sum += A[i];
            stack.push(A[i]);
            
            helper(A, target, sum, stack, index);
            
            stack.pop();
            sum -= A[i];
        }
    }
    
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        list2 = new ArrayList<List<Integer>>();
        
        if(candidates == null){
            return list2;
        }
        
        visited = new boolean[candidates.length];
        
        Arrays.sort(candidates);
        
        helper(candidates, target, 0, new Stack<Integer>(), 0);
        
        return list2;
    }
}

剪枝

for(int i = index; i < A.length && target >= sum + A[i]; ++i){
	...
	helper(A, target, sum, stack, i);
	...
}

40. Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

Example:

given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

class Solution {
    private List<List<Integer>> list2;
    
    private void helper(int []A, int remain, Stack<Integer> stack, int index){
        if(remain == 0){
            list2.add(new ArrayList<Integer>(stack));
            return;
        }
        else if(remain < 0){
            return;
        }
        
        for(int i = index; i < A.length; ++i){
            if(i > index && A[i] == A[i-1]){
                continue;
            }
            stack.push(A[i]);
            helper(A, remain-A[i], stack, i+1);
            stack.pop();
        }
    }
    
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        list2 = new ArrayList<List<Integer>>();
        if(candidates == null){
            return list2;
        }
        Arrays.sort(candidates);
        
        helper(candidates, target, new Stack<Integer>(), 0);
        
        return list2;
    }
}

剪枝

1	for(int i = index; i < A.length && A[i] <= remain; ++i)

216. Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example:

Input: k = 3, n = 7
Output:
[[1,2,4]]

Input: k = 3, n = 9
Output:
[[1,2,6], [1,3,5], [2,3,4]]

class Solution {
    private List<List<Integer>> list2;
    
    private void helper(int k, int remain, Stack<Integer> stack, int index){
        if(k == stack.size()){
            if(remain == 0){
                list2.add(new ArrayList<Integer>(stack));
            }
            return;
        }
        
        for(int i = index; i <= 9; ++i){
            stack.push(i);
            helper(k, remain-i, stack, i+1);
            stack.pop();
        }
    }
    
    public List<List<Integer>> combinationSum3(int k, int n) {
        list2 = new ArrayList<List<Integer>>();
        if(k <= 0 || n <= 0 || n <= k){
            return list2;
        }
        helper(k, n, new Stack<Integer>(), 1);
        
        return list2;
    }
}

剪枝

//stack还需要 k-stack.size()个元素
//[i, 9]中至少还需要有 k-stack.size()个元素
//i最多可以是 9 - (k-stack.size()) + 1 
for(int i = index; i <= 10 -k + stack.size() && i <= remain; ++i)

78. Subsets

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note:

The solution set must not contain duplicate subsets.

Example:

If nums = [1,2,3], a solution is:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

class Solution {
    private List<List<Integer>> list2;
    
    private void helper(int []A, Stack<Integer> stack, int index){
        if(stack.size() <= A.length){
            list2.add(new ArrayList<Integer>(stack));
            //这里不能return,因为每一次递归调用都有stack要加入list2
        }
        
        for(int i = index; i < A.length; ++i){
            stack.push(A[i]);
            helper(A, stack, i+1);
            stack.pop();
        }
    }
    
    public List<List<Integer>> subsets(int[] nums) {
        list2 = new ArrayList<List<Integer>>();
        
        if(nums == null){
            return list2;
        }
        
        helper(nums, new Stack<Integer>(), 0);
        
        return list2;
    }
}

90. Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note:

The solution set must not contain duplicate subsets.

Example:

If nums = [1,2,2], a solution is:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

class Solution {
    private List<List<Integer>> list2;
    
    private void helper(int []A, Stack<Integer> stack, int index){
        if(stack.size() <= A.length){
            list2.add(new ArrayList<Integer>(stack));
        }
        
        //每一轮递归中的for循环，相同元素只能被用一次
        //例如 [2, 2]  第一个2和第二个2的组只能有 [] [2] [2, 2]
        //或者 [1, 2, 2] 对于元素1来说，和前后两个元素2的组合策略是一样的
        for(int i = index; i < A.length; ++i){
            if(index < i && A[i] == A[i-1]){
                continue;
            }
            stack.push(A[i]);
            helper(A, stack, i+1);
            stack.pop();
        }
    }
    
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        list2 = new ArrayList<List<Integer>>();
        
        if(nums == null){
            return list2;
        }
        Arrays.sort(nums);
        helper(nums, new Stack<Integer>(), 0);
        
        return list2;
    }
}

401. Binary Watch

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).

private List<String> list;
private boolean visited[];
// visited[10]
// 1 2 4 8 1 2 4 8 16 32
private String caculateTime(){
    int min = 0;
    int sec = 0;
    
    for(int i = 0; i < 10; ++i){
        if(i < 4 && visited[i]){
            min += Math.pow(2, i);
        }
        else if(visited[i]){
            sec += Math.pow(2, i-4);
        }
    }
    String m = min + ":";
    String s = sec < 10 ? "0"+sec : String.valueOf(sec);
    return m+s;
}
private void helper(int remain, int index){
    if(remain == 0){
        list.add(caculateTime());
        return;
    }
    for(int i = index; i < 10; ++i){
        visited[i] = true;
        
        //不满足 min(4,8) 或者 sec(32, 16, 8, 4)的情况下
        //才递归
        if(!(visited[2] && visited[3] ||
                visited[9] && visited[8] && visited[7] && visited[6])){
            helper(remain-1, i+1);
        }
        visited[i] = false;
    }
}
public List<String> readBinaryWatch(int num) {
    list = new ArrayList<String>();
    visited = new boolean[10];
    helper(num, 0);
    return list;
}

79. Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

example:

Given board  =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

class Solution {
    private boolean [][]visited;
    private int [][]d;
    private int m;
    private int n;
    
    private boolean isValidPos(int x, int y){
        return x >= 0 && x < m && y >=0 && y < n;
    }
    
    private boolean helper(char [][]board, String word, int index, int x, int y){
        if(index == word.length()-1){
            return word.charAt(index) == board[x][y];
        }
        
       
        if(board[x][y] == word.charAt(index)){
            visited[x][y] = true;
            
            for(int i = 0; i < 4; ++i){
                int newX = x + d[i][0];
                int newY = y + d[i][1];
                if(isValidPos(newX, newY) && !visited[newX][newY] && 
                        helper(board, word, index+1, newX, newY)){
                    
                    return true;
                }
            }
            
            visited[x][y] = false;
        }
        
        
        return false;
    }
    
    
    public boolean exist(char[][] board, String word) {
        m = board.length;
        n = board[0].length;
        visited = new boolean[m][n];
        d = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(helper(board, word, 0, i, j)){
                    return true;
                }
            }
        }
        
        return false;
    }
}

200. Number of Islands

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

11110
11010
11000
00000
Answer: 1

Example 2:

11000
11000
00100
00011
Answer: 3

class Solution {
    private boolean [][]visited;
    private int [][]d;
    private int m;
    private int n;
    
    private boolean inArea(int x, int y){
        return x >= 0 && x < m && y >= 0 && y < n;
    }
    
    private void dfs(char [][]grid, int x, int y){
        //不需要递归终止条件
        //dfs一直搜索直到(x, y)四周都被搜索了
        
        if(!visited[x][y]){
            visited[x][y] = true;
            for(int i = 0; i < 4; ++i){
                int newX = d[i][0] + x;
                int newY = d[i][1] + y;
                if(inArea(newX, newY) && grid[newX][newY] == '1' && !visited[newX][newY]){
                    dfs(grid, newX, newY);
                }
            }
        }
    }
    
    public int numIslands(char[][] grid) {
        if(grid == null || grid.length == 0){
            return 0;
        }
        
        int cnt = 0;
        m = grid.length;
        n = grid[0].length;
        visited = new boolean[m][n];
        d = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(!visited[i][j] && grid[i][j] == '1' ){
                    ++cnt;
                    dfs(grid, i, j);
                }
            }
        }
        
        return cnt;
    }
}

130. Surrounded Regions

Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.

A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

解题思路:

这道题使用DFS

Example:

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X

StackOverflow做法

当测试数量大，并且包含大量的’O’，递归调用breakSurrounded太深，爆

class Solution {
    private int m;
    private int n;
    private boolean [][]visited;
    private int [][]d;
    private boolean outOfArea(int x, int y){
        return x < 0 || x >= m || y < 0 || y >= n; 
    }
    private boolean breakSurrounded(char [][]board, int x, int y){
        if(board[x][y] == 'X'){
            return false;
        }
        
        if(!visited[x][y]){
            visited[x][y] = true;
            for(int i = 0; i < 4; ++i){
                int newX = x + d[i][0];
                int newY = y + d[i][1];
                if(outOfArea(newX, newY) ||
                        !visited[newX][newY] && board[newX][newY] == 'O' &&
                         breakSurrounded(board, newX, newY)){
                    visited[x][y] = false;
                    return true;
                }
            }
            visited[x][y] = false;
        }
        return false;
    }
    public void solve(char[][] board) {
        if(board == null || board.length == 0){
            return;
        }
        m = board.length;
        n = board[0].length;
        visited = new boolean[m][n];
        d = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for(int i = 1; i < board.length - 1; ++i){
            for(int j = 1; j < board[0].length - 1; ++j){
                if(board[i][j] == 'O' && !breakSurrounded(board, i, j)){
                    board[i][j] = 'X';
                }
            }
        }
    }
}

优化做法

class Solution {
    private boolean[][] visited;
    private int [][]d;
    private int m;
    private int n;
    
    private boolean inArea(int x, int y){
        return x >= 0 && x < m && y >= 0 && y < n;
    }
    
    private void digChannel(char [][]board, int x, int y){
        if(board[x][y] == 'X'){
            visited[x][y] = true;
            return;
        }
        else if(board[x][y] == 'O'){
            board[x][y] = '*';
        }
        
        if(!visited[x][y]){
            visited[x][y] = true;
            for(int i = 0; i < 4; ++i){
                int newX = x + d[i][0];
                int newY = y + d[i][1];
                if(inArea(newX, newY) && !visited[newX][newY]){
                    digChannel(board, newX, newY);
                }
            }
        }
    }
    public void solve(char[][] board) {
        if(board == null || board.length == 0){
            return;
        }
        
        m = board.length;
        n = board[0].length;
        visited = new boolean[m][n];
        d = new int[][]{{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
        
        for(int i = 0; i < n; ++i){
            if(board[0][i] == 'O'){
                digChannel(board, 0, i);
            }
            if(board[m-1][i] == 'O'){
                digChannel(board, m-1, i);
            }
        }
        
        for(int i = 0; i < m; ++i){
            if(board[i][0] == 'O'){
                digChannel(board, i, 0);
            }
            if(board[i][n-1] == 'O'){
                digChannel(board, i, n-1);
            }
        }
        
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(board[i][j] == 'X'){
                    continue;
                }
                else{
                    board[i][j] = board[i][j] == '*' ? 'O' : 'X';
                }
            }
        }
    }
}

417. Pacific Atlantic Water Flow

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the “Pacific ocean” touches the left and top edges of the matrix and the “Atlantic ocean” touches the right and bottom edges.

Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

Note:

he order of returned grid coordinates does not matter.
Both m and n are less than 150.

Given the following 5x5 matrix:
  Pacific ~   ~   ~   ~   ~ 
       ~  1   2   2   3  (5) *
       ~  3   2   3  (4) (4) *
       ~  2   4  (5)  3   1  *
       ~ (6) (7)  1   4   5  *
       ~ (5)  1   1   2   4  *
          *   *   *   *   * Atlantic
Return:
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

解题思路:

东南方向和西北方向的深度优先搜索

private List<int[]> intArrayList;
private int m;
private int n;
private int [][]direction;
private boolean[][] visited;
private boolean inPacific(int x, int y){
    return x < 0 || y < 0;
}
private boolean inAtlantic(int x, int y){
    return x >= m || y >= n;
}
private boolean inArea(int x, int y){
    return x >= 0 && x < m && y >= 0 && y < n;
}
private boolean flowToPacific(int [][]matrix, int x, int y){
    visited[x][y] = true;
    for(int i = 0; i < 4; ++i){
        int newX = direction[i][0] + x;
        int newY = direction[i][1] + y;
        if(inPacific(newX, newY) ||
               inArea(newX, newY)&& !visited[newX][newY] && matrix[newX][newY] <= matrix[x][y] && flowToPacific(matrix, newX, newY)){
		
            //回溯的时候访问过的点要置为false
            //否则会影响以后的点
            visited[x][y] = false;
            return true;
        }
    }
    visited[x][y] = false;
    return false;
}
private boolean flowToAtlantic(int [][]matrix, int x, int y){
    visited[x][y] = true;
    for(int i = 0; i < 4; ++i){
        int newX = direction[i][0] + x;
        int newY = direction[i][1] + y;
        if(inAtlantic(newX, newY) ||
                inArea(newX, newY)&& !visited[newX][newY] && matrix[newX][newY] <= matrix[x][y] && flowToAtlantic(matrix, newX, newY)){
            visited[x][y] = false;
            return true;
        }
    }
    visited[x][y] = false;
    return false;
}
public List<int[]> pacificAtlantic(int[][] matrix) {
    intArrayList = new ArrayList<int[]>();
    if(matrix == null ||matrix.length == 0){
        return intArrayList;
    }
    direction = new int[][]{{-1, 0}, { 0, -1}, {1, 0}, {0, 1}};
    m = matrix.length;
    n = matrix[0].length;
    visited = new boolean[m][n];
    for(int i = 0; i < matrix.length; ++i){
        for(int j = 0; j < matrix[0].length; ++j){
            if(flowToPacific(matrix, i, j) && flowToAtlantic(matrix, i, j)){
               intArrayList.add(new int[]{i, j});
            }
        }
    }
    return intArrayList;
}

51. N-Queens

Example:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],
 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

class Solution {
    private List<List<String>> list2;
    private boolean []col;
    private boolean []dia1;
    private boolean []dia2;
    private List<String> generateBoard(Stack<Integer> rowLine, int n){
        List<String> list = new ArrayList<String>();
        for(int i = 0; i < rowLine.size(); ++i){
            StringBuilder sb = new StringBuilder();
            int y = rowLine.get(i);
            for(int j = 0; j < n; ++j){
                if(y == j){
                    sb.append('Q');
                }
                else{
                    sb.append('.');
                }
            }
            list.add(sb.toString());
        }
        return list;
    }
    private void putQueue(int n, int x, Stack<Integer> rowLine){
        if(n == x){
            list2.add(generateBoard(rowLine, n));
            return;
        }
        for(int y = 0; y < n; ++y){
            if(!col[y] && !dia1[x+y] && ! dia2[x-y+n-1]) {
                rowLine.push(y);
                col[y] = true;
                dia1[x+y] = true;
                dia2[x-y+n-1] = true;
                putQueue(n, x+1, rowLine);
                col[y] = false;
                dia1[x+y] = false;
                dia2[x-y+n-1] = false;
                rowLine.pop();
            }
        }
    }
    public List<List<String>> solveNQueens(int n) {
        list2 = new ArrayList<List<String>>();
        col = new boolean[n];
        dia1 = new boolean[2*n-1];
        dia2 = new boolean[2*n-1];
        putQueue(n, 0, new Stack<Integer>());
        return list2;
    }
}

52. N-Queens II

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

class Solution {
    private boolean []col;
    private boolean []dia1;
    private boolean []dia2;
    private int res;
    private void putQueensSolutions(int n, int x, Stack<Integer> rowLine){
        if(n == x){
            res += 1;
        }
        
        for(int y = 0; y < n; ++y){
            if(!col[y] && !dia1[x+y] && !dia2[x-y+n-1]){
                col[y] = true;
                dia1[x+y] = true;
                dia2[x-y+n-1] = true;
                putQueensSolutions(n, x+1, rowLine);
                col[y] = false;
                dia1[x+y] = false;
                dia2[x-y+n-1] = false;
            }
        }
    }
    public int totalNQueens(int n){
        col = new boolean[n];
        dia1 = new boolean[2*n-1];
        dia2 = new boolean[2*n-1];
        res = 0;
        putQueensSolutions(n, 0, new Stack<Integer>());
        return res;
    }
}

37. Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character ‘.’.

You may assume that there will be only one unique solution.

解题思路:

很脑瓜子疼的一道题目，
想不明白

private boolean isValid(char [][]board, int x, int y, char c){
    for(int i = 0; i < board[x].length; ++i){
        //行判断
        if(board[x][i] != '.' && c == board[x][i]){
            return false;
        }
        //列判断
        if(board[i][y] != '.' && c == board[i][y]){
            return false;
        }
        //9宫格判断
        if(board[3*(x/3)+i/3][3*(y/3)+i%3] !='.' &&
                board[3*(x/3)+i/3][3*(y/3)+i%3] == c){
            return false;
        }
    }
    return true;
}
public boolean putNumbers(char[][] board){
    for(int i = 0; i < board.length; ++i){
        for(int j = 0; j < board[0].length; ++j){
            if(board[i][j] == '.'){
                for(char ch = '1'; ch <= '9'; ++ch){
                    if(isValid(board, i, j, ch)){
                        board[i][j] = ch;
                        if(putNumbers(board)){
                            return true;
                        }
                        else{
                            board[i][j] = '.';
                        }
                    }
                }
                return false;
            }
        }
    }
    return true;
}
public void solveSudoku(char[][] board) {
    if(board == null || board.length == 0){
        return;
    }
    putNumbers(board);
}

二叉树

发表于 2018-02-19 | 分类于 Catalina

Leetcode

104. Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

For example:
Given binary tree [3,9,20,null,null,15,7],

return its depth = 3.

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        
        //+1是当前的节点
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

111. Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

解题思路:

与上一题不同之处在于：找最小距离要注意，可能存在左右子树为空的情况，此时值就为0，但显然值是不为0的（只有当二叉树为空才为0），所以，在这里注意一下即可！

class Solution {
    public int minDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        return (left == 0 || right == 0) ? left+right+1 : Math.min(left, right) + 1;
    }
}

226. Invert Binary Tree

Invert a binary tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

     4
   /   \
  7     2
 / \   / \
9   6 3   1

解题思路:

翻转二叉树

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return root;
        }
        
        TreeNode temp = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(temp);
        
        return root;
    }
}

100. Same Tree

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null){
            return true;
        }
        
        if(p != null && q != null){
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right) && p.val == q.val;
        }
        
        return false;
    }
}

101. Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        return helper(root.left, root.right);
    }
    
    public boolean helper(TreeNode l, TreeNode r){
        if(l == null && r == null){
            return true;
        }
        if(l != null && r != null){
            return l.val == r.val && helper(l.left, r.right) && helper(l.right, r.left);
        }
        
        return false;
    }
}

222. Count Complete Tree Nodes

Given a complete binary tree, count the number of nodes.

class Solution {
    public int countNodes(TreeNode root) {
        if(root == null){
            return 0;
        }
        
        int lHeight = height(root.left);
        int rHeight = height(root.right);
        if(lHeight == rHeight){
            return (1 << lHeight) + countNodes(root.right);
        }
        else{
            return (1 << rHeight) + countNodes(root.left);
        }
    }
    
    private int height(TreeNode node){
        if(node == null){
            return 0;
        }
        return 1 + height(node.left);
    }
}

110. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        
        return helper(root, 0) != -1;
    }
    
    int helper(TreeNode node, int height){
        if(node == null){
            return height;
        }
        
        int lHeight = helper(node.left, height + 1);
        int rHeight = helper(node.right, height + 1);
        
        if(Math.abs(lHeight - rHeight) > 1){
            return -1;
        }
        
        return Math.max(lHeight, rHeight);
    }
}

112. Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Example:

Given the below binary tree and sum = 22

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null){
            return false;
        }
        
        if(root.left == null && root.right == null){
            return root.val == sum;
        }
        
        sum -= root.val;
        
        return hasPathSum(root.left, sum) ||
                hasPathSum(root.right, sum);
        
    }
}

404. Sum of Left Leaves

Find the sum of all left leaves in a given binary tree.

Example:

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null){
            return 0;
        }
        
        int res = 0;
        if(root.left != null){
            if(root.left.left == null && root.left.right == null){
                res += root.left.val;
            }
            else{
                res += sumOfLeftLeaves(root.left);
            }
        }
        
        res += sumOfLeftLeaves(root.right);
        
        return res;
    }
}

257. Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.

Example:

All root-to-leaf paths are:

1	["1->2->5", "1->3"]

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new LinkedList<String>();
        
        if(root == null){
            return res;
        }
        
        if(root.left == null && root.right == null){
            res.add(String.valueOf(root.val));
            return res;
        }
        
        List<String> leftS = binaryTreePaths(root.left);
        for(int i = 0; i < leftS.size(); ++i){
            res.add(String.valueOf(root.val) + "->" + leftS.get(i));
        }
        
        List<String> rightS = binaryTreePaths(root.right);
        for(int i = 0; i < rightS.size(); ++i){
            res.add(String.valueOf(root.val) + "->" + rightS.get(i));
        }
        
        return res;
    }
}

113. Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

Example:

Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

解题思路:

深度优先搜索策略

class Solution {
    private List<List<Integer>> list2 = new ArrayList<List<Integer>>();
    
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if(root == null){
            return list2;
        }
        helper(root, sum, new Stack<Integer>());
        return list2;
    }
    
    private void helper(TreeNode node, int sum, Stack<Integer> stack){
        stack.push(node.val);
        
        if(node.left == null && node.right == null){
            if(node.val == sum){
                list2.add(new ArrayList<Integer>(stack));
            }
        }
        if(node.left != null){
            helper(node.left, sum - node.val, stack);
        }
        if(node.right != null){
            helper(node.right, sum - node.val, stack);
        }
        
        stack.pop();
    }
}

129. Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

Example:

1
2
3

  1
 / \
2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

class Solution {
    List<List<Integer>> list2 = new ArrayList<List<Integer>>();
    
    public int sumNumbers(TreeNode root) {
        if(root == null){
            return 0;
        }
        
        helper(root, new Stack<Integer>());
        
        int res = 0;
        for(List<Integer> l : list2){
            int sum = 0;
            int factor = 1;
            for(int i = l.size() - 1; i >= 0; --i){
                sum += factor * l.get(i);
                factor *= 10;
            }
            res += sum;
        }
        
        return res;
    }
    
    public void helper(TreeNode root, Stack<Integer> stack){
        stack.push(root.val);
        
        if(root.left == null && root.right == null){
            list2.add(new ArrayList<Integer>(stack));
        }
        if(root.left != null){
            helper(root.left, stack);
        }
        if(root.right != null){
            helper(root.right, stack);
        }
        
        stack.pop();
    }
}

437. Path Sum III

ou are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1
Return 3. The paths that sum to 8 are:
1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

class Solution {
    public int pathSum(TreeNode root, int sum) {
        if(root == null){
            return 0;
        }
        
        int res = helper(root, sum);
        res += pathSum(root.left, sum);
        res += pathSum(root.right, sum);
        
        return res;
    }
    
    private int helper(TreeNode node, int remain){
        if(node == null){
            return 0;
        }
        
        int res = 0;
        if(node.val == remain){
            res = 1;
        }
        
        res += (helper(node.left, remain - node.val) + helper(node.right, remain - node.val) );
         
        
        return res;
    }
}

235. Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

Example:

     _______6______
    /              \
 ___2__          ___8__
/      \        /      \
0      _4       7       9
      /  \
      3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return null;
        }
        
        if(root.val < p.val && root.val < q.val){
            return lowestCommonAncestor(root.right, p, q);
        }
        
        else if(root.val > p.val && root.val > q.val){
            return lowestCommonAncestor(root.left, p, q);
        }
        
        return root;
        
    }
}

98. Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Example:

  2
 / \
1   3
return true

  1
 / \
2   3
return false

public boolean isValidBST(TreeNode root) {
        return helper(root, null, null);
    }
    
    boolean helper(TreeNode root, Integer min, Integer max) {
        if (root == null)
            return true;
        
        if ((min != null && root.val <= min) || (max != null && root.val >= max))
            return false;
        
        return helper(root.left, min, root.val) && helper(root.right, root.val, max);
    }

450. Delete Node in a BST

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Note: Time complexity should be O(height of tree).

Example:

root = [5,3,6,2,4,null,7]
key = 3
    5
   / \
  3   6
 / \   \
2   4   7
Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the following BST.
    5
   / \
  4   6
 /     \
2       7
Another valid answer is [5,2,6,null,4,null,7].
    5
   / \
  2   6
   \   \
    4   7

108. Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

Example:

Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
      0
     / \
   -3   9
   /   /
 -10  5

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums == null){
            return null;
        }
        
        return helper(nums, 0, nums.length-1);
    }
    
    private TreeNode helper(int []A, int lo, int hi){
        if(lo > hi){
            return null;
        }
        
        int mid = (lo + hi) / 2;
        TreeNode node = new TreeNode(A[mid]);
        node.left = helper(A, lo, mid-1);
        node.right = helper(A, mid+1, hi);
        
        return node;
    }
}

230. Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:

You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

class Solution 
{   private static int count = 0;
    private static int res = 0;
    public int kthSmallest(TreeNode root, int k) {
        if(root == null){
            return 0;
        }
        
        count = k;
        
        helper(root, k);
        
        return res;
    }
 
    public void helper(TreeNode node, int k){
        if(node.left != null){
            helper(node.left, k);
        }
        
        if(--count == 0){
            res = node.val;
            return;
        }
        
        if(node.right != null){
            helper(node.right, count);
        }
    }
}

236. Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

     _______3______
    /              \
 ___5__          ___1__
/      \        /      \
6      _2       0       8
      /  \
      7   4

Example:

the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

1
2

栈和队列

发表于 2018-02-17 | 分类于 Catalina

20. Valid Parentheses

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.

解题思路：

括号匹配

class Solution {
    public boolean isValid(String s) {
        
        Stack<Character> stack = new Stack<Character>();
        
        for(int i = 0; i < s.length(); ++i){
            
            char c = s.charAt(i);
            // 前括号入栈
            if(c == '(' || c == '[' || c == '{'){
                stack.push(c);        
            }
            else{
                //需要栈中有元素，否则没有前括号匹配了，错误
                if(stack.isEmpty()){
                    return false;
                }
                //当c为后括号，需要从stack中取出特定的后括号进行匹配
                char match;
                switch(c){
                    case ')' : match = '('; break;
                    case ']' : match = '['; break;
                    case '}' : match = '{'; break;
                    default  : return false;
                }
                
                if(match != stack.pop()){
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

150. Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Examples：

1 2	["2", "1", "+", "3", ""] -> ((2 + 1) 3) -> 9 ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

解题思路：

后缀表达式，遇到数字入栈，遇到标点符号出栈两个数并计算。
注意，计算结果之后，需要重新入栈

class Solution {
    public int evalRPN(String[] tokens) {
        
        Stack<Integer> stack = new Stack<Integer>();
        
        for(String s : tokens){
            if(s.equals("+")){
                stack.push(stack.pop() + stack.pop());
            }
            else if(s.equals("*")){
                stack.push(stack.pop() * stack.pop());
            }
            else if(s.equals("-")){
                int v1 = stack.pop();
                int v2 = stack.pop();
                stack.push(v2 - v1);
            }
            else if(s.equals("/")){
                int v1 = stack.pop();
                int v2 = stack.pop();
                stack.push(v2 / v1);
            }
            else{
                stack.push(Integer.parseInt(s));
            }
        }
        
        return stack.pop();
    }
}

71. Simplify Path

Given an absolute path for a file (Unix-style), simplify it.

Example：

1 2	path = "/home/", => "/home" path = "/a/./b/../../c/", => "/c"

解题思路：

当遇到 “..”，需要栈的特性，弹出最后加入的元素
返回的字符串需要FIFO，需要队列的特性
使用LinkedList为最佳

class Solution {
    public String simplifyPath(String path) {
        LinkedList<String> list = new LinkedList<String>();
        String []strings = path.split("/");
        
        for(String s : strings){
            //需要判断list为非空
            if(s.equals("..") && list.size() != 0){
                list.removeLast();
            }
            else if(s.equals("..") || s.equals(".") || s.equals("")){
                continue;
            }
            else{
                list.add(s);
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for(String s : list){
            sb.append("/" + s);
        }
        
        return sb.length() == 0 ? "/" : sb.toString();
    }
}

144. Binary Tree Preorder Traversal

二叉树先序遍历

递归版

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List<Integer> list = new LinkedList<Integer>();
    
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root != null){
            list.add(root.val);
            preorderTraversal(root.left);
            preorderTraversal(root.right);
        }
        return list;
    }
    
}

迭代版：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<Integer>();
        if(root == null){
            return list;
        }
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            list.add(node.val);
            
            //右子树节点，等左子树节点全部被弹出，才会被访问
            if(node.right != null){
                stack.push(node.right);
            }
            
            //左子树节点一放入，马上被弹出
            if(node.left != null){
                stack.push(node.left);
            }
        }
        
        return list;
    }
}

94. Binary Tree Inorder Traversal

二叉树中序遍历

递归版

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List<Integer> list = new LinkedList<Integer>();
    
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root != null){
            inorderTraversal(root.left);
            list.add(root.val);
            inorderTraversal(root.right);
        }
        
        return list;
    }
}

迭代版

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<Integer>();
        if(root == null){
            return list;
        }
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while(root != null || !stack.isEmpty()){
            //对于每个子树，都要先遍历其最左子节点
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            //访问子树的最左节点
            //现在该节点可是看成是子树的根节点，所以访问其右节点
            TreeNode node = stack.pop();
            list.add(node.val);
            root = node.right;
        }
        
        return list;
    }
}

145. Binary Tree Postorder Traversal

二叉树后续遍历

递归版

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List<Integer> list = new LinkedList<Integer>();
    
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root != null){
            postorderTraversal(root.left);
            postorderTraversal(root.right);
            list.add(root.val);
        }    
        
        return list;
    }
}

迭代版：

二叉树先序遍历，中左右
二叉树后续遍历，左右中 == Reverse(中右左)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> list = new LinkedList<Integer>();
        if(root == null){
            return list;
        }
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            list.addFirst(node.val);
            
            if(node.left != null){
                stack.push(node.left);
            }
            if(node.right != null){
                stack.push(node.right);
            }
        }
        
        return list;
    }
}

341. Flatten Nested List Iterator

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list – whose elements may also be integers or other lists.

Example 1:

1
2
3

Given the list [[1,1],2,[1,1]],
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2:

1
2
3

Given the list [1,[4,[6]]],
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

```
#### 102. Binary Tree Level Order Traversal
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
```java
    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

解题思路：

二叉树层序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list2 = new LinkedList<List<Integer>>();
        if(root == null){
            return list2;
        }
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        
        while(!queue.isEmpty()){
            int cnt = queue.size();
            List<Integer> list = new LinkedList<Integer>();
            while(cnt-- != 0){
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left != null){ queue.offer(node.left); }
                if(node.right != null) { queue.offer(node.right); }
            }
            list2.add(list);
        }
        
        return list2;
    }
}

107. Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree [3,9,20,null,null,15,7],

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

解题思路：

与上一道题目是一样的，只是List加入list2的时候要前插

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> list2 = new LinkedList<List<Integer>>();
        if(root == null){
            return list2;
        }
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while(!queue.isEmpty()){
            int cnt = queue.size();
            LinkedList<Integer> list = new LinkedList<Integer>();
            while(cnt-- != 0){
                TreeNode node = queue.remove();
                list.add(node.val);
                if(node.left != null) { queue.add(node.left); }
                if(node.right != null) { queue.add(node.right); }
            }
            list2.add(0, list);
        }
        
        return list2;
    }
}

103. Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:

Given binary tree [3,9,20,null,null,15,7],

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

解题思路：

之字形打印二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> list2 = new LinkedList<List<Integer>>();
        if(root == null){
            return list2;
        }
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        boolean order = false;
        while(!queue.isEmpty()){
            order = !order;
            int cnt = queue.size();
            List<Integer> list = new LinkedList<Integer>();
            //第一次在list添加val, order为true
            while(cnt-- != 0){
                TreeNode node = queue.remove();
                if(order) { list.add(node.val); }
                else { list.add(0, node.val); }
                
                if(node.left != null) { queue.add(node.left); }
                if(node.right != null) { queue.add(node.right); }
            }
            list2.add(list);
        }
        
        return list2;
    }
}

199. Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

解题思路：

层序遍历
找二叉树每层的最后一个节点

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        if(root == null){
            return list;
        }   
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while(!queue.isEmpty()){
            int cnt = queue.size();
            TreeNode node = null;
            while(cnt-- != 0){
                node = queue.remove();
                if(cnt == 0){
                    //每层的最后一个节点
                    list.add(node.val);
                }
                if(node.left != null) { queue.add(node.left); }
                if(node.right != null) { queue.add(node.right); }
            }
        }
        
        return list;
    }
}

279. Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

解题思路：

图论问题，广度优先搜索问题
寻找满足Ｘ = v1 + v2 + v3 + ….最少的v的个数

示例12

12	中心点
11 | 8 | 3	第一层没有出现０的情况
10 | 7 | 2 || 7 | 4 || 2	第二层没有
9 | 6 | 1 || 6 | 3 || 1 ||| 6 | 3 | || 3 | 0 ||| 1		第三层搜索到0
12 -> 8 -> 4 -> 0

class Solution {
    public int numSquares(int n) {
        Queue<int []> queue = new LinkedList<int []>();   
        queue.add(new int[]{ n, 0});
        boolean []visited = new boolean[n+1];
        visited[n] = true;  //带记忆的搜索，再一层被记录，step值肯定大于前一层的，所以没必要入队
        
        while(!queue.isEmpty()){
            int []A = queue.remove();
            int num = A[0];
            int step = A[1];
            
            int factor = 1;
            while(true){
                int remain = num - factor * factor;
                if(remain < 0){
                    break;
                }
                if(remain == 0){
                    return step + 1;
                }
                if(!visited[remain]){
                    queue.add(new int[]{remain, step+1});
                    visited[remain] = true;                    
                }
                ++factor;
            }
        }
        
        return -1;
    }
}

127. Word Ladder

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time.
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Example:

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.

解题思路:

广度优先搜索

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        //因为word在transform会产生大量的字符串
        //使用dictionary过滤掉无意义的字符串
        HashSet<String> dictionary = new HashSet<String>();
        for(String s: wordList){
            dictionary.add(s);
        }
        Queue<String> queue = new LinkedList<String>(); //保存广度优先搜索的每一层字符串
        Set<String> visited = new HashSet<String>();    //避免搜索重复字符串，可以减少搜索次数
        queue.add(beginWord);
        visited.add(beginWord);
        int length = 1;
        while(!queue.isEmpty()){
            ++length;
            int cnt = queue.size();
            //每一层有cnt个字符串，一一验证
            while(cnt-- != 0){
                char [] chars = queue.remove().toCharArray();
                for(int i = 0; i < chars.length; ++i){
                    char c = chars[i];
                    for(int j = 0; j < 26; ++j){
                        chars[i] = (char)('a' + j);
                        String word = String.valueOf(chars);
                        //只有在dictionary的字符串，才需要验证
                        if(dictionary.contains(word)){
                            if(word.equals(endWord)){
                                return length;
                            }
                            if(!visited.contains(word)){
                                queue.add(word);
                                visited.add(word);
                            }
                        }
                    }
                    chars[i] = c;   //复位
                }
            }
        }
        return 0;
    }
}

126. Word Ladder II

All conditions are as same as the last question，
unless the return

[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]

解题思路:

深度优先搜索

1
2

347. Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

Example:

Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note:

You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

解题思路:

HashMap统计数字的频率
最小堆，堆顶最小元素被过滤

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> list = new ArrayList<>();
        HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>();
        
        //自定义最小堆
        PriorityQueue<int []> pq = new PriorityQueue<int []>(
            new Comparator<int[]>() {
                    @Override
                    public int compare(int[] A1, int[] A2) {
                        return A1[1] == A2[1] ? 0 : (A1[1] < A2[1] ? -1 : 1);
                    }
                }
        );
        //统计每个数的频率
        for(int i : nums){
            freq.put(i, freq.getOrDefault(i, 0) + 1);
        }
        //A[0] ---- 数字 ---- key
        //A[1] ---- 频率 ---- value
        for(Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            if (pq.size() == k) {
                int[] A = pq.peek();
                if (A[1] < entry.getValue()) {
                    pq.poll();
                    pq.add(new int[]{entry.getKey(), entry.getValue()});
                }
            } else {
                pq.add(new int[]{entry.getKey(), entry.getValue()});
            }
        }
        while(!pq.isEmpty()){
            int []A = pq.poll();
            list.add(A[0]);
        }
        return list;
    }
}

23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

解题思路：

本来是想着把所有的节点，依次装入优先队列，然后重新组装成链表
结果是会超时的

下面解法的思路是，最小堆每次只有lists.size()个，每次比较的是每个链表的头节点；

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        Queue<ListNode> pq = new PriorityQueue(new Comparator<ListNode>(){
            @Override public int compare(ListNode l1, ListNode l2) { 
                return l1.val - l2.val; 
            }
        });
        
        ListNode dummyHead = new ListNode(-1);
        ListNode pre = dummyHead;
        
        for(ListNode cur : lists){
            if(cur != null){
                pq.add(cur);
            }
        }
        
        while(!pq.isEmpty()){
            pre.next = pq.poll();
            pre = pre.next;
            if(pre.next != null){
                pq.add(pre.next);
            }
        }
        
        return dummyHead.next;
    }
}

链表

发表于 2018-02-16 | 分类于 Catalina

Leetcode

206. Reverse Linked List

Reverse a singly linked list.

解题思路：

翻转链表，三个指针pre, cur和next指针

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        
        //当cur == null 时候，跳出循环，返回pre
        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            
            pre = cur;
            cur = next;
        }
        
        return pre;
    }
}

92. Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

解题思路：

画图！画图！画图！
搞清链表的拼接处的节点。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode preReverse = dummyHead;
        int cnt = n-m+1;    //统计翻转的次数
        
        //从虚拟头节点开始，找到翻转链表的前一个节点，需要m-1次
        while(--m != 0){
            preReverse = preReverse.next;
        }
        ListNode pre = null;
        ListNode cur = preReverse.next;
        //翻转链表，m节点开始
        while(cnt -- != 0){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        //pre指向翻转链表的最后一个节点, cur指向最后节点的下一个节点
        // tailOfReverse 本来是翻转链表之前的第一个节点，存储在preReverse.next
        ListNode tailOfReverse = preReverse.next;
        tailOfReverse.next = cur;   //拼接翻转链表的尾部
        preReverse.next = pre;      //拼接翻转链表的头部
        return dummyHead.next;
    }
}

83. Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

解题思路：

去除排序链表中重复的节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        
        ListNode pre = null;
        while(head != null){
            pre = head;
            head = head.next;
            //一直寻找，直到pre.val != head.val
            while(head != null && head.val == pre.val){
                head = head.next;
            }
            
            pre.next = head;
        }
        
        return dummyHead.next;
    }
}

86. Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

解题思路：

拼接两条链表的操作，cur节点从虚拟头节点开始！

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummyHead1 = new ListNode(-1);
        ListNode dummyHead2 = new ListNode(-1);
        ListNode cur1 = dummyHead1;
        ListNode cur2 = dummyHead2;
        
        while(head != null){
            if(head.val < x){
                cur1.next = head;
                cur1 = cur1.next;
            }
            else{
                cur2.next = head;
                cur2 = cur2.next;
            }
            head = head.next;
        }
        cur1.next = dummyHead2.next;	//拼接链表
        cur2.next = null;	//链表的尾部置为null，以防循环
        
        return dummyHead1.next;
    }
}

328. Odd Even Linked List

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example:

1 2	Given 1->2->3->4->5->NULL, return 1->3->5->2->4->NULL.

Note:

1 2	The relative order inside both the even and odd groups should remain as it was in the input. The first node is considered odd, the second node even and so on ...

解题思路：

和上一道题目一模一样

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        ListNode dummyHeadOdd = new ListNode(-1);
        ListNode dummyHeadEven = new ListNode(-1);
        ListNode curOdd = dummyHeadOdd;
        ListNode curEven = dummyHeadEven;
        
        boolean odd = true;
        while(head != null){
            if(odd){
                curOdd.next = head;
                curOdd = curOdd.next;
            }
            else{
                curEven.next = head;
                curEven = curEven.next;
            }
            odd = !odd;
            head = head.next;
        }
        
        curEven.next = null;
        curOdd.next = dummyHeadEven.next;
        
        return dummyHeadOdd.next;
    }
}

2. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example

1
2
3

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

解题思路：

把两条链表对应的值相加，得到的值的个位数创建新的节点，保留进位；
注意循环退出的条件

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(-1);
        ListNode cur = dummyHead;
        int carry = 0;
        while(l1 != null || l2 != null || carry != 0){
            int sum = 0;
            
            if(l1 != null){
                sum += l1.val;
                l1 = l1.next;
            }
            if(l2 != null){
                sum += l2.val;
                l2 = l2.next;
            }
            
            sum += carry;
            ListNode node = new ListNode(sum % 10);
            cur.next = node;
            cur = cur.next;
            
            carry = sum / 10;
        }
        
        return dummyHead.next;
    }
}

445. Add Two Numbers II

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Follow up:

What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

1 2	Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 8 -> 0 -> 7

解题思路：

本道题目与上一题是类似的，只不过对于输入和输出都需要先翻转链表
然而题目步允许翻转链表，借助两个栈进行输入的翻转，
输出的链表使用往前插入，达到链表翻转的目的。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(-1);
        Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();
        
        while(l1 != null){
            stack1.push(l1.val);
            l1 = l1.next;
        }
        
        while(l2 != null){
            stack2.push(l2.val);
            l2 = l2.next;
        }
        
        int carry = 0;
        while(!stack1.isEmpty() || !stack2.isEmpty() || carry != 0){
            int sum = carry;
            if(!stack1.isEmpty()){
                sum += stack1.pop();
            }
            if(!stack2.isEmpty()){
                sum += stack2.pop();
            }
            carry = sum / 10;
            ListNode node = new ListNode(sum % 10);
            node.next = dummyHead.next;
            dummyHead.next = node;
        }
        
        return dummyHead.next;
    }
}

203. Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.

Example：

1 2	Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6 Return: 1 --> 2 --> 3 --> 4 --> 5

解题思路：

删除链表中特定的值，一个一个遍历，很简单；
注意更新pre节点的时机

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode pre = dummyHead;
        
        while(head != null){
            if(head.val == val){
                pre.next = head.next;
            }
            else{
                pre = pre.next;
            }
            head = head.next;
        }
        
        return dummyHead.next;
    }
}

82. Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Example：

1 2	Given 1->2->3->3->4->4->5, return 1->2->5. Given 1->1->1->2->3, return 2->3.

解题思路：

输入的链表是排序链表；
重复的节点全部删除，注意pre的处理

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode pre = dummyHead;
        ListNode cur = head;
        
       while(cur != null){
           //若出现重复的数值，cur指向重复节点的最后一个
           while(cur.next != null && cur.val == cur.next.val){
               cur = cur.next;
           }
           //条件成立：cur是没有重复的节点, pre前进
           if(pre.next == cur){
               pre = cur;
           }
           //否则，cur目前是重复的节点, 跳过cur，并且pre不前进
           else{
               pre.next = cur.next;
           }
           //cur照常前进
           cur = cur.next;
       }
        
        return dummyHead.next;
    }
}

21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example：

1 2	Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4

解题思路：

合并链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(-1);
        ListNode cur = dummyHead;
        
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                cur.next = l1;
                l1 = l1.next;
            }
            else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        
        cur.next = l1 == null ? l2 : l1;
        
        return dummyHead.next;
    }
}

解法二：

递归实现：用心去感受，难以说明

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null){
            return l2;
        }    
        if(l2 == null){
            return l1;
        }
        
        ListNode mergeNode = null;
        if(l1.val < l2.val){
            mergeNode = l1;
            mergeNode.next = mergeTwoLists(l1.next, l2);
        }
        else{
            mergeNode = l2;
            mergeNode.next = mergeTwoLists(l1, l2.next);
        }
        
        return mergeNode;
    }
}

24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

解题思路：

四个指针，pre, node1, node2 和 next

/**
 * 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 dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode pre = dummyHead;
        
        while(pre.next != null && pre.next.next != null){
            ListNode node1 = pre.next;
            ListNode node2 = pre.next.next;
            ListNode next = node2.next;
            
            pre.next = node2;
            node2.next = node1;
            node1.next = next;
            
            pre = node1;    //注意更新的节点pre
        }
        
        return dummyHead.next;
    }
}

25. Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

example：

Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5

解题思路：

更新两个关键的节点，
一个是待翻转链表的前一个节点(PreOfReverse)
一个是链表翻转之后的尾节点，即未翻转链表的头节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode cur = head;
        
        int total = 0;
        while(cur != null){
            ++total;
            cur = cur.next;
        }
        
        int times = total / k;
        cur = head;
        ListNode preOfReverse = dummyHead;  //翻转链表的前一个节点
        ListNode tailOfReverse = cur;       //尾节点，本来是第一个链表的头节点，翻转之后变尾节点
        while(times-- > 0){
            ListNode pre = preOfReverse;    //待翻转链表的前一个节点
            int cnt = k;
            //翻转链表操作
            while(cnt-- != 0){
                ListNode next = cur.next;
                cur.next = pre;
                
                pre = cur;
                cur = next;
            }
            
            //更新节点操作
            preOfReverse.next = pre;    
            tailOfReverse.next = cur;
            preOfReverse = tailOfReverse;
            tailOfReverse = cur;
        }
        
        return dummyHead.next;
    }
}

147. Insertion Sort List

Sort a linked list using insertion sort.

解题思路：

使用插入排序，每次取旧队列头节点，插入到新队列的合适位置，pre.val <= cur.val

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummyHead = new ListNode(-1);  //新链表的虚拟头节点
        ListNode cur = head;    
        
        //依次遍历cur节点，将其插入到新链表中合适的位置
        while(cur != null){
            ListNode pre = dummyHead;
            ListNode next = cur.next;
            while(pre.next != null && pre.next.val < cur.val){
                pre = pre.next;
            }
            //将cur移到新链表，插入位置为pre和pre.next之间
            cur.next = pre.next;
            pre.next = cur;
            
            cur = next;
        }
        
        return dummyHead.next;
    }
}

148. Sort List

Sort a linked list in O(n log n) time using constant space complexity.

解题思路：

归并排序链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        //不足一个节点，不需要再分割
        if(head == null || head.next == null){
            return head;
        }
        
        ListNode fast = head;
        ListNode slow = head;
        ListNode middleTail = null;
        
        //切分两条链表
        while(fast != null && fast.next != null){
            middleTail = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        middleTail.next = null;
        ListNode l1 = sortList(head);
        ListNode l2 = sortList(slow);
        
        return merge(l1, l2);
    }
    
    //合并链表操作
    private ListNode merge(ListNode l1, ListNode l2){
        ListNode dummyHead = new ListNode(-1);
        ListNode cur = dummyHead;
        
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                cur.next = l1;
                l1 = l1.next;
            }
            else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        
        cur.next = (l1 == null) ? l2 : l1;
        
        return dummyHead.next;
    }
}

237. Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

解题思路：

删除指定的节点，修改节点值

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        if(node == null){
            return;
        }
        
        if(node.next == null){
            node = null;
        }
        
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

19. Remove Nth Node From End of List

Given a linked list, remove the n(th) node from the end of list and return its head.

Example：

1
2
3

Given linked list: 1->2->3->4->5, and n = 2.
  After removing the second node from the end, the linked list becomes 1->2->3->5.

Note：
Given n will always be valid.
Try to do this in one pass.

解题思路：

双指针问题，注意preOfRemoveNode的位置，画图，枚举

/**
 * 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 dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode p = dummyHead;
        ListNode preOfRemoveNode = dummyHead;
        
        // dummyHead -> 1 -> 2 -> 3 -> 4 -> 5 -> null
        while(n-- != -1){
            p = p.next;    
        }
        
        while(p != null){
            p = p.next;
            preOfRemoveNode = preOfRemoveNode.next;
        }
        
        //验证preOfRemoveNode是否为尾节点
        if(preOfRemoveNode.next == null){
            preOfRemoveNode = null;
        }
        else{
            preOfRemoveNode.next = preOfRemoveNode.next.next;
        }
        
        return dummyHead.next;
    }
}

61. Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

Example：

1
2
3

Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

解题思路：

其实问题挺简单的，就是preOfRotateNode要找对了，还有节点tail

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null || k == 0){
            return head;
        }
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode tail = dummyHead;
        
        //统计节点个数, 并保存尾节点
        int n = 0;
        while(tail.next != null){
            tail = tail.next;
            ++n;
        }
        
        //处理 k > n || k == 0 的情况
        k %= n;
        if(k == 0){
            return head;
        }
        
        ListNode preOfRotateNode = dummyHead;
        k = n - k;      //dummyHead -> 1 -> 2 -> 3 -> 4 -> null
        while(k-- != 0){
            preOfRotateNode = preOfRotateNode.next;
        }
        
        //旋转
        tail.next = dummyHead.next;
        dummyHead.next = preOfRotateNode.next;
        preOfRotateNode.next = null;
        
        return dummyHead.next;
    }
}

143. Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes’ values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

解题思路：

分割链表，并重装

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if(head == null || head.next == null){
            return;
        }
        
        //链表一分为二
        ListNode fast = head;
        ListNode slow = head;
        ListNode middleTail = null;
        while(fast != null && fast.next != null){
            middleTail = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        middleTail.next = null;         //第一条链表的尾后节点置位空
        ListNode l1 = head;             //假设l1 有 n 个节点
        ListNode l2 = reverse(slow);    //那么l2 有 n 个或者 n+1 个
        
        ListNode dummyHead = new ListNode(-1);
        ListNode cur = dummyHead;
        while(l1 != null){
            cur.next = l1;
            l1 = l1.next;
            
            cur.next.next = l2;
            l2 = l2.next;
            
            cur = cur.next.next;
        }
        cur.next = l2;      //l2可能还有1个节点
        
        head = dummyHead.next;
    }
    
    //翻转链表，并返回新链表的头节点
    private ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        
        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            
            pre = cur;
            cur = next;
        }
        
        return pre;
    }
}

234. Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Follow up：
Could you do it in O(n) time and O(1) space?

解题思路：

解法与上一题一样

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null){
            return true;
        }
        
        ListNode fast = head;
        ListNode slow = head;
        ListNode middleTail = null;
        while(fast != null && fast. next != null){
            middleTail = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        middleTail.next = null;
        ListNode l1 = head;
        ListNode l2 = reverse(slow);
        
        while(l1 != null && l2 != null){
            if(l1.val != l2.val){
                return false;
            }
            l1 = l1.next;
            l2 = l2.next;
        }
        
        return true;
    }
    
    private ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        
        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            
            pre = cur;
            cur = next;
        }
        
        return pre;
    }
}

查找

发表于 2018-02-14 | 分类于 Catalina

Leetcode

349. Intersection of Two Arrays

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:
Each element in the result must be unique.
The result can be in any order.

解题思路

简单集合操作set

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
       
        Set<Integer> record = new HashSet<Integer>();
        Set<Integer> res = new HashSet<Integer>();
        
        for(int i = 0; i < nums1.length; ++i){
            record.add(nums1[i]);
        }
        
        for(int i = 0; i < nums2.length; ++i){
            if(record.contains(nums2[i])){
                res.add(nums2[i]);
            }
        }
        
        int []A = new int[res.size()];
        int i = 0;
        for(int a : res){
            A[i++] = a;
        }
        
        return A;
    }
}

350. Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

Note:
Each element in the result should appear as many times as it shows in both arrays.
The result can be in any order.

Follow up:

What if the given array is already sorted? How would you optimize your algorithm?

1	Two Points

What if nums1’s size is small compared to nums2’s size? Which algorithm is better?

1	HashTable, the memory of hashtable is smaller than hashmap

What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

1
2

If only nums2 cannot fit in memory, put all elements of nums1 into a HashMap, read chunks of array that fit into the memory, and record the intersections.
If both nums1 and nums2 are so huge that neither fit into the memory, sort them individually (external sort), then read 2 elements from each array at a time in memory, record intersections.

解题思路

简单map操作

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer, Integer> record = new HashMap<Integer, Integer>();
        List<Integer> res = new ArrayList<Integer>();
        
        for(int i = 0; i < nums1.length; ++i){
            if(record.containsKey(nums1[i])){
                record.put(nums1[i], record.get(nums1[i]) + 1);
            }
            else{
                record.put(nums1[i], 1);
            }
        }
        
        for(int i = 0; i < nums2.length; ++i){
            //注意判断record中值为0的键
            if(record.containsKey(nums2[i]) && record.get(nums2[i]) > 0){
                res.add(nums2[i]);
                record.put(nums2[i], record.get(nums2[i])-1);
            }
        }
        
        int []A = new int[res.size()];
        int i = 0;
        for(int a : res){
            A[i++] = a;
        }
        
        return A;
    }
}

242. Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = “anagram”, t = “nagaram”, return true.
s = “rat”, t = “car”, return false.

Note:
You may assume the string contains only lowercase alphabets.

解题思路

简单的map操作

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()){
            return false;
        }
        
        Map<Character, Integer> record = new HashMap<Character, Integer>();
        
        for(int i = 0; i < s.length(); ++i){
            char c = s.charAt(i);
            if(record.containsKey(c)){
                record.put(c, record.get(c) + 1);
            }
            else{
                record.put(c, 1);
            }
        }
        
        for(int i = 0;  i < t.length(); ++i){
            char c = t.charAt(i);
            if(record.containsKey(c) && record.get(c) > 0){
                record.put(c, record.get(c) - 1);
            }
            else{
                return false;
            }
        }
        
        return true;
    }
}

聪明人的简洁做法

class Solution {
    public boolean isAnagram(String s, String t) {
        int []alphabet = new int[256];
        
        for(int i = 0; i < s.length(); ++i){
            ++alphabet[s.charAt(i)];
        }
        
        for(char c : t.toCharArray()){
            --alphabet[c];
        }
        
        for(int i : alphabet){
            if(i != 0){
                return false;
            }
        }
        
        return true;
    }
}

202. Happy Number

Write an algorithm to determine if a number is “happy”.

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number

1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

解题思路

Set保存着82, 68, 100等等…一旦出现了重复值，那么这个数就不可能是happy number了

class Solution {
    public boolean isHappy(int n) {
        HashSet<Integer> set = new HashSet<Integer>();        
        int result = 0;
        
        while(n != 1){
            result = 0;
            while(n != 0){
                result += Math.pow(n % 10, 2);
                n /= 10;
            }
            if(set.contains(result)){
                return false;
            }
            set.add(result);
            n = result;
        }
        
        return true;
    }
}

290. Word Pattern

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Examples:

pattern = "abba", str = "dog cat cat dog" should return true.
pattern = "abba", str = "dog cat cat fish" should return false.
pattern = "aaaa", str = "dog cat cat dog" should return false.
pattern = "abba", str = "dog dog dog dog" should return false.

Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

解题思路

很简单的键值映射关系，这边有个坑是关于HashMap的get和put操作，最好看下源码

class Solution {
    public boolean wordPattern(String pattern, String str) {
        Map<Character, String> map = new HashMap<Character, String>();
        String []strings = str.split(" ");
        
        if(strings.length != pattern.length()){
            return false;
        }
            
        for(int i = 0; i < pattern.length(); ++i){
            char c = pattern.charAt(i);
            if(map.containsKey(c)){
                if(!map.get(c).equals(strings[i])){
                    return false;
                }
            }
            else if(map.containsValue(strings[i])){
                return false;
            }
            map.put(c, strings[i]);
        }
        
        return true;
    }
}

205. Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example,

Given "egg", "add", return true.
Given "foo", "bar", return false.
Given "paper", "title", return true.

Note:
You may assume both s and t have the same length.

解题思路

将字符映射其最近所存储的位置，一旦发现两者的存储位置不同，返回false

class Solution {
    public boolean isIsomorphic(String s, String t) {
        int []m1 = new int[256];
        int []m2 = new int[256];
        int n = s.length();
        
        for(int i = 0; i < n; ++i){
            char c1 = s.charAt(i);
            char c2 = t.charAt(i);
            
            if(m1[c1] != m2[c2]){
                return false;
            }
            
            m1[c1] = i + 1;
            m2[c2] = i + 1;
        }
        
        return true;
    }
}

451. Sort Characters By Frequency

Given a string, sort it in decreasing order based on the frequency of characters.

Example:

Input:
"tree"
Output:
"eert"
Explanation:
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.
-------------------------------------------------------------------------------------
Input:
"cccaaa"
Output:
"cccaaa"
Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.
-------------------------------------------------------------------------------------
Input:
"Aabb"
Output:
"bbAa"
Explanation:
"bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

解题思路

借助HashMap和TreeMap实现
HashMap用来统计每次字符出现的频率
TreeMap维护频率和字符列表，因为字符出现的频率可能重复，所以使用list来维护

class Solution {
    public String frequencySort(String s) {
        HashMap<Character, Integer> freq = new HashMap<Character, Integer>();
        TreeMap<Integer, List<Character>> sort = new TreeMap<Integer, List<Character>>(
                new Comparator<Integer>(){
                    @Override
                    public int compare(Integer o1, Integer o2){
                        return o1 == o2 ? 0 : (o1 < o2 ? 1 : -1);
                    }
                }
        );
        for(char c : s.toCharArray()){
            if(freq.containsKey(c)){
                freq.replace(c, freq.get(c) + 1);
            }
            else{
                freq.put(c, 1);
            }
        }
        for(Map.Entry<Character, Integer> entry : freq.entrySet()){
            char c = entry.getKey();
            int cnt = entry.getValue();
            if(sort.containsKey(cnt)){
                sort.get(cnt).add(c);
            }
            else{
                List<Character> list = new ArrayList<Character>();
                list.add(c);
                sort.put(cnt, list);
            }
        }
        StringBuilder sb = new StringBuilder();
        for(Map.Entry<Integer, List<Character>> entry : sort.entrySet()){
            int cnt = entry.getKey();
            for(char c : entry.getValue()){
                int i = 0;
                while(i++ < cnt){
                    sb.append(c);
                }
            }
        }
        
        return sb.toString();
    }
}

1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1]

解题思路

由于输入的数组并不是排序数组，所以直接使用对撞指针是不行的
使用Map找complement值

通常做法：首先将所有元素存入，接着遍历索引直到找到匹配的值；
有个小技巧：
只需要遍历一次，每次存入元素之前，就可以判断是否存在匹配的值，并且可以省去判断自否为重复索引的问题

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> index = new HashMap<Integer, Integer>();
        
        for(int i = 0; i < nums.length; ++i){
            int complement = target - nums[i];
            if(index.containsKey(complement)){
                int []A = new int[]{index.get(complement), i};
                return A;
            }
            index.put(nums[i], i);
        }
        
        return null;
    }
}

15. 3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

解题思路

先对数组进行排序，然后基于对撞指针的想法，将三个元素相加，寻找和为0的组合

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list2 = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        
        for(int i = 0; i < nums.length - 2; ++i){
            //去重操作
            if(i != 0 && nums[i] == nums[i-1]){
                continue;
            }
            
            int p = i + 1;
            int q = nums.length - 1;
            while(p < q){
                int sum = nums[i] + nums[p] + nums[q];
                if(sum == 0){
                    list2.add(Arrays.asList(nums[i], nums[p], nums[q]));
                    //while去重操作
                    //边界条件是指针先往前走一步，接着回头看是否重复
                    while(++p < q && nums[p-1] == nums[p]){}
                    while(p < --q && nums[q+1] == nums[q]){}
                }
                else if(sum < 0){
                    ++p;
                }
                else{
                    --q;
                }
            }
        }
        
        return list2;
    }
}

18. 4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

解题思路：

与上一题一样的思路，只不过多了一层循环

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> list2 = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        
        for(int i = 0; i < nums.length - 3; ++i){
            if(i != 0 && nums[i-1] == nums[i]){
                continue;
            }
            
            for(int j = i+1; j < nums.length - 2; ++j){
                if(j != i + 1 && nums[j-1] == nums[j]){
                    continue;
                }
                
                int p = j+1;
                int q = nums.length-1;
                while(p < q){
                    int sum = nums[i] + nums[j] + nums[p] + nums[q];
                    if(sum == target){
                        Integer []A = {nums[i], nums[j], nums[p], nums[q]};
                        list2.add(Arrays.asList(A));
                        
                        while(++p < q && nums[p-1] == nums[p]){}
                        while(p < --q && nums[q+1] == nums[q]){}
                    }
                    else if(sum < target){
                        ++p;
                    }
                    else{
                        --q;
                    }
                }
            }
        }
        
        return list2;
    }
}

16. 3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

1
2
3

For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

解题思路：

类似于题目 3Sum；判别条件变了而已

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int closestValue = nums[0] + nums[1] + nums[2];
        Arrays.sort(nums);
        
        for(int i = 0; i < nums.length - 2; ++i){
            if(i != 0 && nums[i-1] == nums[i]){
                continue;
            }
            
            int p = i + 1;
            int q = nums.length - 1;
            while(p < q){
                int sum = nums[i] + nums[p] + nums[q];
                int remain = sum - target;
                if(remain == 0){
                    return target;
                }
                else if(remain < 0){
                    ++p;        
                }
                else{
                    --q;
                }
                closestValue = (Math.abs(sum - target) < Math.abs(closestValue - target)) ?
                                    sum : closestValue;
            }
        }
        
        return closestValue;
    }
}

454. 4Sum II

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -2的28次方 to 2的28次方 - 1 and the result is guaranteed to be at most 2的31次方 - 1.

Example:

Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
Output:
2
Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

解题思路

空间换时间，题目也说了数组的长度为 0 <= N <= 500
暴力解法的复杂度为N的四次方，通过HashMap可以降为N的2次方
空间复杂度也是为N的2次方

class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        int result = 0;
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        
        for(int a : A){
            for(int b : B){
                map.put(a+b, map.getOrDefault(a+b, 0) + 1);
            }
        }
        
        for(int c : C){
            for(int d : D){
                int remain = 0 - c - d;
                result += map.getOrDefault(remain, 0);
            }
        }
        
        
        return result;
    }
}

49. Group Anagrams

Given an array of strings, group anagrams together.

For example, given: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
Return:

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note: All inputs will be in lower-case.

解题思路：

将包含的相同字符集和个数的字符串进行分类
相同的Anagram字符串作为HashMap的Key，处理之前先进行排序，使其具有唯一性

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> map = new HashMap<String, List<String>>();
        
        for(String str : strs){
            char []chars = str.toCharArray();
            Arrays.sort(chars);
            String s = Arrays.toString(chars);
            
            if(!map.containsKey(s)){
                map.put(s, new ArrayList<String>());
            }
            map.get(s).add(str);
        }
                    
        return new ArrayList<List<String>>(map.values());
    }
}

447. Number of Boomerangs

Given n points in the plane that are all pairwise distinct, a “boomerang” is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).

Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).

Example:

Input:
[[0,0],[1,0],[2,0]]
Output:
2
Explanation:
The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]

解题思路：

PointX与界面上的点距离，利用HashMap维护距离及其相同距离的个数
最后统计有多个对距离相同的边的个数result

假设distance 为 a，并且个数为1，那么result += 0；
假设distance 为 b，并且个数为2，那么result += 2；
假设distance 为 c，并且个数为3，那么result += 6。
以此类推（选择问题, 对于每个点m, 都有m-1种选择）

注意distance返回的值越界，不过该题不会越界, 10000 * 10000 小于 2的31次方-1

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        
        int result = 0;
        
        for(int i = 0; i < points.length; ++i){
            HashMap<Integer, Integer> record = new HashMap<Integer, Integer>();
            
            for(int j = 0; j < points.length; ++j){
                if(j != i){
                    int dis = distance(points[i][0], points[i][1], points[j][0], points[j][1]);
                    
                    record.put(dis, record.getOrDefault(dis, 0) + 1);
                }
            }
            
            for(int val : record.values()){
                result += val * (val-1);
            }
        }
        
        return result;
    }
    
    private int distance(int x1, int y1, int x2, int y2){
        return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
    }
}

149. Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

解题思路：

详见注释

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
class Solution {
    public int maxPoints(Point[] points) {
        int res = 0;
        
        if(points.length < 3){
            return points.length;
        }
        
        for(int i = 0; i < points.length - 1; ++i){
            //Point[i]的与其他points的斜率的计数统计
            HashMap<String, Integer> record = new HashMap<String, Integer>();
            int maxLine = 0;
            int overlap = 0;
            
            //其他点下标从i+1开始，避免重复工作
            for(int j = i + 1; j < points.length; ++j){
                int dx = points[i].x - points[j].x;
                int dy = points[i].y - points[j].y;
                if(dx == 0 && dy == 0){
                    overlap++;
                    continue;	//统计重叠的点
                }
                
                int gcd = getGcd(dx, dy);
                String slope = String.valueOf(dx/gcd) + String.valueOf(dy/gcd);
                
                int cnt = record.getOrDefault(slope, 0);
                record.put(slope, ++cnt);
                maxLine = Math.max(cnt, maxLine);
            }
            
            res = Math.max(res, overlap+maxLine+1);
        }
        
        return res;
    }
    
    //辗转相除法求最大公约数
    private int getGcd(int a, int b){
        if(b == 0){
            return a;
        }
        return getGcd(b, a % b);
    }
}

219. Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

解题思路：

滑动窗口+查找表
滑动窗口的最大为k，在窗口k内若找到重复的元素，返回true
每次将元素加入Set中，一旦set大小超过k，也就是窗口大小大于k，
那么就可以删除窗口最左端元素

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashSet<Integer> record = new HashSet<Integer>();
        
        for(int i = 0; i < nums.length; ++i){
            if(record.contains(nums[i])){
                return true;
            }
            
            record.add(nums[i]);
            
            if(record.size() == k + 1){
                record.remove(nums[i-k]);
            }
        }
        
        return false;
    }
}

217. Contains Duplicate

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

解题思路：

简单的Set操作

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> record = new HashSet<Integer>();
        for(int i = 0; i < nums.length; ++i){
            if(record.contains(nums[i])){
                return true;
            }
            record.add(nums[i]);
        }
        
        return false;
    }
}

220. Contains Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

解题思路：

可以把k看做滑动窗口，对于一个新的数，可以想象成放到这个窗口的最左边或者最右边，如果这个数+t或-t之后落在窗口里，直接返回true。

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        
        TreeSet<Long> record = new TreeSet<Long>();
        
        for(int i = 0; i < nums.length; ++i){
            Long floor = record.floor((long)nums[i] + (long)t);
            Long ceiling = record.ceiling((long)nums[i] - (long)t);
            
            if((floor != null && floor >= (long)nums[i]) ||
                (ceiling != null && ceiling <= (long)nums[i])){
                
                return true;
            }
            
            record.add((long)nums[i]);
            
            if(record.size() == k + 1){
                record.remove((long)nums[i-k]);
            }
        }
        
        return false;
    }
}

数组

发表于 2018-02-13 | 分类于 Catalina

Leetcode

283. Move Zeroes

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.

解题思路

将后面的非0元素往前挪，在nums中，使得[0, k)中的元素均为非0元素

class Solution {
    public void moveZeroes(int[] nums) {
        int k = 0;
        
        for(int i = 0; i < nums.length; ++i){
            if(nums[i] != 0){
                if(i != k){
                    swap(nums, i, k);
                }
                ++k;	//k在成为非0元素的索引后，向前挪
            }
        }
    }
    
    private void swap(int []nums, int i, int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

27. Remove Element

Given an array and a value, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example:

1
2
3

Given nums = [3,2,2,3], val = 3,
Your function should return length = 2, with the first two elements of nums being 2.

解题思路

类似于上题，将非val元素往前挪

class Solution {
    public int removeElement(int[] nums, int val) {
        int k = 0;  // (k, nums.length)为val数组
        
        for(int i = 0; i < nums.length; ++i){
            if(nums[i] != val){
                if(i != k){
                    swap(nums, i, k);
                }
                ++k;
            }
        }
        return k;
    }
    
    private void swap(int []nums, int i, int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

26. Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example:

Given nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
It doesn't matter what you leave beyond the new length.

解题思路

nums[k]为非重复数组的最后一个元素
遍历数组，每次两两比较，当前元素索引i若是与i-1不同，令nums[k]=nums[i]

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length < 2){
            return nums.length;
        }
        
        int k = 1;  //下一个非重复元素的索引
        for(int i = 1; i < nums.length; ++i){
            if(nums[i] != nums[k-1]){
                nums[k++] = nums[i];
            }
        }
        
        return k;
    }
}

80. Remove Duplicates from Sorted Array II

Follow up for “Remove Duplicates”:
What if duplicates are allowed at most twice?

For example,
Given sorted array nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn’t matter what you leave beyond the new length.

解题思路

与前一道题目相似

[0, k)数组中为最多2次重复的元素
在遍历整个数组的时候，只需要当前的i元素不得于i-2的元素
这时将其放入前面

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length < 3){
            return nums.length;
        }
        int k = 2;	//索引k指向为下一个不重复的元素
        for(int i = 2; i < nums.length; ++i){
            if(nums[i] != nums[k-2]){
                nums[k++] = nums[i];
            }
        }
        
        return k;
    }
}

75. Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library’s sort function for this problem.

解题思路

因为数组中的元素只有0,1和2，可以借助三路快排的思路

另一种简单的解题思路是：计数排序，适用于元素种类少的数组

1	0 ---> 1 <---2

class Solution {
    public void sortColors(int[] nums) {
        int i = 0;
        int p0 = -1;	//用p0和i维护0和1元素的位置
        int p2 = nums.length;
        
        
        while(i < p2){
            if(nums[i] == 2){
                swap(nums, --p2, i);	//在2放在末尾后, i指向的元素重新判断
            }
            else if(nums[i] == 1){	//对于1不处理，只增加数组的指针
                ++i;
            }
            else{
                swap(nums, ++p0, i++);	//i指向的是已排序后的1的末尾
            }
        }
    }
    
    private void swap(int []A, int i, int j){
        int t = A[i];
        A[i] = A[j];
        A[j] = t;
    }
}

88.Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

解题思路

由后往前插入元素

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int k = n + m - 1;
        m = m - 1;
        n = n - 1;
        
        while(m >= 0 && n >= 0){
            if(nums1[m] > nums2[n]){
                nums1[k--] = nums1[m--];
            }
            else{
                nums1[k--] = nums2[n--];
            }
        }
        
   
        while(n >= 0){
            nums1[k--] = nums2[n--];
        }
    }
}

215.Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

解题思路

快排partition思路

class Solution {
    public int findKthLargest(int[] nums, int k) {
        k = nums.length - k;
        int lo = 0;
        int hi = nums.length - 1;
        
        while(lo < hi){
            int pos = partition(nums, lo, hi);
            if(pos == k){
                break;
            }
            else if(pos < k){
                lo = pos + 1;
            }
            else{
                hi = pos - 1;
            }
        }
        
        return nums[k];
    }
    
    private int partition(int []A, int lo, int hi){
        int i = lo;
        int j = hi + 1;
        int pivot = A[i];
        while(true){
            while(i < hi && A[++i] < pivot){}
            while(j > lo && A[--j] > pivot){}
            if(i >= j){
                break;
            }
            swap(A, i, j);
        }
        swap(A, lo, j);
        
        return j;
    }
    
    private void swap(int []A, int i, int j){
        int t = A[i];
        A[i] = A[j];
        A[j] = t;
    }
}

167. Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution and you may not use the same element twice.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

解题思路

对撞指针

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int lo = 0;
        int hi = numbers.length - 1;
        
        while(lo < hi){
            int sum = numbers[lo] + numbers[hi];
            if(sum == target){
                break;
            }
            else if(sum < target){
                ++lo;
            }
            else{
                --hi;
            }
        }
        
        int []A = new int []{lo+1, hi+1};
        
        return A;
    }
}

125. Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
“A man, a plan, a canal: Panama” is a palindrome.
“race a car” is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome

解题思路

对撞指针，这类问题要注意索引的边界

class Solution {
    public boolean isPalindrome(String s) {
        int lo = 0;
        int hi = s.length() - 1;
        String ss = s.toLowerCase();
        
        while(lo < hi){
            while(lo < hi && !isAlpha(ss.charAt(lo))){ ++lo; }
            while(lo < hi && !isAlpha(ss.charAt(hi))){ --hi; }
            if(lo < hi){
                char c1 = ss.charAt(lo++);
                char c2 = ss.charAt(hi--);
                if(c1 != c2){
                    return false;
                }
            }
        }
        
        return true;
    }
    
    private boolean isAlpha(char c){
        return (c <= 'z' && c >= 'a') || (c <= 'Z' && c >= 'A') || (c <= '9' && c >= '0');
    } 
}

344. Reverse String

Write a function that takes a string as input and returns the string reversed.

Example:
Given s = “hello”, return “olleh”.

解题思路

对撞指针

class Solution {
    public String reverseString(String s) {
        char []chars = s.toCharArray();
        int lo = 0;
        int hi = chars.length - 1;
        
        while(lo < hi){
            char t = chars[lo];
            chars[lo++] = chars[hi];
            chars[hi--] = t;
        }
        
        return new String(chars);
    }
}

345. Reverse Vowels of a String

Write a function that takes a string as input and reverse only the vowels of a string.

Example 1:
Given s = “hello”, return “holle”.

Example 2:
Given s = “leetcode”, return “leotcede”.

Note:
The vowels does not include the letter “y”.

解题思路

对撞指针，

class Solution {
    public String reverseVowels(String s) {
        char []chars = s.toCharArray();
        int lo = 0;
        int hi = chars.length-1;
        
        while(true){
            while(lo < hi && !isVowel(chars[lo])){ ++lo; }
            while(lo < hi && !isVowel(chars[hi])){ --hi; }
            if(lo >= hi){
                break;    
            }
            swap(chars, lo++, hi--);
        }
        
        return new String(chars);
    }
    
    private void swap(char []C, int i, int j){
        char t = C[i];
        C[i] = C[j];
        C[j] = t;
    }
    
    private boolean isVowel(char c){
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'
            || c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
    }
}

11. Container With Most Water

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

解题思路

对撞指针，求sum = Min(nums[i], nums[j]) * (j - i) 的最大值

class Solution {
    public int maxArea(int[] height) {
        int lo = 0;
        int hi = height.length - 1;
        int max = -1;
        
        while(lo < hi){
            int h = height[lo] < height[hi] ? height[lo++] : height[hi--];  //木桶效应, 
            int sum = h * (hi - lo + 1);    //由于上面缩短了distance(i, j), 补上+1
            max = max < sum ? sum : max;
            
        }
        
        return max;
    }
}

209. Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

解题思路

双索引技术
滑动窗口，求连续最短的连续子数组，要求数组和大于等于s

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int l = 0;     //滑动窗口 [l, r]
        int r = -1;
        int k = nums.length + 1;    //滑动窗口大小
        int sum = 0;
        
        while(l < nums.length){	
            if(r + 1 < nums.length && sum < s){
                sum += nums[++r];
            }
            else{
                sum -= nums[l++];
            }
            
            if(sum >= s){
                k = (k < (r-l+1)) ? k : (r-l+1);
            }
        }
        
        return (k == nums.length + 1 ) ? 0 : k;
    }
}

3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given “abcabcbb”, the answer is “abc”, which the length is 3.

Given “bbbbb”, the answer is “b”, with the length of 1.

Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

解题思路

滑动窗口，注意左右边界的判定条件

class Solution {
    public int lengthOfLongestSubstring(String s) {
        char []chars = s.toCharArray();
        int []visited = new int[256];
        
        int l = 0;
        int r = -1;
        int k = 0;
        
        while(l < chars.length){
            
            if(r + 1 < chars.length && visited[chars[r+1]] == 0){
                ++visited[chars[++r]];
            }
            else{
                --visited[chars[l++]];
            }
            k = k < (r-l+1) ? (r-l+1) : k;
        }
        
        return k;
    }
}

438. Find All Anagrams in a String

Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"
Output:
[0, 6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input:
s: "abab" p: "ab"
Output:
[0, 1, 2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<Integer>();
        
        int []visited = new int[256];
        for(int i = 0; i < p.length(); ++i){
            ++visited[p.charAt(i)];
        }
        
        int start = 0;  //滑动窗口的起点，并且有start <= i
        for(int i = 0; i < s.length(); ++i){
            char c = s.charAt(i);
            --visited[c];
            //while循环找出可以确保visited[c] >= 0
            //并且当visited < 0时，将start重新设置为窗口起点
            while(visited[c] < 0){
                ++visited[s.charAt(start)];
                ++start;
            }
            
            if((i-start+1) == p.length()){
                res.add(start);
            }
        }
        
        return res;
    }
}