Wonion

4916

Wonion
7天前

### java 代码

class Solution {
public int longestSubstringWithoutDuplication(String s) {
Map<Character, Integer> map = new HashMap<>();   // 记录 字符索引的位置
int res = 0;
for(int i = 0, j = 0; i < s.length(); i ++)
{
if(map.containsKey(s.charAt(i)))            // 说明出现了重复的
j = Math.max(j, map.get(s.charAt(i)) + 1);
map.put(s.charAt(i), i);
res = Math.max(res, i - j + 1);
}
return res;
}
}


Wonion
13天前
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stk = new Stack<>();

while(root != null || stk.size() != 0)
{
while(root != null)
{
stk.push(root);
root = root.left;
}
root = stk.pop();
root = root.right;
}
return list;
}
}


Wonion
13天前
class LRUCache {
static Map<Integer, Node> map = new HashMap<>();
static int n;

public LRUCache(int capacity) {
n = capacity;
tail = new Node(-1, -1);
map.clear();
}

public int get(int key) {
if(!map.containsKey(key)) return -1;
Node p = map.get(key);
remove(p);
insert(p);
return p.val;
}

public void put(int key, int value) {
if(map.containsKey(key))       //更新操作
{
Node p = map.get(key);
p.val = value;
remove(p);
insert(p);
}
else
{
if(map.size() == n)      //超出容量
{
Node p = tail.left;
remove(p);
map.remove(p.key);
}
Node p = new Node(key, value);
insert(p);
map.put(key, p);
}
}

private static void remove(Node p)
{
p.right.left = p.left;
p.left.right = p.right;
}

private static void insert(Node p)
{
}
}

class Node
{
int key, val;
Node left, right;
Node (int key, int val)
{
this.key = key;
this.val = val;
}
}

/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/


Wonion
13天前
class Solution {
public int findKthLargest(int[] nums, int k) {
int res = quick_sort(nums, 0, nums.length - 1, k - 1);
return res;
}

private static int quick_sort(int[] nums, int l, int r, int k)
{
if(l >= r) return nums[r];
int mid = nums[l + r >> 1];
int i = l - 1, j = r + 1;
while(i < j)
{
do i ++; while(nums[i] > mid);
do j --; while(nums[j] < mid);
if(i < j)
{
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
if(k <= j) return quick_sort(nums, l, j, k);
else return quick_sort(nums, j + 1, r, k);
}
}


Wonion
19天前
class Solution {
public void setZeroes(int[][] matrix) {

int n = matrix.length, m = matrix[0].length;      //n行m列
int r0 = 1, c0 = 1;
for(int i = 0; i < m; i ++)          //循环第0行
if(matrix[0][i] == 0)
r0 = 0;
for(int i = 0; i < n; i ++)          //循环第0列
if(matrix[i][0] == 0)
c0 = 0;

for(int i = 1; i < n; i ++)          //对于每一行循环每一列
for(int j = 0; j < m; j ++)
if(matrix[i][j] == 0)
matrix[i][0] = 0;
for(int i = 1; i < m; i ++)          //对于每一列循环每一行
for(int j = 0; j < n; j ++)
if(matrix[j][i] == 0)
matrix[0][i] = 0;
for(int i = 1; i < n; i ++)
if(matrix[i][0] == 0)
for(int j = 0; j < m; j ++)
matrix[i][j] = 0;
for(int i = 1; i < m; i ++)
if(matrix[0][i] == 0)
for(int j = 0; j < n; j ++)
matrix[j][i] = 0;
if(r0 == 0)
{
for(int i = 0; i < m; i ++) matrix[0][i] = 0;
}
if(c0 == 0)
{
for(int i = 0; i < n; i ++) matrix[i][0] = 0;
}

}
}


Wonion
19天前
/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;                   //如果不声明指针的话，dummy.next就到最后了
while(l1 != null && l2 != null)
{
if(l1.val <= l2.val)
{
cur.next = l1;
cur = cur.next;
l1 = l1.next;
}
else
{
cur.next = l2;
cur = cur.next;
l2 = l2.next;
}
}

if(l1 != null) cur.next = l1;
else if(l2 != null) cur.next = l2;

return dummy.next;
}
}


Wonion
22天前
import java.util.Scanner;

public class Main{
static int N = 110;

public static void main(String[] args){

Scanner in = new Scanner(System.in);

int n = in.nextInt();
int m = in.nextInt();

int[][] a = new int[N][N];
for(int i = 0; i < n; i ++)
for(int j = 0; j < m; j ++)
a[i][j] = in.nextInt();

for(int i = 0; i < m; i ++)
{
for(int j = n - 1; j >= 0; j --)
System.out.print(a[j][i] + " ");
System.out.println();
}
}
}


Wonion
23天前

### 算法详解

1：两个数做^运算，得到各位相加不进位的计算结果

2：两个数做&运算，得到进位，(因为&是11得1，只有两位都是1时，才会进位)，因为进位是要加到左一位的，所以需要左移1

3：因为可能有些位数加上进位后还要进位，所以要迭代直到进位为0

### 知识点

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10 //进位余0

1 - 0 = 1
1 - 1 = 0
0 - 0 = 0
0 - 1 = 1 //借2余1

### java代码

class Solution {
public int add(int num1, int num2) {
while(num2 != 0)
{
int sum = num1 ^ num2;
int carry = (num1 & num2) << 1;
num1 = sum;
num2 = carry;
}
return num1;
}
}


Wonion
23天前
class Solution {
public int add(int num1, int num2) {
while(num2 != 0)
{
int sum = num1 ^ num2;                //两数相加不进位的计算结果
int carry = (num1 & num2) << 1;       //进位
num1 = sum;
num2 = carry;
}
return num1;
}
}


Wonion
23天前
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int res = 0;
for(int i = 0; i < 32; i ++)
{
if((n >> i & 1) == 1) res ++;
}
return res;
}
}