LintCode

[LintCode] Update Bits

class Solution {
    /**
     *@param n, m: Two integer
     *@param i, j: Two bit positions
     *return: An integer
     */
    public int updateBits(int n, int m, int i, int j) {
        // write your code here
        for(int k = i ; k <= j; k++) {
            n = n & ~(1 << k); // set kth bit in n to 0
            n = n | ((m & (1<<(k-i)))<<i); //set kth bit in n to m's kth bit
        }
        return n;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution {

/**

*@param n, m: Two integer

*@param i, j: Two bit positions

*return: An integer

*/

public int updateBits(int n, int m, int i, int j) {

// write your code here

for(int k = i ; k <= j; k++) {

n = n & ~(1 << k); // set kth bit in n to 0

n = n | ((m & (1<<(k-i)))<<i); //set kth bit in n to m's kth bit

}

return n;

}

n = n & ~(1 << k); 就是把n中的第k个bit设为0 n = n | ((m & (1<<(k-i)))<<i); m & (1<<(k-i)) 是从m的第一个bit开始扫描.因为已知j-i = size of (m)2 ((m & (1<<(k-i)))<<i) 扫描后, 往左shift i位对准n上的i位. n = n | ((m & (1<<(k-i)))<<i) 把n的第i位到j位设为m的0~(j-i)位

Date May 7, 2016
Category LintCode
Comments No Comments

Recover Rotated Sorted Array

public void recoverRotatedSortedArray(ArrayList<Integer> nums) {
        // write your code
        for(int i = 0; i < nums.size()-1; i++){
            if(nums.get(i) > nums.get(i+1)){
                reverse(nums,0,i);
                reverse(nums,i+1,nums.size()-1);
                reverse(nums,0,nums.size()-1);
                break;
            }
        }
    }
    
    
    public void reverse(ArrayList<Integer> nums, int i, int j) {
        while(i < j) {
            Integer tmp = nums.get(i);
            nums.set(i,nums.get(j));
            nums.set(j,tmp);
            i++;
            j--;
        }
    }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

public void recoverRotatedSortedArray(ArrayList<Integer> nums) {

// write your code

for(int i = 0; i < nums.size()-1; i++){

if(nums.get(i) > nums.get(i+1)){

reverse(nums,0,i);

reverse(nums,i+1,nums.size()-1);

reverse(nums,0,nums.size()-1);

break;

}

public void reverse(ArrayList<Integer> nums, int i, int j) {

while(i < j) {

Integer tmp = nums.get(i);

nums.set(i,nums.get(j));

nums.set(j,tmp);

i++;

j--;

}

Date January 8, 2016
Category LintCode
Comments No Comments

Partition Array by Odd and Even

给一个数组, 把奇数放左边, 偶数放右边. 其实就是一个quicksort的partition的改写, 改写的地方很少, 就是判断条件从 nums[i] 对 nums[k]的比较改成nums[i] % 2 != 0的比较.

public void partitionArray(int[] nums) {
        if(nums.length == 0 || nums == null)
            return;
        int i = 0;
        int j = nums.length - 1;
        while(i < j) {
            while(i<j && nums[i] % 2 != 0) // 如果左指针的位置是奇数
                i++;
            while(i< j && nums[j] % 2 == 0) // 如果右指针的位置是偶数
                j--;
            if(i < j)
                swap(nums,i++,j--);
        }
    }
    
    public void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

public void partitionArray(int[] nums) {

if(nums.length == 0 || nums == null)

return;

int i = 0;

int j = nums.length - 1;

while(i < j) {

while(i<j && nums[i] % 2 != 0) // 如果左指针的位置是奇数

i++;

while(i< j && nums[j] % 2 == 0) // 如果右指针的位置是偶数

j--;

if(i < j)

swap(nums,i++,j--);

}

public void swap(int[] nums, int i, int j) {

int t = nums[i];

nums[i] = nums[j];

nums[j] = t;

}

Date January 2, 2016
Category LintCode
Comments No Comments

Binary Tree Paths

打印所有的从root到leaf的path. 开始用的queue做的..后来看了下别的人的答案, 感觉都很简练.po一个别人的答案

public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<String>();
        if(root == null)
            return res;
        if(root.left == null && root.right == null)
            res.add(root.val + "");
        else{
            if(root.left != null)
                res.addAll(binaryTreePaths(root.left));
            if(root.right != null)
                res.addAll(binaryTreePaths(root.right));
            for(int i = 0 ; i < res.size(); i++)
                res.set(i,root.val + "->" + res.get(i));
        }
        return res;
    }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

public List<String> binaryTreePaths(TreeNode root) {

List<String> res = new ArrayList<String>();

if(root == null)

return res;

if(root.left == null && root.right == null)

res.add(root.val + "");

else{

if(root.left != null)

res.addAll(binaryTreePaths(root.left));

if(root.right != null)

res.addAll(binaryTreePaths(root.right));

for(int i = 0 ; i < res.size(); i++)

res.set(i,root.val + "->" + res.get(i));

}

return res;

}

[LintCode] Copy Books

public int copyBooks(int[] pages, int k) {
        // write your code here
        int l = 0;
        int r = 9999999;
        while( l <= r){
            int mid = l + (r - l) / 2;
            if(search(mid,pages,k))
                r = mid-1;
            else
                l = mid+1;
        }
        return l;
    }
    public boolean search(int total, int[] page, int k) {
        int count = 0;
        int sum = 0;
        for(int i = 0; i < page.length;) {
            if(sum + page[i] <= total)
                sum += page[i++];
            else if(page[i] <= total){
                sum = 0;
                count++;
            }
            else
                return false;
        }
        if(sum != 0)
            count++;
        return count <= 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

28

29

public int copyBooks(int[] pages, int k) {

// write your code here

int l = 0;

int r = 9999999;

while( l <= r){

int mid = l + (r - l) / 2;

if(search(mid,pages,k))

r = mid-1;

else

l = mid+1;

}

return l;

}

public boolean search(int total, int[] page, int k) {

int count = 0;

int sum = 0;

for(int i = 0; i < page.length;) {

if(sum + page[i] <= total)

sum += page[i++];

else if(page[i] <= total){

sum = 0;

count++;

}

else

return false;

}

if(sum != 0)

count++;

return count <= k;

Date August 18, 2015
Category LintCode
Comments No Comments

[LintCode] Longest Increasing Continuous subsequence II

public int longestIncreasingContinuousSubsequenceII(int[][] A) {
        // Write your code here
        if(A == null || A.length == 0 || A[0].length == 0)
            return 0;
        int res = 0;
        n = A.length;
        m = A[0].length;
        int[][] dp = new int[n][m];
        for(int i = 0 ; i < n; i++)
            for(int j = 0 ; j < m; j++)
                res = Math.max(res,dfs(A,dp,i,j));
        return res;
    }
    public int dfs(int[][] A, int[][] dp, int x, int y) {
        if(dp[x][y] != 0)
            return dp[x][y];
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (0<=nx && nx < A.length && 0 <= ny && ny < A[0].length && A[x][y] < A[nx][ny]){
                dp[x][y] = Math.max(dp[x][y], dfs(A,dp,nx,ny));
        
            }
        }
        dp[x][y] ++;
        return dp[x][y];
    }public int longestIncreasingContinuousSubsequenceII(int[][] A) {
        // Write your code here
        if(A == null || A.length == 0 || A[0].length == 0)
            return 0;
        int res = 0;
        n = A.length;
        m = A[0].length;
        int[][] dp = new int[n][m];
        for(int i = 0 ; i < n; i++)
            for(int j = 0 ; j < m; j++)
                res = Math.max(res,dfs(A,dp,i,j));
        return res;
    }
    public int dfs(int[][] A, int[][] dp, int x, int y) {
        if(dp[x][y] != 0)
            return dp[x][y];
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (0<=nx && nx < A.length && 0 <= ny && ny < A[0].length && A[x][y] < A[nx][ny]){
                dp[x][y] = Math.max(dp[x][y], dfs(A,dp,nx,ny));
        
            }
        }
        dp[x][y] ++;
        return dp[x][y];
    }

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

public int longestIncreasingContinuousSubsequenceII(int[][] A) {

// Write your code here

if(A == null || A.length == 0 || A[0].length == 0)

return 0;

int res = 0;

n = A.length;

m = A[0].length;

int[][] dp = new int[n][m];

for(int i = 0 ; i < n; i++)

for(int j = 0 ; j < m; j++)

res = Math.max(res,dfs(A,dp,i,j));

return res;

}

public int dfs(int[][] A, int[][] dp, int x, int y) {

if(dp[x][y] != 0)

return dp[x][y];

for (int k = 0; k < 4; k++) {

int nx = x + dx[k];

int ny = y + dy[k];

if (0<=nx && nx < A.length && 0 <= ny && ny < A[0].length && A[x][y] < A[nx][ny]){

dp[x][y] = Math.max(dp[x][y], dfs(A,dp,nx,ny));

}

dp[x][y] ++;

return dp[x][y];

}public int longestIncreasingContinuousSubsequenceII(int[][] A) {

// Write your code here

if(A == null || A.length == 0 || A[0].length == 0)

return 0;

int res = 0;

n = A.length;

m = A[0].length;

int[][] dp = new int[n][m];

for(int i = 0 ; i < n; i++)

for(int j = 0 ; j < m; j++)

res = Math.max(res,dfs(A,dp,i,j));

return res;

}

public int dfs(int[][] A, int[][] dp, int x, int y) {

if(dp[x][y] != 0)

return dp[x][y];

for (int k = 0; k < 4; k++) {

int nx = x + dx[k];

int ny = y + dy[k];

if (0<=nx && nx < A.length && 0 <= ny && ny < A[0].length && A[x][y] < A[nx][ny]){

dp[x][y] = Math.max(dp[x][y], dfs(A,dp,nx,ny));

}

dp[x][y] ++;

return dp[x][y];

}

Date August 18, 2015
Category LintCode
Comments No Comments

[LintCode] Longest Increasing Continuous subsequence

public int longestIncreasingContinuousSubsequence(int[] A) {
        // Write your code here
        if(A == null || A.length == 0)
            return 0;
        if(A.length == 1)// corn case;
            return 1;
        int count = 1;
        int max = 0;
        for(int i = 1; i < A.length; i++) {
            if(A[i] > A[i-1]){
                count++;
            }else{
                count = 1;
            }
            max = Math.max(max,count);
        }
        count = 1;
        for(int i = A.length - 1; i > 0; i--) {
            if(A[i] < A[i-1]){
                count++;
            }else{
                count = 1;
            }
            max = Math.max(max,count);
        }
        return max;
    }

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

public int longestIncreasingContinuousSubsequence(int[] A) {

// Write your code here

if(A == null || A.length == 0)

return 0;

if(A.length == 1)// corn case;

return 1;

int count = 1;

int max = 0;

for(int i = 1; i < A.length; i++) {

if(A[i] > A[i-1]){

count++;

}else{

count = 1;

}

max = Math.max(max,count);

}

count = 1;

for(int i = A.length - 1; i > 0; i--) {

if(A[i] < A[i-1]){

count++;

}else{

count = 1;

}

max = Math.max(max,count);

}

return max;

}

Date August 17, 2015
Category LintCode
Comments No Comments

[LintCode] Count and Say

public String countAndSay(int n) {
        // Write your code here
        String s = "1";
        for(int i = 1; i < n; i++) {
            StringBuffer sb = new StringBuffer();
            int count = 1;
            for(int j = 1; j < s.length(); j++) {
                if(s.charAt(j) == s.charAt(j-1))
                    count++;
                else{
                    sb.append(count);
                    sb.append(s.charAt(j-1));
                    count = 1;
                }
            }
            sb.append(count);
            sb.append(s.charAt(s.length()-1));
            s = sb.toString();
        }
        return s;
    }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

public String countAndSay(int n) {

// Write your code here

String s = "1";

for(int i = 1; i < n; i++) {

StringBuffer sb = new StringBuffer();

int count = 1;

for(int j = 1; j < s.length(); j++) {

if(s.charAt(j) == s.charAt(j-1))

count++;

else{

sb.append(count);

sb.append(s.charAt(j-1));

count = 1;

}

sb.append(count);

sb.append(s.charAt(s.length()-1));

s = sb.toString();

}

return s;

}

Date August 17, 2015
Category LintCode
Comments No Comments

[LintCode] Segment Tree Query II

public int query(SegmentTreeNode root, int start, int end) {
        // write your code here
        if(root == null || root.end < start || root.start  > end)
            return 0;
        if(root.start == root.end)
            return root.count;
        return query(root.left, start,end)+ query(root.right, start, end);
    }

1

2

3

4

5

6

7

8

public int query(SegmentTreeNode root, int start, int end) {

// write your code here

if(root == null || root.end < start || root.start > end)

return 0;

if(root.start == root.end)

return root.count;

return query(root.left, start,end)+ query(root.right, start, end);

}

Date August 16, 2015
Category LintCode
Comments No Comments

[LintCode] Segment Tree Query

public int query(SegmentTreeNode root, int start, int end) {
        // write your code here
        if(root == null || root.start > end || root.end < start)
            return 0;
        if(root.start == root.end)
            return root.max;
        return Math.max(query(root.left,start,end),query(root.right,start,end));
    }

1

2

3

4

5

6

7

8

public int query(SegmentTreeNode root, int start, int end) {

// write your code here

if(root == null || root.start > end || root.end < start)

return 0;

if(root.start == root.end)

return root.max;

return Math.max(query(root.left,start,end),query(root.right,start,end));

}

Date August 16, 2015
Category LintCode
Comments No Comments

[LintCode] Update Bits

Recover Rotated Sorted Array

Partition Array by Odd and Even

Binary Tree Paths

[LintCode] Copy Books

[LintCode] Longest Increasing Continuous subsequence II

[LintCode] Longest Increasing Continuous subsequence

[LintCode] Count and Say

[LintCode] Segment Tree Query II

[LintCode] Segment Tree Query

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

Categories

Tags