public String addBinary(String a, String b) { // int carry=0; // String result=””; // int i=0; // int alen=a.length(); // int blen=b.length(); // while(i<alen||i<blen||carry!=0){ // int x=(i<alen)?((a.charAt(alen-1-i)==’1′)?1:0):0; // int y=(i<blen)?((b.charAt(blen-1-i)==’1′)?1:0):0; // result=(x+y+carry)%2+result; // carry=(x+y+carry)/2; // i++; int carry = 0; String res = “”; int i = 0; int aLen = a.length(); int bLen = […]
public boolean isPalindrome(String s) { // Write your code here if(s.length() == 0 || s == null) return true; s = s.toLowerCase(); s = s.trim(); int i = 0; int j = s.length() – 1; while(i <= j) { while(i <= j && !((s.charAt(i) <= ‘z’ && s.charAt(i) >= ‘a’) || (s.charAt(i) >= ‘0’ && […]
public List<Interval> merge(List<Interval> intervals) { // write your code here List<Interval> res= new ArrayList<Interval>(); if(intervals.size() == 0 || intervals == null) return res; Collections.sort(intervals, new IntervalComparator()); Interval first = intervals.get(0); for(int i = 1; i < intervals.size(); i++) { Interval cur = intervals.get(i); if(cur.start <= first.end) { first.end = Math.max(cur.end, first.end); }else{ res.add(first); first = […]
public boolean isSubtree(TreeNode T1, TreeNode T2) { // write your code here if(T2 == null) return true; else if(T1 == null) return false; else return isSameTree(T1, T2) || isSubtree(T1.left, T2) || isSubtree(T1.right, T2); } public boolean isSameTree(TreeNode T1, TreeNode T2) { if(T1 == null && T2 == null) return true; if(T1 == null || T2 […]
public int lengthOfLastWord(String s) { // Write your code here if(s == null || s.length() == 0) return 0; for(int i = s.length()-1; i >=0; i–) { if(s.charAt(i) != ‘ ‘) { int res = 0; while(i >=0 && s.charAt(i) != ‘ ‘ ){ res++; i–; } return res; } } return 0; }
public int findMissing(int[] nums) { // write your code here if(nums.length == 0 || nums == null) return 0; int missing = 0; int n = nums.length; for(int i = 0; i <= n; i++) { missing^=i; } // xor [0,n] for(int i : nums) missi raneng ^= i;//xor i, i in nums return missing; […]
原题: http://codeforces.com/contest/570/problem/B 题目大意: 给一个范围[1,n], 一个人取范围中的数字m, 问你如何取一个数字a, 可以让|c-a| < |c-m|的概率更高, where c 是一个[1,n]中的随机数 分析: 可以把范围看成一组数, 其中的m把这组数字分成了2组, [1,m)和(m,n]. 于是这个题就转化成问你, 找一个数字a,让a覆盖的数字比m覆盖的数字更大. 这个数字肯定在m+1或者m-1, 这时候, 需要比一下m和n/2, 看看m是在n的中间的左边还是右边, 如果是右边, 那么说明m左边的数字比右边的多, 所以我们选m-1, 相反同理. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int m = in.readInt(); if (n == 1) { out.print(1); return; } if (m > n / […]
原题: http://codeforces.com/contest/570/problem/C 题目大意: 给一个string s, s有小写字母和’.’组成. 做m个query替换操作, 对于每个操作都要进行固定的处理, 这个处理是把s中的连续两个’.’. 替换成1个, 一次替换消除一对’.’ 问对每个query, 需要几次替换. 分析: 开始的时候以为能爆过….结果暴到test case7 过不去了…后来只能分情况讨论. 一上来先算下原始的s需要几次替换, 假设原始string s 需要n次替换. 这时, 对于m个query, 有两种情况可以改变n的值. 替换的字符是’.’ 但是当前字符不是, 有以下两种情况: 如果当前字符的前边是’.’, n++ 如果当前字符的后边是’.’, n++ 替换的字符是字母, 但是当前字符是’.’, 有以下两种情况: 如果当前字符的前边是’.’, n– 如果当前字符的后边是’.’, n– 最后别忘了把字符替换一下. public void solve(int testNumber, InputReader in, OutputWriter out) { int len = in.readInt(); int m = in.readInt(); […]
原题: http://codeforces.com/contest/570/problem/A 题目大意: 竞选问题, n个候选人, m个城市. 选取规则是,第一轮同城选最大,一样选最小index. 第二轮是城市间选最大, 一样选最小index. 分析: 没什么分析的…走一遍矩阵先行找最大, 然后记录下, 再列找最大… public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int m = in.readInt(); int[] count = new int[n]; for (int i = 0; i < m; i++) { int[] nums = IOUtils.readIntArray(in,n); int maxIndex = selection(nums); count[maxIndex]++; } out.print(selection(count)+1); […]
public int maxSquare(int[][] matrix) { // write your code here if(matrix == null || matrix.length == 0) return 0; int[] height = new int[matrix[0].length]; int res = 0; for(int i = 0 ; i < matrix.length; i++) { for(int j = 0; j < matrix[0].length; j++) { if(matrix[i][j] == 1) height[j]++; else height[j] = 0; […]