1
2
3
4
5
6
7
List<List<Integer>> graph = new ArrayList<>(n);
        for (int i = 0; i < n; ++i) graph.add(new ArrayList<>(3));
        for (int[] path : paths) {
            graph.get(path[0] - 1).add(path[1] - 1);
            graph.get(path[1] - 1).add(path[0] - 1);
        }

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer>map=new HashMap();
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(target-nums[i]))
               return new int[]{i,map.get(target-nums[i])};
            map.put(nums[i],i);
        }
        return null;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int[] twoSum(int[] numbers, int target) {
       int i=0;int j=numbers.length-1;
       while(i<j){
           if(numbers[i]+numbers[j]<target) i++;
           else if(numbers[i]+numbers[j]>target) j--;
           else return new int[]{i+1,j+1};
       }
       return null;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {  
        Arrays.sort(nums);
        List<List<Integer>>list=new ArrayList();
        for(int i=0;i<nums.length;i++){
            if(i>0&&nums[i]==nums[i-1])
              continue;//去重
            int L=i+1;int R=nums.length-1;
            while(L<R){
                 if(nums[L]+nums[R]>0-nums[i])
                   R--;
                 else if(nums[L]+nums[R]<0-nums[i])
                   L++;
                  else {
                    list.add(Arrays.asList(nums[i],nums[L],nums[R]));
                    int temp=nums[L];
                    int temp2=nums[R];
                    while(L<R&&nums[++L]==temp);//L去重，且要注意避免越界
                    while(L<R&&nums[--R]==temp2);//R去重，且要注意避免越界
                }                 
            }            
        }
     return list;
    }   
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
      public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> resp = new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            for(int j=i+1;j<nums.length;j++){
                for(int k=j+1;k<nums.length;k++){
                    for(int l=k+1;l<nums.length;l++){
                        if(nums[i]+nums[j]+nums[k]+nums[l] == target){
                            List<Integer> ans = new ArrayList<>();
                            ans.add(nums[i]);
                            ans.add(nums[j]);
                            ans.add(nums[k]);
                            ans.add(nums[l]);
                            Collections.sort(ans);
                            if(!resp.contains(ans)){
                               resp.add(ans); 
                            }
                        }
                    }
                }
            }
        }
        return resp;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>>list=new ArrayList();
      for(int k=0;k<nums.length;k++){
        if(k>0&&nums[k]==nums[k-1])
              continue;//去重            
        for(int i=k+1;i<nums.length;i++){
            if(i>k+1&&nums[i]==nums[i-1])
              continue;//去重
            int L=i+1;int R=nums.length-1;
            while(L<R){
                 if(nums[L]+nums[R]>target-nums[k]-nums[i])
                   R--;
                 else if(nums[L]+nums[R]<target-nums[k]-nums[i])
                   L++;
                  else {
                    list.add(Arrays.asList(nums[k],nums[i],nums[L],nums[R]));
                    int temp=nums[L];
                    int temp2=nums[R];
                    while(L<R&&nums[++L]==temp);//L去重，且要注意避免越界
                    while(L<R&&nums[--R]==temp2);//R去重，且要注意避免越界
                }                 
            }            
        }
      }
      return list;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length < 4) {
            return result;
        }
        Arrays.sort(nums);
        int length = nums.length;
        // 遍历
        for (int i = 0; i < nums.length - 3; i++) {
            // 剪枝
            if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
            if (nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) continue;
            // 去重
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            // 对第二个数进行循环
            for (int j = i + 1; j < nums.length - 2; j++) {
                // 剪枝
                if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;
                if (nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) continue;
                // 去重
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                // 定义指针
                int left = j + 1, right = nums.length - 1;
                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else if (sum == target) {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        // 在找到一个数组后进行去重
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        // 移动指针
                        right--;
                        left++;
                    }
                }                
            }
        }
        return result;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int fib(int n) {
      if(n<=1)
        return n;
      int a=0,b=1,c=0;
      for(int i=1;i<n;i++){
           c=a+b;
           a=b;
           b=c;
      }
     return c;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {  
    public int climbStairs(int n) {
      if(n<3)
        return n;
      int a=1,b=2,c=0;
       for(int i=3;i<=n;i++){
          c=a+b;
          a=b;
          b=c;
       }
       return c;
    }   
}

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int maxSubArray(int[] nums) {
        int dp[]=new int [nums.length];
        dp[0]=nums[0];
        int max=dp[0];
        for(int i=1;i<nums.length;i++){           
            dp[i]=dp[i-1]>0?nums[i]+dp[i-1]:nums[i];             
            max=Math.max(dp[i],max);
        }
        return max;      
    }     
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxSubArray(int[] nums) {
         //解题思路，当前指针之前的序列和小于0就丢弃，就是已经小于0的连续数列就不要参与后面的计算了，大于0就加到nums[i]上面
         
         int curSum=nums[0];              
         int max=nums[0];
         for(int i=1;i<nums.length;i++)
         {
            if(nums[i-1]>0)  nums[i]=nums[i-1]+nums[i];          
            max=Math.max(nums[i],max);
         }        
     return max;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxSubArray(int[] nums) {
      int result=Integer.MIN_VALUE;
      int sum=0;
      for(int i=0;i<nums.length;i++)
      {
          sum+=nums[i];
          if(sum>result) result=sum;
          if(sum<0) sum=0;
      }
    return result;
    }
}

1
2
 return memo[i][target] = dfs(nums, target - nums[i], i + 1, memo) || dfs(nums, target, i + 1, memo);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if (sum % 2 != 0) return false;
        Arrays.sort(nums);
        return dfs(nums, sum / 2, 0, new Boolean[nums.length][sum / 2 + 1]);
    }

    private boolean dfs(int[] nums, int target, int i, Boolean[][] memo) {
        if (i >= nums.length || nums[i] > target) 
            return false;
        if (nums[i] == target) 
            return true;
        if (memo[i][target] != null)
            return memo[i][target];
        return memo[i][target] = dfs(nums, target - nums[i], i + 1, memo) || dfs(nums, target, i + 1, memo);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public boolean canPartition(int[] nums) {
        //实质上是求数组中有没有几个数相加能够达到数组所有元素和的一半，且每个元素只能用1次，是一个0,1背包问题
        int sum=0;
        int max=0;
        for(int i=0;i<nums.length;i++){
           sum+=nums[i];
           max=Math.max(nums[i],max);
        }          
        if(sum%2!=0||max>sum/2) 
            return false;
         int target=sum/2; 
        boolean dp[][]=new boolean[nums.length+1][target+1];
        
        for(int i=1;i<=nums.length;i++) {
            for(int j=0;j<=target;j++){
                if(nums[i-1]>j)//肯定不能用nums[i-1]来组成j,只能用上一行的结果
                    dp[i][j]=dp[i-1][j];//直接抄上一行的结果                
                else if(nums[i-1]<j)//可以用当前nums[i-1]来组成j,那么还要看前面的元素能不能组成j-nums[i-1],也可以不用当前nums[i-1],直接抄前面的结果，两者相或就行了
                    dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i-1]];                 
                else
                 dp[i][j]=true;//可以组成j，因为nums[i-1]=j
            }
        }
        return dp[nums.length][target];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, max);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
    public int coinChange(int[] coins, int amount) {
        if(amount==0) return 0;
        int dp[]=new int [amount+1];
        dp[0]=0;
        Set<Integer>set=new HashSet();
        for(int i=0;i<coins.length;i++) set.add(coins[i]);
        for(int i=1;i<=amount;i++)
        {   
            dp[i]=Integer.MAX_VALUE;
            if(set.contains(i))   dp[i]=1;          
            else {
                  for(int j=1;j<=i/2;j++)
                 {
                     if(dp[j]!=-1&&dp[i-j]!=-1)                                  
                        dp[i]=Math.min(dp[i],dp[j]+dp[i-j]);
                 }
                if(dp[i]==Integer.MAX_VALUE) dp[i]=-1;
            }                           
        }
     return  dp[amount];
    } 
}

1
2
3
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean isValid(String s) {
         Stack<Character>stack=new Stack();            
            for(int i=0;i<s.length();i++){
             if(s.charAt(i)==')'){
                 if(!stack.isEmpty()&&stack.peek()=='(') stack.pop();
                 else  return false;
             }
             else if(s.charAt(i)=='}'){
                 if(!stack.isEmpty()&&stack.peek()=='{') stack.pop();
                 else  return false;
             }
             else if(s.charAt(i)==']'){
                 if(!stack.isEmpty()&&stack.peek()=='[') stack.pop();
                 else  return false;
             }
             else
               stack.push(s.charAt(i));
         }        
       return stack.isEmpty();    
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int arr[]=new int [nums1.length];      
        for(int i=0;i<nums1.length;i++){            
              int j=0;
                while(j<nums2.length&&nums2[j]!=nums1[i])
                     j++;
                j++;//后移一位     
                while(j<nums2.length&&nums2[j]<nums1[i])
                     j++;
                 arr[i]=j>=nums2.length?-1:nums2[j];
                      
        }
        return arr;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        for(int i=0;i<nums1.length;i++){            
                int j=0;
                while(j<nums2.length&&nums2[j++]!=nums1[i]);                                 
              
                while(j<nums2.length&&nums2[j]<nums1[i])
                    j++;                                               
                 nums1[i]=j>=nums2.length?-1:nums2[j];
        }
        return  nums1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;

        Stack<Integer> stack = new Stack<>();
        Map<Integer, Integer> map = new HashMap<>();
        // 先处理 nums2，把对应关系存入哈希表
        for (int i = 0; i < len2; i++) {
            while (!stack.isEmpty() && stack.peek() < nums2[i]) {
                map.put(stack.pop(), nums2[i]);
            }
            stack.add(nums2[i]);
        }
        // 遍历 nums1 得到结果集    
        for (int i = 0; i < len1; i++) {
            nums1[i] = map.getOrDefault(nums1[i], -1);
        }
        return nums1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n=nums.length;
        int ret[]=new int[n];
        Arrays.fill(ret, -1);
        Stack<Integer>stack=new Stack();      
       // Map<Integer,Integer>map=new HashMap();//数组中有重复元素，不好用map了
        for(int i=0;i<n*2-1;i++){
            while(!stack.isEmpty()&&nums[stack.peek()]<nums[i%n]){
                    ret[stack.pop()]=nums[i%n];  
            }           
                   //stack.push(nums[i%n]);
                   stack.push(i%n);//存索引，绝了
        }     
        return ret;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n=nums.length;
        int ret[]=new int[n];
        Arrays.fill(ret, -1);
        Stack<Integer>stack=new Stack();      
        for(int i=0;i<n*2-1;i++){
            while(!stack.isEmpty()&&nums[stack.peek()]<nums[i%n]){
                    ret[stack.pop()]=nums[i%n];  
            }                           
            if(ret[i%n]==-1)
               stack.push(i%n);//存索引，绝了
        }     
        return ret;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        // 使用数组模拟栈，hh 代表栈底，tt 代表栈顶
        int[] d = new int[n * 2];
        int hh = 0, tt = -1;
        for (int i = 0; i < n * 2; i++) {
            while (hh <= tt && nums[i % n] > nums[d[tt]]) {
                int u = d[tt--];
                ans[u] = nums[i % n];
            }
            d[++tt] = i % n;
        }
        return ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
        public boolean find132pattern(int[] nums) {
        int len=nums.length;
        if(len<3) return false;
        Stack<Integer> st=new Stack<>();
        int K=-1;
        for(int I=len-1;I>=0;I--){
            if(K>-1&&nums[K]>nums[I]) return true;
            while(!st.isEmpty()&&nums[st.peek()]<nums[I]){
                K=st.pop();
            }
            st.push(I);
        }
        return false;
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<Integer> getRow(int rowIndex) {
     List<List<Integer>>list=new ArrayList();
     for(int i=0;i<=rowIndex;i++){
         List list2=new ArrayList();       
         for(int j=0;j<=i;j++){  
             if(j==0||j==i){
                 list2.add(1);
             }else{
                 list2.add(list.get(i-1).get(j-1)+list.get(i-1).get(j));
             }
         }
         list.add(list2);
     }
     return list.get(rowIndex);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> pre = new ArrayList<Integer>();
        for (int i = 0; i <= rowIndex; ++i) {
            List<Integer> cur = new ArrayList<Integer>();
            for (int j = 0; j <= i; ++j) {
                if (j == 0 || j == i) {
                    cur.add(1);
                } else {
                    cur.add(pre.get(j - 1) + pre.get(j));
                }
            }
            pre = cur;
        }
        return pre;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int numSquares(int n) {
       int dp[]=new int[n+1];
       for(int i=1;i<=n;i++){
           if((int)Math.sqrt(i)*(int)Math.sqrt(i)==i){
               dp[i]=1;
           }
           else{
               dp[i]=Integer.MAX_VALUE;
               for(int j=1;j<=i/2;j++){
                   dp[i]=Math.min(dp[j]+dp[i-j],dp[i]);
               }
           }
       }
       return dp[n];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int numSquares(int n) {
        int[] f = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int minn = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++) {
                minn = Math.min(minn, f[i - j * j]);
            }
            f[i] = minn + 1;
        }
        return f[n];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution{
public int numSquares(int n) {
    Queue<Integer> queue = new LinkedList<>();
    //记录访问过的节点值
    Set<Integer> visited = new HashSet<>();
    queue.offer(0);
    visited.add(0);
    //树的第几层
    int level = 0;
    while (!queue.isEmpty()) {
        //每一层的节点数量
        int size = queue.size();
        level++;
        //遍历当前层的所有节点
        for (int i = 0; i < size; i++) {
            //节点的值
            int digit = queue.poll();
            //访问当前节点的子节点，类比于二叉树的左右子节点
            for (int j = 1; j <= n; j++) {
                //子节点的值
                int nodeValue = digit + j * j;
                //nodeValue始终是完全平方数的和，当他等于n的
                //时候直接返回
                if (nodeValue == n)
                    return level;
                //如果大于n，终止内层循环
                if (nodeValue > n)
                    break;
                if (!visited.contains(nodeValue)) {
                    queue.offer(nodeValue);
                    visited.add(nodeValue);
                }
            }
        }
    }
    return level;
}
}

1
2
3
4
5
6
7
8
9
10
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;        
       return hasPathSum(root.right, sum-root.val)|| hasPathSum(root.left, sum-root.val);                
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    int count=0;
    int val=-1;
    public int kthSmallest(TreeNode root, int k) {
        inOrder(root,k);
        return val;
    }
    public void inOrder(TreeNode root, int k){
        if(root==null)
          return ;
         inOrder(root.left, k);
         count++;
         if(count==k){
             val= root.val;
             return;
         }
        inOrder(root.right, k);       
    }    
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    int res=0;
    public int minCameraCover(TreeNode root) {       
       return  dfs(root)==0?res+1:res;//如果父节点是无覆盖状态，那么需要在父节点添加一台摄像机
    }
    public int dfs(TreeNode root){
        if(root==null)
           return 2;//节点有覆盖
        int left=dfs(root.left);
        int right=dfs(root.right);
        //0表示无覆盖，1表示有相机，2表示有覆盖，左右节点可以组成9种状态
        //(00,01,02,10,11,12,20,21,22)
               
        //只要有一个无覆盖，父节点就需要相机来覆盖这个子节点 00,01,10,20,02
        if(left==0||right==0){
            res++;
            return 1;
        }
         //子节点其中只要有一个有相机，那么父节点就会是有覆盖的状态11,21,12
        if(left==1||right==1){
            return 2;
        }
        //还有一个就是22，两个子节点都是有覆盖的状态，父节点可以没有相机，可以借助它自己的父节点
        return 0;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int lengthOfLongestSubstring(String s) {
      if(s.length()<=1)
         return s.length();
      int left=0;int max=0;     
      Map<Character,Integer>map=new HashMap();
      char arr[]=s.toCharArray();
      for(int i=0;i<arr.length;i++){
          if(!map.containsKey(arr[i])){
              map.put(arr[i],i);
          }
          else{
              max=Math.max(i-left,max);
              left=Math.max(left,map.get(arr[i])+1);
              map.put(arr[i],i);              
          }        
      }
       max=Math.max(arr.length-left,max); 
      return max;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int lengthOfLongestSubstring(String s) {    
      int left=0;int max=0;     
      Map<Character,Integer>map=new HashMap();
      char arr[]=s.toCharArray();
      for(int i=0;i<arr.length;i++){
          if(map.containsKey(arr[i])){                      
            max=Math.max(i-left,max);
            left=Math.max(left,map.get(arr[i])+1);                         
          }  
           map.put(arr[i],i);        
      }
      max=Math.max(arr.length-left,max); 
      return max;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int lengthOfLongestSubstring(String s) {
     int arr[]=new int[128];
     char arr1[]=s.toCharArray();
     int left=0;int max=0;
     for(int i=0;i<arr1.length;i++){
         arr[arr1[i]-32]++;
         if(arr[arr1[i]-32]>1){
             max=Math.max(max,i-left);
             while(arr[arr1[i]-32]>1){
              arr[arr1[left]-32]--;
              left++;
         }
        }       
     }
    return  max=Math.max(max,s.length()-left);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
      int m=s1.length();
      int n=s2.length();
      int p=s3.length();
       if(m+n!=p)
         return false;
       boolean dp[][]=new boolean[m+1][n+1];    
      //dp[i][j]表示s1的钱i个字符和s2的前j个字符能否组成s3的前i+j个字符     
         dp[0][0]=true;
        for(int i=1;i<=m;i++)//填第一列
            dp[i][0]=dp[i-1][0]&&s1.charAt(i-1)==s3.charAt(i-1);
        for(int j=1;j<=n;j++)//填第一行
            dp[0][j]=dp[0][j-1]&&s2.charAt(j-1)==s3.charAt(j-1);    
        for(int i=1;i<=m;i++){
          for(int j=1;j<=n;j++){
            //dp[i][j]可以由dp[i-1][j]和dp[i][j-1]变化而来                   
            dp[i][j]=(dp[i-1][j]&&s1.charAt(i-1)==s3.charAt(i+j-1))||
            (dp[i][j-1]&&s2.charAt(j-1)==s3.charAt(i+j-1));
          }
      }
      return dp[m][n];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    private boolean[][] visited;
    
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length())
            return false;
        visited = new boolean[s1.length() + 1][s2.length() + 1];
        return backtrack(s1, s2, s3, 0, 0, 0);
    }

    private boolean backtrack(String s1, String s2, String s3, int i, int j, int k) {
        if (k == s3.length())//说明s3的所有字符都被匹配了
            return true;
        if (visited[i][j])//如果当前节点已经被访问过，说明上一条路径从这经过走不通，即使是换一条路，经过相同的节点，依然是走不通的
            return false;//在二维矩阵里面，这个元素访问过，说明它的右边和下边都被访问过了，但是行不通，那我们换条路又经过了这个点肯定还是走不通的
        visited[i][j] = true;
        if (i < s1.length() && s1.charAt(i) == s3.charAt(k)
                && backtrack(s1, s2, s3, i + 1, j, k + 1)
            || j < s2.length() && s2.charAt(j) == s3.charAt(k)
                && backtrack(s1, s2, s3, i, j + 1, k + 1))
            return true;

        return false;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public boolean isSubsequence(String x, String y) {
        int j = 0;
        for (int i = 0; i < y.length() && j < x.length(); i++)
            if (x.charAt(j) == y.charAt(i))
                j++;
        return j == x.length();
    }
    public String findLongestWord(String s, List < String > d) {
        String max_str = "";
        for (String str: d) {
            if (isSubsequence(str, s)) {
                if (str.length() > max_str.length() || (str.length() == max_str.length() && str.compareTo(max_str) < 0))
                    max_str = str;
            }
        }
        return max_str;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int[] gardenNoAdj(int n, int[][] paths) {
       Map<Integer,Set<Integer>>graph=new HashMap();
       for(int i=1;i<=n;i++)
         graph.put(i,new HashSet());
       for(int []path:paths){
            graph.get(path[0]).add(path[1]);
            graph.get(path[1]).add(path[0]);
       }
       int res[]=new int[n];
       for(int i=1;i<=n;i++){
           boolean[]used=new boolean[5];
           for(int adj:graph.get(i))
                used[res[adj-1]]=true;//找出相邻的点还未使用的 1-4 的部份;//比如adj=1,res[0]=0说明
                //res本来都是0，如果不为0，说明有一种花被放进res里面了
            for(int j=1;j<=4;j++){
                if(!used[j])
                   res[i-1]=j;
            }
       }
       return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[] gardenNoAdj(int n, int[][] paths) {
        List<List<Integer>> graph = new ArrayList<>(n);
        for (int i = 0; i < n; ++i) graph.add(new ArrayList<>(3));
        for (int[] path : paths) {
            graph.get(path[0] - 1).add(path[1] - 1);
            graph.get(path[1] - 1).add(path[0] - 1);
        }
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            boolean[] used = new boolean[5];
            for (int j : graph.get(i)) used[ans[j]] = true;
            int t = 1;
            while (used[t]) ++t;
            ans[i] = t;
        }
        return ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.Arrays;

public class Solution {
    public int[] gardenNoAdj(int n, int[][] paths) {
        int[] res = new int[n];
        if(paths.length == 0){
            Arrays.fill(res,1);
            return res;
        }
        int[][] adjoinGarden = new int[n + 1][3];
        int[] gardenSize = new int[n + 1];
        for (int[] p : paths) {
            int v1 = p[0];
            int v2 = p[1];
            adjoinGarden[v1][gardenSize[v1]++] = v2;
            adjoinGarden[v2][gardenSize[v2]++] = v1;
        }
        for (int i = 1; i <= n; i++) {
            boolean[] color = new boolean[4];
            for (int j : adjoinGarden[i]) {
                if (j != 0 && res[j - 1] != 0) {
                    color[res[j - 1] - 1] = true;
                }
            }
            if (!color[0]) {
                res[i - 1] = 1;
            } else if (!color[1]) {
                res[i - 1] = 2;
            } else if (!color[2]) {
                res[i - 1] = 3;
            } else {
                res[i - 1] = 4;
            }
        }
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
    List<List<Integer>>graph=new ArrayList();
    int[][]costs;
  //  Integer[][]memo;
    boolean visited[];
    int max;
    //
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
      costs=new int[n][n];
    //  memo=new Integer[n][n];
      visited=new boolean[n];
      max=n;    
      for(int i=0;i<n;i++)
        graph.add(new ArrayList());//添加n个临界表
      for(int[] flight:flights){         
          costs[flight[0]][flight[1]]=flight[2];//初始化花费
         // costs[flight[1]][flight[0]]=flight[2];//初始化花费//注意是有向图
          graph.get(flight[0]).add(flight[1]);//初始化邻接表
        //  graph.get(flight[1]).add(flight[0]);//初始化邻接表
      }   
       int result=dfs(src,dst,k+2,0);
       return (result ==max*10000) ?-1:result;
    }
    public int  dfs(int src,int dst,int k, int cost){         
           
           if((src==dst)&&k>0){
           //已经到达终点，记录当前花费
           //    return memo[src][dst]=cost;
             return cost;
           }
           if(k<=0)//已经超过k个中转站了，不符合要求，返回一个较大的值
              return max*10000;
         //   if(memo[src][dst]!=null)   
           //    return  memo[src][dst];                         
            if(visited[src])
              return max*10000 ; //不能反向访问              
            visited[src]=true;
           int result= max*10000 ;
           for(int i=0;i<graph.get(src).size();i++){                               
              if(costs[src][graph.get(src).get(i)]>0){//注意是有向图，如果不大于0，说明两点之前没有连线，无法起飞
                 int temp1= dfs(graph.get(src).get(i),dst,k-1,cost+costs[src][graph.get(src).get(i)]); 
                 result=Math.min(result,temp1);  
              }                                                                   
        }   
          visited[src]=false; 
          return result;   
         // return memo[src][dst]=result;                                 
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
public class Solution {

    private int[][] graph;
    private boolean[] visited;
    private int res = Integer.MAX_VALUE;

    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        K = Math.min(K, n - 2);

        this.graph = new int[n][n];
        for (int[] flight : flights) {
            graph[flight[0]][flight[1]] = flight[2];
        }

        this.visited = new boolean[n];
        // 开始深度优先遍历，注意：这里传 K + 1，这是因为 K 次经停，总共 K + 1 个站
        dfs(src, dst, K + 1, 0);

        if (res == Integer.MAX_VALUE) {
            return -1;
        }
        return res;
    }


    /**
     * 从 src 出发，到 dst 为止，最多经过 k 站（这里 k 包括 src）
     *
     * @param src  起点站
     * @param dst  终点站
     * @param k    经过的站点数限制
     * @param cost 已经花费的价格
     */
    private void dfs(int src, int dst, int k, int cost) {
        if (src == dst) {
            res = cost;
            return;
        }

        if (k == 0) {
            return;
        }

        for (int i = 0; i < graph[src].length; i++) {
            if (graph[src][i] > 0) {
                if (visited[i]) {
                    continue;
                }

                // 剪枝：跳过可能产生较高费用的路径，从而选出最少价格
                if (cost + graph[src][i] > res) {
                    continue;
                }

                visited[i] = true;
                dfs(i, dst, k - 1, cost + graph[src][i]);
                visited[i] = false;
            }
        }
    }
}


作者：LeetCode
链接：https://leetcode-cn.com/problems/cheapest-flights-within-k-stops/solution/k-zhan-zhong-zhuan-nei-zui-bian-yi-de-hang-ban-b-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    // 看到了DAG
    // dp[i][j][k],从i站到j站最多中转k站的最小代价!看题目描述自然想到这个状态
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        int[][] cost = new int[n][n];
        for(int i = 0; i < flights.length; i++){
            int st = flights[i][0];
            int en = flights[i][1];
            int price = flights[i][2];
            cost[st][en] = price;
        }
        int[][][] dp = new int[n][n][K+2];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                Arrays.fill(dp[i][j], -1);
            }
        }
        int res = f(cost, src, dst, K+1, dp);
        return res >= 1000000 ? -1 : res;
    }
    private int f(int[][] cost, int src, int dst, int K, int[][][] dp){
        if(K < 0){
            return 1000000;   
        }
        if(dp[src][dst][K] != -1){
            return dp[src][dst][K];
        }
        if(src == dst){
            return dp[src][dst][K] = 0;
        }
        int ans  = Integer.MAX_VALUE;
        for(int i = 0; i < cost.length; i++){
            if(cost[src][i] != 0){
                ans = Math.min(ans, cost[src][i] + f(cost, i, dst, K-1, dp));
            }
        }
        return dp[src][dst][K] = (ans == Integer.MAX_VALUE ? 1000000 : ans);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        // dp[i][k]是经过k个中转站后到达站 i 的最小费用
        int[][] dp = new int[n][K + 1];

        // 循环初始化整个二维数组。
        for(int i = 0; i < n; ++i) Arrays.fill(dp[i], Integer.MAX_VALUE);

        // 利用flights中的信息初始化src可直达的班次
        for(int[] flight : flights) {
            if(flight[0] == src){
                dp[flight[1]][0] = flight[2];
            }
        }

        // 循环初始化数组中dst == src的行
        for(int i = 0; i <= K; i++){
            dp[src][i] = 0;
        }

        //动态规划状态转移方程，开始填表
        //直达的已经初始化了（即k = 0的情况），现在从k = 1 的开始，即只有一个中转站开始
        for(int k = 1; k <= K; k++){
            for(int[] flight : flights){
                //结合题目理解
                if(dp[flight[0]][k - 1] != Integer.MAX_VALUE){
                    dp[flight[1]][k] = Math.min(dp[flight[1]][k], dp[flight[0]][k - 1] + flight[2]);
                }
            }
        }
        return dp[dst][K] == Integer.MAX_VALUE? -1: dp[dst][K];
    }
}