发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/split-array-largest-sum/

　　给你非负整数数组和整数m，让你把数组分成连续的m段子数组，求所有分法的m字段和的最大值的最小化

题目分析

　　最小化最大值问题，可以考虑二分查找，二分check的条件是所有m子段和都小于等于某个数字d，而check方法的实现利用贪心的思想，从前向后扫描原数组，每次凑连续几个数，是这几个数的和尽可能接近d，但不能大于d，这样就得到一组，然后继续向后扫描，一直到数组结尾，看看最后能得到几组，这个组数如果小于等于m，那么d是可行的，check返回true。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class Solution {
    private boolean check(int d, int[] nums, int m) {
        int len = nums.length;
        int sum = 0;
        int count = 0;
        for(int i = 0; i < len; i++) {
            if(nums[i] > d) {
                return false;
            }
            if(sum + nums[i] > d) {
                sum = nums[i];
                count++;
                if(count >= m) {
                    return false;
                }
            } else {
                sum += nums[i];
            }
        }
        return true;
    }
    
    public int splitArray(int[] nums, int m) {
        int len = nums.length;
        int left = 0;
        int right = 0x7fffffff;
        int mid;
        while(right - left > 1) { //(left, right]
            mid = (left + right) / 2;
            if(check(mid, nums, m)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }
}

发表于   |   分类于   |  

题目大意

　　此题是2017微软秋季校园招聘在线编程笔试的第二题

　　http://hihocoder.com/problemset/problem/1400

　　一个长度为N的字符串，已知有M个字符对不能相邻，让你求为满足此性质，原字符串的最少删除字符个数。

题目分析

  • 第一种思路，原题实际上是求满足某种特殊条件的最长子序列，这种特殊条件是满足给定的M对字符不能相邻，所以此题很像最长升序子序列，又注意到，本题字符数一共就26个。可以采用动态规划的思路，我们要维护一个长度为26的数组，也就对应26个英文字母，对应存的值是以该下标字母为结尾所能构成满足条件的最长子序列。，比如f['a' - 'a']存的就是以字母a为结尾的子序列的最大长度。原字符串为str，假设扫描到某个位置i，那么从第0个位置到第i个位置的所能构成的最长子序列其实是遍历f[j]，j跟i所构成的长度为2的字符串满足条件的最大值。实质上，我们要从前到后扫描整个字符串，一直更新f数组的值。最后求的结果就是N-max{f[i]}
  • 第二种思路，记忆化搜索的思路，从前向后搜索字符串，每个位置都可以选择要或者不要，但是由于一些字符之间不能相邻，所以扫描到特定字符时，必须不要，因为跟已纪录的字符串最后一个冲突，如果不冲突还是有两种选择，要或者不要。但是有个问题，初始时，字符串的第一个字符到底是要还是不要，可以简化一下，认为在原字符串前加入一个字符，该字符的ascii值为'a' - 1 这样这个字符不可能跟任何字符产生冲突，换句话说，新构造出的字符串所求的结果跟原字符串相同，之后代码就是标准的dfs的思路。不过这样肯定会超时，因为存在重复计算，需要记录一些东西。引入一个二维数组f，f的第一维存的是已搜索保存的结果最后一位字符，第二维是将要搜索的位置index，比如f[c][5]的含义是搜索路径最后一个是字符c，并且下一个搜索的是第五个字符串时，从第五个字符串到最后一个字符串能够是搜索路径增加的长度。
阅读全文 »

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/binary-tree-postorder-traversal/

　　二叉树的后序遍历迭代（非递归）版。

题目分析

　　二叉树的遍历的递归比较好写，非递归版本通常借助栈实现。既然是后序遍历，对于任何一个节点，首先也访问左子树的所有节点，再访问右子树的所有节点，然后访问本节点。这里我们要用到一个栈和一个两个辅助的指针cur和top。cur代表当前考虑的节点，cur不空的时候会入栈，top为栈顶指针。

　　首先，cur值置为root节点，top置为null，循环的条件是cur不为空或者栈不为空，cur不为空主要是为初始时进入循环。进入循环以后先判断cur指针是否为空

  • 1.cur若不为空，说明需要访问该节点的，但是由于是后序遍历，先将cur入栈，当以后cur的左右子树均访问完时再访问cur，因此把cur更新成cur的左节点
  • 2.cur若为空，左子树访问到了尽头，这时看下栈顶top
    • (1).top的右儿子不为空，那么将cur置为top->right，跳出循环
    • (2).top的右儿子为空，此时top为叶子节点，因此需要访问，之后将此节点弹栈。然后又进入循环，判断出栈的节点是当前栈顶节点的左儿子还是右儿子：
      • a.左儿子，把当前栈顶节点的右儿子赋值给cur，跳出循环
      • b.右儿子，那么要访问栈顶节点，并将此节点弹栈，然后继续循环。
阅读全文 »

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/subsets/

　　输出数组的全部子集。

题目分析

　　输出一个数组的全部子集，这里采用暴力的深度优先搜索。

代码

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
/*
  Given a set of distinct integers, nums, return all possible subsets.
  Note: The solution set must not contain duplicate subsets.
  For example,
  If nums = [1,2,3], a solution is:
  [
    [3],
    [1],
    [2],
    [1,2,3],
    [1,3],
    [2,3],
    [1,2],
    []
  ]
  Subscribe to see which companies asked this question
*/
public class Solution {
	private List<List<Integer>> res = new ArrayList<List<Integer>>();
	private Boolean[] v;
	private void search(int i, int[] nums) {
		int len = nums.length;
		if(i >= len) {
			List<Integer> ans = new ArrayList<Integer>();
			for(int ii = 0; ii < len; ii++) {
				if(v[ii] == true) {
					ans.add(nums[ii]);
				}
			}
			res.add(ans);
			return;
		}
		v[i] = true;
		search(i + 1, nums);
		v[i] = false;
		search(i + 1, nums);
	}
    public List<List<Integer>> subsets(int[] nums) {
    	int len = nums.length;
        v = new Boolean[len];
        res.clear();
        search(0, nums);
        return res;
    }
}